An effective neighborhood search algorithm for scheduling a flow shop of batch processing machines

This paper considers scheduling problem of flow shop with many batch processing machines and objective of maximum lateness. An effective neighborhood search algorithm (NSA) is proposed for the problem, in which a job permutation and a batch permutation are used to indicate the solution of two sub-problems, respectively. Each job permutation consists of several family-permutations for the representation of jobs from the same family. Two swaps are applied to two permutations to produce new solutions. NSA is applied to a number of instances and compared with some methods, and computational results validate the good performance of NSA.

► Literature on BPM scheduling of flow shop seldom considered maximum tardiness and more than two BPMs.
► This paper considers many-BPM flow shop scheduling problem with maximum lateness.
► In neighborhood search algorithm (NSA), two swaps are used to produce new solutions.
► NSA is compared with some methods and results validate the good performance of NSA.