Document Open Access Logo

Nested Active-Time Scheduling

Authors Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, Seeun William Umboh

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.36.pdf
  • Filesize: 0.82 MB
  • 16 pages

Document Identifiers

Author Details

Nairen Cao
  • Georgetown University, Washington D.C., USA
Jeremy T. Fineman
  • Georgetown University, Washington D.C., USA
Shi Li
  • University at Buffalo, NY, USA
Julián Mestre
  • The University of Sydney, Australia
Katina Russell
  • Georgetown University, Washington D.C., USA
Seeun William Umboh
  • The University of Sydney, Australia

Cite As Get BibTex

Nairen Cao, Jeremy T. Fineman, Shi Li, Julián Mestre, Katina Russell, and Seeun William Umboh. Nested Active-Time Scheduling. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.36

Abstract

The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to g jobs during each timestep. The goal in the active-time problem is to minimize the number of active steps, i.e., timesteps in which at least one job is scheduled. In this way, the active time models parallel scheduling when there is a fixed cost for turning the machine on at each discrete step.
This paper presents a 9/5-approximation algorithm for a special case of the active-time scheduling problem in which job windows are laminar (nested). This result improves on the previous best 2-approximation for the general case.

Subject Classification

ACM Subject Classification
  • Theory of computation → Scheduling algorithms
Keywords
  • Scheduling algorithms
  • Active time
  • Approximation algorithm

Metrics

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

Related Versions

References

  1. Susanne Albers. Energy-efficient algorithms. Communications of the ACM, 53(5):86-96, 2010. Google Scholar
  2. Jessica Chang, Harold N. Gabow, and Samir Khuller. A model for minimizing active processor time. Algorithmica, 70(3):368-405, 2014. Google Scholar
  3. Jessica Chang, Samir Khuller, and Koyel Mukherjee. LP rounding and combinatorial algorithms for minimizing active and busy time. J. of Scheduling, 20(6):657-680, 2017. Google Scholar
  4. Vincent Chau and Minming Li. Active and Busy Time Scheduling Problem: A Survey, pages 219-229. Springer International Publishing, 2020. Google Scholar
  5. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, and Joseph Naor. Machine minimization for scheduling jobs with interval constraints. In Proc. of the 45th Symposium on Foundations of Computer Science, pages 81-90, 2004. Google Scholar
  6. Gruia Călinescu and Kai Wang. A new lp rounding algorithm for the active time problem. Journal of Scheduling, pages 1-10, March 2021. Google Scholar
  7. Sami Davies, Samir Khuller, and Shirley Zhang. Balancing flow time and energy consumption. In Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '22, pages 369-380, New York, NY, USA, 2022. Association for Computing Machinery. URL: https://doi.org/10.1145/3490148.3538582.
  8. Sandy Irani and Kirk R. Pruhs. Algorithmic problems in power management. SIGACT News, 36(2):63-76, 2005. Google Scholar
  9. Frederic Koehler and Samir Khuller. Busy time scheduling on a bounded number of machines (extended abstract). In Proc. of the 15th International Symposium on Algorithms and Data Structures, pages 521-532, 2017. Google Scholar
  10. Saurabh Kumar and Samir Khuller. Brief announcement: A greedy 2 approximation for the active time problem. In Proc. of the 30th on Symposium on Parallelism in Algorithms and Architectures, pages 347-349, 2018. Google Scholar
  11. Mozhengfu Liu and Xueyan Tang. Analysis of busy-time scheduling on heterogeneous machines. In Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA '21, pages 340-350, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3409964.3461795.
  12. Sagnik Saha and Manish Purohit. Np-completeness of the active time scheduling problem. arXiv preprint arXiv:2112.03255, 2021. Google Scholar
  13. Ward Van Heddeghem, Sofie Lambert, Bart Lannoo, Didier Colle, Mario Pickavet, and Piet Demeester. Trends in worldwide ICT electricity consumption from 2007 to 2012. Computer Communications, 50:64-76, 2014. Google Scholar
  14. Laurence A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica, 2(4):385-393, 1982. 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 About DROPS Imprint Privacy Contact