OPTIMIZATION OF THE NAVAL SURFACE SHIP RESOURCE-CONSTRAINED PROJECT SCHEDULING PROBLEM

Abstract

The research presented in this thesis focuses on proposing effective methodologies, formulations, and heuristics for scheduling and rescheduling resource-constrained project scheduling problems that are specific to naval surface ship work periods or similar maintenance projects. The network topology for these work period projects is divided into precedence-independent work orders that have precedence-dependent operations within themselves. Mixed-integer linear programming (MILP) models are developed for the initial scheduling and for the rescheduling problem. In initial scheduling, the objective is to front-load work based on priority and duration, to account for the high degree of uncertainty and scope growth that is common in these work periods. In rescheduling, the goal shifts to minimizing schedule deviation-days while incorporating urgent scope growth. Experimentation results, discussions, and insights are provided for initial and rescheduling MILP models, and for combining appropriate heuristic methods to quickly produce good feasible solutions when optimal solution times are not acceptable.