**Reference**:- Erik D. Demaine and Morteza Zadimoghaddam, “Scheduling to Minimize Power Consumption using Submodular Functions”, in
*Proceedings of the 22nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2010)*, Santorini, Greece, June 13–15, 2010, pages 21–29. **Abstract**:-
We develop logarithmic approximation algorithms for extremely general
formulations of multiprocessor multi-interval offline task scheduling to
minimize power usage. Here each processor has an arbitrary specified power
consumption to be turned on for each possible time interval, and each job has
a specified list of time interval/processor pairs during which it could be
scheduled. (A processor need not be in use for an entire interval it is
turned on.) If there is a feasible schedule, our algorithm finds a feasible
schedule with total power usage within an
*O*(log*n*) factor of optimal, where*n*is the number of jobs. (Even in a simple setting with one processor, the problem is Set-Cover hard.) If not all jobs can be scheduled and each job has a specified value, then our algorithm finds a schedule of value at least (1 − ε)*Z*and power usage within an*O*(log (1/ε)) factor of the optimal schedule of value at least*Z*, for any specified*Z*and ε > 0. At the foundation of our work is a general framework for logarithmic approximation to maximizing any submodular function subject to budget constraints. **Comments**:- This paper is also available from the ACM Digital Library.
**Availability**:- The paper is available in PostScript (314k), gzipped PostScript (132k), and PDF (222k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GapScheduling_JScheduling (Scheduling to Minimize Gaps and Power Consumption)
- GapScheduling_SPAA2007 (Scheduling to Minimize Gaps and Power Consumption)

See also other papers by Erik Demaine.

Last updated February 10, 2020 by Erik Demaine.