Title: Minimising makespan in a no-wait flow shop with two batch processing machines: a grasp algorithm

Authors: Jairo Maya; Shanthi Muthuswamy; Mario C. Vélez-Gallego; Miguel Rojas-Santiago

Addresses: Departamento de Ingeniería de Producción, Universidad EAFIT, Carrera 49 #7 sur 50, Medellín, Colombia ' Department of Technology, Northern Illinois University, De Kalb, Il-60115, USA ' Departamento de Ingeniería de Producción, Universidad EAFIT, Carrera 49 #7 sur 50, Medellín, Colombia ' Departamento de Ingeniería Industrial, Universidad del Norte, Km.5 Vía Puerto Colombia, Barranquilla, Colombia

Abstract: In a flow shop with two batch processing machines (BPMs) one of the key objectives is to minimise the makespan. In this study jobs with different sizes were batched together, without exceeding the machine capacity, and processed in the BPMs. Job ready times were also taken into consideration hence, a batch cannot be started unless all the jobs in the batch are ready and available. Also, the batches cannot wait between two machines (i.e., no-wait). The problem under study is NP-hard. A greedy randomised adaptive search procedure (GRASP) algorithm has been developed for this problem. Experiments were conducted to study up to 200 job instances. The solution quality of the GRASP algorithm was compared with the results of a mathematical model developed using CPLEX and a particle swarm optimisation algorithm. The experimental study highlights the advantages, in terms of solution quality of using GRASP to solve large-scale problems.

Keywords: no-wait flow shops; batch processing machines; BPMs; GRASP; greedy randomised adaptive search; makespan; particle swarm optimisation; PSO; mathematical modelling.

DOI: 10.1504/IJISE.2014.061991

International Journal of Industrial and Systems Engineering, 2014 Vol.17 No.2, pp.152 - 169

Published online: 25 Jul 2014 *

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