Método particle swarm optimización aplicado al problema de múltiples objetivos del job shop scheduling o secuenciamiento de máquinas

Abstract

El problema de la programación de tareas en empresas tipo taller (Job Shop Scheduling-JSP) es una rama de la programación productiva que pertenece a la clase de problemas combinatorios de complejidad NP-Hard. Se aplica, usualmente, a la optimización de un único objetivo dejando a un lado la optimización de más ellos que, en la mayoría de las veces, suelen contradecirse. En problemas de tamaño medio y grande se presentan dos o más criterios en conflicto, es por esto, que se hace importante considerar múltiples objetivos a la hora de buscar soluciones factibles y poder así, tomar las respectivas decisiones en cuanto a la mejor combinación que permita disminuir costos, tiempos de finalización y cumplir con los tiempos de entrega. Gran variedad de métodos metaheurísticos han sido aplicados al problema obteniendo resultados aproximados al óptimo. Uno de estos métodos es la optimización por enjambre de partículas, el cual es utilizado usualmente para resolver problemas de optimización continua y en algunos casos para resolver problemas discretos como la programación de tareas. Este trabajo estudia el problema de la programación de tareas y realiza una revisión bibliográfica de los últimos métodos utilizados en la resolución del problema y se enfoca, principalmente, en el método Particle Swarm Optimization (PSO). Además, presenta de manera clara y profunda el método Multi-objective Particle Swarm Optimization (MOPSO) el cual es una modificación del PSO para aplicarlo al problema de secuenciamiento de máquinas y resolverlo en problemas de comparación. Se realiza una prueba de escritorio por medio de Excel para una instancia 3x3 del problema para entender el funcionamiento básico del algoritmo y finalmente, se presenta el pseudocódigo para resolver el problema de secuenciamiento de máquinas en empresas tipo taller con múltiples objetivos de optimización. Proyecto de Grado. Modalidad