| 工件带准备时间的平行机调度问题的一个近似算法 |
| |
| 引用本文： | 程贞敏,张喜娟,李洪兴.工件带准备时间的平行机调度问题的一个近似算法[J].北京师范大学学报(自然科学版),2009,45(4). |
| |
| 作者姓名： | 程贞敏 张喜娟 李洪兴 |
| |
| 作者单位： | 1. 北京联合大学商务学院,100025,北京
2. 大连理工大学电子与信息工程学院,116024,大连 |
| |
| 基金项目： | 国家自然科学基金资助项目(60474023);;教育部科学技术重点项目(03184) |
| |
| 摘 要： | 提出了一个启发式算法,在该算法中,工件中断的次数至多为2N次,计算的复杂度为O(Nnlogn),并以一个实例加以说明.证明了对某些特殊的实例,该算法能够得到最优调度.指出了对于一般情况该算法的最坏情况误差界为(2(n-1))/n.
|
| 关 键 词： | 平行机调度 中断 准备时间 总完工时间 最坏情况误差界 |
AN APPROXIMATION ALGORITHM FOR PARALLEL MACHINE SCHEDULING PROBLEM |
| |
| CHENG Zhenmin,ZHANG Xijuan,LI Hongxing.AN APPROXIMATION ALGORITHM FOR PARALLEL MACHINE SCHEDULING PROBLEM[J].Journal of Beijing Normal University(Natural Science),2009,45(4). |
| |
| Authors: | CHENG Zhenmin ZHANG Xijuan LI Hongxing |
| |
| Abstract: | 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(Nnlogn),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 perf... |
| |
| Keywords: | identical machine scheduling preemptions release times total completion time worst-case performance bound |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
