Taller de flujo regular con capacidad de almacenamiento limitada: Heurísticas constructivas

Abstract

Este Trabajo Fin de Máster aborda un problema de programación de la producción en un taller de flujo regular, conocido en inglés como flow shop. Se presenta como restricción la permutación de trabajos, y adicionalmente, se consideran limitaciones de almacenamiento entre las máquinas que componen el taller (buffers limitados). Se tiene como objetivo minimizar el tiempo de finalización máximo de los trabajos (makespan), alcanzando una solución de calidad para el problema en un tiempo de cálculo razonable. Los métodos aproximados propuestos para la resolución del problema de secuenciación son heurísticas constructivas y de mejora En concreto, se proponen algoritmos heurísticos basados en memoria, en donde se prioriza en caso de empate las secuencias con menor tiempo ocioso entre el procesado de los trabajos y menor tiempo de bloqueo de las máquinas. Algunos de los métodos incluyen una búsqueda local iterativa en cada paso de construcción de la secuencia, repitiendo las combinaciones de trabajos más prometedoras en futuras iteraciones (al contrario que la búsqueda tabú). Se desarrollan 6 heurísticas constructivas distintas, a las cuales también se les añade una búsqueda local reducida de inserción para ampliar la calidad de la solución, dando lugar a 6 heurísticas de mejora. Estos algoritmos se evalúan para distintos parámetros de entrada, obteniendo un total de 60 variantes. Adicionalmente, han sido reimplementadas 24 heurísticas propuestas en la literatura para resolver el problema abordado o similares, como es el problema de secuenciación de flowshop con bloqueo (cuando la capacidad de los buffers entre las máquinas es cero). La evaluación computacional llevada a cabo para las conocidas instancias de referencia de Taillard, demuestra la eficiencia de las 84 heurísticas comparadas, consiguiendo, por lo general, mejores resultados las heurísticas propuestas que las existentes en la literatura.

This thesis addresses the permutation flow shop scheduling problem (PFSP) with intermediate limited buffers located between two consecutive machines. The goal of this study is to minimize the maximum completion time (i.e., makespan). To deal with it, several approximate algorithms are proposed to achieve a good solution for the problem in a reasonable computational time. These proposed approximate methods are constructive heuristics that consider the influence of the idle-time and the blocking-time to break ties with the same makespan. Some of them are based on a memory mechanism, which works in a contrary way that the tabu search, so they include an iterative local search at each step of the sequence construction, repeating the most promising job combinations in future iterations. As a result, six heuristics are developed, to which a reduced local search by insertion is also added to increase the quality of the solution, resulting in 6 enhancement heuristics. Their performance has been tested on the well-known Taillard's benchmark instances. Computational simulations and comparisons are provided for a total of 84 heuristics. It is shown that the proposed algorithms are capable to generate better results than the state-of-the-art algorithms in terms of solution quality and efficiency. In addition, the algorithms are competitive with the algorithms proposed in the literature for solving the blocking flow shop scheduling problem (i.e., LBPFSP with zero-capacity buffers).