Live Webcast 15th Annual Charm++ Workshop

Parallel Computing for DoD Airlift Allocation
PPL Technical Report 2012
Publication Type: Paper
Repository URL:
This research demonstrates the applicability of parallel computing to Air Mobility Command's aircraft allocation problem. The Tanker Airlift Control Center (TACC) is responsible for worldwide tasking of DoD airlift in a manner that is robust against random future events. Our work seeks to improve this process using a parallel stochastic mathematical program that allocates aircraft to various mission sets during a planning cycle. To reconcile real-world mission changes, we incorporate random realizations of the subsequent cycle's execution, accounting for humanitarian/wartime contingencies, cargo fluctuations, aircraft breakdowns, and short-notice special missions. The technical approach employs a two-stage stochastic mixed-integer program with complete recourse. The first stage allocates aircraft by home base and aircraft type using information provided from second-stage schedules of 100+ possible future outcomes. Parallel processors compute these second stage realizations, each of which is a moderately sized linear program. The first and parallelized second stages provide mutual feedback to convergence using multi-cut Benders' decomposition. Results on several prototype problems indicate a parallel processing speedup of over eight times the single-processor computation time; parallelizing the first stage holds greater promise for more detailed modeling. Additionally, we demonstrate a significant benefit from a small allocation adjustment: preserving a modest airlift reserve capacity incurs minor additional expense, but is enormously cost-effective when the future requirements turn out to be higher than expected. These results provide the prelude for additional research that will scale problem complexity and realism to the realm of operational TACC allocations.
Research Areas