Authors

Citation

A. Bar-noy et al., Approximating the throughput of multiple machines in real-time scheduling, SIAM J COMP, 31(2), 2001, pp. 331-352

Citations number

33

Language

INGLESE

art.tipo

Article

Categorie Soggetti

Computer Science & Engineering

Journal title

SIAM JOURNAL ON COMPUTING

ISSN journal

0097-5397
â†’ ACNP

Volume

31

Issue

2

Year of publication

2001

Pages

331 - 352

Database

ISI

SICI code

0097-5397(20011011)31:2<331:ATTOMM>2.0.ZU;2-W

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 w
ith a release time, a deadline, a weight, and a processing time on each of
the machines. The goal is to nda nonpreemptive schedule that maximizes the
weight of jobs that meet their respective deadlines. We give constant facto
r approximation algorithms for four variants of the problem, depending on t
he type of the machines ( identical vs. unrelated) and the weight of the jo
bs ( identical vs. arbitrary). All these variants are known to be NP-hard,
and the two variants involving unrelated machines are also MAX-SNP hard. Th
e 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 algorit
hm 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-approxima
tion 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 f
or polynomially bounded integral input and a (1+1/2k)(k)/(1+1/2k)(k)-1 appr
oximation factor for arbitrary input.
For arbitrary job weights and unrelated machines: a combinatorial ( 3+2 roo
t2 approximate to 5.828)- approximation algorithm.