License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.169
URN: urn:nbn:de:0030-drops-28909
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2890/
Go to the corresponding LIPIcs Volume Portal

Khandekar, Rohit ; Schieber, Baruch ; Shachnai, Hadas ; Tamir, Tami

Minimizing Busy Time in Multiple Machine Real-time Scheduling

pdf-format:
44.pdf (0.5 MB)

Abstract

We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem has important applications in power-aware scheduling, optical network design and unit commitment in power systems. Scheduling to minimize busy times is APX-hard already in the special case where all jobs have the same (unit) processing times and can be scheduled in a fixed time interval.

Our main result is a $5$-approximation algorithm for general instances. We extend this result to obtain an algorithm with the same approximation ratio for the problem of scheduling moldable jobs, that requires also to determine, for each job, one of several processing-time vs. demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.

BibTeX - Entry

@InProceedings{khandekar_et_al:LIPIcs:2010:2890,
  author =	{Rohit Khandekar and Baruch Schieber and Hadas Shachnai and Tami Tamir},
  title =	{{Minimizing Busy Time in Multiple Machine Real-time Scheduling}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{169--180},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2890},
  URN =		{urn:nbn:de:0030-drops-28909},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.169},
  annote =	{Keywords: real-time scheduling, busy time, preemption, approximation algorithm}
}

Keywords: real-time scheduling, busy time, preemption, approximation algorithm
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI