Exact Methods for the Preemptive Resource-Constrained Project Scheduling Problem

Abstract

A simple best-first tree search scheme with pruning rules to minimize the completion time (makespan) of the project is described. A project consists of a set of activities partially ordered by precedence constraints. An activity has a given non-negative duration and uses renewable resources such as manpower and machinery. The total number of available units of each resource is constant and specified in advance. A unit of resource cannot be shared by two activities. An activity is ready to be processed only when all its predecessor activities are completed and the numbers of units of the various resources required by it are free and can be allocated to it. Once started, an activity can be interrupted and rescheduled later on without any increase in remaining duration of that activity. Each such part of the activity can be called a segment of that activity. There are no set-up times. The objective is to assign start times to the activities or segment of activities so that the makespan is minimized.