Name
Abstract | ||
|---|---|---|
We improve complexity bounds for energy-efficient non-preemptive scheduling problems for both the single processor and multiprocessor cases. As energy conservation has become a major concern, traditional scheduling problems have been revisited in the past few years to take into account the energy consumption [1]. We consider the speed scaling setting introduced by Yao et al. [20] where a set of jobs, each with a release date, deadline and work volume, are to be scheduled on a set of identical processors. The processors may change speed as a function of time and the energy they consume is the alpha th power of their speed integrated over time. The objective is then to find a feasible non-preemptive schedule which minimizes the total energy used. We show that for an arbitrarily number of processors and jobs with equal work volumes there is a 2(1 + epsilon)(5(1 + delta))(alpha-1) (B) over tilde (alpha) = O-alpha(1) approximation algorithm, where (B) over tilde (alpha) is the generalized Bell number. This is the first constant factor algorithm for the multi-processor case, and this also extends to arbitrary processor-dependent work volumes, up to losing a factor of ((1+r)r/2)(alpha) in the approximation, where r is the maximum ratio between two work volumes. For the single processor case, we introduce a new linear programming formulation of speed scaling, using a new constraint capturing non-preemption, and prove that its integrality gap is at most 12(alpha-1). With our new constraint we improve on the previously known unbounded integrality gap of at least Omega(n(alpha-1)). Finally, we deal with the inapproximabilty of speed scaling and we prove that the multiprocessor case is APX-hard, even in the special case where all release dates and deadlines are equal and r is 4. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-319-18263-6_10 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Journal | 8952 | 0302-9743 |
Citations | PageRank | References |
12 | 0.60 | 13 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vincent Cohen-Addad | 1 | 85 | 25.47 |
| Zhentao Li | 2 | 84 | 10.40 |
| Claire Mathieu | 3 | 452 | 25.78 |
| Ioannis Milis | 4 | 297 | 29.11 |