Scheduling batch processing machines in a no-wait flow shop using ACO to minimise the makespan

This paper considers a two-stage flow shop scheduling problem with a batch processing machine (BPM) in each stage. The processing time of the batch on the first machine is equal to the longest processing job in the batch, and the batch processing time on the second machine is equal to the sum of processing times of all the jobs in the batch. The jobs cannot wait between the two stages. The problem under study with the makespan objective is NP-hard. An ant colony optimisation (ACO) algorithm combined with batch forming and local search heuristics is proposed and its solution is compared with: a particle swarm optimisation (PSO) algorithm; a greedy randomised adaptive search procedure (GRASP) algorithm; and a commercial solver used to solve the mixed-integer linear formulation. The experimental study helps to highlight the advantages, in terms of solution quality and run time, of using ACO to solve large-scale problems.