|
Article Excerpt
1. Introduction
Call centers usually handle several types of calls distinguished, for example, by the desired language of communication or the level of skill necessary to deliver technical support. It is usually not possible or cost-effective to train every agent to be able to handle every call class. Thus, frequently, one encounters a multi-skill call center, with various call classes and also various agent types, usually defined according to their skill set, i.e., the subset of call classes they can handle. Skill-Based Routing (SBR), or simply routing, refers to the rules that control the call-to-agent and agent-to-call assignments. Most modern call centers perform SBR (Koole and Mandelbaum, 2002).
Call center managers routinely impose constraints on the center's performance. A commonly encountered performance measure is the Service Level (SL), usually defined as the long-term fraction of calls whose waiting time is no larger than a given constant. Call center planners face the problems of determining appropriate staffing levels and agent work schedules. In a staffing problem, the day is divided into periods and one simply decides the number of agents of each type for each period. In a scheduling problem, a set of admissible work schedules is first specified, and the decision variables are the number of agents of each skill type in each work schedule. This determines the staffing indirectly, while making sure that it corresponds to a feasible set of work schedules.
Insights on the coordination of skill set design, staffing, and routing decisions for multi-skill centers are offered by Wallace and White (2005). First, endowing agents with two skills and employing a routing that balances agents' priorities over different call classes, they obtain SLs that are essentially as good as for a system where all agents have all skills. That is, if such a routing policy is practical, then training agents to have more than two skills adds little to performance. Second, assuming control over agent skill sets, staffing counts and routing, they meet nearly exactly (i.e., do not exceed) target SLs set for each call class.
We consider a single-period staffing problem where the agent skill sets and routing rules are given. The routing policies we consider are of the (static) overflow routing family. In this case each call class has an ordered list of agent types that can handle it; upon arrival, a call of that class is assigned to the first agent type in this list that has an available agent, or else is placed in queue (one queue per call class). Likewise, each agent type has an ordered list of call classes (queues) from which to pick up calls when it becomes available. The problem is to minimize staffing costs subject to a set of constraints on SLs (globally and per call class), assuming the center is in steady-state operation. This problem was proposed to us by Bell Canada, a Canadian company whose call centers serving Quebec and Ontario employ nearly 13 000 agents in total. The SL constraints are quite important to them because governmental regulations impose huge fines on the company when some of these constraints are not met on average over the month. The static routing rules may be seen as restrictive, but they were also a request from the company; they wanted to have a tool telling them what happens when they optimize under such constraints, with fixed routings and skill sets. In general, lower costs can obviously be achieved by relaxing the routing rules and optimizing the skill sets, so we do not necessarily recommend fixing these in practice. On the other hand, it is not always possible to have agents with any (arbitrary) combination of skills. Single-period staffing appears as a subproblem in several scheduling algorithms (Gans et al, 2003; Bhulai et al., 2008).
After formulating this problem as an integer program with linear objective function and nonlinear constraints, Cezik and L'Ecuyer (2008) developed and studied a general-purpose solution approach, based on ideas adapted from Atlason et al. (2004). They use integer programming with cutting planes; the cuts are obtained by estimating subgradients of the SL constraints with respect to the decision variables (the number of agents of each type) via simulation. This method can handle arbitrarily complex call center operating conditions (e.g., call-routing policy, non-stationarity, etc.). On the other hand, subgradient estimation by simulation is very time-consuming. Accepting noisier estimates obtained from shorter simulations can save time, but is more likely to return highly suboptimal or infeasible solutions (Cezik and L'Ecuyer, 2008).
Our approach aims to be a quicker alternative by exploiting approximations of the SL. However, in the multi-skill setting, good approximations are not generally available. If we assume that the call center is a loss system, i.e., there are no waiting queues and all calls that cannot be served immediately are lost, then there are many approximations of the loss (or blocking) probability per call class. Koole and Talim (2000) assume overflow routing and develop an approximation via decomposition into subsystems whose state space is smaller and which are easier to analyze. Koole et al. (2003) allow queueing and approximate the delay probability (i.e., that the delay is positive), based on this loss approximation and the relation between the loss probability in the Erlang B system and the delay probability of the Erlang C system. This relation involves the staffing, so their formula applies globally, but not per class. Better estimates of loss probabilities can be obtained via two-moment approximations of the overflow process (the equivalent random method, or Hayward's approximation) (Cooper, 1981; Wolff, 1989; Chevalier et al., 2003, 2004); and the method of Franx et al. (2006). These better methods restrict the overflow pattern (it cannot be cyclical, as defined in Section 3.1). One could choose to approximate the (class-specific) service level in a real system (i.e., with queueing) by the approximated loss probability in a relevant loss model. This would make sense in a system where most calls do not wait. However, this approach is unnatural for most modern call centers, which normally operate so that the fraction of calls that experience a positive delay in queue is considerable (Gans et al, 2003).
Our first contribution is an approximation of the SL per class in a multi-skill center with a special type of overflow routing. This Loss-Delay (LD) approximation exploits ideas from Koole and Talim (2000) and goes beyond a loss system by incorporating queueing. Essentially, it assumes that whenever a call is delayed, it waits in a queue for the last agent type (skill set) in its list. The approximation has an accuracy that varies across problems; despite this, we show that it is useful as a support tool in a staffing-cost minimization algorithm. We do this via examples where the routing policy has the overflow element but does not satisfy the latter assumption (waiting at the last agent type). The routing policy was specified by our industrial partner.
Our second contribution is a heuristic approach to the staffing problem. Key components are appropriate initialization and neighborhood search methods supported by the LD approximation in deciding neighbor feasibility and in selecting to which feasible neighbor to move. The first stage of the search terminates with a solution that is locally optimal (relative to a certain neighborhood) after a finite amount of work. The second stage uses local-search procedures supported by estimates of SLs that are more accurate than the LD approximation and are obtained by simulation. These procedures adjust the solution for feasibility or further cost reduction, evaluating only few additional solutions. We solve realistic problems of varying size and find that our approach often yields better solutions than that of Cezik and L'Ecuyer (2008) when the computing budget is limited. Although neither of the two methods is always dominant, the new heuristic is definitely a useful addition to the toolbox for this class of problems.
We mention other related work. Bassamboo et al (2006) and Harrison and Zeevi (2005) consider a call center with a doubly stochastic time-varying arrival process in an asymptotic regime and find a staffing and routing policy that asymptotically minimizes the cost of staffing and abandonment. It is unclear how their fluid approximation could provide good estimates of the SLs (to solve our problem). Wallace and Whitt (2005) assume no constraints on the choice of skill sets, except that each agent has exactly two skills, one primary skill and one secondary skill. They optimize both the staffing and the choice of skill sets, simultaneously. They allow a different (and more flexible) routing rule than ours and assume that all agent types cost the same. For staffing under a single SL constraint, Pot et al. (2008) have a heuristic that uses a line search to optimize the Lagrange multiplier for the constraint. It is unclear how this can be generalized to an efficient algorithm when there are multiple constraints.
The remainder of this paper is organized as follows. In Section 2 we formulate mathematical programs of multiskill staffing and scheduling and review related literature. Section 3.1 defines overflow routing and a related policy. Sections 3.2 to 3.4 develop the LD approximation. Section 4 describes our approach to the staffing problem and Section 5 details the solution of several problem instances. In Section 6 we compare to alternative approaches, including adapting the method of Wallace and Whitt (2005) and replacing our approximation by that of Koole and Talim (2000). Additional details of our approach are contained in the online Appendix; this includes detailed algorithms and an assessment of sensitivity to algorithm parameters.
2. Formulation of staffing and scheduling problems
The sets of call classes and agent types are N = {1, ..., n} and M = {1,..., m}, respectively. There are b time periods and s types of shifts; a shift is defined by specifying the time periods in which the agent is available to handle calls. The cost vector is c = [([c.sub.1], 1, ..., [c.sub.1], s, ..., [c.sub.m], 1, ..., [c.sub.m,s]).sup.T], where [c.sub.i,q] is the cost of an agent of type i having shift q, and "T" denotes vector transposition. Write [z.sub.i, q] for the number of agents of type i having shift q and set z = [([z.sub.1], 1, ..., [z.sub.m], 1, ..., [z.sub.m.s]).sup.T] Write [x.sub.i, p] for the number of agents of type i that are available to handle calls in period p. Then the staffing vector x = [([x.sub.1], 1, ..., [x.sub.1], b, ..., [x.sub.m], 1, ..., [x.sub.m, b]).sup.T] satisfies x = Az where A is a block-diagonal matrix with m identical blocks A, where the element (p, q) of A has a value of one if shift q covers period p, and is zero otherwise. Our definition of the SL of call class j during period p is
[g.sub.j,p] (x) = [E[number of type-j call arrivals in p that are served and wait at most [tau]] / E[number of type-j call arrivals in p, except those that wait less than [tau] and abandon]]' (1)
where "abandon" implies the call joined the queue--it was not lost immediately upon arrival; and [tau] is a constant called the Acceptable Waiting Time (AWT). In online Appendix A. 1, we consider an alternative SL definition in which calls that are delayed by less than [tau] and abandon are not excluded; and we provide formulas for its approximation. In our examples, the two measures of SL differed by at most 2% in moderate-abandonment cases and negligibly in lowabandonment cases. Given acceptable waiting times [[tau].sub.p], [[tau].sub.j] and [tau], aggregate SLs are defined analogously and denoted [g.sub.p](X), [g.sub.j](X) and g(X) for period p, call class j and overall, respectively.
A formulation of the scheduling problem is
(P1): min [c.sup.T]z = [m.summation over (t = 1)] [s.summation over (q = 1)] [C.sub.i, q], [Z.sub.i, q]...
|
