The central thesis of this dissertation is that an understanding of the structure of a problem leads to high-quality heuristic problem solving performance in constraint-directed scheduling. Our methods for gaining an understanding of problem structure focus on texture measurements:​ algorithms that implement dynamic analyses of each search state. Texture measurements distill structural information from the constraint graph representation of a search state which is then used as a basis for heuristic decision-making.

To enable the rigorous empirical investigation of the above thesis in the context of real-world scheduling problems, we define the ODO framework for constraint-directed search. The framework allows us to implement scheduling algorithms and their components, and to compare them both from the perspective of static similarities and on the basis of empirical performance.

In this dissertation, we extend the scope of scheduling problems that can be addressed, in general, by constraint-directed techniques. Specifically, we develop the concept of a generalized measure of constraint criticality that enables the construction of dynamic, opportunistic heuristic commitment techniques. Based on an analysis of the requirements of a measure of constraint criticality, we suggest the probability of breakage of a constraint as such a measure.

The investigation of our thesis focuses on three classes of scheduling problems:​ job shop scheduling, scheduling with inventory, and scheduling with alternative activities. In each of these problem classes we empirically demonstrate that, as a problem becomes more complex, knowledge of its structure has a dominant role in guiding heuristic search to a solution.