Adaptive Problem-solving for Large-scale Scheduling Problems: A Case
  Study
  Although most scheduling problems are NP-hard, domain specific techniques
perform well in practice but are quite expensive to construct. In adaptive
problem-solving solving, domain specific knowledge is acquired automatically
for a general problem solver with a flexible control architecture. In this
approach, a learning system explores a space of possible heuristic methods for
one well-suited to the eccentricities of the given domain and problem
distribution. In this article, we discuss an application of the approach to
scheduling satellite communications. Using problem distributions based on
actual mission requirements, our approach identifies strategies that not only
decrease the amount of CPU time required to produce schedules, but also
increase the percentage of problems that are solvable within computational
resource limitations.
