Article
Математическая формализация задач проектного планирования в расширенной постановке
Consideration was given to a graphic realization of the method of dynamic programming. Its concept was demonstrated by the examples of the partition and knapsack problems. The proposed method was compared with the existing algorithms to solve these problems.
In this paper, we consider the following scheduling problem. On the single machine need to process $n$ jobs. Job $j, j=1,\dots, n,$ characterized: release times $r_j = j - 1$; processing time $p_j = 2$; weight of jobs are non-decreasing $w_j \leq w_{j+1}$. The objective function is $\min{\sum\limits_{j=1}^n (w_j \cdot C_j)}$, where $C_i$ -- completion time.
In this paper, we consider the minimizing total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine. This problem is known to be open. Here, we give some properties of optimal schedules for the problem and its special cases.