8 TaskJuggler Internals

This chapter contains information that you don't need to know to use TaskJuggler. It describes internal algorithms that are provided for the curious.

8.1 How the Scheduler works

It's important to understand that the scheduler implementation is not an optimization algorithm. It does not search a solution space and evaluates various alternative results against each other. This has been tried, but for any real-world project, the solution space becomes unmanageable and scheduling runs took hours to complete.

Instead, we use a heuristic to decide when each task gets its resources assigned. This heuristic is certainly not perfect but has shown good results with fairly moderate computation costs. The following sections contain an overview of the scheduling algorithm. Users are also encouraged to read the actual source code. It can be found in Project.rb, TaskScenario.rb, ResourceScenario.rb and Allocation.rb. All these files can be found in the lib/taskjuggler directory. You can also browse the sources on github.

The scheduler needs to determine the start and end date for all tasks that don't have such dates yet. To deal with multiple concurrent time zones, all time related events are stored internally as UTC time. Additionally, it allocates resources to tasks. All events such as start or end of a task, or allocation of a resource can only happen aligned with the timing resolution. This determines the smallest possible allocation period that we call a time slot. The duration of the slot can be set by the user. Possible values are 5, 10, 15, 30 and 60 minutes.

TaskJuggler keeps a scoreboard for each time slot for each leaf resource. Each scoreboard entry specifies whether the resource is unassigned, assigned to a specific task or on leave. This explains why the project duration and number of allocated resources determines the memory usage of the scheduler.

For the scheduling of the project, the scheduler only looks at leave tasks that are not milestones. Container tasks and milestones are scheduled once all necessary information is available. During the scheduling process, leave tasks can have 3 different states.

1. Not ready for scheduling: The task is missing a start or end date that depends on another task's date that hasn't been determined yet.
2. Ready for scheduling: The task has at least a start or end date but one of them is still missing or resources have not yet been assigned for all time slots. The scheduling direction (ASAP or ALAP) determines whether the start or end date is needed. ASAP tasks are scheduled from start to end, so they require a start date. ALAP tasks are scheduled from end to start.
3. Scheduling completed: The task has a start and end date and resources have been assigned for all time slots.

The goal of the scheduler is to transfer all tasks in the completed state. Until this goal has been reached, at least one task needs to be in the ready state. If that's not the case, the project schedule cannot be determined and an error is raised. In case there are more than one task in the ready state, we need to have a well defined priority of the tasks. This is necessary since those ready tasks may compete for the same resource in the same time slot.

The priority can be directly influenced by the user with the priority attribute. This user-defined priority always trumps the other internal criteria described below. In case two tasks have the same priority, an additional measure is used. This measure is called path criticalness. The path criticalness is calculated for each leaf task. The path criticalness is a measure for how important the task is to keep the overall project duration (start of first task to end of last task) to a minimum.

To determine the path criticalness, we first need to determine the resource criticalness first. This is a measure for how likely the tasks that have this resource in their allocation list will actually get the resource. A resource criticalness larger than 1.0 means that statistically, at least one tasks will not get enough of this resource. This is just a statistical measure based on the total requested allocations and the number of available work time.

Once we have determined the criticalness of all allocated resources, we can calculate the criticalness of each individual task. This really only matters for effort based tasks. These really need their allocations to be finished within a limited amount of time. For length and duration tasks, the allocations are by definition optional. The user can still influence the allocation to length and duration tasks by adjusting the priority appropriately. However, there is no guarantee that such tasks will ever get any resources assigned. The criticalness of an effort based task is defined as the average of the criticalness of the resources allocated to this task.

We also assign a criticalness to milestones. Based on their priority a criticalness between 0 and 2.0 is assigned. This is done to reflect the user perception that milestones are usually some important goal of the project.

The final step is now the computation of the path criticalness for each effort-based leaf task. For each possible chain of task (path) that is going through a task, the sum of the criticalness values of the tasks of the path is computed. The largest sum is the path criticalness of that task.

This heuristic will favor allocations to tasks with critical resources and long dependency chains. As a result, the critical paths of the project are tried to be kept short. The user can use the criticalness and pathcriticalness columns to review the respective values for he project's tasks and resources.

When the criticalness and pathcriticalness for all leaf resources and tasks has been determined, the leaf tasks are sorted by priority (high to low), then by pathcricialness (high to low) and then by the index (low to high). In a loop that is terminated when all tasks have been scheduled or an error condition has been detected, the first task that is ready for scheduling is completely scheduled. This means that resources are allocated for all time slots and missing dates are being computed. The newly determined end (for ASAP tasks) or start (for ALAP tasks) date is then propagated to dependent tasks, milestones or parent tasks if needed. This can result in other tasks becoming ready for scheduling and the list is searched again for the first task that is ready for scheduling to be scheduled.

A task can only be scheduled when it is ready for scheduling. This means that at least the start date for the scheduling process must be known. For ASAP (As Soon As Possible) tasks, the scheduler start date is the start date of the task. For ALAP (As Late As Possible) tasks the scheduler start date is the end date of the task. ASAP task will be scheduled from start to end, ALAP tasks from end to start. This is important to understand as resource assignments for each time slot will be determined in this order.

Mixing ASAP and ALAP tasks in the same project is supported but should be used very carefully. It can lead to situations where a lower priority tasks that is earlier in the scheduling process ready for scheduling takes away resources from a higher prioritized task that competes for the same resources. This condition is known is priority inversion. If the scheduler detects such a situation, a warning is generated.