|
|||||
|
|
An approximation algorithm for scheduling two parallel machines with capacity constraints |
|
| Authors: | Heng Yang Yinyu Ye Jiawei Zhang |
| Institution: | a State Key Laboratory of Intelligent Technology and System, Department of Automation, Tsinghua University, Beijing 100084, People's Republic of China b Department of Management Science and Engineering, School of Engineering, Stanford University, Stanford, CA 94305-4206, USA c Department of Management Science and Engineering, School of Engineering, Stanford University, Stanford, CA 94305, USA |
| Abstract: | 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 each single machine, so as to minimize the total weighted completion time of the jobs. We study a semidefinite programming-based approximation algorithm for solving this problem and prove that the algorithm has a worst case ratio at most 1.1626. |
| Keywords: | Parallel machine scheduling Max-Cut problem Semidefinite programming Approximation algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |