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

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

Yuval Cohen (Department of Industrial Engineering, Tel-Aviv Afeka College of Engineering, Open University of Israel, Tel-Aviv, Israel), Arik Sadeh (Technology Management Department, Holon Academic Institute of Technology, Holon, Israel) and Ofer Zwikael (Research School of Management, Marketing and International Business, College of Business and Economics, Australian National University, Canberra, ACT, Australia)
DOI: 10.4018/joris.2012100103


Non-delay schedules lack non-essential idle time intervals. Many heuristics for solving the resource-constrained project scheduling problem yield non-delay schedules. This paper presents a technique for finding the shortest non-delay schedule, which should be as good as the heuristics for this purpose. The authors combine branch-and-bound and dynamic programming approaches to yield a surprisingly simple algorithm. (The simplicity is reflected in the number of calculations and memory required.) Due to its simplicity, a project manager should be able to trace the algorithm’s stages and results without difficulty. This simplicity is a result of: (1) the number of stages equals the number of activities; (2) each stage uses only information from the previous stage, and the number of different schedules is typically limited; and (3) the proposed method becomes simpler the more it is constrained. A detailed example illustrates the technique, which is validated by comparisons to models from the literature.
Article Preview


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 rR has limited availability of Krt at any given time t. Each activity j has duration of dj and resource consumption of kjr. 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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing