bell_wong2.pdf (297.19 kB)
0/0

Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines

Download (297.19 kB)
journal contribution
posted on 18.09.2015 by Paul Bell, Prudence W.H. Wong
In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate of sα when running at speeds, where α ≥ 2. The problem is to dispatch jobs to processors and determine the speed and jobs to run for each processor so as to complete all jobs by their deadlines using the minimum energy. The problem has been well studied for the single processor case. For the multiprocessor setting, constant competitive online algorithms for special cases of unit size jobs or arbitrary size jobs with agreeable deadlines have been proposed by Albers et al. (2007). A randomized algorithm has been proposed for jobs of arbitrary sizes and arbitrary deadlines by Greiner et al. (2009). We propose a deterministic online algorithm for the general setting and show that it is O(logαP)-competitive, where P is the ratio of the maximum and minimum job size.

Funding

This work is partially supported by EPSRC Grant EP/E028276/1.

History

School

  • Science

Department

  • Computer Science

Published in

Journal of Combinatorial Optimization

Volume

29

Issue

4

Pages

739 - 749

Citation

BELL, P.C. and WONG, P.W.H., 2015. Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines. Journal of Combinatorial Optimization, 29 (4), pp. 739 - 749

Publisher

© Springer

Version

AM (Accepted Manuscript)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2015

Notes

This article was published in the journal, Journal of Combinatorial Optimization [© Springer]. The definitive version is available at: http://dx.doi.org/10.1007/s10878-013-9618-8. A preliminary version appeared in Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation, 2011, pp. 27–36.

ISSN

1382-6905

eISSN

1573-2886

Language

en

Exports