AFSCN scheduling: How the problem and solution have evolved

The Air Force Satellite Control Network (AFSCN) coordinates communications to more than 100 satellites via nine ground stations positioned around the globe. Customers request an antenna at a ground station for a specific time window along with possible alternative slots. Typically, 500 requests per day result in more than 100 conflicts, which are requests that cannot be satisfied because other tasks need the same slot. Scheduling access requests is referred to as the Satellite Range Scheduling Problem (SRSP). This paper presents an overview of three key issues: (1) how has the problem changed over the last 10 years, (2) what algorithms work best and (3) what objective function is appropriate for AFSCN. We compared data sets from 1992 and from 2002/2003 and found significant differences in the problems. Our evaluation of solutions focuses on three algorithms: local search, Gooley's algorithm from AFIT, and the Genitor genetic algorithm. It can be shown that local search (and therefore metaheuristics based on local search) fail to compete with Gooley's algorithm and Genitor. Finally, while all prior work on AFSCN minimizes request conflicts, we explore an alternative objective function. Because human schedulers must eventually schedule all requests, it might be better to optimize schedules for "repairability". Our results suggest that minimizing schedule overlaps makes it easier to fit larger requests into the schedule. (c) 2005 Elsevier Ltd. All fights reserved.