dc.contributor.advisor | Fernández-Viagas Escudero, Víctor | es |
dc.creator | Navarro García, Belén | es |
dc.date.accessioned | 2021-10-18T18:03:33Z | |
dc.date.available | 2021-10-18T18:03:33Z | |
dc.date.issued | 2021 | |
dc.identifier.citation | Navarro García, B. (2021). Taller de flujo regular con capacidad de almacenamiento limitada: Heurísticas constructivas. (Trabajo Fin de Máster Inédito). Universidad de Sevilla, Sevilla. | |
dc.identifier.uri | https://hdl.handle.net/11441/126673 | |
dc.description.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. | es |
dc.description.abstract | 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). | es |
dc.format | application/pdf | es |
dc.language.iso | spa | es |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Taller de flujo regular con capacidad de almacenamiento limitada: Heurísticas constructivas | es |
dc.type | info:eu-repo/semantics/masterThesis | es |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Organización Industrial y Gestión de Empresas I | es |
dc.description.degree | Universidad de Sevilla. Máster en Organización Industrial y Gestión de Empresas | es |
dc.publication.endPage | 114 p. | es |