

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

Priorities: C,A,B 0 10 20 30 40 50

Late: A (20), B (30)

Iteration: 1

Priorities: B,A,C 0 10 20 30 40 50

Late: A (20), C (10)

Iteration: 2

A C B

Priorities: A,C,B 0 10 20 30 40 50

Late: B (30) Iteration: 3

Figure 2: Simple example To illustrate the swo cycle, consider a simplied scheduling example. Suppose we have a single production line, and three tasks to schedule, A B and C Only one task can be performed at a time. Execution starts at t 0. The duration and deadline for each task is shown in Figure 2. The ob jective is to minimize the number of late tasks. An optimal solution will have one late task.

Suppose our initial priority sequence is hC; A; Bi and the constructor schedules tasks in order, at the earliest possible time. The resulting schedule has two late tasks B and A). Suppose that our analyzer assigns one point of \blame" to each late task, for each unit of time it is late. In this case, A B and C receive 20, 30 and units of blame, respectively. Figure shows the prioritization, the schedule that the constructor builds from that prioritization, and the late tasks with the blame assigned to each.

For the next cycle, the prioritizer must take the previous priority sequence, and the blame assigned by the analyzer, and generate a new priority sequence. A simple prioritizer might just sort the tasks by their numeric blame in descending order, resulting in the new priority sequence hB ; A; Ci After the second cycle, tasks A and C are late, scoring 20 and 10 points of blame, respectively. The new priority sequence is then hA; C; Bi The third solution, constructed from this priority sequence, has only one late task, B

which receives 30 points of blame. At this point we have an optimal solution. If we continue running swo however, as we might expect to do since we typically do not know when we have reached optimality, swo will attempt to x what was wrong with the current solution.

Here, since task B was late, its priority would be increased, and the resulting solution would x that problem at the expense of others. (We would also enter a short cycle, alternating between the last two schedules. We address this by introducing some randomization in the prioritizer.)

Although this example is highly simplied, and there would clearly be better and more sophisticated ways to implement each of the three modules, Figure shows that the behavior illustrated by the simple example is re ected in a real domain. The gure shows the changing position in the priority sequence of three tasks in the scheduling domain that is described in detail in the following section. One task (\Job 24") starts out with a high priority, and remains at a relatively high priority level. We can see that when the task is scheduled
