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 submarin,es. This proposal aims to i) formulate the problem as an optimization problem and ii) solve it fast. As a result, feasible and nearl,y optimal schedules will be produced fast. The formulation will capture various constraints and be used to compare different schedul,es by their objective. The objective will provide clear explanations for why some schedules are more recommendable. To achieve the g,oal, the objective will consider the event priorities and the expense (of sacrificing some events) to accommodate more important eve,nts, and possibly more. To solve the optimization problem efficiently, we will use various techniques such as sketching and warm-sta,rting the algorithm by machine learning. The proposal will consider various forms of inputs, depending on when and how the inputs ar,e revealed, which include fully offline model, stochastic arrival model and worst-case arrival model. The algorithmic solutions, inc,luding IP programming and heuristics, will be tested with synthetic and real-world inputs as available. By the empirical evaluation, of them the PIs will identify challenging instances and tune up the algorithms accordingly. The PIs will also perform retrospective, analysis to compare the actual solutions produced online to the optimum solution obtained with access to the whole input in hindsig,ht. 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 wil,l also have the following other impacts as byproducts. The project will implement several algorithmic ideas to evaluate their effect,iveness. Thus, it has a high potential to demonstrate the power of the new algorithmic ideas and give positive feedback to the cutti,ng-edge scheduling research. Further, the project will involve graduate students who are US citizens and they will learn valuable sk,ills to formulate real world scheduling problems into an optimization problem and make algorithmic ideas work in practice. Approved,for Public Release.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 08, 2022
- Source ID
- N000142212701
Entities
People
- Sungjin Im
Organizations
- Office of Naval Research
- United States Navy
- University of California