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

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

European Journal of Industrial Engineering, 2009, vol. 3, issue 2, 187-206

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. (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.inderscience.com/link.php?id=23605 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:eujine:v:3:y:2009:i:2:p:187-206

Access Statistics for this article

More articles in European Journal of Industrial Engineering from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().