{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:25:23Z","timestamp":1761294323084,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T00:00:00Z","timestamp":1623196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["691672"],"award-info":[{"award-number":["691672"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005713","name":"Technische Universit\u00e4t M\u00fcnchen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005713","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to <jats:italic>m<\/jats:italic> identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that <jats:italic>Greedy<\/jats:italic> is <jats:inline-formula><jats:alternatives><jats:tex-math>$$(2-1\/m)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\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>-competitive. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201. No deterministic online strategy can obtain a competitiveness smaller than 1.88.\u00a0In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that <jats:italic>Greedy<\/jats:italic> does not attain a competitive factor asymptotically smaller than\u00a02 in this setting. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds, for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4\/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3\/2 with high probability.<\/jats:p>","DOI":"10.1007\/s00453-021-00841-8","type":"journal-article","created":{"date-parts":[[2021,6,9]],"date-time":"2021-06-09T06:26:42Z","timestamp":1623220002000},"page":"2803-2832","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Scheduling in the Random-Order Model"],"prefix":"10.1007","volume":"83","author":[{"given":"Susanne","family":"Albers","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0364-2394","authenticated-orcid":false,"given":"Maximilian","family":"Janke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,9]]},"reference":[{"issue":"2","key":"841_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."},{"key":"841_CR2","doi-asserted-by":"crossref","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Proceedings of 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). Springer, pp. 16\u201328 (2007)","DOI":"10.1007\/978-3-540-74208-1_2"},{"issue":"6","key":"841_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212512","volume":"65","author":"M Babaioff","year":"2018","unstructured":"Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Matroid secretary problems. J. ACM 65(6), 1\u201326 (2018)","journal-title":"J. ACM"},{"key":"841_CR4","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Fiat, A., Karloff, H., Vohra, R.: New algorithms for an ancient scheduling problem. In: Proceedings of 24th ACM Symposium on Theory of Computing (STOC), pp. 51\u201358 (1992)","DOI":"10.1145\/129712.129718"},{"issue":"3","key":"841_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., Rabani, Y.: A better lower bound for on-line scheduling. Inf. Process. Lett. 50(3), 113\u2013116 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"841_CR6","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.: A lower bound for randomized on-line scheduling algorithms. Inf. Process. Lett. 51(5), 219\u2013222 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"01","key":"841_CR7","doi-asserted-by":"publisher","first-page":"1540011","DOI":"10.1142\/S0217595915400114","volume":"32","author":"L Chen","year":"2015","unstructured":"Chen, L., Ye, D., Zhang, G.: Approximating the optimal algorithm for online scheduling problems via dynamic programming. Asia Pac. J. Oper. Res. 32(01), 1540011 (2015)","journal-title":"Asia Pac. J. Oper. Res."},{"issue":"1\u20133","key":"841_CR8","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2004.11.018","volume":"337","author":"T Cheng","year":"2005","unstructured":"Cheng, T., Kellerer, H., Kotov, V.: Semi-on-line multiprocessor scheduling with given total processing time. Theor. Comput. Sci. 337(1\u20133), 134\u2013146 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"841_CR9","doi-asserted-by":"crossref","unstructured":"Dohrau, J.: Online makespan scheduling with sublinear advice. In: 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Springer, pp. 177\u2013188 (2015)","DOI":"10.1007\/978-3-662-46078-8_15"},{"key":"841_CR10","first-page":"627","volume":"4","author":"E Dynkin","year":"1963","unstructured":"Dynkin, E.: The optimum choice of the instant for stopping a Markov process. Sov. Math. 4, 627\u2013629 (1963)","journal-title":"Sov. Math."},{"key":"841_CR11","doi-asserted-by":"crossref","unstructured":"Englert, M., \u00d6zmen, D., Westermann, M.: The power of reordering for online minimum makespan scheduling. In: Proceedings of 49th 676 IEEE Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 603\u2013612 (2008)","DOI":"10.1109\/FOCS.2008.46"},{"issue":"2","key":"841_CR12","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."},{"key":"841_CR13","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: A simple O (log log (rank))-competitive algorithm for the matroid secretary problem. In: Proceedings of 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, pp. 1189\u20131201 (2014)","DOI":"10.1137\/1.9781611973730.79"},{"issue":"6","key":"841_CR14","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. Sched. 3(6), 343\u2013353 (2000)","journal-title":"J. Sched."},{"issue":"2","key":"841_CR15","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. Comput. 22(2), 349\u2013355 (1993)","journal-title":"SIAM J. Comput."},{"key":"841_CR16","doi-asserted-by":"crossref","unstructured":"G\u00f6bel, O., Kesselheim, T., T\u00f6nnis, A.: Online appointment scheduling in the random order model. In: Algorithms-ESA 2015. Springer, pp. 680\u2013692 (2015)","DOI":"10.1007\/978-3-662-48350-3_57"},{"key":"841_CR17","first-page":"982","volume":"8","author":"G Goel","year":"2008","unstructured":"Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to Adwords. SODA 8, 982\u2013991 (2008)","journal-title":"SODA"},{"key":"841_CR18","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, pp. 564\u2013565 (2000)"},{"issue":"9","key":"841_CR19","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R Graham","year":"1966","unstructured":"Graham, R.: Bounds for certain multiprocessing anomalies. Bell Syst. Tech. J. 45(9), 1563\u20131581 (1966)","journal-title":"Bell Syst. Tech. J."},{"key":"841_CR20","unstructured":"Gupta, A., Mehta, R., Molinaro, M.: Maximizing Profit with Convex Costs in the Random-Order Model. arXiv preprint arXiv:1804.08172 (2018)"},{"issue":"1","key":"841_CR21","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D Hochbaum","year":"1987","unstructured":"Hochbaum, D., Shmoys, D.: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"key":"841_CR22","doi-asserted-by":"crossref","unstructured":"Karande, C., Mehta, A., Tripathi, P.: Online bipartite matching with unknown distributions. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 587\u2013596 (2011)","DOI":"10.1145\/1993636.1993715"},{"issue":"2","key":"841_CR23","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., Torng, E.: A better algorithm for an ancient scheduling problem. J. Algorithms 20(2), 400\u2013430 (1996)","journal-title":"J. Algorithms"},{"issue":"4","key":"841_CR24","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.orl.2013.03.005","volume":"41","author":"H Kellerer","year":"2013","unstructured":"Kellerer, H., Kotov, V.: An efficient algorithm for bin stretching. Oper. Res. Lett. 41(4), 343\u2013346 (2013)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"841_CR25","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."},{"key":"841_CR26","first-page":"359","volume":"96","author":"C Kenyon","year":"1996","unstructured":"Kenyon, C.: Best-fit bin-packing with random order. SODA 96, 359\u2013364 (1996)","journal-title":"Best-fit bin-packing with random order. SODA"},{"key":"841_CR27","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., T\u00f6nnis, A., Radke, K., V\u00f6cking, B.: Primal beats dual on online packing LPs in the random-order model. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 303\u2013312 (2014)","DOI":"10.1145\/2591796.2591810"},{"key":"841_CR28","first-page":"630","volume":"5","author":"R Kleinberg","year":"2005","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. SODA 5, 630\u2013631 (2005)","journal-title":"SODA"},{"key":"841_CR29","doi-asserted-by":"crossref","unstructured":"Lachish, O.: O (log log rank) competitive ratio for the matroid secretary problem. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, pp. 326\u2013335 (2014)","DOI":"10.1109\/FOCS.2014.42"},{"key":"841_CR30","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Yan, Q.: Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 597\u2013606 (2011)","DOI":"10.1145\/1993636.1993716"},{"key":"841_CR31","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, pp. 426\u2013431 (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"841_CR32","doi-asserted-by":"crossref","unstructured":"Molinaro, M.: Online and random-order load balancing simultaneously. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp. 1638\u20131650 (2017)","DOI":"10.1137\/1.9781611974782.108"},{"issue":"3","key":"841_CR33","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/s10951-007-0019-7","volume":"11","author":"C Osborn","year":"2008","unstructured":"Osborn, C., Torng, E.: List\u2019s worst-average-case or WAC ratio. J. Sched. 11(3), 213\u2013215 (2008)","journal-title":"J. Sched."},{"key":"841_CR34","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Online scheduling. (2004)"},{"key":"841_CR35","unstructured":"Rudin, J., III.: Improved bounds for the on-line scheduling problem (2001)"},{"key":"841_CR36","doi-asserted-by":"crossref","unstructured":"Rudin, J., III., Chandrasekaran, R.: Improved bounds for the online scheduling problem. SIAM J. Comput. 32(3), 717\u2013735 (2003)","DOI":"10.1137\/S0097539702403438"},{"issue":"2","key":"841_CR37","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":"1","key":"841_CR38","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. Inf. Process. Lett. 63(1), 51\u201355 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"841_CR39","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"D Sleator","year":"1985","unstructured":"Sleator, D., Tarjan, R.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00841-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00841-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00841-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,5]],"date-time":"2021-08-05T11:06:38Z","timestamp":1628161598000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00841-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,9]]},"references-count":39,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["841"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00841-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,6,9]]},"assertion":[{"value":"7 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}