Modeling Local Search: A First Step Toward Understanding Hill-climbing Search in Oversubscribed Scheduling ∗

Previous results for a real-world domain, scheduling communications requests for the Air Force Satellite Control Network (AFSCN), suggested that the best search methods perform a greedy random walk. We examine the degree to which this observation is accurate for AFSCN by modeling a next-descent hill-climbing search as a Markov process. We find that the model is somewhat accurate for AFSCN. To generalize, we apply this model to another oversubscribed scheduling problem: scheduling image requests for a set of Earth Observing Satellites (EOS). We find that the hill-climber follows a trajectory that can be modeled as a Markov process. Hill-Climbing Search as a Markovian Process A Genetic Algorithm (GA), Squeaky Wheel Optimization (SWO), and a simple Hill-Climber (HC) have been shown to perform well for AFSCN scheduling (Barbulescu, Whitley, & Howe 2004). Simulated Annealing (SA) and HC perform best for EOS scheduling (Globus et al. 2004). All these methods use a permutation representation with some combination of stochastic motion and simultaneous moves. The GA selects approximately half the tasks for movement and is at the far end of multi-move, disruptive motion. The HC is at the other end of single-move, step-wise motion. SA follows a similar path as the HC, but relaxes the greedy bias by allowing uphill moves; its behavior approaches that of the HC as search progresses. SWO selects a subset of ’troublesome’ tasks to move and is between the extreme moves of the GA and the small steps of the HC. Researchers for AFSCN and EOS identify the underperformance of heuristic search in these domains, but it isn’t clear exactly why this is the case. A simple hypothesis is that these methods lack a suitable ordering heuristic. Underlying this hypothesis is an implicit belief that the bette