{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,15]],"date-time":"2022-11-15T05:52:45Z","timestamp":1668491565544},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[1998,6,1]],"date-time":"1998-06-01T00:00:00Z","timestamp":896659200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1998,6]]},"DOI":"10.1007\/bf01585870","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T08:42:50Z","timestamp":1114677770000},"page":"175-190","source":"Crossref","is-referenced-by-count":37,"title":["Approximability of flow shop scheduling"],"prefix":"10.1007","volume":"82","author":[{"given":"Leslie A.","family":"Hall","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"CR1","first-page":"177","volume":"15","author":"I. B\u00e1r\u00e1ny","year":"1982","unstructured":"I. B\u00e1r\u00e1ny, T. Fiala, T\u00f6bbg\u00e9pes \u00fctemez\u00e9si probl\u00e9m\u00e1k k\u00f6zel optim\u00e1lis megold\u00e1sa, Szigma-Mat.-K\u00f6zgazdas\u00e1gi Foly\u00f3irat 15 (1982) 177\u2013191.","journal-title":"Szigma-Mat.-K\u00f6zgazdas\u00e1gi Foly\u00f3irat"},{"key":"CR2","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"R.G. Downey, M.R. Fellows, Fixed-parameter tractability and completeness I: Basic results, SIAM J. Comput. 24 (1995) 873\u2013921.","journal-title":"SIAM J. Comput."},{"key":"CR3","first-page":"89","volume-title":"Logical Foundations of Computer Science, Proceedings of the Third International Symposium, LFCS 1994, Lecture Notes in Computer Science 813","author":"R.G. Downey","year":"1994","unstructured":"R.G. Downey, M.R. Fellows, B.M. Kapron, M.T. Hallett, H.T. Wareham, The parameterized complexity of some problems in logic and linguistics, in: A. Nerode, Yu.V. Matiyasevich (Eds.), Logical Foundations of Computer Science, Proceedings of the Third International Symposium, LFCS 1994, Lecture Notes in Computer Science 813, Springer, Berlin, 1994, pp. 89\u2013100."},{"key":"CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979."},{"key":"CR5","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, R. Sethi, The complexity of flowshop and jobshop scheduling, Math. Oper. Res. 1 (1976) 117\u2013129.","journal-title":"Math. Oper. Res."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1145\/321978.321985","volume":"23","author":"T. Gonzalez","year":"1976","unstructured":"T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time, J. Assoc. Comput. Mach. 23 (1976) 665\u2013679.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR7","doi-asserted-by":"crossref","unstructured":"L.A. Hall, D.B. Shmoys, Approximation algorithms for constrained scheduling problems, in: Proceedings of the IEEE 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 134\u2013139.","DOI":"10.1109\/SFCS.1989.63468"},{"key":"CR8","unstructured":"L.A. Hall, D.B. Shmoys, Near-optimal sequencing with precedence constraints, in: Proceedings of the Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, University of Waterloo, 1990, pp. 249\u2013260."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/moor.17.1.22","volume":"17","author":"L.A. Hall","year":"1992","unstructured":"L.A. Hall, D.B. Shmoys, Jackson's rule for single-machine scheduling: Making a good heuristic better, Math. Oper. Res. 17 (1992) 22\u201335.","journal-title":"Math. Oper. Res."},{"key":"CR10","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1002\/nav.3800010110","volume":"1","author":"S.M. Johnson","year":"1954","unstructured":"S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Logist. Quart. 1 (1954) 61\u201368.","journal-title":"Naval Res. Logist. Quart."},{"key":"CR11","first-page":"205","volume":"22","author":"H. Kise","year":"1979","unstructured":"H. Kise, T. Ibaraki, H. Mine, Performance analysis of six approximation algorithms for the one-machine maximum lateness scheduling problem with ready times, J. Oper. Res. Soc. Japan 22 (1979) 205\u2013224.","journal-title":"J. Oper. Res. Soc. Japan"},{"key":"CR12","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, North-Holland, 1993, 445\u2013522.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1007\/BF01215349","volume":"14","author":"F.T. Leighton","year":"1994","unstructured":"F.T. Leighton, B. Maggs, S. Rao, Packet routing and job-shop scheduling in O(Congestion + Dilation) steps, Combinatorica 14 (1994) 167\u2013186.","journal-title":"Combinatorica"},{"key":"CR14","first-page":"555","volume":"2","author":"F.T. Leighton","year":"1995","unstructured":"F.T. Leighton, B. Maggs, Fast algorithms for finding O(Congestion + Dilation) packet routing schedules, Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS), vol. 2, 1995, pp. 555\u2013563. A corrected version of this paper appears under the same title as a working paper by F.T. Leighton, B. Maggs, A.W. Richa.","journal-title":"Proceedings of the 28th Hawaii International Conference on System Sciences (HICSS)"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/S0167-5060(08)70743-X","volume":"1","author":"J.K. Lenstra","year":"1977","unstructured":"J.K. Lenstra, A.H.G. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Ann. Discrete Math. 1 (1977) 343\u2013362.","journal-title":"Ann. Discrete Math."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"J.K. Lenstra, D.B. Shmoys, \u00c9. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Math. Programming 46 (1990) 259\u2013271.","journal-title":"Math. Programming"},{"key":"CR17","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"C.H. Papadimitriou, Computational Complexity. Addison\u2014Wesley, Reading, MA, 1994."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.20.2.257","volume":"20","author":"S.A. Plotkin","year":"1995","unstructured":"S.A. Plotkin, D.B. Shmoys, \u00c9. Tardos, Fast approximation algorithms for fractional packing and covering problems, Math. Oper. Res. 20 (1995) 257\u2013301.","journal-title":"Math. Oper. Res."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0166-218X(85)90009-5","volume":"10","author":"C.N. Potts","year":"1985","unstructured":"C.N. Potts, Analysis of a linear programming heuristic for scheduling unrelated parallel machines, Discrete Appl. Math. 10 (1985) 155\u2013164.","journal-title":"Discrete Appl. Math."},{"key":"CR20","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"6","author":"J.P. Schmidt","year":"1995","unstructured":"J.P. Schmidt, A. Siegel, A. Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math. 6 (1995) 223\u2013250.","journal-title":"SIAM J. Discrete Math."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1007\/BF01068694","volume":"22","author":"S. Sevast'janov","year":"1986","unstructured":"S. Sevast'janov, Bounding algorithm for the routing problem with arbitrary paths and alternative servers, Cybernetics 22 (1986) 773\u2013780.","journal-title":"Cybernetics"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"S. Sevast'janov, G. Woeginger, Makespan minimization in open shops: A polynomial time approximation scheme, Math. Programming, (this issue, 1998).","DOI":"10.1007\/BF01585871"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"D.B. Shmoys","year":"1994","unstructured":"D.B. Shmoys, C. Stein, J. Wein, Improved approximation algorithms for shop scheduling problems, SIAM J. Comput. 23 (1994) 617\u2013632.","journal-title":"SIAM J. Comput."},{"key":"CR24","volume-title":"Approximation algorithms for multicommodity flow and shop scheduling problems","author":"C. Stein","year":"1992","unstructured":"C. Stein, Approximation algorithms for multicommodity flow and shop scheduling problems. Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge, MA, 1992 (also appears as MIT\/LCS\/TR-550)."},{"key":"CR25","doi-asserted-by":"crossref","unstructured":"P.M. Vaidya, Speeding up linear programming using fast matrix multiplication, in: Proceedings of the IEEE 30th Annual Symposium on Foundations of Computer Science, 1989, pp. 332\u2013337.","DOI":"10.1109\/SFCS.1989.63499"},{"key":"CR26","doi-asserted-by":"crossref","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. Sevast'janov, D.B. Shmoys, Short shop schedules, Oper. Res. 45 (1997) 288\u2013294.","journal-title":"Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585870.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585870\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,7]],"date-time":"2020-04-07T03:47:32Z","timestamp":1586231252000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,6]]},"references-count":26,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[1998,6]]}},"alternative-id":["BF01585870"],"URL":"http:\/\/dx.doi.org\/10.1007\/bf01585870","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":["General Mathematics","Software"],"published":{"date-parts":[[1998,6]]}}}