{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T09:34:02Z","timestamp":1725701642922},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642330896"},{"type":"electronic","value":"9783642330902"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33090-2_9","type":"book-chapter","created":{"date-parts":[[2012,8,28]],"date-time":"2012-08-28T11:29:11Z","timestamp":1346153351000},"page":"84-95","source":"Crossref","is-referenced-by-count":11,"title":["On the Value of Job Migration in Online Makespan Minimization"],"prefix":"10.1007","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Hellwig","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.jalgor.2004.10.002","volume":"60","author":"G. Aggarwal","year":"2006","unstructured":"Aggarwal, G., Motwani, R., Zhu, A.: The load rebalancing problem. Journal of Algorithms\u00a060(1), 42\u201359 (2006)","journal-title":"Journal of Algorithms"},{"key":"9_CR2","doi-asserted-by":"publisher","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.\u00a029, 459\u2013473 (1999)","journal-title":"SIAM J. Comput."},{"key":"9_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., Rabani, Y.: A better lower bound for on-line scheduling. Infomation Processing Letters\u00a050, 113\u2013116 (1994)","journal-title":"Infomation Processing Letters"},{"key":"9_CR4","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., Vohra, R.: New algorithms for an ancient scheduling problem. Journal of Computer and System Sciences\u00a051, 359\u2013366 (1995)","journal-title":"Journal of Computer and System Sciences"},{"issue":"31-33","key":"9_CR5","doi-asserted-by":"publisher","first-page":"2890","DOI":"10.1016\/j.tcs.2010.04.020","volume":"411","author":"Q. Cao","year":"2010","unstructured":"Cao, Q., Liu, Z.: Online scheduling with reassignment on two uniform machines. Theoretical Computer Science\u00a0411(31-33), 2890\u20132898 (2010)","journal-title":"Theoretical Computer Science"},{"issue":"45","key":"9_CR6","doi-asserted-by":"publisher","first-page":"6269","DOI":"10.1016\/j.tcs.2011.07.014","volume":"412","author":"X. Chen","year":"2011","unstructured":"Chen, X., Lan, Y., Benko, A., D\u00f3sa, G., Han, X.: Optimal algorithms for online scheduling with bounded rearrangement at the end. Theoretical Computer Science\u00a0412(45), 6269\u20136278 (2011)","journal-title":"Theoretical Computer Science"},{"key":"9_CR7","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., Woeginger, G.J.: A lower bound for randomized on-line scheduling algorithms. Information Processing Letters\u00a051, 219\u2013222 (1994)","journal-title":"Information Processing Letters"},{"key":"9_CR8","doi-asserted-by":"publisher","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.: A optimal algorithm for preemptive online scheduling. Operations Research Letters\u00a018, 127\u2013131 (1995)","journal-title":"Operations Research Letters"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1007\/978-3-642-04128-0_41","volume-title":"Algorithms - ESA 2009","author":"G. D\u00f3sa","year":"2009","unstructured":"D\u00f3sa, G., Epstein, L.: Preemptive Online Scheduling with Reordering. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 456\u2013467. Springer, Heidelberg (2009)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Englert, M., \u00d6zmen, D., Westermann, M.: The power of reordering for online minimum makespan scheduling. In: Proc. 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 603\u2013612 (2008)","DOI":"10.1109\/FOCS.2008.46"},{"key":"9_CR11","first-page":"107","volume":"9","author":"U. Faigle","year":"1989","unstructured":"Faigle, U., Kern, W., Turan, G.: On the performance of on-line algorithms for partition problems. Acta Cybernetica\u00a09, 107\u2013119 (1989)","journal-title":"Acta Cybernetica"},{"key":"9_CR12","doi-asserted-by":"publisher","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. Journal of Scheduling\u00a03, 343\u2013353 (2000)","journal-title":"Journal of Scheduling"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/0222026","volume":"22","author":"G. Galambos","year":"1993","unstructured":"Galambos, G., Woeginger, G.: An on-line scheduling heuristic with better worst case ratio than Graham\u2019s list scheduling. SIAM J. on Computing\u00a022, 349\u2013355 (1993)","journal-title":"SIAM J. on Computing"},{"key":"9_CR14","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 multi-processing anomalies. Bell System Technical Journal\u00a045, 1563\u20131581 (1966)","journal-title":"Bell System Technical Journal"},{"issue":"2","key":"9_CR15","doi-asserted-by":"publisher","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 Journal of Applied Mathematics\u00a017(2), 416\u2013429 (1969)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"9_CR16","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proc. 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 564\u2013565 (2000)"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: Theoretical and practical results. Journal of the ACM\u00a034, 144\u2013162 (1987)","journal-title":"Journal of the ACM"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R., Phillips, S.J., Torng, E.: A better algorithm for an ancient scheduling problem. Journal of Algorithms\u00a020, 400\u2013430 (1996)","journal-title":"Journal of Algorithms"},{"issue":"9","key":"9_CR19","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.ipl.2011.01.002","volume":"111","author":"X. Min","year":"2011","unstructured":"Min, X., Liu, J., Wang, Y.: Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines. Information Processing Letters\u00a0111(9), 423\u2013428 (2011)","journal-title":"Information Processing Letters"},{"key":"9_CR20","unstructured":"Rudin III, J.F.: Improved bounds for the on-line scheduling problem. Ph.D. Thesis. The University of Texas at Dallas (May 2001)"},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1287\/moor.1090.0381","volume":"34","author":"P. Sanders","year":"2009","unstructured":"Sanders, P., Sivadasan, N., Skutella, M.: Online scheduling with bounded migration. Mathematics of Operations Research\u00a034(2), 481\u2013498 (2009)","journal-title":"Mathematics of Operations Research"},{"key":"9_CR22","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\u00a063, 51\u201355 (1997)","journal-title":"Information Processing Letters"},{"issue":"2","key":"9_CR23","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.orl.2007.06.004","volume":"36","author":"Z. Tan","year":"2008","unstructured":"Tan, Z., Yu, S.: Online scheduling with reassignment. Operations Research Letters\u00a036(2), 250\u2013254 (2008)","journal-title":"Operations Research Letters"},{"key":"9_CR24","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D.D. Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Communications of the ACM\u00a028, 202\u2013208 (1985)","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33090-2_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T07:55:10Z","timestamp":1620114910000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33090-2_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642330896","9783642330902"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33090-2_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}