𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An optimal rounding gives a better approximation for scheduling unrelated machines

✍ Scribed by Evgeny V. Shchepin; Nodari Vakhania

Book ID
103877652
Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
218 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

A polynomial-time algorithm is suggested for non-preemptive scheduling of n-independent jobs on m-unrelated machines to minimize the makespan. The algorithm has a worst-case performance ratio of 2 -1=m. This is better than the earlier known best performance bound 2. Our approach gives the best possible approximation ratio that can be achieved using the rounding approach.

πŸ“œ SIMILAR VOLUMES

A min-sum 3/2-approximation algorithm fo
A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
✍ FabiΓ‘n A. Chudak πŸ“‚ Article πŸ“… 1999 πŸ› Springer US 🌐 English βš– 70 KB πŸ‘ 1 views

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