Multiprocessor speed scaling for jobs with arbitrary sizes and deadlines

Paul C. Bell () and Prudence W. H. Wong ()
Additional contact information
Paul C. Bell: Loughborough University
Prudence W. H. Wong: University of Liverpool

Journal of Combinatorial Optimization, 2015, vol. 29, issue 4, No 5, 739-749

Abstract: Abstract In this paper we study energy efficient deadline scheduling on multiprocessors in which the processors consumes power at a rate of $$s^\alpha $$ s α when running at speed $$s$$ s , where $$\alpha \ge 2$$ α ≥ 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 ^\alpha P)$$ O ( log α P ) -competitive, where $$P$$ P is the ratio of the maximum and minimum job size.

Keywords: Online algorithms; Dynamic speed scaling; Competitive analysis; Multiprocessor scheduling; Deadline scheduling (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9618-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:29:y:2015:i:4:d:10.1007_s10878-013-9618-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9618-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().