License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.51
URN: urn:nbn:de:0030-drops-154849
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15484/
Antoniadis, Antonios ;
Kumar, Gunjan ;
Kumar, Nikhil
Skeletons and Minimum Energy Scheduling
Abstract
Consider the problem where n jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor has two available states: a sleep state where no energy is consumed but also no processing can take place, and an active state which consumes energy at a rate of one, and in which jobs can be processed. Transitioning from the active to the sleep does not incur any further energy cost, but transitioning from the sleep to the active state requires q energy units. Jobs may be preempted and (in the multi-processor case) migrated.
The single-processor case of the problem is known to be solvable in polynomial time via an involved dynamic program, whereas the only known approximation algorithm for the multi-processor case attains an approximation factor of 3 and is based on rounding the solution to a linear programming relaxation of the problem. In this work, we present efficient and combinatorial approximation algorithms for both the single- and the multi-processor setting. Before, only an algorithm based on linear programming was known for the multi-processor case. Our algorithms build upon the concept of a skeleton, a basic (and not necessarily feasible) schedule that captures the fact that some processor(s) must be active at some time point during an interval. Finally, we further demonstrate the power of skeletons by providing a 2-approximation algorithm for the multiprocessor case, thus improving upon the recent breakthrough 3-approximation result. Our algorithm is based on a novel rounding scheme of a linear-programming relaxation of the problem which incorporates skeletons.
BibTeX - Entry
@InProceedings{antoniadis_et_al:LIPIcs.ISAAC.2021.51,
author = {Antoniadis, Antonios and Kumar, Gunjan and Kumar, Nikhil},
title = {{Skeletons and Minimum Energy Scheduling}},
booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
pages = {51:1--51:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-214-3},
ISSN = {1868-8969},
year = {2021},
volume = {212},
editor = {Ahn, Hee-Kap and Sadakane, Kunihiko},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/15484},
URN = {urn:nbn:de:0030-drops-154849},
doi = {10.4230/LIPIcs.ISAAC.2021.51},
annote = {Keywords: scheduling, energy-efficiency, approximation algorithms, dynamic programming, combinatorial algorithms}
}
|
Keywords: |
|
scheduling, energy-efficiency, approximation algorithms, dynamic programming, combinatorial algorithms |
|
Collection: |
|
32nd International Symposium on Algorithms and Computation (ISAAC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
30.11.2021 |
