== 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. 

=== 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 [https://github.com/taskjuggler/TaskJuggler
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 [[timingresolution|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.

# ''''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.
# ''''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.
# ''''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 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 task 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''' [[columnid|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
(hight 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.
