{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T14:10:28Z","timestamp":1736863828326,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540660194"},{"type":"electronic","value":"9783540487777"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48777-8_29","type":"book-chapter","created":{"date-parts":[[2007,3,2]],"date-time":"2007-03-02T13:43:11Z","timestamp":1172842991000},"page":"391-399","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling Two Machines with Release Times"],"prefix":"10.1007","author":[{"given":"John","family":"Noga","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Steve","family":"Seiden","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,4,30]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S. Better bounds for online scheduling. In Proceedings of the 29th ACM Symposium on Theory of Computing (1997), pp. 130\u2013139.","DOI":"10.1145\/258533.258566"},{"issue":"3","key":"29_CR2","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y. Bartal","year":"1995","unstructured":"Bartal, Y., Fiat, A., Karloff, H., and Vohra, R. New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences 51,3 (Dec 1995), 359\u2013366.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"29_CR3","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0020-0190(94)00026-3","volume":"50","author":"Y. Bartal","year":"1994","unstructured":"Bartal, Y., Karloff, H., and Rabani, Y. A better lower bound for on-line scheduling. Information Processing Letters 50,3 (May 1994), 113\u2013116.","journal-title":"Information Processing Letters"},{"issue":"5","key":"29_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0020-0190(94)00110-3","volume":"51","author":"B. Chen","year":"1994","unstructured":"Chen, B., van Vliet, A., and Woeginger, G. A lower bound for randomized on-line scheduling algorithms. Information Processing Letters 51,5 (Sep 1994), 219\u2013222.","journal-title":"Information Processing Letters"},{"issue":"4","key":"29_CR5","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0167-6377(94)90071-X","volume":"16","author":"B. Chen","year":"1994","unstructured":"Chen, B., van Vliet, A., and Woeginger, G. New lower and upper bounds for on-line scheduling. Operations Research Letters 16,4 (Nov 1994), 221\u2013230.","journal-title":"Operations Research Letters"},{"issue":"4","key":"29_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0167-6377(97)00040-0","volume":"21","author":"B. Chen","year":"1997","unstructured":"CHEN, B., and VESTJENS, A. Scheduling on identical machines: How good is LPT in an online setting? Operations Research Letters 21,4 (Nov 1997), 165\u2013169.","journal-title":"Operations Research Letters"},{"issue":"2","key":"29_CR7","first-page":"107","volume":"9","author":"U. Faigle","year":"1989","unstructured":"Faigle, U., Kern, W., and Tur\u00e0an, G. On the performance of on-line algorithms for partition problems. Acta Cybernetica 9,2 (1989), 107\u2013119.","journal-title":"Acta Cybernetica"},{"issue":"2","key":"29_CR8","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/0222026","volume":"22","author":"G. Galambos","year":"1993","unstructured":"Galambos, G., and Woeginger, G. An online scheduling heuristic with better worst case ratio than Graham\u2019s list scheduling. SIAM Journal on Computing 22,2 (Apr 1993), 349\u2013355.","journal-title":"SIAM Journal on Computing"},{"key":"29_CR9","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R. L. Graham","year":"1966","unstructured":"Graham, R. L. Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal 45 (1966), 1563\u20131581.","journal-title":"Bell Systems Technical Journal"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Hall, L., and Shmoys, D. Approximation schemes for constrained scheduling problems. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (1989), pp. 134\u2013139.","DOI":"10.1109\/SFCS.1989.63468"},{"issue":"2","key":"29_CR11","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"D. Karger","year":"1996","unstructured":"Karger, D., Phillips, S., and Torng, E. A better algorithm for an ancient scheduling problem. Journal of Algorithms 20,2 (Mar 1996), 400\u2013430.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"29_CR12","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF01762111","volume":"3","author":"A. Karlin","year":"1988","unstructured":"Karlin, A., Manasse, M., Rudolph, L., and Sleator, D. Competitive snoopy caching. Algorithmica 3,1 (1988), 79\u2013119.","journal-title":"Algorithmica"},{"issue":"1","key":"29_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF01294261","volume":"11","author":"N. Reingold","year":"1994","unstructured":"Reingold, N., Westbrook, J., and Sleator, D. Randomized competitive algorithms for the list update problem. Algorithmica 11,1 (Jan 1994), 15\u201332.","journal-title":"Algorithmica"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Seiden, S. S. Randomized algorithms for that ancient scheduling problem. In Proceedings of the 5th Workshop on Algorithms and Data Structures (Aug 1997), pp. 210\u2013223.","DOI":"10.1007\/3-540-63307-3_61"},{"issue":"1","key":"29_CR15","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0020-0190(97)00093-8","volume":"63","author":"J. Sgall","year":"1997","unstructured":"Sgall, J. A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters 63,1 (Jul 1997), 51\u201355.","journal-title":"Information Processing Letters"},{"key":"29_CR16","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Wein, J., and Williamson, D. Scheduling parallel machines online. In Proceedings of the 32nd Symposium on Foundations of Computer Science (Oct 1991), pp. 131\u2013140.","DOI":"10.1109\/SFCS.1991.185361"},{"issue":"2","key":"29_CR17","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"Sleator, D., and Tarjan, R. Amortized efficiency of list update and paging rules. Communications of the ACM 28,2 (Feb 1985), 202\u2013208.","journal-title":"Communications of the ACM"},{"key":"29_CR18","unstructured":"Stougie, L., and Vestjens, A. P. A. Randomized on-line scheduling: How low can\u2019t you go? Manuscript, 1997."},{"key":"29_CR19","volume-title":"On-line Machine Scheduling","author":"A. P. A. Vestjens","year":"1997","unstructured":"Vestjens, A. P. A.On-line Machine Scheduling. PhD thesis, Eindhoven University of Technology, The Netherlands, 1997."},{"key":"29_CR20","unstructured":"Von Neumann, J., and Morgenstern, O.Theory of games and economic behavior, 1st ed. Princeton University Press, 1944."},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Yao, A. C. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (1977), pp. 222\u2013227.","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48777-8_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T13:38:15Z","timestamp":1736861895000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48777-8_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540660194","9783540487777"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-48777-8_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}