Learning from failure experiences in case-based schedule repair

Abstract

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. In CABINS, case-based reasoning is used for eliciting situation-dependent user's tradeoffs about repair actions and schedule quality to guide schedule revision for quality improvement. During iterative repair, cases are exploited for multiple purposes, such as (1) repair action selection, (2) evaluation of 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 taking into consideration failure information improves the efficiency of rather costly iterative repair process. The experiments in this paper were performed in the context of job shop scheduling problems.