Approximation algorithms for minimizing average weighted completion time

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₁,…, 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_jC_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_jC_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.