We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested.

Mean residual life is a useful dynamic characteristic to study reliability of a system. It has been widely considered in the literature not only for single unit systems but also for coherent systems. This article is concerned with the study of mean residual life for a coherent system that consists of multiple types of dependent components. In particular, the survival signature based generalized mixture representation is obtained for the survival function of a coherent system and it is used to evaluate the mean residual life function. Furthermore, two mean residual life functions under different conditional events on components’ lifetimes are also defined and studied.

This article studies convergence properties of optimal values and actions for discounted and average-cost Markov decision processes (MDPs) with weakly continuous transition probabilities and applies these properties to the stochastic periodic-review inventory control problem with backorders, positive setup costs, and convex holding/backordering costs. The following results are established for MDPs with possibly non-compact action sets and unbounded cost functions: (i) convergence of value iterations to optimal values for discounted problems with possibly non-zero terminal costs, (ii) convergence of optimal finite-horizon actions to optimal infinite-horizon actions for total discounted costs, as the time horizon tends to infinity, and (iii) convergence of optimal discount-cost actions to optimal average-cost actions for infinite-horizon problems, as the discount factor tends to 1. Being applied to the setup-cost inventory control problem, the general results on MDPs imply the optimality of (*s*, *S*) policies and convergence properties of optimal thresholds. In particular this article analyzes the setup-cost inventory control problem without two assumptions often used in the literature: (a) the demand is either discrete or continuous or (b) the backordering cost is higher than the cost of backordered inventory if the amount of backordered inventory is large.© 2017 Wiley Periodicals, Inc. Naval Research Logistics 00: 000–000, 2017

In standard stochastic dynamic programming, the transition probability distributions of the underlying Markov Chains are assumed to be known with certainty. We focus on the case where the transition probabilities or other input data are uncertain. Robust dynamic programming addresses this problem by defining a min-max game between Nature and the controller. Considering examples from inventory and queueing control, we examine the structure of the optimal policy in such robust dynamic programs when event probabilities are uncertain. We identify the cases where certain monotonicity results still hold and the form of the optimal policy is determined by a threshold. We also investigate the marginal value of time and the case of uncertain rewards.© 2017 Wiley Periodicals, Inc. Naval Research Logistics, 2017

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

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 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 propose a novel simulation-based approach for solving two-stage stochastic programs with recourse and endogenous (decision dependent) uncertainty. The proposed augmented nested sampling approach recasts the stochastic optimization problem as a simulation problem by treating the decision variables as random. The optimal decision is obtained via the mode of the augmented probability model. We illustrate our methodology on a newsvendor problem with stock-dependent uncertain demand both in single and multi-item (news-stand) cases. We provide performance comparisons with Markov chain Monte Carlo and traditional Monte Carlo simulation-based optimization schemes. Finally, we conclude with directions for future research.

We study two-agent scheduling on a single sequential and compatible batching machine in which jobs in each batch are processed sequentially and compatibility means that jobs of distinct agents can be processed in a common batch. A fixed setup time is required before each batch is started. Each agent seeks to optimize some scheduling criterion that depends on the completion times of its own jobs only. We consider several scheduling problems arising from different combinations of some regular scheduling criteria, including the maximum cost (embracing lateness and makespan as its special cases), the total completion time, and the (weighted) number of tardy jobs. Our goal is to find an optimal schedule that minimizes the objective value of one agent, subject to an upper bound on the objective value of the other agent. For each problem under consideration, we provide either a polynomial-time or a pseudo-polynomial-time algorithm to solve it. We also devise a fully polynomial-time approximation scheme when both agents’ scheduling criteria are the weighted number of tardy jobs.

There is significant value in the data collected by satellites during and after a natural disaster. The current operating paradigm in practice is for satellites to passively collect data when they happen to fly over a disaster location. Conversely, this article considers the alternative approach of actively maneuvering satellites to fly directly overhead of the disaster site on a routine basis. Toward this end, we seek to compute a satellite constellation design that minimizes the expected maneuver costs for monitoring an unknown forest fire. In this article, we present a 2-stage stochastic programing model for this problem as well as a accelerated L-shaped decomposition approach. A comparison between our approach and the current operating paradigm indicates that our solution provides longer duration data collections and a greater number of data collections. Analysis also shows that our proposed solution is robust over a wide array of scenarios.

The cultural and creative industries (CCIs) in Taiwan have gradually contributed to the national economy under the impetus of government policies. We employ a two-stage data envelopment analysis model with an additive efficiency decomposition approach to measure the profitability and marketability of 22 Taiwanese cultural and creative companies. Furthermore, we employ the network-based ranking approach to identify benchmark inputs/outputs, and the strengths and weakness of each company. Our empirical results show that the profitability of the cultural and creative companies is better than their marketability. Companies in the industries of publishing, creative life, popular music, and cultural content averagely perform better than those in the other three types of CCIs in terms of profitability. Companies in the creative life industry are on average more efficient than those in the other five types of CCIs in terms of marketability. The profitability/marketability matrix of cultural and creative companies is also presented.

The Replenishment at Sea Planner (RASP) is saving the U.S. Navy millions of dollars a year by reducing fuel consumption of its Combat Logistics Force (CLF). CLF shuttle supply ships deploy from ports to rendezvous with underway U.S. combatants and those of coalition partners. The overwhelming commodity transferred is fuel, ship-to-ship by hoses, while other important packaged goods and spare parts are high-lined, or helicoptered between ships. The U.S. Navy is organized in large areas of responsibility called numbered fleets, and within each of these a scheduler must promulgate a daily forecast of CLF shuttle operations. The operational planning horizon extends out several weeks, or as far into the future as we can forecast demand. We solve RASP with integer linear optimization and a purpose-built heuristic. RASP plans Replenishment-at-Sea (RAS) events with 4-hour (Navy watch) time fidelity. For five years, RASP has served two purposes: (1) it helps schedulers generate a daily schedule and animates it using Google Earth, and (2) it automates reports command-to-ship messages that are essential to keep this complex logistics system operating.