A scheduling algorithm for time-constrained model-based diagnosis

A meta-level reasoning module for time-constrained diagnosis using hierarchical behavioural (physical "part-of") models is proposed, its goal being to direct a model-based diagnostic engine such that the optimum trade-off between computation time and solution quality is found. The problem is defined as the task of finding the order in which to explore candidate components at differing levels within the model hierarchy, such that (a) the total repair cost of the final diagnosis is minimised, and (b) the computation is performed within the multiple deadlines attached to the suspect components. This is a bi-criterion scheduling 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 engine from the meta-level reasoning module (termed here the Diagnostic Supervisor). A scheduler called the Time-Limited Candidate Selector (TLCS) is proposed, which forms the heart of the Diagnostic Supervisor. Its performance is compared to those of the two schedulers from which it was derived: WSPT (weighted shortest processing time) and Hodgson's algorithm. In tests using a three-layer behavioural model of a crude-oil distillation unit, the TLCS algorithm is shown to outperform both of its parents. © 1998 Elsevier Science Ltd. All rights reserved.