An approximation algorithm for scheduling two parallel machines with capacity constraints.
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.
scientific article; zbMATH DE number 1984624