Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cie.2003.11.004 Byline: Paulo M. Franca (a), Jatinder N.D. Gupta (b), Alexandre S. Mendes (d), Pablo Moscato (d), Klaas J. Veltink (c) Abstract: This paper considers the problem of scheduling part families and jobs within each part family in a flowshop manufacturing cell with sequence dependent family setups times where it is desired to minimize the makespan while processing parts (jobs) in each family together. Two evolutionary algorithms -- a Genetic Algorithm and a Memetic Algorithm with local search -- are proposed and empirically evaluated as to their effectiveness in finding optimal permutation schedules. The proposed algorithms use a compact representation for the solution and a hierarchically structured population where the number of possible neighborhoods is limited by dividing the population into clusters. In comparison to a Multi-Start procedure, solutions obtained by the proposed evolutionary algorithms were very close to the lower bounds for all problem instances. Moreover, the comparison against the previous best algorithm, a heuristic named CMD, indicated a considerable performance improvement. Author Affiliation: (a) Departamento de Engenharia de Sistemas, DENSIS Universidade Estadual de Campinas, UNICAMP C. P. 6101, 13081-970 Campinas, SP, Brazil (b) Department of Accounting and Information Systems, College of Administrative Science, The University of Alabama in Huntsville, Huntsville, AL 35899, USA (c) Department of Econometrics, University of Groningen Postbus 800, 9700 AV Groningen, The Netherlands (d) Department of Computer Science, School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, University of Newcastle Callaghan, 2308, NSW, Australia Article History: Received 1 April 2001; Revised 1 November 2002; Accepted 1 November 2003

This paper considers the problem of scheduling part families and jobs within each part family in a flowshop manufacturing cell with sequence dependent family setups times where it is desired to minimize the makespan while processing parts (jobs) in each family together. Two evolutionary algorithms--a Genetic Algorithm and a Memetic Algorithm with local search--are proposed and empirically evaluated as to their effectiveness in finding optimal permutation schedules. The proposed algorithms use a compact representation for the solution and a hierarchically structured population where the number of possible neighborhoods is limited by dividing the population into clusters. In comparison to a Multi-Start procedure, solutions obtained by the proposed evolutionary algorithms were very close to the lower bounds for all problem instances. Moreover, the comparison against the previous best algorithm, a heuristic named CMD, indicated a considerable performance improvement. Keywords: Flowshop scheduling; Family sequence dependent setups; Manufacturing cells; Group technology; Evolutionary algorithms; Empirical results