{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T06:49:42Z","timestamp":1775026182022,"version":"3.50.1"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,10,24]],"date-time":"2007-10-24T00:00:00Z","timestamp":1193184000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,6]]},"DOI":"10.1007\/s00453-007-9086-6","type":"journal-article","created":{"date-parts":[[2007,10,23]],"date-time":"2007-10-23T14:41:06Z","timestamp":1193150466000},"page":"183-199","source":"Crossref","is-referenced-by-count":13,"title":["Grouping Techniques for Scheduling Problems: Simpler and Faster"],"prefix":"10.1007","volume":"51","author":[{"given":"Aleksei V.","family":"Fishkin","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Monaldo","family":"Mastrolilli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,24]]},"reference":[{"key":"9086_CR1","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s00453-001-0076-9","volume":"32","author":"A. Amoura","year":"2002","unstructured":"Amoura, A., Bampis, E., Kenyon, C., Manoussakis, Y.: Scheduling independent multiprocessor tasks. Algorithmica 32, 247\u2013261 (2002)","journal-title":"Algorithmica"},{"key":"9086_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/S0097539798348110","volume":"31","author":"J. Chen","year":"2001","unstructured":"Chen, J., Miranda, A.: A polynomial time approximation scheme for general multiprocessor job scheduling. SIAM J. Comput. 31, 1\u201317 (2001)","journal-title":"SIAM J. Comput."},{"key":"9086_CR3","volume-title":"Computers and Intractability; a Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; a Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"1","key":"9086_CR4","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1137\/S0895480199326104","volume":"14","author":"L. Goldberg","year":"2001","unstructured":"Goldberg, L., Paterson, M., Srinivasan, A., Sweedyk, E.: Better approximation guarantees for job-shop scheduling. SIAM J. Discrete Math. 14(1), 67\u201392 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"9086_CR5","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1287\/moor.21.2.321","volume":"21","author":"M.D. Grigoriadis","year":"1996","unstructured":"Grigoriadis, M.D., Khachiyan, L.G.: Coordination complexity of parallel price-directive decomposition. Math. Oper. Res. 21, 321\u2013340 (1996)","journal-title":"Math. Oper. Res."},{"key":"9086_CR6","first-page":"175","volume":"82","author":"L. Hall","year":"1998","unstructured":"Hall, L.: Approximability of flow shop scheduling. Math. Program. 82, 175\u2013190 (1998)","journal-title":"Math. Program."},{"key":"9086_CR7","doi-asserted-by":"crossref","unstructured":"Hall, L., Shmoys, D.: Approximation algorithms for constrained scheduling problems. In: Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, pp.\u00a0134\u2013139 (1989)","DOI":"10.1109\/SFCS.1989.63468"},{"key":"9086_CR8","first-page":"249","volume-title":"Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference","author":"L. Hall","year":"1990","unstructured":"Hall, L., Shmoys, D.: Near-optimal sequencing with precedence constraints. In: Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, pp.\u00a0249\u2013260. University of Waterloo Press, Waterloo (1990)"},{"issue":"2","key":"9086_CR9","first-page":"317","volume":"23","author":"E. Horowitz","year":"1976","unstructured":"Horowitz, E., Sahni, S.: Exact and approximate algorithms for scheduling nonidentical processors. J.\u00a0ACM 23(2), 317\u2013327 (1976)","journal-title":"J.\u00a0ACM"},{"issue":"2","key":"9086_CR10","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1287\/moor.26.2.324.10559","volume":"26","author":"K. Jansen","year":"2001","unstructured":"Jansen, K., Porkolab, L.: Improved approximation schemes for scheduling unrelated parallel machines. Math. Oper. Res. 26(2), 324\u2013338 (2001)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"9086_CR11","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/s00453-001-0085-8","volume":"32","author":"K. Jansen","year":"2002","unstructured":"Jansen, K., Porkolab, L.: Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica 32(3), 507\u2013520 (2002)","journal-title":"Algorithmica"},{"issue":"2","key":"9086_CR12","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1016\/S0196-6774(02)00248-1","volume":"45","author":"K. Jansen","year":"2002","unstructured":"Jansen, K., Porkolab, L.: Polynomial time approximation schemes for general multiprocessor job shop scheduling. J. Algorithms 45(2), 167\u2013191 (2002)","journal-title":"J. Algorithms"},{"key":"9086_CR13","doi-asserted-by":"crossref","unstructured":"Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: a polynomial time approximation scheme. In: Proceedings of the 31st Annual ACM Symposium on the Theory of Computing (STOC 99), pp.\u00a0394\u2013399 (1999)","DOI":"10.1145\/301250.301351"},{"issue":"2","key":"9086_CR14","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1137\/S0895480199363908","volume":"16","author":"K. Jansen","year":"2003","unstructured":"Jansen, K., Solis-Oba, R., Sviridenko, M.: Makespan minimization in job shops: A linear time approximation scheme. SIAM J. Discrete Math. 16(2), 288\u2013300 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9086_CR15","doi-asserted-by":"crossref","unstructured":"Lawler, E., Lenstra, J., Kan, A.R., Shmoys, D.: Sequencing and scheduling: algorithms and complexity. In: Handbook in Operations Research and Management Science, vol.\u00a04, pp.\u00a0445\u2013522 (1993)","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"9086_CR16","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. 46, 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"9086_CR17","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1023\/A:1026272526225","volume":"6","author":"M. Mastrolilli","year":"2003","unstructured":"Mastrolilli, M.: Efficient approximation schemes for scheduling problems with release dates and delivery times. J. Sched. 6, 521\u2013531 (2003)","journal-title":"J. Sched."},{"key":"9086_CR18","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.jalgor.2005.01.004","volume":"59","author":"M. Mastrolilli","year":"2006","unstructured":"Mastrolilli, M.: A linear time approximation schemes for the single machine scheduling problem with controllable processing times. J. Algorithms 59, 37\u201352 (2006)","journal-title":"J. Algorithms"},{"key":"9086_CR19","unstructured":"Schuurman, P., Woeginger, G.: Approximation schemes\u2014a tutorial. In: Moehring, R., Potts, C., Schulz, A., Woeginger, G., Wolsey, L. (eds.) Lectures on Scheduling (to appear)"},{"key":"9086_CR20","first-page":"191","volume":"82","author":"S. Sevastianov","year":"1998","unstructured":"Sevastianov, S., Woeginger, G.J.: Makespan minimization in open shops: a polynomial time approximation scheme. Math. Program. 82, 191\u2013198 (1998)","journal-title":"Math. Program."},{"key":"9086_CR21","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/0166-218X(94)90036-1","volume":"55","author":"S.V. Sevastianov","year":"1994","unstructured":"Sevastianov, S.V.: On some geometric methods in scheduling theory: a survey. Discrete Appl. Math. 55, 59\u201382 (1994)","journal-title":"Discrete Appl. Math."},{"key":"9086_CR22","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1137\/S009753979222676X","volume":"23","author":"D. Shmoys","year":"1994","unstructured":"Shmoys, D., Stein, C., Wein, J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23, 617\u2013632 (1994)","journal-title":"SIAM J. Comput."},{"key":"9086_CR23","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"D. Shmoys","year":"1993","unstructured":"Shmoys, D., Tardos, E.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993)","journal-title":"Math. Program."},{"key":"9086_CR24","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1287\/opre.45.2.288","volume":"45","author":"D. Williamson","year":"1997","unstructured":"Williamson, D., Hall, L., Hoogeveen, J., Hurkens, C., Lenstra, J., Sevastianov, S., Shmoys, D.: Short shop schedules. Oper. Res. 45, 288\u2013294 (1997)","journal-title":"Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9086-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9086-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9086-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:00Z","timestamp":1559137500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9086-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,24]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["9086"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9086-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,24]]}}}