Speed scaling on parallel processors with migration

Eric Angel, Evripidis Bampis, Fadi Kacem, Dimitrios Letsios*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)
85 Downloads (Pure)

Abstract

We study the problem of scheduling a set of jobs with release dates, deadlines and processing requirements (or works) on parallel speed scalable processors so as to minimize the total energy consumption. We consider that both preemptions and migrations of jobs are allowed. For this problem, there exists an optimal polynomial-time algorithm which uses as a black box an algorithm for linear programming. Here, we formulate the problem as a convex program and we propose a combinatorial polynomial-time algorithm which is based on finding maximum flows. Our algorithm runs in O(nf(n) log U) time, where n is the number of jobs, U is the range of all possible values of processors’ speeds divided by the desired accuracy and f(n) is the time needed for computing a maximum flow in a layered graph with O(n) vertices.

Original languageEnglish
Pages (from-to)1266-1282
Number of pages17
JournalJOURNAL OF COMBINATORIAL OPTIMIZATION
Volume37
Issue number4
Early online date12 Oct 2018
DOIs
Publication statusPublished - 1 May 2019

Keywords

  • Convex programming
  • Energy efficient scheduling
  • Network flows
  • Speed scaling

Fingerprint

Dive into the research topics of 'Speed scaling on parallel processors with migration'. Together they form a unique fingerprint.

Cite this