✦ LIBER ✦
A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
✍ Scribed by Fabián A. Chudak
- Publisher
- Springer US
- Year
- 1999
- Tongue
- English
- Weight
- 70 KB
- Volume
- 2
- Category
- Article
- ISSN
- 1094-6136
No coin nor oath required. For personal study only.
✦ Synopsis
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 p GH units of time if processed on machine i and has a weight w H . If C H is the completion time of job j, the objective is to minimize H w H C H . 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.