Patty.Hodgson@ISL1.RI.CMU.EDU.UUCP (01/27/87)
AI SEMINAR
TOPIC: THE ISIS PROJECT: AN HISTORICAL PERSPECTIVE OR LESSONS LEARNED
AND RESEARCH RESULTS
SPEAKER: MARK S. FOX, CMU Robotics Institute
PLACE: Wean Hall 5409
DATE: Tuesday, January 27, 1987
TIME: 3:30 pm
ABSTRACT:
ISIS is a knowledge-based system designed to provide intelligent
support in the domain of job shop production management and control.
Job-shop scheduling is a "uncooperative" multi-agent (i.e., each
order is to be "optimized" separately) planning problem in which
activities must be selected, sequenced, and assigned resources and
time of execution. Resource contention is high, hence closely
coupling decisions. Search is combinatorially explosive; for
example, 85 orders moving through eight operations without
alternatives, with a single machine substitution for each and no
machine idle time has over 10@+[880] possible schedules. Many of
which may be discarded given knowledge of shop constraints. At
the core of ISIS is an approach to automatic scheduling that provides
a framework for incorporating the full range of real world
constraints that typically influence the decisions made by human
schedulers. This results in an ability to generate detailed schedules
for production that accurately reflect the current status of the shop
floor, and distinguishes ISIS from traditional scheduling systems
based on more restrictive management science models. ISIS is capable
of incrementally scheduling orders as they are received by the shop
as well as reactively rescheduling orders in response to unexpected
events (e.g. machine breakdowns) that might occur.
The construction of job shop schedules is a complex constraint-directed
activity influenced by such diverse factors as due date requirements, cost
restrictions, production levels, machine capabilities and substitutability,
alternative production processes, order characteristics, resource
requirements, and resource availability. The problem is a prime candidate
for application of AI technology, as human schedulers are overburdened by
its complexity and existing computer-based approaches provide little more
than a high level predictive capability. It also raises some interesting
research issues. Given the conflicting nature of the domain's constraints,
the problem differs from typical constraint satisfaction problems. One
cannot rely solely on propagation techniques to arrive at an acceptable
solution. Rather, constraints must be selectively relaxed in which case
the problem solving strategy becomes one of finding a solution that best
satisfies the constraints. This implies that constraints must serve to
discriminate among alternative hypotheses as well as to restrict the number
of hypotheses generated. Thus, the design of ISIS has focused on
o constructing a knowledge representation that captures the requisite
knowledge of the job shop environment and its constraints to support
constraint-directed search, and
o developing a search architecture capable of exploiting this
constraint knowledge to effectively control the combinatorics of
the underlying search space.
This presentation will provide an historical perspective on the development
of ISIS family of systems. It will focus on the evolution of its
representation of knowledge and search techniques. Performance data for
each version will be presented.