Collaborative proposal: Optimization for Submarine Scheduling
Abstract
The Navy regularly assigns submarines to events, which occur on a regular basis or unexpectedly. Example events include maintenance,activities, training exercises, and deployment to critical missions. There is choice to how and when the submarines should be alloca,ted and these are subject to constraints such as whether the crews are available, what state the submarine is in, and whether an eve,nt can be feasibly completed by a particular submarine. Moreover, there are trade-offs among completing missions of varying prioriti,es.There is a critical need for the Navy to solve this important scheduling problem effectively to operate highly valuable submarine,s. This proposal aims to i) formulate the problem as an optimization problem and ii) solve it fast. As a result, feasible and nearly, optimal schedules will be produced fast. The formulation will capture various constraints and be used to compare different schedule,s by their objective. The objective will provide clear explanations for whysome schedules are more recommendable. To achieve the goa,l, the objective will consider the event priorities and the expense (of sacrificing some events) to accommodate more important event,s, and possibly more. To solve the optimization problem efficiently, we will use various techniques such as sketching and warm-start,ing the algorithm by machine learning. The proposal will consider various forms of inputs, depending on when and how the inputs are,revealed, which include fully offline model, stochastic arrival model and worst-case arrival model. The algorithmic solutions, inclu,ding IP programming and heuristics, will be tested with synthetic and real-world inputs as available. By the empirical evaluation o,f them the PIs will identify challenging instances and tune up the algorithms accordingly. The PIs will also perform retrospective a,nalysis to compare the actual solutions produced online to the optimum solution obtained with access to the whole input in hindsight,. The optimization codes will be integrated into the visualization tool in use by the Navy. Although the proposal s primary goal is, to formulate the scheduling problem as an optimization problem and yield an optimization module the Navy can use, the project will,also have the following other impacts as byproducts. The project will implement several algorithmic ideas to evaluate their effectiv,eness. Thus, it has a high potential to demonstrate the power of the new algorithmic ideas and give positive feedback to the cutting,-edge scheduling research. Further, the project will involve graduate students who are US citizens and they will learn valuable skil,ls to formulate real world scheduling problems into an optimization problem and make algorithmic ideas work in practice. Approved fo,r Public Release.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212702
Entities
People
- Benjamin Moseley
Organizations
- Carnegie Mellon University
- Office of Naval Research
- United States Navy