Scheduling Schemes and Heuristics for Leveling

Figure 1. An unleveled schedule (adapted from Peter Brucker and Sigrid Knust, Complex Scheduling, 2nd ed,
Springer-Verlag, 2012, Figure 3.2, p. 120)

The schedule in the above figure is not resource-feasible. Resources are over allocated, and the schedule needs to be leveled. Assuming you want to minimize project duration, how would you level it? If you do not know how to level a schedule by hand, you are at a disadvantage. If you use Project to level the schedule, but don’t know how the software resolves the over allocations, you are in double jeopardy! How will you explain the increase in project duration that leveling may cause? How will you explain why one task is delayed, but not another?

Unfortunately, the leveling algorithms used in scheduling software such as Project are likely to be proprietary. They will not be documented in some knowledge base. To the user, they will appear to be a black box. However, the resource-constrained project scheduling problem (RCPSP) has been studied for decades. Introductions to the topic can be found in textbooks such as Erik Larson and Clifford Gray’s Project Management: The Managerial Process (7^th ed, McGraw-Hill, 2018). The example above and the topics below are covered in Peter Brucker and Sigrid Knust’s Complex Scheduling (2^nd ed, Springer-Verlag, 2012, pp. 119++). Knowledge of the RCPSP problem sets the framework for discussing resource leveling in Project.

Below, I will describe the leveling process. Specifically, I will discuss classification of resource-feasible schedules, schedule generation schemes, and leveling heuristics. I will illustrate these topics in Project. While this will help us understand how to level a schedule, it will not help explain the inner workings of leveling in Project, which remain a black box. It will; however, give us a basis on which to judge whether Project is producing a reasonable result.

Resource-Feasible Schedule Types

The following figure shows six possible levelings of the schedule shown in Figure 1. The top left schedule is feasible in that it conforms to logical precedence constraints and resource constraints. However, tasks 3 and 4 are unnecessarily delayed, which extends the project duration. Removing the delays yields a semi-active schedule (top right). No tasks can be shifted left locally. A local left shift moves a task a successive number of time periods to the left without creating an over allocation. That said, task 3 could be shifted left globally by more than one time period (to start in time period 3 instead of 6). This global shift yields an active schedule (middle left), in which no task can be shifted left locally or globally. The middle right and two bottom schedules are non-delay schedules. In addition to being active schedules, no resource in these is left idle when it could be assigned to an activity. Tasks 1 and 4 are started in the first time-period since there is resource availability.

Figure 2. Feasible, semi-active, active and non-delay schedules.

For the example schedule, there are four active schedules: the five-day active schedule and three variants of the six-day, non-delayed schedule. The non-delay schedules form a subset of active schedules. The five-day active schedule is the optimal schedule in terms of project duration. The optimal schedule will be a member of the active schedule set, but it might not be a member of the non-delay set, as is the case in this example.

Why is this classification important?  Project may not produce an optimal leveling. That is, Project may generate a schedule that is not active. Or, if it is active, it may not be optimal in regards to project duration. A Project user may be unaware that a leveling is sub-optimal. To understand this further, we need to know more about the leveling process.

Scheduling Schemes and Heuristics

Finding an optimal solution to the RCPSP problem through exhaustive enumeration becomes intractable as schedules become complicated.  To get around this issue, scheduling software uses schedule generation schemes (algorithms) and heuristic methods (prioritization) to level schedules. A serial generation scheme will produce an active schedule, and a parallel scheme will produce a non-delay schedule. Both schemes are used in conjunction with leveling heuristics. Heuristics are prioritization rules used to determine which tasks are allocated resources and which tasks are delayed due to insufficient resource availability. While these methods do not guarantee optimal results, they provide feasible solutions efficiently.

The serial and parallel schemes both start with a list of tasks sorted in topological order according to logical precedence relationships. Secondarily, the task list is sorted according to some heuristic (priority rule). Some commonly used heuristics are listed in the table below, although a full list of effective heuristics is more extensive than what is presented here.

In the serial generation scheme, tasks are slotted into the schedule in prioritized order, one at a time. Each task is shifted right until there are no precedence or resource conflicts with any previously scheduled task. In the parallel scheme, tasks are scheduled time period by time period. In each time period, tasks are scheduled in prioritized order assuming logical and resource constraints are satisfied. Otherwise, they are delayed.

Let’s look at two examples. Using a specific scheduling scheme and heuristic, the schedule will be leveled manually, step by step. Then, the equivalent leveled schedule will be generated in Project.

Serial Generation Scheme with ID Heuristic

The task list in Figure 1 represents one possible topological ordering of the tasks according to logical precedence. The task ordering is (1,2,3,4,5) and it coincides with the task ID in Project. The following figure shows the steps involved in leveling the schedule using a serial scheme and ID heuristic. Tasks 1, 2, and 3 can be scheduled in order. Task 4 must be shifted right by two time periods to avoid over allocation of resources in time period 2. Task 5 is scheduled last, following task 4. The result is the five-day optimal active schedule shown in Figure 2c above.

Figure 3. Sequence of steps in serial leveling with ID heuristic.

This leveling can be obtained in Project by selecting the ID only leveling order in the Leveling Options dialog as shown in Figure 4. Note that this does not mean that Project used a serial scheduling scheme to level the schedule. We can only say that the manual leveling matched the ID only leveling coincidentally.

Figure 4. Project ID only leveling order.

Alternatively, the leveling can be obtained by adjusting the task Priority field and selecting the Priority Standard leveling order. Tasks with higher priority are allocated resources before tasks with lower priority. The task priorities are set to reflect the desired task ordering. There are multiple topological orderings based on the defined logical constraints. If an alternative topological ordering (4,5,1,2,3) is used, one of the 6-day variants of the active non-delay schedule is obtained. The steps are shown in Figure 5. Tasks 4, 5, and 1 are scheduled in order. Task 2 must be shifted right by two time periods in order not to cause over allocation in periods 2 and 3. Task 3 is scheduled to follow task 2.

Figure 5. Steps in serial leveling using an alternative topological task ordering.

The tasks in Figure 5 were physically moved in the task list to reflect the alternate topological ordering. The ID Only leveling order could be applied, as above. However, it is easier to adjust the task Priority field and select the Priority Standard leveling order. In Figure 6, the task priorities were set to ensure that resources were allocated to tasks according to the (4,5,1,2,3) topological ordering.

Figure 6. Priority Standard leveling order based on alternate topological ordering of tasks

Again, this does not mean that the Priority Standard leveling order in Project utilized a serial scheduling scheme to level the schedule. However, it is clear that we can use task priorities and the Priority Standard leveling order to mimic the results obtained manually using a serial scheme and ID heuristic. Table 2 maps topological orderings to active schedules shown in Figure 2.

Table 2. Mapping of active schedules to topological ordering used in serial schedule scheme.

Parallel Generation Scheme with Minimum Slack Heuristic

The manual steps involved in leveling the schedule using a parallel scheme and minimum slack heuristic are shown in Figure 7. In time period 1, tasks 1 and 4 are scheduled because sufficient resources are available. In time period 2, task 4 is in progress. Choosing not to pre-empt task 4, task 2 must be delayed. Note that this delays a critical task and subsequently extends the project duration. In time period 3, tasks 2 and 5 could be scheduled. Task 2 is scheduled since it is critical, and task 5 is delayed. In time period 4, tasks 3 and 5 could be scheduled. Task 3 is critical and is scheduled. Task 5 is delayed until task 3 completes. This yields the 6-day non-delay schedule shown in Figure 2d (middle right).

Figure 7. Manual leveling, parallel scheme with minimum slack heuristic.

This leveling can be attained in Project by selecting the Standard leveling order in the Leveling Options dialog as shown in Figure 8. As above, this does not mean that the Standard leveling order in Project utilizes a parallel scheduling scheme. However, there are two ways in which to obtain this non-delay schedule in Project. The first is to use the Standard leveling order. The second is to use the Priority Standard leveling order and either of the two topological orderings shown in Table 2.

Figure 8. Standard leveling order.

Other Leveling Options

Project’s leveling capabilities are more sophisticated than what has been discussed here. Splitting tasks or adjusting task resource loads have not been considered. Both are viable leveling techniques. As an aside, if task splitting is allowed, a 5-day optimal schedule is generated. Task 4 is pre-empted by task 2. Either the ID only or Standard leveling order can be used. Figure 9 shows the result.

Figure 9. Leveling with task splitting allowed.

Discussion

For the example schedule, there are four active schedule leveling solutions:  one five-day optimal schedule relative to minimizing schedule duration and three variants of a six-day non-delay schedule. All four could be derived using a serial scheduling scheme with varying topological orderings of tasks according to logical precedence. The optimal schedule was derived manually using a serial scheme with task ID heuristic. One of the non-delay schedules was derived manually using a parallel scheme and the minimum slack heuristic.

Coincidentally, in Project, the optimal schedule was obtained using the task ID only leveling order. One of the non-delay schedules was obtained using the Standard leveling order. Further, it was shown that setting task priorities according to various topological precedence orderings and using the Priority Standard leveling order could generate the four active schedules. However, Project’s leveling algorithms remain a black box. Without intimate knowledge of Project’s leveling process, all we can say is that coincidentally Project’s leveling solutions matched solutions that were manually derived. We cannot explain how Project arrived at these solutions.

In this simple example, Project’s solutions aligned with our manually derived solutions. In more complicated schedules, Project’s solutions may be sub-optimal. Depending upon which leveling order is selected, Project delivers one leveling solution.  It should be noted; however, that there could be hundreds of viable active schedule solutions. Without independent assessment, it may not be possible to tell how well Project leveled.

What are your thoughts? I’d love to hear about your experiences with leveling in Project in the comments below.