Designing a call center with an IVR (Interactive Voice Response)

A call center is a service operation that caters to customer needs via the telephone. Call centers typically consist of agents that serve customers, telephone lines, an Interactive Voice Response (IVR) unit, and a switch that routes calls to agents. In this paper we study a Markovian model for a call center with an IVR. We calculate operational performance measures, such as the probability for a busy signal and the average wait time for an agent. Exact calculations of these measures are cumbersome and they lack insight. We thus approximate the measures in an asymptotic regime known as QED (Quality and Efficiency Driven) or the Halfin–Whitt regime, which accommodates moderate to large call centers. The approximations are both insightful and easy to apply (for up to 1000’s of agents). They yield, as special cases, known and novel approximations for the M/M/N/N (Erlang-B), M/M/S (Erlang-C) and M/M/S/N queue.     

Towards “zero abandonments” in call center performance

The call center industry is a big business in today's global economy. Staffing costs account for over half of a call center's total operations costs. Some large call centers, in practice, operate at very close to maximum capacity, believing that such an operations policy is efficient. However, by operating at levels close to 100% utilization, a call center is “living dangerously”. If, for example, call volumes even slightly exceed forecasts, customer calls will queue. As queue lengths and durations increase, customers will tend to abandon their calls. We provide some “rule-of-thumb” formulas that evaluate the cost of abandonments. These formulas may be used to justify an investment in additional agents required to improve the quality of service and reduce abandonments. Standard Erlang-C queueing formulas imply that abandonments can be significantly reduced with a small investment in additional agents. Thus, by improving customer service and hiring additional staff, a call center can improve profitability. We illustrate our analysis with realistic data, based on our work with large-scale customer service centers.     

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.     

New Algorithm for Ordered Tree-to-Tree Correction Problem

The ordered tree-to-tree correction problem is to compute the minimum edit cost of transforming one ordered tree to another one. This paper presents a new algorithm for this problem. Given two ordered trees S and T, our algorithm runs in O(|S| |T| + min { ²_S|T| + ^2.5_{S T}, ²_T|S| + ^2.5_{T S}) time, where _S denotes the number of leaves of S and _S denotes the depth of S. The previous best algorithms for this problem run in O(|S| |T| min { _S, _S} min { _T, _T}) time (K. Zhang and D. Shasha, SIAM J. Comput.18, No. 6 (1989), 1245–1262) and in O(min {|S|²|T| log₂ |T|, |T|²|S| log₂ |S|}) time (P. N. Klein, in “Algorithms—ESA'98, 6th Annual European Symposium” (G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci, Eds.), Lecture Notes in Computer Science, Vol. 1461, pp. 91–102, Springer-Verlag, Berlin/New York, 1998). As a comparison, our algorithm is asymptotically faster for certain kind of trees.     

Computing a longest common subsequence for a set of strings

The known 2-string LCS problem is generalized to finding a Longest Common Subsequence (LCS) for a set of strings. A new, general approach that systematically enumerates common subsequences is proposed for the solution. Assuming a finite symbol set, it is shown that the presented scheme requires a preprocessing time that grows linearly with the total length of the input strings and a processing time that grows linearly with (K), the number of strings, and () the number of matches among them. The only previous algorithm for the generalized LCS problem takesO(K·|S ₁|·|S ₂|·...|S _k |) execution time, where |S _i | denotes the length of the stringS _i . Since typically is a very small percentage of |S ₁|·|S ₂|·...·|S _k |, the proposed method may be considered to be much more efficient than the straightforward dynamic programming approach.     

A modular absolute bound condition for primitive association schemes

The well-known absolute bound condition for a primitive symmetric association scheme (X,S) gives an upper bound for |X| in terms of |S| and the minimal non-principal multiplicity of the scheme. In this paper we prove another upper bounds for |X| for an arbitrary primitive scheme (X,S). They do not depend on |S| but depend on some invariants of its adjacency algebra KS where K is an algebraic number field or a finite field. Partially supported by RFBR grants 07-01-00485, 08-01-00379 and 08-01-00640. The paper was done during the stay of the author at the Faculty of Science of Shinshu University.     

On the Polar Decomposition of the Product of Two Operators and Its Applications

Let T = U|T| and S = V|S| be the polar decompositions. In this paper, we shall obtain the polar decomposition of TS as TS = UWV|TS|, where |T||S^*| = W||T||S^*|| is the polar decomposition. Next, we shall show that TS = UV|TS| is the polar decomposition if and only if |T| commutes with |S^*|. Lastly, we shall apply this result to binormal and centered operators. We shall obtain characterizations of these operator classes from the viewpoint of the polar decomposition.     

Queueing analysis of a mobile trunked system with mixed traffic and finite population

In trunk mobile systems, telephone lines are interfaced with the radio system at the repeaters which serve dispatch type mobile subscribers and telephone line users. We study a trunked mobile system which serves two different types of communication traffic (i) dispatch traffic which has short average service time and (ii) interconnect traffic of telephone line users. Both types of users are assumed to arrive from finite population. The dispatch users are allowed to access all repeaters while interconnect users can occupy only a fixed number of repeaters. A sharing service algorithm to derive blocking probabilities of dispatch and interconnect users and average dispatch delay is proposed.     

The security number of lexicographic products

A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] ? S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results.     

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.     

An extension of the Erdős–Ginzburg–Ziv Theorem to hypergraphs

An n-set partition of a sequence S is a collection of n nonempty subsequences of S, pairwise disjoint as sequences, such that every term of S belongs to exactly one of the subsequences, and the terms in each subsequence are all distinct with the result that they can be considered as sets. For a sequence S, subsequence S^′, and set T, |T∩S| denotes the number of terms x of S with xT, and |S| denotes the length of S, and SS^′ denotes the subsequence of S obtained by deleting all terms in S^′. We first prove the following two additive number theory results.(1) Let S be a finite sequence of elements from an abelian group G. If S has an n-set partition, A=A₁,…,A_n, such that

then there exists a subsequence S^′ of S, with length |S^′|≤max{|S|−n+1,2n}, and with an n-set partition, , such that . Furthermore, if ||A_i|−|A_j||≤1 for all i and j, or if |A_i|≥3 for all i, then .(2) Let S be a sequence of elements from a finite abelian group G of order m, and suppose there exist a,bG such that . If |S|≥2m−1, then there exists an m-term zero-sum subsequence S^′ of S with or .Let be a connected, finite m-uniform hypergraph, and be the least integer n such that for every 2-coloring (coloring with the elements of the cyclic group ) of the vertices of the complete m-uniform hypergraph , there exists a subhypergraph isomorphic to such that every edge in is monochromatic (such that for every edge e in the sum of the colors on e is zero). As a corollary to the above theorems, we show that if every subhypergraph of contains an edge with at least half of its vertices monovalent in , or if consists of two intersecting edges, then . This extends the Erdős–Ginzburg–Ziv Theorem, which is the case when is a single edge.     

Restricted sumsets and a conjecture of Lev

LetA, B, S be finite subsets of an abelian groupG. Suppose that the restricted sumsetC={α+b: α ∈A, b ∈B, and α − b ∉S} is nonempty and somec∈C can be written asa+b witha∈A andb∈B in at mostm ways. We show that ifG is torsion-free or elementary abelian, then |C|≥|A|+|B|−|S|−m. We also prove that |C|≥|A|+|B|−2|S|−m if the torsion subgroup ofG is cyclic. In the caseS={0} this provides an advance on a conjecture of Lev. This author is responsible for communications, and supported by the National Science Fund for Distinguished Young Scholars (No. 10425103) and the Key Program of NSF (No. 10331020) in China.     

Joint modelling of the total amount and the number of claims by conditionals

In the risk theory context, let us consider the classical collective model. The aim of this paper is to obtain a flexible bivariate joint distribution for modelling the couple (S,N), where N is a count variable and S=X₁+?+X_N is the total claim amount. A generalization of the classical hierarchical model, where now we assume that the conditional distributions of S|N and N|S belong to some prescribed parametric families, is presented. A basic theorem of compatibility in conditional distributions of the type S given N and N given S is stated. Using a known theorem for exponential families and results from functional equations new models are obtained. We describe in detail the extension of two classical collective models, which now we call Poisson-Gamma and the Poisson-Binomial conditionals models. Other conditionals models are proposed, including the Poisson-Lognormal conditionals distribution, the Geometric-Gamma conditionals model and a model with inverse Gaussian conditionals. Further developments of collective risk modelling are given.     

Numerical semigroups with many gaps of the same parity

Let g _e (S) (respectively, g _o (S)) be the number of even (respectively, odd) gaps of a numerical semigroup S. In this work we study and characterize the numerical semigroups S that verify 2|g _e (S)−g _o (S)|+1∈S. As a consequence we will see that every numerical semigroup can be represented by means of a numerical semigroup with maximal embedding dimension with all its minimal generators odd. The first author is supported by the project MTM2007-62346 and FEDER funds. The authors want to thank P.A. García-Sánchez and the referee for their comments and suggestions.     

On the Distribution of the Derivative Zeros of a Complex Polynomial

We consider the class S(n) of all complex polynomials of degree n > 1 having all their zeros in the closed unit disk ē. By S(n,β) we denote the subclass of p ? S(n) vanishing in the prescribed point β ? ē. For an arbitrary point α ? C and p ? S(n,β) let |p| _α be the distance of α and the set of zeros of P'. Then there exists some P ? S(n,β) with maximal |P|α. We give an estimation for the number of zeros of P on |z| = 1$ resp. P' on $ |z-α| = |P| _α .     

A measuring argument for finite permutation groups

LetG be a finite transitive permutation group on a finite setS. LetA be a nonempty subset ofS and denote the pointwise stabilizer ofA inG byC _G (A). Our main result is the following inequality: [G :C _G (A)]≥|G|^|A|/|S|. This paper is a part of the author’s Ph.D. thesis research, carried out at Tel Aviv University under the supervision of Professor Marcel Herzog.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

Large k-preserving sets in infinite graphs

Let K be a cardinal. If K χ₀, define K := K . Otherwise, let K := K + 1. We prove a conjecture of Mader: Every infinite K -connected graph G = (V, E) contains a set S ? V with |S| = |V| such that G/S is K -connected for all S? S.