A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines

We consider the problem of minimizing the sum of weighted completion times of jobs scheduled on unrelated parallel machines. That is, there are n jobs and m machines; job j takes pij units of time if processed on machine i and has a weight wj. If Cj is the completion time of job j, the objective is to minimize &Sgr;j wj Cj. We show how a recent (2 + ϵ)-approximation algorithm of Schulz and Skutella for the problem in which there are addition release dates can be modified to produce a (3/2 + ϵ)-approximation algorithm when there are no release dates.