Abstract
We present a comprehensive complexity analysis of classical shop scheduling problems subject to various combinations of constraints imposed on the processing times of operations, the maximum number of operations per job, the upper bound on schedule length, and the problem type (taking values “open shop,” “job shop,” “mixed shop”). It is shown that in the infinite class of such problems there exists a finite basis system that allows one to easily determine the complexity of any problem in the class. The basis system consists of ten problems, five of which are polynomially solvable, and the other five are NP-complete. (The complexity status of two basis problems was known before, while the status of the other eight is determined in this paper.) Thereby the dichotomy property of that parameterized class of problems is established. Since one of the parameters is the bound on schedule length (and the other two numerical parameters are tightly related to it), our research continues the research line on complexity analysis of short shop scheduling problems initiated for the open shop and job shop problems in the paper by Williamson et al. (Oper. Res. 45(2):288–294, 1997). We improve on some results of that paper.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Bansal, N., Mahdian, M., & Sviridenko, M. (2005). Minimizing makespan in no-wait job shops. Mathematics of Operations Research, 30(4), 817–831.
Baptiste, P., Carlier, J., Kononov, A., Queyranne, M., Sevastyanov, S., & Sviridenko, M. (2011). Integrality property in preemptive shop scheduling. Discrete Applied Mathematics, 159(5), 272–280.
Brucker, P., & Knust, S. (2000). Operations research: Complexity results of scheduling problems, http://www.mathematik.uni-osnabrueck.de/research/OR/class/.
Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35(2), 164–176.
Chen, B., Potts, C., & Woeginger, G. (1998). A review of machine scheduling: complexity, algorithms and approximability. In Handbook of combinatorial optimization (Vol. 3, pp. 21–169). Boston: Kluwer Academic.
Cole, R., Ost, K., & Schirra, S. (2001). Edge-coloring bipartite multigraphs in O(Elog D) time. Combinatorica, 21(1), 5–12.
Creignou, N., Khanna, S., & Sudan, M. (2001). Complexity classifications of Boolean constraint satisfaction problems. SIAM monographs on discrete mathematics and applications. Philadelphia: SIAM.
Drobouchevitch, I. G., & Strusevich, V. A. (1999). A polynomial algorithm for the three-machine open shop with a bottleneck machine. Annales of Operations Research, 92, 185–214.
Fisher, H., & Thompson, G. L. (1963). Probabilistic learning combinations of local job-shop scheduling rules. In J. F. Muth & G. L. Thompson (Eds.), Industrial scheduling (pp. 225–551). Englewood Cliffs: Prentice-Hall.
Gabow, H., & Kariv, O. (1982). Algorithms for edge coloring bipartite graphs and multigraphs. SIAM Journal of Computing, 11, 117–129.
Garey, M., & Johnson, D. (1979). Computers and intractability. A guide to the theory of NP-completeness. A series of books in the mathematical sciences. San Francisco: Freeman.
Gonzalez, T. (1979). A note on open shop preemptive schedules, Unit execution time shop problems. IEEE Transactions on Computing, 28, 782–786.
Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23(4), 665–679.
Hoogeveen, J., Lenstra, J. K., & Veltman, B. (1994). Three, four, five, six, or the complexity of scheduling with communication delays. Operations Research Letters, 16(3), 129–137.
Jackson, J. (1956). An extension of Jhonson’s results on job lot scheduling. Navel Research Logistics Quartely, 3(3), 201–203.
Jeavons, P., Cohen, D., & Gyssens, M. (1997). Closure properties of constraints. Journal of ACM, 44(4), 527–548.
Kashyrskikh, K. N., Sevastianov, S. V., & Tchernykh, I. D. (2000). Four-parametric complexity analysis of the open shop problem. Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1, 7(4), 59–77 [in Russian].
Kashyrskikh, K. N., Kononov, A. V., Sevastianov, S. V., & Tchernykh, I. D. (2001). Polynomially solvable case of the 2-stage 3-machine open shop problem. Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1, 8(1), 23–39 [in Russian].
König, D. (1916). Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. Mathematikai és Természettudományi Értesitö, 34, 104–119. [German translation: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, 77(1916), 453–465.]
Kononov, A. V., & Sevastianov, S. V. (2000). On the complexity of the connected list vertex-coloring problem. Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1, 7(2), 21–46 [in Russian].
Kononov, A., Sevastianov, S., & Sviridenko, M. (2009). Complete complexity classification of short shop scheduling. In A. Frid et al. (Eds.), Lecture notes in computer science: Vol. 5675. Computer science—theory and applications, 4th international computer science symposium in Russia, CSA 2009, Novosibirsk, Russia, August 2009 (pp. 227–236). Berlin: Springer. Proceedings
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling: algorithms and complexity. In S. Graves, A. H. G. Rinnooy Kan, & P. Zipkin (Eds.), Logistics of production and inventory: Vol. 4. Handbooks in operations research and management science (pp. 445–522). Amsterdam: North-Holland.
Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26(1), 22–35.
Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annales of Discrete Mathematics, 1, 343–362.
Lenstra, J., Shmoys, D., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, Ser. A, 46(3), 259–271.
Leung, J. Y.-T. (Ed.) (2004). Handbook of scheduling. Algorithms, models, and performance analysis. Boca Raton: Chapman & Hall/CRC Computer and Information Science Series.
Masuda, T., Ishii, H., & Nishida, T. (1985). The mixed shop scheduling problem. Discrete Applied Mathematics, 11(2), 175–186.
Melnikov, L., & Vizing, V. (1999). The edge chromatic number of a directed/mixed multigraph. Journal of Graph Theory, 31(4), 267–273.
Neumytov, J., & Sevastianov, S. (1993). An approximation algorithm with best possible bound for the counter routs problem with three machines. Upravlyaemye Sistemy, 31, 53–65 [in Russian].
Schaefer, T. J. (1978). The complexity of satisfiability problems. STOC, 1978, 216–226.
Schrijver, A. (2003). Combinatorial optimization. Polyhedra and efficiency. Algorithms and combinatorics (Vol. 24B). Berlin: Springer.
Sevastianov, S. (2005). An introduction to multi-parameter complexity analysis of discrete problems. European Journal of Operational Research, 165(2), 387–397.
Shakhlevich, N. V., Sotskov, Y. N., & Werner, F. (2000). Complexity of mixed shop scheduling problems: a survey. European Journal of Operational Research, 120, 343–351.
Timkovsky, V. G. (2003). Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity. European Journal of Operational Research, 149, 355–376.
Vizing, V. G. (1999). On a connected graph coloring in prescribed colors. Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 6(4), 36–43 [in Russian].
Vizing, V. G. (2002). A bipartite interpretation of a directed multigraph in problems of the coloring of incidentors. Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 9(1), 27–41 [in Russian].
Vizing, V. G. (2008). On the coloring of incidentors in a partially ordered multigraph. Diskretnyi Analiz i Issledovanie Operatsii, 15(1), 17–22 [in Russian].
Williamson, D., Hall, L., Hoogeveen, J., Hurkens, C., Lenstra, J. K., Sevastianov, S., & Shmoys, D. (1997). Short shop schedules. Operations Research, 45(2), 288–294.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper was published in Kononov et al. (2009).
Rights and permissions
About this article
Cite this article
Kononov, A., Sevastyanov, S. & Sviridenko, M. A Complete 4-parametric complexity classification of short shop scheduling problems. J Sched 15, 427–446 (2012). https://doi.org/10.1007/s10951-011-0243-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-011-0243-z