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.     

The infinite server queue and heuristic approximations to the multi-server queue with and without retrials

In this paper, properties of the time-dependent state probabilities of theM _t /G/∞ queue, when the queue is assumed to start empty are studied. Those results are compared with corresponding time-dependent results for theM/M/1 queue. Approximation to the time-dependent state probabilities of theM/G/m/m queue by means of the corresponding time-dependent state probabilities of theM/G/∞ queue are discussed. Through a decomposition formula it is shown that the main performance characteristics of the ergodicM/M/m/m+d queue are sums of the corresponding random variables for the ergodicM/M/m/m andM/M/1/1+(d−1) queues, respectively, weighted by the 3-rd Erlang formula (stationary probability of waiting or being lost for theM/M/m/m+d queue). Successful exact and approximation extensions of this kind of decomposition formula to theM/M/m/m+d queue with retrials are presented.     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some structural properties of a Markovian storage/production system

We consider a storage/production system with state-dependent production rate and state-dependent demand arrival rate. Every arriving demand gives rise to a 'peak' in the trajectory of the content process. We characterize the processes N ₀(x)and N₁(x), defined as the number of peaks and the number of record peaks, respectively, before the content reaches the level x. The results are applied to the virtual waiting time process W(t) of a M/G/1 queue. Assuming that W(0)= x₀, M(x) is defined to be the number of arrivals before the virtual waiting time drops from x₀ to x₀-x(0⩽ x ⩽ x₀) ; in particular, Mx₀)is the number of customers arriving during the first busy period. It is shown that (M(x))(0⩽ x ⩽ x₀)is a compound Poisson process, and its jump size distribution is derived in closed form. This revised version was published online in June 2006 with corrections to the Cover Date.     

Queue length and waiting time of the M/G/1 queue under the D-policy and multiple vacations

We study the steady-state queue length and waiting time of the M/G/1 queue under the D-policy and multiple server vacations. We derive the queue length PGF and the LSTs of the workload and waiting time. Then, the mean performance measures are derived. Finally, a numerical example is presented and the effects of employing the D-policy are discussed. AMS Subject Classifications 60K25 This work was supported by the SRC/ERC program of MOST/KOSEF grant # R11-2000-073-00000.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

Generalized V-univexity type-I for multiobjective programming with n-set functions

In the last time important results in multiobjective programming involving type-I functions were obtained (Yuan et al. in: Konnov et al. (eds) Lecture notes in economics and mathematical systems, 2007; Mishra et al. An Univ Bucureşti Ser Mat, LII(2): 207–224, 2003). Following one of these ways, we study optimality conditions and generalized Mond-Weir duality for multiobjective programming involving n-set functions which satisfy appropriate generalized univexity V-type-I conditions. We introduce classes of functions called (ρ, ρ′)-V-univex type-I, (ρ, ρ′)-quasi V-univex type-I, (ρ, ρ′)-pseudo V-univex type-I, (ρ, ρ′)-quasi pseudo V-univex type-I, and (ρ, ρ′)-pseudo quasi V-univex type-I. Finally, a general frame for constructing functions of these classes is considered. This research was supported by Grant PN II code ID No. 112/01.10.2007, CEEX code 1/2006 No. 1531/2006, and CNCSIS A No. 105 GR/2006.     

Regularly varying tail of the waiting time distribution in M/G/1 retrial queue

We consider an M/G/1 retrial queue where the service time distribution has a regularly varying tail with index −β, β>1. The waiting time distribution is shown to have a regularly varying tail with index 1−β, and the pre-factor is determined explicitly. The result is obtained by comparing the waiting time in the M/G/1 retrial queue with the waiting time in the ordinary M/G/1 queue with random order service policy.     

AnM/M/s-consistent diffusion model for theGI/G/s queue

This paper develops a diffusion-approximation model for a stableGI/G/s queue: The queue-length process in theGI/G/s queue is approximated by a diffusion process on the nonnegative real line. Some heuristics on the state space and the infinitesimal parameters of the approximating diffusion process are introduced to obtain an approximation formula for the steady-state queue-length distribution. It is shown that the formula is consistent with the exact results for theM/M/s andM/G/ queues. The accuracy of the approximations for principal congestion measures are numerically examined for some particular cases.     

AnM/M/c queue with impatient customers

This paper considers theM/M/c queue in which a customer leaves when its service has not begun within a fixed interval after its arrival. The loss probability can be expressed in a simple formula involving the waiting time probabilities in the standardM/M/c queue. The purpose of this paper is to give a probabilistic derivation of this formula and to outline a possible use of this general formula in theM/M/c retrial queue with impatient customers. This research was supported by the INTAS 96-0828 research project and was presented at the First International Workshop on Retrial Queues, Universidad Complutense de Madrid, Madrid, September 22–24, 1998.     

Affinely equivalent complete flat manifolds

Let E _Aff(Γ,G, m) be the set of affine equivalence classes of m-dimensional complete flat manifolds with a fixed fundamental group Γ and a fixed holonomy group G. Let n be the dimension of a closed flat manifold whose fundamental group is isomorphic to Γ. We describe E _Aff(Γ,G, m) in terms of equivalence classes of pairs (ε, ρ), consisting of epimorphisms of Γ onto G and representations of G in ℝ ^m-n . As an application we give some estimates of card E _Aff(Γ,G, m).     

On the local Artin conductor f<Subscript>Artin</Subscript> (Χ) of a character Χ of Gal(E/K) — II: Main results for the metabelian case

This paper which is a continuation of [2], is essentially expository in nature, although some new results are presented. LetK be a local field with finite residue class fieldK _k. We first define (cf. Definition 2.4) the conductorf(E/K) of an arbitrary finite Galois extensionE/K in the sense of non-abelian local class field theory as wheren _G is the break in the upper ramification filtration ofG = Gal(E/K) defined by . Next, we study the basic properties of the idealf(E/K) inO _k in caseE/K is a metabelian extension utilizing Koch-de Shalit metabelian local class field theory (cf. [8]). After reviewing the Artin charactera _G : G → ℂ ofG := Gal(E/K) and Artin representationsA _g G → G →GL(V) corresponding toa _G : G → ℂ, we prove that (Proposition 3.2 and Corollary 3.5) where Χ_gr : G → ℂ is the character associated to an irreducible representation ρ: G → GL(V) ofG (over ℂ). The first main result (Theorem 1.2) of the paper states that, if in particular,ρ : G → GL(V) is an irreducible representation ofG(over ℂ) with metabelian image, then where Gal(E^ker(ρ)/E^ker(ρ)•) is any maximal abelian normal subgroup of Gal(E^ker(ρ)/K) containing Gal(E^ker(ρ) /K)′, and the break n_G/ker(ρ) in the upper ramification filtration of G/ker(ρ) can be computed and located by metabelian local class field theory. The proof utilizes Basmaji’s theory on the structure of irreducible faithful representations of finite metabelian groups (cf. [1]) and on metabelian local class field theory (cf. [8]). We then discuss the application of Theorem 1.2 on a problem posed by Weil on the construction of a ‘natural’A _G ofG over ℂ (Problem 1.3). More precisely, we prove in Theorem 1.4 that ifE/K is a metabelian extension with Galois group G, then Kazim İlhan ikeda whereN runs over all normal subgroups of G, and for such anN, V _n denotes the collection of all ∼-equivalence classes [ω]∼, where ‘∼’ denotes the equivalence relation on the set of all representations ω : (G/N)^• → ℂ^Χ satisfying the conditions Inert(ω) = {δ ∈ G/N : ℂ_δ} = ω =(G/N) and where δ runs over R((G/N)^•/(G/N)), a fixed given complete system of representatives of (G/N)^•/(G/N), by declaring that ω₁ ∼ ω₂ if and only if ω₁ = ω _2,δ for some δ ∈ R((G/N)^•/(G/N)). Finally, we conclude our paper with certain remarks on Problem 1.1 and Problem 1.3.     

An interpolation approximation for the GI/G/1 queue based on multipoint Padé approximation

The performance evaluation of many complex manufacturing, communication and computer systems has been made possible by modeling them as queueing systems. Many approximations used in queueing theory have been drawn from the behavior of queues in light and heavy traffic conditions. In this paper, we propose a new approximation technique, which combines the light and heavy traffic characteristics. This interpolation approximation is based on the theory of multipoint Padé approximation which is applied at two points: light and heavy traffic. We show how this can be applied for estimating the waiting time moments of the ^GI/G/1 queue. The light traffic derivatives of any order can be evaluated using the MacLaurin series analysis procedure. The heavy traffic limits of the ^GI/G/1 queue are well known in the literature. Our technique generalizes the previously developed interpolation approximations and can be used to approximate any order of the waiting time moments. Through numerical examples, we show that the moments of the steady state waiting time can be estimated with extremely high accuracy under all ranges of traffic intensities using low orders of the approximant. We also present a framework for the development of simple analytical approximation formulas. This revised version was published online in June 2006 with corrections to the Cover Date.     

Combined Elapsed Time and Matrix-Analytic Method for the Discrete Time GI/G/1 and GI X /G/1 Systems

In this paper, we show that the discrete GI/G/1 system can be easily analysed as a QBD process with infinite blocks by using the elapsed time approach in conjunction with the Matrix-geometric approach. The positive recurrence of the resulting Markov chain is more easily established when compared with the remaining time approach. The G-measure associated with this Markov chain has a special structure which is usefully exploited. Most importantly, we show that this approach can be extended to the analysis of the GI ^X /G/1 system. We also obtain the distributions of the queue length, busy period and waiting times under the FIFO rule. Exact results, based on computational approach, are obtained for the cases of input parameters with finite support – these situations are more commonly encountered in practical problems.     

Analysis of customers’ impatience in queues with server vacations

Many models for customers impatience in queueing systems have been studied in the past; the source of impatience has always been taken to be either a long wait already experienced at a queue, or a long wait anticipated by a customer upon arrival. In this paper we consider systems with servers vacations where customers’ impatience is due to an absentee of servers upon arrival. Such a model, representing frequent behavior by waiting customers in service systems, has never been treated before in the literature. We present a comprehensive analysis of the single-server, M/M/1 and M/G/1 queues, as well as of the multi-server M/M/c queue, for both the multiple and the single-vacation cases, and obtain various closed-form results. In particular, we show that the proportion of customer abandonments under the single-vacation regime is smaller than that under the multiple-vacation discipline. This work was supported by the Euro-Ngi network of excellence.     

Generalized Mukai conjecture for special Fano varieties

Let X be a Fano variety of dimension n, pseudoindex i _X and Picard number ρ_X. A generalization of a conjecture of Mukai says that ρ_X(i _X −1)≤n. We prove that the conjecture holds for a variety X of pseudoindex i _X ≥n+3/3 if X admits an unsplit covering family of rational curves; we also prove that this condition is satisfied if ρ_X> and either X has a fiber type extremal contraction or has not small extremal contractions. Finally we prove that the conjecture holds if X has dimension five.     

On the M/G/1 retrial queueing system with linear control policy

Summary This paper is concerned with the study of a newM/G/1 retrial queueing system in which the delays between retrials are exponentially distributed random variables with linear intensityg(n)=α+nμ, when there aren≥1 customers in the retrial group. This new retrial discipline will be calledlinear control policy. We carry out an extensive analysis of the model, including existence of stationary regime, stationary distribution of the embedded Markov chain at epochs of service completions, joint distribution of the orbit size and the server state in steady state and busy period. The results agree with known results for special cases.     

Continuity of the M/G/c queue

Consider an M/G/c queue with homogeneous servers and service time distribution F. It is shown that an approximation of the service time distribution F by stochastically smaller distributions, say F _n , leads to an approximation of the stationary distribution π of the original M/G/c queue by the stationary distributions π _n of the M/G/c queues with service time distributions F _n . Here all approximations are in weak convergence. The argument is based on a representation of M/G/c queues in terms of piecewise deterministic Markov processes as well as some coupling methods.