Published

2005-05-01

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

DOI:

https://doi.org/10.15446/ing.investig.v25n2.14634

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)

Authors

  • Efredy Delgado Universidad Nacional de Colombia
  • Carlos Julio Cortés Rodríguez Universidad Nacional de Colombia
  • Óscar Germán Duarte Velasco Universidad Nacional de Colombia

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.

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. DOI: https://doi.org/10.1016/0360-8352(96)00047-2

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. DOI: https://doi.org/10.1016/S0278-6125(00)80011-4

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. DOI: https://doi.org/10.1109/ROBOT.1991.131689

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. DOI: https://doi.org/10.1287/opre.8.4.487

Goldberg, D.E. (1994) Genetic and Evolutionary Algorithms come of Age, Communications of the ACM, Volume 37, No. 3, pages 113-119. DOI: https://doi.org/10.1145/175247.175259

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). DOI: https://doi.org/10.1002/047134608X.W3352

Jamshidi (1994), “Design and Implementation of Intelligent Manufacturing Systems”

Kusiak Andrew (1990), Intelligent Manufacturing System, Cap. 12-13 John Wiley & Sons DOI: https://doi.org/10.1016/0895-7177(90)90369-X

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. DOI: https://doi.org/10.1080/00207549008942754

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. DOI: https://doi.org/10.1016/0360-8352(96)00053-8

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, DOI: https://doi.org/10.1243/0954405001517531

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. DOI: https://doi.org/10.1007/978-1-4613-1361-8_1

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. DOI: https://doi.org/10.1016/0377-2217(96)00041-0

Shi, G. (1997), “A Genetic Algorithm Applied to a Classic Job-Shop Scheduling Problem”, International Journal of Systems Science, 28(1), 25-32. DOI: https://doi.org/10.1080/00207729708929359

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. DOI: https://doi.org/10.1243/0954405991517164

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. DOI: https://doi.org/10.1287/opre.40.1.113

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. DOI: https://doi.org/10.1243/0954405001517685

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)

http://citeseer.nj.nec.com/bierwirth95generalized.html

How to Cite

APA

Delgado, E., Cortés Rodríguez, C. J. and Duarte Velasco, Óscar G. (2005). Applying genetic algorithms for programming manufacturing cell tasks. Ingeniería e Investigación, 25(2), 24–31. https://doi.org/10.15446/ing.investig.v25n2.14634

ACM

[1]
Delgado, E., Cortés Rodríguez, C.J. and Duarte Velasco, Óscar G. 2005. Applying genetic algorithms for programming manufacturing cell tasks. Ingeniería e Investigación. 25, 2 (May 2005), 24–31. DOI:https://doi.org/10.15446/ing.investig.v25n2.14634.

ACS

(1)
Delgado, E.; Cortés Rodríguez, C. J.; Duarte Velasco, Óscar G. Applying genetic algorithms for programming manufacturing cell tasks. Ing. Inv. 2005, 25, 24-31.

ABNT

DELGADO, E.; CORTÉS RODRÍGUEZ, C. J.; DUARTE VELASCO, Óscar G. Applying genetic algorithms for programming manufacturing cell tasks. Ingeniería e Investigación, [S. l.], v. 25, n. 2, p. 24–31, 2005. DOI: 10.15446/ing.investig.v25n2.14634. Disponível em: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14634. Acesso em: 28 mar. 2024.

Chicago

Delgado, Efredy, Carlos Julio Cortés Rodríguez, and Óscar Germán Duarte Velasco. 2005. “Applying genetic algorithms for programming manufacturing cell tasks”. Ingeniería E Investigación 25 (2):24-31. https://doi.org/10.15446/ing.investig.v25n2.14634.

Harvard

Delgado, E., Cortés Rodríguez, C. J. and Duarte Velasco, Óscar G. (2005) “Applying genetic algorithms for programming manufacturing cell tasks”, Ingeniería e Investigación, 25(2), pp. 24–31. doi: 10.15446/ing.investig.v25n2.14634.

IEEE

[1]
E. Delgado, C. J. Cortés Rodríguez, and Óscar G. Duarte Velasco, “Applying genetic algorithms for programming manufacturing cell tasks”, Ing. Inv., vol. 25, no. 2, pp. 24–31, May 2005.

MLA

Delgado, E., C. J. Cortés Rodríguez, and Óscar G. Duarte Velasco. “Applying genetic algorithms for programming manufacturing cell tasks”. Ingeniería e Investigación, vol. 25, no. 2, May 2005, pp. 24-31, doi:10.15446/ing.investig.v25n2.14634.

Turabian

Delgado, Efredy, Carlos Julio Cortés Rodríguez, and Óscar Germán Duarte Velasco. “Applying genetic algorithms for programming manufacturing cell tasks”. Ingeniería e Investigación 25, no. 2 (May 1, 2005): 24–31. Accessed March 28, 2024. https://revistas.unal.edu.co/index.php/ingeinv/article/view/14634.

Vancouver

1.
Delgado E, Cortés Rodríguez CJ, Duarte Velasco Óscar G. Applying genetic algorithms for programming manufacturing cell tasks. Ing. Inv. [Internet]. 2005 May 1 [cited 2024 Mar. 28];25(2):24-31. Available from: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14634

Download Citation

CrossRef Cited-by

CrossRef citations1

1. Imran Ali Chaudhry, Isam AbdulQader Elbadawi, Muhammad Usman, Muhammad Tajammal Chughtai. (2018). Minimising Total Flowtime in a No-Wait Flow Shop (NWFS) using Genetic Algorithms. Ingeniería e Investigación, 38(3), p.68. https://doi.org/10.15446/ing.investig.v38n3.75281.

Dimensions

PlumX

Article abstract page views

387

Downloads

Download data is not yet available.

Most read articles by the same author(s)