**Reference**:- 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. **Abstract**:-
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
cost α.
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*O*(√*n*)-approximation for maximizing throughput given a hard upper bound on the number of gaps. **Length**:- The paper is 9 pages.
**Availability**:- 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.

Last updated December 29, 2018 by Erik Demaine.