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