Learning Search Control for Constraint-Based Scheduling

Megan Eskey and Monte Zweben

This paper describes an application of an analytical learning technique, Plausible Explanation-Based Learning (PEBL), that dynamically acquires search control knowledge for a constraint-based scheduling system. In general, the efficiency of a scheduling system suffers because of resource contention among activities. Our system learns the general conditions under which chronic contention occurs and uses search control to avoid repeating mistakes. Because it is impossible to prove that a chronic contention will occur with only one example, traditional EBL techniques are insufficient. We extend classical EBL by adding an empirical component that creates search control rules only when the system gains enough confidence in the plausible explanations. This extension to EBL was driven by our observations about the behavior of our scheduling system when applied to the real-world problem of scheduling tasks for NASA Space Shuttle payload processing. We demonstrate the utility of this approach and provide experimental results.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.