For the project manager, the objective of resource leveling is to minimize the length of the resource-feasible schedule. For the computer scientist, the objective is to write code that will find a resource-feasible schedule in a reasonably short amount of time. The resource-constrained project scheduling problem (RCPSP) is NP-hard, which means that finding an optimal solution may take considerable time to compute. To solve the problem quickly, schedule generation schemes and heuristic algorithms are used. The trade-off is that these algorithms, while finding a solution to the problem in a short amount of time, do not guarantee an optimal solution in terms of schedule length. So, the project manager is left wondering how optimal a leveling really is.


Some levelings…

Let’s start with an example. The schedule shown below is 16 days long, and there are three resources, each with a capacity of five units per day. All three resources exceed this capacity within the span of the schedule. To be resource-feasible, the schedule needs to be leveled.

Figure 1. Unleveled 16-day schedule.


Project’s standard leveling order yields a 29-day schedule (Figure 2). The ID only leveling order yields a 32-day schedule (Figure 3). Preemption (task splitting) and adjusting assignment levels were not considered for this example.

Figure 2. Project standard leveling order 29-day schedule.


Figure 3. Project ID only leveling order 32-day schedule.


Both of these leveled schedules have unnecessary delays. In the standard leveling, Task 4 could be started three days earlier. In the ID only leveling, Task 9 could be started 13 days earlier. While the task delays do not change the overall lengths of the leveled schedules, the delays indicate that these levelings are not members of the set of active resource-feasible schedules for this example. Active schedules are a subset of feasible schedules in which no task can be started earlier, either locally or globally, without causing a delay in some other task in the schedule.


But, are the levelings optimal?

What the project manager using Project does not see is that there are three unique active leveled schedules that yield a 26-day optimal result. Here is one of them.

Figure 4. One of three 26-day optimal leveled schedules.


The following chart shows the distribution of active resource-feasible schedule lengths for this particular example, along with the median length and the cumulative distribution. The distribution was generated using a schedule simulation technique similar to the one described in a prior article. The minimum value of the distribution is construed to be the optimal active resource-feasible schedule length. Project’s standard and ID only leveling lengths are superimposed on the chart for comparison, even though neither schedule is a member of active schedule set.

Figure 5. Distribution of active resource-feasible schedule lengths.


With knowledge of the underlying distribution of active resource-feasible schedule lengths, the project manager can assess the optimality of the standard and ID only leveling solutions that Project provides for this particular schedule. Relative to the unleveled schedule length, the optimal resource-feasible scheduled length is 163% longer, the standard leveling length is 181% longer, and the ID only leveling length is 200% longer. Relative to the optimal resource-feasible schedule length, the standard leveling length is 112% longer and the ID only leveling length is 123% longer.


What do you think?

How concerned are you about the optimality of resource-feasible schedules?  How do you assess whether a leveling is optimal?  Does not being able to assess optimality discourage you from using resource leveling? Please share your thoughts in the comments below.