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 as:

• 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 constraints).
• 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.