Real-time scheduling to minimize machine busy times

Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Consider the following scheduling problem. We are given a set of jobs, each having a release time, a due date, a processing time, and demand for machine capacity. The goal is to schedule all jobs non-preemptively in their release-time deadline windows on machines that can process multiple jobs simultaneously, subject to machine capacity constraints, with the objective to minimize the total busy time of the machines. Our problem naturally arises in power-aware scheduling, optical network design, and customer service systems, among others. The problem is APX-hard by a simple reduction from the subset sum problem. A main result of this paper is a 5-approximation algorithm for general instances. While the algorithm is simple, its analysis involves a non-trivial charging scheme which bounds the total busy time in terms of work and span lower bounds on the optimum. This improves and extends the results of Flammini et al. (Theor Comput Sci 411(40–42):3553–3562, 2010). We extend this approximation to the case of moldable jobs, where the algorithm also needs to choose, for each job, one of several processing-time versus 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.

Original languageEnglish (US)
Pages (from-to)561-573
Number of pages13
JournalJournal of Scheduling
Volume18
Issue number6
DOIs
StatePublished - Dec 1 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Engineering(all)
  • Management Science and Operations Research
  • Artificial Intelligence

Keywords

  • Approximation algorithms
  • Minimum total busy time
  • Power-aware
  • Real-time scheduling

Fingerprint

Dive into the research topics of 'Real-time scheduling to minimize machine busy times'. Together they form a unique fingerprint.

Cite this