**Reference**:- Erik D. Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar, and Morteza Zadimoghaddam, “Scheduling to Minimize Gaps and Power Consumption”,
*Journal of Scheduling*, volume 16, number 2, April 2013, pages 151–160. **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. **Comments**:- This paper is also available from SpringerLink.
**Length**:- The paper is 15 pages.
**Availability**:- The paper is available in PostScript (644k), gzipped PostScript (311k), and PDF (346k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GapScheduling_SPAA2007 (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 January 18, 2021 by Erik Demaine.