Gómez Meneses, PedroBriones Méndez, Miguel Ángel2017-09-272023-11-132017-09-272023-11-132017-09-272017-08https://tesis.ucsc.cl/handle/25022009/3560Informe de Proyecto de Título para optar al Título de Ingeniería Civil InformáticaEl Permutation Flow-Shop Scheduling Problem (PFSSP) es una clase de problemas de programación en el cual un conjunto de trabajos permutables (el orden de ingreso puede ser modificado) debe ser procesado por un conjunto de máquinas fijas optimizando el tiempo de ejecución por máquina y el tiempo total del proceso completo (desde el primer hasta el último trabajo finalizado) minimizando los tiempos de espera y de inactividad en cada uno de ellos. Este tipo de problemas puede aplicarse tanto a las instalaciones de producción como a los diseños informáticos. En el presente informe se investigan los resultados para el PFSSP utilizando la innovadora metaheurística denominada Extremal Optimization (EO), desarrollada recientemente y basada en la teoría de co-evolución y el fenómeno del equilibrio puntuado de Bak-Sneppen que no considera la evolución de forma lineal sino más bien ramificada, e incluyendo, como método de selección, el concepto de feromona extraído del Algoritmo de Colonia de Hormigas (ACO). Como el informe es investigativo se realiza análisis a 4 variantes de EO. Se comienza aplicando EO en su forma pura y luego con búsqueda local, ambas con un criterio de selección propio, y luego se utiliza como método de selección el concepto de feromona analizando los datos obtenidos tanto en su forma pura y búsqueda local (con feromona). Con el procedimiento anterior se logra estudiar con más detenimiento el cambio que surge al aplicar la feromona a EO. Si bien el proceso de búsqueda puede variar dependiendo del individuo a cargo, la feromona aplicada a EO no se ve afectada.Facultad de IngenieríaIngeniería Civil InformáticaThesis