For SWO to be effective, it is obvious that analysis, prioritization and construction must all work together to improve the quality of solutions. We have already discussed the complications that can arise when constraints are placed on the order in which the constructor can make decisions, as is the case for List Scheduling and ALS, where construction is done strictly left-to-right. Without more complex analysis, the search spaces can effectively become uncoupled, so that changes in priority don't cause the constructor to fix problems discovered by analysis.
Another way the search can become uncoupled is related to the notion of ``excess cost,'' discussed for the scheduling implementation. The calculation of excess cost in the analyzer turned out to be a key idea for improving the performance of SWO. However, problems sometimes have tasks that must be handled badly in order to achieve a good overall solution. One of the scheduling problems described previously has two such ``sacrificial'' tasks. Whenever a good solution is found, the analyzer assigns high blame to these sacrificial tasks, and the constructor handles them well on the next iteration. This means that the resulting solution is of poor overall quality, and it is not until other flaws cause other tasks to move ahead of the sacrificial tasks in the priority sequence that SWO can again, briefly, explore the space of good solutions. In such cases, to some extent the analysis is actually hurting the ability of SWO to converge on good solutions.
Ideally, we would like to generalize the notion of excess cost to recognize sacrificial tasks, and allow those tasks to be handled badly without receiving proportionate blame. For problems in which a task must be sacrificed in all solutions, it may be possible to use a learning mechanism to accomplish this.
However, the notion of a sacrificial task can be more subtle than this. Suppose for example that we are scheduling the construction of two airplanes, P1 and P2, and that each has a key task, T1 and T2, respectively, requiring all of some shared resource, R. Because of the resource conflict, we must either give R to T1 early in the schedule, starting construction on plane P1 before P2, or we must give R to T2 early in the schedule, with the opposite result. Whichever of the two tasks is started early will finish on time, but the other will be late.
Suppose we construct a schedule in which T1 goes first, and T2 is late, thus receiving a heavy blame factor. SWO increases the priority on T2, and as a consequence, T2 goes first in the subsequent schedule. But then T1 is late, and on the next iteration it will again go first. We could alternate in this manner forever, and the result would be that SWO would fail to explore either option very effectively, because it would be jumping back and forth between the option of building plane P1 first, and the option of building plane P2 first, without remaining in one region of the search space long enough to refine a solution.
The difficulty is that neither T1 nor T2 can be identified as a sacrificial task. Assuming the two planes are not identical, we cannot simply argue from symmetry that we should just pick one of the two tasks to be sacrificed. If, however, we could identify a sacrificial task by the role it plays in a solution, we could achieve what we need. Here, the task to be sacrificed must be the one that belongs to whichever plane is started later. If the analyzer could reduce the blame assigned to that task in a schedule, whichever task it happens to be, it would allow SWO to explore that region of the search much more effectively.
This problem of interchangeable roles would arise even more clearly with the introduction of conditional elements in a solution. Suppose, for example, we have a scheduling problem in which the constructor may choose to include or not include task instances of some type, adding however many instances are needed to satisfy a resource requirement. If those tasks are all instances of the same task type, then they are interchangeable, and penalizing one may simply cause a shuffling of those instances that does not really address the problem. Moreover, with conditional tasks, it is not clear how the analyzer should assign blame when the set of task instances in the current schedule may be very different from the set of task instances in successor schedules.
To address these concerns, the notion of prioritization could be generalized to apply to additional aspects of a problem. In scheduling this might mean not just prioritizing tasks, but also resources over various time intervals. We also propose that the these prioritizations be limited to the ``fixed'' elements of a problem. In scheduling problems, for example, these may be the non-conditional tasks, resources, etc. (In our example domains, all of the elements are fixed in this sense, so this was not an issue.)
One intuition behind this proposal is that these are the elements that will tend to define roles. In the earlier example with tasks T1 and T2, corresponding to the two planes being built, the critical element is not either task per se, but actually resource R, early in the schedule. If this phase of resource R receives a high priority, and the later phase of resource R receives a lower priority, then whichever of the two tasks occurs later will be recognized as less critical. While this does not exactly capture the notion of ``role'' that we would like, it comes a lot closer than the current approach. In addition, assigning priorities to the fixed elements of a problem has the advantage of being applicable to problems with conditional tasks. Research is currently under way to explore this approach.