Main Page

From ResourceLevelWiki

Jump to: navigation, search

Resource Leveling Algorithm. v. 0.20090312a

This document is currently an alpha draft. It is intended to be changed a lot, even completely rewritten if needed. The algorithm as described still misses some features yet. It is modified along with regression testing that brings new usecases. It is still made public to give ideas and already get feedback. Currently 24 regression usecases are successfully covered by this algorithm.

Contents

[edit] Objective

The goal of this paper is to present a free resource leveling algorithm that can be implemented easily.

It will give simple data structures and simple functions that can be nearly copied/pasted to run. It is assumed that the reader has already a basic knowledge of project management, meaning he knows about the problem of resource leveling inside a project.

[edit] Input data

Here are the notions the algorithm deals with as input:

  • Resources: they contain the following attributes:
    • Availability calendar: it is a calendar containing a number of working hours for each day from the beginning to the end of the project.
  • Tasks: they contain the following attributes:
    • Priority: it measures how much important this task is. It is an integer (the greater the more important).
    • Sizing: it measures the number of working hours needed to complete the task.
    • List of successors: a list of other tasks that cannot begin unless this one is completed.
    • List of assignable resources: a list of references to the resources that can be assigned to this task. For each assignable resource, it is possible to indicate a maximal amount of working hours for this association.
  • Different ways to assign a set of resources to a task (the algorithm can try several attempts and choose the best one). Each way can be tuned considering some human parameters. The parameters are pondered with coefficients:
    • It can be better to assign just 1 resource to a task if possible even if the task is a bit delayed.
    • It can be better to not change assigned tasks of a resource too often.
    • It can be better for a task to reuse the same resources as its predecessors.
    • The more resources are working on a task, the more effort it will need to complete the task due to human communication constraints.

[edit] Output data

Here is the information the algorithm gives as output:

  • For each resource:
    • Calendar of tasks to work on: for each day, a set of tasks and their corresponding working hours.

[edit] Conventions

The following naming conventions apply for the following explanations:

  • Ri represents a resource (number i).
  • Ti represents a task (number i).
  • [ A, B, C ] represents a list containing items A, B and C.
  • ... represents a sequence (could be undefined) of items. Can be used in lists ([ A, ..., Z ]).
  • map< TypeA, TypeB > represents a type of map, whose keys are of type TypeA and the values of type TypeB.
  • list< TypeA > represents a type of list, storing items of type TypeA.
  • [ NameA: TypeA, NameB: TypeB, … ] represents a list of finite number elements that have a given name and a given type. This can be seen as a record data structure. Values of such a structure can be abbreviated [ ValueA, ValueB ], given that ValueA is affected to NameA attribute, and so on.
  • T.Priority represents the priority of task T.
  • T.Sizing represents the number of hours needed to complete T.
  • T.MaximalResourceAllocation[R] represents the maximal number of hours the resource R can work on task T.
  • T.Predecessors represents the list of predecessors of T.
  • T.SharingResourcesTasksID is an identifier that is the same for all the tasks that can share at least 1 resource. It can be seen as an identifier of a partition of tasks. It identifies all the tasks that might influence each others due to resources assignments.
  • Map.keys represents the list containing every key of a map.

The granularity of the examples in this document is about days. However, the algorithm does take hours assignment into account. This choice in the document has been made for clarity reasons.

[edit] Overview

[edit] Base principle

The main idea of the algorithm is to consider, for each task, the available resources that could work for it. Therefore a calendar of resources’ availability for each task is built.

Then tasks are assigned 1 by 1, from the most important one to the least important one, to their available resources. Each time a task is assigned, available resources of the other tasks are updated accordingly.

Fig. 1: Creation of the resources' availability calendar, per task

Fig. 2: Assignment of tasks to their available resources

[edit] Computing dynamically the importance of tasks

The efficiency of the algorithm lies in the ordering of the tasks; that is computing the importance of the tasks. It is mandatory that the most important ones (the high priority tasks) are assigned to their resources before others, if possible.

However it is possible that low priority tasks have to be assigned before high priority ones, otherwise they would delay still greater priority ones due to dependencies. Such delays might be only seen when we assign tasks far in the future, and can be hardly seen when assigning first ones.

Therefore computing the importance of a task requires trying all possible assignments of tasks to resources. It is not feasible due to performance constraints.

This is why the algorithm makes a first sort of the tasks, based on simply computed importance (using priorities and critical paths). It is then possible that this order is not optimal at all. It can be figured out when the algorithm realizes that a task is delayed but could have been assigned to resources in the past that were already assigned to another task. Therefore the order of the tasks is modified dynamically based on those findings, and then it tries again assigning them in that new order. The algorithm remembers each sort that has been tried and then can choose among untried paths or least expensive paths.

[edit] Reordering tasks and remembering: the paths tree

The main idea being that we have to find the best possible sort of tasks, the algorithm has to keep record of all tried paths. This naturally induces creating a tree of all the tried paths already encountered in the algorithm.

Each node of this tree represents a task assigned to its resources a certain way. A branch of this tree represents a given sort of the tasks, and associated to each node is the consequences of such an assignment (whether it delays incorrectly other tasks or not).

Then the algorithm can be interpreted as finding the best path among this tree, that is the one minimizing the consequences.

Here is an example of an assignment that needs to reorder the tasks.

Example of a case that has to reorder the initial tasks' sort

[edit] Several ways to assign a task to its available resources

Each time a task is assigned to some of its resources, several attempts are made to do it differently, and then the best solution is kept. Each attempt is recorded, along with the consequences it has in terms of tasks’ delays, and then it is possible to choose among different ways which one is the best.

[edit] Algorithm architecture and components

In order to better understand the algorithm, a few actors can be defined.

Fig. 3: Actors of the algorithm with their call relations

  • Algorithm entry point represents the main method of the algorithm, handling inputs and outputs as described before.
  • The importance manager handles the order of tasks and their importance. It
    • creates the original order of tasks and
    • updates the importance of tasks.
  • The solution manager tries to assign a sorted list of tasks to their resources. Its goal is to find different ways to assign them and to compare several solutions to get the best one.
  • The task assignment manager tries to assign a single task to its resources. It then updates all relevant information that might be impacted on other tasks. Finally it checks if other tasks can accept the assignation.
  • The paths manager stores all the tried paths (tasks’ sorts) the algorithm got, and for each one of them stores the consequences this path had on the tasks. Then this manager gives the possibility to retrieve the best possible path based on this information.

[edit] Algorithm summary

The algorithm can be summarized this way:

1. Compute the minimal start dates of each task, considering that all their available resources could work for them, and taking dependencies into consideration.

Fig. 4: Initialization - Create the resource's availability calendar per task, and record the minimal start dates in it

2. Sort the tasks by simple importance. The importance is computed recursively as the maximal value among the priority of the task and the importance of all its direct successors (successors that could begin right after this task’s completion)

Fig. 5: Example of importances calculation based on priorities and critical paths

3. Call a recursive method that tries to assign tasks 1 by 1:
3.1. Try several ways to assign the task to its available resources. For each way:

Fig. 6: Example of assignment of a task and consequences in delaying other tasks

3.1.1. Compute the consequences of this assignment in following tasks not yet assigned (compute their new minimal schedule, according to the new resources' availability and tasks' dependencies).
3.1.2. Complete the memory of tried paths with this information.
3.1.3. If the assignment does not shift tasks (their minimal end date) that are more important than already assigned ones, call recursively the method that will assign the next task in the list. Remember all possible solutions returned by this call, as well as possible better paths it can propose in case of impossibilities.Once all iterations have been tried, either return the possible solutions, or find possible better paths if no solution has been found.
3.2. If there is a better path that can be taken at this point, do it by getting back to the iterations with the new path.
4. Choose the best solution among all the remembered ones.

[edit] Detailed explanation

[edit] First explanations, data types

[edit] Identifying the way a task is assigned to its available resources

There is a data type identifying a task assigned a certain way to its resources (there is an iterative way to assign tasks to resources; for example first try to assign as much resources as possible to end earlier, then try to assign a minimal set of resources to the task to avoid communication complexity...). Each way to assign a task is identified by an iteration number. Therefore it is possible to get back to a certain way of task assignment by remembering this identifier. Iteration numbers begin from 0 and increase 1 by 1 for each task. This data type is called AssignedTaskID_Type. A way to assign a task to its available resources is recorded in another structure, storing assigned working hours per resource, per day: TaskAssignmentSolution_Type.

[edit] Recording consequences of a task's assignment

When a task is assigned to its resources, it will modify the availabilities of resources for other tasks, and then maybe shift those tasks' schedule. This can be harmless, but it can also be not profitable for the final solution. Therefore it is needed to remember the consequences of each assignment on the other tasks. Based on this information, it will be possible to find cleverly a possible better path to use. The type ShiftedTaskConsequences_Type has been made on that purpose. It stores a tree of tasks whose minimal end dates have been shifted by an assignment. It is a tree because such shifts occur recursively: T1's assignment shifts T2 (taking its resources), and then T2 will also shift T3 because T3 depends on T2.

[edit] Reordering tasks, replacing branches, paths memory

It is needed sometimes to perform a reordering of the tasks to assign. When we try to assign a sequence of tasks to resources, it is possible we realize this sequence is not optimal (meaning the original order of tasks list can be optimized). This optimization is done by moving down some tasks below others, therefore resulting in a new tasks order that hopefully will lead to a better solution once tasks are assigned to resources. A branch of tasks is represented by the type Branch_Type.

Each different order of tasks can be seen as a path in the tree of every possibility of tasks’ assignment to its resources. Each node of this tree is identified with the task and the way it has been assigned to its resources (the iteration number). To better find optimized paths, it is needed to store every path tried, and the reason why some of them were considered as not optimized. Therefore, the algorithm remembers the order of tasks and iteration numbers along with the importance of the task when it was assigned, and the maximal priority of the tasks shifted due to this assignment. This is done in a tree structure, whose nodes represent a task assigned to its resources. In this tree, T2 child of T1 means that T1 has been assigned first, then T2. To represent this tree, the type PathNode_Type has been created. Fig. 7: Example of a graph of already tried paths Therefore we can easily remember which path has already been tried and did not work due to high priority tasks shift.

[edit] The main structure storing the way tasks are assigned to resources

The algorithm will use a special data structure that represents a configuration of tasks assigned to resources. This structure (called AssignmentInfo_Type) is a map storing information per task. The idea behind is to imagine resources as containers of tasks' efforts. At the beginning of the algorithm, resources work hours are empty (not assigned to any task), and the algorithm will assign tasks little by little to free resources hours in a calendar. The AssignmentInfo_Type structure keeps track of the evolution of the assignments along the algorithm.

[edit] Method names grouped by actors

Following previous architecture of the algorithm, here are the method names that will be used. File:AlgoMethods.png

[edit] The detailed algorithm methods

Main

[edit] Solution Manager

SolutionManager::findAssignmentForTasksList

SolutionManager::tryPossibleSolution

SolutionManager::assignCompleteTask

[edit] Task Assignment Manager

TaskAssignmentManager::assignPossibleSolution

TaskAssignmentManager::shiftChildrenTasks

TaskAssignmentManager::shiftTaskMinimalDates

TaskAssignmentManager::computeShiftedDateHours

TaskAssignmentManager::removeCountedHoursFromResourcesBuffers

TaskAssignmentManager::removeResourcesFromOtherTasks

TaskAssignmentManager::notifyMinimalEndDateChanged

[edit] Importance Manager

ImportanceManager::populateImportances

ImportanceManager::getSortedTasks

ImportanceManager::updatePredecessorsImportances

ImportanceManager::updateImportance

[edit] Paths Manager

PathsManager::findPossibleBetterPathForTask

PathsManager::computeShiftedTasksList

PathsManager::findUnknownPathReorderingShiftedTasks

PathsManager::computeNewPathMovingTask

PathsManager::validateUnknownPath

PathsManager::reorderBranch

PathsManager::findPossibleBetterPathAlreadyKnown

PathsManager::getBestPathAmongBestShiftedImportancePaths

PathsManager::findSmallestShiftedConsequencesPaths

PathsManager::completeTriedPath

[edit] Current implementations

[edit] Ruby

The first implementation of this algorithm has been made in Ruby language (http://www.ruby-lang.org). The regression has been made in that language, too.

[edit] Access information and download

If you want to try the algorithm and run the regression cases with it, you will have to:

  1. Get Ruby if not already shipped with your OS
  2. Get a SVN client if not already shipped with your OS
  3. Checkout the SVN repository in a directory ("svn co https://resourcelevel.svn.sourceforge.net/svnroot/resourcelevel")
  4. Go to the "./resourcelevel/trunk/ruby/test" directory.
  5. Type "ruby -I../lib -w run.rb". This will run the regression tests, and display the result after a big debugging output. The last lines should look like this:

 .
 Finished in 2.205 seconds.
 
 24 tests, 24 assertions, 0 failures, 0 errors

Additionally, you can browse the SVN tree right here: http://resourcelevel.svn.sourceforge.net/viewvc/resourcelevel/trunk/ruby/

[edit] Remarks

  • Usually this is not the philosophy to set start/end dates and durations based on planned efforts as it is rarely realistic when dealing with several resources. However it is very handy and realistic when there is just 1 resource per task, and an additional factor increasing tasks' effort based on the resources complexity has been taken into account (TODO). This gives this algorithm more credibility even for multiple resources per task.
  • The way tasks are assigned to resources is not exhaustive. It exists many many different ways to do it. The algorithm each time tries several ways, and will then evaluate the final assignment to select the best one.
  • The way tasks are sorted is (or should be in case of bugs) exhaustive. This means that once it has been decided how tasks are assigned to resources, the algorithm has to find the optimal sort of tasks to ensure the ones with the biggest priority will be assigned first.
  • There are 2 performance bottlenecks identified so far:
    • PathsManager::findPossibleBetterPathForTask: A high level performance bottleneck. If this method gives better paths in a stupid way, it can either result in the same problems as the ones faced before by previous paths, or result in randomly chosen paths and therefore never find a good solution easily.
    • TaskAssignmentManager::notifyMinimalEndDateChanged: A low level performance bottleneck. This method is called very often, as for each assignment try, it will modify all impacted tasks recursively due to resources removal or tasks’ dependencies.

[edit] Ideas for improvement

  • In the algorithm, use a cache for SolutionManager::findAssignmentForTasksList calls: it is possible that it is called many times for the same iCurrentTasksList, each of them beginning at the same start date with the same assigned resources in the date range [start date -> end of project]. In this case, return the already computed solutions. These repetitions of calls would be due to the fact that we try several different resources repartition by task, and some may result in the same calls (to be validated though before implementing).
  • Take other constraints into account, as deadlines or costs for example. Deadlines would be very easy to implement, as we already deal with dependencies we can't move in TaskAssignmentManager::shiftChildrenTasks method. It would then just require minimal modifications in TaskAssignmentManager::shiftChildrenTasks method.
  • The needed effort computation can be a little bit randomized. It is a way to modelize the human errors in sizings or the various fluctuations that we can't forecast due to external factors hindering day to day performance of resources. This can be implemented in the main iteration of method SolutionManager::findAssignmentForTasksList. It can also be tuned using genetic algorithms (as it seems to be the next trend in Project Management Resource leveling) to modelize human errors that could be a little bit predictable. The good point is that we just need to modify SolutionManager::findAssignmentForTasksList to implement any strategy we want on this.
  • We can add the notion that resources are not equal in front of the same task. Some will be more efficient than others (technical knowledge, training need...). We still want to assign several resources for the task (as it can be better to train resource R1 and use it on the task than using directly resource R2 on it, even without training - maybe because R2 has to work on another priority task in the same time). In this case we can change the needed effort of a Task in the algorithm depending on which resource is affected to it. This is done also in the main iteration of SolutionManager::findAssignmentForTasksList.
  • We could select a subset of tasks to level. 2 possibilities:
    • If we have implemented deadlines constraints in the algorithm: We can use this kind of constraint for the children Tasks that were not part of the selection (therefore we don't want to move them, so they are seen as deadlines to their parents).
    • Else: We will automatically also level the children Tasks (recursively) of all selected Tasks.

For this to be implemented, we must keep assignment hours of all the tasks not selected.

  • Coefficients used for the rules of a single task’s assignment to resources could be tuned with a little GUI.
  • Ability to use some minimal/maximal lags between tasks could be set.
  • As increasing number of resources per Task also increases needed effort, we could also support the case when assigning several tasks to the same resource at the same time also reduces efficiency of this resource (time spent to switch from 1 task to another, get back to where the resource left the former task... consumes a little bit of time in practice. This is not as straightforward to implement as the cost of several resources per task, as it implies modifications of previously assigned resources to tasks, but it should not be a big deal.
  • We could add some rules concerning the resources' choice when assigning tasks to resources' availability. For example:
    • Resources choice preference among the set of available resources (I prefer assigning resource R1 instead of R2 if possible).
    • Resources choice preference based on parent tasks assignments (If R1 deals with the parent task, it is better if it also deals with the child task if possible).
  • It has been chosen to always populate PathNode_Type.TaskPaths with the computed map of accessible tasks in PathsManager::completeTriedPath. This can be challenged as in some cases, this information will be useless. The cases are when we complete a path that results in a shift of a direct successor (not part of the critical path) due to the assignment strategy only. In this special case, we will not call PathsManager::findPossibleBetterPathForTask method, so the population can be useless. However, we must ensure that it can still be computed later (if the path is chosen to be forced). Therefore we could think of populating this map only when needed, but this has 2 main drawbacks:
    • In all cases the map is used, we have to test first if it has been initialized before knowing if a task is accessible.
    • In order to compute the accessible tasks, we must add a pointer to the parent PathNode_Type to each PathNode_Type object.

[edit] Contacts

Any comment, suggestion, remark, idea... is welcomed.

I am planning on improving this algorithm a lot, and very grateful to any help you can give with this.

You can use the discussion page or my email to contribute.

Thanks

Muriel Salvan

Personal tools