Minimizing Total Weighted Completion Time on Uniform Machines with Unbounded Batch

摘要：

In this paper,we consider the scheduling problem of minimizing total weighted com pletion time on uniform machines with unbounded batch.Each of the machine Ml (l=1.……,m) has a speed sl and can process up to B (≥n) jobs simultaneously as a batch. The processing time of a batch denoted by P(B) is given by the processing time of the longest job in it,and the running time of the batch on machine Ml is P(B)/sl.We present some useful properties of the optimal schedule,and then design an O(nm+2) time backward dynamic programming algorithm for the problem.

关键词： Uniform machines with unbounded batch batch-SPT dynamic programming algorithm polynomially solvable

作者: Cuixia Miao Yu-Zhong Zhang Jianfeng Ren

作者单位: Institute of Operations Research,Qufu Normal University,Rizhao,Shandong,276826,China School of Mathe Institute of Operations Research,Qufu Normal University,Rizhao,Shandong,276826,China

会议类型: 国际会议

会议名称: The 8th International Symposium on Operations Research and Its Applications(第八届运筹及其应用国际专题讨论会 ISORA09)

会议地点: 张家界

会议语种:英文

页码: 402-408

在线出版日期: 2009-09-20（万方平台首次上网日期，不代表论文的发表时间）