Models and algorithms for energy-efficient scheduling with immediate start of jobs

Akiyoshi Shioura (), Natalia V. Shakhlevich (), Vitaly A. Strusevich () and Bernhard Primas ()
Additional contact information
Akiyoshi Shioura: School of Engineering, Tokyo Institute of Technology
Natalia V. Shakhlevich: School of Computing, University of Leeds
Vitaly A. Strusevich: University of Greenwich, Old Royal Naval College
Bernhard Primas: School of Computing, University of Leeds

Journal of Scheduling, 2018, vol. 21, issue 5, No 3, 505-516

Abstract: Abstract We study a scheduling model with speed scaling for machines and the immediate start requirement for jobs. Speed scaling improves the system performance, but incurs the energy cost. The immediate start condition implies that each job should be started exactly at its release time. Such a condition is typical for modern Cloud computing systems with abundant resources. We consider two cost functions, one that represents the quality of service and the other that corresponds to the cost of running. We demonstrate that the basic scheduling model to minimize the aggregated cost function with n jobs is solvable in $$O(n\log n)$$ O ( n log n ) time in the single-machine case and in $$O(n^{2}m)$$ O ( n 2 m ) time in the case of m parallel machines. We also address additional features, e.g., the cost of job rejection or the cost of initiating a machine. In the case of a single machine, we present algorithms for minimizing one of the cost functions subject to an upper bound on the value of the other, as well as for finding a Pareto-optimal solution.

Keywords: Speed scaling; Energy minimization; Immediate start; Bicriteria optimization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0552-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:21:y:2018:i:5:d:10.1007_s10951-017-0552-y

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

DOI: 10.1007/s10951-017-0552-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 ().