Job shop scheduling with unit processing times

ABSTRACT

We consider randomized algorithms for the preemptive job shop problem, or equivalently, the case in which all operations have unit length. We give an α-approximation for the case of two machines where α < 1.45, an improved approximation ratio of O(log m/log log m) for an arbitrary number m of machines, and the first (2+ε)-approximation for a constant number of machines. The first result is via an approximation algorithm for a string matching problem which is of independent interest.

REFERENCES

• 1: S. B. Akers, A graphical approach to production scheduling problems, Operations Research 4 (1956), 244--245.
• 2: N. Alon, and J. Spencer, The Probabilistic Method. John Wiley & Sons, 2000.
• 3: Tighter bounds on preemptive job shop scheduling with two machines, Computing, v.67 n.1, p.83-90, July 2001 [doi>10.1007/s006070170017]
• 4: P. Baptiste, J. Carlier, A. Kononov, M. Queyranne, S. Sevastianov and M. Sviridenko, Structural Properties of Preemptive Schedules, submitted for publication.
• 5: Artur Czumaj , Christian Scheideler, A new algorithm approach to the general Lovász local lemma with applications to scheduling and satisfiability problems (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.38-47, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335310]
• 6: U. Feige and C. Scheideler, Improved bounds for acyclic job shop scheduling. Combinatorica 22 (2002), no. 3, 361--399.
• 7: Leslie Ann Goldberg , Mike Paterson , Aravind Srinivasan , Elizabeth Sweedyk, Better Approximation Guarantees for Job-Shop Scheduling, SIAM Journal on Discrete Mathematics, v.14 n.1, p.67-92, 2001 [doi>10.1137/S0895480199326104]
• 8: Gaston H. Gonnet, Expected Length of the Longest Probe Sequence in Hash Code Searching, Journal of the ACM (JACM), v.28 n.2, p.289-304, April 1981 [doi>10.1145/322248.322254]
• 9: T. Gonzalez and S. Sahni. Flowshop and job-shop schedules: complexity and approximation. Operations Research 26, pp. 36--52, 1978.
• 10: Klaus Jansen , Roberto Solis-Oba , Maxim Sviridenko, Makespan Minimization in Job Shops: A Linear Time Approximation Scheme, SIAM Journal on Discrete Mathematics, v.16 n.2, p.288-300, 2003 [doi>10.1137/S0895480199363908]
• 11: E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and Scheduling: Algorithms and Complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin (eds.), Logistics of Production and Inventory, Handbooks in Operations Research and Management Science 4, North-Holland, Amsterdam, 1993, 445--522.
• 12: F. T. Leighton, B. Maggs, and S. Rao. Packet routing and jobshop scheduling in O(congestion + dilation) steps. Combinatorica 14, pp. 167--186, 1994.
• 13: F. T. Leighton, B. M. Maggs, and A. W. Richa, Fast algorithms for finding O(congestion + dilation) packet routing schedules. Combinatorica19 (1999) 375--401.
• 14: Martin Raab , Angelika Steger, "Balls into Bins" - A Simple and Tight Analysis, Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, p.159-170, October 08-10, 1998
• 15: S. V. Sevastianov , G. J. Woeginger, Makespan minimization in preemptive two machine job shops, Computing, v.60 n.1, p.73-79, 1998 [doi>10.1007/BF02684330]
• 16: S. V. Sevast'janov, On some geometric methods in scheduling theory: a survey, Discrete Applied Mathematics, v.55 n.1, p.59-82, Oct. 28, 1994 [doi>10.1016/0166-218X(94)90036-1]
• 17: S. Sevastianov, Bounding algorithm for the routing problem with arbitrary paths and alternative servers, Cybernetics 22 (1986), pp. 773--780.
• 18: Yu. N. Sotskov , N. V. Shakhlevich, NP-hardness of shop-scheduling problems with three jobs, Discrete Applied Mathematics, v.59 n.3, p.237-266, May 26, 1995 [doi>10.1016/0166-218X(93)E0169-Y]
• 19: David B. Shmoys , Clifford Stein , Joel Wein, Improved Approximation Algorithms for Shop Scheduling Problems, SIAM Journal on Computing, v.23 n.3, p.617-632, June 1994 [doi>10.1137/S009753979222676X]
• 20: D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov and D. B. Shmoys, Short shop schedules, Operation Research 45 (1997), pp. 288--294.