@book{24f1365b6ac141a4b13fc5bf7d3f43b6,

title = "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$",

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.",

keywords = "MSC-90B35, IR-65753, EWI-3386",

author = "Peter Brucker and Hurink, {Johann L.} and Sigrid Knust",

note = "Imported from MEMORANDA",

year = "2001",

language = "English",

series = "Memorandum / Department of Applied Mathematics",

publisher = "University of Twente, Faculty of Mathematical Sciences",

number = "1566",

}