Paper by Erik D. Demaine

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)