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

The notion of signature has been widely applied for the reliability evaluation of technical systems that consist of binary components. Multi-state system modeling is also widely used for representing real life engineering systems whose components can have different performance levels. In this article, the concept of survival signature is generalized to a certain class of unrepairable homogeneous multi-state systems with multi-state components. With such a generalization, a representation for the survival function of the time spent by a system in a specific state or above is obtained. The findings of the article are illustrated for multi-state consecutive-*k*-out-of-*n* system which perform its task at three different performance levels. The generalization of the concept of survival signature to a multi-state system with multiple types of components is also presented. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 593–599, 2017

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi-stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017

This paper considers optimal staffing in service centers. We construct models for profit and cost centers using dynamic rate queues. To allow for practical optimal controls, we approximate the queueing process using a Gaussian random variable with equal mean and variance. We then appeal to the Pontryagin's maximum principle to derive a closed form square root staffing (SRS) rule for optimal staffing. Unlike most traditional SRS formulas, the main parameter in our formula is not the probability of delay but rather a cost-to-benefit ratio that depends on the shadow price. We show that the delay experienced by customers can be interpreted in terms of this ratio. Throughout the article, we provide theoretical support of our analysis and conduct extensive numerical experiments to reinforce our findings. To this end, various scenarios are considered to evaluate the change in the staffing levels as the cost-to-benefit ratio changes. We also assess the change in the service grade and the effects of a service-level agreement constraint. Our analysis indicates that the variation in the ratio of customer abandonment over service rate particularly influences staffing levels and can lead to drastically different policies between profit and cost service centers. Our main contribution is the introduction of new analysis and managerial insights into the nonstationary optimal staffing of service centers, especially when the objective is to maximize profitability. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 615–630, 2017

Lifetime experiments are common in many research areas and industrial applications. Recently, process monitoring for lifetime observations has received increasing attention. However, some existing methods are inadequate as neither their in control (IC) nor out of control (OC) performance is satisfactory. In addition, the challenges associated with designing robust and flexible control schemes have yet to be fully addressed. To overcome these limitations, this article utilizes a newly developed weighted likelihood ratio test, and proposes a novel monitoring strategy that automatically combines the likelihood of past samples with the exponential weighted sum average scheme. The proposed Censored Observation-based Weighted-Likelihood (COWL) control chart gives desirable IC and OC performances and is robust under various scenarios. In addition, a self-starting control chart is introduced to cope with the problem of insufficient reference samples. Our simulation shows a stronger power in detecting changes in the censored lifetime data using our scheme than using other alternatives. A real industrial example based on the breaking strength of carbon fiber also demonstrates the effectiveness of the proposed method. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 631–646, 2017

In this article, we study a two-level lot-sizing problem with supplier selection (LSS), which is an *NP-hard* problem arising in different production planning and supply chain management applications. After presenting various formulations for LSS, and computationally comparing their strengths, we explore the polyhedral structure of one of these formulations. For this formulation, we derive several families of strong valid inequalities, and provide conditions under which they are facet-defining. We show numerically that incorporating these valid inequalities within a branch-and-cut framework leads to significant improvements in computation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 647–666, 2017

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a -approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a -approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5-approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017