ISIS: A Constraint-Directed Reasoning Approach to Job Shop Scheduling.

Abstract

Analysis of the j(b shop scheduling domain has indicated that de crux of the scheduling problem is the determination and satisfaction of a large number and variety of constraints. Schedules arc influenced by such diverse factors as due date requirements, cost restrictions, production levels, machine capabilities, operation precedences. resource requirements, and resource availability. This paper describes 1SIS, a scheduling system capable of incorporating all relevant constraints in the construction of job shop schedules. We examine both the representation of' constraints within ISIS, and the: manter in 'hich these cor, straints are utilized in conducting a constraint-directed search for an acceptable schedule. The importat issues relating to the relaxation of constraints are addressed. Finally, the interactive scheduling facilities provided by ISIS are considered. 1. introduc,ion Tio constructi(>n of schedules to cjovern the production of orders in a job shop is a complex problem that is influenced by knowledge accumulated from many different sources in the shop. The acceptcbdity of a particular schedule depends on such diverse factors as due date requirements, cost restrictions, production levels, machine capabilities, operation precedences, resource requirements, and resource availability. Most current approaches to automatic scheduling incorporate only a fraction of this knowledge. This leads to a purely predictive o. pproach to scheduling; based on a restricted model of the environment, predictions are made as to when operations are to be performed. The resultipg schedules often bear litt!e resemblance to the factory state, leavir.'g deIdled scheduling to the shop-floor sup.rvisor. Automatic scheduling is then reduced to a weekly or monthly runs whose outpu...