Abstract
This paper addresses the "utility problem" in Case-Based Reasoning (CBR) systems applied to complex optimization tasks like job-shop scheduling. By introducing filtering mechanisms—Validated, Interruptive, and Hybrid—that utilize past failure experiences to prune the search space, the authors demonstrate significant improvements in computational efficiency. Experimental results using the CABINS system show that hybrid filtering can reduce tactic applications by approximately 65% compared to unfiltered systems, effectively mitigating "stubbornness" and "greediness" in iterative optimization.
Introduction
In the development of Case-Based Reasoning (CBR) systems, a common assumption was that increasing the size of the knowledge base would lead to better performance. However, researchers eventually encountered the "utility problem," where the overhead of searching, matching, and storing vast amounts of knowledge outweighs the benefits. This is particularly evident in "ill-structured" optimization problems like job-shop scheduling, where no perfect mathematical model exists to predict the ripple effects of schedule repairs.
This study focuses on CABINS, a system that learns to optimize schedules by storing cases of successful and unsuccessful repairs. Without filtering, CABINS often becomes "greedy" (applying tactics with low similarity) and "stubborn" (persisting with repairs likely to fail), leading to degraded system performance.
Knowledge Filtering Strategies
To combat the utility problem, the authors propose three information filters that leverage failure experiences to guide the search process:
- Validated Filtering: This tactic-level filter checks a proposed repair against past failure cases. If the current state is too similar to previous failures for that specific tactic, the repair is rejected before execution.
- Interruptive Filtering: This task-level filter evaluates whether a specific activity is even repairable. If past experiences indicate a high probability of failure for the current problem state, the system skips the repair attempt entirely to save time.
- Hybrid Filtering: A serial combination of both strategies, where the system first decides if a repair is worth attempting (Interruptive) and then validates the specific chosen tactic (Validated).
These filters utilize a $k$-Nearest Neighbor approach to statistically estimate success likelihood based on the "similarity sum" of past failures, providing a robust mechanism for pruning without requiring a deep domain model.
Experimental Evaluation
The filtering strategies were evaluated using a benchmark suite of job-shop scheduling problems consisting of 10 orders with 5 activities each. A massive library of 12,000 cases was generated using a greedy Rule-Based Optimizer (RBR) to serve as training data. The researchers employed cross-validation across 60 randomly generated problems to compare the performance of unfiltered CBR, the RBR baseline, and the new filtering strategies.
Key Results and Discussion
The experimental results demonstrate that failure-based filtering significantly enhances system efficiency. As shown in the performance data, the Hybrid filtering strategy (H) achieved the most dramatic improvements.
Efficiency Gains
The Hybrid model reduced the number of tactic applications by approximately 65% compared to the Unfiltered system (776.6 vs. 2206.2). CPU time followed a similar trend, dropping from 551.1 seconds to 424.1 seconds. This proves that the computational overhead of the filtering logic is far lower than the cost of executing failed repair attempts.
Solution Quality
While the Unfiltered system produced the lowest solution cost (698.8), the filtered systems maintained costs (e.g., 753.4 for Hybrid) that were comparable to the standard Rule-Based Optimizer (752.4). The results suggest that filtering effectively prevents the system from taking "shots in the dark," trading a small amount of potential quality for a massive gain in reliability and speed.
Conclusion
This research highlights that in complex search spaces, failure is often a better teacher than success. By setting a "credibility threshold" through filtering, CBR systems can avoid the greediness trap and focus computational resources on high-probability repairs. Future work will focus on the automated adaptation of filtering parameters to allow systems to dynamically tune their thresholds for different problem domains.
Summary updated