Approximation techniques for average completion time scheduling

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.