Progressive hedging algorithm for the resource constrained project scheduling problem with modular production

Abstract

In modular shipbuilding, modules are used to lower construction costs and decrease lead times. Achieving these decreases in both costs and time requires making the right choices in material use and activity planning. Therefore, we introduce the Resource Constrained Project Scheduling Problem with Modular Production in which decisions are made for the inventory level of resources, activity selection and activity scheduling, in order to maximize profit minus inventory costs. Since these decisions have to be made before uncertain project arrival information is revealed, a scenario-tree based approach is used that optimizes over multiple scenarios simultaneously. An Integer Linear Programming formulation is introduced for this problem and a Progressive Hedging algorithm to find good solutions to this problem, along with two extensions to this algorithm. A computational study is performed, where the activity selection decisions are used to model choices in modular production and outsourcing. The basic PH algorithm outperforms using a commercial solver to find feasible solutions to the ILP model, in terms of both solution quality and computing time. However, the basic PH algorithm still has a hard time converging to an implementable solution, which makes the algorithm rely heavily on a repair step. The introduced extensions improve the convergence properties significantly, and can also be used to prioritize solution quality and/or computing time.