{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T02:46:12Z","timestamp":1771469172389,"version":"3.50.1"},"reference-count":38,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["European Journal of Operational Research"],"published-print":{"date-parts":[[2000,1]]},"DOI":"10.1016\/s0377-2217(99)00161-7","type":"journal-article","created":{"date-parts":[[2003,4,5]],"date-time":"2003-04-05T00:21:01Z","timestamp":1049502061000},"page":"343-351","source":"Crossref","is-referenced-by-count":39,"title":["Complexity of mixed shop scheduling problems: A survey"],"prefix":"10.1016","volume":"120","author":[{"given":"Natalia V.","family":"Shakhlevich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri N.","family":"Sotskov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Werner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0377-2217(99)00161-7_BIB1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1287\/opre.3.4.429","article-title":"A non-numerical approach to production scheduling problems","volume":"3","author":"Akers","year":"1955","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB2","doi-asserted-by":"crossref","unstructured":"J.O. Achugbue, F.Y. Chin, Scheduling the open shop to minimize mean flow time, SIAM Journal of Computing 11 (4) (1982) 709\u2013720","DOI":"10.1137\/0211058"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB3","first-page":"19","article-title":"Scheduling a partially ordered set of jobs for a class of serving systems, Izvestiya Akademii Nauk BSSR","volume":"3","author":"Borodich","year":"1986","journal-title":"Seriya Fiziko-matematicheskikh Nauk (in Russian)"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB4","unstructured":"S.A. Borodich, A.V. Tuzikov, On the complexity of construction time-optimal schedules for some two-stage service systems with non-fixed routes, in: Methods, Algorithms, and Programs for the Solution of Extremal Problems (in Russian), Minsk, Institute of Engineering Cybernetics, 1985, 76\u201385"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB5","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1007\/BF02276919","article-title":"An efficient algorithm for the job-shop problem with two jobs","volume":"40","author":"Brucker","year":"1988","journal-title":"Computing"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB6","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01719698","article-title":"A polynomial algorithm for the two machine job-shop scheduling problem with fixed number of jobs","volume":"16","author":"Brucker","year":"1994","journal-title":"OR Spektrum"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB7","doi-asserted-by":"crossref","unstructured":"P. Brucker, Scheduling Algorithms, Springer, Berlin, 1995, p. 326","DOI":"10.1007\/978-3-662-03088-2"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB8","unstructured":"P. Brucker, S.A. Kravchenko, Y.N. Sotskov, Preemptive job-shop scheduling problems with a fixed number of jobs, Osnabr\u00fccker Schriften zur Mathematik, Reihe P, Heft 184, Zeitschrift f\u00fcr Operations Research (1996) 47"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01539799","article-title":"On the complexity of two machine job shop scheduling with regular objective functions","volume":"19","author":"Brucker","year":"1997","journal-title":"OR Spektrum"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB10","doi-asserted-by":"crossref","unstructured":"Y. Cho, S. Sahni, Preemptive scheduling of independent jobs with release and due times in open, flow and job shops, Operations Research 29 (3) (1981) 511\u2013522","DOI":"10.1287\/opre.29.3.511"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB11","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jagm.1993.1002","article-title":"Minimizing mean flow time in two-machine open shops and flow shops","volume":"14","author":"Du","year":"1993","journal-title":"Journal of Algorithms"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB12","doi-asserted-by":"crossref","unstructured":"M.R. Garey, D.S. Johnson, R. Sethi, The complexity of flow shop and job shop scheduling, Mathematics of Operations Research 1 (2) (1976) 117\u2013129","DOI":"10.1287\/moor.1.2.117"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB13","doi-asserted-by":"crossref","unstructured":"T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time, Journal of the Association for Computing Machinery 23 (4) (1976) 665\u2013679","DOI":"10.1145\/321978.321985"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB14","doi-asserted-by":"crossref","unstructured":"T. Gonzalez, S. Sahni, Flow shop and job shop schedules: Complexity and approximation, Operations Research 26 (1) (1978) 36\u201352","DOI":"10.1287\/opre.26.1.36"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","article-title":"Optimization and approximation in deterministic sequencing and scheduling: A survey","volume":"5","author":"Graham","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB16","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1287\/opre.11.6.889","article-title":"A geometric model and graphical algorithm for a sequencing problem","volume":"11","author":"Hardgrave","year":"1963","journal-title":"Operations Research"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB17","doi-asserted-by":"crossref","unstructured":"J.R. Jackson, An extension of Johnson's result on job lot scheduling, Naval Research Logistics Quarterly 3 (3) (1956) 201\u2013203","DOI":"10.1002\/nav.3800030307"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB18","doi-asserted-by":"crossref","unstructured":"S.M. Johnson, Optimal two- and three-stage production schedules with set up times included, Naval Research Logistics Quarterly 1 (1) (1954) 61\u201368","DOI":"10.1002\/nav.3800010110"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB19","unstructured":"S.A. Kravchenko, Y.N. Sotskov, Complexity of the two machine job-shop scheduling problem with a fixed number of jobs, Central European Journal of Operations Research and Economics (1995)"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB20","first-page":"233","article-title":"Optimal makespan schedule for three jobs on two machines","volume":"43","author":"Kravchenko","year":"1996","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB21","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1287\/moor.6.1.153","article-title":"Minimizing maximum lateness in a two-machine open shop","volume":"6","author":"Lawler","year":"1981","journal-title":"Mathematics of Operations Research"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB22","doi-asserted-by":"crossref","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling algorithms and complexity, in: Handbooks in Operations Research and Management Science, vol. 4, Logistics of Production and Inventory, North-Holland, New York, 1993, pp. 452\u2013522","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB23","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/S0167-5060(08)70821-5","article-title":"Computational complexity of discrete optimization problems","volume":"4","author":"Lenstra","year":"1979","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB24","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","article-title":"Complexity of machine scheduling problems","volume":"1","author":"Lenstra","year":"1977","journal-title":"Annals of Discrete Mathematics"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB25","doi-asserted-by":"crossref","unstructured":"T. Masuda, H. Ishii, T. Nishida, The mixed shop scheduling problem, Discrete Applied Mathematics 11 (2) (1985) 175\u2013186","DOI":"10.1016\/S0166-218X(85)80007-X"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB26","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF02243393","article-title":"Scheduling two jobs with fixed and nonfixed routines","volume":"52","author":"Shakhlevich","year":"1994","journal-title":"Computing"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB27","unstructured":"N.V. Shakhlevich, Y.N. Sotskov, F. Werner, Shop-scheduling problems with fixed and non-fixed machine orders of the jobs, Preprint N 14, Otto-von-Guericke-Universit\u00e4t, Magdeburg, 1997, p. 30"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB28","unstructured":"N.V. Shakhlevich, V.A. Strusevich, Scheduling two jobs in a multi-machine open shop to minimize an arbitrary regular penalty function, Report 9125\/A, Econometric Institute, Erasmus University Rotterdam, The Netherlands, 1990, p. 24"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB29","unstructured":"Y.N. Sotskov, Optimal scheduling two jobs with regular criterion, in: Automatization of Design Processes (in Russian), Institute of Engineering Cybernetics, Minsk, Belarus, 1985, pp. 86\u201395"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB30","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1016\/0377-2217(91)90066-5","article-title":"The complexity of shop-scheduling problems with two or three jobs","volume":"53","author":"Sotskov","year":"1991","journal-title":"European Journal of Operational Research"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB31","doi-asserted-by":"crossref","unstructured":"Y.N. Sotskov, Two, three, many or the complexity of scheduling with fixed number of jobs, in: Operations Research Proceedings 1994, Springer, Berlin\u2013Heidelberg, 1995, pp. 168\u2013172","DOI":"10.1007\/978-3-642-79459-9_31"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB32","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0166-218X(93)E0169-Y","article-title":"NP-hardness of shop-scheduling problems with three jobs","volume":"59","author":"Sotskov","year":"1995","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1049\/ise.1994.0001","article-title":"Scheduling theory and practice: Minsk Group results","volume":"1","author":"Sotskov","year":"1994","journal-title":"Intelligent Systems Engineering"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB34","first-page":"88","article-title":"On nonhomogeneous two-stage deterministic processing systems","volume":"3","author":"Strusevich","year":"1989","journal-title":"Kibernetica (in Russian)"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB35","unstructured":"V.A. Strusevich, Complexity Aspects of Shop Scheduling Problems, Ph.D. Thesis, Erasmus University Rotterdam, Rotterdam, The Netherlands, 1991"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB36","doi-asserted-by":"crossref","unstructured":"V.A. Strusevich, Two machine super-shop scheduling problem, Journal of the Operational Research Society 42\/6 (1991) 479\u2013492","DOI":"10.1057\/jors.1991.96"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB37","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1023\/A:1018997431986","article-title":"Shop scheduling problems under precedence constraints","volume":"69","author":"Strusevich","year":"1997","journal-title":"Annals of Operations Research"},{"key":"10.1016\/S0377-2217(99)00161-7_BIB38","doi-asserted-by":"crossref","unstructured":"W. Szwarc, Solution of the Akers\u2013Friedman scheduling problem, Operations Research 8 (6) (1960) 782\u2013788","DOI":"10.1287\/opre.8.6.782"}],"container-title":["European Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221799001617?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0377221799001617?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,14]],"date-time":"2020-01-14T18:00:51Z","timestamp":1579024851000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0377221799001617"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["S0377221799001617"],"URL":"https:\/\/doi.org\/10.1016\/s0377-2217(99)00161-7","relation":{},"ISSN":["0377-2217"],"issn-type":[{"value":"0377-2217","type":"print"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}