Leap Before You Look: An Effective Strategy in an Oversubscribed Scheduling Problem

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 19

Constraint Satisfaction and Satisfiability

Oversubscribed scheduling problems require removing or partially satisfying tasks when enough resources are not available. For a particular oversubscribed problem, Air Force Satellite Control Network scheduling, we find that the best approaches make long leaps in the search space. We find this is in part due to large plateaus in the search space. Algorithms moving only one task at a time are impractical. Both a genetic algorithm and Squeaky Wheel Optimization (SWO) make long leaps in the search space and produce good solutions almost 100 times faster than local search. Greedy initialization is shown to be critical to good performance, but is not as important as directed leaps. When using fewer than 2000 evaluations, SWO shows superior performance; with 8000 evaluations, a genetic algorithm using a population seeded with greedy solutions further improves on the SWO results.