Integrating CBR and Heuristic Search to Solve Complex Real-Time Scheduling Problems

Contents

This paper presents the Case-Based Reasoning Real-Time Scheduler system (CBR- RTS), that integrates into a case-based reasoning framework a heuristic search component to solve complex real-time scheduling problems. The problem addressed involves scheduling sets of tasks with precedence, ready time and deadline constraints. CBR-RTS uses the solution of known problems (cases) to simplify and solve new problems. When the systems does not have applicable cases, the new problem, complete or already simplified, is passed to a learning algorithm that searches for a solution using a dedicated algorithm, currently an implementation of a searching algorithm proposed by Xu and Parnas. A particularly interesting feature of CBR-RTS is its learning ability. New problems solved by the learning module can be added to the case base for future reuse. Performed tests show that small bases of cases carefully chosen allow to substantially reduce the time needed to solve new complex problems.