{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:37:48Z","timestamp":1759667868900,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,9,8]],"date-time":"2016-09-08T00:00:00Z","timestamp":1473292800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft (DE)","doi-asserted-by":"publisher","award":["Al 464\/7-1"],"award-info":[{"award-number":["Al 464\/7-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00453-016-0209-9","type":"journal-article","created":{"date-parts":[[2016,9,8]],"date-time":"2016-09-08T15:22:41Z","timestamp":1473348161000},"page":"598-623","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["On the Value of Job Migration in Online Makespan Minimization"],"prefix":"10.1007","volume":"79","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"given":"Matthias","family":"Hellwig","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,8]]},"reference":[{"issue":"1","key":"209_CR1","doi-asserted-by":"crossref","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. J. Algorithms 60(1), 42\u201359 (2006)","journal-title":"J. Algorithms"},{"key":"209_CR2","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, 459\u2013473 (1999)","journal-title":"SIAM J. Comput."},{"key":"209_CR3","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."},{"key":"209_CR4","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, 359\u2013366 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"209_CR5","first-page":"295","volume":"4","author":"E Ces\u00e1ro","year":"1885","unstructured":"Ces\u00e1ro, E.: Sur la s\u00e9rie harmonique. Nouvelles Ann. de Math. 3e S\u00e9r. 4, 295\u2013296 (1885)","journal-title":"Nouvelles Ann. de Math. 3e S\u00e9r."},{"key":"209_CR6","doi-asserted-by":"crossref","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. Inf. Process. Lett. 51, 219\u2013222 (1994)","journal-title":"Inf. Process. Lett."},{"key":"209_CR7","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.: A optimal algorithm for preemptive online scheduling. Oper. Res. Lett. 18, 127\u2013131 (1995)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"209_CR8","doi-asserted-by":"crossref","first-page":"1220","DOI":"10.1137\/130919738","volume":"43","author":"M Englert","year":"2014","unstructured":"Englert, M., \u00d6zmen, D., Westermann, M.: The power of reordering for online minimum makespan scheduling. SIAM J. Comput. 43(3), 1220\u20131237 (2014)","journal-title":"SIAM J. Comput."},{"key":"209_CR9","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 Cybern. 9, 107\u2013119 (1989)","journal-title":"Acta Cybern."},{"key":"209_CR10","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, 343\u2013353 (2000)","journal-title":"J. Sched."},{"key":"209_CR11","doi-asserted-by":"crossref","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. Comput. 22, 349\u2013355 (1993)","journal-title":"SIAM J. Comput."},{"key":"209_CR12","doi-asserted-by":"crossref","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multi-processing anomalies. Bell Syst. Tech. J. 45, 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"209_CR13","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1137\/0117039","volume":"17","author":"RL Graham","year":"1969","unstructured":"Graham, R.L.: Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2), 416\u2013429 (1969)","journal-title":"SIAM J. Appl. Math."},{"key":"209_CR14","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proceedings of 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 564\u2013565 (2000)"},{"key":"209_CR15","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"DS Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34, 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"209_CR16","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1006\/jagm.1996.0019","volume":"20","author":"DR Karger","year":"1996","unstructured":"Karger, D.R., Phillips, S.J., Torng, E.: A better algorithm for an ancient scheduling problem. J. Algorithms 20, 400\u2013430 (1996)","journal-title":"J. Algorithms"},{"issue":"9","key":"209_CR17","doi-asserted-by":"crossref","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. Inf. Process. Lett. 111(9), 423\u2013428 (2011)","journal-title":"Inf. Process. Lett."},{"key":"209_CR18","unstructured":"Rudin, III, J.F.: Improved bounds for the on-line scheduling problem. Ph.D. Thesis. The University of Texas at Dallas, May 2001"},{"key":"209_CR19","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1137\/S0097539702403438","volume":"32","author":"JF Rudin III","year":"2003","unstructured":"Rudin III, J.F., Chandrasekaran, R.: Improved bounds for the online scheduling problem. SIAM J. Comput. 32, 717\u2013735 (2003)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"209_CR20","doi-asserted-by":"crossref","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. Math. Oper. Res. 34(2), 481\u2013498 (2009)","journal-title":"Math. Oper. Res."},{"key":"209_CR21","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, 51\u201355 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"209_CR22","doi-asserted-by":"crossref","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. Oper. Res. Lett. 36(2), 250\u2013254 (2008)","journal-title":"Oper. Res. Lett."},{"key":"209_CR23","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28, 202\u2013208 (1985)","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0209-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0209-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0209-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T14:39:38Z","timestamp":1501511978000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0209-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9,8]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["209"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0209-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2016,9,8]]}}}