Scheduling to Minimize Power Consumption using Submodular Functions
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 sp...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2012
|
| Online Access: | http://hdl.handle.net/1721.1/72589 https://orcid.org/0000-0003-3803-5703 |
| Summary: | 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. |
|---|