{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:34:46Z","timestamp":1759667686168},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,6,27]],"date-time":"2007-06-27T00:00:00Z","timestamp":1182902400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,5]]},"DOI":"10.1007\/s00224-007-9007-8","type":"journal-article","created":{"date-parts":[[2007,6,28]],"date-time":"2007-06-28T20:33:28Z","timestamp":1183062808000},"page":"431-449","source":"Crossref","is-referenced-by-count":5,"title":["Optimal On-Line Algorithms to Minimize Makespan on Two Machines with Resource Augmentation"],"prefix":"10.1007","volume":"42","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Arik","family":"Ganot","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,6,27]]},"reference":[{"issue":"2","key":"9007_CR1","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1137\/S0097539797324874","volume":"29","author":"S. Albers","year":"1999","unstructured":"Albers, S.: Better bounds for online scheduling. SIAM J. Comput. 29(2), 459\u2013473 (1999)","journal-title":"SIAM J. Comput."},{"key":"9007_CR2","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line load balancing with applications to machine scheduling and virtual circuit routing. J. ACM 44, 486\u2013504 (1997)","journal-title":"J. ACM"},{"key":"9007_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Dhamdhere, K., K\u00f6nemann, J., Sinha, A.: Non-clairvoyant scheduling for minimizing mean slowdown. In: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201903), pp.\u00a0260\u2013270 (2003)","DOI":"10.1007\/3-540-36494-3_24"},{"key":"9007_CR4","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0020-0190(94)00026-3","volume":"50","author":"Y. Bartal","year":"1994","unstructured":"Bartal, Y., Karloff, H., Rabani, Y.: A better lower bound for on-line scheduling. Inf. Process. Lett. 50, 113\u2013116 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"9007_CR5","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1006\/jcss.1995.1074","volume":"51","author":"Y. Bartal","year":"1995","unstructured":"Bartal, Y., Fiat, A., Karloff, H., Vohra, R.: New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci. 51(3), 359\u2013366 (1995)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9007_CR6","first-page":"181","volume":"6","author":"P. Berman","year":"1999","unstructured":"Berman, P., Coulston, C.: Speed is more powerful than clairvoyance. Nord. J. Comput. 6(2), 181\u2013193 (1999)","journal-title":"Nord. J. Comput."},{"issue":"1","key":"9007_CR7","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P. Berman","year":"2000","unstructured":"Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. J. Algorithms 35(1), 108\u2013121 (2000)","journal-title":"J. Algorithms"},{"key":"9007_CR8","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","volume":"18","author":"B. Chen","year":"1995","unstructured":"Chen, B., van Vliet, A., Woeginger, G.J.: An optimal algorithm for preemptive on-line scheduling. Oper. Res. Lett. 18, 127\u2013131 (1995)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"9007_CR9","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1137\/0213044","volume":"13","author":"G. Dobson","year":"1984","unstructured":"Dobson, G.: Scheduling independent tasks on uniform processors. SIAM J. Comput. 13(4), 705\u2013716 (1984)","journal-title":"SIAM J. Comput."},{"key":"9007_CR10","doi-asserted-by":"crossref","unstructured":"Ebenlendr, T., Jawor, W., Sgall, J.: Preemptive online scheduling: optimal algorithms for all speeds. In: Proc. of the 14th Annual European Symposium on Algorithms (ESA2006), pp.\u00a0327\u2013339 (2006)","DOI":"10.1007\/11841036_31"},{"issue":"2","key":"9007_CR11","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0167-6377(01)00085-2","volume":"29","author":"L. Epstein","year":"2001","unstructured":"Epstein, L.: Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios. Oper. Res. Lett. 29(2), 93\u201398 (2001)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"9007_CR12","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/S0167-6377(02)00179-7","volume":"30","author":"L. Epstein","year":"2002","unstructured":"Epstein, L., Favrholdt, L.M.: Optimal preemptive semi-online scheduling to minimize makespan on two related machines. Oper. Res. Lett. 30(4), 269\u2013275 (2002)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9007_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.jalgor.2004.11.002","volume":"57","author":"L. Epstein","year":"2005","unstructured":"Epstein, L., Favrholdt, L.M.: Optimal non-preemptive semi-online scheduling on two related machines. J. Algorithms 57(1), 49\u201373 (2005)","journal-title":"J. Algorithms"},{"issue":"1","key":"9007_CR14","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0167-6377(99)00062-0","volume":"26","author":"L. Epstein","year":"2000","unstructured":"Epstein, L., Sgall, J.: A lower bound for on-line scheduling on uniformly related machines. Oper. Res. Lett. 26(1), 17\u201322 (2000)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9007_CR15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1002\/jos.60","volume":"4","author":"L. Epstein","year":"2001","unstructured":"Epstein, L., Noga, J., Seiden, S.S., Sgall, J., Woeginger, G.J.: Randomized online scheduling on two uniform machines. J. Sched. 4(2), 71\u201392 (2001)","journal-title":"J. Sched."},{"key":"9007_CR16","first-page":"107","volume":"9","author":"U. Faigle","year":"1989","unstructured":"Faigle, U., Kern, W., Turan, G.: On the performance of online algorithms for partition problems. Acta Cybernetica 9, 107\u2013119 (1989)","journal-title":"Acta Cybernetica"},{"issue":"5","key":"9007_CR17","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R. Fleischer","year":"2000","unstructured":"Fleischer, R., Wahl, M.: Online scheduling revisited. J. Sched. 3(5), 343\u2013353 (2000)","journal-title":"J. Sched."},{"issue":"3","key":"9007_CR18","doi-asserted-by":"crossref","first-page":"554","DOI":"10.1137\/0216037","volume":"16","author":"D.K. Friesen","year":"1987","unstructured":"Friesen, D.K.: Tighter bounds for LPT scheduling on uniform processors. SIAM J. Comput. 16(3), 554\u2013560 (1987)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9007_CR19","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1137\/0206013","volume":"6","author":"T. Gonzalez","year":"1977","unstructured":"Gonzalez, T., Ibarra, O.H., Sahni, S.: Bounds for LPT schedules on uniform processors. SIAM J. Comput. 6(1), 155\u2013166 (1977)","journal-title":"SIAM J. Comput."},{"key":"9007_CR20","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u20192000), pp.\u00a0564\u2013565 (2000)"},{"key":"9007_CR21","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 Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"9007_CR22","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"R.L. Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17, 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"9007_CR23","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1145\/321992.321995","volume":"24","author":"E. Horwath","year":"1977","unstructured":"Horwath, E., Lam, E.C., Sethi, R.: A level algorithm for preemptive scheduling. J. Assoc. Comput. Mach. 24, 32\u201343 (1977)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"4","key":"9007_CR24","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1145\/347476.347479","volume":"47","author":"B. Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47(4), 214\u2013221 (2000)","journal-title":"J. ACM"},{"issue":"1","key":"9007_CR25","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0196-6774(03)00074-9","volume":"49","author":"B. Kalyanasundaram","year":"2003","unstructured":"Kalyanasundaram, B., Pruhs, K.: Maximizing job completions online. J. Algorithms 49(1), 63\u201385 (2003)","journal-title":"J. Algorithms"},{"issue":"2","key":"9007_CR26","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"D. Karger","year":"1996","unstructured":"Karger, D., Phillips, S., Torng, E.: A better algorithm for an ancient scheduling problem. J. Algorithms 20(2), 400\u2013430 (1996)","journal-title":"J. Algorithms"},{"key":"9007_CR27","unstructured":"Lam, T.W., To, K.K.: Trade-offs between speed and processor in hard-deadline scheduling. In: Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999), pp.\u00a0623\u2013632 (1999)"},{"key":"9007_CR28","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1287\/opre.45.1.116","volume":"45","author":"P. Mireault","year":"1997","unstructured":"Mireault, P., Orlin, J.B., Vohra, R.V.: A parametric worst case analysis of the LPT heuristic for two uniform machines. Oper. Res. 45, 116\u2013125 (1997)","journal-title":"Oper. Res."},{"key":"9007_CR29","unstructured":"Rudin, J.F. III: Improved bounds for the on-line scheduling problem. Ph.D. thesis, The University of Texas at Dallas (May 2001)"},{"issue":"1\u20132","key":"9007_CR30","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/S0304-3975(00)00288-7","volume":"262","author":"S. Seiden","year":"2001","unstructured":"Seiden, S.: Preemptive multiprocessor scheduling with rejection. Theor. Comput. Sci. 262(1\u20132), 437\u2013458 (2001)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"9007_CR31","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0167-6377(00)00053-5","volume":"27","author":"S. Seiden","year":"2000","unstructured":"Seiden, S., Sgall, J., Woeginger, G.: Semi-online scheduling with decreasing job sizes. Oper. Res. Lett. 27(5), 215\u2013221 (2000)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9007_CR32","doi-asserted-by":"crossref","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. Inf. Process. Lett. 63(1), 51\u201355 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9007_CR33","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D. Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28, 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"key":"9007_CR34","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/S0167-6377(98)00032-7","volume":"23","author":"J. Wen","year":"1998","unstructured":"Wen, J., Du, D.: Preemptive on-line scheduling for two uniform processors. Oper. Res. Lett. 23, 113\u2013116 (1998)","journal-title":"Oper. Res. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9007-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9007-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9007-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:34Z","timestamp":1558698694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9007-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6,27]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9007"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9007-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6,27]]}}}