TESIS LICENCIATURA
Evaluación de la Factibilidad de Soluciones Generadas con Estructuras de Vecindad para el Problema de Talleres de Manufactura
Pedro Bello Campusano
En este trabajo de tesis se evalúa la factibilidad y la eficacia de una nueva estructura de vecindad definida en una línea de tiempo propuesta, partiendo de una solución aleatoria, la cual desde el inicio se hace factible a través de métodos heurísticos. El primero, es un método convencional de Nakano y Yamada (1991), el cual tiene el nombre de algoritmo de calendarización, el segundo, es un método de armonización global que permite seguir calendarizando y corrigiendo soluciones no factibles. Posteriormente, se implementa el algoritmo de búsqueda local iterada, en el cual se aplica la estructura de vecindad con línea de tiempo (EVLT), que es la estructura de vecindad propuesta y se realiza una comparación de eficacia con respecto a la estructura de vecindad clásica de permutación de pares adyacentes sin tiempos de ocio (EVPA) Cruz-Chávez (2014). Para las pruebas, se utilizan los benchmarks que se encuentran en la página de Or-Library (1990) con instancias simétricas, para realizar la comparación de los resultados obtenidos.En base a los resultados obtenidos se observa que al aplicar la EVLT existe una mejora con respecto a la EVPA; la estructura de vecindad propuesta genera resultados más rápidamente para instancias pequeñas además de que el número de soluciones no factibles obtenidas en la búsqueda local iterada es inferior al 13%. En la mayor parte de las pruebas realizadas con los benchmarks utilizados y con EVLT se alcanza mejor makespan que con la EVPA.