Continuous Speed Scaling with Variability: A Simple and Direct Approach

A. Antoniadis, P. Kling, S. Ott, S. Riechers, Theoretical Computer Science (2017) 1–13.

Download
Restricted 110-TCSSubmission.pdf 494.60 KB
Journal Article | English
Author
; ; ;
Abstract
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.
Publishing Year
Journal Title
Theoretical Computer Science
Page
1-13
LibreCat-ID

Cite this

Antoniadis A, Kling P, Ott S, Riechers S. Continuous Speed Scaling with Variability: A Simple and Direct Approach. Theoretical Computer Science. 2017:1-13. doi:10.1016/j.tcs.2017.03.021
Antoniadis, A., Kling, P., Ott, S., & Riechers, S. (2017). Continuous Speed Scaling with Variability: A Simple and Direct Approach. Theoretical Computer Science, 1–13. https://doi.org/10.1016/j.tcs.2017.03.021
@article{Antoniadis_Kling_Ott_Riechers_2017, title={Continuous Speed Scaling with Variability: A Simple and Direct Approach}, DOI={10.1016/j.tcs.2017.03.021}, journal={Theoretical Computer Science}, publisher={Elsevier}, author={Antoniadis, Antonios and Kling, Peter and Ott, Sebastian and Riechers, Sören}, year={2017}, pages={1–13} }
Antoniadis, Antonios, Peter Kling, Sebastian Ott, and Sören Riechers. “Continuous Speed Scaling with Variability: A Simple and Direct Approach.” Theoretical Computer Science, 2017, 1–13. https://doi.org/10.1016/j.tcs.2017.03.021.
A. Antoniadis, P. Kling, S. Ott, and S. Riechers, “Continuous Speed Scaling with Variability: A Simple and Direct Approach,” Theoretical Computer Science, pp. 1–13, 2017.
Antoniadis, Antonios, et al. “Continuous Speed Scaling with Variability: A Simple and Direct Approach.” Theoretical Computer Science, Elsevier, 2017, pp. 1–13, doi:10.1016/j.tcs.2017.03.021.
Main File(s)
File Name
110-TCSSubmission.pdf 494.60 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T13:07:43Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar