Search

Every day, the Los Angeles County Fire Department uses weather forecasts and automated real-time weather observations, together with field-tested moisture content of soil and vegetation, to decide whether and where to position firefighting equipment and personnel, as well as what equipment to use, for the following day. Anticipating a particularly hazardous “red flag” day, they activate off-duty personnel and reserve equipment and add these to the total augmented, prepositioned force. Analysis of years of detailed daily data can advise these costly decisions. Three models, respectively, predict for each region of the county the probability of a fire start, the area burned by a fire given any particular package of equipment and personnel preassigned to fight it, and which packages to form and send to each position. The conflicting objectives are to minimize the expected number of citizens evacuated and the constrained augmentation cost for personnel and equipment.

This paper studies the resilience of the regional highway transportation system of the San Francisco Bay Area. Focusing on peak periods for commuter traffic, traffic patterns are computed from a model that includes nonlinear increases in travel times due to congestion and reflects actual travel demands as captured by U.S. Census demographic data. We consider the consequences associated with loss of one or more road, bridge, and/or tunnel segments, where travelers are allowed to reroute to avoid congestion or potentially not travel at all if traffic is bad. We use a sequential game to identify sets of road, bridge, or tunnel segments whose loss results in worst-case travel times. We also demonstrate how the model can be used to quantify the operational resilience of the system, as well as to characterize trade-offs in resilience for different defensive investments, thus providing concise information to guide planners and decision makers.

We introduce a simple modification to the repeated shortest-path algorithm for the all-pairs shortest-path problem that adds a cumulative distance label update at each iteration based on the shorte...

On the surface of a sphere, we take as inputs two points, neither of them contained in any of a number of spherical polygon obstacles, and quickly find the shortest route connecting these two points while avoiding any obstacle. The WetRoute method presented here has been adopted by the US Navy for several applications. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 374–385, 2016

The article of record as published may be found at http://dx.doi.org/10.1287/inte.2014.0780 The 2013 UPS George D. Smith Prize was awarded to the Naval Postgraduate School’s (NPS) Operations Research (OR) department for “effective and innovative preparation of students to be good practitioners of operations research, management science, or analytics.” In the spirit of the prize, this paper shares details about our degree program. The program is closely linked to its military sponsor, the United States Department of Defense, in a unique relationship that ensures NPS students and faculty are focused on critical and important problems facing the military. Our students bring firsthand knowledge of the challenges our organization faces, and leave our academic program as OR practitioners prepared to immediately meet those challenges.

The authors propose a definition of infrastructure resilience that is tied to the operation (or function) of an infrastructure as a system of interacting components and that can be objectively evaluated using quantitative models. Specifically, for any particular system, the authors use quantitative models of system operation to represent the decisions of an infrastructure operator who guides the behavior of the system as a whole, even in the presence of disruptions. Modeling infrastructure operation in this way makes it possible to systematically evaluate the consequences associated with the loss of infrastructure components, and leads to a precise notion of “operational resilience” that facilitates model verification, validation, and reproducible results. Using a simple example of a notional infrastructure, the authors demonstrate how to use these models for (1) assessing the operational resilience of an infrastructure system, (2) identifying critical vulnerabilities that threaten its continued function, and (3) advising policymakers on investments to improve resilience.

Military Operations Research, 18(3), pp. 35-52. The article of record as published may be located at http://dx.doi.org/10.5711/1082598318335 The Air Tasking and Efficiency Model (ATEM) has been used since 2006. Its development was motivated by an urgent need to plan and evaluate intratheater airlift of passengers and palletized freight for Operation Iraqi Freedom in Iraq and Operation Enduring Freedom in Afghanistan ATEM plans routes and aircraft configurations (capacity of passenger seats and pallet positions) for heterogeneous fleet of aircraft flying between multiple airfields. ATEM respects limits on crew duty periods, times and abilities of each airfield to handle and fuel each aircraft type, and aircraft speed and carrying capacity. Initially, ATEM advised improving daily and weekly route ensembles, conveying more passengers and pallets and using fewer aircraft than prior manually generated solutions. This early use reduced the required number of ground convoys and thereby exposure to improvised explosive devises. Later, ATEM advised where to advantageously move aircraft to new home airfields, how to shift aircraft between theaters, and when to bring aircraft home from war.

Military Operations Research, 18(1), pp. 21-37. The article of record as published may be located at http://dx.doi.org/10.5711/1082598318121 This paper shows that no simple, common-sense rule of thumb can be used to identify a most-vital arc, even in a simple maximum-flow problem. The correct answer requires analysis equivalent in difficulty to completely solving the maximum-flow problem, perhaps repeatedly. This insight generalizes to finding a most-vital component, or set of components, in a system whose operations is described by a more general model. Our paper shows how to evaluate the criticality of sets of components, how to assess the worst-case set of components that might be lost to a given number of simultaneous hostile attacks (or engineering failures, or losses to Mother Nature), and how to allocate limited defensive resources to minimize the maximum damage from subsequent attack. Collateral insights include the fact that there is no way to prioritize individual components by critically, and the the analysis that determines critical component sets also yields objective assessments of operations system resilience and can provide constructive advice on how to increase it.

We develop a game-theoretic model called BASTION to guide the employment of antisubmarine warfare (ASW) platforms such as ships and aircraft that are defending a stationary oceanic bastion from attack by hostile submarines. The model is an example of a two-person zero-sum game with some additional variables (ship locations) that are under the control of the maximizing defender, but known to the minimizing attacker. The attacker knowing the ship locations, but not the locations of other platforms such as aircraft, must select a path to the bastion. The probability of detecting the attacker as it follows this path is the objective shared by the opponents.

© 2009 Wiley Periodicals, Inc. Naval Research Logistics 58: 281–295, 2011 The article of record as published may be located at http://dx.doi.org/DOI 10.1002/nav.20377

The U.S. Coast Guard, Customs and Border Patrol, Marine Corps, and Navy have deployed several hundred port patrol vessels to protect waterways, U.S. Navy ships and other high-value assets in ports world-wide. Each vessel has an armed crew of four, is relatively fast, and features a surface search radar, radios, and a machine gun. These vessels coordinate surveillance patrols in groups of two or four. We developed a mathematical model for advantageously positioning these vessels, and possibly shore-based radar too, to minimize the probability that an intelligent adversary in one or more speedboats will evade detection while mounting an attack. Attackers can use elevated obstructions to evade radar detection in their attack paths, and ports feature many such restrictions to navigation and observation. A key, but realistic assumption complicates planning: the attackers will be aware of defensive positions and capabilities in advance of mounting their attack. The defender-attacker optimization suggests plans here for a fictitious port, the port of Hong Kong, and the U.S. Navy Fifth Fleet Headquarters in Bahrain. In these cases, the defender can almost certainly detect any attack, even though the attacker, observing defender prepositioning, plans clever, and evasive attack tracks. Published 2011 Wiley Periodicals, Inc.† Naval Research Logistics, 2011

We evaluate what distinguishes a highly cited Interfaces paper from other Interfaces papers that are cited less often. Citations are used to acknowledge prior relevant research, to document sources of information, and to substantiate claims. As such, citations play a key role in the evolution of knowledge. More recently, citations are also being used to quantify the impact of papers and journals, a practice not without controversy, but one that motivates our work here. We find that Edelman competition papers, longer papers, tutorials, papers with larger numbers of references to prior literature, and papers with a larger number of “callouts” (a feature no longer used by Interfaces) tend to have a higher number of citations.

A “proliferator” seeks to complete a first small batch of fission weapons as quickly as possible, whereas an “interdictor” wishes to delay that completion for as long as possible. We develop and solve a max-min model that identifies resource-limited interdiction actions that maximally delay completion time of the proliferator's weapons project, given that the proliferator will observe any such actions and adjust his plans to minimize that time. The model incorporates a detailed project-management (critical path method) submodel, and standard optimization software solves the model in a few minutes on a personal computer. We exploit off-the-shelf project-management software to manage a database, control the optimization, and display results. Using a range of levels for interdiction effort, we analyze a published case study that models three alternate uranium-enrichment technologies. The task of “cascade loading” appears in all technologies and turns out to be an inherent fragility for the proliferator at all levels of interdiction effort. Such insights enable policy makers to quantify the effects of interdiction options at their disposal, be they diplomatic, economic, or military.

We study how changes to the composition and employment of the US Navy combat logistic force (CLF) influence our ability to supply our navy worldwide. The CLF consists of about 30 special transport ships that carry ship and aircraft fuel, ordnance, dry stores, and food, and deliver these to client combatant ships underway, making it possible for our naval forces to operate at sea for extended periods. We have modeled CLF operations to evaluate a number of transforming initiatives that simplify its operation while supporting an even larger number of client ships for a greater variety of missions. Our input is an employment schedule for navy battle groups of ships operating worldwide, extending over a planning horizon of 90–180 days. We show how we use optimization to advise how to sustain these ships. We have used this model to evaluate new CLF ship designs, advise what number of ships in a new ship class would be needed, test concepts for forward at-sea logistics bases in lieu of conventional ports, demonstrate the effects of changes to operating policy, and generally try to show whether and how the CLF can support planned naval operations. Published 2008 Wiley Periodicals, Inc. Naval Research Logistics 2008

Practitioners of optimization-based decision support advise commerce and government on how to coordinate the activities of millions of people who employ assets worth trillions of dollars. The contributions of these practitioners substantially improve planning methods that benefit our security and welfare. The success of real-world optimization applications depends on a few trade secrets that are essential, but that rarely, if at all, appear in textbooks. This paper summarizes a set of these secrets and uses examples to discuss each. “Thou shalt never get such a secret from me but by a parable.” Shakespeare, The Two Gentlemen of Verona

FATHM is a large-scale attrition model of two-sided ground combat, including air strikes by Blue on Red. While FATHM has borrowed extensively from other combat models, it also exhibits some unique features, particularly its use of linear programming calls to solve a sequence of air-to-ground engagements that are interspersed among ground-to-ground engagements. In spite of making hundreds of such calls, FATHM can still fight a realistically-scaled theater war in about three minutes on a personal computer. This paper gives the genesis and essential features.

“Convincing yourself is easy, persuading a colleague is harder, but proving it to a computer is hardest of all!”—R. Hamming, ca 1985. The art of formulating linear and integer linear programs is, well, an art: It is hard to teach, and even harder to learn. To help demystify this art, we present a set of modeling building blocks that we call “formulettes.” Each formulette consists of a short verbal description that must be expressed in terms of variables and constraints in a linear or integer linear program. These formulettes can better be discussed and analyzed in isolation from the much more complicated models they comprise. Not all models can be built from the formulettes we present. Rather, these are chosen because they are the most frequent sources of mistakes. We also present Naval Postgraduate School (NPS) format; a define-before-use formulation guide we have followed for decades to express a complete formulation.

We propose a definition of infrastructure resilience that is tied to the operation (or function) of an infrastructure as a system of interacting components and that can be objectively evaluated using quantitative models. Specifically, for any particular system, we use quantitative models of system operation to represent the decisions of an infrastructure operator who guides the behavior of the system as a whole, even in the presence of disruptions. Modeling infrastructure operation in this way makes it possible to systematically evaluate the consequences associated with the loss of infrastructure components, and leads to a precise notion of "operational resilience" that facilitates model verification, validation, and reproducible results. Using a simple example of a notional infrastructure, we demonstrate how to use these models for (1) assessing the operational resilience of an infrastructure system, (2) identifying critical vulnerabilities that threaten its continued function, and (3) advising policymakers on investments to improve resilience.

We describe the industrial project that a “proliferator” would conduct to produce a first, small batch of nuclear weapons. From refining yellowcake ore to final weapons assembly, we highlight the project's tasks and their interactions. The proliferator can choose alternative production technologies that offer quicker completion, but at higher cost in terms of limited resources. The proliferator can also expedite his project by devoting more resources to critical tasks. From physics and chemistry, we determine raw material requirements. From industrial engineering and materials science, we convert these requirements into estimates of the time, manpower, energy, and money required to complete each task under normal and expedited conditions. Using generalized project-management analysis tools, we then estimate the earliest possible completion time of the project, assuming two different levels of resource availability. We also estimate the time required to complete a weapon if some of the project's steps can ...

We describe JOINT DEFENDER, a new two-sided optimization model for planning the pre-positioning of defensive missile interceptors to counter an attack threat. In our basic model, a defender pre-positions ballistic missile defense platforms to minimize the worst-case damage an attacker can achieve; we assume that the attacker will be aware of defensive pre-positioning decisions, and that both sides have complete information as to target values, attacking-missile launch sites, weapon system capabilities, etc. Other model variants investigate the value of secrecy by restricting the attacker’s and/or defender’s access to information. For a realistic scenario, we can evaluate a completely transparent exchange in a few minutes on a laptop computer, and can plan near-optimal secret defenses in seconds. JOINT DEFENDER’s mathematical foundation and its computational efficiency complement current missile-defense planning tools that use heuristics or supercomputing. The model can also provide unique insight into the value of secrecy and deception to either side. We demonstrate with two hypothetical North Korean scenarios.

Planning United States military procurement commits a significant portion of our nation's wealth and determines our ability to defend ourselves, our allies, and our principles over the long term. Our military pioneered and has long used mathematical optimization to unravel the distinguishing complexities of military capital planning. The succession of mathematical optimization models we present exhibits increasingly detailed features; such embellishments are always needed for real-world, long-term procurement decision models. Two case studies illustrate practical modeling tricks that are useful in helping decision makers decide how to spend about a trillion dollars.

United States Air Force Space Command spends billions of dollars each year acquiring and developing launch vehicles and space systems. The space systems in orbit must continually meet defensive and offensive requirements and remain interoperable over time. Space Command can launch additional space systems only if it has a launch vehicle of sufficient capability. Space planners using space and missile optimization analysis (SAMOA) consider a 24-year time horizon when determining which space assets and launch vehicles to fund and procure. A key tool within SAMOA is an integer linear program called the space command optimizer of utility toolkit (SCOUT) that Space Command uses for long-range planning. SCOUT gives planners insight into the annual funding profiles needed to meet Space Command's acquisition goals. The 1999 portfolio of 74 systems will cost about $310 billion and includes systems that can lift satellites into orbit; yield information on space, surface, and subsurface events, activities, and threats; and destroy terrestrial, airborne, and space targets.

Interfaces, 32, pp. 1-14. A plant line schedule specifies a plant's sustained batch operations over time with detail sufficient to manage all activities. Plantwide considerations include restrictions on how production centers can be formed from production lines, packaging lines, conveyers, and so forth; the cost and time of product-package item setups, changeovers, and shutdowns; honoring instock service levels, minimum inventory, and committed shipments; recognizing efficiency gains with longer batch runs; respecting crew constraints; and the costs of materials, labor, and carrying inventory. We developed a cost-minimizing optimization model, PROFITS, that features multiple independent time streams for various categories of events that mimic existing periodic reviews of operations. PROFITS is embedded in a graphical user interface that eases the grueling aspects of scheduling, preparing data, controlling scenarios, and visualizing results. At Hidden Valley Manufacturing Company, completing an eight-week plant-line schedule takes about an hour. This is much faster than manual scheduling was-and the schedules are better.

Although Ezell claims that we only “repackaged in a new article the limitations identified by Ezell et al. of PRA in terrorism risk analysis,” he neither addresses nor refutes any of our substantive technical points and examples, and his comments reflect a fundamental lack of understanding of our main ideas. We are therefore grateful for this opportunity to clarify our reasoning in light of his comments, as follows.

The Operations Research Department at the Naval Postgraduate School educates experienced junior military officers in state-of-the-art operations research methods. As part of the educational program all officers go through a standard graduate course on network modeling. Within that course, students complete a class-long network modeling project of a real-world infrastructure system that solidifies their understanding of operations research concepts and moves the learning experience beyond the classroom. Through the project, students abstract their real-world problems into mathematics, repeatedly evaluate the connection between the mathematics and reality, and reason about the model results. The project has educational, research, and practical benefits. On occasion, students make discoveries of such significance that we have contacted the infrastructure system operators with briefings on the student analysis results. Some student projects have eventually influenced Department of Homeland Security and Department of Defense policy. We detail what makes the network modeling project work, and how to implement it in other universities.

Maritime Policy & Management, 25, pp. 335-348. A multinational company uses a personal computer to schedule a fleet of coastal tankers and barges transporting liquid bulk products among plants, distribution centres (tank farms), and industrial customers. A simple spreadsheet interface cloaks a sophisticated optimization-based decision support system and makes this system useable via a variety of natural languages. The dispatchers, whose native language is not English, and some of whom presumably speak no English at all, communicate via the spreadsheet, and view recommended schedules displayed in Gantt charts-both internationally familiar tools. Inside the spreadsheet, a highly detailed simulation can generate every feasible alternate vessel employment schedule, and an integer linear set partitioning model selects one schedule for each vessel so that all loads and deliveries are completed at minimal cost while satisfying all operational requirements. The optimized fleet employment schedule is displayed graphically with hourly time resolution over a planning horizon of 2-3 weeks. Each vessel will customarily make several voyages and many port calls to load and unload products during this time.

Interfaces, 27, pp. 15-37. Most optimization-based decision support systems are used repeatedly with only modest changes to input data from scenario to scenario. Unfortunately, optimization (mathematical programming) has a well-deserved reputation for amplifying small input changes into drastically different solutions. A previously optimal solution, or a slight variation of one, may still be nearly optimal in a new scenario and managerially preferable to a dramatically different solution that is mathematically optimal. Mathematical programming models can be stated and solved so that they exhibit varying degrees of persistence with respect to previous values of variables, constraints, or even exogenous considerations. We use case studies to highlight how modeling with persistence has improved managerial acceptance and describe how to incorporate persistence as an intrinsic feature of any optimization model.

United States Coast Guard (USCG) districts schedule cutters 180 feet or less in length to weekly statuses (statuses is USCG jargon for assignments) from which they primarily respond to calls for search and rescue, law enforcement, and pollution control. The First Coast Guard District, based in Boston, has one of the largest scheduling problems: Each of 16 cutters is assigned weekly to one of six statuses to ensure patrol coverage, enforce equitable distribution of patrols, and honor restrictions on consecutive cutter statuses. When we state this quarterly scheduling problem as an elastic mixed-integer linear program, we obtain face-valid schedules—superior to manually prepared schedules for all measures of effectiveness considered—within a few minutes on a personal computer. Initial acceptance of the model was hampered by disruptive schedule revisions that resulted from minor changes in input. Modifications to preserve run-to-run persistence of solutions have brought success.

Mobil Oil Corporation consolidates and dispatches truck shipments of heavy petroleum products—lubricants in packages and in bulk—from 10 lubricant plants nationwide. It dispatches hundreds of orders daily either individually or as consolidated truckloads, using a very nonhomogeneous fleet of Mobil-controlled and contract vehicles and common carriers. Shipment schedules may span several days and include stops to pick up returned drums or entire trailers. Shipping costs depend upon the vehicle used, the shipment size, the locations of the stops, and the route distance and time. Candidate consolidations are generated automatically or with dispatcher assistance. Then, the dispatcher uses optimization to select a minimal-cost set of schedules. Mobil has been using this system for three years, reducing annual transportation costs by about $1 million (US).

Interfaces, 25, pp. 69-93. (Nominated for the 1994 International Management Science Achievement Award.) Digital Equipment Corporation evaluates global supply chain alternatives and determines worldwide manufacturing and distribution strategy, using the Global Supply Chain Model (GSCM) which recommends a production, distribution, and vendor network,, GSCM minimizes cost or weighted cumulative production and distribution times or both subject to meeting estimated demand and restrictions on local content, offset trade, and joint capacity for multiple products, echelons, and time periods.Cost factors include fixed and variable production charges, inventory charges, distribution expenses via multiple modes, taxes, duties, and duty drawback. GSCM is a large mixed-integer linear program that incorporates a global, multiproduct bill of materials for supply chains with arbitrary echelon structure and comprehensive model of integrated global manufacturing and distribution decisions. The supply chain restructuring has saved over $100 million (US).

Since 1965, the United States Air Force has relied on mathematical programming for the planning of conventional air-to-ground munitions. The centerpiece of this planning effort is HEAVY ATTACK, a theater-level model employing large-scale nonlinear programming to load weapons onto aircraft and assign sorties to targets. The single-period objective is to maximize the expected destroyed target value over the forecast weather states by assigning sorties which use the best delivery tactics in each weather state with available aircraft and weapons stocks. Over multiple periods, HEAVY ATTACK accounts for differences between targets in regeneration rate, value, and ease of damage assessment, and accounts for aircraft attrition and remaining weapons stocks, mounting the best sorties possible with the remaining resources. In 1988 approximately $2 billion worth of weapons were purchased with guidance from HEAVY ATTACK; additional expenditures of $5.2 billion are being planned for 1994-99. In 1990-91, media coverage of Desert Storm made the focus of HEAVY ATTACK apparent to millions of viewers

Mathematical Programming, 64, pp. 17-51. Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows,and generalized network TOWS. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.

This paper (a) describes a defender-attacker-defender sequential game model (DAD) to plan defenses for an infrastructure system that will enhance that system's resilience against attacks by an intelligent adversary, (b) describes a realistic formulation of DAD for defending a transportation network, (c) develops a decomposition algorithm for solving this instance of DAD and others, and (d) demonstrates the solution of a small transportation-network example. A DAD model generally evaluates system operation through the solution of an optimization model, and the decomposition algo- rithm developed here requires only that this system-operation model be continuous and convex. For example, our transportation-network example incorporates a conges- tion model with a (convex) nonlinear objective function and linear constraints.

We introduce a real-time decision support system which uses optimization methods, simulation, and the judgement of the decision maker for operational assignment of units to tasks and for tactical allocation of units to task requirements. The system, named ARES for the Greek god of war, accommodates a high degree of detail in the logistics of unit movements during operations, yet separates the assignment and allocation activities in a fashion which naturally accommodates human intervention and judgement—ARES is designed to assist the decision maker, not to replace him. ARES is demonstrated with a hypothetical scenario constructed for 14 Engineering Battalions of the Hellenic Army which are assigned 20 tasks employing 25 resource types in repairing major damage to public works following a great earthquake. (This hypothetical data was prepared prior to the earthquake in Kalamata near Athens on 13 September, 1986, and exhibits uncanny, but coincidental, resemblance to that real situation.) ARES is designed for use in real time, and quick data preparation is aided by the provision from published sources of standard data for many foreseeable tasks; this data can be quickly accessed via visual icons on a computer screen and customized for the actual work at hand. © 1993 John Wiley & Sons, Inc.

Traditional probabilistic risk assessment (PRA), of the type originally developed for engineered systems, is still proposed for terrorism risk analysis. We show that such PRA applications are unjustified in general. The capacity of terrorists to seek and use information and to actively research different attack options before deciding what to do raises unique features of terrorism risk assessment that are not adequately addressed by conventional PRA for natural and engineered systems-in part because decisions based on such PRA estimates do not adequately hedge against the different probabilities that attackers may eventually act upon. These probabilities may differ from the defender's (even if the defender's experts are thoroughly trained, well calibrated, unbiased probability assessors) because they may be conditioned on different information. We illustrate the fundamental differences between PRA and terrorism risk analysis, and suggest use of robust decision analysis for risk management when attackers may know more about some attack options than we do.

Natural gas utilities supply about a quarter of the energy needs of the United States. From wellhead to consumer, operations are governed by an astounding diversity of purchase, transport, and storage contract agreements which prepare a complex physical distribution system to meet future demands no more predictable than next year's weather. We present a decision support system based on a highly detailed optimization model used by utilities to plan operations which minimize cost while satisfying regulatory agencies. Applications at Southwest Gas Corporation are presented along with a case study at Questar Pipeline Corporation. “But thou, contracted to thine own bright eyes, Feed'st thy light's flame with self-substantial fuel” William Shakespeare, First Sonnet

In areas of risk assessment ranging from terrorism to health, safety, and the environment, authoritative guidance urges risk analysts to quantify and display their uncertainties about inputs that significantly affect the results of an analysis, including their uncertainties about subjective probabilities of events. Such “uncertainty characterization” is said to be an important part of fully and honestly informing decision makers about the estimates and uncertainties in analyses that support policy recommendations, enabling them to make better decisions. But is it? Characterization of uncertainties about probabilities often carries zero value of information and accomplishes nothing to improve risk-management decisions. Uncertainties about consequence probabilities are not worth characterizing when final actions must be taken based on information available now. “But there seemed to be no chance of this, so she began looking at everything about her to pass away the time.”—Lewis Carroll, Alice in Wonderland

Employment scheduling is the process whereby U. S. Navy ships, submarines, aircraft and other units are assigned to major operations, exercises, maintenance periods, inspections and other events; the employment schedule directly influences fleet combat readiness. Currently, this process is largely manual requiring several full-time scheduling officers and additional personnel at various levels of management. We introduce an optimization model that automates a substantial part of the employment scheduling problem. The model is formulated as a generalized set partitioning problem and is applied to the annual planning schedule for naval surface combatants of the Atlantic Fleet. For the calendar year 1983, 111 ships engage in 19 primary events yielding a model with 228 constraints and 10,723 binary variables. This model is solved optimally in about 1.6 minutes producing a schedule that is significantly better than the corresponding published schedule. The optimized peacetime employment schedule which has as its objective maximizing combat readiness should always be the goal and guide. U.S. Navy, NWP − 1 He knew the things that were, the things that would be, and the things that had come before. Homer, The Iliad

This is a sea story about using a simple classroom example to save a great deal of money, as well as to convince beginning Postgraduate Naval School operations research students—experienced, skeptical military officers—that mathematical analysis can yield immediate results. The application is planning a ship’s transit from one point to another in a fixed amount of time, given that the ship can operate with one or more of its propulsion plants idled to save fuel. Simple analysis yields nonintuitive results that US Navy shipboard energy-conservation guides overlook. One of the authors (Kline) solved this homework problem as a student and subsequently applied this example when he took command of USS AQUILA, a patrol hydrofoil missile ship. AQUILA achieved results so striking in comparison to her sister ships that the squadron material officer inspected her engineering plant to ensure that no safety settings were being overridden to achieve this record. Kline’s spreadsheet decision-support tool was provided to other hydrofoil commanders. A more general version has been conveyed to the US Navy. Considering that our navy spends about a billion dollars per year on fuel for surface-combatant ships alone, this development promises substantial, long-term returns. “But thou, contracted to thine own bright eyes, Feed'st thy light'st flame with self-substantial fuel.” Shakespeare, Sonnet I

Military Operations Research, 11, 2006, pp. 41-62. We plan a long-term project schedule for which the total budget depends upon the year the project finishes. Each task in the project can begin only when all its predecessor tasks have been completed, and each task has a range of feasible durations with a month-by-month cost profile for each duration. A task start can be delayed, but once started for some chosen duration, a task cannot be interrupted. Each task suffers some risk of delay and changed cost. Ignoring budget constraints, we use Monte Carlo simulation of the duration of each task in the project to infer the probability distribution of the project completion time. We then optimize a deterministic project schedule following budget guidance. Finally, we successively reschedule as the project progresses, simulating annual review of the active tasks, and possibly delaying each active task's duration and changing its monthly costs for its forecast duration. We do not require an independence assumption, so we can accommodate learning effects from completed tasks. U.S. Army Future Combat Systems (FCS) is our motivating application. FCS is a complex of information technologies, sensors, and command systems expected to require more than a decade and $16 billion to develop. The U.S. General Accounting Office finds FCS at significant risk of cost and schedule growth, and suggests two alternatives to a baseline Army plan. We analyze these three alternate project plans for FCS to discover which one can most likely be completed soonest and cheapest.