Scheduling a dag on two machines with release times to minimize total completion time

We consider the scheduling situation where a set of unit execution time jobs have to be scheduled on two machines. Jobs have release dates and there are some precedence constraints between them. The objective is to minimize the total completion time. When the graph of precedence constraints is an out-tree, the problem is known to be solvable in polynomial time. In this talk, we show that this result can be extended for any directed acyclic graph. Our algorithm is based on a dynamic programming formulation of the problem combined with Garey and Johnson's algorithm for the maximum completion time criterion.

B.Hammer