Heurísticas basadas en la distribución de cargas para el problema del taller de flujo de permutación distribuido heterogéneo

Abstract

[ES] El problema del taller de flujo de permutación distribuida heterogénea o distributed heterogeneous permutation flowshop problem (DHPFSP) es una generalización del problema de flujo de permutación (PFSP) en la que se consideran múltiples talleres con diferentes capacidades y tiempos de procesamiento, problema muy estudiado dentro de la Investigación Operativa. El DHPFSP resulta de especial relevancia en el entorno de producción actual donde la descentralización de la producción se convierte una ventaja competitiva al permitir una mayor flexibilidad y capacidad de respuesta a los cambios en la demanda o en la disminución de riesgos. En este trabajo se presenta el problema DHPFSP, y se proponen dos heurísticas constructivas para el problema, también se propone un algoritmo de búsqueda local. Los algoritmos constructivos y de búsqueda local propuestos son evaluados sobre dos conjuntos de datos de prueba que se diferencian en el nivel de heterogeneidad de los talleres. Durante la evaluación de los algoritmos se mide y compara tanto la calidad de las soluciones, como el tiempo de ejecución de los algoritmos como una medida del costo computacional. Se estudia cómo el número de fábricas, máquinas, trabajos y el nivel de heterogeneidad de los talleres afectan el desempeño de los algoritmos. Se analizan los resultados para dar conclusiones sobre los algoritmos propuestos y líneas de investigación futura.

[EN] The Distributed Heterogeneous Permutation Flowshop Problem (DHPFSP) is a generalization of the Permutation Flowshop Scheduling Problem (PFSP) in which multiple workshops with different capacities and processing times are considered a problem widely studied in the field of Operations Research. The DHPFSP is particularly relevant in today s production environment, where the decentralization of manufacturing has become a competitive advantage by enabling greater flexibility and responsiveness to changes in demand, as well as reducing risks.This work presents the DHPFSP and proposes two constructive heuristics to address the problem. Additionally, a local search algorithm is introduced. The proposed algorithms and the local search procedure are evaluated on two benchmark datasets that differ in the level of heterogeneity among the workshops. The evaluation measures and compares both the solution quality and the execution time of the algorithms as an indicator of computational cost.We study how the number of factories, machines, jobs, and the degree of workshop heterogeneity affect algorithm performance. The results are analyzed to draw conclusions about the proposed algorithms and to suggest future research directions.