Document Open Access Logo

Scheduling in the Random-Order Model

Authors Susanne Albers, Maximilian Janke

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.68.pdf
  • Filesize: 486 kB
  • 18 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Computer Science, Technical University of Munich, Germany
Maximilian Janke
  • Department of Computer Science, Technical University of Munich, Germany

Funding

Work supported by the European Research Council, Grant Agreement No. 691672, project APEG.

Cite AsGet BibTex

Susanne Albers and Maximilian Janke. Scheduling in the Random-Order Model. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.68

Abstract

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 [Graham, 1966]. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201 [Fleischer and Wahl, 2000]. No deterministic online strategy can obtain a competitiveness smaller than 1.88 [Rudin III, 2001]. 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 [Osborn and Torng, 2008]. 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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Scheduling
  • makespan minimization
  • online algorithm
  • competitive analysis
  • lower bound
  • random-order

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Albers. Better bounds for online scheduling. SIAM Journal on Computing, 29(2):459-473, 1999. Publisher: SIAM. Google Scholar
  2. M. Babaioff, N. Immorlica, D. Kempe, and Robert Kleinberg. A knapsack secretary problem with applications. In Proc. 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 16-28. Springer, 2007. Google Scholar
  3. M. Babaioff, N. Immorlica, David Kempe, and R. Kleinberg. Matroid Secretary Problems. J. ACM, 65(6):1-26, 2018. Publisher: ACM New York, NY, USA. Google Scholar
  4. Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. In Proc. 24th ACM Symposium on Theory of Computing (STOC), pages 51-58, 1992. Google Scholar
  5. Y. Bartal, H. Karloff, and Y. Rabani. A better lower bound for on-line scheduling. Inf. Process. Lett., 50(3):113-116, 1994. Google Scholar
  6. B. Chen, A. van Vliet, and G. Woeginger. A lower bound for randomized on-line scheduling algorithms. Inf. Process. Lett., 51(5):219-222, 1994. Publisher: Elsevier. Google Scholar
  7. L. Chen, D. Ye, and G. Zhang. Approximating the optimal algorithm for online scheduling problems via dynamic programming. Asia-Pacific Journal of Operational Research, 32(01):1540011, 2015. Publisher: World Scientific. Google Scholar
  8. T.C.E. Cheng, H. Kellerer, and V. Kotov. Semi-on-line multiprocessor scheduling with given total processing time. Theoretical computer science, 337(1-3):134-146, 2005. Publisher: Elsevier. Google Scholar
  9. J. Dohrau. Online makespan scheduling with sublinear advice. In 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 177-188. Springer, 2015. Google Scholar
  10. E.B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics, 4:627-629, 1963. Google Scholar
  11. M. Englert, D. Özmen, and M. Westermann. The power of reordering for online minimum makespan scheduling. In Proc. 49th 676 IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 603-612. IEEE, 2008. Google Scholar
  12. U. Faigle, W. Kern, and G. Turán. On the performance of on-line algorithms for partition problems. Acta cybernetica, 9(2):107-119, 1989. Google Scholar
  13. M. Feldman, O. Svensson, and R. Zenklusen. A simple O (log log (rank))-competitive algorithm for the matroid secretary problem. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1189-1201. SIAM, 2014. Google Scholar
  14. R. Fleischer and M. Wahl. On-line scheduling revisited. Journal of Scheduling, 3(6):343-353, 2000. Publisher: Wiley Online Library. Google Scholar
  15. G. Galambos and G. Woeginger. An on-line scheduling heuristic with better worst-case ratio than Graham’s list scheduling. SIAM Journal on Computing, 22(2):349-355, 1993. Publisher: SIAM. Google Scholar
  16. G. Goel and A. Mehta. Online budgeted matching in random input models with applications to Adwords. In SODA, volume 8, pages 982-991, 2008. Google Scholar
  17. T. Gormley, N. Reingold, E. Torng, and J. Westbrook. Generating adversaries for request-answer games. In Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pages 564-565, 2000. Google Scholar
  18. R. Graham. Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9):1563-1581, 1966. Publisher: Wiley Online Library. Google Scholar
  19. Anupam Gupta, Ruta Mehta, and Marco Molinaro. Maximizing Profit with Convex Costs in the Random-order Model. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107, pages 71:1-71:14, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.71.
  20. D.S. Hochbaum and D.B. Shmoys. Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM, 34(1):144-162, 1987. Publisher: ACM New York, NY, USA. Google Scholar
  21. C. Karande, A. Mehta, and P. Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 587-596, 2011. Google Scholar
  22. D.R. Karger, S.J. Phillips, and E. Torng. A better algorithm for an ancient scheduling problem. Journal of Algorithms, 20(2):400-430, 1996. Publisher: Elsevier. Google Scholar
  23. H. Kellerer and V. Kotov. An efficient algorithm for bin stretching. Operations Research Letters, 41(4):343-346, 2013. Publisher: Elsevier. Google Scholar
  24. H. Kellerer, V. Kotov, M.G. Grazia Speranza, and Z. Tuza. Semi on-line algorithms for the partition problem. Operations Research Letters, 21(5):235-242, 1997. Publisher: Elsevier. Google Scholar
  25. C. Kenyon. Best-Fit Bin-Packing with Random Order. In SODA, volume 96, pages 359-364, 1996. Google Scholar
  26. T. Kesselheim, A. Tönnis, K. Radke, and B. Vöcking. 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, pages 303-312, 2014. Google Scholar
  27. R.D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In SODA, volume 5, pages 630-631, 2005. Google Scholar
  28. O. Lachish. O (log log rank) competitive ratio for the matroid secretary problem. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 326-335. IEEE, 2014. Google Scholar
  29. M. Mahdian and Q. Yan. 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, pages 597-606, 2011. Google Scholar
  30. A. Meyerson. Online facility location. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 426-431. IEEE, 2001. Google Scholar
  31. M. Molinaro. Online and random-order load balancing simultaneously. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1638-1650. SIAM, 2017. Google Scholar
  32. C.J. Osborn and E. Torng. List’s worst-average-case or WAC ratio. Journal of Scheduling, 11(3):213-215, 2008. Publisher: Springer. Google Scholar
  33. K. Pruhs, J. Sgall, and E. Torng. Online scheduling. CRC Press, 2004. Google Scholar
  34. J.F. Rudin III. Improved bounds for the on-line scheduling problem, 2001. Google Scholar
  35. J.F. Rudin III and R. Chandrasekaran. Improved bounds for the online scheduling problem. SIAM Journal on Computing, 32(3):717-735, 2003. Publisher: SIAM. Google Scholar
  36. P. Sanders, N. Sivadasan, and M. Skutella. Online scheduling with bounded migration. Mathematics of Operations Research, 34(2):481-498, 2009. Publisher: INFORMS. Google Scholar
  37. J. Sgall. A lower bound for randomized on-line multiprocessor scheduling. Inf. Process. Lett., 63(1):51-55, 1997. Publisher: Citeseer. Google Scholar
  38. D.D. Sleator and R.E. Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28(2):202-208, 1985. Publisher: ACM New York, NY, USA. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact