工件带准备时间的平行机调度问题的一个近似算法  

AN APPROXIMATION ALGORITHM FOR PARALLEL MACHINE SCHEDULING PROBLEM

作　　者：程贞敏[1] 张喜娟[1] 李洪兴[2] 

机构地区：[1]北京联合大学商务学院,北京100025 [2]大连理工大学电子与信息工程学院,大连116024

出　　处：《北京师范大学学报（自然科学版）》2009年第4期350-354,共5页Journal of Beijing Normal University(Natural Science)

基　　金：国家自然科学基金资助项目(60474023);教育部科学技术重点项目(03184)

摘　　要：提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.The two parallel machine scheduling problem with preemption and release time is considered. The objective is to minimize total completion time. This is a NP-hard problem. A heuristic algorithm MSPT is proposed to solve the problem. In this algorithm, the time of preemption is at most 2N, the problem can be solved in time O（Nnlog n）, an example is given to illustrate the algorithm. It is proved that the algorithm can produce an optimal scheduling algorithm for special cases. For general cases, the worst-case performance bound is 2（n-1）/n.

关 键 词：平行机调度 中断 准备时间 总完工时间 最坏情况误差界 

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