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.

BibTeX

@Article{GapScheduling_JScheduling,
  AUTHOR        = {Erik D. Demaine and Mohammad Ghodsi and
                   MohammadTaghi Hajiaghayi and Amin S. Sayedi-Roshkhar and
                   Morteza Zadimoghaddam},
  TITLE         = {Scheduling to Minimize Gaps and Power Consumption},
  JOURNAL       = {Journal of Scheduling},
  journalurl    = {http://www.springer.com/business+%26+management/operations+research/journal/10951},
  VOLUME        = 16,
  NUMBER        = 2,
  MONTH         = {April},
  YEAR          = 2013,
  PAGES         = {151--160},

  doi           = {https://dx.doi.org/10.1007/s10951-012-0309-6},
  dblp          = {https://dblp.org/rec/journals/scheduling/DemaineGHSZ13},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s10951-012-0309-6">SpringerLink</A>.},
  length        = {15 pages},
  papers        = {GapScheduling_SPAA2007; SubmodularGapScheduling_SPAA2010},
  replaces      = {GapScheduling_SPAA2007},
  withstudent   = 1,
}

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)