Improving Schedule Quality through Case-Based Reasoning

Planning and Scheduling

We describe a framework, implemented in CABINS, for iterative schedule revision based on acquisition and reuse of user optimization preferences to improve schedule quality. Practical scheduling problems generally require allocation of resources in the presence of a large, diverse and typically conflicting set of constraints and optimization criteria. The ill-structuredness of both the solution space and the desired objectives make scheduling problems difficult to formalize. CABINS records situation-dependent tradeoffs about repair actions and schedule quality to guide schedule improvement. During iterative repair, cases are exploited for: (1) repair action selection, (2) evaluation intermediate repair results and (3) recovery from revision failures. The contributions of the work lie in experimentally demonstrating in a domain where neither the user nor the program possess causal knowledge of the domain that (a) taking into consideration failure information in the form of failed cases or a repair history of a case improves schedule quality, (b) schedule quality improves with increasing case size and (c) preserving the case base rather than inducing rules gives better results.