Approximating the throughput of multiple machines in real-time scheduling

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.