Search

We study price optimization of perishable inventory over multiple, consecutive selling seasons in the presence of demand uncertainty. Each selling season consists of a finite number of discrete time periods, and demand per time period is Bernoulli distributed with price-dependent parameter. The set of feasible prices is finite, and the expected demand corresponding to each price is unknown to the seller, whose objective is to maximize cumulative expected revenue. We propose an algorithm that estimates the unknown parameters in a learning phase, and in each subsequent season applies a policy determined as the solution to a sample dynamic program, which modifies the underlying dynamic program by replacing the unknown parameters by the estimate. Revenue performance is measured by the regret: the expected revenue loss relative to the optimal attainable revenue under full information. For a given number of seasons n, we show that if the number of seasons allocated to learning is asymptotic to $$(n^2\log n)^{1/3}$$ ( n 2 log n ) 1 / 3 , then the regret is of the same order, uniformly over all unknown demand parameters. An extensive numerical study that compares our algorithm to six benchmarks adapted from the literature demonstrates the effectiveness of our approach.

We study a pricing problem with finite inventory and semi-parametric demand uncertainty. Demand is a price-dependent Poisson process whose mean is the product of buyers’ arrival rate, which is a constant $$\lambda $$ λ , and buyers’ purchase probability $$q(p)$$ q ( p ) , where p is the price. The seller observes arrivals and sales, and knows neither $$\lambda $$ λ nor $$q$$ q . Based on a non-parametric maximum-likelihood estimator of $$(\lambda ,q)$$ ( λ , q ) , we construct an estimator of mean demand and show that as the system size and number of prices grow, it is asymptotically more efficient than the maximum likelihood estimator based only on sale data. Based on this estimator, we develop a pricing algorithm paralleling (Besbes and Zeevi in Oper Res 57:1407–1420, 2009) and study its performance in an asymptotic regime similar to theirs: the initial inventory and the arrival rate grow proportionally to a scale parameter n. If $$q$$ q and its inverse function are Lipschitz continuous, then the worst-case regret is shown to be $$O((\log n / n)^{1/4})$$ O ( ( log n / n ) 1 / 4 ) . A second model considered is the one in Besbes and Zeevi (2009, Section 4.2), where no arrivals are involved; we modify their algorithm and improve the worst-case regret to $$O((\log n / n)^{1/4})$$ O ( ( log n / n ) 1 / 4 ) . In each setting, the regret order is the best known, and is obtained by refining their proof methods. We also prove an $$\Omega (n^{-1/2})$$ Ω ( n - 1 / 2 ) lower bound on the regret. Numerical comparisons to state-of-the-art alternatives indicate the effectiveness of our arrivals-based approach.

We examine and compare simulation-based algorithms for solving the agent scheduling problem in a multiskill call center. This problem consists in minimizing the total costs of agents under constraints on the expected service level per call type, per period, and aggregated. We propose a solution approach that combines simulation with integer or linear programming, with cut generation. In our numerical experiments with realistic problem instances, this approach performs better than all other methods proposed previously for this problem. We also show that the two-step approach, which is the standard method for solving this problem, sometimes yield solutions that are highly suboptimal and inferior to those obtained by our proposed method.

A multi-skill staffing problem in a call center where the agent skill sets are exogenous and the call routing policy has well-specified features of overflow between different agent types is addressed. Constraints are imposed on the service level for each call class, defined here as the steady-state fraction of calls served within a given time threshold, excluded. An approximation of these service levels is developed that allows an arbitrary overflow mechanism and customer abandonment. A two-stage heuristic that finds good solutions to mathematical programs with such constraints is developed. The first stage uses search methods supported by the approximation. Because service level approximation errors may be substantial, the solution is adjusted in a second stage in which performance is estimated by simulation. Realistic problems of varying size and routing policy are solved. The proposed approach is shown to be competitive with (and often better than) previously available methods. [Supplementary materials...

Motivated by a Bell Canada call center operating in blend mode, we consider a system with two types of traffic and two types of agents. Outbound calls are served only by blend agents, whereas inbound calls can be served by either inbound-only or blend agents. Inbound callers may balk or abandon. There are several performance measures of interest, including the rate of outbound calls and the proportion of inbound calls waiting more than some fixed number of seconds. We present a collection of continuous-time Markov chain (CTMC) models which capture many real-world characteristics while maintaining parsimony that results in fast computation. We discuss and explore the tradeoffs between model fidelity and efficacy and compare our different CTMC models with a realistic simulation model of a Bell Canada call center, used as a benchmark.

Online communities amass vast quantities of valuable knowledge and thus generate major value to their owners. Where these communities are incorporated in a business as the main means of sharing ideas and issues regarding products produced by the business, it is important that the value of this knowledge endures and is easily recognized. For good management of such a business, risk analysis of the integrated online community is required. We choose to focus on the process of knowledge creation rather than the knowledge gained from individual messages isolated from context. Consequently, we model collections of messages, linked via tree-like structures; these message collections we call threads. Here we suggest a risk framework aimed at managing micro-level thread related risks. Specifically, we target the risk that there is no satisfactory response to the original message after a period of time. Risks are considered as binary events; the event can therefore be flagged when it is predicted to occur for the attention of the community manager. To predict such a binary response, we use several methods, including a Bayesian probit regression estimated via Gibbs sampling; results indicate this model to be suitable for classification tasks such as those considered.

We develop and study efficient Monte Carlo algorithms for pricing path-dependent options with the variance gamma model. The key ingredient is difference-of-gamma bridge sampling, based on the representation of a variance gamma process as the difference of two increasing gamma processes. For typical payoffs, we obtain a pair of estimators (named low and high) with expectations that (1) are monotone along any such bridge sampler, and (2) contain the continuous-time price. These estimators provide pathwise bounds on unbiased estimators that would be more expensive (infinitely expensive in some situations) to compute. By using these bounds with extrapolation techniques, we obtain significant efficiency improvements by work reduction. We then combine the gamma bridge sampling with randomized quasi–Monte Carlo to reduce the variance and thus further improve the efficiency. We illustrate the large efficiency improvements on numerical examples for Asian, lookback, and barrier options.

We develop stochastic models of time-dependent arrivals, with focus on the application to call centers. Our models reproduce three essential features of call center arrivals observed in recent empirical studies: a variance larger than the mean for the number of arrivals in any given time interval, a time-varying arrival intensity over the course of a day, and nonzero correlation between the arrival counts in different periods within the same day. For each of the new models, we characterize the joint distribution of the vector of arrival counts, with particular focus on characterizing how the new models are more flexible than standard or previously proposed models. We report empirical results from a study on arrival data from a real-life call center, including the essential features of the arrival process, the goodness of fit of the estimated models, and the sensitivity of various simulated performance measures of the call center to the choice of arrival process model.

Batch processing machines, where a number of jobs are processed simultaneously as a batch, occur frequently in semiconductor manufacturing environments, particularly at diffusion in wafer fabrication and at burn-in in final test. In this paper we consider a batch-processing machine subject to uncertain (Poisson) job arrivals. Two different cases are studied: (1) the processing times of batches are independent and identically distributed (IID), corresponding to a diffusion tube; and (2) the processing time of each batch is the maximum of the processing times of its constituent jobs, where the processing times of jobs are IID, modelling a burn-in oven. We develop computational procedures to minimize the expected long-run-average number of jobs in the system under a particular family of control policies. The control policies considered are threshold policies, where processing of a batch is initiated once a certain number of jobs have accumulated in the system. We present numerical examples of our methods and...

A simulation-based quantile estimator measures the level of system performance that can be delivered with a prespecified probability. To estimate selected quantiles of the response of a finite-horizon simulation, we develop procedures based on correlation induction techniques for variance reduction, with emphasis on antithetic variates and Latin hypercube sampling. These procedures achieve improved precision by controlling the simulation's random-number inputs as an integral part of the experimental design. The proposed multiple-sample quantile estimator is the average of negatively correlated quantile estimators computed from disjoint samples of the simulation response, where negative correlation is induced between corresponding responses in different samples while mutual independence of responses is maintained within each sample. The proposed single-sample quantile estimator is computed from negatively correlated simulation responses within one all-inclusive sample. The single-sample estimator based on Latin hypercube sampling is shown to be asymptotically normal and unbiased with smaller variance than the comparable direct-simulation estimator based on independent replications. Similar asymptotic comparisons of the multiple-sample and direct-simulation estimators focus on bias and mean square error. Monte Carlo results suggest that the proposed procedures can yield significant reductions in bias, variance, and mean square error when estimating quantiles of the completion time of a stochastic activity network.

A random vector X with given univariate marginals can be obtained by first applying the normal distribution function to each coordinate of a vector Z of correlated standard normals to produce a vector U of correlated uniforms over (0,1) and then transforming each coordinate of U by the relevant inverse marginal. One approach to fitting requires, separately for each pair of coordinates of X, the rank correlation, r(ρ), or the product-moment correlation, rL(ρ), where ρ is the correlation of the corresponding coordinates of Z, to equal some target r*. We prove the existence and uniqueness of a solution for any feasible target, without imposing restrictions on the marginals. For the case where r(ρ) cannot be computed exactly because of an infinite discrete support, the relevant infinite sums are approximated by truncation, and lower and upper bounds on the truncation errors are developed. With a function [Formula: see text] defined by the truncated sums, a bound on the error r(ρ*) − r* is given, where ρ* is a solution to [Formula: see text]. Based on this bound, an algorithm is proposed that determines truncation points so that the solution has any specified accuracy. The new truncation method has potential for significant work reduction relative to truncating heuristically, largely because as required accuracy decreases, so does the number of terms in the truncated sums. This is quantified with examples. The gain appears to increase with the heaviness of tails.

We develop strategies for integrated use of certain well-known variance reduction techniques to estimate a mean response in a finite-horizon simulation experiment. The building blocks for these integrated variance reduction strategies are the techniques of conditional expectation, correlation induction (including antithetic variates and Latin hypercube sampling), and control variates; all pairings of these techniques are examined. For each integrated strategy, we establish sufficient conditions under which that strategy will yield a smaller response variance than its constituent variance reduction techniques will yield individually. We also provide asymptotic variance comparisons between many of the methods discussed, with emphasis on integrated strategies that incorporate Latin hypercube sampling. An experimental performance evaluation reveals that in the simulation of stochastic activity networks, substantial variance reductions can be achieved with these integrated strategies. Both the theoretical and experimental results indicate that superior performance is obtained via joint application of the techniques of conditional expectation and Latin hypercube sampling.

A popular approach for modeling dependence in a finite-dimensional random vector X with given univariate marginals is via a normal copula that fits the rank or linear correlations for the bivariate marginals of X. In this approach, known as the NORTA method, the normal distribution function is applied to each coordinate of a vector Z of correlated standard normals to produce a vector U of correlated uniform random variables over (0,1); then X is obtained by applying the inverse of the target marginal distribution function for each coordinate of U.The fitting requires finding the appropriate correlation {rho} between any two given coordinates of Z that would yield the target rank or linear correlation r between the corresponding coordinates of X. This root-finding problem is easy to solve when the marginals are continuous but not when they are discrete. In this paper, we provide a detailed analysis of this root-finding problem for the case of discrete marginals. We prove key properties of r and of its derivative as a function of {rho}. It turns out that the derivative is easier to evaluate than the function itself. Based on that, we propose and compare alternative methods for finding or approximating the appropriate {rho}. The case of discrete distributions with unbounded support is covered as well. In our numerical experiments, a derivative-supported method is faster and more accurate than a state-of-the-art, nonderivative-based method. We also characterize the asymptotic convergence rate of the function r (as a function of {rho}) to the continuous-marginals limiting function, when the discrete marginals converge to continuous distributions

This article details several procedures for using path control variates to improve the accuracy of simulation-based point and confidence-interval estimators of the mean completion time of a stochastic activity network (SAN). Because each path control variate is the duration of the corresponding directed path in the network from the source to the sink, the vector of selected path controls has both a known mean and a known covariance matrix. This information is incorporated into estimation procedures for both normal and nonnormal responses. To evaluate the performance of these procedures experimentally, we examine the bias, variance, and mean square error of the controlled point estimators as well as the average half-length and coverage probability of the corresponding confidence-interval estimators for a set of SANs in which the following characteristics are systematically varied: (a) the size of the network (number of nodes and arcs); (b) the topology of the network; (c) the percentage of activities with exponentially distributed durations; and (d) the relative dominance of the critical path. The experimental results show that although large improvements in accuracy can be achieved with some of these procedures, the confidence-interval estimators for normal responses may suffer serious loss of coverage probability in some applications.

We develop and evaluate time-series models of call volume to the emergency medical service of a major Canadian city. Our objective is to offer simple and effective models that could be used for realistic simulation of the system and for forecasting daily and hourly call volumes. Notable features of the analyzed time series are: a positive trend, daily, weekly, and yearly seasonal cycles, special-day effects, and positive autocorrelation. We estimate models of daily volumes via two approaches: (1) autoregressive models of data obtained after eliminating trend, seasonality, and special-day effects; and (2) doubly-seasonal ARIMA models with special-day effects. We compare the estimated models in terms of goodness-of-fit and forecasting accuracy. We also consider two possibilities for the hourly model: (3) a multinomial distribution for the vector of number of calls in each hour conditional on the total volume of calls during the day and (4) fitting a time series to the data at the hourly level. For our data, (1) and (3) are superior.

We consider importance sampling (IS) to increase the efficiency of Monte Carlo integration, especially for pricing exotic options where the random input is multivariate normal. When the importance function (the product of integrand and original density) is multimodal, determining a good IS density is a difficult task. We propose an automated importance sampling density selection procedure (AISDE). AISDE selects an IS density as a mixture of multivariate normal densities with modes at certain local maxima of the importance function. When the simulation input is multivariate normal, we use principal component analysis to obtain a reduced-dimension, approximate importance function, which allows efficient identification of a good IS density via AISDE in original problem dimensions over 100. We present Monte Carlo experimental results on randomly generated option-pricing problems (including path-dependent options), demonstrating large and consistent efficiency improvement.

Broadie and Glasserman (1997) proposed a simulation-based method they named stochastic mesh for pricing high-dimensional American options. Based on simulated states of the assets underlying the option at each exercise opportunity, the method produces an estimator of the option value at each sampled state. Under the mild assumption of the finiteness of certain moments, we derive an asymptotic upper bound on the probability of error of the mesh estimator, where both the error size and the probability bound vanish as the sample size increases. We include the empirical performance for the test problems used by Broadie and Glasserman in a recent unpublished manuscript. We find that the mesh estimator has large bias that decays very slowly with the sample size, suggesting that in applications it will most likely be necessary to employ bias and/or variance reduction techniques.

Develops and studies general-purpose techniques for improving the efficiency of the stochastic mesh method that has been developed for pricing American options via Monte Carlo simulation. First, we develop a mesh-based, biased-low estimator. By recursively averaging the low and high estimators at each stage, we obtain a significantly more accurate point estimator at each of the mesh points. Second, we adapt the importance sampling ideas of Glasserman, Heidelberger and Shahabuddin (1998), for the simulation of European path-dependent options, to the pricing of American options with a stochastic mesh. Third, we sketch generalizations of the mesh method and we discuss links with other techniques for valuing American options. Our empirical results show that bias-reduced point estimates are much more accurate than the standard mesh-method point estimates. Importance sampling is found to increase the accuracy for smooth option-payoff functions, while variance increases are possible for non-smooth payoffs.

This paper details a new control-variate splitting scheme yielding an unbiased estimator of the mean response and an unbiased estimator of the variance of the first estimator. This scheme also yields an asymptotically exact confidence interval for the mean response. We present analytical and empirical performance comparisons of this scheme versus other control-variate procedures.

In this paper we develop strategies for integrating certain well-known variance reduction techniques to estimate a mean response in a finite-horizon simulation experiment. Our building blocks are the techniques of conditional expectation, correlation induction, and control variates. Under some mild assumptions, we explain how each integrated strategy yields a smaller response variance than its constituent variance reduction techniques yield individually. We also provide asymptotic variance comparisons for integrated strategies involving the correlation-induction technique of Latin hypercube sampling. Our Monte Carlo results show that in the simulation of stochastic activity networks, large efficiency gains can be achieved by using these integrated variance reduction strategies.