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

Authors: Miguel Rojas-Santiago; Shanthi Muthuswamy; Purushothaman Damodaran; Mario C. Velez-Gallego

Addresses: Departamento de Ingeniería Industrial, Universidad del Norte, Barranquilla, Colombia ' Department of Technology, Northern Illinois University, De Kalb, Il-60115, USA ' Department of Industrial and Systems Engineering, Northern Illinois University, De Kalb, Il-60115, USA ' Departamento de Ingeniería de Producción, Universidad EAFIT, Medellín, Colombia

Abstract: 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.

Keywords: no-wait flow shop; batch processing machines; BPMs; ant colony optimisation; ACO; makespan.

DOI: 10.1504/IJISE.2017.087192

International Journal of Industrial and Systems Engineering, 2017 Vol.27 No.3, pp.390 - 411

Received: 05 Jun 2015
Accepted: 03 Oct 2015
Published online: 11 Oct 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article