Profitable Scheduling on Multiple Speed-Scalable Processors

P. Kling, P. Pietrzyk, in: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013, pp. 251–260.

Download
Restricted 499-P._Kling__P._Pietryzk_-_Profitable_Scheduling_on_Multiple_Speed-scalable_Processors__2013_.pdf 558.66 KB
Conference Paper | English
Author
Kling, Peter; Pietrzyk, Peter
Abstract
We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors.Moreover, we provide a tight analysis of the algorithm's competitiveness.Our results generalize and improve upon work by \citet{Chan:2010}, which considers a single speed-scalable processor.Using significantly different techniques, we can not only extend their model to multiprocessors but also prove an enhanced and tight competitive ratio for our algorithm.In our scheduling problem, jobs arrive over time and are preemptable.They have different workloads, values, and deadlines.The scheduler may decide not to finish a job but instead to suffer a loss equaling the job's value.However, to process a job's workload until its deadline the scheduler must invest a certain amount of energy.The cost of a schedule is the sum of lost values and invested energy.In order to finish a job the scheduler has to determine which processors to use and set their speeds accordingly.A processor's energy consumption is power $\Power{s}$ integrated over time, where $\Power{s}=s^{\alpha}$ is the power consumption when running at speed $s$.Since we consider the online variant of the problem, the scheduler has no knowledge about future jobs.This problem was introduced by~\citet{Chan:2010} for the case of a single processor.They presented an online algorithm which is $\alpha^{\alpha}+2e\alpha$-competitive.We provide an online algorithm for the case of multiple processors with an improved competitive ratio of $\alpha^{\alpha}$.
Publishing Year
Proceedings Title
Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)
Page
251-260
LibreCat-ID
499

Cite this

Kling P, Pietrzyk P. Profitable Scheduling on Multiple Speed-Scalable Processors. In: Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ; 2013:251-260. doi:10.1145/2486159.2486183
Kling, P., & Pietrzyk, P. (2013). Profitable Scheduling on Multiple Speed-Scalable Processors. In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (pp. 251–260). https://doi.org/10.1145/2486159.2486183
@inproceedings{Kling_Pietrzyk_2013, title={Profitable Scheduling on Multiple Speed-Scalable Processors}, DOI={10.1145/2486159.2486183}, booktitle={Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Kling, Peter and Pietrzyk, Peter}, year={2013}, pages={251–260} }
Kling, Peter, and Peter Pietrzyk. “Profitable Scheduling on Multiple Speed-Scalable Processors.” In Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 251–60, 2013. https://doi.org/10.1145/2486159.2486183.
P. Kling and P. Pietrzyk, “Profitable Scheduling on Multiple Speed-Scalable Processors,” in Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013, pp. 251–260.
Kling, Peter, and Peter Pietrzyk. “Profitable Scheduling on Multiple Speed-Scalable Processors.” Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013, pp. 251–60, doi:10.1145/2486159.2486183.
Main File(s)
File Name
499-P._Kling__P._Pietryzk_-_Profitable_Scheduling_on_Multiple_Speed-scalable_Processors__2013_.pdf 558.66 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-15T13:40:02Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar