Approximating the throughput of multiple machines in real-time scheduling

Amotz Bar-Noy, Sudipto Guha, Joseph Naor, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

144 Scopus citations

Abstract

We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to find a nonpreemptive schedule that maximizes the weight of jobs that meet their respective deadlines. We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated) and the weight of the jobs (identical vs. arbitrary). All these variants are known to be NP-hard, and the two variants involving unrelated machines are also MAX-SNP hard. The specific results obtained are as follows: • For identical job weights and unrelated machines: a greedy 2-approximation algorithm. • For identical job weights and k identical machines: the same greedy algorithm achieves a tight (1+1/k)k/(1+1/k)k-1 approximation factor. • For arbitrary job weights and a single machine: an LP formulation achieves a 2-approximation for polynomially bounded integral input and a 3-approximation for arbitrary input. For unrelated machines, the factors are 3 and 4, respectively. • For arbitrary job weights and k identical machines: the LP-based algorithm applied repeatedly achieves a (1+1/k)k/(1+1/k)k-1 approximation factor for polynomially bounded integral input and a (1+1/2k)k/(1+1/2k)k-1 approximation factor for arbitrary input. • For arbitrary job weights and unrelated machines: & combinatorial (3 + 2√2 ≈ 5.828)-approximation algorithm.

Original languageEnglish (US)
Pages (from-to)331-352
Number of pages22
JournalSIAM Journal on Computing
Volume31
Issue number2
DOIs
StatePublished - 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximation algorithms
  • Multiple machines scheduling
  • Parallel machines scheduling
  • Real-time scheduling
  • Scheduling
  • Throughput

Fingerprint

Dive into the research topics of 'Approximating the throughput of multiple machines in real-time scheduling'. Together they form a unique fingerprint.

Cite this