Modelo de optimización bi-objetivo para la programación de máquinas en paralelo: teoría de juegos vs algoritmos genéticos
Resumen
Este artículo contempla el problema de programación de la producción en una con curación de máquinas en paralelo con el objetivo de minimizar dos criterios en particular: el lapso y el tiempo total de flujo. En este problema en particular, el incremento de uno de estos objetivos resulta en la reducción del otro, por lo que se propone su solución bajo enfoques meta heurísticos. Dos tipos de algoritmos fueron considerados: uno basado en la teoría de juegos y el otro en los algoritmos genéticos. Para el primero se diseña un mecanismo de juego no cooperativo entre dos jugadores, en donde cada jugador busca optimizar cada criterio de programación de las máquinas. Para el segundo enfoque se implementa el algoritmo genético SPEA, en donde se seleccionan aquellas soluciones dominantes en ambos objetivos. Resultados de ambos enfoques resultan en un Frente de Pareto, las cuales representan las soluciones dominantes para ambos objetivos. Estos resultados demuestran que ambos enfoques son complementarios: SPEA arroja resultados que cubren todo el frente de Pareto, mientras que el algoritmo de Juegos No Cooperativo indica la programación más conveniente para cada agente en particular.Descargas
Citas
V. Suresh and D. Chaudhuri, “Bicriteria scheduling problem for unrelated parallel machines,” Comput. Ind. Eng., vol. 30, no. 1, pp. 77–82, Jan. 1996. DOI:10.1016/0360-8352(95)00028-3
L. Yu, H. M. Shih, M. Pfund, W. M. Carlyle, and J. W. Fowler, “Scheduling of unrelated parallel machines: an application to PWB manufacturing,” IIE Trans., vol. 34,no. 11, pp. 921–931. DOI: 10.1023/A:1016185412209
M. Pfund, L. Yu, J. W. Fowler, And M. Carlyle, “TheImpacts Of Variability On Scheduling Approaches For A Printed Wiring Board Assembly Operation,” J. Electron. Manuf., vol. 11, no. 01, pp. 19–31, Mar. 2002. DOI:10.1142/S0960313102000242
Y. Yang and L. Tang, “Local Search Heuristic for Multiple Objective Coil Scheduling Problem on Unrelated Parallel Machines,” in 2009 International Joint Conference on Computational Sciences and Optimization, 2009, vol. 2, pp. 777–780. DOI: 10.1109/CSO.2009.402
Y.-K. Lin, J. W. Fowler, and M. E. Pfund, “Multiple-objective heuristics for scheduling unrelated parallel machines,” Eur. J. Oper. Res., vol. 227, no. 2, pp. 239–253, Jun. 2013. DOI: 10.1016/j.ejor.2012.10.008
C. Low, Y. Yip, and T.-H. Wu, “Modelling and heuristics of FMS scheduling with multiple objectives,” Comput. Oper. Res., vol. 33, no. 3, pp. 674–694, Mar. 2006. DOI:10.1016/j.cor.2004.07.013
M. J. Geiger, “Solving multi-objective scheduling problems— An integrated systems approach,” in Artificial Intelligence in Theory and Practice, vol. 217, M. Bramer, Ed. Springer US, 2006, pp. 493–502. DOI: 10.1007/978-0-387-34747-9
G. Kulcsár And M. K. Forrai, “Solving Multi-Objective Production Scheduling Problems Using A New Approach,” Prod. Syst. Inf. Eng., vol. 5, pp. 81–94, 2009.
S. Bandyopadhyay and R. Bhattacharya, “Solving multi-objective parallel machine scheduling problem by a modified NSGA-II,” Appl. Math. Model., vol. 37, no. 10–11, pp. 6718–6729, Jun. 2013. DOI: 10.1016/j.apm.2013.01.050
S. A. Torabi, N. Sahebjamnia, S. A. Mansouri, and M. A. Bajestani, “A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem,” Appl. Soft Comput., vol. 13, no. 12, pp. 4750– 4762, Dec. 2013. DOI: 10.1016/j.asoc.2013.07.029
E. Kutanoglu and S. D. Wu, “An Incentive Compatible Mechanism for Distributed Resource Planning,” pp. 28, 2001.
S. D. W. Erhan Kutanoglu, “An Auction-Theoretic Modeling of Production Scheduling to Achieve Distributed Decision Making,” Ph.D. dissertation, Dept. Ind. Man. Sys. Eng., Lehigh Univ, Bethlehem, PA, 1997.
A. Archer and E. Tardos, “Truthful mechanisms for one-parameter agents,” in Proceedings 2001 IEEE International Conference on Cluster Computing, 2001, pp.482–491. DOI:10.1109/SFCS.2001.959924
E. Even-dar, A. Kesselman, and Y. Mansour, “Convergence time to nash equilibria,” School of Computer Science, Tel Aviv Univ., p. 17, 2003.
N. Nisan, “Algorithms for Selfish Agents,” in STACS 99 Lecture Notes in Computer Science, vol. 1563, C. Meinel and S. Tison, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 1–15.
G.-Q. Zhang, J.-J. Wang, and Y.-J. Liu, “Scheduling Jobs with Variable Job Processing Times on Unrelated Parallel Machines,” Sci. World J., no. 242107, pp. 1–7, 2014. DOI: 10.1155/2014/242107
B. Heydenreich, R. Müller, and M. Uetz, “Games and Mechanism Design in Machine Scheduling-An Introduction,” Prod. Oper. Manag., vol. 16, no. 4, pp. 437–454, Jan. 2009. DOI: 10.1111/j.1937-5956.2007.tb00271.x
D. R. Rios, C. R. Pinto, and C. Paternina-Arboleda, Game Theoretic Approaches to Parallel Machine Scheduling: A Bi-objective Optimization Problem Viewed as a Non-cooperative Game of Two Players. LAP Lambert Academic Publishing, pp.176, 2012.
E. Zitzler and L. Thiele, An Evolutionary Algorithm for Multiobjective Optimization: The Strength Pareto Approach. Zurich: TIK, 1998.
A. Cama Pinto, E. De la Hoz Franco, and D. Cama Pinto, “Las redes de sensores inalámbricos y el internet de las cosas,” INGE CUC, vol. 8, no. 1, pp. 163–172, 2012.
Y. Donoso and R. Fabregat, Multi-Objective Optimization in Computer Networks Using Metaheuristics. Boston, MA: Auerbach Publications, pp. 472, 2007.
C. E. Gómez Montoya, C. A. Candela Uribe, and L. E. Sepúlveda Rodríguez, “Seguridad en la configuración del servidor web Apache,” INGE CUC, vol. 9, no. 2, pp. 31–38, 2013.
E. Gutierrez and G. Mejía, “Evaluación de los algoritmos Genéticos para el problema de Máquinas en Paralelo con Tiempos de Alistamiento Dependientes de la Secuencia y Restricciones en las Fechas de Entrega.” p. 6, 2006.
P. M. França, A. S. Mendes, and P. Moscato, “Memetic algorithms to minimize tardiness on a single machine with sequence-dependent setup times,” in Proceedings of the 5th International Conference of the Decision Sciences Institute, 1999, pp. 1708–1710.
A. Gómez Cabrera and A. R. Orozco Ovalle, “Simulación digital como herramienta para la gestión del conocimiento en la construcción de edificaciones en concreto,” INGE CUC, vol. 10, no. 1, pp. 75–82, 2014.
K. Deb and D. Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms. New York, NY: John Wiley & Sons, Inc., pp. 249-258, 2001
J. D. Schaffer, R. A. Caruana, L. J. Eshelman, and R. Das, “A study of control parameters affecting online performance of genetic algorithms for function optimization,” in Proceedings of the third international conference on Genetic algorithms, 1989, pp. 51–60
A. P. Cortés Vásquez, “Sistema de Aprendizaje de Patrones de Navegación Web Mediante Gramáticas Probabilísticas de Hipertexto,” INGE CUC, vol. 11, no. 1, pp. 72–78, 2015. Doi: 10.17981/ingecuc.11.1.2015.07
E. Altman, T. Başar, T. Jiménez, and N. Shimkin, “Routing into Two Parallel Links: Game-Theoretic Distributed Algorithms,” J. Parallel Distrib. Comput., vol. 61, no. 9, pp. 1367–1381, Sep. 2001. DOI: 10.1006/jpdc.2001.1754
Los artículos publicados son de exclusiva responsabilidad de sus autores y no reflejan necesariamente las opiniones del comité editorial.
IJMSOR respeta los derechos morales de sus autores, los cuales ceden al comité editorial los derechos patrimoniales del material publicado. A su vez, los autores informan que el presente trabajo es inédito y no ha sido publicado anteriormente.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
