{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T21:36:51Z","timestamp":1768772211738,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T00:00:00Z","timestamp":1528156800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11501512"],"award-info":[{"award-number":["11501512"]}],"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":["11271324"],"award-info":[{"award-number":["11271324"]}],"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":["11471286"],"award-info":[{"award-number":["11471286"]}],"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":["61672323"],"award-info":[{"award-number":["61672323"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LY18A010029"],"award-info":[{"award-number":["LY18A010029"]}],"id":[{"id":"10.13039\/501100004731","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":[[2019,2]]},"DOI":"10.1007\/s10878-018-0314-6","type":"journal-article","created":{"date-parts":[[2018,6,5]],"date-time":"2018-06-05T01:42:06Z","timestamp":1528162926000},"page":"668-684","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A fully polynomial time approximation scheme for scheduling on parallel identical two-stage openshops"],"prefix":"10.1007","volume":"37","author":[{"given":"Jianming","family":"Dong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruyan","family":"Jin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jueliang","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,5]]},"reference":[{"key":"314_CR1","first-page":"98","volume":"2","author":"A Al-Salem","year":"2004","unstructured":"Al-Salem A (2004) A heuristic to minimize makespan in proportional parallel flow shops. Int J Comput Inf Sci 2:98\u2013107","journal-title":"Int J Comput Inf Sci"},{"key":"314_CR2","doi-asserted-by":"publisher","first-page":"3059","DOI":"10.1080\/0020754031000106443","volume":"41","author":"D Cao","year":"2003","unstructured":"Cao D, Chen M (2003) Parallel flowshop scheduling using Tabu search. Int J Prod Res 41:3059\u20133073","journal-title":"Int J Prod Res"},{"key":"314_CR3","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1057\/jors.1995.28","volume":"46","author":"B Chen","year":"1995","unstructured":"Chen B (1995) Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. J Oper Res Soc 46:234\u2013244","journal-title":"J Oper Res Soc"},{"key":"314_CR4","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0377-2217(93)90249-M","volume":"70","author":"B Chen","year":"1993","unstructured":"Chen B, Strusevich VA (1993) Worst case analysis of heuristics for open shops with parallel machines. Eur J Oper Res 70:379\u2013390","journal-title":"Eur J Oper Res"},{"key":"314_CR5","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1287\/opre.44.6.891","volume":"44","author":"B Chen","year":"1996","unstructured":"Chen B, Glass CA, Potts CN, Strusevich VA (1996) A new heuristic for three-machine flow shop scheduling. Oper Res 44:891\u2013898","journal-title":"Oper Res"},{"key":"314_CR6","first-page":"1493","volume-title":"A review of machine scheduling: complexity, algorithms and approximability","author":"B Chen","year":"1998","unstructured":"Chen B, Potts CN, Woeginger GJ (1998) A review of machine scheduling: complexity, algorithms and approximability. Springer, Berlin, pp 1493\u20131641"},{"key":"314_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.ipl.2013.01.009","volume":"113","author":"Y Chen","year":"2013","unstructured":"Chen Y, Zhang A, Chen G, Dong J (2013) Approximation algorithms for parallel open shop scheduling. Inf Process Lett 113:220\u2013224","journal-title":"Inf Process Lett"},{"key":"314_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2017.05.016","volume":"687","author":"J Dong","year":"2017","unstructured":"Dong J, Hu J, Kovalyov MY, Lin G, Luo T, Tong W, Wang X, Xu Y (2017) Corrigendum to \u201cAn FPTAS for the parallel two-stage flowshop problem. Theoretical computer science, 657: 64\u201372 (2017)\u201d. Theor Comput Sci 687:93\u201394","journal-title":"Theor Comput Sci"},{"key":"314_CR9","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1016\/j.tcs.2016.04.046","volume":"657","author":"J Dong","year":"2017","unstructured":"Dong J, Tong W, Luo T, Wang X, Hu J, Xu Y, Lin G (2017) An FPTAS for the parallel two-machine flowshop problem. Theor Comput Sci 657:64\u201372","journal-title":"Theor Comput Sci"},{"key":"314_CR10","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco"},{"key":"314_CR11","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey MR, Johnson DS, Sethi R (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117\u2013129","journal-title":"Math Oper Res"},{"key":"314_CR12","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 23:665\u2013679","journal-title":"J ACM"},{"key":"314_CR13","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1287\/opre.26.1.36","volume":"26","author":"T Gonzalez","year":"1978","unstructured":"Gonzalez T, Sahni S (1978) Flowshop and jobshop schedules: complexity and approximation. Oper Res 26:36\u201352","journal-title":"Oper Res"},{"key":"314_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1057\/jors.1988.63","volume":"39","author":"JND Gupta","year":"1988","unstructured":"Gupta JND (1988) Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc 39:359\u2013364","journal-title":"J Oper Res Soc"},{"key":"314_CR15","doi-asserted-by":"publisher","first-page":"1489","DOI":"10.1080\/00207549108948025","volume":"29","author":"JND Gupta","year":"1991","unstructured":"Gupta JND, Tunc EA (1991) Schedules for a two-stage hybrid flowshop with parallel machines at the second stage. Int J Prod Res 29:1489\u20131502","journal-title":"Int J Prod Res"},{"key":"314_CR16","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1023\/A:1018976827443","volume":"69","author":"JND Gupta","year":"1997","unstructured":"Gupta JND, Hariri AMA, Potts CN (1997) Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Ann Oper Res 69:171\u2013191","journal-title":"Ann Oper Res"},{"key":"314_CR17","first-page":"175","volume":"82","author":"LA Hall","year":"1998","unstructured":"Hall LA (1998) Approximability of flow shop scheduling. Math Program 82:175\u2013190","journal-title":"Math Program"},{"key":"314_CR18","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D Hochbaum","year":"1987","unstructured":"Hochbaum D, Shmoys D (1987) Using dual approximation algorithms for scheduling problems: theoretical and practical results. J ACM 34:144\u2013162","journal-title":"J ACM"},{"key":"314_CR19","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/S0377-2217(96)90070-3","volume":"89","author":"JA Hoogeveen","year":"1996","unstructured":"Hoogeveen JA, Lenstra JK, Veltman B (1996) Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. Eur J Oper Res 89:172\u2013175","journal-title":"Eur J Oper Res"},{"key":"314_CR20","doi-asserted-by":"crossref","unstructured":"Jansen K, Sviridenko MI (2000) Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. In: Proceedings of STACS 2000, LNCS 1770, pp 455\u2013465","DOI":"10.1007\/3-540-46541-3_38"},{"key":"314_CR21","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-machine production schedules with setup times included. Nav Res Logist 1:61\u201368","journal-title":"Nav Res Logist"},{"key":"314_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26580-3","volume-title":"Scheduling: theory, algorithm and systems","author":"M Pinedo","year":"2016","unstructured":"Pinedo M (2016) Scheduling: theory, algorithm and systems. Springer, Berlin"},{"key":"314_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejor.2009.09.024","volume":"205","author":"R Ruiz","year":"2010","unstructured":"Ruiz R, V\u00e1zquez-Rodr\u00edguez JA (2010) The hybrid flow shop scheduling problem. Eur J Oper Res 205:1\u201318","journal-title":"Eur J Oper Res"},{"key":"314_CR24","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"SK Sahni","year":"1976","unstructured":"Sahni SK (1976) Algorithms for scheduling independent tasks. J ACM 23:116\u2013127","journal-title":"J ACM"},{"key":"314_CR25","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/S0167-6377(99)00005-X","volume":"24","author":"P Schuurman","year":"1999","unstructured":"Schuurman P, Woeginger GJ (1999) Approximation algorithms for the multiprocessor open shop scheduling problem. Oper Res Lett 24:157\u2013163","journal-title":"Oper Res Lett"},{"key":"314_CR26","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0304-3975(98)00157-1","volume":"237","author":"P Schuurman","year":"2000","unstructured":"Schuurman P, Woeginger GJ (2000) A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. Theor Comput Sci 237:105\u2013122","journal-title":"Theor Comput Sci"},{"key":"314_CR27","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:191\u2013198","journal-title":"Math Program"},{"key":"314_CR28","unstructured":"Tong W, Miyano E, Goebel R, Lin G (2016) A PTAS for multiple parallel identical multi-stage flowshops to minimize the makespan. In: Proceedings of the 10th international frontiers of algorithmics workshop (FAW 2016), LNCS 9711, pp 227\u2013237"},{"key":"314_CR29","first-page":"687","volume":"32","author":"G Vairaktarakis","year":"2000","unstructured":"Vairaktarakis G, Elhafsi M (2000) The use of flowlines to simplify routing complexity in two-stage flowshops. IIE Trans 32:687\u2013699","journal-title":"IIE Trans"},{"key":"314_CR30","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1111\/j.1468-0394.2005.00297.x","volume":"22","author":"H Wang","year":"2005","unstructured":"Wang H (2005) Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions. Expert Syst 22:78\u201385","journal-title":"Expert Syst"},{"key":"314_CR31","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"DP Williamson","year":"1997","unstructured":"Williamson DP, Hall LA, Hoogeveen JA, Hurkens CAJ, Lenstra JK, Sevastianov SV, Shmoys DB (1997) Short shop schedules. Oper Res 45:288\u2013294","journal-title":"Oper Res"},{"key":"314_CR32","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/j.ejor.2011.08.007","volume":"216","author":"X Zhang","year":"2012","unstructured":"Zhang X, van de Velde S (2012) Approximation algorithms for the parallel flow shop problem. Eur J Oper Res 216:544\u2013552","journal-title":"Eur J Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0314-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0314-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0314-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T19:11:55Z","timestamp":1559675515000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0314-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,5]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["314"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0314-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,5]]},"assertion":[{"value":"5 June 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}