Abstract
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 language | English (US) |
---|---|
Title of host publication | Handbook of Scheduling |
Subtitle of host publication | Algorithms, Models, and Performance Analysis |
Publisher | CRC Press |
Pages | 11-1-11-30 |
ISBN (Electronic) | 9780203489802 |
ISBN (Print) | 9781584883975 |
State | Published - Jan 1 2004 |
Externally published | Yes |
ASJC Scopus subject areas
- General Engineering
- General Computer Science
- General Economics, Econometrics and Finance
- General Business, Management and Accounting