An Enhanced NEH Method in Solving Permutation Flow Shop Problem  

作　　者：高守玮 林晨 张卫东 

机构地区：[1]Dept.of Automation,Shanghai Jiaotong Univ. [2]Dept. of Space Science,Lulea Univ.of Technology

出　　处：《Journal of Shanghai Jiaotong university(Science)》2007年第1期47-52,共6页上海交通大学学报（英文版）

基　　金：New Century Excellent Talents in University (No.NCET04-0383);Science and Technology Phosphor Program of Shanghai (No.04QMH1405)

摘　　要：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.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.

关 键 词：flow shop constructive heuristic MAKESPAN critical path 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置] TH186[自动化与计算机技术—控制科学与工程]