| 流水作业问题的一个启发式算法 |
| |
| 引用本文： | 时凌.流水作业问题的一个启发式算法[J].湖北民族学院学报(哲学社会科学版),2001,19(4):48-50. |
| |
| 作者姓名： | 时凌 |
| |
| 作者单位： | 湖北民族学院计算机与数学系 湖北恩施445000 |
| |
| 摘 要： | 讨论具有延迟时间的流水作业问题，并提出了解决该问题的一种启发算法，证明了其最坏性能比是（m 1）/2，并且上界是紧的，特别当m=2，即两台机器上具有延迟时间的流水作业问题时，其最坏性能比是3/2，最后将所得结论推广到FmID2问题，即加工时间相等且延迟时间只取两上值的流水作业问题，其最坏性能比也是m 1/2。
|
| 关 键 词： | 流水作业 启发式算法 最坏性能比 延迟时间 |
| 文章编号： | 1008-8423(2001)04-0048-03 |
| 修稿时间： | 2001年7月24日 |
A heuristic algorithm for two-machine flow-shop problem with delays |
| |
| SHI,Ling.A heuristic algorithm for two-machine flow-shop problem with delays[J].Journal of Hubei Institute for Nationalities(Natural Sciences),2001,19(4):48-50. |
| |
| Authors: | SHI Ling |
| |
| Abstract: | We consider the m-machine flow-shop problem with delays .We present a heuristic algorithmto solve the problem and prove the worst-case performance is m+12,and the bound is tight. Especially, when m = 2 ,the worst-case performance is 3/2.Finally, we extend our result to FmID2 problem ,and prove the worst -case performance ism+12 ,too. |
| |
| Keywords: | heuristic algorithm flow-shop problem the worst-case performance delays |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
