Study of th Block Assembly Scheduling Problem in Shipbuilding using Exact Methods and Metaheuristic Algorithms

Resumo

La presente tesis doctoral aborda el estudio y la optimización del problema de la programación y secuenciación del ensamblaje de bloques en construcción naval mediante métodos exactos y algoritmos metaheurísticos. Este problema de programación y secuenciación se modela como un problema de taller flexible con ensamblajes (FJSP-A) y, aunque ha sido ampliamente estudiado en la literatura, se vuelve muy complejo en el contexto de la construcción naval. Esto es debido a su gran escala y a las restricciones adicionales como la capacidad limitada delos buffers, los plazos de entrega y la integración de la estrategia de erección en grada. De manera secuencial, en primer lugar, la presente tesis propone y compara un modelo de programación lineal entera mixta (MILP) y un modelo de programación con restricciones (CP) para el FJSP-A general con buffers limitados y recursos relajados para la minimización del makespan. A continuación, dado el potencial mostrado por el modelo CP, se realiza un análisis comparativo de los métodos exactos y dos metaheurísticas, un Algoritmo Genético (GA) y un algoritmo de Evolución Diferencial (DE), empleando casos reales. Los resultados experimentales demuestran la superioridad de CP sobre el resto de métodos, al mismo tiempo que ilustra el rendimiento de las metaheurísticas propuestas. Finalmente, se desarrolla una estrategia de descomposición basada en CP para abordar el problema completo, integrando el ensamblaje de los bloques y su erección en grada. El algoritmo propuesto combina heurísticas y las ventajas de CP, proporcionando soluciones de alta calidad en escenarios muy complejos y abordando tanto la minimización del makespan como la optimización del uso de recursos. Con la presente tesis doctoral se pretende tender puentes entre la investigación académica y la realidad industrial del naval, ofreciendo un conjunto de herramientas de optimización disponibles para la planificación de alto nivel. Con ello se contribuye a mejorar la competitividad de la industria naval a través de técnicas avanzadas de planificación y optimización de la programación.