Approximation schemes for single‐machine scheduling with a fixed maintenance activity to minimize the total amount of late work

We consider the problem of scheduling n independent and simultaneously available jobs without preemption on a single machine, where the machine has a fixed maintenance activity. The objective is to find the optimal job sequence to minimize the total amount of late work, where the late work of a job is the amount of processing of the job that is performed after its due date. We first discuss the approximability of the problem. We then develop two pseudo‐polynomial dynamic programming algorithms and a fully polynomial‐time approximation scheme for the problem. Finally, we conduct extensive numerical studies to evaluate the performance of the proposed algorithms. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 172–183, 2016     

Rolling‐horizon replenishment: Policies and performance analysis

We consider a rolling‐horizon (RH) replenishment modeling framework under which a buyer can update demand information and inventory status, modify order quantities committed previously, place an advanced order for a new period at the end of the RH, and move along in time seamlessly. We show that the optimal order policy for the two‐period RH problem is a dual‐threshold type for updating period(s) plus a base‐stock type for the advanced order. We provide analytical formulas and algorithms to compute the optimal thresholds and the optimal base‐stock level exactly. With our analytical results and numerical procedures, we demonstrate the significant value of RH replenishment in matching supplies to demands more closely. We also show that with RH updating (flexibility), the value of additional demand information beyond the RH diminishes quickly. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Revenue maximization in two-station tandem queueing systems

We study optimal pricing for tandem queueing systems with finite buffers. The service provider dynamically quotes prices to incoming price sensitive customers to maximize the long-run average revenue. We present a Markov decision process model for the optimization problem. For systems with two stations, general-sized buffers, and two or more prices, we describe the structure of the optimal dynamic pricing policy and develop tailored policy iteration algorithms to find an optimal pricing policy. For systems with two stations but no intermediate buffer, we characterize conditions under which quoting either a high or a low price to all customers is optimal and provide an easy-to-implement algorithm to solve the problem. Numerical experiments are conducted to compare the developed algorithms with the regular policy iteration algorithm. The work also discusses possible extensions of the obtained results to both three-station systems and two-station systems with price and congestion sensitive customers using numerical analysis.     

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     

Capacity investment decisions under risk aversion

This article studies the optimal capacity investment problem for a risk‐averse decision maker. The capacity can be either purchased or salvaged, whereas both involve a fixed cost and a proportional cost/revenue. We incorporate risk preference and use a consumption model to capture the decision maker's risk sensitivity in a multiperiod capacity investment model. We show that, in each period, capacity and consumption decisions can be separately determined. In addition, we characterize the structure of the optimal capacity strategy. When the parameters are stationary, we present certain conditions under which the optimal capacity strategy could be easily characterized by a static two‐sided (s, S) policy, whereby, the capacity is determined only at the beginning of period one, and held constant during the entire planning horizon. It is purchased up to B when the initial capacity is below b, salvaged down to Σ when it is above σ, and remains constant otherwise. Numerical tests are presented to investigate the impact of demand volatility on the optimal capacity strategy. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 218–235, 2016     

Optimal FCFS allocation rules for periodic‐review assemble‐to‐order systems

In Assemble‐To‐Order (ATO) systems, situations may arise in which customer demand must be backlogged due to a shortage of some components, leaving available stock of other components unused. Such unused component stock is called remnant stock. Remnant stock is a consequence of both component ordering decisions and decisions regarding allocation of components to end‐product demand. In this article, we examine periodic‐review ATO systems under linear holding and backlogging costs with a component installation stock policy and a First‐Come‐First‐Served (FCFS) allocation policy. We show that the FCFS allocation policy decouples the problem of optimal component allocation over time into deterministic period‐by‐period optimal component allocation problems. We denote the optimal allocation of components to end‐product demand as multimatching. We solve the multi‐matching problem by an iterative algorithm. In addition, an approximation scheme for the joint replenishment and allocation optimization problem with both upper and lower bounds is proposed. Numerical experiments for base‐stock component replenishment policies show that under optimal base‐stock policies and optimal allocation, remnant stock holding costs must be taken into account. Finally, joint optimization incorporating optimal FCFS component allocation is valuable because it provides a benchmark against which heuristic methods can be compared. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 158–169, 2015     

A sequential dynamic pricing model and its applications

Consider a sequential dynamic pricing model where a seller sells a given stock to a random number of customers. Arriving one at a time, each customer will purchase one item if the product price is lower than her personal reservation price. The seller's objective is to post a potentially different price for each customer in order to maximize the expected total revenue. We formulate the seller's problem as a stochastic dynamic programming model, and develop an algorithm to compute the optimal policy. We then apply the results from this sequential dynamic pricing model to the case where customers arrive according to a continuous‐time point process. In particular, we derive tight bounds for the optimal expected revenue, and develop an asymptotically optimal heuristic policy. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Revenue management with aircraft reassignment flexibility

A well‐studied problem in airline revenue management is the optimal allocation of seat inventory among different fare‐classes, given a capacity for the flight and a demand distribution for each class. In practice, capacity on a flight does not have to be fixed; airlines can exercise some flexibility on the supply side by swapping aircraft of different capacities between flights as partial booking information is gathered. This provides the airline with the capability to more effectively match their supply and demand. In this paper, we study the seat inventory control problem considering the aircraft swapping option. For theoretical and practical purposes, we restrict our attention to the class of booking limit policies. Our analytical results demonstrate that booking limits considering the swapping option can be considerably different from those under fixed capacity. We also show that principles on the relationship between the optimal booking limits and demand characteristics (size and risk) developed for the fixed‐capacity problem no longer hold when swapping is an option. We develop new principles and insights on how demand characteristics affect the optimal booking limits under the swapping possibility. We also develop an easy to implement heuristic for determining the booking limits under the swapping option and show, through a numerical study, that the heuristic generates revenues close to those under the optimal booking limits. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Minimizing the false alarm rate in systems with transient abnormality

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     

Pricing bridges to cross a river

We consider a pricing problem in directed, uncapacitated networks. Tariffs must be defined by an operator, the leader, for a subset of m arcs, the tariff arcs. Costs of all other arcs in the network are assumed to be given. There are n clients, the followers, and after the tariffs have been determined, the clients route their demands independent of each other on paths with minimal total cost. The problem is to find tariffs that maximize the operator's revenue. Motivated by applications in telecommunication networks, we consider a restricted version of this problem, assuming that each client utilizes at most one of the operator's tariff arcs. The problem is equivalent to pricing bridges that clients can use in order to cross a river. We prove that this problem is APX‐hard. Moreover, we analyze the effect of uniform pricing, proving that it yields both an m approximation and a (1 + lnD)‐approximation. Here, D is upper bounded by the total demand of all clients. In addition, we consider the problem under the additional restriction that the operator must not reject any of the clients. We prove that this problem does not admit approximation algorithms with any reasonable performance guarantee, unless P = NP, and we prove the existence of an n‐approximation algorithm. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

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.     

Nonlinear pricing with consumer satiation

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 63: 386–400, 2016     

A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

Coordination of pricing and inventory control across products

We consider the joint pricing and inventory‐control problem for a retailer who orders, stocks, and sells two products. Cross‐price effects exist between the two products, which means that the demand of each product depends on the prices of both products. We derive the optimal pricing and inventory‐control policy and show that this policy differs from the base‐stock list‐price policy, which is optimal for the one‐product problem. We find that the retailer can significantly improve profits by managing the two products jointly as opposed to independently, especially when the cross‐price demand elasticity is high. We also find that the retailer can considerably improve profits by using dynamic pricing as opposed to static pricing, especially when the demand is nonstationary. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

Continuous-time markov decision processes with nonzero terminal reward

In this article we consider a continuous-time Markov decision process with a denumerable state space and nonzero terminal rewards. We first establish the necessary and sufficient optimality condition without any restriction on the cost functions. The necessary condition is derived through the Pontryagin maximum principle and the sufficient condition, by the inherent structure of the problem. We introduce a dynamic programming approximation algorithm for the finite-horizon problem. As the time between discrete points decreases, the optimal policy of the discretized problem converges to that of the continuous-time problem in the sense of weak convergence. For the infinite-horizon problem, a successive approximation method is introduced as an alternative to a policy iteration method.     

On the asymptotic optimality of algorithms for the flow shop problem with release dates

We consider the nonpermutation flow shop problem with release dates, with the objective of minimizing the sum of the weighted completion times on the final machine. Since the problem is NP‐hard, we focus on the analysis of the performance of several approximation algorithms, all of which are related to the classical Weighted Shortest Processing Time Among Available Jobs heuristic. In particular, we perform a probabilistic analysis and prove that two online heuristics and one offline heuristic are asymptotically optimal. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times

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     

Optimal sensor placement for underwater threat detection

The optimization framework for optimal sensor placement for underwater threat detection has been developed. It considers single‐period and multiperiod detection models, each of which includes two components: detection algorithm and optimization problem for sensor placement. The detection algorithms for single‐period and multiperiod models are based on likelihood ratio and sequential testing, respectively. For the both models, the optimization problems use the principle of superadditive coverage, which is closely related to energy‐based and information‐based approaches. An algorithm for quasi‐regular sensor placement approximating solutions to the optimization problems has been developed based on corresponding continuous relaxations and a criterion for its applicability has been obtained. Numerical experiments have demonstrated that the algorithm consistently outperforms existing optimization techniques for optimal sensor placement.© 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Robust shortest path planning and semicontractive dynamic programming

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 66:15–37, 2019     

On the polyhedral structure of two‐level lot‐sizing problems with supplier selection

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