The Santa Claus problem
Nikhil Bansal, Maxim Sviridenko
STOC 2006
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.
Nikhil Bansal, Maxim Sviridenko
STOC 2006
David Gamarnik, Maxim Sviridenko
Discrete Applied Mathematics
Tracy Kimbrel, Baruch Schieber, et al.
Journal of Scheduling
Moshe Lewenstein, Maxim Sviridenko
SODA 1998