Abstract
We study several combinatorial optimization problems which combine the classic shop scheduling problems (open shop scheduling or job shop scheduling) and the shortest path problem. The objective of the considered problem is to select a subset of jobs that forms a feasible solution of the shortest path problem, and to execute the selected jobs on the open shop or job shop machines such that the makespan is minimized. We show that these problems are \(\mathrm {NP}\)-hard even if the number of machines is two, and they cannot be approximated within a factor of less than 2 if the number of machines is an input unless \(\mathrm {P}=\mathrm {NP}\). We present several approximation algorithms for these problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Aissi, H., Bazgan, C., Vanderpooten, D.: Approximating min-max (regret) versions of some polynomial problems. In: Chen, D.Z., Lee, D.T. (eds.) COCOON 2006. LNCS, vol. 4112, pp. 428–438. Springer, Heidelberg (2006)
Bárány, I., Fiala, T.: Többgépes ütemezési problémák közel optimális megoldása (in Hungarian). Szigma - Matematikai - Közgazdasági Folyóirat 15, 177–191 (1982)
Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)
Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery 23, 665–679 (1976)
Jackson, J.R.: An extension of Johnson’s results on job-lot scheduling. Naval Research Logistics Quarterly 3, 201–203 (1956)
Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: A linear time approximation scheme. SIAM Journal on Discrete Mathematics 16, 288–300 (2003)
Johnson, S.M.: Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, 61–68 (1954)
Lenstra, J.K., Kan, A.R., Brucker, P.: Complexity of machine scheduling problems. Annals of Operations Research 1, 343–362 (1977)
Lenstra, J.K., Rinnooy Kan, A.: Computational complexity of discrete optimization. Annals of Operations Research 4, 121–140 (1979)
Mastrolilli, M., Svensson, O.: Hardness of approximating flow and job shop scheduling problems. Journal of the Association for Computing Machinery 58, 20:1–20:32 (2011)
Nip, K., Wang, Z.: Combination of two-machine flow shop scheduling and shortest path problems. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 680–687. Springer, Heidelberg (2013)
Nip, K., Wang, Z., Talla Nobibon, F., Leus, R.: A Combination of Flow Shop Scheduling and the Shortest Path Problem. Journal of Combinatorial Optimization 29, 36–52 (2015)
Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics 8, 223–250 (1995)
Sevastianov, S.V., Woeginger, G.J.: Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming 82, 191–198 (1998)
Shmoys, D.B., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM Journal on Computing 23, 617–632 (1994)
Wang, Z., Cui, Z.: Combination of parallel machine scheduling and vertex cover. Theoretical Computer Science 460, 10–15 (2012)
Williamson, D.P., Hall, L.A., Hoogeveen, J.A., Hurkens, C.A.J., Lenstra, J.K., Sevast’janov, S.V., Shmoys, D.B.: Short shop schedules. Operations Research 45, 288–294 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Nip, K., Wang, Z., Xing, W. (2015). Combinations of Some Shop Scheduling Problems and the Shortest Path Problem: Complexity and Approximation Algorithms. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)