{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T15:45:47Z","timestamp":1762271147963},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540671411"},{"type":"electronic","value":"9783540465416"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-46541-3_38","type":"book-chapter","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T16:03:24Z","timestamp":1186070604000},"page":"455-465","source":"Crossref","is-referenced-by-count":14,"title":["Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Jansen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxim I.","family":"Sviridenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2000,3,24]]},"reference":[{"key":"38_CR1","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1038\/sj\/jors\/0460209","volume":"46","author":"B. Chen","year":"1995","unstructured":"B. Chen, Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage, Journal of the Operational Research Society 46 (1995), 234\u2013244.","journal-title":"Journal of the Operational Research Society"},{"key":"38_CR2","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0377-2217(93)90249-M","volume":"70","author":"B. Chen","year":"1993","unstructured":"B. Chen and V.A. Strusevich, Worst case analysis of heuristics for open shops with parallel machines, European Journal of Operational Research 70 (1993), 379\u2013390.","journal-title":"European Journal of Operational Research"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M.R. Garey","year":"1978","unstructured":"M.R. Garey and D.S. Johnson, Strong NP-completeness results: Motivation, examples and implications, Journal of the ACM 25 (1978), 499\u2013508.","journal-title":"Journal of the ACM"},{"key":"38_CR4","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1287\/moor.1.2.117","volume":"1","author":"M.R. Garey","year":"1976","unstructured":"M.R. Garey, D.S. Johnson and R. Sethi, The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research 1 (1976), 117\u2013129.","journal-title":"Mathematics of Operations Research"},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T. Gonzales","year":"1976","unstructured":"T. Gonzales and S. Sahni, Open shop scheduling to minimize finish time, Journal of the ACM 23 (1976), 665\u2013679.","journal-title":"Journal of the ACM"},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"L.A. Hall, Approximability of flow shop scheduling, Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science (1995), 82\u201391 and Mathematical Programming 82 (1998), 175\u2013190.","DOI":"10.1007\/BF01585870"},{"key":"38_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"D.S. Hochbaum and D.B. Shmoys, Using dual approximation algorithms for scheduling problems: theoretical and practical results, Journal of the ACM 34 (1987), 144\u2013162.","journal-title":"Journal of the ACM"},{"key":"38_CR8","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/S0377-2217(96)90070-3","volume":"89","author":"J.A. Hoogeveen","year":"1996","unstructured":"J.A. Hoogeveen, J.K. Lenstra and B. Veltman, Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard, European Journal of Operational Research 89 (1996), 172\u2013175.","journal-title":"European Journal of Operational Research"},{"key":"38_CR9","doi-asserted-by":"crossref","unstructured":"K. Jansen, R. Solis-Oba and M.I. Sviridenko, Makespan minimization in job shops: a polynomial time approximation scheme, Proceedings of the 31th Annual ACM Symposium on Theory of Computing, to appear, 1999.","DOI":"10.1145\/301250.301351"},{"key":"38_CR10","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1016\/S0927-0507(05)80189-6","volume":"4","author":"E.L. Lawler","year":"1993","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: Handbook in Operations Research and Management Science, Vol. 4, North-Holland, 1993, 445\u2013522.","journal-title":"Handbook in Operations Research and Management Science"},{"key":"38_CR11","doi-asserted-by":"crossref","unstructured":"P. Schuurman and G.J. Woeginger, Approximation algorithms for the multiprocessor open shop scheduling problem, Operations Research Letters, to appear.","DOI":"10.1016\/S0167-6377(99)00005-X"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"P. Schuurman and G.J. Woeginger, A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem, Theoretical Computer Science, to appear.","DOI":"10.1016\/S0304-3975(98)00157-1"},{"key":"38_CR13","first-page":"191","volume":"82","author":"S.V. Sevastianov","year":"1998","unstructured":"S.V. Sevastianov and G.J. Woeginger, Makespan minimization in open shops: A polynomial time approximation scheme, Mathematical Programming 82 (1998), 191\u2013198.","journal-title":"Mathematical Programming"},{"key":"38_CR14","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0377-2217(89)90208-7","volume":"43","author":"C. Sriskandarajah","year":"1989","unstructured":"C. Sriskandarajah and S.P. Sethi, Scheduling algorithms for flexible flow shops: worst and average case performance, European Journal of Operational Research 43 (1989), 143\u2013160.","journal-title":"European Journal of Operational Research"},{"key":"38_CR15","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"D.P. Williamson","year":"1997","unstructured":"D.P. Williamson, L.A. Hall, J.A. Hoogeveen, C.A.J. Hurkens, J.K. Lenstra, S.V. Sevastianov and D.B. Shmoys, Short shop schedules, Operations Research 45 (1997), 288\u2013294.","journal-title":"Operations Research"}],"container-title":["Lecture Notes in Computer Science","STACS 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46541-3_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,17]],"date-time":"2019-02-17T21:40:51Z","timestamp":1550439651000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46541-3_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540671411","9783540465416"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-46541-3_38","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}