Stochastic regret minimization for revenue management problems with nonstationary demands

We study an admission control model in revenue management with nonstationary and correlated demands over a finite discrete time horizon. The arrival probabilities are updated by current available information, that is, past customer arrivals and some other exogenous information. We develop a regret‐based framework, which measures the difference in revenue between a clairvoyant optimal policy that has access to all realizations of randomness a priori and a given feasible policy which does not have access to this future information. This regret minimization framework better spells out the trade‐offs of each accept/reject decision. We proceed using the lens of approximation algorithms to devise a conceptually simple regret‐parity policy. We show the proposed policy achieves 2‐approximation of the optimal policy in terms of total regret for a two‐class problem, and then extend our results to a multiclass problem with a fairness constraint. Our goal in this article is to make progress toward understanding the marriage between stochastic regret minimization and approximation algorithms in the realm of revenue management and dynamic resource allocation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 433–448, 2016     

Dynamic service rate control for a single‐server queue with Markov‐modulated arrivals

We consider the problem of service rate control of a single‐server queueing system with a finite‐state Markov‐modulated Poisson arrival process. We show that the optimal service rate is nondecreasing in the number of customers in the system; higher congestion levels warrant higher service rates. On the contrary, however, we show that the optimal service rate is not necessarily monotone in the current arrival rate. If the modulating process satisfies a stochastic monotonicity property, the monotonicity is recovered. We examine several heuristics and show where heuristics are reasonable substitutes for the optimal control. None of the heuristics perform well in all the regimes and the fluctuation rate of the modulating process plays an important role in deciding the right heuristic. Second, we discuss when the Markov‐modulated Poisson process with service rate control can act as a heuristic itself to approximate the control of a system with a periodic nonhomogeneous Poisson arrival process. Not only is the current model of interest in the control of Internet or mobile networks with bursty traffic, but it is also useful in providing a tractable alternative for the control of service centers with nonstationary arrival rates. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 661–677, 2013     

A stochastic approximation algorithm to compute bid prices for joint capacity allocation and overbooking over an airline network

In this article, we develop a stochastic approximation algorithm to find good bid price policies for the joint capacity allocation and overbooking problem over an airline network. Our approach is based on visualizing the total expected profit as a function of the bid prices and searching for a good set of bid prices by using the stochastic gradients of the total expected profit function. We show that the total expected profit function that we use is differentiable with respect to the bid prices and derive a simple expression that can be used to compute its stochastic gradients. We show that the iterates of our stochastic approximation algorithm converge to a stationary point of the total expected profit function with probability 1. Our computational experiments indicate that the bid prices computed by our approach perform significantly better than those computed by standard benchmark strategies and the performance of our approach is relatively insensitive to the frequency with which we recompute the bid prices over the planning horizon. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Choosing arrival process models for service systems: Tests of a nonhomogeneous Poisson process

Service systems such as call centers and hospital emergency rooms typically have strongly time‐varying arrival rates. Thus, a nonhomogeneous Poisson process (NHPP) is a natural model for the arrival process in a queueing model for performance analysis. Nevertheless, it is important to perform statistical tests with service system data to confirm that an NHPP is actually appropriate, as emphasized by Brown et al. [8]. They suggested a specific statistical test based on the Kolmogorov–Smirnov (KS) statistic after exploiting the conditional‐uniform (CU) property to transform the NHPP into a sequence of i.i.d. random variables uniformly distributed on [0,1] and then performing a logarithmic transformation of the data. We investigate why it is important to perform the final data transformation and consider what form it should take. We conduct extensive simulation experiments to study the power of these alternative statistical tests. We conclude that the general approach of Brown et al. [8] is excellent, but that an alternative data transformation proposed by Lewis [22], drawing upon Durbin [10], produces a test of an NHPP test with consistently greater power. We also conclude that the KS test after the CU transformation, without any additional data transformation, tends to be best to test against alternative hypotheses that primarily differ from an NHPP only through stochastic and time dependence. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 66–90, 2014     

Production‐inventory systems with imperfect advance demand information and updating

We consider a supplier with finite production capacity and stochastic production times. Customers provide advance demand information (ADI) to the supplier by announcing orders ahead of their due dates. However, this information is not perfect, and customers may request an order be fulfilled prior to or later than the expected due date. Customers update the status of their orders, but the time between consecutive updates is random. We formulate the production‐control problem as a continuous‐time Markov decision process and prove there is an optimal state‐dependent base‐stock policy, where the base‐stock levels depend upon the numbers of orders at various stages of update. In addition, we derive results on the sensitivity of the state‐dependent base‐stock levels to the number of orders in each stage of update. In a numerical study, we examine the benefit of ADI, and find that it is most valuable to the supplier when the time between updates is moderate. We also consider the impact of holding and backorder costs, numbers of updates, and the fraction of customers that provide ADI. In addition, we find that while ADI is always beneficial to the supplier, this may not be the case for the customers who provide the ADI. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A dynamic,nonstationary inventory problem for a price/quantity setting firm

A dynamic and nonstationary model is formulated for a firm which attempts to minimize total expected costs over a finite planning horizon. The control variables are price and production. The price p and the demand ζ are linked through the relationship ζ = g(p) + η, where g(p) is the riskless demand curve and η is a random variable. The general model allows for proportional ordering costs, convex holding and stockout costs, downward sloping riskless demand curve, backlogging, partial backlogging, lost sales, partial spoilage of inventory, and two modes of collecting revenue. Sufficient conditions are developed for this problem to have an optimal policy which resembles the single critical number policy known from stochastic inventory theory. It is also shown what set of parameters will satisfy these sufficiency conditions.     

Dynamic pricing in a dual‐market environment

This article is concerned with the determination of pricing strategies for a firm that in each period of a finite horizon receives replenishment quantities of a single product which it sells in two markets, for example, a long‐distance market and an on‐site market. The key difference between the two markets is that the long‐distance market provides for a one period delay in demand fulfillment. In contrast, on‐site orders must be filled immediately as the customer is at the physical on‐site location. We model the demands in consecutive periods as independent random variables and their distributions depend on the item's price in accordance with two general stochastic demand functions: additive or multiplicative. The firm uses a single pool of inventory to fulfill demands from both markets. We investigate properties of the structure of the dynamic pricing strategy that maximizes the total expected discounted profit over the finite time horizon, under fixed or controlled replenishment conditions. Further, we provide conditions under which one market may be the preferred outlet to sale over the other. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 531–549, 2015     

经马氏修正的Poisson过程的极大似然估计

近年来 ,隐马氏模型成为研究相依随机变量的一个十分有用的工具。实际应用过程中的一个很重要的问题是如何对隐马氏模型的参数进行估计。将一类连续时间隐马氏模型的问题转化为离散时间隐马氏模型的问题 ,给出了具体的隐马氏模型———经马氏修正的Poisson过程的极大似然估计及其算法。此类过程被广泛用来对复杂电信网络的交通流进行建模     

Inventory management with advance capacity information

An important aspect of supply chain management is dealing with demand and supply uncertainty. The uncertainty of future supply can be reduced if a company is able to obtain advance capacity information (ACI) about future supply/production capacity availability from its supplier. We address a periodic‐review inventory system under stochastic demand and stochastic limited supply, for which ACI is available. We show that the optimal ordering policy is a state‐dependent base‐stock policy characterized by a base‐stock level that is a function of ACI. We establish a link with inventory models that use advance demand information (ADI) by developing a capacitated inventory system with ADI, and we show that equivalence can only be set under a very specific and restrictive assumption, implying that ADI insights will not necessarily hold in the ACI environment. Our numerical results reveal several managerial insights. In particular, we show that ACI is most beneficial when there is sufficient flexibility to react to anticipated demand and supply capacity mismatches. Further, most of the benefits can be achieved with only limited future visibility. We also show that the system parameters affecting the value of ACI interact in a complex way and therefore need to be considered in an integrated manner. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Call center arrival modeling: A Bayesian state‐space approach

In this article, we introduce three discrete time Bayesian state‐space models with Poisson measurements, each aiming to address different issues in call center arrival modeling. We present the properties of the models and develop their Bayesian inference. In so doing, we provide sequential updating and smoothing for call arrival rates and discuss how the models can be used for intra‐day, inter‐day, and inter‐week forecasts. We illustrate the implementation of the models by using actual arrival data from a US commercial bank's call center and provide forecasting comparisons. © 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 28–42, 2011     

Modeling and analysis of a mixed‐model assembly line with stochastic operation times

We consider a mixed‐model assembly line (MMAL) comprised a set of workstations and a conveyor. The workstations are arranged in a serial configuration. The conveyor moves at a constant speed along the workstations. Initial units belonging to different models are successively fed onto the conveyor, and they are moved by the conveyor to pass through the workstations to gradually generate final products. All assembling tasks are manually performed with operation times to be stochastic. An important performance measure of MMALs is overload times that refer to uncompleted operations for operators within their work zones. This paper establishes a method to analyze the expected overload times for MMALs with stochastic operation times. The operation processes of operators form discrete time nonhomogeneous Markov processes with continuous state spaces. For a given daily production schedule, the expected overload times involve in analyzing the Markov processes for finite horizon. Based on some important properties of the performance measure, we propose an efficient approach for calculating the expected overload times. Numerical computations show that the results are very satisfactory. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

An exact analysis of a joint production‐inventory problem in two‐echelon inventory systems

We consider a two‐echelon inventory system with a manufacturer operating from a warehouse supplying multiple distribution centers (DCs) that satisfy the demand originating from multiple sources. The manufacturer has a finite production capacity and production times are stochastic. Demand from each source follows an independent Poisson process. We assume that the transportation times between the warehouse and DCs may be positive which may require keeping inventory at both the warehouse and DCs. Inventory in both echelons is managed using the base‐stock policy. Each demand source can procure the product from one or more DCs, each incurring a different fulfilment cost. The objective is to determine the optimal base‐stock levels at the warehouse and DCs as well as the assignment of the demand sources to the DCs so that the sum of inventory holding, backlog, and transportation costs is minimized. We obtain a simple equation for finding the optimal base‐stock level at each DC and an upper bound for the optimal base‐stock level at the warehouse. We demonstrate several managerial insights including that the demand from each source is optimally fulfilled entirely from a single distribution center, and as the system's utilization approaches 1, the optimal base‐stock level increases in the transportation time at a rate equal to the demand rate arriving at the DC. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

A time dependent continuous review inventory model with compound poisson demand

We discuss a time dependent optimal ordering policy for a finite horizon inventory system for which the provision of service is essential and thus no stockout is allowed. It is assumed that the system can place an order at any point in time during the horizon when it cannot meet the customer's demand and that lead time is negligible. The demand is considered to be distributed as a compound Poisson process with known parameters and the functional equation approach of dynamic programming is used to formulate the objective function. An algorithm has been developed to obtain the solution for all the cases. In addition, analytical solutions of the basic equation under two limiting conditions are presented.     

基于条件熵的不完备信息系统属性约简算法

在相容关系下定义了三种不完备条件熵——H′条件熵、E′条件熵和I′条件熵,并对它们的性质进行了分析比较,研究发现,H′条件熵和I′条件熵不适用于相容关系下信息观点的约简。利用E′条件熵刻画信息系统中属性的相对重要性,设计了一种新的基于信息论观点的启发式约简算法,它统一了完备信息系统与非完备信息系统中的约简方法。通过实例说明,该算法能得到决策表的相对约简。     

Equilibrium customer strategies and social–profit maximization in the single‐server constant retrial queue

We consider the single‐server constant retrial queue with a Poisson arrival process and exponential service and retrial times. This system has not waiting space, so the customers that find the server busy are forced to abandon the system, but they can leave their contact details. Hence, after a service completion, the server seeks for a customer among those that have unsuccessfully applied for service but left their contact details, at a constant retrial rate. We assume that the arriving customers that find the server busy decide whether to leave their contact details or to balk based on a natural reward‐cost structure, which incorporates their desire for service as well as their unwillingness to wait. We examine the customers' behavior, and we identify the Nash equilibrium joining strategies. We also study the corresponding social and profit maximization problems. We consider separately the observable case where the customers get informed about the number of customers waiting for service and the unobservable case where they do not receive this information. Several extensions of the model are also discussed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Stationary (s,s) policies for a finite horizon

In the finite-horizon stochastic (s, S) inventory model with periodic review the parameters of the optimal policy generally vary with the length of the horizon. A stationary policy, however, is easier to implement and may be easier to calculate. This paper studies optimal stationary policies for a finite horizon and relates them to optimal policies through their relation to optimal stationary policies for an infinite horizon.     

Partially controlled demand and inventory control: An additive model

The primary goal of this paper is to establish properties of the inventory and advertising policy minimizing the expected discounted cost over a finite horizon in a dynamic nonstationary inventory model with random demand which is influenced by the level of goodwill. Under linearization of the cost associated with the maximum inventory and the advertising effect on demand, the model is shown to be equivalent to an inventory model with disposal. Many results of this paper are extended to cover convex ordering cost of inventory and time lag in delivery of stocks.     

Dynamic pricing and replenishment: Optimality,bounds, and asymptotics

In many applications, managers face the problem of replenishing and selling products during a finite time horizon. We investigate the problem of making dynamic and joint decisions on product replenishment and selling in order to improve profit. We consider a backlog scenario in which penalty cost (resulting from fulfillment delay) and accommodation cost (resulting from shortage at the end of the selling horizon) are incurred. Based on continuous‐time and discrete‐state dynamic programming, we study the optimal joint decisions and characterize their structural properties. We establish an upper bound for the optimal expected profit and develop a fluid policy by resorting to the deterministic version of the problem (ie, the fluid problem). The fluid policy is shown to be asymptotically optimal for the original stochastic problem when the problem size is sufficiently large. The static nature of the fluid policy and its lack of flexibility in matching supply with demand motivate us to develop a “target‐inventory” heuristic, which is shown, numerically, to be a significant improvement over the fluid policy. Scenarios with discrete feasible sets and lost‐sales are also discussed in this article.     

Dynamic learning,pricing, and ordering by a censored newsvendor

We address the problem of determining optimal ordering and pricing policies in a finite‐horizon newsvendor model with unobservable lost sales. The demand distribution is price‐dependent and involves unknown parameters. We consider both the cases of perishable and nonperishable inventory. A very general class of demand functions is studied in this paper. We derive the optimal ordering and pricing policies as unique functions of the stocking factor (which is a linear transformation of the safety factor). An important expression is obtained for the marginal expected value of information. As a consequence, we show when lost sales are unobservable, with perishable inventory the optimal stocking factor is always at least as large as the one given by the single‐period model; however, if inventory is nonperishable, this result holds only under a strong condition. This expression also helps to explain why the optimal stocking factor of a period may not increase with the length of the problem. We compare this behavior with that of a full information model. We further examine the implications of the results to the special cases when demand uncertainty is described by additive and multiplicative models. For the additive case, we show that if demand is censored, the optimal policy is to order more as well as charge higher retail prices when compared to the policies in the single‐period model and the full information model. We also compare the optimal and myopic policies for the additive and multiplicative models. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

The dynamic transshipment problem

We investigate the strategy of transshipments in a dynamic deterministic demand environment over a finite planning horizon. This is the first time that transshipments are examined in a dynamic or deterministic setting. We consider a system of two locations which replenish their stock from a single supplier, and where transshipments between the locations are possible. Our model includes fixed (possibly joint) and variable replenishment costs, fixed and variable transshipment costs, as well as holding costs for each location and transshipment costs between locations. The problem is to determine how much to replenish and how much to transship each period; thus this work can be viewed as a synthesis of transshipment problems in a static stochastic setting and multilocation dynamic deterministic lot sizing problems. We provide interesting structural properties of optimal policies which enhance our understanding of the important issues which motivate transshipments and allow us to develop an efficient polynomial time algorithm for obtaining the optimal strategy. By exploring the reasons for using transshipments, we enable practitioners to envision the sources of savings from using this strategy and therefore motivate them to incorporate it into their replenishment strategies. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48:386–408, 2001