| An Enhanced NEH Method in Solving Permutation Flow Shop Problem |
| |
| 作者姓名： | 高守玮 林晨 张卫东 |
| |
| 作者单位： | Dept.of Automation Shanghai Jiaotong Univ.，Dept. of Space Science，Lulea Univ.of Technology，Dept.of Automation，Shanghai Jiaotong Univ.，Shanghai 200240 China，Lulea 97187 Sweden，Shanghai 200240 China |
| |
| 基金项目： | 上海市青年科技启明星计划 |
| |
| 摘 要： | This paper proposed an enhanced NEH with full insertion moves to solve the permutation flow shop problem.The characteristics of the original NEH are investigated and analyzed,and it is concluded that the given method would be promising to find better solutions,while the cost would be increased.Fast makespan calculating method and eliminating non-promising permutation policy are introduced to reduce the evaluation effort.The former decreases the time complexity from O(n4m) to O(n3m),which is an acceptable cost for medium and small size instances considering the obtained solution quality.The results from computational experience show that the latter also can eliminate a lot of non-promising solutions.
|
| 关 键 词： | 分解协调算法 建设性启发式 鉴定路径 调解方法 |
| 文章编号： | 1007-1172（2007）01-0047-06 |
| 修稿时间： | 2006-07-31 |
An Enhanced NEH Method in Solving Permutation Flow Shop Problem |
| |
| GAO Shou-wei,LIN Chen,ZHANG Wei-dong.An Enhanced NEH Method in Solving Permutation Flow Shop Problem[J].Journal of Shanghai Jiaotong university,2007,12(1):47-52. |
| |
| Authors: | GAO Shou-wei LIN Chen ZHANG Wei-dong |
| |
| Institution: | 1. Dept. of Automation,Shanghai Jiaotong Univ. ,Shanghai 200240, China
2. Dept. of Space Science,Lulea Univ. of Technology, Lulea 97187, Sweden |
| |
| Abstract: | This paper proposed an enhanced NEH with full insertion moves to solve the permutation flow shop problem.The characteristics of the original NEH are investigated and analyzed,and it is concluded that the given method would be promising to find better solutions,while the cost would be increased.Fast makespan calculating method and eliminating non-promising permutation policy are introduced to reduce the evaluation effort.The former decreases the time complexity from O(n4m) to O(n3m),which is an acceptable cost for medium and small size instances considering the obtained solution quality.The results from computational experience show that the latter also can eliminate a lot of non-promising solutions. |
| |
| Keywords: | flow shop constructive heuristic makespan critical path |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
