A new approximation algorithm for unit execution time scheduling with chain-type precedence constraints

In this paper a new approximation algorithm with worst case performance ratio 3/2 is presented for the problem of scheduling unit execution time jobs on two parallel machines with the objective of minimizing the makespan where each job can be processed on only one machine and there are chain-type precedence constraints in the jobs. This result answers an open problem in Jansen et al. ‘Does there exist a polynomial time heuristic with worst-case guarantee better than 5/3 for the problem U2Chain?’. The new approximation algorithm is also applied to the problem J2|pmtn|Cmax.