{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:31:22Z","timestamp":1760707882970},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648482"},{"type":"electronic","value":"9783540685302"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_41","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T17:14:16Z","timestamp":1194542056000},"page":"490-501","source":"Crossref","is-referenced-by-count":15,"title":["Techniques for Scheduling with Rejection"],"prefix":"10.1007","author":[{"given":"Daniel W.","family":"Engels","sequence":"first","affiliation":[]},{"given":"David R.","family":"Karger","sequence":"additional","affiliation":[]},{"given":"Stavros G.","family":"Kolliopoulos","sequence":"additional","affiliation":[]},{"given":"Sudipta","family":"Sengupta","sequence":"additional","affiliation":[]},{"given":"R. N.","family":"Uma","sequence":"additional","affiliation":[]},{"given":"Joel","family":"Wein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"key":"41_CR1","unstructured":"Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie. Multiprocessor scheduling with rejection. In Proc. 7th SODA, 95\u2013103, 1996."},{"key":"41_CR2","unstructured":"C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proc. 8th SODA, 609\u2013618, 1997."},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"F. A. Chudak. Improved approximation algorithms for uncapacitated facility location. In Proc. 6th IPCO 1998. To appear.","DOI":"10.1007\/3-540-69346-7_14"},{"key":"41_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"41_CR5","unstructured":"M. Goemans. Improved approximation algorithms for scheduling with release dates. In Proc. 8th SODA, 591\u2013598, 1997."},{"key":"41_CR6","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"R.L. Graham, E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5:287\u2013326, 1979.","journal-title":"Annals of Discrete Mathematics"},{"key":"41_CR7","doi-asserted-by":"crossref","unstructured":"S. Guha and S. Khuller. Greedy strikes back: Improved facility location algorithms. In Proc. 9th SODA, 1998.","DOI":"10.1006\/jagm.1998.0993"},{"key":"41_CR8","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1287\/moor.22.3.513","volume":"3","author":"L. A. Hall","year":"1997","unstructured":"L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling tominimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research, (3):513\u2013544, August 1997.","journal-title":"Mathematics of Operations Research"},{"key":"41_CR9","unstructured":"E. L. Lawler. Scheduling a single machine to minimize the number of late jobs. Preprint, Computer Science Division, Univ. of California, Berkeley, 1982."},{"key":"41_CR10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"E. L. Lawler","year":"1969","unstructured":"E. L. Lawler and J. M. Moore. A functional equation and its application to resource allocation and sequencing problems. In Manag. Sci., volume 16, 77\u201384, 1969.","journal-title":"Manag. Sci."},{"key":"41_CR11","unstructured":"E. L. Lawler and D. B. Shmoys. Weighted number of late jobs (preliminary version). To appear in: J.K. Lenstra and D.B. Shmoys (eds.) Scheduling, Wiley."},{"key":"41_CR12","unstructured":"Maxwell. Personal communication. 1996."},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"I. M. Ovacik and R. Uzsoy. DecompositionMethods for Complex Factory Scheduling Problems. Kluwer Academic Publishers, 1997.","DOI":"10.1007\/978-1-4615-6329-7"},{"key":"41_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1007\/3-540-60220-8_53","volume-title":"Proc. of 4th WADS","author":"C. Phillips","year":"1995","unstructured":"C. Phillips, C. Stein, and J. Wein. Scheduling jobs that arrive over time. In Proc. of 4th WADS, LNCS, 955, 86\u201397, Berlin, 1995. Springer-Verlag. To appear in Mathematical Programming B."},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1287\/mnsc.12.5.437","volume":"12","author":"M. H. Rothkopf","year":"1966","unstructured":"M. H. Rothkopf. Scheduling independent tasks on parallel processors. In Manag. Sci., volume 12, 437\u2013447, 1966.","journal-title":"Manag. Sci."},{"key":"41_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/3-540-63248-4_11","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"A. S. Schulz","year":"1997","unstructured":"A. S. Schulz and M. Skutella. Random-based scheduling: New approximations and LP lower bounds. In J. Rolim, editor, Randomization and Approximation Techniques in Computer Science, LNCS, 955, 119\u2013133. Springer, Berlin, 1997."},{"key":"41_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/3-540-63397-9_32","volume-title":"Algorithms \u2014 ESA\u201997","author":"A. S. Schulz","year":"1997","unstructured":"A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. In R. Burkard and G. Woeginger, editors, Algorithms \u2014 ESA\u201997, LNCS, 1284, 416\u2013429. Springer, Berlin, 1997."},{"key":"41_CR18","doi-asserted-by":"crossref","unstructured":"D. B. Shmoys, \u00c9. Tardos, and K. Aardal. Approximation algorithms for facility location problems. In Proc. of the 29th ACM STOC, 265\u2013274, 1997.","DOI":"10.1145\/258533.258600"},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/nav.3800030106","volume":"3","author":"W.E. Smith","year":"1956","unstructured":"W.E. Smith. Various optimizers for single-stage production. Naval Research Logistics Quarterly, 3:59\u201366, 1956.","journal-title":"Naval Research Logistics Quarterly"},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0166-218X(90)90104-K","volume":"26","author":"M. E. Dyer","year":"1990","unstructured":"M. E. Dyer and L. A. Wolsey. Formulating the single machine sequencing problem with release dates as a mixed integer program. In Discrete Applied Mathematics, 26, 255\u2013270, 1990.","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T04:28:16Z","timestamp":1556944096000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}