Title: Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms

Authors: Purushothaman Damodaran, Neal S. Hirani, Mario C. Velez-Gallego

Addresses: Department of Industrial and Systems Engineering, Florida International University, Miami, FL 33174, USA. ' Department of Systems Science and Industrial Engineering, State University of New York, Binghamton, NY 13902–6000, USA. ' Departamento de Ingenieria de Produccion, Universidad EAFIT, Medellin, Colombia

Abstract: This paper aims to minimise the makespan of a set of identical batch processing machines in parallel. The batch processing machine can process a batch of jobs as long as the total size of all the jobs in the batch does not exceed its capacity. The processing time of the job and its size are given. Batch processing time is equal to the longest processing job in the batch. Two interdependent decisions are required, namely grouping jobs into batches, and scheduling the batches on the machines. The problem under study is NP-hard and hence a Genetic Algorithm (GA) approach is proposed. The effectiveness of the GA approach to solve randomly generated problems was compared with a Simulated Annealing (SA) approach, a Random Keys Genetic Algorithm (RKGA), a Hybrid Genetic Heuristic (HGH) and a commercial solver. The proposed GA approach was found to be very effective in finding a good solution in a short time as opposed to SA, RKGA and a commercial solver. Both GA and HGH are marginally better than each other on different problem instances. [Submitted 17 August 2007; Revised 10 October 2007; Revised 30 May 2008; Revised 29 July 2008; Accepted 15 September 2008]

Keywords: parallel processing; batch processing; parallel machines; scheduling; genetic algorithms; GAs; makespan.

DOI: 10.1504/EJIE.2009.023605

European Journal of Industrial Engineering, 2009 Vol.3 No.2, pp.187 - 206

Published online: 02 Mar 2009 *

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