Matheuristic methods for solving the multi-calendar naval surface ship work period problem

Abstract

This thesis deals with the development of a binary integer programming (BIP) model and novel matheuristics to solve the naval surface ship work period problem (NSWPP) with multi-calendar activities and resources, multiple types of precedence relationships, and timing requirements. As this extended NSWPP is NP-hard, its computation time increases exponentially with the number of variables. The proposed solution approach reduces computation times by using a decomposition matheuristic method to quickly provide near-optimal solutions. The matheuristic method is a sequential multi-step optimization (MSO) using heuristic priority rules to classify the project activities into subgroups which are then optimally scheduled. Schemes are then devised to construct a final solution from the smaller optimal subgroup solutions. Extensive numerical experiments are then conducted using actual ship refit data. The MSO matheuristic is shown to obtain near optimal feasible solutions for large-scale instances of the problem in reasonable computation times.