This article provides conditions under which total-cost and average-cost Markov decision processes (MDPs) can be reduced to discounted ones. Results are given for transient total-cost MDPs with transition rates whose values may be greater than one, as well as for average-cost MDPs with transition probabilities satisfying the condition that there is a state such that the expected time to reach it is uniformly bounded for all initial states and stationary policies. In particular, these reductions imply sufficient conditions for the validity of optimality equations and the existence of stationary optimal policies for MDPs with undiscounted total cost and average-cost criteria. When the state and action sets are finite, these reductions lead to linear programming formulations and complexity estimates for MDPs under the aforementioned criteria.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

This article proposes an approximation for the blocking probability in a many-server loss model with a non-Poisson time-varying arrival process and flexible staffing (number of servers) and shows that it can be used to set staffing levels to stabilize the time-varying blocking probability at a target level. Because the blocking probabilities necessarily change dramatically after each staffing change, we randomize the time of each staffing change about the planned time. We apply simulation to show that (i) the blocking probabilities cannot be stabilized without some form of randomization, (ii) the new staffing algorithm with randomiation can stabilize blocking probabilities at target levels and (iii) the required staffing can be quite different when the Poisson assumption is dropped.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min-cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

Stochastic network design is fundamental to transportation and logistic problems in practice, yet faces new modeling and computational challenges resulted from heterogeneous sources of uncertainties and their unknown distributions given limited data. In this article, we design arcs in a network to optimize the cost of single-commodity flows under random demand and arc disruptions. We minimize the network design cost plus cost associated with network performance under uncertainty evaluated by two schemes. The first scheme restricts demand and arc capacities in budgeted uncertainty sets and minimizes the worst-case cost of supply generation and network flows for any possible realizations. The second scheme generates a finite set of samples from statistical information (e.g., moments) of data and minimizes the expected cost of supplies and flows, for which we bound the worst-case cost using budgeted uncertainty sets. We develop cutting-plane algorithms for solving the mixed-integer nonlinear programming reformulations of the problem under the two schemes. We compare the computational efficacy of different approaches and analyze the results by testing diverse instances of random and real-world networks.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

A simultaneous non-zero-sum game is modeled to extend the classical network interdiction problem. In this model, an interdictor (e.g., an enforcement agent) decides how much of an inspection resource to spend along each arc in the network to capture a smuggler. The smuggler (randomly) selects a commodity to smuggle—a source and destination pair of nodes, and also a corresponding path for traveling between the given pair of nodes. This model is motivated by a terrorist organization that can mobilize its human, financial, or weapon resources to carry out an attack at one of several potential target destinations. The probability of evading each of the network arcs nonlinearly decreases in the amount of resource that the interdictor spends on its inspection. We show that under reasonable assumptions with respect to the evasion probability functions, (approximate) Nash equilibria of this game can be determined in polynomial time; depending on whether the evasion functions are exponential or general logarithmically-convex functions, exact Nash equilibria or approximate Nash equilibria, respectively, are computed.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

We examine capacity allocation mechanisms in a supply chain comprising a monopolistic supplier and two competing retailers with asymmetric market powers. The supplier allocates limited capacity to retailers according to uniform, proportional, or lexicographic mechanism. We study the impact of these allocation mechanisms on supplier pricing decisions and retailer ordering behavior. With individual order size no greater than supplier capacity, we show that all three mechanisms guarantee equilibrium ordering. We provide precise structures of retailer ordering decisions in Nash and dominant equilibria. Further, we compare the mechanisms from the perspective of the supplier, the retailers, and the supply chain. We show that regardless of whether retailer market powers are symmetric, lexicographic allocation with any priority sequence of retailers is better than the other two mechanisms for the supplier. Further, under lexicographic allocation, the supplier gains more profit by granting higher priority to the retailer with greater market power. We also extend our study to the case with multiple retailers.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

We study a single-product fluid-inventory model in which the procurement price of the product fluctuates according to a continuous time Markov chain. We assume that a fixed order price, in addition to state-dependent holding costs are incurred, and that the depletion rate of inventory is determined by the sell price of the product. Hence, at any time the controller has to simultaneously decide on the selling price of the product and whether to order or not, taking into account the current procurement price and the inventory level. In particular, the controller is faced with the question of how to best exploit the random time windows in which the procurement price is low. We consider two policies, derive the associated steady-state distributions and cost functionals, and apply those cost functionals to study the two policies.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

This article studies flexible capacity strategy (FCS) under oligopoly competition with uncertain demand. Each firm utilizes either the FCS or inflexible capacity strategy (IFCS). Flexible firms can postpone their productions until observing the actual demand, whereas inflexible firms cannot. We formulate a new asymmetrical oligopoly model for the problem, and obtain capacity and production decisions of the firms at Nash equilibrium. It is interesting to verify that cross-group competition determines the capacity allocation between the two groups of firms, while intergroup competition determines the market share within each group. Moreover, we show that the two strategies coexist among firms only when cost differentiation is medium. Counterintuitively, flexible firms benefit from increasing production cost when the inflexible competition intensity is sufficiently high. This is because of retreat of inflexible firms, flexibility effect, and the corresponding high price. We identify conditions under which FCS is superior than IFCS. We also demonstrate that flexible firms benefit from increasing demand uncertainty. However, when demand variance is not very large, flexible firms may be disadvantaged. We further investigate the effects of cross-group and intergroup competition on individual performance of the firms. We show that as flexible competition intensity increases, inflexible firms are mainly affected by the cross-group competition first and then by the intergroup competition, whereas flexible firms are mainly affected by the intergroup competition. Finally, we examine endogenous flexibility and identify its three drivers: cost parameters, cross-group competition, and intergroup competition.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

In this article, we study how to derive bounds for the reliability and the expected lifetime of a coherent system with heterogeneous ordered components. These bounds can be used to compare the performance of the systems obtained by permuting the components at a given system structure, that is, to study where we should place the different components at a system structure to get the most reliable system. Moreover, a similar procedure is applied to get bounds for mixtures and for the generalized proportional hazard rate model when the baseline populations are ordered.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

This article analyzes a class of stochastic contests among multiple players under risk-averse exponential utility. In these contests, players compete over the completion of a task by simultaneously deciding on their investment, which determines how fast they complete the task. The completion time of the task for each player is assumed to be an exponentially distributed random variable with rate linear in the player's investment and the completion times of different players are assumed to be stochastically independent. The player that completes the task first earns a prize whereas the remaining players earn nothing. The article establishes a one-to-one correspondence between the Nash equilibrium of this contest with respect to risk-averse exponential utilities and the nonnegative solution of a nonlinear equation. Using the properties of the latter, it proves the existence and the uniqueness of the Nash equilibrium, and provides an efficient method to compute it. It exploits the resulting representation of the equilibrium investments to determine the effects of risk aversion and the differences between the outcome of the Nash equilibrium and that of a centralized version.© 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

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 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 consider a problem of optimal division of stock between a logistic depot and several geographically dispersed bases, in a two-echelon supply chain. The objective is to minimize the total cost of inventory shipment, taking into account direct shipments between the depot and the bases, and lateral transshipments between bases. We prove the convexity of the objective function and suggest a procedure for identifying the optimal solution. Small-dimensional cases, as well as a limit case in which the number of bases tends to infinity, are solved analytically for arbitrary distributions of demand. For a general case, an approximation is suggested. We show that, in many practical cases, partial pooling is the best strategy, and large proportions of the inventory should be kept at the bases rather than at the depot. The analytical and numerical examples show that complete pooling is obtained only as a limit case in which the transshipment cost tends to infinity. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 3–18, 2017

In this article, the reliability and the mean residual life (MRL) functions of a system with active redundancies at the component and system levels are investigated. In active redundancy at the component level, the original and redundant components are working together and lifetime of the system is determined by the maximum of lifetime of the original components and their spares. In the active redundancy at the system level, the system has a spare, and the original and redundant systems work together. The lifetime of such a system is then the maximum of lifetimes of the system and its spare. The lifetimes of the original component and the spare are assumed to be dependent random variables. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 19–28, 2017

We analyze an interdiction scenario where an interceptor attempts to catch an intruder as the intruder moves through the area of interest. A motivating example is the detection and interdiction of drug smuggling vessels in the Eastern Pacific and Caribbean. We study two models in this article. The first considers a nonstrategic target that moves through the area without taking evasive action to avoid the interdictor. We determine the optimal location the interceptor should position itself to best respond when a target arrives. The second model analyzes the strategic interaction between the interceptor and intruder using a Blotto approach. The intruder chooses a route to travel on and the interceptor chooses a route to patrol. We model the interaction as a two-player game with a bilinear payoff function. We compute the optimal strategy for both players and examine several extensions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 29–40, 2017

We investigate a single-machine scheduling problem for which both the job processing times and due windows are decision variables to be determined by the decision maker. The job processing times are controllable as a linear or convex function of the amount of a common continuously divisible resource allocated to the jobs, where the resource allocated to the jobs can be used in discrete or continuous quantities. We use the common flow allowances due window assignment method to assign due windows to the jobs. We consider two performance criteria: (i) the total weighted number of early and tardy jobs plus the weighted due window assignment cost, and (ii) the resource consumption cost. For each resource consumption function, the objective is to minimize the first criterion, while keeping the value of the second criterion no greater than a given limit. We analyze the computational complexity, devise pseudo-polynomial dynamic programming solution algorithms, and provide fully polynomial-time approximation schemes and an enhanced volume algorithm to find high-quality solutions quickly for the considered problems. We conduct extensive numerical studies to assess the performance of the algorithms. The computational results show that the proposed algorithms are very efficient in finding optimal or near-optimal solutions. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 41–63, 2017

The cyclic best-first search (CBFS) strategy is a recent search strategy that has been successfully applied to branch-and-bound algorithms in a number of different settings. CBFS is a modification of best-first search (BFS) that places search tree subproblems into contours which are collections of subproblems grouped in some way, and repeatedly cycles through all non-empty contours, selecting one subproblem to explore from each. In this article, the theoretical properties of CBFS are analyzed for the first time. CBFS is proved to be a generalization of all other search strategies by using a contour definition that explores the same sequence of subproblems as any other search strategy. Further, a bound is proved between the number of subproblems explored by BFS and the number of children generated by CBFS, given a fixed branching strategy and set of pruning rules. Finally, a discussion of heuristic contour-labeling functions is provided, and proof-of-concept computational results for mixed-integer programming problems from the MIPLIB 2010 database are shown. © 2017 Wiley Periodicals, Inc. Naval Research Logistics, 64: 64–82, 2017