Constraint-Directed Search: A Case Study of Job-Shop Scheduling.

摘要

This thesis investigates the problem of constraint-directed reasoning in the job-shop scheduling domain. The job-shop scheduling problem is defined as: selecting a sequence of operations whose execution results in the completion of an order, and assigning times (i.e., start and end times) and resources to each operation. The number of possible schedules grows exponentially with the number of orders, alternative production plans, substitutable resources, and possible times to assign resources and perform operations. The acceptability of a particular schedule depends not only on the availability of alternatives, but on other knowledge such as organizational goals, physical limitations of resources, causal restrictions amongst resources and operations, availability of resources, and preferences amongst alternatives. By viewing the scheduling problem from a constraint-directed search perspective, much of this knowledge can be viewed as constraints on the schedule generation and selection process. In this thesis, we present a system called ISIS. ISIS uses a constraint-directed search paradigm to solve the scheduling problem. ISIS provides: a knowledge representation language (SRL) for modeling organizations and their constraints; hierarchical, constraint-directed scheduling of orders, which includes: constraint-directed bounding of the solution space; context-sensitive selection of constraints, and weighted interpretation of constraints; analytic and generative constraint relaxation; and techniques for the diagnosis of poor schedules.