Abstract
Shop scheduling problems are known to be notoriously intractable, both in theory and practice. In this paper we give a randomized approximation algorithm for flow shop scheduling where the number of machines is part of the input problem. Our algorithm has a multiplicative factor of 2(1 + δ) and an additive term of O(m ln(m + n)p max )/δ2).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Leslie A. Goldberg, Mike Paterson, Aravind Srinivasan, and Elizabeth Sweedyk. Better approximation guarantees for job shop scheduling. In Proc. 8th ACM-SIAM Symp. on Discrete Algorithms(SODA), pages 599–608, 1997. 214
Leslie A. Hall. Approximability of flow shop scheduling. In Proc. 36th IEEE Annual Symp. on Foundations of Computer Science, pages 82–91, 1995. 214
S.M. Johnson. Optimal two-and three-stage procution schedules with setup times included. Naval Research Logistics Quarterly, 1:61–68, 1954. 213
J.P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-holding bounds for applications with limited independence. In Proc. 4th ACM-SIAM Symp. on Discrete Algorithms(SODA), pages 331–340, 1993. 214
S. Sevast’janov. Bounding algorithm for the routing problem with arbitrary paths and alternative servers. Cybernetics, 22:773–780, 1986. 214
S. Sevast’janov and G. Woeginger. Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming, 82(1-2), 1998. 214
D.B. Shmoys. Approximation algorithms for NP-Hard problems, chapter Cut problems and their applications to divide and conquer, pages 192–234. PWS, 1997. 215
D.B. Shmoys, C. Stein, and J. Wein. Improved approximation algorithms for shop scheduling problems. SIAM Journal of Computing, 23:617–632, 1994. 214
Maxim Sviridenko, K. Jansen, and R. Solis-Oba. Makespan minimization in job shops: A polynomial time approxmiation scheme. In Proc. 31st Annual ACM Symp. on Theory of Computing, pages 394–399, 1999. 214
D.P. Williamson, L.A. Hall, J.A. Hoogeveen, C.A.J. Hurkens, J.K. Lenstra, and S.V. Sevast’janov. Short shop schedules. Operations Research, 45:288–294, 1997. 214
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Garg, N., Jain, S., Swamy, C. (1999). A Randomized Algorithm for Flow Shop Scheduling. In: Rangan, C.P., Raman, V., Ramanujam, R. (eds) Foundations of Software Technology and Theoretical Computer Science. FSTTCS 1999. Lecture Notes in Computer Science, vol 1738. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46691-6_16
Download citation
DOI: https://doi.org/10.1007/3-540-46691-6_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66836-7
Online ISBN: 978-3-540-46691-8
eBook Packages: Springer Book Archive