Paper by Erik D. Demaine
- Erik D. Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar, and Morteza Zadimoghaddam, “Scheduling to Minimize Gaps and Power Consumption”, in Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), San Diego, California, June 9–11, 2007, pages 46–54.
This paper considers scheduling tasks while minimizing the power consumption
of one or more processors, each of which can go to sleep at a fixed
There are two natural versions of this problem, both considered extensively
in recent work: minimize the total power consumption (including computation
time), or minimize the number of “gaps” in execution.
For both versions in a multiprocessor system, we develop a
polynomial-time algorithm based on sophisticated dynamic programming.
In a generalization of the power-saving problem,
where each task can execute in any of a specified set of time intervals,
we develop a (1 + (2/3)α)-approximation,
and show that dependence on α is necessary.
In contrast, the analogous multi-interval gap scheduling problem
is set-cover hard (and thus not o(lg n)-approximable),
even in the special cases of just two intervals per job
or just three unit intervals per job.
We also prove several other hardness-of-approximation results.
Finally, we give an
for maximizing throughput given a hard upper bound on the number of gaps.
- The paper is 9 pages.
- The paper is available in PostScript (335k) and PDF (247k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- GapScheduling_JScheduling (Scheduling to Minimize Gaps and Power Consumption)
- SubmodularGapScheduling_SPAA2010 (Scheduling to Minimize Power Consumption using Submodular Functions)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated December 15, 2022 by