Int. J. of Industrial and Systems Engineering   »   2014 Vol.17, No.2

 

 

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

 

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

 

Available online: 29 May 2014

 

 

Editors Full text accessAccess for SubscribersPurchase this articleComment on this article