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.     

Two Issues in Setting Call Centre Staffing Levels

Motivated by a problem facing the Police Communication Centre in Auckland, New Zealand, we consider the setting of staffing levels in a call centre with priority customers. The choice of staffing level over any particular time period (e.g., Monday from 8 am–9 am) relies on accurate arrival rate information. The usual method for identifying the arrival rate based on historical data can, in some cases, lead to considerable errors in performance estimates for a given staffing level. We explain why, identify three potential causes of the difficulty, and describe a method for detecting and addressing such a problem.     

Analysis of call centre arrival data using singular value decomposition

We consider the general problem of analysing and modelling call centre arrival data. A method is described for analysing such data using singular value decomposition (SVD). We illustrate that the outcome from the SVD can be used for data visualization, detection of anomalies (outliers), and extraction of significant features from noisy data. The SVD can also be employed as a data reduction tool. Its application usually results in a parsimonious representation of the original data without losing much information. We describe how one can use the reduced data for some further, more formal statistical analysis. For example, a short‐term forecasting model for call volumes is developed, which is multiplicative with a time series component that depends on day of the week. We report empirical results from applying the proposed method to some real data collected at a call centre of a large‐scale U.S. financial organization. Some issues about forecasting call volumes are also discussed. Copyright © 2005 John Wiley & Sons, Ltd.     

The impact of special days in call arrivals forecasting: A neural network approach to modelling special days

A key challenge for call centres remains the forecasting of high frequency call arrivals collected in hourly or shorter time buckets. In addition to the complex intraday, intraweek and intrayear seasonal cycles, call arrival data typically contain a large number of anomalous days, driven by the occurrence of holidays, special events, promotional activities and system failures. This study evaluates the use of a variety of univariate time series forecasting methods for forecasting intraday call arrivals in the presence of such outliers. Apart from established, statistical methods, we consider artificial neural networks (ANNs). Based on the modelling flexibility of the latter, we introduce and evaluate different methods to encode the outlying periods. Using intraday arrival series from a call centre operated by one of Europe’s leading entertainment companies, we provide new insights on the impact of outliers on the performance of established forecasting methods. Results show that ANNs forecast call centre data accurately, and are capable of modelling complex outliers using relatively simple outlier modelling approaches. We argue that the relative complexity of ANNs over standard statistical models is offset by the simplicity of coding multiple and unknown effects during outlying periods.     

考虑运营稳定性的内支线班轮航线网络规划模型

货主选择承运航线的影响因素,既包括挂靠港口的计划到港时间与单箱运价,还包括反映班轮运营稳定性的甩箱率与准班率。对此,文章将挂靠港口的航行与在港时间不确定引入研究,并对挂靠港口间的不确定性建立联系,基于航次仿真来计算各挂靠港的到港时间分布、船舶的航次最大载箱量分布。以班轮航线的甩箱率与准班率限制、内支线最大船型与最长往返时间为约束,在优化内支线航线网络结构的同时,计算航线适配船型、班期密度及挂靠港计划到港时间。针对所构建的带不确定参数的NP难问题,文章设计了基于模拟仿真的智能优化算法,通过方案仿真技术来处理输入模型的众分布函数,借助智能优化原理从大范围解空间内寻找满意方案。文末对船舶航次仿真与网络规划模型的有效性进行了验证,算例分析表明:内支线班轮航线网络的货主选择比例达64%,且不论货主更偏好运输时间或价格,航线方案皆能贴近货主偏好。     

Asymptotic Analysis of a Loss Model with Trunk Reservation II: Trunks Reserved for Slow Traffic

We consider a model for a single link in a circuit switched network. The link has C circuits, and the input consists of offered calls of two types, that we call primary and secondary traffic. Of the C links R are reserved for primary traffic. We assume that both traffic types arrive as Poisson arrival streams. Assuming that C is large and   R = O (1)  , the arrival rate of secondary traffic is   O ( C )  while that of primary traffic is smaller, of the order     . The holding times of the secondary calls are assumed exponentially distributed with unit mean. Those of the primary calls are exponentially distributed with a large mean, that is     . The loads for both traffic types are thus comparable  ( O ( C ))  and we assume that the system is "critically loaded," i.e., the system's capacity is approximately equal to the total load. We analyze asymptotically the steady state probability that   n ₂  (resp.   n ₁  ) circuits are occupied by primary (resp. secondary) calls. In particular, we obtain two-term asymptotic approximations to the blocking probabilities for both traffic types. This work complements part I, where we assumed that the secondary traffic had an arrival rate that was     and a service rate that was     . Thus in part I the R trunks were reserved for the "fast traffic," whose arrival and service rates were   O ( C )  and   O (1)  .     

A new model for call centre queue management

A new model for call centre queue management is described. It incorporates important features of call centre queues and is shown to produce results that are very different from those produced by the more usual models. The analytic approach is easy to apply, and is used to offer some interesting insights for call center queue management.     

Non‐parametric modelling of time‐varying customer service times at a bank call centre

Call centres are becoming increasingly important in our modern commerce. We are interested in modelling the time‐varying pattern of average customer service times at a bank call centre. Understanding such a pattern is essential for efficient operation of a call centre. The call service times are shown to be lognormally distributed. Motivated by this observation and the important application, we propose a new method for inference about non‐parametric regression curves when the errors are lognormally distributed. Estimates and pointwise confidence bands are developed. The method builds upon the special relationship between the lognormal distribution and the normal distribution, and improves upon a naive estimation procedure that ignores this distributional structure. Our approach includes local non‐parametric estimation for both the mean function and the heteroscedastic variance function of the logged data, and uses local polynomial regression as a fitting tool. A simulation study is performed to illustrate the method. We then apply the method to model the time‐varying patterns of mean service times for different types of customer calls. Several operationally interesting findings are obtained and discussed. Copyright © 2006 John Wiley & Sons, Ltd.     

Optimality and Greed in Dynamic Allocation

In dynamic allocation items arrive and depart randomly and while present are stored in a limited facility; the job of an allocation algorithm is to decide whether and where to store an arriving item, while trying to minimize the cost incurred by rejections. Ordinarily, to prove the value of such an algorithm, one must either assume a specific arrival distribution (e.g., Poisson-λ), or try to obtain bounds relative to an adversary (as in competitive analysis).We present here a novel method of proving precise optimality for certain kinds of dynamic allocation algorithms, without assuming a specific arrival distribution. We do need to assume memoryless departure for at least some item types, and most importantly, we must assume conditions are such that it is not right to reject arrivals unnecessarily.The method is applied to two simple call assignment problems which arose, in quite different circumstances, at Lucent Technologies. In both cases the method was successful in showing that the intuitively best assignment algorithm really does minimize expected cost under fairly general, and essentially necessary, assumptions.     

A generalization of the Erlang formula of traffic engineering

Calls arrive at a switch, where they are assigned to any one of the available idle outgoing links. A call is blocked if all the links are busy. A call assigned to an idle link may be immediately lost with a probability which depends on the link. For exponential holding times and an arbitrary arrival process we show that the conditional distribution of the time to reach the blocked state from any state, given the sequence of arrivals, is independent of the policy used to route the calls. Thus the law of overflow traffic is independent of the assignment policy. An explicit formula for the stationary probability that an arriving call sees the node blocked is given for Poisson arrivals. We also give a simple asymptotic formula in this case.Work on this paper was done while the author was at Bellcore and at Berkeley.     

Bounds for the tail distribution in a queue with a superposition of general periodic Markov sources: theory and application

An efficient yet accurate estimation of the tail distribution of the queue length has been considered as one of the most important issues in call admission and congestion controls in ATM networks. The arrival process in ATM networks is essentially a superposition of sources which are typically bursty and periodic either due to their origin or their periodic slot occupation after traffic shaping. In this paper, we consider a discrete-time queue where the arrival process is a superposition of general periodic Markov sources. The general periodic Markov source is rather general since it is assumed only to be irreducible, stationary and periodic. Note also that the source model can represent multiple time-scale correlations in arrivals. For this queue, we obtain upper and lower bounds for the asymptotic tail distribution of the queue length by bounding the asymptotic decay constant. The formulas can be applied to a queue having a huge number of states describing the arrival process. To show this, we consider an MPEG-like source which is a special case of general periodic Markov sources. The MPEG-like source has three time-scale correlations: peak rate, frame length and a group of pictures. We then apply our bound formulas to a queue with a superposition of MPEG-like sources, and provide some numerical examples to show the numerical feasibility of our bounds. Note that the number of states in a Markov chain describing the superposed arrival process is more than 1.4 × 10⁸⁸. Even for such a queue, the numerical examples show that the order of the magnitude of the tail distribution can be readily obtained.     

Analysis of a multicast switch via the arrival modulation technique

Multicast switching is emerging as a new switching technology that can provide efficient transport in a broadband network for video and other multipoint communication services. In this paper, we analyze the call blocking probability in a multicast switch via thearrival modulation technique. Our study shows that multicast traffic encounters higher blocking probability than point-to-point traffic because of simultaneous output port contentions. To ensure adequate performance for multicast traffic, we develop and analyze a simple call scheduling algorithm calledFixed Splitting. The results show that the fixed splitting algorithm reduces the call blocking probability significantly when it is applied with appropriately selected splitting parameters.     

On the Counting Process for a Class of Markovian Arrival Processes with an Application to a Queueing System

In this paper, we consider the counting process for a class of Markovian arrival processes (MAPs). We assume that the representing matrices in such MAPs are expanded in terms of matrix representations of the standard generators in the Lie algebra of the special linear group. The primary purpose of this paper is to construct an explicit solution of the time-dependent distribution and factorial moments of the number of arrival events in (0,t] of the counting process for this class of MAPs. Our construction relies on the Baker–Hausdorff lemma and the specific structure of the representing matrices. To investigate the efficiency of CPU usage with the explicit solution, we have conducted numerical experiments on computing the time-dependent distribution of the counting process through the explicit solution and uniformization-based method. We show that the CPU times required to compute the time-dependent distribution of the number of arrival events in (0,t] through the explicit solution have little sensitivity to t, while the consumption of CPU times with the uniformization-based method becomes greater as t increases. For illustrative purposes, we present a system performance analysis of a queueing system for possible use in automatic call distribution (ACD) systems. As an application of the explicit solution, we use it to express the waiting time distribution of the queueing system. Some numerical examples are also given with comparisons to computer simulations.AMS subject classification: 60K20, 60K25, 68M20This revised version was published online in June 2005 with corrected coverdate     

Loss circuit switched communication network-performance analysis and dynamic routing

We investigate a loss circuit switched communication network with state-dependent dynamic routing strategy, wherein the state of the network at the time of call arrival determines whether or not the call is accepted and, if accepted, its route. We develop an approximate approach to the network performance analysis. The approach enhances the Fixed Point Model by treating multiple solutions of the Fixed Point Equations. Assuming that the multiple solutions correspond to the long-living network modes, we develop the aggregated Markov chain that describes the network transitions among these modes. We also propose and discuss a new state-dependent dynamic routing strategy which we call Least-Expected-Blocking strategy (LEB). LEB accepts an incoming call only if this results in a decrease in the expected blocking probability and it chooses a route that yields the maximum decrease. The new strategy outperforms the previously known strategies by the criterion of network steady blocking probability.     

Optimizing steady state Markov chains by state reduction

Many service systems have a parameter which can be changed continuously within a certain range. In queueing, for instance, one may be able to change the service rate by means of faster servers, or the arrival rate through advertising. The question to be addressed is how to choose the value of the parameter in order to maximize rewards. In this paper, service systems are formulated as Markov chains in equilibrium. The optimum is then found by Newton's method. This requires one to determine the first and second derivative of the rewards, and an effective method for doing this is proposed. The method is based on state reduction, which is a technique for finding equilibrium probabilities for finite and even for infinite state Markov chains. The optimization technique is then used to obtain a number of curves involving two simple service systems.     

Performance analysis of an ISDN switch with distributed architecture: circuit switched calls

We have developed an approximate analytic model and a detailed simulation model to study the performance of an ISDN switch with distributed architecture. The analytic model treats the switch as a network of single server and infinite server queues with nonpreemptive priority service, general service times and batch arrivals. The simulation program is written in a distributed and modular way so as to simplify model development and debugging. Also extensive statistical techniques are employed for simulation output validation. It is observed that the analytic and the simulation models are in close agreement for the mean end-to-end delay and in moderately close agreement for the 95th percentile points of the end-to-end delay distribution. The comparisons between the analytic and the simulation models lead us to conjecture that the analytic model would be even more accurate for bigger systems with several hundred processors (where simulation models are too expensive to run). Even though the model assumes Poisson external call arrival process, it is shown that it may be applied with reasonable accuracy even when external call arrivals are non-Poisson. This is due to the fact that the composite message arrival process at a processor or transmission element tends to be close to Poisson even when the external call arrivals are non-Poisson.     

Regenerative simulation of TES processes

Regenerative simulation has become a familiar and established tool for simulation-based estimation. However, many applications (e.g., traffic in high-speed communications networks) call for autocorrelated stochastic models to which traditional regenerative theory is not directly applicable. Consequently, extensions of regenerative simulation to dependent time series is increasingly gaining in theoretical and practical interest, with Markov chains constituting an important case. Fortunately, a regenerative structure can be identified in Harris-recurrent Markov chains with minor modification, and this structure can be exploited for standard regenerative estimation. In this paper we focus on a versatile class of Harris-recurrent Markov chains, called TES (Transform-Expand-Sample). TES processes can generate a variety of sample paths with arbitrary marginal distributions, and autocorrelation functions with a variety of functional forms (monotone, oscillating and alternating). A practical advantage of TES processes is that they can simultaneously capture the first and second order statistics of empirical sample paths (raw field measurements). Specifically, the TES modeling methodology can simultaneously match the empirical marginal distribution (histogram), as well as approximate the empirical autocorrelation function. We explicitly identify regenerative structures in TES processes and proceed to address efficiency and accuracy issues of prospective simulations. To show the efficacy of our approach, we report on a TES/M/1 case study. In this study, we used the likelihood ratio method to calculate the mean waiting time performance as a function of the regenerative structure and the intrinsic TES parameter controlling burstiness (degree of autocorrelation) in the arrival process. The score function method was used to estimate the corresponding sensitivity (gradient) with respect to the service rate. Finally, we demonstrated the importance of the particular regenerative structure selected in regard to the estimation efficiency and accuracy induced by the regeneration cycle length.     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimizing Bernoulli Routing Policies for Balancing Loads on Call Centers and Minimizing Transmission Costs

We address the problem of assigning probabilities at discrete time instants for routing toll-free calls to a given set of call centers to minimize a weighted sum of transmission costs and load variability at the call centers during the next time interval.We model the problem as a tripartite graph and decompose the finding of an optimal probability assignment in the graph into the following problems: (i) estimating the true arrival rates at the nodes for the last time period; (ii) computing routing probabilities assuming that the estimates are correct. We use a simple approach for arrival rate estimation and solve the routing probability assignment by formulating it as a convex quadratic program and using the affine scaling algorithm to obtain an optimal solution.We further address a practical variant of the problem that involves changing routing probabilities associated with k nodes in the graph, where k is a prespecified number, to minimize the objective function. This involves deciding which k nodes to select for changing probabilities and determining the optimal value of the probabilities. We solve this problem using a heuristic that ranks all subsets of k nodes using gradient information around a given probability assignment.The routing model and the heuristic are evaluated for speed of computation of optimal probabilities and load balancing performance using a Monte Carlo simulation. Empirical results for load balancing are presented for a tripartite graph with 99 nodes and 17 call center gates.