An approximate algorithm for a high-multiplicity parallel machine scheduling problem

详细信息    查看全文

• 作者：Carlo Filippi
• 关键词：Scheduling ; Parallel machines ; High multiplicity ; Approximation
• 刊名：Operations Research Letters
• 出版年：2010
• 出版时间：July 2010
• 年：2010
• 卷：38
• 期：4
• 页码：312-317
• 全文大小：382 K

文摘

We consider a high-multiplicity parallel machine scheduling problem where the objective is to minimize the weighted sum of completion times. We suggest an approximate algorithm and we prove that it is asymptotically exact. The algorithm exploits a convex quadratic relaxation of the problem to fix a partial schedule, consisting of most jobs, and then assigns the residual jobs following a simple and general rule. The quality of the obtained solution is evidenced by some numerical tests.