An approximation algorithm for scheduling two parallel machines with capacity constraints. (Q1408454)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An approximation algorithm for scheduling two parallel machines with capacity constraints. |
scientific article |
Statements
An approximation algorithm for scheduling two parallel machines with capacity constraints. (English)
0 references
22 September 2003
0 references
In the paper an approximation algorithm for the parallel machine problem \(P2| q| \sum{w_jC_j}\) is proposed. Jobs have to be processed on two identical parallel machines with limited capacity such that the weighted sum of completion times is minimized. After formulating the problem as a maximum cut problem with capacity constraints it is solved with semidefinite programming. It is proved that the approximation algorithm has a worst-case ratio of 1.1626.
0 references
scheduling
0 references
parallel machines
0 references
maximum cut
0 references
approximation algorithm
0 references
semidefinite programming
0 references
0 references
0 references
