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 ∑jwjCj. We show how a recent (2+ϵ)-approximation algorithm of Schulz and Skutella for the problem in which there are in addition release dates can be modified to produce a (3/2+ϵ)-approximation algorithm when there are no release dates.
No takes yet. Share an insight, caveat, or question.
Fabián A. Chudak (1999) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: