文献类型：期刊文献

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

英文题名：AN APPROXIMATION ALGORITHM FOR PARALLEL MACHINE SCHEDULING PROBLEM

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

第一作者：程贞敏

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

第一机构：北京联合大学商务学院

年份：2009

期号：4

起止页码：350-354

中文期刊名：北京师范大学学报：自然科学版

收录：CSTPCD;;北大核心:【北大核心2008】；CSCD:【CSCD2011_2012】；

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

语种：中文

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

外文关键词：identical machine scheduling; preemptions; release times; total completion time; worst-case performance bound

摘要：提出了一个启发式算法,在该算法中,工件中断的次数至多为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.