Learning Search Control for Constraint-Based Scheduling

This paper describes an application of an analytical learning technique, Plausible Explanation-Based Learning (PEB L), 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.

Authors

• Megan Eskey
• Monte Zweben

Keywords

No keywords are indexed for this paper.