Accession Number : ADA138307

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

Descriptive Note : Doctoral thesis,

Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST

Personal Author(s) : Fox,M S

PDF Url : ADA138307

Report Date : 13 Dec 1983

Pagination or Media Count : 197

Abstract : 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.

Descriptors :   *Scheduling, *Production, *Sequences, *Management planning and control, Operations research, Artificial intelligence, Computer applications, Models, Information processing, Semantics, Syntax, Computer logic, Problem solving, Decision making

Subject Categories : Administration and Management
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE