Matheuristic Optimization Approaches for Large Scale Resource Constrained Scheduling Problems in Refit Operations

Abstract

This thesis will discuss the development of matheuristic methods for scheduling the refit activities in the naval surface ship work period problem (NSWPP). The NSWPP is a variant of the classical resource-constrained project scheduling problem (RCPSP) with specific network structure and constraints. The NSWPP is a non-deterministic polynomial-time hard problem whose solution becomes computationally demanding as the problem size increases. Therefore, a matheuristic method called multi-step optimization (MSO) is developed in this paper, which combines heuristics and mixed-integer linear programming (MILP) to schedule the NSWPP activities efficiently. MSO uses heuristic priority rules to decompose the activities from the main project into subgroups. The subgroups are then iteratively optimized using a time-indexed discrete-time MILP formulation. The results from the comparative tests conducted show that MSO is computationally efficient and produces near-optimal solutions. Also, a comparative study of the solutions generated by MSO proves that the proposed method outperforms state-of-the-art heuristics.