𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation algorithm for scheduling on three dedicated machines

✍ Scribed by Michel X. Goemans

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
608 KB
Volume
61
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An approximation algorithm for schedulin
An approximation algorithm for scheduling two parallel machines with capacity constraints
✍ Heng Yang; Yinyu Ye; Jiawei Zhang πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 205 KB

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 algori

Approximation schemes for scheduling on
Approximation schemes for scheduling on parallel machines
✍ Noga Alon; Yossi Azar; Gerhard J. Woeginger; Tal Yadid πŸ“‚ Article πŸ“… 1998 πŸ› Springer US 🌐 English βš– 124 KB πŸ‘ 1 views

We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine completion times. As a main result, we identify some conditions on the objective function, under which

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