Operational-level planners in Maritime Operations Centers aim to assign naval forces in support of combatant commanders efficiently and effectively, but they lack a software-based planning tool to develop optimal ship employment schedules. They must assign ships to particular missions spread throughout numerous regions over a particular time horizon to meet the combatant commander's force requirements. Currently, this is a manual process. We present Navy Mission Planner (NMP), a decision aid based on an integer linear program that allows efficient generation of candidate employment schedules. NMP uses constrained, stack-based enumeration of candidate employment schedules over the feasible region. Total enumeration can produce an enormous number of schedules--easily reaching quadrillions of feasible solutions. By constraining the enumeration to eliminate impractical schedules, we can manage the computational burden and provide the naval planner useful solutions containing a near-optimal set of employment schedules for each assigned ship over the planning horizon. We submit a realistic scenario and provide a credible, face-valid solution to the multi-ship, multi-mission assignment problem, with sets of employment schedules that are as good as or better than sets produced manually.
Carlyle, W. Matthew
Naval Postgraduate School (U.S.)
Naval Postgraduate School
Approved for public release; distribution is unlimited.