Finding the Shortest Non-Delay Schedule for a Resource-Constrained Project

Introduction

This paper suggests a new heuristic technique to solve the well known resource-constrained project scheduling problem (RCPSP). RCPSP is related to any business project having limited resources, a characteristic of most business projects. However, the proposed approach may suit (with minor modifications) other resource constrained scheduling environments. The quality of the solution compared to other heuristic solutions is guaranteed since the proposed technique finds the optimal non-delay schedule whereas most heuristics generate non-delay schedules. RCPSP is the problem of finding a schedule that minimizes the makespan of a project under resource and precedence constraints (Herroelen & Leus, 2005). RCPSPs are characterized by a set of one or more limited resource types and a set of activities to be scheduled. Each activity lasts a given duration and during its execution has a fixed consumption level for each type of resource. In resource-constrained scheduling, the aim is to find a feasible schedule with the shortest makespan. Although the RCPSP can be easily formulated, its solution complexity is known to be NP-hard (Blazewicz, 1983; Demeulemeester & Herroelen, 2002; Sprecher, 2002). This renders exact solution approaches impractical for large-scale projects. The motivation for seeking a heuristic procedure is therefore obvious. This paper provides a very simple and efficient heuristic technique with an approach that could be extended to other resource constrained scheduling environments.

Many excellent heuristics yield schedules that belong to a class known in the literature as “non-delay” schedules (Kolisch, 1996; Kolisch & Hartman, 1999; Demeulemeester & Herroelen, 2002). The non-delay approach is similar to the “early start” approach. According to this approach, any activity that can be started without postponing other activities should not be delayed. The non-delay/early start approach is very popular among project managers, since delaying activities may increase, in general, the risk of not completing the project on time.

The proposed scheduling technique finds the best schedule within the class of non-delay schedules. The technique utilizes both precedence and resource constraints to form a surprisingly efficient branch-and-bound procedure (both the efficiency and quality of the proposed technique are discussed towards the end of the paper). Moreover, the technique is flexible in that it can serve (with minor modifications) any number of resources and changes in their levels (as long as they are known in advance). In contrast with many other scheduling methods, the technique and its results can easily be traced and intuitively understood by a project manager. As such, the generated schedule could serve as a managerial tool for planning when there are changes in resource levels (as a result of initiative or unplanned events).

As explained above, the problem is finding a feasible schedule that minimizes the makespan of a project under resource and precedence constraints. The classical resource-constrained problem is formally described in Sprecher et al. (1995). This paper uses part of their notation as follows.

Consider a single project that is implemented over a finite number of periods with T being the upper bound on the project makespan and t=1,…,T being the a period index. The project consists of J activities. R is the set of renewable resource types and each resource type r∈R has limited availability of K_rt at any given time t. Each activity j has duration of d_j and resource consumption of k_jr. The activities are partially ordered by precedence constraints where Pj is the set of the immediate predecessors of activity j. The activities are numerically or alphabetically labeled, so that any predecessor of j has a smaller number than j.