An improved version of the NEH algorithm and its application to large-scale flow-shop scheduling problems.

This paper deals with the Flow-shop Scheduling Problem (FSP). The NEH algorithm is regarded as one of the best constructive methods for solving the FSP. However, the running time of the NEH algorithm when used to solve large-scale FSPs is fairly long. The block properties of the FSP are investigated to reduce the running time. Using these block properties it is found that if a partial schedule is evaluated, the lower bounds of other partial makespans can be obtained in a time of O(1). A pruning procedure based on the block properties of the FSP is introduced into the NEH algorithm to reduce the computational complexity. Experimental results show that the improved NEH algorithm has a greatly reduced running time compared with the classical NEH algorithm. It takes less than 0.2 seconds on average to get a solution for a large-scale FSP (up to 500 jobs and 20 machines). [ABSTRACT FROM AUTHOR]