The objective of resource leveling is to minimize schedule length while honoring precedence relationships and resource constraints. If we know what a schedule’s optimal leveled length is, we can compare that to leveling results that Project provides. In a prior article, we assessed the optimality of Project’s leveling relative to one particular schedule. The next step is to explore the optimality of Project’s leveling across multiple schedules.
To do this, we need a sample of schedules to study. The Project Scheduling Problem Library (PSPLIB) is a benchmark against which the performance of leveling algorithms has been gauged for over two decades. In particular, we will use the j30 set for which an optimal leveling has been determined for each of the 480 schedules in the set. From the schedule data in this set, we can extract two observations for each schedule, the unleveled schedule length and the optimal leveled schedule length.
By loading the schedules into Microsoft Project Pro 2019 and leveling them using the standard and the ID only leveling orders, we can add Project’s standard and ID only leveled schedule lengths to the observations. A computer program was written to automate the loading and leveling of the schedules. Project’s leveling was done without task splitting or adjustment of resource assignments.
The resulting dataset contains four lengths for each schedule in the sample: unleveled, optimal leveled, Project standard leveled and Project ID only leveled.
Leveled schedule lengths
To show the effect of leveling on schedule length, the leveled scheduled lengths were scaled relative to the unleveled schedule length. As can be seen in the Figure 1 boxplots, the lower bound of leveled schedule lengths is the unleveled scheduled length. Of the 480 schedules in the sample, 216 have an optimal leveled schedule length equal to their unleveled schedule length. Due to the factorial design of the PSPLIB sample, one-quarter (120) of the sample schedules did not need to be leveled. That is, they had no resource over allocations. The remaining 96 schedules could be leveled within available slack.
The boxplots show that the leveled scheduled lengths are positively skewed. There are instances where the optimal leveled schedule length is more than twice the length of the unleveled schedule in this sample. The median increase in schedule length for the optimal leveled schedules is 103%. The median increases in length for the standard and ID only levelings are 112% and 116%, respectively. The distributions of standard and ID only leveling lengths differ significantly from the optimal distribution. And, the distributions of standard and ID only levelings are different from each other.
Figure 1. Optimal, standard and ID only leveled schedule lengths relative to unleveled schedule length.
Leveled schedule lengths relative to the optimal leveling
To show how Project’s leveling varied from the optimal, the standard and ID only lengths were scaled to the optimal leveled schedule length. The boxplots in Figure 2 show that relative to the optimal leveled schedule length, the median increases in length for the standard and ID only levelings are 105% and 109%, respectively. Scaled relative to the optimal schedule length, the distribution of standard leveling lengths is different from the ID only leveling lengths.
Figure 2. Standard and ID only leveled schedule lengths relative to optimal leveled schedule length.
Resource utilization and optimal leveled schedule length
Resource utilization is the ratio of a resource’s total assigned work units to total available work units in the unleveled schedule. The number of total available work units is the product of the resource capacity per time period and schedule length. Utilization is averaged across all resources in the schedule. As shown in the figure below, there is a positive correlation between resource utilization and scaled optimal leveled schedule length in this sample of schedules.
Figure 3. Relation between average resource utilization and scaled optimal schedule length in the PSPLIB j30 set.
Discussion
The boxplots above compare Project’s levelings of a sample of schedules to the published optimal levelings for those schedules. The distributions of Project’s standard and ID only levelings are different from the distribution of optimal levelings. And, the distributions of standard and ID only levelings are different from each other. While we can see the differences, it is difficult to explain them without explicit knowledge of what algorithms or heuristics Project uses to level schedules.
Resource utilization and optimal leveled schedule length are positively correlated. But, resource utilization may not be the sole predictor of leveled schedule length or a very good one. Other factors such as network topology might influence the leveling performance. More study is needed in this area.
Distributions of leveled schedule lengths are positively skewed, which means we should not be surprised if Project levels a schedule to two or three times its unleveled length. The factors that contribute to this skewing need to be determined.
Schedule samples need to be tailored to specific companies or industries. We cannot generalize leveling behavior based on a single, artificially generated sample. The parameters that are used to generate sample schedules need to be based upon values observed in the field.
See the PSPLIB site for more information about the j30 schedule set and related research.
What do you think?
Were you surprised by Project’s leveling performance? Is finding an optimal leveling useful? What parameters help you describe the resource utilization or network topology of your project schedules? How do these parameters affect your leveling?
Please share your thoughts in the comments below.
Acknowledgement
I would like to thank Eric Uyttewaal for commenting on a draft of this article.
MR ERIC UYTTEWAAL
Hi Robin, You did a lot of work for this article: Great job (but I already knew that)! What I did not know before I read your draft article is how much choosing a suboptimal leveling method (‘ID Only’ instead of ‘Standard’) adds to the length of the schedule: 109/105*100%=3.8%. That is after we have lost already 5% to Microsoft Project’s fairly weak scheduling algorithm of ‘Standard’ relative to the optimal schedule (leveled-by-hand through puzzling).
In further research, it would be fun to also quantify what other options like ‘Leveling can adjust individual assignments on a task’ and ‘Leveling can create splits in remaining work’ can perhaps improve these results. Since these options increase the number of versions of the schedule that MS Project considers, I expect that they might give us gains: How close can MS Project’s leveling get to the Optimal Schedule?
Robin Nicklas
Eric,
Comparing standard leveling order to ID only leveling order and comparing both to optimal leveling is a start. I agree that a logical next step would be to explore the leveling options of task splitting and assignment adjustment.
One of the reasons why I chose to explore Project’s leveling performance is that I’ve noticed, for some schedules, the leveled schedule length is shorter, perhaps optimal, in prior versions of Project, but not in MS Project Pro 2019. I have no personal insight as to what changed between versions.
The optimal leveled schedules in PSPLIB are not the result of manual puzzling. The optimal schedules have been identified through the use of exhaustive branch and bound search techniques, or more recently through the use of genetic or simulated annealing algorithms.
The open question is what leveling algorithms and heuristic techniques is Project using now?
-Robin
John Owen
Most scheduling tools use simple rules to determine the order in which tasks are assigned resources during resource leveling like ID, Total Slack etc.. These are never going to reliably produce optimal solutions. One trick I used in the past is to repeat the leveling process many times, assigning new random numbers to the priority field for all tasks in each cycle and use Priority for leveling order.. Save the sequence of numbers that gave the best results (earliest overall finish) and if you perform enough cycles you’ll eventually get the optimal solution. It is however very time consuming and there is no way to determine if you truly have the optimal solution. Basically a similar solution to the infinite number of monkeys with typewriters!
Trevor Rabey
Robin,
I would like to make a comment (take issue with, actually) about two aspects of the article, the objective of resource leveling, and the idea of “optimal”. Here goes.
The objective of resource leveling is to delay tasks (just enough) in order to remove resource over-allocation. There may well be numerous solutions which achieve this objective, and they all are going to be a big improvement because they at least take us from a plan which is not even feasible to one that is.
Whether any of the solutions is “optimal” depends on what our definition of “optimal” is to start with. For most practical purposes, I would suggest that any solution is probably optimal enough. I don’t expect MSP to find the absolutely most shortest overall duration (if that’s what optimal means), but I am very pleased with what it does do. It’s not claimed to be an optimiser, but it is a feasibiliser.
Trevor Rabey
Robin,
in order to keep an overall duration to a minimum, or at least as tight as possible, I like to sort my tasks by total slack, and then make a list of priorities (in Excel) from 999 down and paste in that list in the priorities column. That is, the tasks with the least total slack get the highest priority, then level by priority. That has to be close to “optimal”.
Robin Nicklas
Trevor,
Project’s leveling produces resource-feasible schedules. Like you do, I consider this an essential requirement. And, I agree with you that we should not expect Project to produce optimally leveled schedules in terms of schedule length. That is just too hard of a problem.
Further, the likelihood of achieving an optimal schedule length during project execution may be very low. Based upon the distribution of resource-feasible schedule lengths, we may prefer a longer leveled schedule length, one that is more likely to be achieved.
For several years, I have used a scheduling exercise in my classes. The unleveled project is 175 days in length. Project 2013 and 2016 leveled the schedule to 235 days, which happens to be an optimal leveling in terms of schedule length. But, Project 2019 levels the schedule to 300 days (starting with the same unleveled schedule and using the same leveling options). The 300-day length is five days short of the sum of all task lengths. Should I be concerned? What are some real world consequences of this scenario?
What Project users don’t see is the distribution of resource-feasible schedule lengths. By exploring Project’s leveling performance, we may gain insight that will help set our expectations.
Robin Nicklas
John,
Anyone who has studied resource leveling has come across the use of heuristic methods, general rules governing the order in which you assign resources to competing tasks. You mention a few: minimum slack (give the resource to the most critical task), minimum duration (minimize flow time by giving the resource to the shortest task), and ID (give the resource to the first available task in the list—which is great for breaking ties). The list is extensive.
But, like you, my favorite one is RANDOM! Much like a manager confronted with a resource constraint first thing in the morning, you flip a coin and move on. Coupled with repeated trials, as you suggest, you can build a distribution of resource-feasible schedule lengths. It is like a Galton box for resource-constrained schedules.
Using the Priority field in Project is one way to implement such a simulation. While there are Project add-ins for general schedule simulation (e.g., Full Monte), I am not aware of any that consider resource constraints.
You might be interested in my article on resource-constrained schedule simulation