Makespan minimization in job shops: A linear time approximation scheme

In this paper we present a linear time approximation scheme for the job shop scheduling problem with a fixed number of machines and fixed number of operations per job. This improves on the previously best 2 + epsilon, epsilon > 0, approximation algorithm for the problem by Shmoys, Stein, and Wein [SIAM J. Comput., 23 (1994), pp. 617-632]. Our approximation scheme is very general and it can be extended to the case of job shop scheduling problems with release and delivery times, multistage job shops, dag job shops, and preemptive variants of most of these problems.