{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T23:01:23Z","timestamp":1773702083999,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T00:00:00Z","timestamp":1629331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In the classic minimum makespan scheduling problem, we are given an input sequence of <jats:italic>n<\/jats:italic> jobs with sizes. A scheduling algorithm has to assign the jobs to <jats:italic>m<\/jats:italic> parallel machines. The objective is to minimize the makespan, which is the time it takes until all jobs are processed. In this paper, we consider online scheduling algorithms without preemption. However, we allow the online algorithm to change the assignment of up to <jats:italic>k<\/jats:italic> jobs at the end for some limited number <jats:italic>k<\/jats:italic>. For <jats:italic>m<\/jats:italic> identical machines, Albers and Hellwig (Algorithmica 79(2):598\u2013623, 2017) give tight bounds on the competitive ratio in this model. The precise ratio depends on, and increases with, <jats:italic>m<\/jats:italic>. It lies between 4\/3 and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\approx 1.4659$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>1.4659<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. They show that <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = O(m)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is sufficient to achieve this bound and no <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = o(n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can result in a better bound. We study <jats:italic>m<\/jats:italic> uniform machines, i.e., machines with different speeds, and show that this setting is strictly harder. For sufficiently large <jats:italic>m<\/jats:italic>, there is a <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta = \\varTheta (1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that, for <jats:italic>m<\/jats:italic> machines with only two different machine speeds, no online algorithm can achieve a competitive ratio of less than <jats:inline-formula><jats:alternatives><jats:tex-math>$$1.4659 + \\delta $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1.4659<\/mml:mn>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>\u03b4<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = o(n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>o<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We present a new algorithm for the uniform machine setting. Depending on the speeds of the machines, our scheduling algorithm achieves a competitive ratio that lies between 4\/3 and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\approx 1.7992$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>\u2248<\/mml:mo>\n                    <mml:mn>1.7992<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = O(m)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also show that <jats:inline-formula><jats:alternatives><jats:tex-math>$$k = \\varOmega (m)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u03a9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>m<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is necessary to achieve a competitive ratio below 2. Our algorithm is based on maintaining a specific imbalance with respect to the completion times of the machines, complemented by a bicriteria approximation algorithm that minimizes the makespan and maximizes the average completion time for certain sets of machines.<\/jats:p>","DOI":"10.1007\/s00453-021-00852-5","type":"journal-article","created":{"date-parts":[[2021,8,19]],"date-time":"2021-08-19T06:03:30Z","timestamp":1629353010000},"page":"3537-3566","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Online Makespan Scheduling with Job Migration on Uniform Machines"],"prefix":"10.1007","volume":"83","author":[{"given":"Matthias","family":"Englert","sequence":"first","affiliation":[]},{"given":"David","family":"Mezlaf","sequence":"additional","affiliation":[]},{"given":"Matthias","family":"Westermann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,19]]},"reference":[{"issue":"2","key":"852_CR1","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. 29(2), 459\u2013473 (1999)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"852_CR2","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1007\/s00453-016-0209-9","volume":"79","author":"S Albers","year":"2017","unstructured":"Albers, S., Hellwig, M.: On the value of job migration in online makespan minimization. Algorithmica 79(2), 598\u2013623 (2017)","journal-title":"Algorithmica"},{"issue":"3","key":"852_CR3","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S.A., Waarts, O.: On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 44(3), 486\u2013504 (1997)","journal-title":"J. ACM"},{"issue":"3","key":"852_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.J., 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":"3","key":"852_CR5","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.J., Rabani, Y.: A better lower bound for on-line scheduling. Inf. Process. Lett. 50(3), 113\u2013116 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"852_CR6","doi-asserted-by":"publisher","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"},{"issue":"4","key":"852_CR7","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., Woeginger, G.J.: New lower and upper bounds for on-line scheduling. Oper. Res. Lett. 16(4), 221\u2013230 (1994)","journal-title":"Oper. Res. Lett."},{"issue":"45","key":"852_CR8","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. Theor. Comput. Sci. 412(45), 6269\u20136278 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"852_CR9","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1142\/S0129054114500191","volume":"25","author":"N Ding","year":"2014","unstructured":"Ding, N., Lan, Y., Chen, X., D\u00f3sa, G., Guo, H., Han, X.: Online minimum makespan scheduling with a buffer. Int. J. Found. Comput. Sci. 25(5), 525\u2013536 (2014)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"852_CR10","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s10878-008-9200-y","volume":"20","author":"G D\u00f3sa","year":"2010","unstructured":"D\u00f3sa, G., Epstein, L.: Online scheduling with a buffer on related machines. J. Combin. Optim. 20(2), 161\u2013179 (2010)","journal-title":"J. Combin. Optim."},{"issue":"1","key":"852_CR11","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1137\/090766139","volume":"25","author":"G D\u00f3sa","year":"2011","unstructured":"D\u00f3sa, G., Epstein, L.: Preemptive online scheduling with reordering. SIAM J. Discrete Math. 25(1), 21\u201349 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"8\u201310","key":"852_CR12","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1016\/j.tcs.2010.10.019","volume":"412","author":"G D\u00f3sa","year":"2011","unstructured":"D\u00f3sa, G., Wang, Y., Han, X., Guo, H.: Online scheduling with rearrangement on two related machines. Theor. Comput. Sci. 412(8\u201310), 642\u2013653 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"852_CR13","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00224-013-9451-6","volume":"56","author":"T Ebenlendr","year":"2015","unstructured":"Ebenlendr, T., Sgall, J.: A lower bound on deterministic online algorithms for scheduling on related machines without preemption. Theory Comput. Syst. 56(1), 73\u201381 (2015)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"852_CR14","doi-asserted-by":"publisher","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."},{"issue":"4","key":"852_CR15","doi-asserted-by":"publisher","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":"3","key":"852_CR16","doi-asserted-by":"publisher","first-page":"1230","DOI":"10.1137\/100794006","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., van Stee, R.: Max-min online allocations with a reordering buffer. SIAM J. Discrete Math. 25(3), 1230\u20131250 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"852_CR17","first-page":"107","volume":"9","author":"U Faigle","year":"1989","unstructured":"Faigle, U., Kern, W., Tur\u00e1n, G.: On the performance of on-line algorithms for partition problems. Acta Cybern. 9(2), 107\u2013119 (1989)","journal-title":"Acta Cybern."},{"issue":"6","key":"852_CR18","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.: On-line scheduling revisited. J. Schedul. 3(6), 343\u2013353 (2000)","journal-title":"J. Schedul."},{"issue":"3","key":"852_CR19","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1137\/0216037","volume":"16","author":"DK 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."},{"key":"852_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman (1979)"},{"key":"852_CR21","unstructured":"Gormley, T., Reingold, N., Torng, E., Westbrook, J.: Generating adversaries for request-answer games. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 564\u2013565 (2000)"},{"issue":"1","key":"852_CR22","doi-asserted-by":"publisher","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 multiprocessing anomalies. Bell Syst. Tech. J. 45(1), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"issue":"2","key":"852_CR23","doi-asserted-by":"publisher","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."},{"issue":"3","key":"852_CR24","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"DS Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"852_CR25","doi-asserted-by":"publisher","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(2), 400\u2013430 (1996)","journal-title":"J. Algorithms"},{"issue":"5","key":"852_CR26","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/S0167-6377(98)00005-4","volume":"21","author":"H Kellerer","year":"1997","unstructured":"Kellerer, H., Kotov, V., Speranza, M.G., Tuza, Z.: Semi on-line algorithms for the partition problem. Oper. Res. Lett. 21(5), 235\u2013242 (1997)","journal-title":"Oper. Res. Lett."},{"issue":"21\u201323","key":"852_CR27","doi-asserted-by":"publisher","first-page":"2099","DOI":"10.1016\/j.tcs.2009.01.007","volume":"410","author":"M Liu","year":"2009","unstructured":"Liu, M., Xu, Y., Chu, C., Zheng, F.: Online scheduling on two uniform machines to minimize the makespan. Theor. Comput. Sci. 410(21\u201323), 2099\u20132109 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"852_CR28","doi-asserted-by":"publisher","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(1), 116\u2013125 (1997)","journal-title":"Oper. Res."},{"key":"852_CR29","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chap, Online Scheduling. CRC Press (2004)"},{"key":"852_CR30","unstructured":"Rudin, J.F., III: Improved Bound for the Online Scheduling Problem. Ph.D. thesis, University of Texas at Dallas (2001)"},{"key":"852_CR31","doi-asserted-by":"crossref","unstructured":"Rudin, J.F., III., Chandrasekaran, R.: Improved bound for the online scheduling problem. SIAM J. Comput. 32(3), 717\u2013735 (2003)","DOI":"10.1137\/S0097539702403438"},{"issue":"2","key":"852_CR32","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. Math. Oper. Res. 34(2), 481\u2013498 (2009)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"852_CR33","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. Oper. Res. Lett. 36(2), 250\u2013254 (2008)","journal-title":"Oper. Res. Lett."},{"issue":"16","key":"852_CR34","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1016\/j.ipl.2012.05.009","volume":"112","author":"Y Wang","year":"2012","unstructured":"Wang, Y., Benko, A., Chen, X., D\u00f3sa, G., Guo, H., Han, X., Sik-L\u00e1nyi, C.: Online scheduling with one rearrangement at the end: revisited. Inf. Process. Lett. 112(16), 641\u2013645 (2012)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00852-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00852-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00852-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T11:38:10Z","timestamp":1637321890000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00852-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,19]]},"references-count":34,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["852"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00852-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,19]]},"assertion":[{"value":"26 May 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}