{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:13:12Z","timestamp":1784110392643,"version":"3.55.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T00:00:00Z","timestamp":1625184000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T00:00:00Z","timestamp":1625184000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971091"],"award-info":[{"award-number":["11971091"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11701062"],"award-info":[{"award-number":["11701062"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s10878-021-00773-7","type":"journal-article","created":{"date-parts":[[2021,7,2]],"date-time":"2021-07-02T12:02:31Z","timestamp":1625227351000},"page":"350-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["A PTAS for non-resumable open shop scheduling with an availability constraint"],"prefix":"10.1007","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5403-6576","authenticated-orcid":false,"given":"Yuan","family":"Yuan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yan","family":"Lan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Ding","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Han","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,7,2]]},"reference":[{"issue":"2","key":"773_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1051\/ro:2002008","volume":"36","author":"J B\u0142azewicz","year":"2002","unstructured":"B\u0142azewicz J, Formanowicz P (2002) Scheduling jobs in open shops with limited machine availability. RAIRO-Oper Res-Recherche Op\u00e9rationnelle 36(2):149\u2013156","journal-title":"RAIRO-Oper Res-Recherche Op\u00e9rationnelle"},{"issue":"6","key":"773_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.ipl.2004.03.004","volume":"90","author":"J Breit","year":"2004","unstructured":"Breit J (2004) An improved approximation algorithm for two-machine flow shop scheduling with an availability constraint. Information Process Lett 90(6):273\u2013278","journal-title":"Information Process Lett"},{"issue":"8","key":"773_CR3","doi-asserted-by":"publisher","first-page":"2143","DOI":"10.1016\/j.cor.2005.01.004","volume":"33","author":"J Breit","year":"2006","unstructured":"Breit J (2006) A polynomial-time approximation scheme for the two-machine flow shop scheduling problem with an availability constraint. Computers Oper Res 33(8):2143\u20132153","journal-title":"Computers Oper Res"},{"issue":"2","key":"773_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0167-6377(01)00079-7","volume":"29","author":"J Breit","year":"2001","unstructured":"Breit J, Schmidt G, Strusevich VA (2001) Two-machine open shop scheduling with an availability constraint. Oper Res Lett 29(2):65\u201377","journal-title":"Oper Res Lett"},{"issue":"2","key":"773_CR5","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s001860200267","volume":"57","author":"J Breit","year":"2003","unstructured":"Breit J, Schmidt G, Strusevich VA (2003) Non-preemptive two-machine open shop scheduling with non-availability constraints. Math Methods Oper Res 57(2):217\u2013234","journal-title":"Math Methods Oper Res"},{"issue":"3","key":"773_CR6","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1287\/ijoc.5.3.321","volume":"5","author":"B Chen","year":"1993","unstructured":"Chen B, Strusevich VA (1993) Approximation algorithms for three-machine open shop scheduling. ORSA J Comput 5(3):321\u2013326","journal-title":"ORSA J Comput"},{"issue":"5","key":"773_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0167-6377(00)00033-X","volume":"26","author":"TE Cheng","year":"2000","unstructured":"Cheng TE, Wang G (2000) An improved heuristic for two-machine flowshop scheduling with an availability constraint. Oper Res Lett 26(5):223\u2013229","journal-title":"Oper Res Lett"},{"key":"773_CR8","doi-asserted-by":"crossref","unstructured":"De\u00a0Werra D (1989) Graph-theoretical models for preemptive scheduling. Tech Rep, Elsevier","DOI":"10.1016\/B978-0-444-87358-3.50012-2"},{"issue":"4","key":"773_CR9","doi-asserted-by":"publisher","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. J ACM (JACM) 23(4):665\u2013679","journal-title":"J ACM (JACM)"},{"issue":"3","key":"773_CR10","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/s11590-011-0281-7","volume":"6","author":"H Hadda","year":"2012","unstructured":"Hadda H (2012) A polynomial-time approximation scheme for the two machine flow shop problem with several availability constraints. Optim Lett 6(3):559\u2013569","journal-title":"Optim Lett"},{"issue":"4","key":"773_CR11","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10852-013-9245-5","volume":"13","author":"H Hadda","year":"2014","unstructured":"Hadda H (2014) A PTAS for a particular case of the two-machine flow shop with limited machine availability. J Math Model Algorithms Oper Res 13(4):511\u2013522","journal-title":"J Math Model Algorithms Oper Res"},{"issue":"1","key":"773_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s10288-009-0102-3","volume":"8","author":"H Hadda","year":"2010","unstructured":"Hadda H, Dridi N, Hajri-Gabouj S (2010) An improved heuristic for two-machine flow shop scheduling with an availability constraint and nonresumable jobs. 4OR 8(1):87\u201399","journal-title":"4OR"},{"issue":"1","key":"773_CR13","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 Q 1(1):61\u201368","journal-title":"Naval Res Logist Q"},{"issue":"3","key":"773_CR14","doi-asserted-by":"publisher","first-page":"528","DOI":"10.1016\/S0377-2217(01)00083-2","volume":"136","author":"W Kubiak","year":"2002","unstructured":"Kubiak W, B\u0142azewicz J, Formanowicz P, Breit J, Schmidt G (2002) Two-machine flow shops with limited machine availability. Eur J Oper Res 136(3):528\u2013540","journal-title":"Eur J Oper Res"},{"issue":"1","key":"773_CR15","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1002\/nav.20122","volume":"53","author":"MA Kubzin","year":"2006","unstructured":"Kubzin MA, Strusevich VA, Breit J, Schmidt G (2006) Polynomial-time approximation schemes for two-machine open shop scheduling with nonavailability constraints. Naval Res Logist (NRL) 53(1):16\u201323","journal-title":"Naval Res Logist (NRL)"},{"issue":"2","key":"773_CR16","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/j.cor.2007.10.013","volume":"36","author":"MA Kubzin","year":"2009","unstructured":"Kubzin MA, Potts CN, Strusevich VA (2009) Approximation results for flow shop scheduling problems with machine availability constraints. Computers Oper Res 36(2):379\u2013390","journal-title":"Computers Oper Res"},{"issue":"3\u20134","key":"773_CR17","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/BF00121681","volume":"9","author":"CY Lee","year":"1996","unstructured":"Lee CY (1996) Machine scheduling with an availability constraint. J Global Optim 9(3\u20134):395\u2013416","journal-title":"J Global Optim"},{"issue":"3","key":"773_CR18","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0167-6377(96)00041-7","volume":"20","author":"CY Lee","year":"1997","unstructured":"Lee CY (1997) Minimizing the makespan in the two-machine flowshop scheduling problem with an availability constraint. Oper Res Lett 20(3):129\u2013139","journal-title":"Oper Res Lett"},{"issue":"2","key":"773_CR19","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/S0377-2217(97)00452-9","volume":"114","author":"CY Lee","year":"1999","unstructured":"Lee CY (1999) Two-machine flowshop scheduling with availability constraints. Eur J Oper Res 114(2):420\u2013429","journal-title":"Eur J Oper Res"},{"issue":"11","key":"773_CR20","doi-asserted-by":"publisher","first-page":"1239","DOI":"10.1057\/palgrave.jors.2601421","volume":"53","author":"T Lorigeon","year":"2002","unstructured":"Lorigeon T, Billaut J, Bouquard J (2002) A dynamic programming algorithm for scheduling jobs in a two-machine open shop with an availability constraint. J Oper Res Soc 53(11):1239\u20131246","journal-title":"J Oper Res Soc"},{"issue":"1","key":"773_CR21","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1287\/moor.18.1.12","volume":"18","author":"L Lu","year":"1993","unstructured":"Lu L, Posner ME (1993) An NP-hard open shop scheduling problem with polynomial average time complexity. Math Oper Res 18(1):12\u201338","journal-title":"Math Oper Res"},{"issue":"2","key":"773_CR22","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1016\/j.ejor.2018.04.019","volume":"271","author":"G Mosheiov","year":"2018","unstructured":"Mosheiov G, Sarig A, Strusevich VA, Mosheiff J (2018) Two-machine flow shop and open shop scheduling problems with a single maintenance window. Eur J Oper Res 271(2):388\u2013400","journal-title":"Eur J Oper Res"},{"issue":"3","key":"773_CR23","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1002\/nav.10107","volume":"51","author":"C Ng","year":"2004","unstructured":"Ng C, Kovalyov MY (2004) An FPTAS for scheduling a two-machine flowshop with one unavailability interval. Naval Res Logist (NRL) 51(3):307\u2013315","journal-title":"Naval Res Logist (NRL)"},{"key":"773_CR24","doi-asserted-by":"crossref","unstructured":"Pinedo M, Schrage L (1982) Stochastic shop scheduling: a survey. In: Deterministic and stochastic scheduling. Springer, pp 181\u2013196","DOI":"10.1007\/978-94-009-7801-0_9"},{"issue":"1\u20132","key":"773_CR25","first-page":"191","volume":"82","author":"SV Sevastianov","year":"1998","unstructured":"Sevastianov SV, Woeginger GJ (1998) Makespan minimization in open shops: a polynomial time approximation scheme. Math Program 82(1\u20132):191\u2013198","journal-title":"Math Program"},{"issue":"3","key":"773_CR26","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/0377-2217(93)90250-Q","volume":"70","author":"N Shakhlevich","year":"1993","unstructured":"Shakhlevich N, Strusevich V (1993) Two machine open shop scheduling problem to minimize an arbitrary machine usage regular penalty function. Eur J Oper Res 70(3):391\u2013404","journal-title":"Eur J Oper Res"},{"key":"773_CR27","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1023\/A:1018964131329","volume":"83","author":"VA Strusevich","year":"1998","unstructured":"Strusevich VA (1998) A greedy open shop heuristic with job priorities. Annal Oper Res 83:253\u2013270","journal-title":"Annal Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00773-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00773-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00773-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,28]],"date-time":"2022-02-28T18:32:33Z","timestamp":1646073153000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00773-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,2]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["773"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00773-7","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,2]]},"assertion":[{"value":"14 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}