Approximation techniques for average completion time scheduling

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

Research output: Contribution to conferencePaper

Abstract

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)
Pages609-618
Number of pages10
StatePublished - Jan 1 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

Other

OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

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

  • Cite this

    Chekuri, C. S., Motwani, R., Natarajan, B., & Stein, C. (1997). Approximation techniques for average completion time scheduling. 609-618. Paper presented at Proceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA, .