New Exact Methods for Scheduling Multi Mode Multiple Resource Constrained Project Scheduling Problems

Abstract

Project scheduling problem (PSP) has enticed researchers since over a century. Enhancement in computational power enables the search for solutions to more complex problems progressively. However, the search for optimal solutions to problems spanning a few thousand or more variables poses phenomenal challenges even today. A plethora of approaches – such as, exact solution approaches, heuristic, metaheuristic, and others – have been proposed and developed by researchers. Amongst the families of such optimization problems, the resource constrained project scheduling problems (RCPSP) represent one of the well-studied problems in literature, especially during and since the World War-II.

A project consists of a set of activities partially ordered by precedence constraints. An activity has a given non-negative completion time, and can be performed in different modes. For each of its modes, the activity uses different types of resources, such as manpower, machinery, money etc., in either a different combination and/or different amounts. The resources considered are of, both, renewable and non-renewable nature. An activity is ready to be processed only when all its predecessor activities are completed and the numbers of units of the various resource types required by it, in the mode that it is to be performed, are free and can be allocated to it. Once started an activity is not interrupted and runs to its completion (non-preemptive). Scheduling is selecting the mode and committing resources to the realization of each activity at a defined time, while meeting the precedence and resource constraints. The aim is to assign modes and start times to activities so that the desired objective (makespan, flowtime, maximum tardiness, number of tardy jobs, etc.) is optimized.

Several exact solution approaches to the single mode RCPSP have been presented in literature. However, only a few have considered the possibility of an activity being performed in more than one modes (Multi-Mode or MM). We study the MM-RCPSP for an exact solution, deploying breadth-first and best-first approaches with pruning rules while retaining the optimality of the solution. The algorithms perform better than the best existing exact algorithm by Sprecher and Drexl (1998) on standard test problem sets of the PSPLIB. We adopt our breadth-first approach for implementation on a computecluster with SMP (Shared Memory Processors) architecture. The implementation shows promising improvement in time taken to solve the PSPLIB problem instances with the increase in number of processors deployed to solve the problems.