Algorithms: schedule

Schedules

The solution space for any search algorithm is a tree of schedules (partial and complete) that put tasks on processors at a certain start time. These schedules are searched by algorithms which pick which schedule to expand at each step.

Representation

In general, schedules are represented as follows:

class Schedule {
    Schedule parent;
    ScheduledTask task;
    int processor;
    int startTime; // (maybe)
}

They form a linked-list-like structure with each schedule containing a new task and a reference to the previous schedule. Each child schedule schedules a new task. This can be iterated on to form the full schedule.

Schedules can be expanded (forming valid children schedules with a new task) by calling the expand() method on a schedule. This returns a set of child schedules. In the future, expand will need to be optimised beyond checking all tasks that can be scheduled (such as with duplicate schedule checking) and may need to be refactored.

Algorithm-Specific

Some algorithms/optimisations will require alterations to the general representation of a schedule. For example, A* assigns costs (calculated by some heuristic function) to each schedule. Implementation of this is probably easier to be directly made in the schedule class, but final design of schedules is still to be decided based on what algorithm(s) we decide to implement further and optimise.

Issue

The GitHub issue that covers discussion/implementation of how schedules are represented is here.