𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation algorithm for scheduling two parallel machines with capacity constraints

✍ Scribed by Heng Yang; Yinyu Ye; Jiawei Zhang

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
205 KB
Volume
130
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of scheduling n independent jobs on two identical parallel machines, with a limit on the number of jobs that can be assigned to each single machine, so as to minimize the total weighted completion time of the jobs. We study a semideΓΏnite programming-based approximation algorithm for solving this problem and prove that the algorithm has a worst case ratio at most 1.1626.

πŸ“œ 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