Throughput maximization for speed scaling with agreeable deadlines

Eric Angel (), Evripidis Bampis (), Vincent Chau () and Dimitrios Letsios ()
Additional contact information
Eric Angel: Université d’Evry Val d’Essonne
Evripidis Bampis: LIP6, Université Pierre et Marie Curie
Vincent Chau: City University of Hong Kong
Dimitrios Letsios: Technische Universität München

Journal of Scheduling, 2016, vol. 19, issue 6, No 2, 619-625

Abstract: Abstract We study the following energy-efficient scheduling problem. We are given a set of n jobs which have to be scheduled by a single processor whose speed can be varied dynamically. Each job $$J_j$$ J j is characterized by a processing requirement (work) $$p_j$$ p j , a release date $$r_j$$ r j , and a deadline $$d_j$$ d j . We are also given a budget of energy E which must not be exceeded and our objective is to maximize the throughput (i.e., the number of jobs which are completed on time). We show that the problem can be solved optimally via dynamic programming in $$O(n^4 \log n \log P)$$ O ( n 4 log n log P ) time when all jobs have the same release date, where P is the sum of the processing requirements of the jobs. For the more general case with agreeable deadlines where the jobs can be ordered so that, for every $$i

Keywords: Throughput; Speed scaling; Scheduling (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-015-0452-y 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:jsched:v:19:y:2016:i:6:d:10.1007_s10951-015-0452-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-015-0452-y

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

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