Solución al Problema de Secuenciación de Trabajos mediante el Problema del Agente Viajero

Anaya Fuentes, G.E.; Hernández Gress, E.S.; Seck Tuoh Mora, J.C.; Medina Marín, J.

doi:10.1016/j.riai.2016.07.003

Información del artículo

Resumen

Texto completo

Bibliografía

Descargar PDF

Estadísticas

Resumen

En este trabajo se estudia el Problema de Secuenciación de Trabajos codificado como un Problema de Agente Viajero y resuelto mediante Algoritmos Genéticos. Se propone un Algoritmo Genético en donde se comparan dos tipos de selección: por torneo y por ruleta. Se realizan diferentes pruebas para la solución del Problema del Agente Viajero con los dos tipos de selección bajo diferentes parámetros: número de individuos, número de iteraciones, probabilidad de cruce y probabilidad de mutación; a partir de estos se seleccionan los parámetros y el tipo de selección. Posteriormente se codifica al Problema de Secuenciación como un Problema del Agente Viajero. La propuesta se presenta mediante la aplicación a diferentes ejemplos del Problema de Secuenciación de Trabajos y la comparación con los resultados obtenidos en la literatura.

Palabras clave:

algoritmos eficientes

sistemas industriales de producción

problemas de optimización

problema de agente viajero

Abstract

In this paper we proposed a solution to the Job-Shop Scheduling Problem using the Traveling Salesman Problem solved by Genetic Algorithms. We proposed a genetic algorithm where we compare two types of selection: tournament and roulette. Different tests are performed to solve the Traveling Salesman Problem with the two types of selection under different parameters: number of individuals, number of iterations, crossover probability and mutation probability. Then the best type of selection and the best parameters are used to solve the Job-Shop Scheduling Problem with Genetic Algorithms for the Traveling Salesman Problem. The proposal is presented solving different examples of Job Sequencing Problem and compare them with the results obtained in the literature.

Keywords:

Efficient algorithms

industrial production systems

optimization problem

traveling salesman problem

Texto completo

Referencias no citadas

Beasley, 1990, Bektas, 2006, Bozejko et al., 2009, Buthainah and Hamza, 2008, Cerny, 1985, Chambers, 1998, Chatterjee et al., 1996, Chunguo et al., 2004, Delgado, 2005, Dorigo, 1997, Fogel, 1998, Gao et al., 2007, Ge et al., 2007, Gerhard, 2006, Goldberg, 1989, Holland, 1992, Jog et al., 1991, Juang, 2004, Larrañaga et al., 1999, Maldonado, 2010, Moon et al., 2002, Ruiz, 2011, Sivanamdam and Deepa, 2008, Tamilarasi y Anantha, 2010, Wagner, 1975, Winston, 2005 y Yamada y Nakano, 1997.

Referencias

[Beasley, 1990]

J. Beasley.

OR-Library: Distributing test problems by electronic mail.

Journal of the Operational Research Society, 11 (1990), pp. 1069-1072

[Bektas, 2006]

Bektas, T., 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures, 34,209-219.

[Bozejko et al., 2009]

W. Bozejko, J. Pempera, C. Smuntnicki.

Parallel simulated annealing for the Job Shop Scheduling problem.

Biological Cybernetics, 60 (2009), pp. 139-144

[Buthainah and Hamza, 2008]

F. Buthainah, A. Hamza.

Enhanced Traveling Salesman Problem solving by Genetic Algorithm Technique.

World Academy of Science, Engineering and Technology, 38 (2008), pp. 298-302

[Cerny, 1985]

Cerny, V., 1985. Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm. Lecture note in computer science Proceedings of the 9th Intenational Conference on Computational Science, 5544, 631-640.

[Chambers, 1998]

L. Chambers.

Genetic Algorithms.

University Western Press, (1998),

[Chatterjee et al., 1996]

S. Chatterjee, C. Carrera, L. Linch.

Genetic Algorithms and traveling salesman problems.

Siam Journal of Optimation, (1996), pp. 515-529

[Chunguo et al., 2004]

W. Chunguo, X. Wei, L. Yanchun.

A Modified Integer-Coding Genetic Algorithm for Job Shop Scheduling Problem, Trends in Artificial Intelligence.

Lecture Notes in Computer Science, 3157 (2004), pp. 373-380

[Delgado, 2005]

Delgado E., 2005. Aplicación de Algoritmos Genéticos para la Programación de Tareas de una celda de manufactura. Ingeniería e Investigación: Universidad Nacional de Colombia, 24-31.

[Dorigo, 1997]

M. Dorigo.

Ant colonies for the traveling salesman problem.

Universidad Libre de Bruselas, (1997),

[Fogel, 1998]

D. Fogel.

An evolutionary approach to the traveling salesman problem.

Biological Cybernetics, 60 (1998), pp. 139-144

[Gao et al., 2007]

Gao, S., Zhang L, and Zhang F. 2007. g. Solving Traveling Salesman Problem by Ant Colony Optimization Algorithm with Association Rule Proceedings of the Third International Conference on Natural Computation, 3, 693-698.

[Ge et al., 2007]

Ge, H., Du W., y Quian F., 2007. A hybrid algorithm based on swarm optimization and simulated annealing for job shop scheduling. Proceedings of the Third International Conference on Natural Computation, 3, 715-719.

[Gerhard, 2006]

R. Gerhard.

Discrete and Combinatorial Optimization.

Universidad de Heidelberg-Instituto de Ciencias de la Computación, (2006),

[Goldberg, 1989]

D. Goldberg.

Genetic Algorithms in Search.

Optimization and Machine Learning, Addison-Wesley Publishing Corporation, (1989),

[Holland, 1992]

J. Holland.

Adaptation in Natural and Artificial Systems.

MIT Press, (1992),

[Jog et al., 1991]

P. Jog, J. Kim, J. Suh, D. Gucht.

Parallel Genetic Algorithms Applied to the Traveling Salesman Problem.

European Journal of Operational Research, (1991), pp. 490-510

[Juang, 2004]

C. Juang.

A hybrid genetic algorithm and particle swarm optimization for recurrent network design.

IEEE Transactions on Evolutionary Computation, 34 (2004), pp. 997-1006

[Larrañaga et al., 1999]

P. Larrañaga, C. Kuijpers, R. Murga, I. Inza, S. Dizdarevic.

Genetic Algorithms for the Traveling Salesman Problem: A review of Representations and Operators.

Artificial Intelligence Review, (1999), pp. 129-170

[Maldonado, 2010]

Maldonado C. 2010. El mundo de las ciencias de la complejidad: Una investigación sobre qué son, su desarrollo y sus posibilidades. Universidad del Rosario.

[Moon et al., 2002]

C. Moon, J. Kim, G. Choi, Y. Seo.

An efficient genetic algorithm for the traveling salesman problem with precedent constraints.

European Journal of Operational Research, (2002), pp. 606-617

[Ruiz, 2011]

J. Ruiz.

Complexity Indicators Applied to the Job Shop Scheduling Problem.

International Journal of Combinatorial Optimization Problems and Informatics, (2011), pp. 25-31

[Sivanamdam and Deepa, 2008]

S. Sivanamdam, S. Deepa.

Introduction to Genetic Algorithms.

Springer, (2008),

[Tamilarasi y Anantha, 2010]

A. Tamilarasi, K. Anantha.

An enhanced genetic algorithm with simulated annealing for jobshop scheduling.

International Journal of Engineering Science and Technology, 2 (2010), pp. 144-151

[Wagner, 1975]

H. Wagner.

Principles of Operations Research.

Englewood Cliffs, 2ª ed., N.J. Prentice Hall, (1975),

[Winston, 2005]

W. Winston.

Investigación de Operaciones: Aplicaciones y Algoritmos.

Indiana University Press, (2005),

[Yamada y Nakano, 1997]

Yamada T., y Nakano R., 1997. Genetic Algorithms for Job Shop Scheduling. Proceedings of Modern Heuristic for Decision Support, UNICOM Seminar London, 67-81.

Indexada en:

Síguenos:

Indexada en:

Síguenos:

Suscríbase a la newsletter