Adaptive server staffing in the presence of time-varying arrivals: a feed-forward control approach

We study the short-term staffing problem of systems that experience random, non-stationary demand. The typical method to accommodate changes in arrival rate is to use historical data to identify peak periods and associated forecasting for upcoming time windows. In this paper, we develop a method that instead detects change as it happens. Motivated by an automatic call distributor system in a call centre with time-varying arrivals, we propose a change detection algorithm based upon non-homogeneous Poisson processes. The proposed method is general and may be thought of as a feed-forward strategy, in which we detect a change in the arrival process, estimate the new magnitude of the arrival rate, and assign an appropriate number of servers to the tasks. The generalized likelihood ratio statistic is used and a recommendation for its decision limit is developed. Simulation results are used to evaluate the performance of the detector in the context of a telephone call centre.     

Asymptotically optimal staffing of service systems with joint QoS constraints

We consider the problem of staffing large-scale service systems with multiple customer classes and multiple dedicated server pools under joint quality-of-service (QoS) constraints. We first analyze the case in which arrival rates are deterministic and the QoS metric is the probability a customer is queued, given by the Erlang-C formula. We use the Janssen–Van Leeuwaarden–Zwart bounds to obtain asymptotically optimal solutions to this problem. The second model considered is one in which the arrival rates are not completely known in advance (before the server staffing levels are chosen), but rather are known via a probability distribution. In this case, we provide asymptotically optimal solutions to the resulting stochastic integer program, leveraging results obtained for the case of deterministic arrivals.     

Staffing call centers under arrival-rate uncertainty with Bayesian updates

We consider the problem of staffing service centers with quality-of-service constraints. We focus on the case where the arrival rates are uncertain. We introduce formulations that handle staffing decisions made over two decision periods, minimizing the staffing costs over the stages while satisfying a service quality constraint on the second stage operation. A Bayesian update is used to obtain the second-stage arrival-rate distribution based on the first stage prior arrival-rate distribution and the observations in the first stage.     

Optimal design of multi‐server Markovian queues with polynomial waiting and service costs

This paper is concerned with the optimal design of queueing systems. The main decisions in the design of such systems are the number of servers, the appropriate control to have on the arrival rates, and the appropriate service rate these servers should possess. In the formulation of the objective function to this problem, most publications use only linear cost rates. The linear rates, especially for the waiting cost, do not accurately reflect reality. Although there are papers involving nonlinear cost functions, no paper has ever considered using polynomial cost functions of degree higher than two. This is because simple formulas for computing the higher moments are not available in the literature. This paper is an attempt to fill this gap in the literature. Thus, the main contributions of our work are as follows: (i) the derivation of a very simple formula for the higher moments of the waiting time for the M/M/s queueing system, which requires only the knowledge of the expected waiting time; (ii) proving their convexity with respect to the design variables; and (iii) modeling and solving more realistic design problems involving general polynomial cost functions. We also focus on simultaneous optimization of the staffing level, arrival rate and service rate. Copyright © 2013 John Wiley & Sons, Ltd.     

Call Center Staffing with Simulation and Cutting Plane Methods

We present an iterative cutting plane method for minimizing staffing costs in a service system subject to satisfying acceptable service level requirements over multiple time periods. We assume that the service level cannot be easily computed, and instead is evaluated using simulation. The simulation uses the method of common random numbers, so that the same sequence of random phenomena is observed when evaluating different staffing plans. In other words, we solve a sample average approximation problem. We establish convergence of the cutting plane method on a given sample average approximation. We also establish both convergence, and the rate of convergence, of the solutions to the sample average approximation to solutions of the original problem as the sample size increases. The cutting plane method relies on the service level functions being concave in the number of servers. We show how to verify this requirement as our algorithm proceeds. A numerical example showcases the properties of our method, and sheds light on when the concavity requirement can be expected to hold.     

Estimating arrival rate of nonhomogeneous Poisson processes with semidefinite programming

We present a summary of methods based on semidefinite programming for estimating arrival rate of nonhomogeneous Poisson processes from a finite set of observed data. Both one-dimensional time dependent, and multi-dimensional time and location dependent rates are considered. The arrival rate is a nonnegative function of time (or time and location). We also assume that it is a smooth function with continuous derivatives of up to certain order k. We estimate the rate function by one or multi-dimensional splines, with the additional condition that the underlying rate function is nonnegative. This approach results in an optimization problem over nonnegative polynomials, which can be modeled and solved using semidefinite programming. We also describe a method which requires only linear constraints. Numerical results based on e-mail arrival and highway accidents are presented.     

到达不确定呼叫中心人员配置的鲁棒优化模型

针对呼叫中心实际运营中顾客到达不确定的特点,采用鲁棒离散优化方法,建立呼叫中心人员配置的鲁棒模型。利用对偶原理将鲁棒模型转换易于求解的线性鲁棒对等式,通过调节模型中的鲁棒参数来权衡鲁棒解的保守性与最优性之间的关系,计算模型中约束违背概率上限来表示鲁棒解的可靠性。通过现实呼叫中心数据算例,验证了模型的有效性,分析了不同鲁棒水平下各时间段服务人员配置规律,以及系统最小成本与违背概率之间的权衡关系。最后,对到达扰动系数进行了敏感性分析。     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.     

Setting staffing requirements for time dependent queueing networks: The case of accident and emergency departments

An incentive scheme aimed at reducing patients’ waiting times in accident and emergency departments was introduced by the UK government in 2000. It requires 98% of patients to be discharged, transferred, or admitted to inpatient care within 4 hours of arrival. Setting the minimal hour by hour medical staffing levels for achieving the government target, in the presence of complexities like time-varying demand, multiple types of patients, and resource sharing, is the subject of this paper. Building on extensive body of research on time dependent queues, we propose an iterative scheme which uses infinite server networks, the square root staffing law, and simulation to come up with a good solution. The implementation of this algorithm in a typical A&E department suggests that significant improvement on the target can be gained, even without increase in total staff hours.     

企业技术投资决策模型及其模拟

何时投资购买技术是企业技术战略研究的一个关键问题.传统的技术投资的决策准则是使用净现值(NPV)方法,这种方法会导致企业过早的投资于一项技术,也不能解释企业技术投资时间滞后的现象.企业技术投资时间的滞后可以通过技术本身的不确定性来解释,技术的不确定性主要表现为在技术演化过程中新技术出现的速度和新技术技术效率改进程度的不确定.本文针对企业技术投资中的技术效率决策问题,假设技术出现服从泊松分布、技术改进程度服从均匀分布,构建了技术投资决策模型,并对模型进行模拟,结论表明决策模型比NPV方法能更好的解释企业技术投资决策的行为.     

Coordination of staffing and pricing decisions in a service firm

Customer demand is sensitive to the price paid for the service in many service environments. Using queueing theory framework, we develop profit maximization models for jointly determining the price and the staffing level in a service company. The models include constraints on the average waiting time and the blocking probability. We show convexity of the single‐variable subproblem under certain plausible assumptions on the demand and staffing cost functions. Using numerical examples, we investigate the sensitivity of the price and the staffing level to changes in the marginal service cost and the user‐specified constraint on the congestion measure. Copyright © 2008 John Wiley & Sons, Ltd.     

Balancing staffing and switching costs in a service center with flexible servers

In this paper, we study the problem of balancing staffing and switching costs in a service center with multiple types of customers and time-dependent service demand. We assume that servers are flexible and can be switched from serving one type of customers to another. The objective is to minimize the total staffing and switching costs subject to service level constraints. Column generation heuristics are developed based on a formulation from the perspective of servers. Computational experiments show that the heuristics perform well. Furthermore, an extension of the model is presented for the situation where there is a penalty if some of the service requests are not covered (satisfied).     

Continuous time control of the arrival process in an m/g/1 queue

The problem of continuously controlling the arrival process in an M/G/1 queue is studied. The control is exercised by keeping the facility open or closed for potential arrivals, and is based on the residual workload process. The reward structure includes a reward rate R when the server is busy, and a holding cost rate cx when the residual workload is x. The economic criterion used is long run average return. A control limit policy is shown to be optimal. An iterative method for calculating this control limit policy is suggested.     

Managing uncertainty in call centres using Poisson mixtures

We model a call centre as a queueing model with Poisson arrivals having an unknown varying arrival rate. We show how to compute prediction intervals for the arrival rate, and use the Erlang formula for the waiting time to compute the consequences for the occupancy level of the call centre. We compare it to the current practice of using a point estimate of the arrival rate (assumed constant) as forecast. Copyright © 2001 John Wiley & Sons, Ltd.     

A bulk arrival queueing model with fuzzy parameters and varying batch sizes

This paper develops a nonlinear programming approach to derive the membership functions of the steady-state performance measures in bulk arrival queueing systems with varying batch sizes, in that the arrival rate and service rate are fuzzy numbers. The basic idea is based on Zadeh’s extension principle. Two pairs of mixed integer nonlinear programs (MINLP) with binary variables are formulated to calculate the upper and lower bounds of the system performance measure at possibility level α. From different values of α, the membership function of the system performance measure is constructed. For practice use, the defuzzification of performance measures is also provided via Yager ranking index. To demonstrate the validity of the proposed method, a numerical example is solved successfully.     

A network model for nursing staff scheduling

The staffing of hospital nurses has become critical in recent years. As a means of containing skyrocketing costs, many hospitals are reducing nursing staff to a bare minimum. At the same time, the hospitals must maintain some minimal staffing level as insufficient staff could lead to a life threatening situation possibly with detrimental social, economic, and legal consequences. This article will present a model which can be used to determine the optimal scheduling of nursing staff under varying conditions. A typical problem will illustrate its use.     

A differential game formulation of a controlled network

This paper considers multiclass queueing network systems with fixed routing. With the service control as one player and the arrival and service rates as the other, the problem of network regulation can be formulated as a differential game. Representations of the value function are developed by studying the geometric properties of the associated Hamiltonians and are expressed in terms of related simpler halfspace problems. Also, a method of constructing the optimal feedback controls through the representation and the projected Isaacs equations is provided. The controls so constructed give both a guaranteed level of performance and robust stability over a range of rate perturbations.     

Dynamic rate Erlang-A queues

The multi-server queue with non-homogeneous Poisson arrivals and customer abandonment is a fundamental dynamic rate queueing model for large-scale service systems such as call centers and hospitals. Scaling the arrival rates and number of servers arises naturally when a manager updates a staffing schedule in response to a forecast of increased customer demand. Mathematically, this type of scaling ultimately gives us the fluid and diffusion limits as found in Mandelbaum et al. (Queueing Syst 30(1):149–201, 1998) for Markovian service networks. These asymptotics were inspired by the Halfin and Whitt (Oper Res 29(3):567–588, 1981) scaling for multi-server queues. In this paper, we provide a review and an in-depth analysis of the Erlang-A queueing model. We prove new results about cumulant moments of the Erlang-A queue, the transient behavior of the Erlang-A limit cycle, new fluid limits for the delay time of a virtual customer, and optimal static staffing policies for healthcare systems. We combine tools from queueing theory, ordinary differential equations, complex analysis, cumulant moments, orthogonal polynomials, and dynamic optimization to obtain new insights about this fundamental queueing model.     

The roster quality staffing problem – A methodology for improving the roster quality by modifying the personnel structure

Quantitative decision support on personnel planning is often restricted to either rostering or staffing. There exist some approaches in which aspects at the staffing level and the rostering level are treated in a sequential way. Obviously, such practice risks producing suboptimal solutions at both decision levels. These arguments justify an integrated approach towards improving the overall quality of personnel planning. This contribution constitutes (1) the introduction of the roster quality staffing problem and (2) a three-step methodology that enables assessing the appropriateness of a personnel structure for achieving high quality rosters, while relying on an existing rostering algorithm. Based on the rostering assessment result, specific modifications to the personnel structure can be suggested at the staffing level. The approach is demonstrated by means of two different hospital cases, which have it that they are subject to complex rostering constraints. Experimental results show that the three-step methodology indeed points out alternative personnel structures that better comply with the rostering requirements. The roster analysis approach and the corresponding staffing recommendations integrate personnel planning needs at operational and tactical levels.     

Determining an adequate probe separation for estimating the arrival rate in an M/D/1 queue using single-packet probing

We present a technique to estimate the arrival rate from delay measurements, acquired using single-packet probing. With practical applications in mind, we investigate a lower bound on the value of probe separation, to obtain a satisfactory estimate in a fixed amount of time. This leads to a problem: how long does it take for an M/D/1 queue to converge to its steady state as a function of the load? We examine this problem using three independent approaches: the time until the autocovariance of the transient workload process becomes negligible; the time it takes for the first transient moment of the workload process to get close to its stationary limit; and the convergence rate of the transient workload distribution to stationarity. These approaches yield different, yet strikingly similar results. We conclude with a recommendation for the probe separation threshold, and a practical approach to obtaining an arrival rate estimate using single-packet probing.