Comparison of Exact Methods and Metaheuristics to Solve the Flexible Job-Shop Assembly Problem in Frigate Shipbuilding

Abstract

[Abstract] Frigate shipbuilding requires meticulous scheduling due to unique construction processes, involving numerous tasks and limited resources. Current strategies, particularly those involving block erection on slipways, face bottlenecks in hull assembly due to resource constraints. This study addresses these challenges through an extended formulation of the Flexible Job-Shop Scheduling Problem with Assemblies (FJSP-A), incorporating limited workshop capacity and a fixed block-erection strategy. We evaluate the performance of exact and heuristic solution methods, comparing a strengthened constraint programming (CP) model, a holistic mixed-integer linear programming (MILP) formulation, a MILP-based decomposition approach from the literature, and two adapted metaheuristics, a genetic algorithm (GA) and a differential evolution (DE) strategy. While CP consistently delivers the best solutions across objectives, large lower-bound gaps remain in the most complex instances. Metaheuristics, particularly the GA with a sequencing-focused encoding, provide competitive alternatives when faster approximate solutions are required or when problem size or available budget limits the use of exact methods. The results offer practical guidance for selecting optimisation strategies in shipbuilding environments and highlight research avenues for integrating enhanced heuristics or multi-objective approaches into resource-constrained assembly scheduling.