Improvement of constructive heuristics using variable neighbourhood descent for scheduling a flow shop with sequence dependent setup time

• Two better neighbourhood search-based improvement heuristics are developed and analysed.
• Experimentation is carried out on 960 problem instances.
• A paired comparison test is used for validating the superiority of the proposed heuristics.
• The study reveals dependence of VND-based algorithms on the initial constructive algorithms used.
• Guidelines are provided for choosing the appropriate heuristic for a given problem.

This paper deals with the problem of scheduling a flow shop operating in a sequence dependent setup time environment. The objective is to determine the sequence that minimises the makespan. Two efficient neighbourhood search-based heuristics have been developed and tested using 960 problems, and the results obtained reveal their usefulness. The algorithms make use of two existing constructive heuristics. A neighbourhood search known as variable neighbourhood descent is used to improve the two constructive heuristics. Experimentation is carried out on the 96 groups of problems with 10 problem instances in each group. Performance analysis is carried out using the relative performance improvement of each heuristic. The analysis shows a consistently better performance of the neighbourhood-based improvement heuristics. A paired comparison test is used for validating the superiority of the proposed heuristics. The statistical analysis reveals that the performance of the neighbourhood-based heuristics is very much dependent on the initial constructive heuristics used.