Moshe Lewenstein, Maxim Sviridenko
SIAM Journal on Discrete Mathematics
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 + ε, ε > 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.
Moshe Lewenstein, Maxim Sviridenko
SIAM Journal on Discrete Mathematics
Nikhil Bansal, Don Coppersmiths, et al.
SIAM Journal on Computing
Don Coppersmith, David Gamarnik, et al.
SODA 2002
Marcin Bienkowski, Jarosław Byrka, et al.
Journal of Scheduling