Resource leveling algorithms: a comparison
Resource leveling is the process of resolving resource efforts across tasks when a resource is over-allocated. Deswik.Sched ensures that resources are not under-used or over-allocated. As you assign resources (or resource pools) to tasks in your schedule, you do not need to consider whether a particular resource is already allocated elsewhere in your schedule. Resource leveling will identify whether you have resource over-allocation issues or not.
Deswik.Sched has come a long way from version 1.2 where resource leveling could only be done on task priorities. There’s now three major leveling algorithms which support a myriad of features.
1. Normal Leveling Algorithm
The resource leveler:
- Determines a point in time (called the conflict date) in which to search for and resolve conflicts (resource over-allocations).
- Searches for tasks that may (or may not) be conflicting.
- Resolves conflicts one resource (or resource pool) at a given point in time.
- Performs a cut down schedule calculation at the end of the iteration to move the ‘bumped’ tasks forward in time.
- Then repeats this until all tasks are assigned a physical resource.
2. LPA – Linear Progression Algorithm
Schedules have been getting larger. In the early days, our largest customer schedule had just over 16,000 tasks and took over 5 minutes just to open. Now many schedules are around 100,000 tasks and frequently over 1 million dependencies.
Schedule calculation (ST) time is determined by:
- The number of tasks (NT) in a schedule.
- The number of dependencies (ND) in the schedule
ST = NT * ND
Leveling time (LT) is determined by:
- The schedule calculation ST time
- The number of tasks.
LT = ST * NT
LT = NT * NT * ND
This means that leveling larger schedules is exponentially slower to level than smaller schedules. To stop leveling times being exponentially determinant on the number of tasks, the LPA algorithm breaks the schedule into a number of sub-schedules (each of 1000 tasks in size). These sub-schedules are then levelled as separate schedules.
This means leveling time is determined by:
- Time to level 1 sub-schedule (LTSS)
- Number of sub-schedules (NSS)
LT = LTSS * NSS
That means that leveling time is now a linear progression (LP) of the time it takes to level one sub-schedule. As such, we call this algorithm the Linear Progression Algorithm – LPA.
3. Sequencer – (Mini Leveler)
The Sequencer initially goes through all the tasks and adds those that can be leveled, such as those that don’t have constraints, predecessors, and so on, to an ordered list. During leveling, when a task is leveled it is removed from the ordered list and its successors are added. This process is repeated until the ordered list is empty. If no task in the list can be leveled the leveling date (i.e. the conflict start date) is pushed out until a task can be leveled. When a task is leveled it is assigned a physical resource and set a start date.
The following graph compares the 3 different algorithms on four large schedules:
For more information on the resource leveling algorithms in Deswik.Sched, go to the Help Files.