| 最小化时间表长的平行机调度近似算法研究 |
| |
| 引用本文： | 程贞敏,李洪兴,谷敏强.最小化时间表长的平行机调度近似算法研究[J].北京师范大学学报(自然科学版),2012,48(1):11-15. |
| |
| 作者姓名： | 程贞敏 李洪兴 谷敏强 |
| |
| 作者单位： | 北京联合大学商务学院,北京,100025;大连理工大学电子与信息工程学院,辽宁大连,116024;汕头大学理学院数学系,广东汕头,515063 |
| |
| 基金项目： | 北京市教委科技面上资助项目，北京联合大学科研基金资助项目 |
| |
| 摘 要： | 讨论机器具有固定周期维护t,目标函数为最小化时间表长的m台平行机调度问题.这是一个NP-难的问题.关于该问题主要分析了当维护时间t≤T/3时,利用经典的装箱算法FFD我们可以得到关于该问题的一个近似算法FFPTD.该算法的最坏误差界为2,最后以实例说明2为该算法的紧界.
|
| 关 键 词： | 平行机调度 周期维护 时间表长 近似算法 最坏误差界 |
APPROXIMATED ALGORITHM FOR IDENTICAL MACHINE SCHEDULING WITH MINIMIZED MAKESPANS |
| |
| CHENG Zhenmin,LI Hongxing,GU Minqiang.APPROXIMATED ALGORITHM FOR IDENTICAL MACHINE SCHEDULING WITH MINIMIZED MAKESPANS[J].Journal of Beijing Normal University(Natural Science),2012,48(1):11-15. |
| |
| Authors: | CHENG Zhenmin LI Hongxing GU Minqiang |
| |
| Institution: | 1)Business College of Beijing Union University,100025,Beijing,China; 2)School of Electronic and Information Engineering,Dalian University of Technology,116024,Dalian,Liaoning,China; 3)Department of Mathematics,College of science,Shantou University,515063,Shantou,Guangdong,China) |
| |
| Abstract: | Identical machine scheduling with periodic maintenance was considered.The objective was to minimize make-spans.It was a NP-hard problem.An approximated algorithm was proposed to solve this problem with the bins packing algorithm FFD.For the case t≤T/3,the worst-case bound was 2.An example was given to illustrate that 2 was a tight bound. |
| |
| Keywords: | identical machine scheduling periodical maintenance makespans approximative algorithm worst-case bound |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
