Correo Electrónico
DNINFOA - SIA
Bibliotecas
Convocatorias
Identidad U.N.
Published
Applying genetic algorithms for programming manufacturing cell tasks
Aplicación de algoritmos genéticos para la programación de tareas en una celda de manufactura
Keywords:
flexible manufacturing, manufacturing cells, production-line scheduling, genetic algorithms (en)manufactura flexible, celdas de manufactura, programación de líneas de producción, algoritmos genéticos (es)
Downloads
This work was aimed at developing computational intelligence for scheduling a manufacturing cell’s tasks, based mainly on genetic algorithms. The manufacturing cell was modelled as being a production-line; the makespan was calculated by using heuristics adapted from several libraries for genetic algorithms computed in C++ builder.
Several problems dealing with small, medium and large list of jobs and machinery were resolved. The results were compared with other heuristics. The approach developed here would seem to be promising for future research concerning scheduling manufacturing cell tasks involving mixed batches.
El propósito del trabajo fue plantear una metodología para la programación de tareas de una celda de manufactura, basada principalmente en algoritmos genéticos. La celda de manufactura fue modelada como una línea de flujo, y se desarrollaron cálculos que permiten saber el makespan usando una heurística adaptada de una librería realizada para algoritmos genéticos, esto implantado en un ambiente de programación C++ builder. Se resolvieron problemas diversos, considerando distintos tamaños de lista en trabajos y máquinas, los cuales fueron comparados con los resultados de otras heurísticas. Los futuros trabajos pueden considerar la programación de tareas en celdas de manufactura con lotes de diferentes volúmenes.
Downloads
References
Askin R. G., and C. R. Standridge (1993), Modelling and Analysis of Manufacturing Systems, John Wiley & Sons, New York.
Brizuela A., Carlos and Sannomiya, Nobuo (2000). “From the Classical Job Shop to Real Problem: A Genetic Algorithm Approach”, Kyoto Institute of Technology.
Chase, R.; Aquilano N.; Jacobs R. (2000), Administración de producción y operaciones; Mc Graw Hill.
Cheng, R.; Gen, M.; Tsujimura, Y. (1996), “A Tutorial Survey of Job-Shop Scheduling Problems using Genetic Algorithms-I. Representation”, Computers & Industrial Engineering, 30(4), 983-997.
Davis, L. (1985). “Sob-Shop Scheduling with Genetic Algorithm”, in Grefenstette J. J. (ed.) Proceedings of the 1st International Conference on Genetic Algorithms and their Applications, Pittsburgh, PA, USA, Lawrence Erlbaum, pp. 136-140.
Delgado, Alberto (1998) Inteligencia artificial y minirrobots, Ecoe Ediciones,
Díaz A. y otros (1996), Optimización heurística y redes neuronales, Editorial Paraninfo.
Duarte, Oscar G. (2001) “UNGENETICO: una librería de clases en C++ para algoritmos genéticos con codificación hibrida”, trabajo de promoción para acceder al cargo de profesor asociado, Facultad de Ingeniería, Universidad Nacional.
ElMaraghy, H.; Patel. V.; Abdallah, B.I. (2000), “Scheduling of Manufacturing Systems Under Dual Resource Constraints Using Genetic Algorithms”, Journal of manufacturing Systems Dearborn.
Falkenauer, E. and Bouffouix, S. (1991), “A Genetic Algorithm for the Job-Shop”, Proceedings of the IEEE International Conference on Robotics and Automation, Sacramento, California, USA, pp. 824-829.
Garey, Michael R. and Johnson, David S. (1979)”, Computers and Intractability: A guide to the theory of NP-Completeness”, W.H. Freeman and Company, New York.
Gershwin (1994), “Manufacturing Systems Engineering”, Chapter 4 Prentice - Hall
Gideon, Weiss (1995), “A Tutorial in Stochastic Scheduling”, Editors: Chretienne, P and Coffman, E.G. Jr. and Lenstra, J.K. and Liu, Z., Scheduling: Theory and its applications, chapter 3, pages 33-64, John Wiley & Sons.
Giffler, B. and Thompson, G. L. (1960), “Algorithms for Solving Production Scheduling Problems”, Operations Research, 8(4), 487-503.
Goldberg, D.E. (1994) Genetic and Evolutionary Algorithms come of Age, Communications of the ACM, Volume 37, No. 3, pages 113-119.
Husbans P and Mill F (2000), Scheduling with genetic algorithms, School of Cognocitive and Computing Sciences University of Sussex Falmer Brighton UK.
Jain A.S and Meeran S. (2000), A State of the art Review of Job Shop Scheduling Techniques, University of Dundee, Scotland UK
Jones, Albert and Rabelo, Luis C. (1998), Survey of Job Shop Scheduling Techniques, NISTIR, National Institute of Standards and Technology, Gaithersburg, MD (on-line publication).
Jamshidi (1994), “Design and Implementation of Intelligent Manufacturing Systems”
Kusiak Andrew (1990), Intelligent Manufacturing System, Cap. 12-13 John Wiley & Sons
Liu D, Hou E. (1994) “n/m Job Shop Scheduling with genetic Algorithm”, Intelligent Automation and Soft Computing, Vol 1- pags. 511-516, Trends in research, development and applications. TST Press.
Mazzola J., Daniels R. “Flow shop scheduling with resource flexibility”, obtenido de la referencia www.orunc.edu/downloads/abstracts/mazzola/flow.html
Montazeri, M. and Van Wassenhove, L.N. (1990), Analysis of scheduling rules for an FMS, International Journal of Production Research 1990,28(4) 785-802.
Murata T., Ishibuchi H., and Tanaka H. (1996), “Multi-Objective Genetic Algorithms and Its Application to Flow Shop Scheduling”, Computers and Industrial Engg. (v.30, n.4, 1996), pp.1061-1071.
Morton, Thomas E. and Pentico, David W. (1993), “Heuristic Scheduling Systems with Applications to Production Systems and Project Management”, Wiley series in engineering and technology management, Wiley-Interscience,
Norman, B. A. and Bean, J. (1997), “Random Keys Genetic Algorithm for Job Shop Scheduling”, Engineering Design and Automation, vol 3, 145-156.
Onwubolu G.C., (2000) “Manufacturing cell scheduling using genetic algorithms”, Proceeding Institute Mechanical Engineers Vol. 214, Part B,
Osman, I. H. and Kelly, J. P (1996), Meta-Heuristics: An Overview, in Osman, I. H. and Kelly, J. PR MetaHeuristics: Theory and Applications, Kluwer Academic Publishers, Norwell, MA, USA, Chapter 1, pp. 1-21.
Pinedo, Michael (1995), Scheduling: Theory, Algorithms, and Systems, Englewood Cliffs, Prentice Hall, N.J.
Proceeding of the first world Automation Congress 1994 Hawaii USA Intelligent Automation and Soft Computing, Vol 1- Trends in research, development and applications, 1994, TST Press.
Sabuncuoglu, I. and Gurgun, B. (1996), “A Neural Network Model for Scheduling Problems”, European Journal of Operational Research, 93(2), Sept, 288-299.
Shi, G. (1997), “A Genetic Algorithm Applied to a Classic Job-Shop Scheduling Problem”, International Journal of Systems Science, 28(1), 25-32.
Singh N. (1996), System Approach to Computer Integrated Design and Manufacturing, pp 529-544, John Wiley & Sons editors
Soma H.; Hori M., and Sogou T. (1995), “Schedule Optimization Using Fuzzy Inference”, OMRON Corporation IEEE Proceeding International Conference on Fuzzy Systems March 20-24, Yokohama /Japon.
Song, Y.; Hughes, J.G.; Azarmi, N., and Voudouris C. (2000), “A Genetic Algorithm with an Incomplete Representation for the Job Shop Scheduling Problems”, University of Ulster at Jordanstown
Strizle T. (1998) “Applying iterated local search to the permutation flow shop problem” obtenido mediante http://www.idsia.ch/~monaldo/fisp.html
Tanigawa Y.; Fujimoto, H.; Yasuda, K.; Iwahashi, K.; (1995), “Applications of genetics Algorithms and simulations to dispatching rule-based FMS Scheduling”, IEEE International Conference on Robotics and Automation.
Tedford, J.D.; Lowe, C. (1999), “Scheduling for Just-InTime Flexible Manufacturing Using Adaptative Fuzzy Logic”, Proceedings of the Institution of Mechanical Engineers, Vol. 213 Part B.
Torres, Fidel (2001), “Asignación y secuenciación de tareas sobre máquinas, por medio de heurísticas de recocido simulado”, Congreso Internacional de Inteligencia Computacional, Medellín.
Van Laarhooven, P J. M.; Aarts, E. H. L. and Lenstra, J. K. (1992), lob Shop Scheduling by Simulated Annealing”, Operations Research, Jan-Feb, 40(1), 113-125.
Vollman, T.; Berry, W., and Whybark D. (1997), “Sistemas de planificación y de control de la fabricación”, Mc GrawHill-Irwin, tercera edición.
Wang, W.; Brunn, P (2000), “An effective genetic algorithm for job shop scheduling”, Proceeding Institute Mechanical Engineers, Vol. 214 Part B.
Wang, M.Y, Sethi S.P(1995), “Minimizing makespan in flow shop with pallet requirements”, University of Toronto Canada, obtenido mediante http://www.idsia.ch/~monaldo/fisp.html
Yamada, T.; Reeves, C. (1998), “Solving the Csum permutation flow shop scheduling problem by genetic local search”, IEEE International Conference on Evolutionary Computation pp: 230-234.
Young, I.C. (1994), “Job Shop Scheduling with Genetic Algorithms and Tabu Search”, septiembre de 1994, documento on-line publicado en la dirección www.cs.umass.edu/~young/grad/tardy/tardy/html Revision en internet
http://citeseer.nj.nec.com/19048.html
http://www.cs.umass.edu/~young/grad/tardy/tardy/html
http://w3.mor.itesm.mx/~optimiza/optibusca/scheduling.html
http://www.wi.leidenuniv.nl/~gusz/Flying_Circus/1.Reading/2.Tutorial/02/index.html
http://www.prenhall.com/weiss_dswin/html/jobsched.htm
http://www.uni-parderbron.de/sfb376/projects/c2/publications/sor97-fmsp-abstract.html
http://www.orunc.edu/downloads/abstracts/mazzola/flow.html
http://www.idsia.ch/~monaldo/fjsp.html
http://citeseer.nj.nec.com/149983.html y http://citeseer.nj.nec.com/411935.html (GA for Scheduling)
License
Copyright (c) 2005 Efredy Delgado, Carlos Julio Cortés Rodríguez, Óscar Germán Duarte Velasco
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
