考虑作业释放时间和机器数量变化的同型机调度问题  

Identical parallel machine scheduling problem with release dates and the change of the number of machines

作　　者：赵福强 刘桂庆[1] 

机构地区：[1]合肥工业大学数学学院,安徽合肥230009

出　　处：《合肥工业大学学报（自然科学版）》2017年第9期1283-1288,共6页Journal of Hefei University of Technology：Natural Science

基　　金：教育部高等学校博士学科点专项科研基金资助项目(20120111120013)

摘　　要：文章研究了机器数量变化对最大完工时间影响的同型机调度问题,其作业带有释放时间。基于改进的McNaughton规则,提出了一种多项式时间算法,进而证明了该算法能求得问题的最优解和最优机器数目m~*,同时给出了机器影响的上下界。最后,结合算例及其计算结果,并通过实验验证了该算法的有效性。The identical parallel machine scheduling problem considering the influence that additional machines may have on the makespan with unequal release dates is researched. Firstly, based on the modified McNaughton rule, a polynomial time algorithm is proposed and then it is proved that the algorithm can obtain the optimal solution and the optimal number of machines m^＊, Moreover, the up- per and lower bounds of the machine impact are given, Finally, an example and the computation results are given, and the validity of the algorithm is also verified by experiment.

关 键 词：同型机调度 机器影响 释放时间 可中断 最大完工时间 

分 类 号：O223[理学—运筹学与控制论]