Taller de flujo regular con tiempos de cambio dependientes de la secuencia: Heurísticas constructivas basadas en la memoria

Abstract

Este Trabajo Fin de Grado aborda un problema de programación de la producción para un taller con una configuración de tipo Flow-Shop. Se presenta como restricción la permutación y la existencia de tiempos de set-up no anticipatorios dependientes de la máquina y la secuencia. Se pretende alcanzar una solución de calidad para el problema en un tiempo de cálculo razonable, buscando como objetivo la minimización del makespan. Los algoritmos utilizarán una pequeña modificación de la función objetivo genérica, priorizando en caso de empate las secuencias con menor tiempo ocioso entre el procesado de los trabajos. Los métodos aproximados propuestos para la resolución de este problema de secuenciación serán heurísticas constructivas basadas en la memoria. Incluirán una búsqueda local iterativa en cada paso de construcción de la secuencia, repitiendo las combinaciones de trabajos más prometedores en futuras iteraciones. Se han implementado cuatro heurísticas similares, realizando además una evaluación computacional con 1000 instancias para distintas versiones de ellas. Un total de 17 heurísticas han sido comparadas, que demuestran la eficiencia de las propuestas.

This thesis addresses a production scheduling problem using a flow shop layout and makespan minimisation. The permutation and the existence of non-anticipatory sequence-dependent setup times are presented as constraints. The goal of this study is to achieve a good solution for the problem in a reasonable computational time. To deal with it, several approximate algorithms are proposed, considering and idle-time based indicator to break ties with the same makespan. These proposed approximate methods are based on a memory mechanism, which works in a contrary way that the tabu search. In addition, they will include an iterative local search at each step of the sequence construction, repeating the most promising job combinations in future iterations. As a result, four heuristics have been implemented, and their performance has been tested on a benchmark composed of 1000 instances. A total of 17 heuristics have been compared.