×

Scheduling in the random-order model. (English) Zbl 1519.90067

Summary: Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to \(m\) identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is \((2-1/m)\)-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. In 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 Greedy does not attain a competitive factor asymptotically smaller than \(2\) 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.

MSC:

90B35 Deterministic scheduling theory in operations research
68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Albers, S., Better bounds for online scheduling, SIAM J. Comput., 29, 2, 459-473 (1999) · Zbl 0943.68183 · doi:10.1137/S0097539797324874
[2] 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-28 (2007) · Zbl 1171.90417
[3] Babaioff, M.; Immorlica, N.; Kempe, D.; Kleinberg, R., Matroid secretary problems, J. ACM, 65, 6, 1-26 (2018) · Zbl 1425.68461 · doi:10.1145/3212512
[4] 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-58 (1992) · Zbl 1295.90008
[5] Bartal, Y.; Karloff, H.; Rabani, Y., A better lower bound for on-line scheduling, Inf. Process. Lett., 50, 3, 113-116 (1994) · Zbl 0807.68013 · doi:10.1016/0020-0190(94)00026-3
[6] Chen, B.; van Vliet, A.; Woeginger, G., A lower bound for randomized on-line scheduling algorithms, Inf. Process. Lett., 51, 5, 219-222 (1994) · Zbl 0821.68011 · doi:10.1016/0020-0190(94)00110-3
[7] Chen, L.; Ye, D.; Zhang, G., Approximating the optimal algorithm for online scheduling problems via dynamic programming, Asia Pac. J. Oper. Res., 32, 1, 1540011 (2015) · Zbl 1311.90058 · doi:10.1142/S0217595915400114
[8] Cheng, T.; Kellerer, H.; Kotov, V., Semi-on-line multiprocessor scheduling with given total processing time, Theor. Comput. Sci., 337, 1-3, 134-146 (2005) · Zbl 1087.68015 · doi:10.1016/j.tcs.2004.11.018
[9] 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-188 (2015) · Zbl 1432.68589
[10] Dynkin, E., The optimum choice of the instant for stopping a Markov process, Sov. Math., 4, 627-629 (1963) · Zbl 0242.60018
[11] Englert, M., Özmen, 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-612 (2008) · Zbl 1301.68277
[12] Faigle, U.; Kern, W.; Turán, G., On the performance of on-line algorithms for partition problems, Acta Cybern., 9, 2, 107-119 (1989) · Zbl 0689.68051
[13] 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-1201 (2014) · Zbl 1372.68285
[14] Fleischer, R.; Wahl, M., On-line scheduling revisited, J. Sched., 3, 6, 343-353 (2000) · Zbl 0966.90032 · doi:10.1002/1099-1425(200011/12)3:6<343::AID-JOS54>3.0.CO;2-2
[15] Galambos, G.; Woeginger, G., An on-line scheduling heuristic with better worst-case ratio than Graham’s list scheduling, SIAM J. Comput., 22, 2, 349-355 (1993) · Zbl 0781.90051 · doi:10.1137/0222026
[16] Göbel, O., Kesselheim, T., Tönnis, A.: Online appointment scheduling in the random order model. In: Algorithms-ESA 2015. Springer, pp. 680-692 (2015) · Zbl 1466.90033
[17] Goel, G.; Mehta, A., Online budgeted matching in random input models with applications to Adwords, SODA, 8, 982-991 (2008) · Zbl 1192.68482
[18] 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-565 (2000) · Zbl 0962.91001
[19] Graham, R., Bounds for certain multiprocessing anomalies, Bell Syst. Tech. J., 45, 9, 1563-1581 (1966) · Zbl 0168.40703 · doi:10.1002/j.1538-7305.1966.tb01709.x
[20] Gupta, A., Mehta, R., Molinaro, M.: Maximizing Profit with Convex Costs in the Random-Order Model. arXiv preprint arXiv:1804.08172 (2018) · Zbl 1499.68413
[21] Hochbaum, D.; Shmoys, D., Using dual approximation algorithms for scheduling problems theoretical and practical results, J. ACM, 34, 1, 144-162 (1987) · doi:10.1145/7531.7535
[22] 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-596 (2011) · Zbl 1288.68287
[23] Karger, D.; Phillips, S.; Torng, E., A better algorithm for an ancient scheduling problem, J. Algorithms, 20, 2, 400-430 (1996) · Zbl 0844.68010 · doi:10.1006/jagm.1996.0019
[24] Kellerer, H.; Kotov, V., An efficient algorithm for bin stretching, Oper. Res. Lett., 41, 4, 343-346 (2013) · Zbl 1286.68029 · doi:10.1016/j.orl.2013.03.005
[25] Kellerer, H.; Kotov, V.; Speranza, MG; Tuza, Z., Semi on-line algorithms for the partition problem, Oper. Res. Lett., 21, 5, 235-242 (1997) · Zbl 0908.90165 · doi:10.1016/S0167-6377(98)00005-4
[26] Kenyon, C., Best-fit bin-packing with random order. SODA, 96, 359-364 (1996) · Zbl 0847.68050
[27] Kesselheim, T., Tönnis, A., Radke, K., Vöcking, 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-312 (2014) · Zbl 1315.68291
[28] Kleinberg, R., A multiple-choice secretary algorithm with applications to online auctions, SODA, 5, 630-631 (2005) · Zbl 1297.68268
[29] 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-335 (2014)
[30] 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-606 (2011) · Zbl 1288.68288
[31] Meyerson, A.: Online facility location. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, pp. 426-431 (2001)
[32] 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-1650 (2017) · Zbl 1415.90043
[33] Osborn, C.; Torng, E., List’s worst-average-case or WAC ratio, J. Sched., 11, 3, 213-215 (2008) · Zbl 1168.90463 · doi:10.1007/s10951-007-0019-7
[34] Pruhs, K., Sgall, J., Torng, E.: Online scheduling. (2004)
[35] Rudin, J., III.: Improved bounds for the on-line scheduling problem (2001)
[36] Rudin, J., III., Chandrasekaran, R.: Improved bounds for the online scheduling problem. SIAM J. Comput. 32(3), 717-735 (2003) · Zbl 1023.90031
[37] Sanders, P.; Sivadasan, N.; Skutella, M., Online scheduling with bounded migration, Math. Oper. Res., 34, 2, 481-498 (2009) · Zbl 1218.90176 · doi:10.1287/moor.1090.0381
[38] Sgall, J., A lower bound for randomized on-line multiprocessor scheduling, Inf. Process. Lett., 63, 1, 51-55 (1997) · Zbl 1336.68107 · doi:10.1016/S0020-0190(97)00093-8
[39] Sleator, D.; Tarjan, R., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 2, 202-208 (1985) · doi:10.1145/2786.2793
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.