{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:30:17Z","timestamp":1759847417811},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,7,22]],"date-time":"2011-07-22T00:00:00Z","timestamp":1311292800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s10951-011-0243-z","type":"journal-article","created":{"date-parts":[[2011,7,21]],"date-time":"2011-07-21T10:36:13Z","timestamp":1311244573000},"page":"427-446","source":"Crossref","is-referenced-by-count":9,"title":["A Complete 4-parametric complexity classification of short shop scheduling problems"],"prefix":"10.1007","volume":"15","author":[{"given":"Alexander","family":"Kononov","sequence":"first","affiliation":[]},{"given":"Sergey","family":"Sevastyanov","sequence":"additional","affiliation":[]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,7,22]]},"reference":[{"issue":"4","key":"243_CR1","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1287\/moor.1050.0155","volume":"30","author":"N. Bansal","year":"2005","unstructured":"Bansal, N., Mahdian, M., & Sviridenko, M. (2005). Minimizing makespan in no-wait job shops. Mathematics of Operations Research, 30(4), 817\u2013831.","journal-title":"Mathematics of Operations Research"},{"issue":"5","key":"243_CR2","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1016\/j.dam.2010.11.015","volume":"159","author":"P. Baptiste","year":"2011","unstructured":"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\u2013280.","journal-title":"Discrete Applied Mathematics"},{"key":"243_CR3","unstructured":"Brucker, P., & Knust, S. (2000). Operations research: Complexity results of scheduling problems, http:\/\/www.mathematik.uni-osnabrueck.de\/research\/OR\/class\/ ."},{"issue":"2","key":"243_CR4","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1287\/mnsc.35.2.164","volume":"35","author":"J. Carlier","year":"1989","unstructured":"Carlier, J., & Pinson, E. (1989). An algorithm for solving the job-shop problem. Management Science, 35(2), 164\u2013176.","journal-title":"Management Science"},{"key":"243_CR5","first-page":"21","volume-title":"Handbook of combinatorial optimization","author":"B. Chen","year":"1998","unstructured":"Chen, B., Potts, C., & Woeginger, G. (1998). A review of machine scheduling: complexity, algorithms and approximability. In Handbook of combinatorial optimization (Vol.\u00a03, pp. 21\u2013169). Boston: Kluwer Academic."},{"issue":"1","key":"243_CR6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s004930170002","volume":"21","author":"R. Cole","year":"2001","unstructured":"Cole, R., Ost, K., & Schirra, S. (2001). Edge-coloring bipartite multigraphs in O(Elog\u2009D) time. Combinatorica, 21(1), 5\u201312.","journal-title":"Combinatorica"},{"key":"243_CR7","series-title":"SIAM monographs on discrete mathematics and applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity classifications of Boolean constraint satisfaction problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., & Sudan, M. (2001). Complexity classifications of Boolean constraint satisfaction problems. SIAM monographs on discrete mathematics and applications. Philadelphia: SIAM."},{"key":"243_CR8","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1023\/A:1018982630730","volume":"92","author":"I. G. Drobouchevitch","year":"1999","unstructured":"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\u2013214.","journal-title":"Annales of Operations Research"},{"key":"243_CR9","first-page":"225","volume-title":"Industrial scheduling","author":"H. Fisher","year":"1963","unstructured":"Fisher, H., & Thompson, G.\u00a0L. (1963). Probabilistic learning combinations of local job-shop scheduling rules. In J. F. Muth & G.\u00a0L. Thompson (Eds.), Industrial scheduling (pp. 225\u2013551). Englewood Cliffs: Prentice-Hall."},{"key":"243_CR10","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1137\/0211009","volume":"11","author":"H. Gabow","year":"1982","unstructured":"Gabow, H., & Kariv, O. (1982). Algorithms for edge coloring bipartite graphs and multigraphs. SIAM Journal of Computing, 11, 117\u2013129.","journal-title":"SIAM Journal of Computing"},{"key":"243_CR11","series-title":"A series of books in the mathematical sciences","volume-title":"Computers and intractability. A\u00a0guide to the theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., & Johnson, D. (1979). Computers and intractability. A\u00a0guide to the theory of NP-completeness. A series of books in the mathematical sciences. San Francisco: Freeman."},{"key":"243_CR12","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1109\/TC.1979.1675246","volume":"28","author":"T. Gonzalez","year":"1979","unstructured":"Gonzalez, T. (1979). A note on open shop preemptive schedules, Unit execution time shop problems. IEEE Transactions on Computing, 28, 782\u2013786.","journal-title":"IEEE Transactions on Computing"},{"issue":"4","key":"243_CR13","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T. Gonzalez","year":"1976","unstructured":"Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23(4), 665\u2013679.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"3","key":"243_CR14","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0167-6377(94)90024-8","volume":"16","author":"J. Hoogeveen","year":"1994","unstructured":"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\u2013137.","journal-title":"Operations Research Letters"},{"issue":"3","key":"243_CR15","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1002\/nav.3800030307","volume":"3","author":"J. Jackson","year":"1956","unstructured":"Jackson, J. (1956). An extension of Jhonson\u2019s results on job lot scheduling. Navel Research Logistics Quartely, 3(3), 201\u2013203.","journal-title":"Navel Research Logistics Quartely"},{"issue":"4","key":"243_CR16","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., & Gyssens, M. (1997). Closure properties of constraints. Journal of ACM, 44(4), 527\u2013548.","journal-title":"Journal of ACM"},{"issue":"4","key":"243_CR17","first-page":"59","volume":"7","author":"K. N. Kashyrskikh","year":"2000","unstructured":"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\u201377 [in\u00a0Russian].","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1"},{"issue":"1","key":"243_CR18","first-page":"23","volume":"8","author":"K. N. Kashyrskikh","year":"2001","unstructured":"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\u201339 [in\u00a0Russian].","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1"},{"key":"243_CR19","first-page":"104","volume":"34","author":"D. K\u00f6nig","year":"1916","unstructured":"K\u00f6nig, D. (1916). Graphok \u00e9s alkalmaz\u00e1suk a determin\u00e1nsok \u00e9s a halmazok elm\u00e9let\u00e9re. Mathematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtesit\u00f6, 34, 104\u2013119. [German translation: \u00dcber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre, Mathematische Annalen, 77(1916), 453\u2013465.]","journal-title":"Mathematikai \u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtesit\u00f6"},{"issue":"2","key":"243_CR20","first-page":"21","volume":"7","author":"A. V. Kononov","year":"2000","unstructured":"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\u201346 [in\u00a0Russian].","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1"},{"key":"243_CR21","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-3-642-03351-3_22","volume-title":"Computer science\u2014theory and applications, 4th international computer science symposium in Russia, CSA 2009","author":"A. Kononov","year":"2009","unstructured":"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.\u00a05675. Computer science\u2014theory and applications, 4th international computer science symposium in Russia, CSA 2009, Novosibirsk, Russia, August 2009 (pp. 227\u2013236). Berlin: Springer. Proceedings"},{"key":"243_CR22","series-title":"Logistics of production and inventory","first-page":"445","volume-title":"Handbooks in operations research and management science","author":"E. L. Lawler","year":"1993","unstructured":"Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D.\u00a0B. (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\u2013522). Amsterdam: North-Holland."},{"issue":"1","key":"243_CR23","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J. K. Lenstra","year":"1978","unstructured":"Lenstra, J. K., & Rinnooy Kan, A. H. G. (1978). Complexity of scheduling under precedence constraints. Operations Research, 26(1), 22\u201335.","journal-title":"Operations Research"},{"key":"243_CR24","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J. K. Lenstra","year":"1977","unstructured":"Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annales of Discrete Mathematics, 1, 343\u2013362.","journal-title":"Annales of Discrete Mathematics"},{"issue":"3","key":"243_CR25","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J. Lenstra","year":"1990","unstructured":"Lenstra, J., Shmoys, D., & Tardos, E. (1990). Approximation algorithms for scheduling unrelated parallel machines. Mathematical Programming, Ser. A, 46(3), 259\u2013271.","journal-title":"Mathematical Programming, Ser. A"},{"key":"243_CR26","volume-title":"Handbook of scheduling. Algorithms, models, and performance analysis","year":"2004","unstructured":"Leung, J. Y.-T. (Ed.) (2004). Handbook of scheduling. Algorithms, models, and performance analysis. Boca Raton: Chapman & Hall\/CRC Computer and Information Science Series."},{"issue":"2","key":"243_CR27","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/S0166-218X(85)80007-X","volume":"11","author":"T. Masuda","year":"1985","unstructured":"Masuda, T., Ishii, H., & Nishida, T. (1985). The mixed shop scheduling problem. Discrete Applied Mathematics, 11(2), 175\u2013186.","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"243_CR28","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1002\/(SICI)1097-0118(199908)31:4<267::AID-JGT1>3.0.CO;2-D","volume":"31","author":"L. Melnikov","year":"1999","unstructured":"Melnikov, L., & Vizing, V. (1999). The edge chromatic number of a directed\/mixed multigraph. Journal of Graph Theory, 31(4), 267\u2013273.","journal-title":"Journal of Graph Theory"},{"key":"243_CR29","first-page":"53","volume":"31","author":"J. Neumytov","year":"1993","unstructured":"Neumytov, J., & Sevastianov, S. (1993). An approximation algorithm with best possible bound for the counter routs problem with three machines. Upravlyaemye Sistemy, 31, 53\u201365 [in\u00a0Russian].","journal-title":"Upravlyaemye Sistemy"},{"key":"243_CR30","first-page":"216","volume":"1978","author":"T. J. Schaefer","year":"1978","unstructured":"Schaefer, T. J. (1978). The complexity of satisfiability problems. STOC, 1978, 216\u2013226.","journal-title":"STOC"},{"key":"243_CR31","series-title":"Algorithms and combinatorics","volume-title":"Combinatorial optimization. Polyhedra and efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A. (2003). Combinatorial optimization. Polyhedra and efficiency. Algorithms and combinatorics (Vol.\u00a024B). Berlin: Springer."},{"issue":"2","key":"243_CR32","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/j.ejor.2004.04.009","volume":"165","author":"S. Sevastianov","year":"2005","unstructured":"Sevastianov, S. (2005). An introduction to multi-parameter complexity analysis of discrete problems. European Journal of Operational Research, 165(2), 387\u2013397.","journal-title":"European Journal of Operational Research"},{"key":"243_CR33","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0377-2217(99)00161-7","volume":"120","author":"N. V. Shakhlevich","year":"2000","unstructured":"Shakhlevich, N. V., Sotskov, Y. N., & Werner, F. (2000). Complexity of mixed shop scheduling problems: a survey. European Journal of Operational Research, 120, 343\u2013351.","journal-title":"European Journal of Operational Research"},{"key":"243_CR34","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/S0377-2217(02)00767-1","volume":"149","author":"V. G. Timkovsky","year":"2003","unstructured":"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\u2013376.","journal-title":"European Journal of Operational Research"},{"issue":"4","key":"243_CR35","first-page":"36","volume":"6","author":"V. G. Vizing","year":"1999","unstructured":"Vizing, V. G. (1999). On a connected graph coloring in prescribed colors. Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 6(4), 36\u201343 [in Russian].","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1"},{"issue":"1","key":"243_CR36","first-page":"27","volume":"9","author":"V. G. Vizing","year":"2002","unstructured":"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\u201341 [in Russian].","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1"},{"issue":"1","key":"243_CR37","first-page":"17","volume":"15","author":"V. G. Vizing","year":"2008","unstructured":"Vizing, V. G. (2008). On the coloring of incidentors in a partially ordered multigraph. Diskretnyi Analiz i Issledovanie Operatsii, 15(1), 17\u201322 [in Russian].","journal-title":"Diskretnyi Analiz i Issledovanie Operatsii"},{"issue":"2","key":"243_CR38","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"D. Williamson","year":"1997","unstructured":"Williamson, D., Hall, L., Hoogeveen, J., Hurkens, C., Lenstra, J. K., Sevastianov, S., & Shmoys, D. (1997). Short shop schedules. Operations Research, 45(2), 288\u2013294.","journal-title":"Operations Research"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-011-0243-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-011-0243-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-011-0243-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T05:39:46Z","timestamp":1559453986000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-011-0243-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,7,22]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["243"],"URL":"https:\/\/doi.org\/10.1007\/s10951-011-0243-z","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,7,22]]}}}