A SCHEDULING ALGORITHM FOR TIME-CONSTRAINED MODEL-BASED DIAGNOSIS

A meta-level reasoning module for time-constrained diagnosis using hie rarchical behavioural (physical ''part-of'') models is proposed. its g oal bring to direct a model-based diagnostic engine such that;the opti mum trade-off between computation time and solution quality is found. The problem is defined as the task of finding the order in which to ex plore candidate components at differing levels within the model hierar chy, such that (a) the total repair cost of the final diagnosis is min imised, and (b) the computation is performed within the multiple deadl ines attached to the suspect components. This is a bi-criterion schedu ling problem, time and cost being the two factors that are taken into account during evaluation of the ordering of diagnostic jobs. A simple architecture is presented that elegantly separates the diagnostic eng ine from the meta-level reasoning module (termed here the Diagnostic S upervisor). A scheduler called the Time-Limited Candidate Selector (TL CS) is proposed, which forms the heart of the Diagnostic Supervisor. I ts performance is compared to those of the two schedulers from which i t was derived: WSPT (weighted shortest processing time) and Hodgson's algorithm. In tests using a three-layer behavioural model of a crude-o il distillation unit, the TLCS algorithm is shown to outperform both o f its parents. (C) 1998 Elsevier Science Ltd. All rights reserved.