Throughput maximization for speed scaling with agreeable deadlines

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

2 Scopus Citations
View graph of relations

Author(s)

  • Eric Angel
  • Evripidis Bampis
  • Vincent Chau
  • Dimitrios Letsios

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)619-625
Journal / PublicationJournal of Scheduling
Volume19
Issue number6
Publication statusPublished - 1 Dec 2016

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 Jj is characterized by a processing requirement (work) pj, a release date rj, and a deadline dj. 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(n4log nlog 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<j, it holds that ri≤ rj and di≤ dj, we propose an optimal dynamic programming algorithm which runs in O(n6log nlog P) time. In addition, we consider the weighted case where every job Jj is also associated with a weight wj and we are interested in maximizing the weighted throughput (i.e., the total weight of the jobs which are completed on time). For this case, we show that the problem becomes NP-hard in the ordinary sense even when all jobs have the same release date and we propose a pseudo-polynomial time algorithm for agreeable instances.

Research Area(s)

  • Scheduling, Speed scaling, Throughput

Citation Format(s)

Throughput maximization for speed scaling with agreeable deadlines. / Angel, Eric; Bampis, Evripidis; Chau, Vincent; Letsios, Dimitrios.

In: Journal of Scheduling, Vol. 19, No. 6, 01.12.2016, p. 619-625.

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