Representación Gráfica del Problema de Máquinas en Paralelo No Relacionadas para Colonia de Hormigas por Medio de un Grafo Disyuntivo
DOI:
https://doi.org/10.30973/progmat/2011.3.1/4Palabras clave:
Modelado, Grafo disyuntivo, dígrafo, Máquinas en Paralelo no Relacionadas, Colonia de HormigasResumen
El presente trabajo propone un modelado del problema de Máquinas en Paralelo no Relacionadas para Colonia de Hormigas por medio de un grafo disyuntivo, el cual facilita la comprensión del comportamiento del método de solución aplicado al problema antes mencionado. Para entender el funcionamiento del grafo propuesto, se realizó un análisis por medio de un digrafo para una solución particular a una instancia pequeña. Se da una introducción a definiciones básicas de teoría de grafos. Se analizan las características básicas del problema de Máquinas en Paralelo no Relacionadas, y se da una introducción general a Colonia de Hormigas, lo que da las bases para analizar las características tanto del problema como del método de solución, para lograr un modelo de grafos eficiente que permita mejorar la comprensión de Colonia de Hormigas aplicado a un problema de Calendarización de tipo NP.
Citas
Papadimitrou Christos H., Steiglitz Kenneth. Combinatorial Optimization. Algorithms and Complexity. ISBN. 0-486-40258-4, Dover Publications, Inc. Mineola, New York, 1998.
Comellas Francesc, Fàbrega Josep, Sànchez Anna, Serra Oriol. Matemática Discreta. ISBN. 84- 8301-456-4. Universidad Politécnica de Cataluña, S. L. Ediciones UPC, 2001.
Diestel Reinhard. Graph Theory. Graduate Texts in Mathematics. Third Edition. ISBN. 0072-5285, ISBN-10 3-540-26183-4, ISBN-13 978-3-540-26183-4. Springer-Verlag Berlin Heidelberg. Alemania, 2006.
Pinedo Michael L. Scheduling Theory, Algorithms, and Systems. Third Edition. New York University. ISBN: 978-0-387-78934-7, eISBN: 978-0-387-78935-4. Ed. Prentice Hall. Springer, 2008.
Garey M. R., D. Johnson. “Computers and Intractability” a Guide to the Theory of NP Completeness. Freeman. New York NY. ISBN 0-7167-1044-7. 1979.
Dorigo M., Maniezzo V., Colorni A. Positive Feedback as a Search Strategy. Technical report 91- 016, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1991a.
Dorigo M., Maniezzo V., Colorni A. The Ant System: An Autocatalytic Optimizing Process. Technical Report 91-016 Revised, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1991b. 48 Martínez-Oropeza Alina
Dorigo M. Optimization, Learning and Natural Algorithms [in Italian]. PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1992.
Dorigo M., Maniezzo V., Colorni A. Ant System: Optimization by a Colony of Cooperating Agents. IEEETransactions on Systems, Man. and Cybernetics–Part B, 26(1):29– 41, 1996. https://doi.org/10.1109/3477.484436
Dorigo M., Stützle T. The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. Handbook of Metaheuristics, Springer. 2003.
Grassé P. P. La Reconstruction Du Nid et Les Coordinations Inter-Individuelles Chez Bellicositermes Natalensis et Cubitermes Sp. La théorie de la Stigmergie: Essai d Interpretation Du Comportement Des Termites Constructeurs, pages 41- 81, 1959.
Cruz-Chávez Marco Antonio, Martínez Oropeza Alina, Zavala-Díaz José Crispín, Martínez-Rangel Martín G. Relajación del Problema de Calendarización de Trabajos en un Taller de Manufactura utilizando un Grafo Bipartita. 7mo. Congreso Internacional de Cómputo en Optimización y Software AGECOMP-CICos 2009. ISBN: 978-970.9750-26.3. 2009
Cruz-Chávez Marco Antonio, Martínez Oropeza Alina, Rivera López Rafael. Relaxation of Job Shop Scheduling Problem using a Bipartite Graph. Presentado como Ponencia en Cerma 2010. To publish in IEEE. 2010. https://doi.org/10.1109/CERMA.2010.27
Kozo Sugiyama. Graph Drawing and Applications for Software and Knowledge Engineers. ISBN. 981-02-4879-2. Vol. 11. World Scientific. 2002.
Di Battista Giuseppe, Eades Peter, Tamassia Roberto , Tollis Ioannis G. Graph Drawing. Algorithms for the Visualization of Graphs. ISBN. 0-13-301615-3. Ed. Prentice Hall. USA, 1999.
Martínez Oropeza Alina. Solución al Problema de Máquinas en Paralelo No Relacionadas Mediante un Algoritmo de Colonia de Hormigas. Tesis Profesional para obtener el grado de Maestro en Ingeniería y Ciencias Aplicadas. CIICAp UAEM. Cuernavaca, Mor., México, 2010.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2011 Programación Mtatemática y Software
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Usted es libre de:
 |
Compartir — compartir y redistribuir el material publicado en cualquier medio o formato. |
 |
Adaptar — combinar, transformar y construir sobre el material para cualquier propósito, incluso comercialmente. |
Bajo las siguientes condiciones:
 |
Atribución — Debe otorgar el crédito correspondiente, proporcionar un enlace a la licencia e indicar si se realizaron cambios. Puede hacerlo de cualquier manera razonable, pero de ninguna manera que sugiera que el licenciador lo respalda a usted o a su uso. |
| Sin restricciones adicionales: no puede aplicar términos legales o medidas tecnológicas que restrinjan legalmente a otros a hacer cualquier cosa que permita la licencia. |
