An Approximation Algorithm for the Two-Parallel
Machines Scheduling Problem with Capacity Constraints
Yang, Ye and Zhang
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 a single
machine, so as to minimize the total weighted
completion time of the jobs. We study a semidefinite
programming (SDP) based approximation algorithm
for solving this problem and prove that the algorithm
has a worst case ratio at most $1.1626$.
Working Paper, Department of Management Sciences,
University of Iowa, IA 52242, USA
Contact: [email protected]
![[DVI]](../gif/DVI.gif)
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)