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

Abstract

This doctoral thesis addresses the study and optimization of the block assemblyscheduling in shipbuilding using exact methods and metaheuristic algorithms.The scheduling process, which involves the assembly and erection of vessel hullblocks in the slipway, is modeled as a flexible job-shop problem with assemblies(FJSP-A). Despite being extensively studied in the literature, this problem becomeshighly complex within the shipbuilding context due to its large-scalenature and additional constraints such as limited buffer capacity, deadlines andthe integration of the block erection strategy.The thesis adopts a sequential approach to tackle this complexity. Initially,it proposes and compares a mixed-integer linear programming (MILP) modeland a constraint programming (CP) model for the general FJSP-A with limitedbuffer capacity and relaxed resources for makespan minimization. Giventhe superior performance demonstrated by the CP model, the thesis conductsa comparative analysis of exact methods and two metaheuristics, namely GeneticAlgorithm (GA) and Differential Evolution (DE) algorithm, using real casestudies. Experimental results illustrate that the CP model consistently outperformsthe MILP models, GA, and DE strategies, illustrating the performance ofthe developed metaheuristics. Subsequently, a CP-based decomposition strategyis developed to address the full problem by integrating block assembly anderection in the slipway. The proposed algorithm leverages heuristics and theadvantages of CP programming to provide high-quality solutions in complexscenarios, addressing both makespan minimization and resource optimization.Overall, the doctoral thesis aims to bridge the gap between academic researchand the industrial reality of shipbuilding by offering a suite of optimizationtools for high-level planning of shipbuilding construction processes.This contributes to enhancing the competitiveness of the shipbuilding industrythrough advanced planning and scheduling optimization techniques.