A polynomial algorithm for P vertical bar p(j)=1, r(j), outtree vertical bar 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 Sigma C-j is minimized. It is shown that the problem can be solved in O(n(2)) time if no pre-emption is allowed. Furthermore, it is proved that allowing preemption does not reduce the optimal objective value, which verifies a conjecture of Baptiste Timkovsky [1].