UET-scheduling with chain-type precedence constraints

The authors consider a special case of the precedence constrained scheduling problem of n unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. They show that this problem is NP-complete in general, and the authors derive an approximation algorithm with constant worst case guarantee.