{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:16:58Z","timestamp":1725484618480},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424932"},{"type":"electronic","value":"9783540446767"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_17","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T12:43:15Z","timestamp":1179492195000},"page":"206-217","source":"Crossref","is-referenced-by-count":6,"title":["Grouping Techniques for Scheduling Problems: Simpler and Faster"],"prefix":"10.1007","author":[{"given":"Aleksei V.","family":"Fishkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"17_CR1","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Proceedings of the 5th Annual European Symposium on Algorithms","author":"A.K. Amoura","year":"1997","unstructured":"A.K. Amoura, E. Bampis, C. Kenyon, and Y. Manoussakis, Scheduling independent multiprocessor tasks, Proceedings of the 5th Annual European Symposium on Algorithms, vol. 1284, LNCS, 1997, pp. 1\u201312."},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"J. Chen and A. Miranda, A polynomial time approximation scheme for general multiprocessor job scheduling, Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 418\u2013427.","DOI":"10.1145\/301250.301363"},{"key":"17_CR3","unstructured":"M. R. Garey and D. S. Johnson, Computers and intractability; a guide to the theory of np-completeness, W.H. Freeman, 1979."},{"key":"17_CR4","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"21","author":"M. D. Grigoriadis","year":"1996","unstructured":"M. D. Grigoriadis and L. G. Khachiyan, Coordination complexity of parallel price-directive decomposition, Mathematics of Operations Research 21 (1996), 321\u2013340.","journal-title":"Mathematics of Operations Research"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/S0895480199326104","volume":"14","author":"L.A. Goldberg","year":"2001","unstructured":"L.A. Goldberg, M. Paterson, A. Srinivasan, and E. Sweedyk, Better approximation guarantees for job-shop scheduling, SIAM Journal on Discrete Mathematics 14 (2001), no. 1, 67\u201392.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1145\/321941.321951","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"E. Horowitz and S. Sahni, Exact and approximate algorithms for scheduling non-identical processors, Journal of the ACM 23 (1976), 317\u2013327.","journal-title":"Journal of the ACM"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"K. Jansen and L. Porkolab, Improved approximation schemes for scheduling unrelated parallel machines, Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 408\u2013417.","DOI":"10.1145\/301250.301361"},{"key":"17_CR8","unstructured":"K. Jansen and L. Porkolab, Linear-time approximation schemes for scheduling malleable parallel tasks, Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 490\u2013498."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"K. Jansen and L. Porkolab, Polynomial time approximation schemes for general multiprocessor job shop scheduling, ICALP\u201900, 2000, pp. 878\u2013889.","DOI":"10.1007\/3-540-45022-X_74"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"K. Jansen, R. Solis-Oba, and M. Sviridenko, Makespan minimization in job shops: a polynomial time approximation scheme, Proceedings of the 31st Annual ACM Symposium on the Theory of Computing, 1999, pp. 394\u2013399.","DOI":"10.1145\/301250.301351"},{"key":"17_CR11","first-page":"177","volume":"1671","author":"K. Jansen","year":"1999","unstructured":"K. Jansen, R. Solis-Oba, and M. Sviridenko, A linear time approximation scheme for the job shop scheduling problem, APPROX\u201999, vol. 1671, 1999, pp. 177\u2013188.","journal-title":"APPROX\u201999"},{"key":"17_CR12","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, Handbook in Operations Research and Management Science 4 (1993), 445\u2013522.","journal-title":"Handbook in Operations Research and Management Science"},{"key":"17_CR13","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J. K. Lenstra","year":"1990","unstructured":"J. K. Lenstra, D. B. Shmoys, and E. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming 46 (1990), 259\u2013271.","journal-title":"Mathematical Programming"},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0166-218X(94)90036-1","volume":"55","author":"S. V. Sevastianov","year":"1994","unstructured":"S. V. Sevastianov, On some geometric methods in scheduling theory: a survey, Discrete Applied Mathematics 55 (1994), 59\u201382.","journal-title":"Discrete Applied Mathematics"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"D.B. Shmoys and E. Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming (1993), 461\u2013474.","DOI":"10.1007\/BF01585178"},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"D.B. Shmoys","year":"1994","unstructured":"D.B. Shmoys, C. Stein and J. Wein, Improved approximation algorithms for shop scheduling problems, SIAM Journal on Computing 23 (1994), 617\u2013632.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR17","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","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:44:08Z","timestamp":1556412248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}