METAHEURÍSTICA PARA ABORDAR EL PROBLEMA PROP

Abstract

En este Trabajo de Fin de Grado se aborda el problema PROP (Parallel Row Ordering Problem) de diseño de layouts por filas paralelas en una planta, donde se deben asignar y ordenar instalaciones de tamaños heterogéneos en dos filas con instalaciones prefijadas a cada fila, minimizando el coste de manipulación derivado de los flujos entre instalaciones y de sus distancias (calculadas a partir de los centros). Se trata de un problema NP-difícil, por lo que se recurre a métodos heurísticos eficientes orientados a obtener soluciones de alta calidad en tiempos contenidos. Se propone una metodología basada en GRASP (Greedy Randomized Adaptive Search Procedure). En la fase constructiva se desarrollan varias familias de heurísticas: (i) ordenación global por puntuación (que integra flujos y tamaños), (ii) enfoques greedy-random con lista restringida de candidatos (RCL) controlada por un parámetro de aleatoriedad ¿, y (iii) estrategias random-greedy basadas en muestreo y mejor inserción. La fase de mejora aplica movimientos intra-fila, en particular swap e insertion, en variantes first y best improvement, además de combinaciones secuenciales. Para sostener la eficiencia, la evaluación pasa de un esquema tradicional a uno vectorizado apoyado en operaciones matriciales, permitiendo tanto el cálculo completo como el parcial, además de actualizaciones incrementales por fila. El plan experimental estandariza los formatos de instancia y el protocolo de repeticiones y semillas, y evalúa las configuraciones en términos de coste, tiempo, desviación relativa y número de mejores resultados por instancia. Los resultados indican que las configuraciones más competitivas emplean un constructivo greedy-random, que restringe los candidatos mediante una lista restringida (RCL) y elige aleatoriamente dentro de ella, seguido de una búsqueda local secuencial, por su mejor equilibrio entre calidad y tiempo frente a constructivos puramente aleatorios o de otro tipo. El trabajo entrega, además, artefactos reproducibles que facilitan el análisis comparativo. Por último, se compara la metodología propuesta con el estado del arte. Las mejores configuraciones igualan los valores de referencia en buena parte de las instancias, de forma especialmente consistente en la familia AV25, aunque no los superan de manera sistemática y quedan por encima de los mejores valores reportados en varias instancias de la familia P24.