Approximation algorithms for minimizing average weighted completion time

Chandra Chekuri, Sanjeev Khanna

Research output: Chapter in Book/Report/Conference proceedingChapter


In this chapter we survey approximation algorithms for scheduling to minimize average (weighted) completion time (equivalently sum of (weighted) completion times). We are given n jobs J1,…, Jn, where each job J j has a positive weight wj. We denote by Cj the completion time of job j in a given schedule. The objective in the problems we consider is to find a schedule to minimize Σj wjCj (average weighted completion time). The most basic problem in this context is to minimizeΣj Cj on a single machine with job j having a processing time pj, and all jobs are available at time 0, in other words, the problem 1 ||Σj Cj. It is easy to see that ordering jobs by the SPT rule (shortest processing time first) gives an optimal schedule. A slight generalization with jobs having weights, 1 ||Σj wjCj, also has a simple optimality rule first stated by Smith [1] (known as Smith’s rule): schedule jobs in nondecreasing order of the ratio pj/wj.

Original languageEnglish (US)
Title of host publicationHandbook of Scheduling
Subtitle of host publicationAlgorithms, Models, and Performance Analysis
PublisherCRC Press
ISBN (Electronic)9780203489802
ISBN (Print)9781584883975
StatePublished - Jan 1 2004
Externally publishedYes

ASJC Scopus subject areas

  • General Engineering
  • General Computer Science
  • General Economics, Econometrics and Finance
  • General Business, Management and Accounting


Dive into the research topics of 'Approximation algorithms for minimizing average weighted completion time'. Together they form a unique fingerprint.

Cite this