A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$

P. Brucker, Johann L. Hurink, S. Knust

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)


A polynomial algorithm is proposed for two scheduling problems for which the complexity status was open. A set of jobs with unit processing times, release dates and outtree precedence relations has to be processed on parallel identical machines such that the total completion time $\sum C_j$ is minimized. It is shown that the problem can be solved in $O(n^2)$ time if no preemption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste and Timkovsky [1].
Original languageEnglish
Pages (from-to)407-412
Number of pages6
JournalMathematical methods of operations research
Issue number3
Publication statusPublished - 2002


  • EWI-6075
  • MSC-90B35
  • IR-63172


Dive into the research topics of 'A polynomial algorithm for $P | p_j = 1, r_j, outtree | \Sigma C_j$'. Together they form a unique fingerprint.

Cite this