Implementation

We describe the implementation in terms of the three main components of SWO:

Constructor.

The constructor builds a schedule by adding tasks one at a time, in the order they occur in the priority sequence. A task is added by selecting a line and a position relative to the tasks already in that line. A task may be inserted between any two tasks already in the line or at the beginning or end of that line's schedule. Changes to the relative positions of the tasks already in the line are not considered. Each task in the line is then assigned to its earliest possible start time, subject to the ordering, i.e., a task starts at either its release time, or immediately after the previous task on that line, whichever is greater.

For each of the possible insertion points in the schedule, relative to the tasks already in each line, the constructor calculates the effect on the objective function, and the task is placed at the best-scoring location. Ties are broken randomly. After all tasks have been placed, the constructor applies SWO to the individual line schedules, attempting to improve the score for each line by reordering the cables that were assigned to it.

Analyzer.

To assign blame to each task in the current schedule, the analyzer first calculates a lower bound on the minimum possible cost that each task could contribute to any schedule. For example, if a task has a release time that is later than its due date, then it will be late in every schedule, and the minimum possible cost already includes that penalty. Minimum possible setup costs are also included. For a given schedule, the blame assigned to each task is its ``excess cost,'' the difference between its actual cost and its minimum possible cost. Excess lateness costs are assigned to tasks that are late, and excess setup costs are split between adjacent tasks.

Prioritizer.

Once the blame has been assigned, the prioritizer modifies the previous sequence of tasks by moving tasks with non-zero blame factors forward in the sequence. Tasks are moved forward a distance that increases with the magnitude of the blame. To move from the back of the sequence to the front, a task must have a high blame factor over several iterations. We call this a ``sticky sort.''

Our current implementation has considerable room for improvement. The analysis and feedback currently being used are very simple, and the construction of schedules could take various heuristics into account, such as preferring to place a task in a line that has more ``slack,'' all other things being equal.