Resource Allocation Modeling Applied to Air Force Crew Scheduling: An Advanced Analytics Case Study
Building upon our work with the 20th Air Force with TimePiece™, Kepler internally developed, as a partnership with the George Mason University Systems Engineering and Operations Research (SEOR) department, the Resource Allocation Model to optimally assign personnel and assets to fulfill critical mission requirements in minimal time.
Introduction and Problem Statement
The 20th Air Force maintains and operates the Air Force’s Intercontinental Ballistic Missile (ICBM) force, providing on-alert, combat-ready ICBMs to the President of the United States. The ICBM mission requires staffing trained and certified personnel for alerts at geographically separated operation centers (op centers). Personnel must be scheduled for daily alerts, monthly training, and annual certifications.
The current scheduling process is manual and time-consuming, with many tradeoffs, conflicting availability, and limited training capacity. Schedulers create the monthly schedule for the following month; however, during execution of the schedule, unanticipated events or changes often cause substantial rework. With so many moving parts and numerous constraints, the 20th Air Force needed a way to automate the scheduling tasks while also being flexible to respond to changing conditions.
Currently schedulers create the monthly schedule using TimePiece™, a software product developed by Kepler to facilitate scheduling and provide visibility throughout the organization. TimePiece™ has enhanced the effectiveness of the scheduling process; however it does not provide the ability to optimally allocate resources and is not dynamic to respond to last minute changes.
Kepler’s Solution: The Resource Allocation Model
We utilized linear programming (LP) and integer programming (IP) techniques to develop a mixed-integer program (MIP) for assigning resources to requirements. The model executes in four phases. Each phase consists of running a mathematical program to perform a series of assignments, and contains several parameter assignments to be used in subsequent mathematical program execution phases. The model initially creates the “original schedule” – the monthly schedule for alerts and training for the following month. During the month the original schedule is being executed, the model has two methods to address daily changes in personnel availability and creates a “new schedule”, as necessary.
To solve a MIP, the model is sent to a commercial solver, such as CPLEX or Gurobi, that uses various algorithms and techniques to solve the mathematical program. For this model, there were 4 mathematical programs to solve, one for each phase, each with a different set of decision variables. After executing the model, the solver found an integer solution after 3 hours within 1.97% of the LP-upper bound. The LP upper-bound results from the LP-relaxation, which allows integer variables to take on fractional values. The LP upper-bound is not feasible for an integer program, however it gives us an idea of the best solution. Our goal is to reduce the gap between our integer solution and the LP upper-bound. After running test scenarios to determine the tradeoff between solution time and the solution’s gap to the LP upper-bound, we found that the solution after 3 hours was the optimal integer solution.
The Resource Allocation problem is a common issue seen in almost every organization. Its difficulty arises out of having numerous conflicting resource availabilities and countless constraints on when, where, and how resources can be assigned, not to mention interdependencies among the resources that also impact their assignment. The 20th Air Force historically dealt with this problem manually by getting all the various schedulers and resource managers into a room for 1-2 weeks and letting them hash out a schedule for the following month. This process was costly and very time consuming, and the 20th Air Force needed a better solution. We developed a model that quickly optimizes the allocation of 20th Air Force resources, significantly reducing the time required to complete the monthly schedules from 1-2 weeks to about 3 hours, and producing a solution within 2% of optimality. The model ensures the allocation of resources is balanced across the force, and allows schedulers to quickly address unforeseen changes in resource availability and still fulfill critical mission requirements.