Throughput maximization in multiprocessor speed-scaling

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

3 Scopus Citations
View graph of relations

Author(s)

  • Eric Angel
  • Evripidis Bampis
  • Vincent Chau
  • Nguyen Kim Thang

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)1-12
Journal / PublicationTheoretical Computer Science
Volume630
Publication statusPublished - 30 May 2016

Abstract

In the classical energy minimization problem, introduced in [24], we are given a set of n jobs each one characterized by its release date, its deadline, its processing volume and we aim to find a feasible schedule of the jobs on a single speed-scalable machine so that the total energy consumption is minimized. Here, we study the throughput maximization version of the problem where we are given a budget of energy E and where every job has also a value. Our goal is to determine a feasible schedule maximizing the (weighted) throughput of the jobs that are executed between their respective release dates and deadlines. We first consider the preemptive non-migratory multiprocessor case in a fully heterogeneous environment in which every job has a machine-dependent release date, deadline and processing volume and every machine obeys to a different speed-to-power function. We present a polynomial time greedy algorithm based on the primal-dual scheme that approximates the optimum solution within a factor depending on the energy functions (the factor is constant for typical energy functions of form P(z)=zα). Then, we focus on the non-preemptive case for which we consider a fixed number of identical parallel machines and two important families of instances: (1) equal processing volume jobs; and (2) agreeable jobs. For both cases we present optimal pseudo-polynomial-time algorithms.

Research Area(s)

  • Approximation, Energy efficient, Scheduling, Throughput maximization

Citation Format(s)

Throughput maximization in multiprocessor speed-scaling. / Angel, Eric; Bampis, Evripidis; Chau, Vincent et al.
In: Theoretical Computer Science, Vol. 630, 30.05.2016, p. 1-12.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review