New heuristics for no-wait flowshops to minimize makespan

摘要

This paper addresses the m-machine no-wait flowshop scheduling problem to minimize makespan. We propose two heuristics that are based on simulated annealing and Genetic Algorithm techniques. We also propose improvement procedures to these heuristics. Extensive computational experiments show that the simulated annealing heuristic outperforms the best two existing heuristics. They also show that the improvement procedures, applied to the Simulated Annealing and Genetic Algorithm, result in significant reduction in error, about 750% error reduction to Simulated Annealing and about 1960% to Genetic Algorithm.