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, 2016

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two-stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig-Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig-Wolfe reformulation provides solutions with a tight LP-gap eliminating the need for a full branch-and-price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

The warehouse problem with deterministic production cost, selling prices, and demand was introduced in the 1950s and there is a renewed interest recently due to its applications in energy storage and arbitrage. In this paper, we consider two extensions of the warehouse problem and develop efficient computational algorithms for finding their optimal solutions. First, we consider a model where the firm can invest in capacity expansion projects for the warehouse while simultaneously making production and sales decisions in each period. We show that this problem can be solved with a computational complexity that is linear in the product of the length of the planning horizon and the number of capacity expansion projects. We then consider a problem in which the firm can invest to improve production cost efficiency while simultaneously making production and sales decisions in each period. The resulting optimization problem is non-convex with integer decision variables. We show that, under some mild conditions on the cost data, the problem can be solved in linear computational time.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

We consider scheduling problems involving two agents (agents *A* and *B*), each having a set of jobs that compete for the use of a common machine to process their respective jobs. The due dates of the *A*-jobs are decision variables, which are determined by using the common (*CON*) or slack (*SLK*) due date assignment methods. Each agent wants to minimize a certain performance criterion depending on the completion times of its jobs only. Under each due date assignment method, the criterion of agent *A* is always the same, namely an integrated criterion consisting of the due date assignment cost and the weighted number of tardy jobs. Several different criteria are considered for agent *B*, including the maxima of regular functions (associated with each job), the total (weighted) completion time, and the weighted number of tardy jobs. The overall objective is to minimize the performance criterion of agent *A*, while keeping the objective value of agent *B* no greater than a given limit. We analyze the computational complexity, and devise polynomial or pseudo-polynomial dynamic programming algorithms for the considered problems. We also convert, if viable, any of the devised pseudopolynomial dynamic programming algorithms into a fully polynomial-time approximation scheme.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

In this article, we consider shortest path problems in a directed graph where the transitions between nodes are subject to uncertainty. We use a minimax formulation, where the objective is to guarantee that a special destination state is reached with a minimum cost path under the worst possible instance of the uncertainty. Problems of this type arise, among others, in planning and pursuit-evasion contexts, and in model predictive control. Our analysis makes use of the recently developed theory of abstract semicontractive dynamic programming models. We investigate questions of existence and uniqueness of solution of the optimality equation, existence of optimal paths, and the validity of various algorithms patterned after the classical methods of value and policy iteration, as well as a Dijkstra-like algorithm for problems with nonnegative arc lengths.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

This article treats an elementary optimization problem, where an inbound stream of successive items is to be resequenced with the help of multiple parallel queues in order to restore an intended target sequence. Whenever early items block the one item to be currently released into the target sequence, they are withdrawn from their queue and intermediately stored in an overflow area until their actual release is reached. We aim to minimize the maximum number of items simultaneously stored in the overflow area during the complete resequencing process. We met this problem in industry practice at a large German automobile producer, who has to resequence containers with car seats prior to the assembly process. We formalize the resulting resequencing problem and provide suited exact and heuristic solution algorithms. In our computational study, we also address managerial aspects such as how to properly avoid the negative effects of sequence alterations.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

A Markov population decision chain concerns the control of a population of individuals in different states by assigning an action to each individual in the system in each period. This article solves the problem of finding policies that maximize expected system utility over a finite horizon in Markov population decision chains with finite state-action space under the following assumptions: (1) The utility function exhibits constant risk posture, (2) the progeny vectors of distinct individuals are independent, and (3) the progeny vectors of individuals in a state who take the same action are identically distributed. The main result is that it is possible to solve the problem with the original state-action space without augmenting it to include information about the population in each state or any other aspect of the system history. In particular, there exists an optimal policy that assigns the same action to all individuals in a given state and period, independently of the population in that period and such a policy can be computed efficiently. The optimal utility operators that find the maximum of a finite collection of polynomials (rather than affine functions) yield an optimal solution with effort linear in the number of periods.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

In various scenarios, consumers may become satiated with products, and the degree of satiation is directly associated with their prior experiences. Confronted with consumer satiation, the seller is unable to either identify consumers who have a higher likelihood of being satiated ex ante or distinguish satiated from non-satiated consumers ex post. Therefore, the seller should address dynamic selling, valuation uncertainty, and quantity decisions, all of which are important operational issues. We consider a two-period problem in which consumer types are influenced by their prior consumption experiences. Faced with these consumers, the seller intends to optimize quantities and adjust the prices of the products in each period to maximize revenue. We find that the seller may reduce ex ante production quantity as some consumers become satiated. Moreover, the ex ante quantity is first decreasing and then increasing with regard to the satiation rate. Furthermore, two-period information asymmetries may provide a rationale for upward distortion in quantity when consumer preferences are highly sensitive to first-period consumption.© 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

In this article, we study a class of Quasi-Skipfree (QSF) processes where the transition rate submatrices in the skipfree direction have a column times row structure. Under homogeneity and irreducibility assumptions we show that the stationary distributions of these processes have a product form as a function of the level. For an application, we will discuss the -queue that can be modeled as a QSF process on a two-dimensional state space. In addition, we study the properties of the stationary distribution and derive monotonicity of the mean number of the customers in the queue, their mean sojourn time and the variance as a function of for fixed mean arrival rate. © 2016 Wiley Periodicals, Inc. Naval Research Logistics, 2016

We consider a dynamic pricing model in which the instantaneous rate of the demand arrival process is dependent on not only the current price charged by the concerned firm, but also the present state of the world. While reflecting the current economic condition, the state evolves in a Markovian fashion. This model represents the real-life situation in which the sales season is relatively long compared to the fast pace at which the outside environment changes. We establish the value of being better informed on the state of the world. When reasonable monotonicity conditions are met, we show that better present economic conditions will lead to higher prices. Our computational study is partially calibrated with real data. It demonstrates that the benefit of heeding varying economic conditions is on par with the value of embracing randomness in the demand process. © 2015 Wiley Periodicals, Inc. Naval Research Logistics, 2015

We introduce and study a generalization of the classic sequential testing problem, asking to identify the correct state of a given series system that consists of independent stochastic components. In this setting, costly tests are required to examine the state of individual components, which are sequentially tested until the correct system state can be uniquely identified. The goal is to propose a policy that minimizes the expected testing cost, given a-priori probabilistic information on the stochastic nature of each individual component. Unlike the classic setting, where variables are tested one after the other, we allow multiple tests to be conducted simultaneously, at the expense of incurring an additional set-up cost. The main contribution of this article consists in showing that the batch testing problem can be approximated in polynomial time within factor , for any fixed . In addition, we explain how, in spite of its highly nonlinear objective function, the batch testing problem can be formulated as an approximate integer program of polynomial size, while blowing up its expected cost by a factor of at most . Finally, we conduct extensive computational experiments, to demonstrate the practical effectiveness of these algorithms as well as to evaluate their limitations. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 275–286, 2016

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

]]>Considering a supply chain with a supplier subject to yield uncertainty selling to a retailer facing stochastic demand, we find that commonly studied classical coordination contracts fail to coordinate both the supplier's production and the retailer's procurement decisions and achieve efficient performance. First, we study the vendor managed inventory (VMI) partnership. We find that a consignment VMI partnership coupled with a production cost subsidy achieves perfect coordination and a win-win outcome; it is simple to implement and arbitrarily allocates total channel profit. The production cost subsidy optimally chosen through Nash bargaining analysis depends on the bargaining power of the supplier and the retailer. Further, motivated by the practice that sometimes the retailer and the supplier can arrange a “late order,” we also analyze the behavior of an advance-purchase discount (APD) contract. We find that an APD with a revenue sharing contract can efficiently coordinate the supply chain as well as achieve flexible profit allocation. Finally, we explore which coordination contract works better for the supplier vs. the retailer. It is interesting to observe that Nash bargaining solutions for the two coordination contracts are equivalent. We further provide recommendations on the applications of these contracts. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 305–319, 2016

We consider a stochastic partially observable system that can switch between a normal state and a transient abnormal state before entering a persistent abnormal state. Only the persistent abnormal state requires alarms. The transient and persistent abnormal states may be similar in appearance, which can result in excess false alarms. We propose a partially observable Markov decision process model to minimize the false alarm rate, subject to a given upper bound on the expected alarm delay time. The cost parameter is treated as the Lagrange multiplier, which can be estimated from the bound of the alarm delay. We show that the optimal policy has a control-limit structure on the probability of persistent abnormality, and derive closed-form bounds for the control limit and present an algorithm to specify the Lagrange multiplier. We also study a specialized model where the transient and persistent abnormal states have the same observation distribution, in which case an intuitive “watchful-waiting” policy is optimal. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 320–334, 2016

This article studies coherent systems of heterogenous and statistically dependent components' lifetimes. We present a sufficient and necessary condition for a stochastically longer system lifetime resulted by allocating a single active redundancy. For exchangeable components' lifetimes, allocating the redundancy to the component with more minimal path sets is proved to produce a more reliable system, and for systems with stochastic arrangement increasing components' lifetimes and symmetric structure with respect to two components, allocating the redundancy to the weaker one brings forth a larger reliability. Several numerical examples are presented to illustrate the theoretical results as well. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 335–345, 2016

]]>For the single-machine scheduling problem with the objective of simultaneously minimizing total flow time and number of tardy jobs, a lower bound on the number of efficient sequences is known. However, the proof thereof, which makes use of a modified version of Smith's algorithm, is unduly lengthy and sophisticated. Adopting a totally new point of view, we present in this short article a much simpler proof based on the naive idea of pairwise interchange. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 346–348, 2016