Global Hierarchical Opportunistic Scheduling Tool: a system for scheduling based on constraint analysis
Danielle Ziébelin · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1991
When a human being doesn't know how to solve a problem, one of the methods at his disposal consists in using problem-solving knowledge on easier problems. This knowledge can then serve as heuristics to guide the search for a solution to the original problem. Many AI researchers have already profited from this idea and in our turn we have adopted it to seek solutions to workshop scheduling problems. Setting up scheduling to satisfy, as well as is possible, the preferences that have been expressed is very complicated when the set of constraints is too large and conflictual to be solved directly. The strategy we propose consists in evaluating the interaction between constraints and grouping those that lead to the same schedule into simplified subproblems. A solution to these subproblems takes the form of a series of tasks satisfying the constraints. In combination with others, this solution can guide the scheduling system in its choices for constraint satisfaction. Establishing such a strategy requires close cooperation between constraint analysis decisions and scheduling decisions. But maximum effectiveness precludes any rigidly predefined way of organizing this cooperation. Thus the system must be able to adapt its problem-solving strategy in terms of evolution in the solution. The cooperative and opportunistic nature of the system has led us to choose a 'blackboard' based architecture.