On the multi-mode, multi-skill resource constrained project scheduling problem (MRCPSP-MS)

Abstract

In this paper we describe an extension of the Resource-Constrained Project Scheduling Problem (RCPSP). A literature review is presented to place our research in its proper context. The problem presented here belongs to the class of the optimization scheduling problems with multi-level (or multi-mode) activities. This means that the activities can be scheduled at different modes, each mode using a different resource level, implying different costs and durations. Each activity must be allocated exactly one unit of each required resource and the resource unit may be used at any of its specified levels. The processing time of an activity is given by the maximum of the durations that would result from a specific allocation of resources. The objective is to find the optimal solution that minimizes the overall project cost, while respecting a delivery date. A penalty is included for tardiness beyond the specified delivery date. We present a formal description of the problem and a mathematical model for it. We also introduce the implementation algorithm for the problem. The implementation was designed using the JAVA language, and the algorithm proposed is based on a branch and bound procedure, using breadth-first search (BFS) project network traversing, among some heuristic rules to filter large subsets of fruitless candidates relative to resource levels combinations.