{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:40:14Z","timestamp":1737006014146,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425601"},{"type":"electronic","value":"9783540448082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44808-x_17","type":"book-chapter","created":{"date-parts":[[2007,5,4]],"date-time":"2007-05-04T00:32:08Z","timestamp":1178238728000},"page":"202-215","source":"Crossref","is-referenced-by-count":0,"title":["Implementation of a PTAS for Scheduling with Release Dates"],"prefix":"10.1007","author":[{"given":"Clint","family":"Hepner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cliff","family":"Stein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,9,11]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, and M. Sviridenko. Approximation schemes for minimizing average weighted completion time with release dates. 40th Annual Symposium on Foundations of Computer Science, pages 32\u201343, 1999.","DOI":"10.1109\/SFFCS.1999.814574"},{"key":"17_CR2","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1002\/nav.3800260315","volume":"26","author":"R. Chandra","year":"1979","unstructured":"Ramesh Chandra. On n\/1\/F dynamic deterministic systems. Naval Research Logistics Quarterly, 26:537\u2013544, 1979.","journal-title":"Naval Research Logistics Quarterly"},{"key":"17_CR3","unstructured":"Chekuri C., Motwani R., Natarajan B., and Stein C. Approximation techniques for average completion time scheduling. Proceedings of Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 609\u201318, 1997."},{"key":"17_CR4","unstructured":"Chengbin Chu. One-machine scheduling for minimizing total flow time with release dates. In Proceedings of Rensselaer\u2019s Second Conference on C.I.M, pages 570\u2013576, 1990."},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1002\/1520-6750(199210)39:6<859::AID-NAV3220390610>3.0.CO;2-W","volume":"39","author":"C. Chu","year":"1992","unstructured":"Chengbin Chu. A branch-and-bound algorithm to minimize total flow time with unequal release dates. Naval Research Logistics, 39:859\u2013875, 1992.","journal-title":"Naval Research Logistics"},{"issue":"2","key":"17_CR6","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1287\/moor.10.2.328","volume":"10","author":"P. G. Gazmuri","year":"1985","unstructured":"Pedro G. Gazmuri. Probabilistic analysis of a machine scheduling problem. Mathematics of Operations Research, 10(2):328\u2013339, 1985.","journal-title":"Mathematics of Operations Research"},{"key":"17_CR7","unstructured":"Michel X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proceedings of Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997."},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0166-218X(83)90019-7","volume":"5","author":"A.M.A. Hariri","year":"1983","unstructured":"A.M.A Hariri and C.N. Potts. An algorithm for single machine sequencing with release dates to minimize total weighted completion time. Discrete Applied Mathematics, 5:99\u2013109, 1983.","journal-title":"Discrete Applied Mathematics"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"J.A. Hoogeveen and A.P.A Vestjens. Optimal on-line algorithms for single-machine scheduling. In Proceedings of the Fifth Conference On Integer Programming and Combinatorial Optimization, pages 404\u2013414, 1996.","DOI":"10.1007\/3-540-61310-2_30"},{"key":"17_CR10","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"O.H. Ibarra and C.E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the Association for Computing Machinery, 22:463\u2013468, 1975.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"17_CR11","doi-asserted-by":"publisher","first-page":":1155","DOI":"10.1137\/S0097539796305778","volume":"28","author":"H. Kellerer","year":"1999","unstructured":"Hans Kellerer, Thomas Tautenhahn, and Gerhard J. Woeginger. Approximability and nonapproximability results for minimizing total flow time on a single machine. SI AM Journal of Computing, 28(4):1155\u20131166, 1999.","journal-title":"SI AM Journal of Computing"},{"key":"17_CR12","doi-asserted-by":"publisher","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, and P. Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343\u2013362, 1977.","journal-title":"Annals of Discrete Mathematics"},{"key":"17_CR13","first-page":"199","volume":"82","author":"C. Phillips","year":"1998","unstructured":"C. Phillips, C. Stein, and J. Wein. Minimizing average completion time in the presence of release dates. Mathematical Programming, 82:199\u2013223, 1998.","journal-title":"Mathematical Programming"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Andreas S. Schulz and Martin Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. Technical Report 533\/1996, Technische Universit\u00e4t Berlin, Fachbereich Mathematik, 1996.","DOI":"10.1007\/3-540-63397-9_32"},{"key":"17_CR15","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":"17_CR16","unstructured":"E. Torng and P. Uthaisombut. Lower bounds for srpt-subsequence algorithms for nonpreemptive scheduling. In Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, pages 973\u2013974, 1999."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experimentation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44808-X_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T01:54:09Z","timestamp":1736992449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44808-X_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425601","9783540448082"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-44808-x_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}