Authors

Citation

C. Chekuri et al., Approximation techniques for average completion time scheduling, SIAM J COMP, 31(1), 2001, pp. 146-166

Citations number

35

Language

INGLESE

art.tipo

Article

Categorie Soggetti

Computer Science & Engineering

Journal title

SIAM JOURNAL ON COMPUTING

ISSN journal

0097-5397
â†’ ACNP

Volume

31

Issue

1

Year of publication

2001

Pages

146 - 166

Database

ISI

SICI code

0097-5397(20010729)31:1<146:ATFACT>2.0.ZU;2-R

Abstract

We consider the problem of nonpreemptive scheduling to minimize average ( w
eighted) completion time, allowing for release dates, parallel machines, an
d precedence constraints. Recent work has led to constant-factor approximat
ions for this problem based on solving a preemptive or linear programming r
elaxation and then using the solution to get an ordering on the jobs. We in
troduce several new techniques which generalize this basic paradigm. We use
these ideas to obtain improved approximation algorithms for one-machine sc
heduling to minimize average completion time with release dates. In the pro
cess, we obtain an optimal randomized on-line algorithm for the same proble
m that beats a lower bound for deterministic on-line algorithms. We conside
r extensions to the case of parallel machine scheduling, and for this we in
troduce two new ideas: rst, we show that a preemptive one-machine relaxatio
n is a powerful tool for designing parallel machine scheduling algorithms t
hat simultaneously produce good approximations and have small running times
; second, we show that a nongreedy rounding of the relaxation yields better
approximations than a greedy one. We also prove a general theorem relating
the value of one-machine relaxations to that of the schedules obtained for
the original m-machine problems. This theorem applies even when there are
precedence constraints on the jobs. We apply this result to obtain improved
approximation ratios for precedence graphs such as in-trees, out-trees, an
d series-parallel graphs.