A polynomial algorithm for P|pj = 1, rj, outtree |ΣCj

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 ΣCj is minimized. It is shown that the problem can be solved in O(n²) 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.