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

Laura Barbulescu, L. Darrell Whitley, and Adele E. Howe

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.

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.