{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T17:59:49Z","timestamp":1783792789491,"version":"3.55.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,2,6]],"date-time":"2007-02-06T00:00:00Z","timestamp":1170720000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2007,2,6]],"date-time":"2007-02-06T00:00:00Z","timestamp":1170720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2007,6]]},"DOI":"10.1007\/s00186-006-0127-8","type":"journal-article","created":{"date-parts":[[2007,2,5]],"date-time":"2007-02-05T12:13:47Z","timestamp":1170677627000},"page":"461-481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":38,"title":["Complexity of shop-scheduling problems with fixed number of jobs: a survey"],"prefix":"10.1007","volume":"65","author":[{"given":"Peter","family":"Brucker","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu N.","family":"Sotskov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Frank","family":"Werner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,2,6]]},"reference":[{"key":"127_CR1","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1287\/opre.4.2.244","volume":"4","author":"SB Akers","year":"1956","unstructured":"Akers SB (1956) A graphical approach to production scheduling problems. Oper Res 4:244\u2013245","journal-title":"Oper Res"},{"key":"127_CR2","first-page":"429","volume":"3","author":"SB Akers","year":"1956","unstructured":"Akers SB, Friedman J (1956) A non-numerical approach to production scheduling problems. Oper Res 3:429\u2013442","journal-title":"Oper Res"},{"key":"127_CR3","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, Reading"},{"key":"127_CR4","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF02276919","volume":"40","author":"P Brucker","year":"1988","unstructured":"Brucker P (1988) An efficient algorithm for the job-shop problem with two jobs. Computing 40:353\u2013359","journal-title":"Computing"},{"key":"127_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01719698","volume":"16","author":"P Brucker","year":"1994","unstructured":"Brucker P (1994) A polynomial algorithm for the two machine job-shop scheduling problem with a fixed number of jobs. Oper Res Spekt 16:5\u20137","journal-title":"Oper Res Spekt"},{"key":"127_CR6","unstructured":"Brucker P, Jurisch B, Meyer W (1989) Geometric methods for solving the job-shop scheduling problem. Preprint Heft 127, Fachbereich Mathematik\/Informatik, Universit\u00e4t Osnabr\u00fcck"},{"key":"127_CR7","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01719698","volume":"16","author":"P Brucker","year":"1994","unstructured":"Brucker P, Kravchenko SA, Sotskov YuN (1994) On the complexity of two machine job-shop scheduling with regular objective functions. Oper Res Spect 16:5\u20137","journal-title":"Oper Res Spect"},{"key":"127_CR8","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/PL00020906","volume":"49","author":"P Brucker","year":"1999","unstructured":"Brucker P, Kravchenko SA, Sotskov YuN (1999) Preemptive job-shop scheduling problems with a fixed number of jobs. Math Methods Oper Res 49:41\u201376","journal-title":"Math Methods Oper Res"},{"key":"127_CR9","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF02238804","volume":"45","author":"P Brucker","year":"1990","unstructured":"Brucker P, Schlie R (1990) Job-shop scheduling with multipurpose machines. Computing, 45:369\u2013375","journal-title":"Computing,"},{"key":"127_CR10","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T Gonzalez","year":"1976","unstructured":"Gonzalez T, Sahni A (1976) Open shop scheduling to minimize finish time. J Associat Comput Mach 23:665\u2013679","journal-title":"J Associat Comput Mach"},{"key":"127_CR11","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1287\/opre.11.6.889","volume":"11","author":"WH Hardgrave","year":"1963","unstructured":"Hardgrave WH, Nemhauser GL (1963) A geometric model and graphical algorithm for a sequencing problem. Oper Res 11:889\u2013900","journal-title":"Oper Res"},{"key":"127_CR12","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"SM Johnson","year":"1954","unstructured":"Johnson SM (1954) Optimal two- and three-stage production schedules with setup times included. Naval Res Logist Quart 1:61\u201368","journal-title":"Naval Res Logist Quart"},{"key":"127_CR13","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/BF01680374","volume":"43","author":"SA Kravchenko","year":"1996","unstructured":"Kravchenko SA, Sotskov YuN (1996) Optimal makespan schedule for three jobs on two machines. Math Methods Oper Res 43:233\u2013238","journal-title":"Math Methods Oper Res"},{"key":"127_CR14","doi-asserted-by":"publisher","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. Discr Appl Math 11:175\u2013186","journal-title":"Discr Appl Math"},{"key":"127_CR15","first-page":"70","volume":"23","author":"VV Servach","year":"1983","unstructured":"Servach VV (1983) On the Akers\u2013Friedman problem. Upravljajemye Syst Novosibirsk 23:70\u201381 (in Russian)","journal-title":"Upravljajemye Syst Novosibirsk"},{"key":"127_CR16","unstructured":"Shakhlevich NV, Strusevich VA (1990) Scheduling two jobs in a multi-machine open shop to minimize an arbitrary regular penalty function. Report 9125\/A, Erasmus University Rotterdam, The Netherlands"},{"key":"127_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF02243393","volume":"52","author":"NV Shakhlevich","year":"1994","unstructured":"Shakhlevich NV, Sotskov YuN (1994) Scheduling two jobs with fixed and nonfixed routines. Computing 52:17\u201330","journal-title":"Computing"},{"key":"127_CR18","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1023\/A:1018943016617","volume":"92","author":"NV Shakhlevich","year":"1999","unstructured":"Shakhlevich NV, Sotskov YuN, Werner F (1999) Shop-scheduling problems with fixed and non-fixed machine orders of jobs. Ann Oper Res 92:281\u2013304","journal-title":"Ann Oper Res"},{"key":"127_CR19","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0377-2217(99)00161-7","volume":"120","author":"NV Shakhlevich","year":"2000","unstructured":"Shakhlevich NV, Sotskov YuN, Werner F (2000) Complexity of mixed shop scheduling problems: A survey. Euro J Oper Res 120:343\u2013351","journal-title":"Euro J Oper Res"},{"key":"127_CR20","unstructured":"Sotskov YuN (1985) Optimal scheduling of two jobs with a regular criterion. Institute of Engineering Cybernetics of the Academy of Sciences of BSSR, Minsk, pp. 86\u201395 (in Russian)"},{"key":"127_CR21","first-page":"488","volume":"33","author":"YuN Sotskov","year":"1989","unstructured":"Sotskov YuN (1989) Complexity of scheduling with fixed number of jobs. Dokl Akad Nauk BSSR. 33:488\u2013491 (in Russian)","journal-title":"Dokl Akad Nauk BSSR."},{"key":"127_CR22","doi-asserted-by":"crossref","unstructured":"Sotskov YuN (1990) Complexity of optimal scheduling of three jobs Kibernetika N 5:74\u201378 (in Russian)","DOI":"10.1007\/BF01068549"},{"key":"127_CR23","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1016\/0377-2217(91)90066-5","volume":"53","author":"YuN Sotskov","year":"1991","unstructured":"Sotskov YuN (1991) The complexity of shop-scheduling problems with two or three jobs. Euro J Oper Res 53:326\u2013336","journal-title":"Euro J Oper Res"},{"key":"127_CR24","first-page":"96","volume":"4","author":"YuN Sotskov","year":"1990","unstructured":"Sotskov YuN, Shakhlevich NV (1990) NP-hardness of optimal scheduling three jobs. Vestsi Akad Navuk BSSR Ser Fiz-Mat Navuk 4:96\u2013101 (in Russian)","journal-title":"Vestsi Akad Navuk BSSR Ser Fiz-Mat Navuk"},{"key":"127_CR25","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0166-218X(93)E0169-Y","volume":"59","author":"YuN Sotskov","year":"1995","unstructured":"Sotskov YuN, Shakhlevich NV (1995) NP-hardness of shop-scheduling problems with three jobs. Discr Appl Mathe 59:237\u2013266","journal-title":"Discr Appl Mathe"},{"key":"127_CR26","first-page":"43","volume":"6","author":"VA Strusevich","year":"1986","unstructured":"Strusevich VA (1986) On the possibility of constructing optimal makespan schedules for multi-stage systems with nonfixed routes. Vestsi Akad Navuk BSSR Ser Fiz-Mat Navuk 6:43\u201348 (in Russian)","journal-title":"Vestsi Akad Navuk BSSR Ser Fiz-Mat Navuk"},{"key":"127_CR27","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1287\/opre.8.6.782","volume":"8","author":"W Szwarc","year":"1960","unstructured":"Szwarc W (1960) Solution of the Akers-Friedman scheduling problem. Oper Res 8:782\u2013788","journal-title":"Oper Res"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-006-0127-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-006-0127-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-006-0127-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-006-0127-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T16:44:06Z","timestamp":1683737046000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-006-0127-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2,6]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["127"],"URL":"https:\/\/doi.org\/10.1007\/s00186-006-0127-8","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2,6]]},"assertion":[{"value":"3 December 2004","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2006","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}