MODELLING AND SOLVING THE MULTI-CALENDAR NAVAL SURFACE SHIP WORK PERIOD PROBLEM UNDER ACTIVITY RELATIONSHIP CONSTRAINTS

Abstract

This thesis deals with modelling and solving the multi-calendar extensions of the naval surface ship work period problem (NSWPP). NSWPP is a variant of the resource constrained project scheduling problem (RCPSP) with its own specific network characteristics and constraints including limited work periods, activities of varying priority, multi-calendars activities and resources, precedence relationships, and time constraints. A binary integer programming model focusing on front-loading activities based on priority and duration is developed. The NSWPP is NP-hard causing its solution time to grow exponentially with the number of activities and resources. To shorten computation time, the Serial Schedule Generation Scheme heuristic is modified to adapt to the additional features of the multi-calendar NSWPP. The modified serial SGS reduces computational time from over 40 minutes to around 10 minutes for a large size instance of the problem. Experiments are carried out using data from real large-scale naval refit operations.