An efficient MILP-based decomposition strategy for solving large-scale scheduling problems in the shipbuilding industry

Abstract

This work presents a novel hybrid and systematic MILP-based solution approach for the resolution of multi-stage scheduling problems arising in the shipbuilding industry. The manufacturing problem involves the processing of a large number of sub-blocks and blocks, which should be rigorously produced and assembled with the aim of finalizing a project on time. Firstly, this paper presents three alternative rigorous MILP mathematical formulations relied on a continuous-time representation for solving the problem under study. Although the objective values reported by these exact optimization approaches outperform the results found through other solution techniques proposed in the literature to solve the same problem instances, the main drawback of the MILP models is the high computation time. Therefore, this work proposes an algorithm for solving the mathematical models in a decomposable way with the goal of accelerating the resolution times. The applicability of our proposal is demonstrated by effectively coping with several instances of a real-world case study dealing with the construction of a ship for the development of marine resources. Computational results show that the proposed decomposition method is able to obtain high-quality solutions in few seconds of CPU time for all examples considered.