| m台机器上流水作业时间表问题的复杂性及一种新的启发式算法 |
| |
| 引用本文： | 时凌.m台机器上流水作业时间表问题的复杂性及一种新的启发式算法[J].西南民族学院学报(自然科学版),2003,29(3):258-263. |
| |
| 作者姓名： | 时凌 |
| |
| 作者单位： | 湖北民族学院理学院 湖北恩施 |
| |
| 基金项目： | Supported by the Educational Department of Hubei Province No.2002x13. |
| |
| 摘 要： | 研究流水作业时间表问题，在具有延迟时间的条件下证明该问题是强NP-困难的．给出一种新的启发式算法，并证明该算法的最坏性能比是(m 1)/2，且上界是紧的．
|
| 关 键 词： | 流水作业时间表 复杂性 延迟时间 准备时间 3－划分 NP－困难 算法 |
| 文章编号： | 1003-2843(2003)03-0258-06 |
| 修稿时间： | 2003年3月10日 |
Complexity and simple heuristic for m-machine flow shop problem with delays and release times |
| |
| SHI Ling.Complexity and simple heuristic for m-machine flow shop problem with delays and release times[J].Journal of Southwest Nationalities College(Natural Science Edition),2003,29(3):258-263. |
| |
| Authors: | SHI Ling |
| |
| Abstract: | Considering m-machine flow-shop problem with delays and release times, we use 3-Partition to prove that the F2RD problem is NP-hard in the strong sense, and then we introduce a simple heuristic and prove that the worst-case performance is (m+1)/2. At last, we give an example to show the bound is tight. Specially, when m =2, the worst-case performance is 3/2, the bound is tight, too. |
| |
| Keywords: | flow-shop problem delays release times 3-Partition NP-hard |
| 本文献已被 CNKI 维普 等数据库收录！ |
