Evaluating the performance for makespan minimisation in no-wait flowshop sequencing

This paper deals with scheduling jobs in an m-machine no-wait with the objective of minimising the maximum completion time of the jobs. The problem is known to be NP-hard for more than two machines, so we focus on obtaining good (although not necessarily optimal) solutions in a short time interval. To do so, we propose a new heuristic based on an analogy between the problem under consideration and the well-known travelling salesman problem (TSP). The proposal is compared with other improvement strategies reported in the literature. Results from computational experience show that, for problems up to five machines and 80 jobs, the new heuristic outperforms, on average, existing methods. Regarding the computational effort, there are no significant differences between the suggested heuristic and the other heuristics under comparison.