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

The scheduler needs to determine the start and end date for all tasks that don't have such dates yet. Additionally, it allocates resources to tasks. All events such as start of a task, or allocation of a resource can only happen aligned with the timing resolution. The smallest possible allocation period is called a time slot. The duration of the slot can be determined by the user. Possible values are 5, 10, 15, 30 and 60 minutes. Internally, all events are stored as UTC time.

TaskJuggler keeps a scoreboard for each time slot for each leaf resource. This explains why the project duration and number of allocated resources determines the memory usage of the scheduler.

During the scheduling process, 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.
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 tasks 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 for the same time slot.

The priority can be directly influenced by the user with the priority attribute. 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. 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. For length and duration tasks, the allocations are optional. The user can still influence the allocation to length and duration tasks by adjusting the priority appropriately. The criticalness of a 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.

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 task with critical resources and long dependency chains. As a result, the critical paths of the project are tried to be kept short.

This heuristic is certainly not perfect but has shown good results with fairly short computation overhead. The scheduling process is not an optimization process. It does not evaluate alternatives and it does not search for local extremes in a solution space.

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.