Continuous Speed Scaling with Variability: A Simple and Direct Approach
Antoniadis, Antonios
Kling, Peter
Ott, Sebastian
Riechers, Sören
ddc:040
We consider an extension of the dynamic speed scaling scheduling model introduced by Yao et al.: A set of jobs, each with a release time, deadline, and workload, has to be scheduled on a single, speed-scalable processor. Both the maximum allowed speed of the processor and the energy costs may vary continuously over time. The objective is to find a feasible schedule that minimizes the total energy costs. Theoretical algorithm design for speed scaling problems often tends to discretize problems, as our tools in the discrete realm are often better developed or understood. Using the above speed scaling variant with variable, continuous maximal processor speeds and energy prices as an example, we demonstrate that a more direct approach via tools from variational calculus can not only lead to a very concise and elegant formulation and analysis, but also avoids the “explosion of variables/constraints” that often comes with discretizing. Using well-known tools from calculus of variations, we derive combinatorial optimality characteristics for our continuous problem and provide a quite concise and simple correctness proof.
Elsevier
2017
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://ris.uni-paderborn.de/record/110
Antoniadis A, Kling P, Ott S, Riechers S. Continuous Speed Scaling with Variability: A Simple and Direct Approach. <i>Theoretical Computer Science</i>. 2017:1-13. doi:<a href="https://doi.org/10.1016/j.tcs.2017.03.021">10.1016/j.tcs.2017.03.021</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.tcs.2017.03.021
info:eu-repo/semantics/closedAccess