Document Open Access Logo

Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling

Author Nguyen Kim Thang

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2016.20.pdf
  • Filesize: 404 kB
  • 14 pages

Document Identifiers

Author Details

Nguyen Kim Thang

Cite As Get BibTex

Nguyen Kim Thang. Lagrangian Duality based Algorithms in Online Energy-Efficient Scheduling. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SWAT.2016.20

Abstract

We study online scheduling problems in the general energy model of speed scaling with power down. The latter is a combination of the two extensively studied energy models, speed scaling and power down, toward a more realistic one. Due to the limits of the current techniques, only few results have been known in the general energy model in contrast to the large literature of the previous ones. 

In the paper, we consider a Lagrangian duality based approach to design and analyze algorithms in the general energy model. We show the applicability of the approach to problems which are unlikely to admit a convex relaxation. Specifically, we consider the problem of minimizing energy with a single machine in which jobs arrive online and have to be processed before their deadlines. We present an alpha^alpha-competitive algorithm (whose the analysis is tight up to a constant factor) where the energy power function is of typical form z^alpha + g for constants alpha > 2 and g non-negative. Besides, we also consider the problem of minimizing the weighted flow-time plus energy. We give an O(alpha/ln(alpha))-competitive algorithm; that matches (up to a constant factor) to the currently best known algorithm for this problem in the restricted model of speed scaling.

Subject Classification

Keywords
  • Online Scheduling
  • Energy Minimization
  • Speed Scaling and Power-down
  • Lagrangian Duality

Metrics

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

References

  1. Susanne Albers. Energy-efficient algorithms. Commun. ACM, 53(5):86-96, 2010. Google Scholar
  2. Susanne Albers and Antonios Antoniadis. Race to idle: new algorithms for speed scaling with a sleep state. ACM Transactions on Algorithms (TALG), 10(2):9, 2014. Google Scholar
  3. S. Anand, Naveen Garg, and Amit Kumar. Resource augmentation for weighted flow-time explained by dual fitting. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms, pages 1228-1241, 2012. Google Scholar
  4. Spyros Angelopoulos, Giorgio Lucarelli, and Kim Thang Nguyen. Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow time problems. In Proc. 23rd European Symposium of Algorithms (ESA), pages 35-46. Springer, 2015. Google Scholar
  5. Antonios Antoniadis, Chien-Chung Huang, and Sebastian Ott. A fully polynomial-time approximation scheme for speed scaling with sleep state. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1102-1113. SIAM, 2015. Google Scholar
  6. Yossi Azar, Nikhil R. Devanur, Zhiyi Huang, and Debmalya Panigrahi. Speed scaling in the non-clairvoyant model. In Proc. 27th ACM on Symposium on Parallelism in Algorithms and Architectures, pages 133-142, 2015. Google Scholar
  7. Evripidis Bampis, Christoph Dürr, Fadi Kacem, and Ioannis Milis. Speed scaling with power down scheduling for agreeable deadlines. Sustainable Computing: Informatics and Systems, 2(4):184-189, 2012. Google Scholar
  8. Nikhil Bansal, Ho-Leung Chan, Dmitriy Katz, and Kirk Pruhs. Improved bounds for speed scaling in devices obeying the cube-root rule. Theory of Computing, 8(1):209-229, 2012. Google Scholar
  9. Nikhil Bansal, Ho-Leung Chan, and Kirk Pruhs. Speed scaling with an arbitrary power function. In Proc. 20th ACM-SIAM Symposium on Discrete Algorithms, pages 693-701, 2009. Google Scholar
  10. Nikhil Bansal, Tracy Kimbrel, and Kirk Pruhs. Speed scaling to manage energy and temperature. J. ACM, 54(1), 2007. Google Scholar
  11. Nikhil R. Devanur and Zhiyi Huang. Primal dual gives almost optimal energy efficient online algorithms. In Proc. 25th ACM-SIAM Symposium on Discrete Algorithms, 2014. Google Scholar
  12. Anupam Gupta, Ravishankar Krishnaswamy, and Kirk Pruhs. Online primal-dual for non-linear optimization with applications to speed scaling. In Proc. 10th Workshop on Approximation and Online Algorithms, pages 173-186, 2012. Google Scholar
  13. Xin Han, Tak Wah Lam, Lap-Kei Lee, Isaac Kar-Keung To, and Prudence W. H. Wong. Deadline scheduling and power management for speed bounded processors. Theor. Comput. Sci., 411(40-42):3587-3600, 2010. Google Scholar
  14. Sungjin Im, Janardhan Kulkarni, and Kamesh Munagala. Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints. In STOC, 2014. Google Scholar
  15. Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, and Kirk Pruhs. Selfishmigrate: A scalable algorithm for non-clairvoyantly scheduling heterogeneous processors. In Proc. 55th IEEE Symposium on Foundations of Computer Science, 2014. Google Scholar
  16. Sandy Irani, Sandeep K. Shukla, and Rajesh Gupta. Algorithms for power savings. ACM Transactions on Algorithms, 3(4), 2007. Google Scholar
  17. Nguyen Kim Thang. Lagrangian duality in online scheduling with resource augmentation and speed scaling. In Proc. 21st European Symposium on Algorithms, pages 755-766, 2013. 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