Heuristic project scheduling: Validating the quality of a project schedule

Submitted by Mario Vanhoucke on Thu, 01/19/2012 - 16:41

Project scheduling is the act of constructing a timetable for each project activity, and differs in complexity due to the presence of renewable resources with limited availability. The construction of a resource feasible project schedule within the restrictions of a limited availability of renewable resources can be done to optimize a predefined scheduling objective (see “Resource constrained project scheduling: What is my scheduling objective?”). In this article, the differences between three possible schedules that can be constructed from project network data are described, as follows:

Infeasible schedule: A schedule with one or more resource conflicts.
Feasible schedule: A schedule without any resource conflict. This is also known as a heuristic schedule to denote that it does not contain resource conflicts but the scheduling objective can possibly be improved.
Optimal schedule: A schedule without any resource conflict and with the best possible scheduling objective value.

The difference between these three possible schedules is explained in detail for scheduling problems with a minimization and a maximization scheduling objective.

Figure 1: The gap between a feasible heuristic solution and an infeasible (lower or upper) bound

Figure 1 gives an overview of the three possible schedules and shows that a heuristic solution found by a software tool is a resource feasible solution without any resource conflict but not necessarily the best possible schedule that can be found. The optimal schedule is a feasible schedule with the best possible scheduling objective (the lower (higher), the better in case of a minimization (maximization) objective). Better schedules cannot be found unless resource conflicts are added which then results in infeasible project schedules. Bounds are calculated on resource infeasible schedules to have an idea about the range of possible scheduling objectives for the project. Both the calculation of bounds and feasible schedules can be used to define the gap, as follows:

GAP

the difference between the scheduling objective

of a heuristic (= feasible) schedule

and the value of a (lower or upper) bound

Since both the generation of heuristic schedules and the calculation of bounds can be done by simple and fast algorithms, the gap gives an indication of the room for improvement one can make by starting with a feasible schedule and by making small changes and adaptations to the schedule to improve the value of the scheduling objective.

Minimization objective

The most well-known scheduling minimization objective is the minimization of the total duration of a project baseline schedule, as described in “What is my scheduling objective? Minimizing the project lead time”.

Infeasible schedules can be easily generated using simple and straightforward lower bound calculations as shown in “What is my scheduling objective? Lower bounds on the total project duration”. Feasible heuristic schedules can be constructed by quick and easy methods such as priority rule based scheduling techniques, illustrated in “Optimizing regular scheduling objectives: Priority rule based scheduling”. Optimal schedules are harder to find due to the inherent complexity of resource-constrained project scheduling and are often the subject of research at academic institutions.

The top left corner in figure 2 displays a project network with 11 activities and finish-start precedence relations. Each number above the node denotes the estimated duration of the activity while the number below the node is used to refer to the resource demand. The maximum availability of the resource is equal to 5 units (e.g. people).

The optimal schedule is given by the schedule on the top right corner of the picture. Its optimal duration of 17 days lies in between the feasible schedule found by the Greatest Cumulative Resource Work Content (GRWC) priority rule and the best lower bound calculated by the resource based lower bound (see “What is my scheduling objective? Lower bounds on the total project duration”). The heuristic schedule has a total duration of 19 days displayed at the bottom right corner of the picture. The GCRWC priority rule results in the activity list [1,2,3,6,9,4,7,5,8,10,11] that can be transformed in the heuristic schedule using a serial generation scheme as discussed in “Optimizing regular scheduling objectives: Priority rule based scheduling”. The gap between the heuristic schedule and the lower bound is equal to 3 days.

Figure 2. An example project network with its optimal schedule and the gap between a feasible schedule and the resource based lower bound

It should be noted that this general approach is also applicable to scheduling objectives other than the time minimization. While the time minimization is the most dominant scheduling objective, other minimization objectives for which no lower bounds are available in PMKC are given in “What is my scheduling objective? Minimizing the resource idle time” and “What is my scheduling objective? Leveling the use of resources”. Moreover, while the heuristic solutions found by priority rules (“Optimizing regular scheduling objectives: Priority rule based scheduling”) are restricted to regular scheduling objectives, other heuristic techniques such as the Burgess and Killebrew algorithm can be used to construct feasible schedules with non-regular scheduling objectives. This algorithm will not be discussed at PM Knowledge Center. The difference between regular and non-regular scheduling objectives is explained in “Resource constrained project scheduling: Regular and non-regular scheduling objectives”.

Maximization objective

When the scheduling objective is a value to maximize instead of to minimize, the gap calculation is similar but opposite to the approach for a minimization objective. The heuristic schedule is now a lower bound since improvement from a heuristic feasible schedule to an optimal schedule will lead to an increase (i.e. improvement) of the scheduling objective. Likewise, the calculation of a bound using an infeasible schedule is now an upper bound since it ignores resource constraints and allows resource conflicts. A typical and well-known scheduling maximization objective is the net present value optimization objective as discussed in “What is my scheduling objective? Maximizing the net present value”.