Risk‐sensitive sizing of responsive facilities

We develop a risk‐sensitive strategic facility sizing model that makes use of readily obtainable data and addresses both capacity and responsiveness considerations. We focus on facilities whose original size cannot be adjusted over time and limits the total production equipment they can hold, which is added sequentially during a finite planning horizon. The model is parsimonious by design for compatibility with the nature of available data during early planning stages. We model demand via a univariate random variable with arbitrary forecast profiles for equipment expansion, and assume the supporting equipment additions are continuous and decided ex‐post. Under constant absolute risk aversion, operating profits are the closed‐form solution to a nontrivial linear program, thus characterizing the sizing decision via a single first‐order condition. This solution has several desired features, including the optimal facility size being eventually decreasing in forecast uncertainty and decreasing in risk aversion, as well as being generally robust to demand forecast uncertainty and cost errors. We provide structural results and show that ignoring risk considerations can lead to poor facility sizing decisions that deteriorate with increased forecast uncertainty. Existing models ignore risk considerations and assume the facility size can be adjusted over time, effectively shortening the planning horizon. Our main contribution is in addressing the problem that arises when that assumption is relaxed and, as a result, risk sensitivity and the challenges introduced by longer planning horizons and higher uncertainty must be considered. Finally, we derive accurate spreadsheet‐implementable approximations to the optimal solution, which make this model a practical capacity planning tool.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Generating Pareto‐optimal boundary points in multiparty negotiations using constraint proposal method

In this paper a constraint proposal method is developed for computing Pareto‐optimal solutions in multiparty negotiations over continuous issues. Constraint proposal methods have been previously studied in a case where the decision set is unconstrained. Here we extend the method to situations with a constrained decision set. In the method the computation of the Pareto‐optimal solutions is decentralized so that the DMs do not have to know each others' value functions. During the procedure they have to indicate their optimal solutions on different sets of linear constraints. When the optimal solutions coincide, the common optimum is a candidate for a Pareto‐optimal point. The constraint proposal method can be used to generate either one Pareto‐optimal solution dominating the status quo solution or several Pareto‐optimal solutions. In latter case a distributive negotiation among the efficient points can be carried out afterwards. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 210–225, 2001     

A parallel machine replacement model

This paper considers a finite horizon parallel machine replacement problem where a fixed number of machines is in operation at all times. The operating cost for a machine goes up as the machine gets older. An older machine may have to be replaced by a new one when its operating cost becomes too high. There is a fixed order cost associated with the purchase of new machines. Machine purchase prices and salvage values may depend on the period in which they were purchased. The objective is to find a replacement plan that minimizes the total discounted cost over the problem horizon. We believe that the costs in our model are more commonly observed in practice than those previously used in the literature. The paper develops properties of optimal solutions and an efficient forward‐time algorithm to find an optimal replacement plan. A dominance property is developed that further limits the options to be considered, and a simple forecast horizon result is also presented. Future research possibilities are mentioned. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 275–287, 2002; Published online in Wiley InterScience (http://www.interscience.wiley.com). DOI 10.1002/nav.10012     

Dynamic pricing and replenishment: Optimality,bounds, and asymptotics

In many applications, managers face the problem of replenishing and selling products during a finite time horizon. We investigate the problem of making dynamic and joint decisions on product replenishment and selling in order to improve profit. We consider a backlog scenario in which penalty cost (resulting from fulfillment delay) and accommodation cost (resulting from shortage at the end of the selling horizon) are incurred. Based on continuous‐time and discrete‐state dynamic programming, we study the optimal joint decisions and characterize their structural properties. We establish an upper bound for the optimal expected profit and develop a fluid policy by resorting to the deterministic version of the problem (ie, the fluid problem). The fluid policy is shown to be asymptotically optimal for the original stochastic problem when the problem size is sufficiently large. The static nature of the fluid policy and its lack of flexibility in matching supply with demand motivate us to develop a “target‐inventory” heuristic, which is shown, numerically, to be a significant improvement over the fluid policy. Scenarios with discrete feasible sets and lost‐sales are also discussed in this article.     

Dynamic pricing and inventory control with learning

Optimal operating policies and corresponding managerial insight are developed for the decision problem of coordinating supply and demand when (i) both supply and demand can be influenced by the decision maker and (ii) learning is pursued. In particular, we determine optimal stocking and pricing policies over time when a given market parameter of the demand process, though fixed, initially is unknown. Because of the initially unknown market parameter, the decision maker begins the problem horizon with a subjective probability distribution associated with demand. Learning occurs as the firm monitors the market's response to its decisions and then updates its characterization of the demand function. Of primary interest is the effect of censored data since a firm's observations often are restricted to sales. We find that the first‐period optimal selling price increases with the length of the problem horizon. However, for a given problem horizon, prices can rise or fall over time, depending on how the scale parameter influences demand. Further results include the characterization of the optimal stocking quantity decision and a computationally viable algorithm. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 303–325, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10013     

Flexibility and complexity in periodic distribution problems

In this paper, we explore trade‐offs between operational flexibility and operational complexity in periodic distribution problems. We consider the gains from operational flexibility in terms of vehicle routing costs and customer service benefits, as well as the costs of operational complexity in terms of modeling, solution methods, and implementation challenges for drivers and customers. The period vehicle routing problem (PVRP) is a variation of the classic vehicle routing problem in which delivery routes are constructed for a period of time; the PVRP with service choice (PVRP‐SC) extends the PVRP to allow service (visit) frequency to become a decision of the model. For the periodic distribution problems represented by PVRP and PVRP‐SC, we introduce operational flexibility levers and a set of quantitative measures to evaluate the trade‐offs between flexibility and complexity. We develop a Tabu Search heuristic to incorporate a range of operational flexibility options. We analyze the potential value and the increased operational complexity of the flexibility levers. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

Inventory control under substitutable demand: A stochastic game application

Substitutable product inventory problem is analyzed using the concepts of stochastic game theory. It is assumed that there are two substitutable products that are sold by different retailers and the demand for each product is random. Game theoretic nature of this problem is the result of substitution between products. Since retailers compete for the substitutable demand, ordering decision of each retailer depends on the ordering decision of the other retailer. Under the discounted payoff criterion, this problem is formulated as a two‐person nonzero‐sum stochastic game. In the case of linear ordering cost, it is shown that there exists a Nash equilibrium characterized by a pair of stationary base stock strategies for the infinite horizon problem. This is the unique Nash equilibrium within the class of stationary base stock strategies. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 359–375, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10018     

Nonstationary stochastic gold-mining: A time-sequential tactical-allocation problem

This paper presents an extension of gold-mining problems formulated in earlier work by R. Bellman and J. Kadane. Bellman assumes there are two gold mines labeled A and B, respectively, each with a known initial amount of gold. There is one delicate gold-mining machine which can be used to excavate one mine per day. Associated with mine A is a known constant return rate and a known constant probability of breakdown. There is also a return rate and probability of breakdown for mine B. Bellman solves the problem of finding a sequential decision procedure to maximize the expected amount of gold obtained before breakdown of the machine. Kadane extends the problem by assuming that there are several mines and that there are sequences of constants such that the jth constant for each mine represents the return rate for the jth excavation of that mine. He also assumes that the probability of breakdown during the jth excavation of a mine depends on j. We extend these results by assuming that the return rates are random variables with known joint distribution and by allowing the probability of breakdown to be a function of previous observations on the return rates. We show that under certain regularity conditions on the joint distributions of the random variables, the optimal policy is: at each stage always select a mine which has maximal conditional expected return per unit risk. This gold-mining problem is also a formulation of the problem of time-sequential tactical allocation of bombers to targets. Several examples illustrating these results are presented.     

Algorithms for the multi‐item multi‐vehicles dynamic lot sizing problem

We consider a two‐stage supply chain, in which multi‐items are shipped from a manufacturing facility or a central warehouse to a downstream retailer that faces deterministic external demand for each of the items over a finite planning horizon. The items are shipped through identical capacitated vehicles, each incurring a fixed cost per trip. In addition, there exist item‐dependent variable shipping costs and inventory holding costs at the retailer for items stored at the end of the period; these costs are constant over time. The sum of all costs must be minimized while satisfying the external demand without backlogging. In this paper we develop a search algorithm to solve the problem optimally. Our search algorithm, although exponential in the worst case, is very efficient empirically due to new properties of the optimal solution that we found, which allow us to restrict the number of solutions examined. Second, we perform a computational study that compares the empirical running time of our search methods to other available exact solution methods to the problem. Finally, we characterize the conditions under which each of the solution methods is likely to be faster than the others and suggest efficient heuristic solutions that we recommend using when the problem is large in all dimensions. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006.     

Value management of diagnostic equipment with cancelation,no‐show,and emergency patients

Magnetic resonance imaging and other multifunctional diagnostic facilities, which are considered as scarce resources of hospitals, typically provide services to patients with different medical needs. This article examines the admission policies during the appointment management of such facilities. We consider two categories of patients: regular patients who are scheduled in advance through an appointment system and emergency patients with randomly generated demands during the workday that must be served as soon as possible. According to the actual medical needs of patients, regular patients are segmented into multiple classes with different cancelation rates, no‐show probabilities, unit value contributions, and average service times. Management makes admission decisions on whether or not to accept a service request from a regular patient during the booking horizon to improve the overall value that could be generated during the workday. The decisions should be made by considering the cancelation and no‐show behavior of booked patients as well as the emergency patients that would have to be served because any overtime service would lead to higher costs. We studied the optimal admission decision using a continuous‐time discrete‐state dynamic programming model. Identifying an optimal policy for this discrete model is analytically intractable and numerically inefficient because the state is multidimensional and infinite. We propose to study a deterministic counterpart of the problem (i.e., the fluid control problem) and to develop a time‐based fluid policy that is shown to be asymptotically optimal for large‐scale problems. Furthermore, we propose to adopt a mixed fluid policy that is developed based on the information obtained from the fluid control problem. Numerical experiments demonstrate that this improved policy works effectively for small‐scale problems. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 287–304, 2016     

Solving partially observable agent‐intruder games with an application to border security problems

In this paper, we introduce partially observable agent‐intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two‐person zero‐sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ?‐optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ?‐optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.     

Capacity allocation with machine duplication in semiconductor manufacturing

The manufacturing process for a computer chip is complex in that it involves a large number of distinct operations requiring a substantial lead‐time for completion. Our observations of such a manufacturing process at a large plant in the United States led us to identify several tactical and operational problems that were being addressed by the production planners on a recurring basis. This paper focuses on one such problem. At a tactical level, given a demand forecast of wafers to be manufactured, one specific problem deals with specifying which machine or machine groups will process different batches of wafers. We address this problem by recognizing the capacity limitations of the individual machines as well as the requirement for reducing operating and investment costs related to the machines. A mathematical model, which is a variation of the well‐known capacitated facility location problem, is proposed to solve this problem. Given the intractability of the model, we first develop problem specific lower bounding procedures based on Lagrangean relaxation. We also propose a heuristic method to obtain “good” solutions with reasonable computational effort. Computational tests, using hypothetical and industry‐based data, indicate that our heuristic approach provides optimal/near optimal solutions fairly quickly. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

装备维修器材生产路径决策的两阶启发式算法

当前装备供应保障系统中维修器材存在短缺、积压以及配送系统效率低下等问题,亟须对生产、库存和配送作业环节进行集成优化。为客观反映各个决策环节,将该问题公式化为一个混合整数线性规划模型,针对该模型多变量、多约束的特点,提出了一个基于数学规划的两阶启发式算法对其进行求解。结合算例,检验模型的可行性,并选取求解器CPLEX和一个类似的迭代算法与该算法在求解质量和运算时间方面进行对比与分析。结果表明,提出的模型是合理可行的,该算法在求解不同规模实例时表现出优异的性能。     

Formulations for dynamic lot sizing with service levels

In this article, we study deterministic dynamic lot‐sizing problems with a service‐level constraint on the total number of periods in which backlogs can occur over a finite planning horizon. We give a natural mixed integer programming formulation for the single item problem (LS‐SL‐I) and study the structure of its solution. We show that an optimal solution to this problem can be found in \begin{align*}\mathcal O(n^2\kappa)\end{align*} time, where n is the planning horizon and \begin{align*}\kappa=\mathcal O(n)\end{align*} is the maximum number of periods in which demand can be backlogged. Using the proposed shortest path algorithms, we develop alternative tight extended formulations for LS‐SL‐I and one of its relaxations, which we refer to as uncapacitated lot sizing with setups for stocks and backlogs. {We show that this relaxation also appears as a substructure in a lot‐sizing problem which limits the total amount of a period's demand met from a later period, across all periods.} We report computational results that compare the natural and extended formulations on multi‐item service‐level constrained instances. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Balancing perfectly periodic service schedules: An application from recycling and waste management

A national recycling and waste management company provides periodic services to its customers from over 160 service centers. The services are performed periodically in units of weeks over a planning horizon. The number of truck‐hours allocated to this effort is determined by the maximum weekly workload during the planning horizon. Therefore, minimizing the maximum weekly workload results in minimum operating expenses. The perfectly periodic service scheduling (PPSS) problem is defined based on the practices of the company. It is shown that the PPSS problem is strongly NP‐hard. Attempts to solve large instances by using an integer programming formulation are unsuccessful. Therefore, greedy BestFit heuristics with three different sorting schemes are designed and tested for six real‐world PPSS instances and 80 randomly generated data files. The heuristics provide effective solutions that are within 2% of optimality on average. When the best found BestFit schedules are compared with the existing schedules, it is shown that operational costs are reduced by 18% on average. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 160–171, 2012     

Stochastic regret minimization for revenue management problems with nonstationary demands

We study an admission control model in revenue management with nonstationary and correlated demands over a finite discrete time horizon. The arrival probabilities are updated by current available information, that is, past customer arrivals and some other exogenous information. We develop a regret‐based framework, which measures the difference in revenue between a clairvoyant optimal policy that has access to all realizations of randomness a priori and a given feasible policy which does not have access to this future information. This regret minimization framework better spells out the trade‐offs of each accept/reject decision. We proceed using the lens of approximation algorithms to devise a conceptually simple regret‐parity policy. We show the proposed policy achieves 2‐approximation of the optimal policy in terms of total regret for a two‐class problem, and then extend our results to a multiclass problem with a fairness constraint. Our goal in this article is to make progress toward understanding the marriage between stochastic regret minimization and approximation algorithms in the realm of revenue management and dynamic resource allocation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 433–448, 2016     

The cyclic separation scheduling problem

This paper deals with the problem of scheduling items (tasks, employees, equipment, etc.) over a finite time horizon so as to minimize total cost expenditures while maintaining a predefined separation between certain items. The problem is cyclic, because the same schedule will be repeated over several consecutive time periods of equal length. Thus, requirements are present to maintain the separation of items not only within the individual time periods considered, but also between items in adjoining periods. A special purpose branch-and-bound algorithm is developed to solve this scheduling problem by taking advantage of its cyclic nature. Computational results are given.     

多平台侦察水雷优化模型

针对侦察水雷作战特点,运用最优化理论解决多平台侦察水雷问题。建立多平台侦察水雷优化模型,并通过基于效能指标的单类平台侦察水雷作战模型和基于二分法的最大侦察搜索区域宽度解算模型,得到各类平台的数量需求及其最佳侦察线路配置等关键参数的最优解,较好地满足了侦察水雷作战需求。     

Route optimization for multiple searchers

We consider a discrete time‐and‐space route‐optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically moving targets. This article formulates a novel convex mixed‐integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, and target‐ and location‐dependent search effectiveness. We present two solution approaches, one based on the cutting‐plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting‐plane approach solves many realistically sized problem instances in a few minutes, while existing branch‐and‐bound algorithms fail. A specialized cut improves solution time by 50[percnt] in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting‐plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Optimal service rates of a service facility with perishable inventory items

In this paper we optimally control service rates for an inventory system of service facilities with perishable products. We consider a finite capacity system where arrivals are Poisson‐distributed, lifetime of items have exponential distribution, and replenishment is instantaneous. We determine the service rates to be employed at each instant of time so that the long‐run expected cost rate is minimized for fixed maximum inventory level and capacity. The problem is modelled as a semi‐Markov decision problem. We establish the existence of a stationary optimal policy and we solve it by employing linear programming. Several numerical examples which provide insight to the behavior of the system are presented. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 464–482, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10021