{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:36:21Z","timestamp":1757543781434},"publisher-location":"Boston","reference-count":14,"publisher":"Kluwer Academic Publishers","isbn-type":[{"type":"print","value":"1402081405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/1-4020-8141-3_18","type":"book-chapter","created":{"date-parts":[[2006,2,21]],"date-time":"2006-02-21T15:15:11Z","timestamp":1140534911000},"page":"209-222","source":"Crossref","is-referenced-by-count":22,"title":["Scheduling With Release Times and Deadlines on A Minimum Number of Machines"],"prefix":"10.1007","author":[{"given":"Mark","family":"Cieliebak","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Erlebach","sequence":"additional","affiliation":[]},{"given":"Fabian","family":"Hennecke","sequence":"additional","affiliation":[]},{"given":"Birgitta","family":"Weber","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Widmayer","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"18_CR1","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"A. Bar-Noy, R. Bar-Yehuda, A. Freund, J.S. Naor, and B. Schieber. A unified approach to approximating resource allocation and scheduling. Journal of the ACM, 48(5): 1069\u20131090, 2001.","journal-title":"Journal of the ACM"},{"issue":"2","key":"18_CR2","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A. Bar-Noy","year":"2001","unstructured":"A. Bar-Noy, S. Guha, J.S. Naor, and B. Schieber. Approximating the throughput of multiple machines in real-time scheduling. SIAM Journal on Computing, 31(2):331\u2013352, 2001.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"18_CR3","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/A:1009822211065","volume":"4","author":"P. Berman","year":"2000","unstructured":"P. Berman and B. DasGupta. Multi-phase algorithms for throughput maximization for real-time scheduling. Journal of Combinatorial Optimization, 4(3):307\u2013323, 2000.","journal-title":"Journal of Combinatorial Optimization"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt, V.B. Le, and J.P. Spinrad. Graph Classes: a Survey. SIAM Monographs on Discrete Mathematics and Applications, 1999.","DOI":"10.1137\/1.9780898719796"},{"key":"18_CR5","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy and S. Naor. New hardness results for congestion minimization and machine scheduling. accepted for STOC\u201904, 2004.","DOI":"10.1145\/1007352.1007364"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"J. Chuzhoy, R. Ostrovsky, and Y. Rabani. Approximation algorithms for the job interval selection problem and related scheduling problems. In IEEE Symposium on Foundations of Computer Science, pages 348\u2013356, 2001.","DOI":"10.1109\/SFCS.2001.959909"},{"key":"18_CR7","unstructured":"M. Cieliebak, T. Erlebach, F. Hennecke, B. Weber, and P. Widmayer. Scheduling jobs on a minimum number of machines. Technical Report 419, Institute of Theoretical Computer Science, ETH Z\u00fcrich, 2003."},{"key":"18_CR8","unstructured":"E.G. Coffman Jr., M.R. Garey, and D.S. Johnson. Approximation algorithms for bin packing: A survey. In D. Hochbaum, editor, Approximation Algorithms for NP-hard Problems. PWS, 1996."},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/S0196-6774(02)00291-2","volume":"46","author":"T. Erlebach","year":"2003","unstructured":"T. Erlebach and F.C.R. Spieksma. Interval selection: Applications, algorithms, and lower bounds. Journal of Algorithms, 46(1):27\u201353, 2003.","journal-title":"Journal of Algorithms"},{"key":"18_CR10","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Company, New York, 1979."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, and D.B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S.C. Graves, A.H.G. Rinnooy Kan, and P. Zip kin, editors, Handbooks in Operations Research and Management Science, volume 4, pages 445\u2013522. North-Holland, 1993.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"F. Malucelli and S. Nicoloso. Shiftable interval graphs. In Proc. 6th International Conference on Graph Theory, 2000.","DOI":"10.1016\/S1571-0653(05)80167-2"},{"issue":"3","key":"18_CR13","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"D.D. Sleator and R.E. Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362\u2013391, 1983.","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BFb0053973","volume":"1444","author":"F.C.R. Spieksma","year":"1998","unstructured":"F.C.R. Spieksma. Approximating an interval scheduling problem. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, volume 1444, pages 169\u2013180. Springer-Verlag LNCS, 1998.","journal-title":"International Workshop on Approximation Algorithms for Combinatorial Optimization Problems"}],"container-title":["IFIP International Federation for Information Processing","Exploring New Frontiers of Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/1-4020-8141-3_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T20:28:10Z","timestamp":1619555290000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/1-4020-8141-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["1402081405"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/1-4020-8141-3_18","relation":{},"subject":[]}}