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

Peter Brucker, Johann L. Hurink, Sigrid Knust

Research output: Book/ReportReportOther research output

67 Downloads (Pure)

Abstract

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.
Original languageEnglish
Place of PublicationEnschede
PublisherUniversity of Twente
Publication statusPublished - 2001

Publication series

NameMemorandum / Department of Applied Mathematics
PublisherUniversity of Twente, Faculty of Mathematical Sciences
No.1566
ISSN (Print)0169-2690

Fingerprint

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

Cite this