Actas de congresos
Evolutionary Algorithms For Scheduling A Flowshop Manufacturing Cell With Sequence Dependent Family Setups
Registro en:
Computers And Industrial Engineering. , v. 48, n. 3, p. 491 - 506, 2005.
3608352
10.1016/j.cie.2003.11.004
2-s2.0-14644435008
Autor
Franca P.M.
Gupta J.N.D.
Mendes A.S.
Moscato P.
Veltink K.J.
Institución
Resumen
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. © 2005 Elsevier Ltd. All rights reserved. 48 3 491 506 Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., A survey of scheduling research involving setup considerations, OMEGA (1999) International Journal of Management Science, 27, pp. 219-239 Aarts, E.H.L., Van Laarhoven, P.J.M., Lenstra, J.K., Ulder, N.L.J., A computational study of local search algorithms for job shop scheduling (1994) ORSA Journal on Computing, 6, pp. 118-125 Cheng, T.C.E., Gupta, J.N.D., Wang, G., A review of flowshop scheduling research with setup times (2000) Production and Operations Management, 9, pp. 283-302 Corne, D., Glover, F., Dorigo, M., (1999) New Ideas in Optimisation, , McGraw-Hill New York Glass, C.A., Potts, C.N., A comparison of local search methods for flow shop scheduling (1996) Annals of Operations Research, 63, pp. 489-509 Gorges-Schleuter, M., Asparagos96 and the traveling salesman problem (1997) Proceedings of 1997 IEEE International Conference on Evolutionary Computation - ICEC'97, pp. 171-174. , Indianapolis, USA Gupta, J.N.D., Darrow, W.P., The two-machine sequence dependent flowshop scheduling problem (1986) European Journal of Operational Research, 24, pp. 439-446 Hart, W.E., Baden, S., Belew, R.K., Kohn, S., Analysis of the numerical effects of parallelism on a parallel genetic algorithm (1996) Proceedings of 10th International Parallel Processing Symposium - IPPS'96, pp. 606-612. , Honolulu, USA Hitomi, K., Nakamura, N., Yoshida, T., Okuda, K., An experimental investigation of group production scheduling (1977) Proceedings of the Fourth International Conference on Production Research, Tokyo, pp. 608-617 Mendes, A.S., Muller, F.M., França, P.M., Moscato, P., Comparing meta-heuristic approaches for parallel machine scheduling problems with sequence-dependent setup times (1999) Proceedings of the 15th International Conference on CAD/CAM Robotics and Factories of the Future, , Àguas de LindÒia, SP, Brazil Moscato, P., On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms (1989) Caltech Concurrent Computation Program, p. 826. , C3P Report 1989 Radcliffe, N.J., Formal memetic algorithms (1994) Evolutionary Computing: AISB Workshop, pp. 1-16. , T.C. Fogarthy Springer New York Schaller, J.E., Gupta, J.N.D., Vakharia, A.J., Scheduling a flowline manufacturing cell with sequence dependent family setup times (2000) European Journal of Operations Research, 125, pp. 324-339