General variable neighborhood search algorithm to minimize makespan of the distributed no-wait flow shop scheduling problem

This paper addresses minimizing makespan of the distributed no-wait flow shop scheduling problem where there are several identical factories that work in parallel. There are jobs with series of operations that should be allocated to one of these factories and all operations of jobs should be performed in the allocated factories. After starting the first operation of the job, all other operations of the job should be processed without any interruption or delay. The goal is finding allocation and sequence of jobs on each factory such that the completion time of the last job processed in the system is minimized. For the addressed problem, several heuristics available in the literature developed to solve the classical no-wait flowshop scheduling problem have been extended to the addressed problem. Due to NP-hard nature of the addressed problem, a metaheuristic algorithm called General Variable Neighbourhood Search (GVNS) has been proposed which similar to Variable Neighbourhood Search (VNS) algorithm has shaking procedure and local search algorithm but the severity of the shaking procedure depending on the progress of incumbent solution changes. Also, time-saving strategies that allow focusing on promising movements in the search algorithm, as well as the shaking producer of the proposed GVNS algorithm, are incorporated. The performance of the heuristic algorithms and GVNS thorough comprehensive benchmark problems are presented.