A comment on scheduling two parallel machines with capacity constraints

AbstractIn a recent paper [Discrete Appl. Math. 130 (2003) 449–467], Yang, Ye, and Zhang investigate the problem of scheduling independent jobs on two identical 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. They provide a semidefinite programming based, polynomial time approximation algorithm with a worst case ratio of 1.1626.In this short technical note, we establish the existence of an FPTAS for this problem, and for the corresponding makespan minimization problem