Conventional wisdom in the field of scheduling, is that scheduling
problems exhibit such a richness and variety that no single scheduling
method is sufficient. But in the last five years, research in
Artificial Intelligence constraint-directed approaches to scheduling
have demonstrated a surprising degree of effectiveness and generality.
The primary components of constraint-directed scheduling are a problem
topology, textures and objectives. A problem topology is represented
by a constraint graph where nodes are activities and arcs are
constraints among the activities, e.g., temporal and resource. A
problem topology may be altered by problem reformulations, such as
abstraction and aggregation. Problem textures are fundamental measures
of constraint graphs that indicate decision complexity, uncertainty
and elasticity. Texture measures, such
- Value Contention: degree of to which more than one
variable wish to have the same value.
- Variable Reliance: degree to which a variable
relies upon the assignment of a particular value.
- Variable Looseness: size of range (conjunction of
- Constraint Tightness: degree to which the
constraint reduces the set of admissable solutions.
- Constraint Importance: how important is it to
satisfy the constraint.
are used to determine where in the constraint graph the next decision
is to be made, i.e., variable and constraint selection. Problem
objectives define what is to be optimized.
See Fox, M.S., Sadeh, N., and Baykan, C., (1989), "Constrained Heuristic Search", Proceedings of the International Joint Conference on Artificial Intelligence, pp. 309-316, Detroit MI., for more details.