A polynomial algorithm for P | p j=1, r j, outtree | ∑ C j

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 ∑ 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 & Timkovsky [1]. Copyright Springer-Verlag Berlin Heidelberg 2003