• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Polynomial algorithm for the scheduling problem $1|pmtn, p=2, r_j=j-1, w_j \leq w_{j+1}| \sum{w_j c_j}$

P. 25-28.
Lazarev A. A., Arkhipov D. I.

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.