Document Open Access Logo

Optimally Handling Commitment Issues in Online Throughput Maximization

Authors Franziska Eberle , Nicole Megow , Kevin Schewior

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.41.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Franziska Eberle
  • Department for Mathematics and Computer Science, University of Bremen, Germany
Nicole Megow
  • Department for Mathematics and Computer Science, University of Bremen, Germany
Kevin Schewior
  • Universität zu Köln, Department of Mathematics and Computer Science, Germany

Funding

  • Megow, Nicole: Partially supported by the German Science Foundation (DFG) under contract ME 3825/1.
  • Schewior, Kevin: Partially supported by the DAAD within the PRIME program using funds of BMBF and the EU Marie Curie Actions.

Cite As Get BibTex

Franziska Eberle, Nicole Megow, and Kevin Schewior. Optimally Handling Commitment Issues in Online Throughput Maximization. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 41:1-41:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.41

Abstract

We consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on m machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis, it is commonly required that jobs contain some slack ε > 0, which means that the feasible time window for scheduling a job is at least 1+ε times its processing time. In this paper, we answer the question on how to handle commitment requirements which enforce that a scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services and disallows last-minute rejections of critical tasks. We present the first online algorithm for handling commitment on parallel machines for arbitrary slack ε. When the scheduler must commit upon starting a job, the algorithm is Θ(1/ε)-competitive. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job’s slack becomes less than a δ-fraction of its size, we prove a competitive ratio of 𝒪(1/(ε - δ)) for 0 < δ < ε. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithms admits any bounded competitive ratio.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Scheduling algorithms
Keywords
  • Deadline scheduling
  • throughput
  • online algorithms
  • competitive analysis

Metrics

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

References

  1. Kunal Agrawal, Jing Li, Kefu Lu, and Benjamin Moseley. Scheduling parallelizable jobs online to maximize throughput. In Proceedings of the Latin American Theoretical Informatics Symposium (LATIN), pages 755-776, 2018. URL: https://doi.org/10.1007/978-3-319-77404-6_55.
  2. Yossi Azar, Inna Kalp-Shaltiel, Brendan Lucier, Ishai Menache, Joseph Naor, and Jonathan Yaniv. Truthful online scheduling with commitments. In Proceedings of the ACM Symposium on Economics and Computations (EC), pages 715-732, 2015. URL: https://doi.org/10.1145/2764468.2764535.
  3. Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs. Competitive algorithms for due date scheduling. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), pages 28-39, 2007. URL: https://doi.org/10.1007/978-3-540-73420-8_5.
  4. Sanjoy K. Baruah and Jayant R. Haritsa. Scheduling for overload in real-time systems. IEEE Trans. Computers, 46(9):1034-1039, 1997. URL: https://doi.org/10.1109/12.620484.
  5. Sanjoy K. Baruah, Jayant R. Haritsa, and Nitin Sharma. On-line scheduling to maximize task completions. In Proceedings of the IEEE Real-Time Systems Symposium (RTSS), pages 228-236, 1994. URL: https://doi.org/10.1109/REAL.1994.342713.
  6. Sanjoy K. Baruah, Gilad Koren, Decao Mao, Bhubaneswar Mishra, Arvind Raghunathan, Louis E. Rosier, Dennis E. Shasha, and Fuxing Wang. On the competitiveness of on-line real-time task scheduling. Real-Time Systems, 4(2):125-144, 1992. URL: https://doi.org/10.1007/BF00365406.
  7. Ran Canetti and Sandy Irani. Bounding the power of preemption in randomized scheduling. SIAM J. Comput., 27(4):993-1015, 1998. URL: https://doi.org/10.1137/S0097539795283292.
  8. Lin Chen, Franziska Eberle, Nicole Megow, Kevin Schewior, and Cliff Stein. A general framework for handling commitment in online throughput maximization. Math. Prog., 2020. URL: https://doi.org/10.1007/s10107-020-01469-2.
  9. Lin Chen, Nicole Megow, and Kevin Schewior. The power of migration in online machine minimization. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 175-184, 2016. URL: https://doi.org/10.1145/2935764.2935786.
  10. Lin Chen, Nicole Megow, and Kevin Schewior. An 𝒪(log m)-competitive algorithm for online machine minimization. SIAM J. Comput., 47(6):2057-2077, 2018. URL: https://doi.org/10.1137/17M116032X.
  11. Bhaskar DasGupta and Michael A. Palis. Online real-time preemptive scheduling of jobs with deadlines. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 96-107, 2000. URL: https://doi.org/10.1007/3-540-44436-X_11.
  12. Michael L. Dertouzos and Aloysius K. Mok. Multiprocessor on-line scheduling of hard-real-time tasks. IEEE Trans. Software Eng., 15(12):1497-1506, 1989. URL: https://doi.org/10.1109/32.58762.
  13. Andrew D. Ferguson, Peter Bodík, Srikanth Kandula, Eric Boutin, and Rodrigo Fonseca. Jockey: guaranteed job latency in data parallel clusters. In Proceedings of the European Conference on Computer Systems (EuroSys), pages 99-112, 2012. URL: https://doi.org/10.1145/2168836.2168847.
  14. Juan A. Garay, Joseph Naor, Bülent Yener, and Peng Zhao. On-line admission control and packet scheduling with interleaving. In Proceedings of the IEEE International Conference on Computer Communications (INFOCOM), pages 94-103, 2002. URL: https://doi.org/10.1109/INFCOM.2002.1019250.
  15. Michael H. Goldwasser. Patience is a virtue: The effect of slack on competitiveness for admission control. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 396-405, 1999. URL: http://dl.acm.org/citation.cfm?id=314500.314592.
  16. Ronald L. Graham, Eugene L. Lawler, Jan Karel Lenstra, and Alexander H.G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. In Discrete Optimization II, volume 5 of Annals of Discrete Mathematics, pages 287-326. Elsevier, 1979. URL: https://doi.org/10.1016/S0167-5060(08)70356-X.
  17. Sungjin Im and Benjamin Moseley. General profit scheduling and the power of migration on heterogeneous machines. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 165-173, 2016. URL: https://doi.org/10.1145/2935764.2935771.
  18. Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. J. ACM, 47(4):617-643, 2000. URL: https://doi.org/10.1145/347476.347479.
  19. Bala Kalyanasundaram and Kirk Pruhs. Eliminating migration in multi-processor scheduling. J. Algorithms, 38(1):2-24, 2001. URL: https://doi.org/10.1006/jagm.2000.1128.
  20. Bala Kalyanasundaram and Kirk Pruhs. Maximizing job completions online. J. Algorithms, 49(1):63-85, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00074-9.
  21. Gilad Koren and Dennis E. Shasha. MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling. Theor. Comput. Sci., 128(1-2):75-97, 1994. URL: https://doi.org/10.1016/0304-3975(94)90165-1.
  22. Gilad Koren and Dennis E. Shasha. Dsuperscriptover: An optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J. Comput., 24(2):318-339, 1995. URL: https://doi.org/10.1137/S0097539792236882.
  23. Richard J. Lipton and Andrew Tomkins. Online interval scheduling. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 302-311, 1994. URL: http://dl.acm.org/citation.cfm?id=314464.314506.
  24. Brendan Lucier, Ishai Menache, Joseph Naor, and Jonathan Yaniv. Efficient online scheduling for deadline-sensitive jobs: extended abstract. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 305-314, 2013. URL: https://doi.org/10.1145/2486159.2486187.
  25. Kirk Pruhs and Clifford Stein. How to schedule when you have to buy your energy. In Proceedings of the International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 352-365, 2010. URL: https://doi.org/10.1007/978-3-642-15369-3_27.
  26. Chris Schwiegelshohn and Uwe Schwiegelshohn. The power of migration for online slack scheduling. In Proceedings of the European Symposium of Algorithms (ESA), volume 57, pages 75:1-75:17, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.75.
  27. Gerhard J. Woeginger. On-line scheduling of jobs with fixed start and end times. Theor. Comput. Sci., 130(1):5-16, 1994. URL: https://doi.org/10.1016/0304-3975(94)90150-3.
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 About DROPS Imprint Privacy Contact