zbMATH — the first resource for mathematics

Constraint-directed search: a case study of job-shop scheduling. (English) Zbl 0702.68032
Research Notes in Artificial Intelligence. London: Pitman Publishing; Los Altos, CA: Morgan Kaufmann Publ., Inc. 184 p. £17.95 (1987).
This book 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 among resources and operations, availability of resources, and preferences among 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. The problem of scheduling orders in a job-shop under these constraints raises a number of issues of interest to the artificial intelligence community.
This monograph presents a system called ISIS which uses a constraint- directed search paradigm to solve the scheduling problem. In addition, the ISIS system has been designed to provide complete facilities for practical use in the factory. Versions of the ISIS program have been tested on a model of a real factory using simulated orders. The interactive system bridges the gap between scheduling systems which simply guide the human scheduler, to a scheduling system that can control operations in real time.
Reviewer: R.Slowinski

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68R05 Combinatorics in computer science
90B35 Deterministic scheduling theory in operations research
68-02 Research exposition (monographs, survey articles) pertaining to computer science
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence