Abstract
Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state. Each machine requires L units of energy to awaken from the sleep state and in its active state the machine can process jobs and consumes a unit of energy per unit time. We allow for preemption and migration of jobs and provide the first constant approximation algorithm for this problem
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
| Pages | 2758–2769 |
| Publication status | Published - 2020 |
| Externally published | Yes |
| Event | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Hilton Salt Lake City Center, Salt Lake City, United States Duration: 5 Jan 2020 → 8 Jan 2020 Conference number: 31 |
Conference
| Conference | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |
|---|---|
| Abbreviated title | SODA 2020 |
| Country/Territory | United States |
| City | Salt Lake City |
| Period | 5/01/20 → 8/01/20 |
Keywords
- n/a OA procedure