Optimal balanced control for call centers

Abstract

In this paper we study the optimal assignment of tasks to agents in a call center. For this type of problem, typically, no single deterministic and stationary (i.e., state independent and easily implementable) policy yields the optimal control, and mixed strategies are used. Other than finding the optimal mixed strategy, we propose to optimize the performance over the set of “balanced” deterministic periodic non-stationary policies. We provide a stochastic approximation algorithm that allows to find the optimal balanced policy by means of Monte Carlo simulation. As illustrated by numerical examples, the optimal balanced policy outperforms the optimal mixed strategy.

Appendices

Appendix A: Implementation of the phantom estimator

In the following we discuss the implementation of the phantom estimator. Denote the waiting time difference between two phantoms by Δ _w (s):

(17)

Note that there are only two different choices for the Markov kernel (P or Q) at the splitting point. Therefore, one of the two phantoms is equal to the nominal path. Specifically, if the decision variable (either zero or one) for the j-th choice is u(j)=1, then the “plus” phantom is equal to the nominal path, which yields $W_{1}^{+} (s, j ) = W_{1}(\theta)$. In this case, using the difference variable Δ _w (s), then average waiting time of the “minus” phantom is obtained by

$$ W_1^- ( s, j ) = W_1^+ (s, j ) - \Delta_w ( s, j ) = W_1(\theta) - \Delta_w ( s, j ). $$

(18)

On the other hand, if u(j)=0, then average waiting time of the “minus” phantom is equal to the nominal path, which yields $W_{1}^{-} X_{\theta}( s, j ) =W_{1}(\theta)$ and

$$ W_1^+ (s, j ) = W_1^- ( s, j ) + \Delta_w ( s, j ) = W_1(\theta) + \Delta_w ( s, j ). $$

(19)

Let $\mathcal{I}(j)$ be the indicator whether the transition kernel of the nominal path is equal to P or Q:

The nominal path coincides with either of the phantoms and the average waiting time of the phantom that has to be additionally simulated is obtained from combining (18) with (19):

$$W_1 ( \theta) - \mathcal{I}(j) \Delta_w(s, j) . $$

Following this train of thoughts, the difference between the cumulative costs in Eq. (15) can be written as

$$ D(s, j) = A \mathcal{I}(j) \bigl( \bigl(W_1 ( \theta) - \alpha \bigr)^2 - \bigl( W_1 ( \theta) - \mathcal{I}(j) \cdot \Delta_w(s,j) - \alpha\bigr)^2 \bigr) $$

(20)

and the resulting gradient estimator is

(21)

In the following we discuss implementation issues for the phantom estimator when the balanced control policy is used. Let θ be a rational number. In this case θ can be written as a fraction of two division-free integers, that is, θ=p/q, for p,q∈ℕ. In the balanced sequence for θ, there will be p 1s in any subsequence of length q of u _θ,ϕ (n), and {u _θ,ϕ (k)} will be periodic with the period length q. For example, the period of the balanced sequence generated for θ=0.3=3/10 and ϕ=0 is: (0,0,0,1,0,0,1,0,0,1) with period length q=10. Let n%q denote the position in the period of the nth element of {u _θ,ϕ (k)}. It is easy to see that if m%q=n%q, then for k≥1, it holds that

$$u_{\theta,\phi}(m+k) = u_{\theta,\phi}(n+k). $$

We extend the state-space of the phantom process $X^{\pm}_{\theta}( n )$ with the auxiliary variable $u_{\theta,\phi}^{\pm}(n)$ denoting at which position in the period of the θ-balanced sequence the process is. For irrational θ, using the fact that, on a computer, θ is given in finite decimal notation, we may obtain a rational number equal or arbitrarily close to θ by applying the continued fraction algorithm on θ (see, for example, Chap. 10 in Hardy and Wright 1960). Then in the coupling schemes we extend the physical state by $u_{\theta,\phi}^{\pm}(n)$. In words, the “plus” and “minus” version couple as soon as the following variables are identical: the number of jobs waiting, the number of type 1 jobs in service, the number of type 2 jobs in service, and the balanced sequences driving the policy have the same position in the period.

Appendix B: Balanced sequences

For an infinite sequence U=(u ₁,u ₂,…) of zeros and ones,

$$s(k,n) = \sum_{j = k}^{k+n-1} u_j , \quad k \leq n , $$

denotes the numbers of ones in the subsequence of length n beginning at the k-th element of U. With this notation s(n):=s(1,n) is the number of ones in the prefix of length n of U. We say that U=(u ₁,u ₂,…) has density θ∈[0,1] if lim _n→∞ s(n)/n exists and is equal to θ. Consider, for example, the case θ=1/2. Then the sequence (0,1,0,1,0,1,…) has rate 1/2 and could be used for modeling a mixing policy at θ=1/2. However, (0,1,0,0,1,1,0,0,0,1,1,1,…) has also rate 1/2. The latter sequence is probably not a good choice as the sequences of consecutive ones and zeros lead to a rater unbalanced system behavior.

In the following we introduce the concept of uniformly recurrent sequences. An infinite sequence U=(u ₁,u ₂,…) is uniformly recurrent if for every finite subsequence W of U, an integer k exists such that W is a subsequence of every subsequence of U of length k. Note that any periodic sequence is uniformly recurrent. For example, the sequence (0,1,0,1,…) is uniformly recurrent as any subsequence of length l is contained in any other finite subsequence of length l+1.

Note that if U has some density θ, it is the asymptotic frequency of the ones in U. If such U is applied as control sequence then policy P is applied with fraction θ of all decision events while Q is applied with remaining fraction 1−θ. Moreover, it follows for k=0,1,… that

$$\lim_{n \rightarrow\infty} \frac{s(k,n)-n \theta}{n} = 0 . $$

Intuitively a small maximal absolute deviation between s(k,n) and nθ means that the ones and zeros are regularly distributed with density θ. Thus U should be such that the maximal absolute deviation is small. It can be shown that for every density θ∈[0,1] there exists U for which the maximal deviation of |s(k,n)−nθ| is smaller than one. Such sequences are called regular. Following, for example, Altman et al. (2000a), a sequence of zeros and ones is called balanced if the difference in number of ones (or zeros which is equivalent) for subsequences of the same length is at most one.

Obviously any regular sequences is a balanced sequence. Also it can be proven (see, for example, Lothaire 2002 Chaps. 1 and 2) that regular sequences are uniformly recurrent.

Example 4

An example of a regular sequence with density θ=2/5 is the periodic sequence (1,0,1,0,0,1,0,1,0,0,1,0,1,0,0,…). If θ is rational then corresponding regular sequences are always periodic with period equal to the denominator of θ. Thus 5 is the period of the sequence in this example. Another example of a regular sequence is the well-known (see Lothaire 2002) Fibonacci sequence (1,0,1,1,0,1,0,1,1,0,1,1,0,…) with density θ= $(\sqrt {5}-1)/2$ which can not be periodic since its density θ is irrational. However, also the Fibonacci sequence is uniformly recurrent as any regular sequence is.

By the classification of balanced sequences (see Morse and Hedlund 1940) it follows that any sequence which is both uniformly recurrent and balanced is in fact a regular sequence. Thus within the subset of uniformly recurrent control sequences to which we restricted earlier regular is equivalent to balanced. Therefore in this paper we use the term “balanced control policy” in the following sense:

A balanced control policy of rate θ∈[0,1] is a deterministic policy mixing P and Q according to an infinite control sequence U=(u ₁,u ₂,…) of zeros and ones where U is regular of density θ. This implies that U is both uniformly recurrent and balanced. Moreover, on average over all decision events P is applied with fraction θ and Q with fraction 1−θ.

Another useful fact is that regular sequences of given density θ have the same finite subsequences (see Lothaire 2002) which implies that regularity of a given density θ uniquely determines the sequence (and thus also the policy) modulo a shift ϕ. Therefore balanced control policies of the same density θ have the same Césaro average performance and thus we may speak of the balanced policy of rate θ instead of a balanced policy of rate θ.

In this paper we compare while varying over θ∈[0,1] the performance of the balanced control policy of rate θ with the Bernoulli policy of rate θ while varying over θ∈[0,1]. For simulation a practical implementation of the balanced policy of rate θ is necessary, several ways to construct regular sequences are known. In this paper we use the one given by (6).

Appendix C: Proof of Lemma 2

Lemma 2

Let $\{ R(U_{\theta,\varPhi}(j))\}_{j=1}^{\infty}$ be a randomized balanced (P,Q)-policy of rate θ. Then for j=1,2,… we have that

$$\mathbb{E}_\varPhi\bigl[R\bigl(U_{\theta,\varPhi}(j)\bigr)\bigr] = \theta P + (1-\theta) Q. $$

Proof

From 0≤θ≤1 it is easily seen that U _θ,Φ (j)∈{0,1} for j=1,2,… . Thus the random variable U _θ,Φ (j) has a Bernoulli distribution. Also for any x∈ℝ we trivially have that

$$ \int_{0}^1 \lfloor x + \phi\rfloor d \phi= x. $$

(22)

By (22) it follows that

Hence

Thus

 □