Recocido simulado y Hill Climbing con doble vecindad para el problema de calendarización en talleres de manufactura

RESUMEN Uno de los problemas clásicos del área de optimización combinatoria es el Problema de Calendarización para Talleres de Manufactura (del inglés Job shop Scheduling Problem), el cual se puede entender como un proceso de toma de decisiones y asignación de recursos para completar un número de tareas con períodos de tiempo determinados. Actualmente el estudio de este problema sigue vigente, ya que está clasificado como de complejidad NP-Completo y por lo tanto no existen métodos que puedan encontrar la mejor solución con algoritmos determinísticos que presentan prueba de optimalidad en un tiempo polinomial. En esta tesis se propone un algoritmo aproximado de cuatro fases para resolver el problema del Job Shop. Este algoritmo presenta una implementación de Recocido Simulado junto a una Mejora Iterativa de Búsqueda Local ampliada a una Doble Vecindad. Las instancias usadas en la experimentación pertenecen a benchmarks clásicos de la literatura y los resultados fueron comparados con los óptimos conocidos de dichas instancias. Se encontró el óptimo en más de la mitad de las instancias de prueba.

ABSTRACT The Job Shop Scheduling Problem is one of the most well-known problems of Combinatorial Optimization, it can be seen as a process of decision-making and resource allocation for the completion of a number of tasks within a certain time. The study of this problem is still relevant today as it has been classified as NP- Complete in complexity and thus there isn’t a method that can find the best solution by means of a deterministic algorithm with optimality proof in a polynomial time. In this thesis we propose a four-step approximate algorithm to solve the Job Shop problem. This algorithm features an implementation of Simulated Annealing along with an Iterative Improvement Local Search expanded to a Double Neighborhood. The instances used in the experimentation belong to classical benchmarks from the literature and the results were compared with the known optima of these instances. The algorithm found the optimum for more than half the instances used as a benchmark.