Using The Trace Facilities to Relax a Model

The algorithm used here is based on list scheduling: at each step, an activity is selected from the list of non-scheduled activities and scheduled at its earliest possible time. If everything is all right, the process continues until all activities are scheduled. It may happen, however, that at some step in this procedure, the current, partial schedule becomes inconsistent with the set of constraints of the problem. Given such a situation, there is no hope to find a complete schedule by continuing to extend the partial schedule. In standard, non-deterministic search, a backtrack would occur at this point, undoing a previous decision in an attempt to re-establish a consistent partial schedule. Our approach here is different. Instead of backtracking, the algorithm analyses the reason that the partial schedule is inconsistent, called the "fail reason," and identifies a constraint that can be relaxed in order to restore consistency to the current partial solution. Note the contrast between this approach and standard, non-deterministic search. Rather than backtracking to search for a valid partial schedule, we relax a problem constraint, changing the problem to one for which the current partial schedule may be valid.

The main goal of this chapter is to demonstrate the use of the trace facilities in the analysis of the fail reason. The chapter also presents how a problem can be relaxed using Concert Technology facilities and a solution object as well as how activities can be selected using predicates and evaluators.