Approximation techniques for average completion time scheduling

C. Chekuri, R. Motwani, B. Natarajan, C. Stein

Research output: Contribution to conferencePaperpeer-review


The problem of nonpreemptive scheduling to minimize average (weighted) completion time, allowing for release dates, parallel machines, and precedence constraints is considered. New techniques are introduced which generalize recent approaches based on linear programming relaxation. An optimal randomized online algorithm is obtained for the same problem which beats a lower bound for deterministic online algorithms. The problem is extended to the case of parallel machine scheduling. In this case, the efficiencies of preemptive one-machine relaxation and non-greedy `rounding' of the relaxation are demonstrated. A general theorem relating the value of one-machine relaxations to the value of schedules obtained for n-machine problems is proven.

Original languageEnglish (US)
Number of pages10
StatePublished - 1997
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997


OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Approximation techniques for average completion time scheduling'. Together they form a unique fingerprint.

Cite this