A Tabu Search for Scheduling and Rescheduling Combat Aircraft

Scheduling an air campaign is a time and labor intensive task. Exacerbating this task is the fact that combat planners still make use of manual methods to accomplish much of this daunting but critical effort. While some work has been done to automate the process, the heuristics used generate schedules that must undergo major modifications before they are "flyable." Combat planners, therefore, distrust the results and use the automated features of the software sparingly. An additional problem arises due to the lag time between the publication of the Air Tasking Order (ATO) and the start of the ATO day. During this time period conditions in the dynamic battlespace can, and often do, change (aircraft break, runways may be damaged, close air support requests come in, for example). The execution software currently in use will do a validation check against the current conditions, but yields no options for replanning. This research explores the use of tabu search (TS) to determine "good" solutions for the initial air campaign plan. It extends previous work by including air-tasking priorities.