A high quality solution constructive heuristic for flow shop sequencing

This paper addresses the flow shop sequencing problem. Following an investigation of the problem characteristics, a property of this scheduling problem is presented, and is used for the development of a new constructive heuristic with the objective of minimizing the total time to complete the schedule (makespan). The new method, denoted by N&M, is compared with the best constructive heuristic reported in the literature, named NEH. Results from computational experience have shown that for problems having up to 10 machines and 100 jobs, the new heuristic outperforms, on average, the NEH heuristic. There is no significant difference regarding computation effort for both NEH and N&M heuristics.