Learning to improve constraint-based scheduling

摘要

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 computational efficiency of a scheduling system suffers due to 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 and ground processing.