## 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 J_{1},…, J_{n}, where each job J j has a positive weight w_{j}. We denote by C_{j} 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} w_{j}C_{j} (average weighted completion time). The most basic problem in this context is to minimizeΣ_{j} C_{j} on a single machine with job j having a processing time p_{j}, and all jobs are available at time 0, in other words, the problem 1 ||Σ_{j} C_{j}. 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} w_{j}C_{j}, also has a simple optimality rule first stated by Smith [1] (known as Smith’s rule): schedule jobs in nondecreasing order of the ratio p_{j}/w_{j}.

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