| << Day_To_Day_Juggling << | Table Of Contents | >> fdl >> |
This chapter contains information that you don't need to know to use TaskJuggler. It describes internal algorithms that are provided for the curious.
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.
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