Heurísticas para el problema de taller de flujo de permutación distribuido heterogénea

Abstract

[ES] En este trabajo se estudia el problema de permutación distribuida heterogénea o DHPFSP (distributed heterogeneous permutation flowshop scheduling problem). Este problema pertenece al ámbito de la secuenciación de la producción, rama de la Investigación Operativa. Esta configuración de la producción es especialmente relevante en la economía actual, en la que una empresa puede disponer de varios centros de producción. Se caracteriza el DHPFSP para posteriormente proponer cinco heurísticas, cuyo rendimiento se analiza estadísticamente mediante un ANOVA, teniendo en cuenta distintos factores como el número de trabajos, y las interacciones de primer orden. Sobre todas las heurísticas se aplica una búsqueda local con el fin de mejorar la calidad de la solución, y se mide el rendimiento de la misma. Adicionalmente, se realiza un estudio sobre el coste computacional de las distintas heurísticas, y se analiza cómo cambia el valor esperado de la función objetivo según lo heterogéneo que sea la instancia del problema. Finalmente se sugiere la mejor heurística para resolver el problema teniendo en cuenta todos los factores estudiados.

[EN] In this paper we study the distributed heterogeneous permutation flowshop scheduling problem (DHPFSP). This problem belongs to the field of production sequencing, a branch of Operations Research. This produc- tion configuration is particularly relevant in today’s economy, where a company may have several production centers. The DHPFSP is characterized and then five heuristics are proposed, whose performance is statistically analyzed by means of an ANOVA, taking into account different factors such as the number of jobs, and first- order interactions. On all heuristics a local search is applied in order to improve the quality of the solution, and the performance of the solution is measured. Additionally, a study on the computational cost of the different heuristics is performed, and it is analyzed how the expected value of the objective function changes according to the heterogeneity of the problem instance. Finally, we suggest the best heuristic to solve the problem taking into account all the factors studied.