Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines

This paper presents the scheduling problem on flow shop with many batch processing machines (BPM) to minimise total tardiness, maximum tardiness and number of tardy jobs, respectively. We propose an efficient variable neighbourhood search (VNS) for the problem, in which job permutation is the only optimisation object and the solutions of batch formation and batch scheduling can be directly obtained by using the permutation. To obtain the promising results, an initial solution of VNS is first produced and then one insertion operation and two swap operations are applied to improve the solution. The proposed VNS is finally tested and the computational results show its good performance on many-BPM flow shop scheduling.