On the average waiting time for regular routing to deterministic queues

Arie Hordijk ^{∗}  Dinard van der Laan ^{†}

January 10, 2003

Abstract

We provide an algorithm to compute a lower bound for the total average waiting time for the optimal routing to N ≥ 2 deterministic queues. We also obtain an upper bound for the total average waiting time of the optimal routing policy. The upper and lower bounds coincide in case N = 2. Our analysis of deterministic queues is based on results from number theory, involving Farey intervals, best approximation points, convergents and continued fraction expansions. It gives explicit formulae for the average waiting time in case of regular routing to a deterministic queue.

1 Introduction

In this paper we consider the deterministic optimal routing to N parallel inhomogeneous queues. We assume that the arrival epochs are a deterministic sequence, T = 0, 1, 2, … say, and the service times at the queues are deterministic, S_{i} at queue i say. In stochastic models there is a difference between openloop control in which there is no state information and closed-loop control in which the controller knows the loads at the queues. In the deterministic model there is no such difference in state information. But, as in the open-loop control we describe the routing policy as a sequence of the numbers of the queues to which the successive arriving customers are routed. For an overview of papers on open-loop control see [12]. An overview of results on closed-loop control can be found in [11] and [15].

The optimal routing for homogeneous queues, i.e. queues with S_{i} = S, for i = 1, …, N, is well-known to be the round robin policy (see [17]). For inhomogeneous queues the computation of the optimal policy may be difficult (see [4] and [6] for approximating algorithms). In the seminal paper [8] Hajek showed for an exponential queue that the optimal routing of a given fraction of the customers to that queue is a regular or bracket sequence. For N = 2 it is proved in [1] and [3] that the optimal routing to each of the queues is a regular or bracket sequence for general stochastic interarrival and service time sequences. However, if N ≥ 3 the optimal routing fails to be the composition of regular sequences, because in general regular sequences can not be combined to a feasible routing policy. Finding the optimal routing becomes a combinatorial hard problem for N ≥ 3. In [16] the deterministic model is studied where the system is fully loaded, i.e. ∑_{i=1}^{N} \frac{1}{S_{i}} = 1, and a mathematical programming problem is designed to compute the optimal routing. In this paper we consider the case ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1. Now finding the optimal routing is split into two parts:

∗Dept. of Mathematics, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands. E-mail:

hordijk@math.leidenuniv.nl . Telephone: (+31)715277146

†Dept. of Mathematics, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands. E-mail: dvdlaan@math.leidenuniv.nl . Telephone: (+31)715277140

• Find best routing densities d_{i} to the queues i = 1, …, N

• Construct a best allocation pattern for the given routing densities d_{i}

For N = 2 the second part is completely solved, since the allocation uses regular sequences as mentioned above. In [7] the problem of finding the best densities is studied, and a very interesting connection is made there to combinatorics on words. Moreover, a recursive formula for the average waiting time for a given density is obtained by using a (backward) continued fraction decomposition of the inverse of the service time, and an algorithm is derived to compute an optimal routing sequence. The present paper is in the same spirit but considers the more general case of N ≥ 2 queues. We provide an algorithm to compute a lower bound for the total average waiting time for the optimal routing by finding best routing densities given that the routing to each of the queues is regular. In [12] we derived an upper bound for the total waiting time for a given allocation pattern as a function of its unbalance (which is a measure of the deviation from the regular routing). Combining these results we use a billiard sequence to provide an upper bound for the average waiting time of the optimal routing policy too. The upper and lower bounds coincide in case N = 2. This paper provides an analysis of deterministic queues based on results from number theory, involving Farey intervals, best approximation points, convergents and continued fraction expansions.

The paper is organized as follows. Section 2 gives a description of the queueing system together with the definitions of routing policy and regular sequences. In section 3 the Lindley recursion together with the extension of Little’s relation between the average number of customers and the waiting time is given for the routing model. Its proof is given in the appendix. In section 4 Farey intervals are introduced. The period sequence of the upper bracket sequence of which the rational density belongs to some Farey interval is determined as a finite composition of the period sequences of the upper bracket sequences of the end-points densities of that Farey interval. This result gives the key to the proof that for upper bracket sequences the average number of customers L(d) is a linear function of the density d on a Farey interval. This result is proved in section 5, where it is also shown that L(d) is a convex function of the density. In section 6 best lower approximation points of \frac{1}{S_{i}}, where S_{i} is the service time for queue i, are introduced. They correspond to the so-called jump points in [7], where recursive formulae for computing the average waiting time W (d_{i}) were obtained. The main result of section 6 is the explicit formulae for the average number of customers L_{S_{i}}(d_{i}) (and of the average waiting time W (d_{i})) at best lower approximation points d_{i} of \frac{1}{S_{i}}. Together with the fact that consecutive best lower approximation points constitute a Farey interval on which L_{S_{i}}(d_{i}) is linear, this provides an efficient algorithm for computing L_{S_{i}}(d_{i}) given that the best lower approximation points are known. Section 6 also contains an exposition, based on well-known results from number theory, how the ordered set of best approximation points can be computed by the use of the continued fraction expansion and the induced convergents. The efficient algorithm to compute this ordered set is illustrated by an example. In section 7 the above mentioned results are applied to find the minimal regular routing. More precisely we derive an algorithm for computing

min_{d_{1}+···+d_{N} =1} ∑_{i=1}^{N} L_{S_{i}}(d_{i}),

using the above mentioned convexity and linearity properties on Farey intervals. The algorithm is again illustrated by an example. We characterize the set of densities for which the minimum is achieved. Also, as a consequence of the characterization we find that there exist minimizing rational densities if ∑_{i=1}^{N} \frac{1}{S_{i}} > 1. Indeed, the algorithm computes such a set of rational densities. For N = 2 this implies that the regular policy with these densities is periodic, and hence an optimal periodic routing policy is found by the algorithm. For N ≥ 3 the algorithm computes a lower bound for the optimal routing policy. Together with results of [12] which we summarize in section 7, we find a billiard sequence with rational densities (hence a periodic policy) which has an average waiting time not larger than the lower bound plus \frac{N}{2} − 1. The performance of this billiard sequence should be close to optimal if N is not too large. For N = 2 the lower bound equals the upper bound.

2 Description of the queueing system and notations

We consider a queueing system with N ≥ 2 parallel FIFO (First In First Out) queues. Customers arrive at moments T_{1}, T_{2}, … with T_{1} = 0 and T_{1} ≤ T_{2} ≤ … and the n -th arriving customer has to be routed to one of the queues at the moment T_{n} of its arrival. We consider deterministic routing policies using no state information. Then the routing policy is described by an infinite word U = (U_{1}, U_{2}, …) on the alphabet {1, 2, …, N} where U_{n} is the queue to which the n - th arriving customer is routed (see [12]). For every queue i ∈ {1, 2, …, N} we have a sequence u^{i} = (u_{1}^{i}, u_{2}^{i}, …) of zeros and ones where u_{n}^{i} = 1 if U_{n} = i and u_{i}^{n} = 0 if U_{n} ≠ i. Then u^{i} is called the routing, splitting or admission sequence for queue i (see for example [8], [23], [2], [12] and [16]).

For a sequence of nonnegative integers u = (u_{1}, u_{2}, …) we define the counting function κ_{u} : ℤ_{≥0} → ℤ by κ_{u}(n) := ∑_{i=1}^{n} u_{i}. Thus κ_{u}(n) is the partial sum of the first n terms. Note that if u^{i} is a splitting sequence then κ_{u^{i}}(n) is the number of customers that is routed to queue i among the first n arriving customers.

Put δ_{n} := T_{n+1} −T_{n} for n = 1, 2, . . .. Then {δ_{n}} is the sequence of interarrival times. Further for queue i ∈ {1, 2, …, N} we have a sequence of service times {σ_{j}^{i}}_{j=1,2,...}, where σ_{j}^{i} is the service time of the j -th customer that is routed to queue i.

In a deterministic queueing system the interarrival times are constant and the service times are constant for every queue. Thus there exist positive numbers δ, σ_{1}, σ_{2}, …, σ_{N} such that δ = δ_{1} = δ_{2} = … and σ_{i} = σ_{1}^{i} = σ_{2}^{i} = σ_{3}^{i} = … for i = 1, 2, …, N. By time scaling with a factor δ we assume without loss of generality that δ = 1 and then S_{i} := \frac{σ_{i}}{δ} is the service time of server i for the new time scale. Thus such a deterministic queueing system with N parallel FIFO queues can be described by the vector (S_{1}, S_{2}, …, S_{N}) of service times when the interarrival times are assumed to be equal to the time unit. In the sequel we use the description (S_{1}, S_{2}, …, S_{N}) system when we mean a queueing system with deterministic interarrival and service times as described above.

2.1 Routing policies and words

A routing policy U is described by a sequence of symbols (letters) (U_{1}, U_{2}, …) and can be seen as an (infinite) word (sequence) on a finite alphabet. If we have N parallel queues then U is a so-called ℕ -word on the alphabet {1, 2, …, N}. We refer to the beginning of section 2 of [12] for the definitions of the density of a letter, period of a word, subword, prefix, suffix, concatenation of sequences, etc. See [18] and [10] for more on words and combinatorics.

We recall that the domain of a word I is a subinterval of ℤ and the length of a finite (i.e I is finite) word W is denoted by | W |. Moreover, a sequence (word) of zeros and ones is said to have density d if the letter 1 has density d. It follows that the density of letter 0 is 1 − d in that case.

Definition 2.1 Let u be an infinite sequence (I - word) of zeros and ones for some appropriate infinite interval I. We say that u is regular with density d if for every N ∈ ℕ we have for every subword u′ of u of length N that |u′|_{1}, the number of ones in u′, equals ⌊Nd⌋ or ⌈Nd⌉. In that case we also say that the set H_{1} ⊆ I, corresponding to the places of the ones, is a regular set (of density d).

The following theorem follows for I = ℕ from the classification of balanced sequences in [20] and the fact that regular sequences are particular balanced sequences (see [25]).

Theorem 2.2 Let u and I be as above. Then u is regular with density d if and only if there exists θ ∈ ℝ such that u_{t} = ⌊(t + 1)d + θ⌋ − ⌊td + θ⌋ for every t ∈ I or there exists a θ′ ∈ ℝ such that u_{t} = ⌈(t + 1)d + θ′⌉ − ⌈td + θ′⌉ for every t ∈ I.

Regular sequences are also called bracket sequences and Theorem 2.2 shows the reason for this. Moreover, the θ in the bracket form is called the phase of the bracket sequence. In the sequel all infinite regular sequences we consider are ℕ -words. Hence if I is infinite, then I = ℕ.

Definition 2.3 The upper bracket sequence of density d is the ℕ-word u = (u_{1}, u_{2}, …, u_{n}) on the alphabet {0,1} for which u_{t} = ⌈td⌉ − ⌈(t − 1)d⌉ for every t ∈ ℕ. The lower bracket sequence of density d is the ℕ-word u = (u_{1}, u_{2}, …, u_{n}) on the alphabet {0,1} for which u_{t} = ⌊td⌋ − ⌊(t − 1)d⌋ for every t ∈ ℕ.

If we make the assumption that letter 0 is smaller than letter 1 in the alphabet {0, 1} then the upper bracket sequence of density d is the lexicographic greatest regular ℕ -word of density d and the lower bracket sequence is the lexicographic smallest regular sequence of density d. We have the following properties of these sequences (see [12]).

Lemma 2.4 For the upper bracket sequence u of density d we have that κ_{u}(n) = ⌈nd⌉ for every n ∈ ℤ_{≥0} and for the lower bracket sequence v of density density d we have that κ_{v}(n) = ⌊nd⌋ for every n ∈ ℤ_{≥0}.

Lemma 2.5 Let u and v be as in Lemma 2.4. Then for the support sets H_{1}(u) and H_{1}(v) of the ones of these bracket sequences we have that

H_{1}(u) = \{⌊\frac{t}{d}⌋ + 1\}_{t=0}^{∞} and H_{1}(v) = \{⌈\frac{t}{d}⌉\}_{t=1}^{∞}.

3 Definitions and preliminary results

For t ≥ 0 and i ∈ {1, 2, …, N} let V_{i}(t) be the remaining workload measured in time units for server i at time t and let B_{i}(t) be the number of customers waiting in the buffer of queue i at moment t. Then \underline{V} (t) := (V_{1}(t), V_{2}(t), …, V_{N}(t)) is the vector of remaining workloads in the system at time t, \underline{B}(t) := (B_{1}(t), B_{2}(t), …, B_{N}(t)) is the vector of buffer contents at time t and B(t) := ∑_{i=1}^{N} B_{i}(t) is the total number of customers waiting in one of the buffers at time t. Let G_{i}(t) = {t′ ∈ [0, t] : V_{i}(t′) = 0} and let m_{i}(t) be the Lebesque measure of G_{i}(t). Then m_{i}(t) is the time that server i was idle up to time t. We say that a server i is non-idling in a time interval [t_{1}, t_{2}] if m_{i}(t_{1}) = m_{i}(t_{2}).

For an (S_{1}, S_{2}, …, S_{N}) system we assume that V_{i}(0) = 0 for i = 1, 2, …, N and for a given routing policy U = (U_{1}, U_{2}, …) and time t > 0 we can compute \underline{V} (t) recursively by Lindley’s formula which gives that

V_{i}(t) = max(V_{i}(t′) + u_{t′}^{i} · S_{i} + (t′ − t), 0) for i = 1, 2, …, N where t′ = ⌈t⌉ − 1. (1)

Note that we define V_{i}(t) such that the function t → V_{i}(t) is left continuous, but not right continuous in general. However, the right discontinuities of this function can only be at integer t. Moreover, it follows inductively that for every i ∈ {1, 2, …, N} and t, t_{0} ∈ ℝ with t ≥ t_{0} ≥ 0 we have that

V_{i}(t) − V_{i}(t_{0}) = (κ_{u^{i}}(⌈t⌉) − κ_{u^{i}}(⌈t_{0}⌉)) · S_{i} + (m_{i}(t) − m_{i}(t_{0})) − (t − t_{0}). (2)

Note that in an (S_{1}, S_{2}, …, S_{N}) system it holds that T_{t} = t − 1 for t = 1, 2, … and thus κ_{u^{i}}(⌈t⌉) is the number of customers routed to server i before time t. Further for an (S_{1}, S_{2}, …, S_{N}) system we have for every t ≥ 0 that B_{i}(t) = ⌊\frac{V_{i}(t)}{S_{i}}⌋ for i = 1, 2, …, N and thus \underline{B}(t) and B(t) can be easily obtained from \underline{V} (t).

Definition 3.1 Let U = (U_{1}, U_{2}, …) be a routing policy. Then we define

L(U) := lim sup_{t′→∞} \frac{1}{t′} · ∫_{t=0}^{t′} B(t)d(t)

as the average number of customers waiting in one of the buffers for policy U. We define

W (U) := lim sup_{t′→∞} \frac{1}{t′} ∑_{t=1}^{t′} V_{U_{t}}(T_{t})

as the average waiting time for the arriving customers for policy U.

We show in the appendix as an extension of Little’s law for routing policies that

L(U) = λ · W (U) if W (U) < ∞, (3)

where λ is the arrival rate of customers in the queueing system. In an (S_{1}, S_{2}, …, S_{N}) system we have by the time scaling that the arrival rate of customers λ is equal to 1 and thus it follows by (3) that

L(U) = W (U) if W (U) < ∞. (4)

The objective in this paper is optimal routing with respect to minimizing the average waiting time. Thus we look for routing policies U such that L(U) and W (U) are minimized.

For this problem it is useful to consider for a particular server i ∈ {1, 2, …, N} the average number of customers waiting in buffer i and the average waiting time of the customers that are routed to this server i. So, for i = 1, 2, …, N we define

L^{i}(U) := lim sup_{t′→∞} \frac{1}{t′} · ∫_{t=0}^{t′} B_{i}(t)d(t)

as the average number of customers waiting in buffer i for policy U. Recall that H_{i}(U) is the support of letter i of the ℕ -word U and for t ∈ ℕ let I_{t} = {1, 2, …, t}. Moreover, for i = 1, 2, …, N we define

W^{i}(U) := lim sup_{t′→∞} \frac{1}{| H_{i}(U) ∩ I_{t′} |} · ∑_{t∈H_{i}(U)∩I_{t′}} V_{i}(T_{t}) = lim sup_{t′→∞} \frac{1}{κ_{u^{i}}(t′)} · ∑_{t=1}^{t′} u_{t}^{i} · V_{i}(t − 1) (5)

as the average waiting time of customers routed to server i for policy U.

Note that L^{i}(U) and W^{i}(U) depend on u^{i}, the routing sequence for server i, but they do not depend on u^{j} if j ≠ i. Therefore, if the routing to server i is according to some infinite sequence w of zeros and ones then we also use the notations L^{i}(w) and W^{i}(w) instead of L^{i}(U) and W^{i}(U) respectively. Moreover, if we consider a single queue of the system and it is not necessary to refer to the number of the server i then we just write L(w) and W (w) respectively. We define \overline{d_{i}} := lim sup_{t→∞} \frac{κ_{u^{i}}(t)}{t} which we call the upper density of routing sequence u^{i} and we define \underline{d_{i}} := lim inf_{t→∞} \frac{κ_{u^{i}}(t)}{t} which we call the lower density of u^{i}. If \overline{d_{i}} = \underline{d_{i}} then the routing sequence u^{i} has a density d_{i} := lim_{t→∞} \frac{κ_{u^{i}}(t)}{t} and d_{i} is the arrival rate for server i in that case. In the appendix we show that

L^{i}(u^{i}) = d_{i} · W^{i}(u^{i}) if d_{i} exists and W^{i}(u^{i}) < ∞. (6)

By (4) and (6) we obtain the following proposition.

Proposition 3.2 Let U be a routing policy applied in an (S_{1}, S_{2}, …, S_{N}) system such that routing sequence u^{i} has density d_{i} and W^{i}(u^{i}) < ∞ for i = 1, 2, …, N. Then

W (U) = L(U) = ∑_{i=1}^{N} L^{i}(u^{i}) = ∑_{i=1}^{N} d_{i} · W^{i}(u^{i}).

Note that ∑_{i=1}^{N} d_{i} = 1 if the conditions of Proposition 3.2 are satisfied.

4 The upper bracket sequence and Farey intervals

In the sequel we denote by w(d) the upper bracket sequence of density d. Thus for the counting function κ we have that κ_{w(d)}(n) = ⌈n · d⌉ for every n ∈ ℤ_{≥0}. If d is rational, d = \frac{p}{q} with gcd(p, q) = 1 let ω(d) := (w(d)_{1}, w(d)_{2}, …, w(d)_{q}) be the period word of w(d). Note that we use the slightly different notations w(d) and ω(d) for respectively the upper bracket sequence and the period word of this sequence. Let d_{1}, d_{2} be rational fractions with 0 ≤ d_{1} ≤ d_{2} ≤ 1, d_{i} = \frac{p_{i}}{q_{i}} and gcd(p_{i}, q_{i}) = 1 for i = 1, 2. Then I = [d_{1}, d_{2}] is called a Farey interval if and only if q_{1} · p_{2} − p_{1} · q_{2} = 1. From elementary number theory (see for example [9], chapter 3, page 23) we have the following facts about Farey intervals. If [d_{1}, d_{2}] is a Farey interval and d_{0} = \frac{p_{1}+p_{2}}{q_{1}+q_{2}} . Then I′ = [d_{1}, d_{0}] and I′′ = [d_{0}, d_{2}] are also Farey intervals. Moreover, all rational numbers in (d_{1}, d_{2}) have denominator greater than or equal to q_{1} + q_{2}.

4.1 Factorisation of the upper bracket sequence

Recall that a factor of a word is a finite subsequence of consecutive letters of the word. Let X be a set of nonempty finite words over some alphabet A. A finite X - factorisation of a finite word w is a finite sequence (x_{1}, x_{2}, …, x_{n}) such that w = x_{1}x_{2} … x_{n} and x_{i} ∈ X for i = 1, 2, …, n. An infinite X -factorisation of an ℕ - word w is an infinite sequence (x_{1}, x_{2}, …) such that w = x_{1}x_{2} … and x_{i} ∈ X for i = 1, 2, . . .. Sometimes we just say factorisation instead of (in)finite X -factorisation. The set X is called a code (ℕ -code) if every finite respectively infinite word over the alphabet A has at most one X - factorisation. It is easily seen that every ℕ -code is also a code, but the converse is not true (see [18], chapter 6, page 177).

Lemma 4.1 Let d_{1}, d_{2} ∈ ℚ ∩ [0, 1] with d_{1} ≠ d_{2}. Then ω(d_{1}) and ω(d_{2}) are not powers of the same word.

Proof. Suppose that there exist k, l ∈ ℕ and a sequence of zeros and ones u such that u^{k} = ω(d_{1}) and u^{l} = ω(d_{2}). Then it follows that d_{1}, the density of ω(d_{1}), equals the density of u and also d_{2}, the density of ω(d_{2}), equals the density of u. Hence d_{1} = d_{2}, which gives a contradiction. □

Theorem 4.2 Let d_{1}, d_{2} ∈ ℚ ∩ [0, 1] with d_{1} ≠ d_{2}. Then X := {ω(d_{1}), ω(d_{2})} is an ℕ-code for words over the alphabet {0, 1}.

Proof. By Lemma 4.1 and Corollary 6.2.5 in [18] (which follows immediately from the so-called Defect theorem) there exists neither a finite nor an infinite nontrivial relation between ω(d_{1}) and ω(d_{2}). Hence X is a code and also an ℕ-code.

Lemma 4.3 Let I = [d_{1}, d_{2}] be a Farey interval and d_{0} = \frac{p_{1}+p_{2}}{q_{1}+q_{2}} as above. Then ω(d_{0}) = ω(d_{2})ω(d_{1}).

Proof. We put u := ω(d_{2})ω(d_{1}). We have gcd(p_{1} + p_{2}, q_{1} + q_{2}) = 1 because q_{1} + q_{2} is the smallest denominator in (d_{1}, d_{2}). Hence | u |=| ω(d_{0}) |= q_{1} + q_{2} and it suffices to prove that κ_{u}(n) = κ_{ω(d_{0})}(n) for 1 ≤ n ≤ q_{1} + q_{2}. For 1 ≤ n ≤ q_{2} we have that

κ_{ω(d_{0})}(n) = ⌈d_{0} · n⌉ ≤ ⌈d_{2} · n⌉ = κ_{u}(n).

Suppose ⌈d_{0} · n⌉ < ⌈d_{2} · n⌉ for some 1 ≤ n ≤ q_{2}. Then there exist a positive integer k such that \frac{n·(p_{1}+p_{2})}{q_{1}+q_{2}} ≤ k < \frac{n·p_{2}}{q_{2}} . Hence n · q_{2} · (p_{1} + p_{2}) ≤ k · q_{2} · (q_{1} + q_{2}) < n · p_{2} · (q_{1} + q_{2}) and thus 0 ≤ q_{2} · (k · (q_{1} + q_{2}) − n · (p_{1} + p_{2})) < n. Since n ≤ q_{2} it follows that k · (q_{1} + q_{2}) − n · (p_{1} + p_{2}) = 0 and thus d_{0} = \frac{p_{1}+p_{2}}{q_{1}+q_{2}} = \frac{k}{n} with 1 ≤ n ≤ q_{2}, which gives a contradiction. So, κ_{u}(n) = κ_{ω(d_{0})}(n) for 1 ≤ n ≤ q_{2}. Analogously it follows that κ_{u}(n) = κ_{ω(d_{0})}(n) for q_{2} + 1 ≤ n ≤ q_{1} + q_{2}. □

Theorem 4.4 Let I = [d_{1}, d_{2}] be a Farey interval and put X := {ω(d_{1}), ω(d_{2})}. Then for every d ∈ (d_{1}, d_{2}) there exists a unique infinite X-factorisation of the upper bracket sequence w(d) of density d. Moreover, if d is rational then there exists a unique finite X-factorisation of the period word ω(d) of w(d).

Proof. The factorization is obtained by the following algorithm. Initialize by putting x_{0} = d_{1} = \frac{p_{0}}{q_{0}} , y_{0} = d_{2} = \frac{r_{0}}{s_{0}} , u_{0} = ω(x_{0}), v_{0} = ω(y_{0}) and i := 0. At step i we have that x_{i} = \frac{p_{i}}{q_{i}} with gcd(p_{i}, q_{i}) = 1 and y_{i} = \frac{r_{i}}{s_{i}} with gcd(r_{i}, s_{i}) = 1 and we do the following iteratively: z_{i} := \frac{p_{i}+r_{i}}{q_{i}+s_{i}}, w_{i} := v_{i}u_{i}. If d = z_{i} then stop. Else if d < z_{i} then x_{i+1} := x_{i}, u_{i+1} := u_{i}, y_{i+1} := z_{i}, v_{i+1} := w_{i}. Else if d > z_{i} then x_{i+1} := z_{i}, u_{i+1} := w_{i}, y_{i+1} := y_{i}, v_{i+1} := v_{i}. If the algorithm has not stopped then let i := i + 1 and go to the next step. From the algorithm it follows by induction that w_{i} is factored in u_{0} = ω(d_{1}) and v_{0} = ω(d_{2}) for every i ∈ ℤ_{≥0} and by Lemma 4.3 we have that w_{i} = ω(z_{i}). If d is rational then the algorithm stops for some i = N and then d = z_{N} and ω(d) = ω(z_{N}) = w_{N} is factored in ω(d_{1}) and ω(d_{2}). If d is irrational then lim_{i→∞} z_{i} = d and lim_{i→∞} w_{i} = w(d). □

5 The average number of customers in a single queue

We consider a single queue i ∈ {1, 2, …, N} of an (S_{1}, S_{2}, …, S_{N}) system. Let S = S_{i} be the service time in this queue. We suppose that the routing sequence for this queue has density d ∈ [0, 1]. Then d is the arrival rate of customers for this queue and the traffic intensity for this queue is ρ := d · S. The stability condition for the queue is ρ ≤ 1, or equivalently d ≤ \frac{1}{S}. Suppose that the routing sequence u^{i} is a regular sequence of density d ∈ [0, 1]. Then it is proved in [14] that W^{i}(u^{i}) and L^{i}(u^{i}) exist for every ρ and are independent of the initial phase θ. It follows from Loynes’ stability theorem (see [5]) that the limit is finite for ρ < 1. For ρ = 1 this is proved in [16]. If ρ > 1 then the queue is not stable and L^{i}(u^{i}) = W^{i}(u^{i}) = ∞ in that case. Combining these results it follows that if u is a regular sequence of density d ∈ [0, 1] then

L^{i}(u) = L^{i}(w(d)) and W^{i}(u) = W^{i}(w(d)). (7)

Thus for the average number of customers waiting in a single queue all regular sequences of density d have the same performance as the upper bracket sequence w(d) of density d. Moreover, this performance does only depend on the service time S of the queue and the density d. Therefore to simplify notation we write L_{S}(d), or L(d), if the value of S is clear from the context, instead of the more involved L^{i}(w(d)). Similarly we write W_{S}(d) or W (d) instead of W^{i}(w(d)). So, for a single queue with constant service time S we have that L(d) = L_{S}(d) is the average number of customers waiting in the queue when the routing to the queue is according to a regular sequence of density d and W (d) = W_{S}(d) is the average waiting time of these customers. Moreover, in [3] it is proved for rather general settings that routing according to a regular sequence of density d is optimal among all routing sequences of (lower) density at least d. This result implies the following lemma.

Lemma 5.1 For every service time S and any routing sequence u^{i} of (lower) density at least d we have that W^{i}(u^{i}) ≥ W (d) and L^{i}(u^{i}) ≥ L(d).

In the sequel if we consider a single queue then the remaining workload for the server (measured in time units) at time t is simply denoted by V (t) instead of V_{i}(t). Remember that the interarrival times of customers at the routing point are constant and equal to 1 by time scaling and that we assume that V (0) = 0. One of the objectives in this paper is to give an efficient algorithm for computing L_{S}(d) and W_{S}(d) for arbitrary S > 0 and d ∈ [0, 1]. For this it is useful to consider for a fixed value of S the functions d → L(d) and d → W (d) , where both these functions have domain [0, 1] and codomain [0, ∞]. In [7] an algorithm is given to compute W_{S}(d) and some properties of the function W (d) are obtained. The following lemma follows directly from the results in [7].

Lemma 5.2 If d ≤ \frac{1}{⌈S⌉} where S is the service time then W (d) = 0

From Lemma 5.2 it follows that W (d) = 0 for every d ∈ [0, 1] if the service time S ≤ 1, which is a trivial case. Therefore we assume in the sequel that S > 1. If S > 1 then the queue is stable if d ∈ [0, \frac{1}{S}] and unstable if d ∈ (\frac{1}{S} , 1]. Thus by (6) we have the following lemma.

Lemma 5.3

L(d) = d · W (d) if d ∈ [0, \frac{1}{S}].

Moreover, if d ∈ (\frac{1}{S} , 1] then L(d) = W (d) = ∞.

So, there is a direct relation between L(d) and W (d) and if you have computed one of them then the other follows from Lemma 5.3. In [16] the value of W (d) was computed for d = \frac{1}{S}, the most right point of the interval of stability and traffic intensity ρ = 1. The following result was obtained.

Lemma 5.4 For service time S > 1 we have that W (\frac{1}{S}) = \frac{1}{2} if S is irrational. If S = \frac{p}{q} with p, q ∈ ℕ, gcd(p, q) = 1 then W (\frac{1}{S}) = \frac{1}{2} − \frac{1}{2q}.

The following properties of the function W (d) are proved in [7].

Theorem 5.5 For given service time S > 1 the function W (d) is continuous and monotonically increasing on the interval [0, \frac{1}{S}]. Moreover, on the interval [\frac{1}{⌈S⌉}, \frac{1}{S}] the function W (d) is strictly increasing.

It also follows from the more general results in [14] that the function L(d) is continuous and monotonically increasing on the interval of stability. We prove some properties of the function L(d) which do not hold for W (d). These properties of the function L(d) will be used in our algorithm for computing L_{S}(d) and W_{S}(d).

Let u be a finite sequence of zeros and ones of length k and suppose that k consecutively arriving customers are routed to the queue according to u. Suppose that the first of these k customers arrives at time t_{0} and thus the last at time t_{0} + k − 1. Then we say that u lasts from t_{0} to t_{0} + k and thus V (t_{0}) is the workload at the beginning of u and V (t_{0} + k) is the workload at the end of u. We say that u is workload non-increasing if for every initial workload V (t_{0}) it holds that V (t_{0} + k) ≤ V (t_{0}). Note that from Lindley’s equation (1) it follows that for this it is sufficient that V (t_{0}) = 0 implies that V (t_{0} + k) = 0. The following lemma is useful for proving properties of L(d).

Lemma 5.6 Let d ∈ ℚ, 0 ≤ d ≤ 1. Then ω(d), the period word of the upper bracket sequence of density d, is workload non-increasing if and only if d ≤ \frac{1}{S}.

Proof. Let d = \frac{p}{q} where p, q ∈ ℕ with gcd(p, q) = 1. Then q = |ω(d)| and we may assume that ω(d) lasts from some t_{0} ∈ ℤ_{≥0} to t_{1} = t_{0} + q ∈ ℤ_{≥0}. Suppose that d > \frac{1}{S}. Then by (2) we have for S = S_{i}

V (t_{1}) = V (t_{0})+κ_{ω(d)}(q)·S_{i} +(m_{i}(t_{1})−m_{i}(t_{0}))−q ≥ V (t_{0})+p·S_{i} −q = V (t_{0})+q(d·S_{i} −1) > V (t_{0}).

Hence ω(d) is not workload non-increasing if d > \frac{1}{S}. Conversely, suppose that d ≤ \frac{1}{S} and V (t_{1}) > V (t_{0}). Let t^{∗} = max : t ∈ [t_{0}, t_{1}] for which V (t^{∗}) ≤ V (t_{0}). Since V (t) is monotonically non-increasing in any interval (a, a + 1] for which a ∈ ℤ_{≥0} it follows that t^{∗} ∈ ℤ_{≥0}. Moreover, it follows that the server is non-idling in the interval [t^{∗}, t_{1}]. So, by (2) and Lemma 2.4 we have that

V (t_{1}) = V (t^{∗})+(κ_{ω(d)}(q)−κ_{ω(d)}(t^{∗} −t_{0}))·S −(t_{1} −t^{∗}) ≤ V (t_{0})+(p−⌈d(t^{∗} −t_{0})⌉)·S −(t_{0} +q −t^{∗}) ≤

V (t_{0}) + (p − d(t^{∗} − t_{0})) · S − (t_{0} + q − t^{∗}) ≤ V (t_{0}) + (p − d(t^{∗} − t_{0})) · \frac{1}{d} − (t_{0} + q − t^{∗}) = V (t_{0}),

which contradicts V (t_{1}) > V (t_{0}). Hence ω(d) is workload non-increasing if d ≤ \frac{1}{S}. □

Suppose that d ∈ ℚ, d ≤ \frac{1}{S} and that the customers are routed to the queue according to the upper bracket sequence w(d) = ω(d)^{∞}. Then it follows from Lemma 5.6 that if the workload is 0 at the beginning of an ω(d) factor then it is also 0 at the end of the factor and thus at the beginning of the next factor. So, since the workload is 0 at t = 0, the beginning of the first ω(d) factor, it follows that the workload is 0 at the end of every ω(d) factor. Thus the workload process is renewed after every ω(d) factor. Hence we have the following corollary.

Corollary 5.7 If d ∈ ℚ, d ≤ \frac{1}{S} then W (d) is equal to the average waiting time of customers routed to the queue during the first period ω(d). Similarly L(d) is equal to the average number of customers in the queue during the first period ω(d).

In [14] the following theorem is shown in a more general form. In fact, the convexity of L(d) for any stationary sequence of generally distributed interarrival times and stationary generally distributed service times is proved, which implies the special deterministic case. We give a simple proof for the deterministic queueing system of this paper.

Theorem 5.8 For given service time S > 1 the function L(d) is convex on the interval of stability [0, \frac{1}{S}].

Proof. Since L(d), the average number of customers in the queue under the bracket policy with density d, is a continuous function of d on the interval of stability [0, \frac{1}{S}], it is sufficient to show the following mid-point convexity of L(d) (see [19] Theorem 1.7). Let d_{1} = \frac{p_{1}}{q_{1}} and d_{2} = \frac{p_{2}}{q_{2}} where p_{i}, q_{i} ∈ ℕ with gcd(p_{i}, q_{i}) = 1 and period words w_{i} := ω(d_{i}), i = 1, 2. Define the mid-point d := \frac{1}{2}(d_{1} + d_{2}) and show that L(d) ≤ \frac{1}{2}(L(d_{1}) + L(d_{2})). In order to prove this we consider the admission sequence

w = (w_{1}^{q_{2}}w_{2}^{q_{1}})^{∞} (8)

A simple calculation gives that the density of w equals

\frac{p_{1}q_{2} + p_{2}q_{1}}{2q_{1}q_{2}} = d.

It follows from Lemma 5.6 that the queue is empty after each w_{i} factor. Since | w_{1}^{q_{2}} |=| w_{2}^{q_{1}} |= q_{1}q_{2} it follows that

L(w) = \frac{1}{2}(L(d_{1}) + L(d_{2})).

Hence, since the bracket policy is optimal (see [1]) we have

L(d) ≤ L(w) = \frac{1}{2}(L(d_{1}) + L(d_{2})).

□

The following theorem shows that the function L(d) is not only convex, but also piecewise linear. This property will be of great use in our algorithm for computing L_{S}(d) and W_{S}(d).

Theorem 5.9 Let d_{1}, d_{2} ∈ [0, 1] be rational numbers such that I = [d_{1}, d_{2}] is a Farey interval and d_{1} < d_{2} ≤ \frac{1}{S}, where S is the service time. Let d ∈ I, d = λ · d_{1} + (1 − λ) · d_{2}, where λ ∈ [0, 1]. Then L(d) = λ · L(d_{1}) + (1 − λ) · L(d_{2}).

Proof. Arriving customers are routed to the queue according to routing sequence w(d) and to compute L(d) we assume that the workload is 0 at starting moment t = 0. According to Theorem 4.4 w(d) can be factored in factors ω(d_{1}) and ω(d_{2}). From the assumption d_{1} < d_{2} ≤ \frac{1}{S} and Lemma 5.6 it follows that both the factors ω(d_{1}) and ω(d_{2}) are workload non-increasing. Thus if the workload in the queue is 0 at the beginning of such a factor then it is also 0 at the end of the factor and thus it is 0 at the beginning of the next factor. So, the queue is always empty at the beginning of an ω(d_{1}) or ω(d_{2}) factor. Hence the average number of customers in the queue during any ω(d_{1}) or ω(d_{2}) factor is L(d_{1}) respectively L(d_{2}). Hence, if p is the fraction of time the system is in an ω(d_{1}) factor and thus (1 − p) is the fraction of time the system is in an ω(d_{2}) factor then

L(d) = p · L(d_{1}) + (1 − p) · L(d_{2}). (9)

It is easily seen that p = λ and thus (9) is valid with p = λ. This implies the theorem. □

Remark. Thus we have that the function L(d) is linear on Farey intervals contained in the stability interval. The linearity of the function L(d) on Farey intervals can be generalised to some more generally distributed service times if the following condition holds. If [d_{1}, d_{2}] with 0 ≤ d_{1} < d_{2} ≤ 1 is the Farey interval then both the ω(d_{1}) and ω(d_{2}) factor should be workload non-increasing with probability one. If this condition holds then the proof of Theorem 5.9 remains valid.

6 Computation of the average waiting time

6.1 The value of W (d) in best lower approximation points

Definition 6.1 Let x > 0 be a given real number and let r = \frac{p}{q} with p ∈ ℤ_{≥0}, q ∈ ℕ with gcd(p, q) = 1 be a rational number in the interval (0, x]. Then r is a best lower approximation of x if there does not exist a rational number in the interval (r, x]) with denominator smaller than or equal to q.

Note that x is a best lower approximation of x itself if and only if x is a rational number.

Lemma 6.2 Let S > 1 be the service time and d be a best lower approximation of \frac{1}{S}. Then during an ω(d) factor the server is non-idling before the last letter of the factor. Moreover, if d = \frac{p}{q} where p, q ∈ ℕ with gcd(p, q) = 1 and the arriving customers are routed to the queue according to the upper bracket sequence w(d) then

V (t) = ⌈⌈t⌉d⌉S − t for every t ∈ [0, q − 1]. (10)

Proof. Let d = \frac{p}{q} where p, q ∈ ℕ with gcd(p, q) = 1. Then q = |ω(d)| and we may assume that ω(d) lasts from some t_{0} ∈ ℤ_{≥0} to t_{1} = t_{0} + q ∈ ℤ_{≥0}. We have that 0 < d ≤ \frac{1}{S} < 1 and thus q ≥ 2. Recall that V (t) denotes the workload in the queue at moment t ≥ 0. Let k ∈ {1, 2, …, q − 1}. Suppose that ⌈d · k⌉S − k ≤ 0. Then it follows that d = \frac{p}{q} ≤ \frac{⌈d·k⌉}{k} ≤ \frac{1}{S}. Since \frac{⌈d·k⌉}{k} is a rational number with

denominator smaller than q it follows that d < \frac{⌈d·k⌉}{k} ≤ \frac{1}{S}, which contradicts that d is a best lower approximation of \frac{1}{S}. Thus ⌈d · k⌉S − k > 0. Hence by (2) and Lemma 2.4 we have that

V (t_{0} + k) ≥ V (t_{0}) + κ_{ω(d)}(k) · S − k = V (t_{0}) + ⌈d · k⌉S − k > V (t_{0}).

So, we have that V (t_{0} + k) > V (t_{0}) for every k ∈ {1, 2, …, q − 1} and thus V (t) > 0 for every t ∈ (t_{0}, t_{0} + q − 1]. Thus the server is non-idling in the time interval [0, q − 1]. So, by (2) and Lemma 2.4 we have for every t ∈ [0, q − 1] that

V (t) = V (0) + κ_{w(d)}(⌈t⌉) · S − t = ⌈⌈t⌉d⌉S − t.
□

Theorem 6.3 Let S > 1 be the service time and d be a best lower approximation of \frac{1}{S}. Let d = \frac{p}{q} where p, q ∈ ℕ with gcd(p, q) = 1. Then

W (d) = \frac{p − 1}{2p}(pS + 1 − q) and (11)

L(d) = \frac{p − 1}{2q}(pS + 1 − q). (12)

Proof. We have that d ≤ \frac{1}{S}. Thus according to Lemma 5.7 it holds that W (d) is equal to the average waiting time in the first period ω(d). From |ω(d)| = q and (5) it follows that

W (d) = \frac{1}{κ_{ω(d)}(q)} · ∑_{t=1}^{q} ω(d)_{t} · V (t − 1) = \frac{1}{p} · ∑_{t=0}^{q−1} ω(d)_{t+1} · V (t). (13)

By Definition 2.3 and (10) we have for t = 0, 1 …, q − 1 that

ω(d)_{t+1} · V (t) = (⌈(t + 1)d⌉ − ⌈t · d⌉)(⌈td⌉S − t). (14)

Let A = \{0, ⌊\frac{1}{d}⌋, ⌊\frac{2}{d}⌋, …\}. Then it follows by Lemma 2.5 for every t ∈ ℤ_{≥0} that

w(d)_{t+1} = ⌈(t + 1)d⌉ − ⌈t · d⌉ = \{ \begin{matrix}1 & if t ∈ A \\ 0 & if t ∉ A \end{matrix} (15)

On combining (13),(14) and (15) we obtain

W (d) = \frac{1}{p} · ∑_{t∈A∩\{0,1,...,q−1\}}(⌈td⌉S − t) = \frac{1}{p} · ∑_{t′=0}^{p−1}(⌈⌊\frac{t′}{d} ⌋d⌉S − ⌊\frac{t′}{d} ⌋) =

\frac{S}{p} · ∑_{t′=0}^{p−1}(⌈⌊\frac{t′}{d} ⌋d⌉) − \frac{1}{p} · ∑_{t′=0}^{p−1}(⌊t′ · \frac{q}{p}⌋). (16)

It is easily seen that if 0 < x < 1 then ⌈⌊\frac{k}{x}⌋x⌉ = k for k = 0, 1, . . .. Thus

\frac{S}{p} · ∑_{t′=0}^{p−1}(⌈⌊\frac{t′}{d} ⌋d⌉) = \frac{S}{p} · ∑_{t′=0}^{p−1} t′ = \frac{S(p − 1)}{2}.

Moreover, analogously to Theorem 100 in [9] (cf. [12], Lemma 5.7) it follows that

∑_{t′=0}^{p−1}(⌊t′ · \frac{q}{p}⌋) = \frac{1}{2}(p − 1)(q − 1).

Hence by (16) we have that

W (d) = \frac{S(p − 1)}{2} − \frac{1}{2p}(p − 1)(q − 1) = \frac{p − 1}{2p}(pS + 1 − q).

By Lemma 5.3 it follows that

L(d) = d · W (d) = \frac{p − 1}{2q}(pS + 1 − q).

□

So, for given service time S > 1 the values of W (d) and L(d) are easily obtained for all best lower approximations of \frac{1}{S}. Before we give a procedure to obtain iteratively the best lower approximations of \frac{1}{S}, we first have the following lemma.

Lemma 6.4 If I is a subinterval of positive Lebesque measure of the open interval (0, 1), then there exists a unique rational number of lowest denominator in I.

Proof. Since I has positive Lebesque measure and the rational numbers are dense in the real numbers, I contains rational numbers. Suppose there exist a, b ∈ ℕ such that [\frac{a}{b}, \frac{a+1}{b}] ⊆ I and there exist no rational numbers in the interval (\frac{a}{b}, \frac{a+1}{b}) with denominator smaller or equal than b. Then \frac{a}{b}, \frac{a+1}{b} are consecutive elements of the Farey series of order b (see [9], page 23) and thus we have by Theorem 28 in [9] that (a + 1)b − ba = b = 1. Hence \frac{a}{b} is an integer which contradicts that I ⊆ (0, 1). □

Let r_{1} be the rational number of lowest denominator in the interval (0, \frac{1}{S}] and put i := 1. Do the following iteratively. If r_{i} = \frac{1}{S} then stop. Else if r_{i} < \frac{1}{S} then let r_{i+1} be the rational number of lowest denominator in the interval (r_{i}, \frac{1}{S}] and let i := i + 1. According to Lemma 6.4 the r_{i} are well defined.

Lemma 6.5 The number d is a best lower approximation of \frac{1}{S} if and only if d = r_{i} for some i ∈ ℕ. Moreover, if S is rational then there exists some k ∈ ℕ such that

\frac{1}{⌈S⌉} = r_{1} < r_{2} < … < r_{k} = \frac{1}{S} .

If S is irrational then

\frac{1}{⌈S⌉} = r_{1} < r_{2} < … and lim_{i→∞} r_{i} = \frac{1}{S} .

Proof. Let r_{i} = \frac{p_{i}}{q_{i}} with p_{i}, q_{i} ∈ ℕ and gcd(p_{i}, q_{i}) = 1. We first prove that r_{1} = \frac{1}{⌈S⌉}. Suppose that q_{1} < ⌈S⌉. Then r_{1} = \frac{p_{1}}{q_{1}} ≥ \frac{1}{q_{1}} > \frac{1}{S}, which gives a contradiction. Since \frac{1}{⌈S⌉} ≤ \frac{1}{S} we have that q_{1} = ⌈S⌉ and by Lemma 6.4 it follows that r_{1} = \frac{1}{⌈S⌉}. By definition and Lemma 6.4 we have that the r_{i} are best lower approximations. Moreover, both the sequence r_{1}, r_{2}, … of best lower approximations and the sequence q_{1}, q_{2}, … of denominators are strictly increasing. Let d = \frac{a_{1}}{a_{2}} be a best lower approximation of \frac{1}{S} with a_{1}, a_{2} ∈ ℕ and gcd(a_{1}, a_{2}) = 1. Then there exist some l ∈ ℕ such that q_{i} ≥ a_{2} if and only if i ≥ l. From the definition it follows that q_{l} = a_{2} and thus we have by Lemma 6.4 that r_{l} = \frac{a_{1}}{a_{2}} = d. So, d is a best lower approximation of \frac{1}{S} if and only if d = r_{i} for some i ∈ ℕ. If S is rational then \frac{1}{S} is a best lower approximation of itself and thus we have that r_{k} = \frac{1}{S} for some k ∈ ℕ. If S is irrational then \frac{1}{S} is irrational and it follows from the definition that r_{i} < \frac{1}{S} for every i ∈ ℕ. Thus we have that r := lim_{i→∞} r_{i} ≤ \frac{1}{S}. Suppose that r < \frac{1}{S}. Then by definition there exist no rational numbers in the interval (r, \frac{1}{S}), which contradicts the fact that the rational numbers are dense in the real numbers. □

Lemma 6.6 If r_{i}, r_{i+1} are consecutive best lower approximations of \frac{1}{S} then [r_{i}, r_{i+1}] is a Farey interval.

Proof. Let r_{i} = \frac{a_{1}}{b_{1}} with a_{1}, b_{1} ∈ ℕ, gcd(a_{1}, b_{1}) = 1 and let r_{i+1} = \frac{a_{2}}{b_{2}} with a_{2}, b_{2} ∈ ℕ, gcd(a_{2}, b_{2}) = 1. By definition and Lemma 6.4 we have that b_{1} < b_{2} and that there exist no rational numbers in the interval (r_{i}, r_{i+1}) with denominator smaller or equal than b_{2}. Hence \frac{a_{1}}{b_{1}} , \frac{a_{2}}{b_{2}} are consecutive members of the Farey series of order b_{2} and thus by Theorem 28 in [9] we have that b_{1} · a_{2} − a_{1} · b_{2} = 1. Thus [r_{i}, r_{i+1}] is a Farey interval. □

For every service time S > 1 we have by Theorem 5.8 that the function L(d) is convex on the interval [0, \frac{1}{S}]. Moreover, it follows from Lemma 5.2 that L(d) is linear on [0, r_{1}] and from Theorem 5.9 and Lemma 6.6 that L(d) is linear on every interval [r_{i}, r_{i+1}]. Thus it follows from Lemma 6.5 that L(d) is piecewise linear on the interval [0, \frac{1}{S}]. Therefore the slope of L(d) can only change in the best lower approximation points r_{i}. In [7] these points r_{i} are called jump points. According to Lemma 5.3 L(d) = W (d) = ∞ for d > \frac{1}{S}.

The value of L_{S}(d) and W_{S}(d) can be computed exactly for every given service time S > 1 and d ∈ [0, 1]. The following algorithm can be used to compute L(d) and W (d) for any d.

Algorithm. If 0 ≤ d ≤ \frac{1}{⌈S⌉} then L(d) = W (d) = 0. Else if \frac{1}{S} < d ≤ 1 then L(d) = W (d) = ∞. Else if d = \frac{1}{S} then W (d) is given by Lemma 5.4 and L(d) = d · W (d). Else we have that \frac{1}{⌈S⌉} < d < \frac{1}{S}. Then there exist consecutive best lower approximations points r_{i} and r_{i+1} such that d ∈ [r_{i}, r_{i+1}] (in the following subsection we give a method based on the continued fraction expansion of \frac{1}{S} to determine these points r_{i}, r_{i+1} in an efficient way). If d = r_{i} or d = r_{i+1} then W (d) and L(d) are given by Theorem 6.3. Else r_{i} < d < r_{i+1}. Then compute L(r_{i}) and L(r_{i+1}) by applying Theorem 6.3 and put λ = \frac{r_{i+1}−d}{r_{i+1}−r_{i}}. Then L(d) = λ · L(r_{1}) + (1 − λ) · L(r_{2}) and we can compute W (d) by W (d) = \frac{L(d)}{d}.

We illustrate the algorithm by the following example. Example. We calculate W_{S}(d) for S = \frac{31}{19} and d = \frac{\sqrt{6}}{4}. The best lower approximations of \frac{1}{S} = \frac{19}{31} are r_{1} = \frac{1}{2}, r_{2} = \frac{3}{5}, r_{3} = \frac{11}{18} and r_{4} = \frac{19}{31}. Since d ∈ [\frac{11}{18}, \frac{19}{31}] we obtain from Theorem 6.3 that L(\frac{11}{18}) = \frac{5}{19}

and L(\frac{19}{31}) = \frac{9}{31}. We have λ = \frac{\frac{19}{31} −d}{\frac{19}{31} − \frac{11}{18}} = 342 − \frac{279\sqrt{6}}{2} and L(d) = λ · L(\frac{11}{18}) + (1 − λ) · L(\frac{19}{31}) = \frac{72\sqrt{6}}{19} − 9.

Hence W (d) = \frac{L(d)}{d} = \frac{288}{19} − 6\sqrt{6}.

6.2 Best lower approximations and the continued fraction expansion

In this subsection we show that the best lower approximations r_{1}, r_{2}, … of \frac{1}{S} can be obtained by applying the continued fraction expansion of \frac{1}{S}. This gives for given d ∈ (\frac{1}{⌈S⌉}, \frac{1}{S}) an efficient algorithm for computing consecutive best lower approximation r_{i}, r_{i+1} of \frac{1}{S} such that d ∈ [r_{i}, r_{i+1}].

See for example [9] for definitions and properties of the continued fraction expansion of a real number. Put α := \frac{1}{S}. The partial quotients a_{0}, a_{1}, … of the (simple) continued fraction expansion of α are recursively defined by:

\{ \begin{matrix}a_{0} = ⌊α⌋; & α_{1} = \frac{1}{α−a_{0}} \\ a_{n} = ⌊α_{n}⌋; & α_{n+1} = \frac{1}{α_{n}−a_{n}} for n = 1, 2, … \end{matrix} \} .

Then

α = a_{0} + \frac{1}{a_{1} + _{\frac{1}{a_{2}+... \frac{1}{an+...}}}} := [a_{0}, a_{1}, …, a_{n}, …].

Since S > 1 we have that 0 < α < 1 and thus a_{0} = 0. Moreover, note that a_{1}, a_{2}, … are positive integers. If α is rational then α_{m} −a_{m} = 0 for some in m ∈ ℕ and the process of computing the partial quotients stops for n = m. Then the continued fraction expansion of α is finite and α = [0, a_{1}, a_{2}, …, a_{m}]. If α is irrational then the continued fraction expansion of α is infinite.

We define p_{n}, q_{n} recursively by

\begin{matrix}p_{0} = a_{0}, & p_{1} = a_{0}a_{0} + 1, & p_{n} = a_{n}p_{n−1} + p_{n−2}(n ≥ 2), \\ q_{0} = 1, & q_{1} = a_{1}, & q_{n} = a_{n}q_{n−1} + q_{n−2}(n ≥ 2) \end{matrix} .

Then \frac{p_{n}}{q_{n}} = [a_{0}, a_{1}, …, a_{n}] and \frac{p_{n}}{q_{n}} is called the nth convergent of α = [a_{0}, a_{1}, …]. If α = [a_{0}, a_{1}, …, a_{m}] is rational then the mth convergent \frac{p_{m}}{q_{m}} = α is the last convergent of α and thus the number of convergents of α is finite. If α is irrational then the number of convergents of α is infinite. We put x_{n} := \frac{p_{n}}{q_{n}}. Then the convergents of α have the following properties (see [9]).

Lemma 6.7 (i) The even convergents x_{2n} increase strictly with n, while the odd convergents x_{2n+1} decrease strictly.

(ii) Every odd convergent is greater than any even convergent.

(iii) Every even convergent is smaller than α and every odd convergent is greater than α (except that in case of rational α the last convergent is equal to α, whether this be even or odd).

(iv) If α is irrational then lim_{n→∞} x_{n} = α.

Lemma 6.8 If n > 1, 0 < q ≤ q_{n}, and \frac{p}{q} ≠ \frac{p_{n}}{q_{n}}, then

| \frac{p_{n}}{q_{n}} − α |<| \frac{p}{q} − α | .

Lemma 6.7 and Lemma 6.8 have the following corollary.

Corollary 6.9 The even convergents \frac{p_{2n}}{q_{2n}}, n = 1, 2, … are best lower approximations of α.

So, the even convergents obtained by the continued fraction expansion of α are best lower approximations of α. However, in general the converse is not true. First of all if α is equal to the n-th convergent \frac{p_{n}}{q_{n}} for some odd positive integer then this odd convergent is also a best approximation of α. Moreover, to obtain all best lower approximations of α from the continued fraction of α we also have to consider the so-called even intermediate convergents, which we define now.

Definition 6.10 Let α = [a_{0}, a_{1}, …] if α is irrational or α = [a_{0}, a_{1}, …, a_{m}] for some m ∈ ℕ if α is rational. Then a rational number \frac{p}{q} is an even intermediate convergent of α if and only if p = p_{n−2} + c · p_{n−1} and q = q_{n−2} + c · q_{n−1} for some positive even integer n (with n smaller or equal than m if α is rational) and c ∈ \{1, 2, …, a_{n} − 1\}, where \frac{p_{n}}{q_{n}} is the n-th convergent of α.

Note that for every positive even integer n ≤ m we have that

\frac{p_{n−2}}{q_{n−2}} < \frac{p_{n−2} + p_{n−1}}{q_{n−2} + q_{n−1}} < \frac{p_{n−2} + 2p_{n−1}}{q_{n−2} + 2q_{n−1}} < … < \frac{p_{n−2} + (a_{n} − 1)p_{n−1}}{q_{n−2} + (a_{n} − 1)q_{n−1}} < \frac{p_{n−2} + (a_{n})p_{n−1}}{q_{n−2} + (a_{n})q_{n−1}} = \frac{p_{n}}{q_{n}} ≤ α.

(17)

So, all even intermediate convergents of α are smaller than α. Moreover, it can be shown (see for example [21]) that every even intermediate convergent \frac{p}{q} of α is a best lower approximations of α. Conversely, we have the following lemma, which follows directly from results in [21].

Lemma 6.11 Let r_{i} = \frac{p}{q} with gcd(p, q) = 1 be a best lower approximation of α ∈ (0, 1). Then one of the following three possibilities holds for r_{i}.

• r_{i} is an even convergent \frac{p_{2n}}{q_{2n}} with n ≥ 1 of α.

• r_{i} is an even intermediate convergent of α.

• r_{i} is equal to α, which is an odd convergent of itself.

Recall that we ordered the best lower approximations r_{1}, r_{2}, … of α ∈ (0, 1) such that r_{1} < r_{2} < … and that \frac{p_{n}}{q_{n}} is the n -th convergent of α. Using the preceding results it is possible to identify the ordered set B := (r_{1}, r_{2}, …) of best lower approximations of α in terms of the convergents and the partial quotients of α. Doing this we have three slightly different cases. First note that p_{0} = 0 and q_{0} = 1.

1. If α = [0, a_{1}, a_{2}, …] is irrational then the ordered set B is infinite,

B = (\frac{p_{1}}{q_{1} + 1}, \frac{2p_{1}}{2q_{1} + 1}, …, \frac{a_{2}p_{1}}{a_{2}q_{1} + 1} = \frac{p_{2}}{q_{2}} , \frac{p_{3} + p_{2}}{q_{3} + q_{2}} , \frac{2p_{3} + p_{2}}{2q_{3} + q_{2}} , …, \frac{p_{4}}{q_{4}} , …). (18)

2. If α is rational and an even convergent of itself, α = [0, a_{1}, a_{2}, …, a_{k}] = \frac{p_{k}}{q_{k}} where k is even, then B is finite,

B = (\frac{p_{1}}{q_{1} + 1}, \frac{2p_{1}}{2q_{1} + 1}, …, \frac{a_{2}p_{1}}{a_{2}q_{1} + 1} = \frac{p_{2}}{q_{2}} , \frac{p_{3} + p_{2}}{q_{3} + q_{2}} , \frac{2p_{3} + p_{2}}{2q_{3} + q_{2}} , …,

\frac{p_{k−2}}{q_{k−2}} , \frac{p_{k−1} + p_{k−2}}{q_{k−1} + q_{k−2}} , \frac{2p_{k−1} + p_{k−2}}{2q_{k−1} + q_{k−2}} , …, \frac{a_{k}p_{k−1} + p_{k−2}}{a_{k}q_{k−1} + q_{k−2}} = \frac{p_{k}}{q_{k}} = α). (19)

3. If α is rational and an odd convergent of itself, α = [0, a_{1}, a_{2}, …, a_{k}] = \frac{p_{k}}{q_{k}} where k is odd, then B is finite,

B = (\frac{p_{1}}{q_{1} + 1}, \frac{2p_{1}}{2q_{1} + 1}, …, \frac{a_{2}p_{1}}{a_{2}q_{1} + 1} = \frac{p_{2}}{q_{2}} , \frac{p_{3} + p_{2}}{q_{3} + q_{2}} , \frac{2p_{3} + p_{2}}{2q_{3} + q_{2}} , …, \frac{p_{k−1}}{q_{k−1}} , \frac{p_{k}}{q_{k}} = α). (20)

Example. Suppose that α = \frac{339}{410}. Then the continued fraction algorithm gives that α = [0, 1, 4, 1, 3, 2, 3, 2] and the convergents \{\frac{p_{n}}{q_{n}} \}_{n=0}^{7} of α are \frac{0}{1}, \frac{1}{1}, \frac{4}{5}, \frac{5}{6}, \frac{19}{23}, \frac{43}{52}, \frac{148}{179}, \frac{339}{410}. By (20) it follows that the ordered set of best lower approximations of α is B = (\frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{9}{11}, \frac{14}{17}, \frac{19}{23}, \frac{62}{75}, \frac{105}{127}, \frac{148}{179}, \frac{339}{410}).

We now give the algorithm based on continued fraction expansion for computing for any d ∈ (\frac{1}{⌈S⌉}, \frac{1}{S}) two consecutive best lower approximations r_{i}, r_{i+1} of α = \frac{1}{S} such that d ∈ [r_{i}, r_{i+1}].

Algorithm. Apply the continued fraction algorithm to find consecutively the partial quotients a_{1}, a_{2}, … and the corresponding convergents \frac{p_{1}}{q_{1}} , \frac{p_{2}}{q_{2}} , … of α until we have found an even convergent \frac{p_{2n}}{q_{2n}}, that is greater or equal than d or we have that \frac{p_{N−1}}{q_{N−1}} < d < \frac{p_{N}}{q_{N}} = α for some odd integer N, N > 1. Note that according to Lemma 6.7 this first part of the algorithm stops after finite time. If we have the latter case then we put r_{i} = \frac{p_{N−1}}{q_{N−1}} and r_{i+1} = \frac{p_{N}}{q_{N}}. Then d ∈ (r_{i}, r_{i+1}) and we are finished. So, suppose we have the former case. Then by Lemma 6.7 we have that \frac{p_{2n−2}}{q_{2n−2}} < d ≤ \frac{p_{2n}}{q_{2n}} and by (17) there exists some

unique integer k, 0 ≤ k < a_{2n} such that \frac{k·p_{2n−1}+p_{2n−2}}{k·q_{2n−1}+q_{2n−2}} < d ≤ \frac{(k+1)·p_{2n−1}+p_{2n−2}}{(k+1)·q_{2n−1}+q_{2n−2}} . It is easily seen that

this holds for k = ⌊\frac{d·q_{2n−2}−p_{2n−2}}{p_{2n−1}−d·q_{2n−1}} ⌋. By putting r_{i} = \frac{k·p_{2n−1}+p_{2n−2}}{k·q_{2n−1}+q_{2n−2}} and r_{i+1} = \frac{(k+1)·p_{2n−1}+p_{2n−2}}{(k+1)·q_{2n−1}+q_{2n−2}} we have that d ∈ (r_{i}, r_{i+1}] and we are finished.

We give an example to illustrate this algorithm.

Example.

Suppose α := \frac{1}{S} = \frac{7433}{9734} + \frac{\sqrt{18773}}{9734} and d = 0.77761. Then applying the continued fraction algorithm to α we consecutively find a_{0} = 0 , \frac{p_{0}}{q_{0}} = \frac{0}{1}, a_{1} = 1 , \frac{p_{1}}{q_{1}} = 1, a_{2} = 3, \frac{p_{2}}{q_{2}} = \frac{3}{4}, a_{3} = 2, \frac{p_{3}}{q_{3}} = \frac{7}{9}, a_{4} = 137, \frac{p_{4}}{q_{4}} = \frac{962}{1237} and we have that d ≤ \frac{p_{4}}{q_{4}} . Then we compute that k = ⌊\frac{d·q_{2}−p_{2}}{p_{3}−d·q_{3}} ⌋ = 73 and it follows that

r_{i} = \frac{k·p_{3}+p_{2}}{k·q_{3}+q_{2}} = \frac{514}{661} and r_{i+1} = \frac{(k+1)·p_{3}+p_{2}}{(k+1)·q_{3}+q_{2}} = \frac{521}{670}.

Remark. The number of operations needed for this algorithm based on the continued fraction expansion is linear in the number of digits of the denominator of r_{i+1}. So, this algorithm is very efficient in practice. Moreover, as illustrated in the last example of the previous subsection the exact value of W_{S}(d) can be easily calculated after we have obtained the consecutive best lower approximations r_{i}, r_{i+1} of \frac{1}{S} such that d ∈ (r_{i}, r_{i+1}]. So, this is an efficient method for calculating the exact value of W_{S}(d) and in most cases it should be quicker than the recursive algorithm used in [7]. Indeed, if this recursive algorithm is applied then, when d ∈ (r_{i}, r_{i+1}], all the best lower approximations r_{1} < r_{2} < … < r_{i} < r_{i+1} of \frac{1}{S} and the corresponding value of W_{S}(r_{n}) for n = 1, 2, …, i + 1 are explicitly calculated. So, if q is the denominator of r_{i+1} then this recursive algorithm for computing W_{S}(d) has to do a number of order q calculations in worst case. In our algorithm not all the best lower approximations of \frac{1}{S} are explicitly calculated. Indeed, only the convergents of \frac{1}{S} and the last two best lower approximations r_{i}, r_{i+1} with corresponding values W_{S}(r_{i}) and W_{S}(r_{i+1}) are calculated. Therefore our algorithm only has to do a number of order log(q) calculations.

7 Minimization over multiple queues

7.1 Properties of a minimal point

In this section we obtain results on the minimimal average waiting time in case of N parallel queues as introduced in section 2.

For a given \overline{S} := (S_{1}, S_{2}, …, S_{N}) queueing system with N parallel FIFO queues and (d_{1}, d_{2}, …, d_{n}) ∈ [0, 1]^{N} we put

L\overline{S}(d_{1}, d_{2}, …, d_{n}) = L(d_{1}, d_{2}, …, d_{n}) := ∑_{i=1}^{N} L_{S_{i}}(d_{i}).

Let U be a routing policy applied in an \overline{S} = (S_{1}, S_{2}, …, S_{N}) system such that routing sequence u^{i} has density d_{i} for i = 1, 2, …, N. Then by Proposition 3.2 and Lemma 5.1 we have that

W (U) = ∑_{i=1}^{N} L^{i}(u^{i}) ≥ ∑_{i=1}^{N} L_{S_{i}}(d_{i}) = L\overline{S}(d_{1}, d_{2}, …, d_{n}) (21)

Put

H^{N} := {(x_{1}, x_{2}, …, x_{N}) ∈ ℝ^{N} : x_{i} ≥ 0, i = 1, 2, …, N and ∑_{i=1}^{N} x_{i} = 1.

It is easily seen that if some routing policy U has densities d_{1}, d_{2}, …, d_{N} then (d_{1}, d_{2}, …, d_{N}) ∈ H^{N}. Moreover, since H^{N} is a convex and compact subset of ℝ^{N} and L\overline{S}(d_{1}, d_{2}, …, d_{n}) is convex in (d_{1}, d_{2}, …, d_{n}) by Theorem 5.8 we have the following lemma.

Lemma 7.1 For an \overline{S} := (S_{1}, S_{2}, …, S_{N}) queueing system put

M(\overline{S}) := \{(d_{1}, d_{2}, …, d_{N}) ∈ H : L\overline{S}(d_{1}, d_{2}, …, d_{N}) = min_{H^{N}} L\overline{S}(x_{1}, x_{2}, …, x_{N})\}. (22)

Then M(\overline{S}) is an nonempty convex and compact subset of H^{N}.

We put

R(\overline{S}) = R((S_{1}, S_{2}, …, S_{N})) := L\overline{S}(d_{1}, d_{2}, …, d_{n}), where (d_{1}, d_{2}, …, d_{n}) ∈ M(\overline{S}).

Then R(\overline{S}) is a lower bound for the average waiting time in the \overline{S} system, since Theorem 4.1 and Theorem 4.2 of [3] give the following result, where we do not require that the routing sequences u^{i} have densities d_{i} for i = 1, 2, …, N.

Proposition 7.2 For any routing policy U applied to the \overline{S} := (S_{1}, S_{2}, …, S_{N}) queueing system we have that

W (U) ≥ R(\overline{S}).

We also have upper bounds for the average waiting time in the \overline{S} = (S_{1}, S_{2}, …, S_{N}) system. By Theorem 4.7 in [12] we have the following proposition.

Proposition 7.3 Let U be a periodic routing policy such that the routing sequence u^{i} has density d_{i} for i = 1, 2, …, N. Then

W (U) ≤ L\overline{S}(d_{1}, d_{2}, …, d_{N}) + \overline{O}(U),

where \overline{O}(U) ≥ 0 is the so-called total primal unbalance of U, which is some kind of measure of the irregularity of the sequence (see [12] or [13] for the definition of unbalance).

The total primal unbalance can always be bounded. Indeed, by Theorem 5.1 in [12] we have the following proposition.

Proposition 7.4 Let rational densities d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1 be given. Then there exists a periodic routing policy U such that routing sequence u^{i} has density d_{i} for i = 1, 2, …, N and \overline{O}(U) ≤ \frac{N}{2} − 1.

We note that such a routing sequence policy U with given densities d_{i} and \overline{O}(U) ≤ \frac{N}{2} − 1 can easily be obtained by constructing a so-called billiard sequence (see [12]). Moreover, the upper bound of Proposition 7.3 is tight. Note that by the definition of L\overline{S}(d_{1}, d_{2}, …, d_{N}) we have that W (U) = L\overline{S}(d_{1}, d_{2}, …, d_{N}) if for every i ∈ \{1, 2 …, N\} the routing sequence u^{i} is a regular sequence of density d_{i}. Indeed, from the definition of the total primal unbalance it follows that \overline{O}(U) = 0 if and only if u^{i} is a regular sequence for i = 1, 2, …, N. Suppose that ∑_{i=1}^{N} \frac{1}{S_{i}} < 1. Then for every (x_{1}, x_{2}, …, x_{N}) ∈ H^{N} there exists some i for which x_{i} > \frac{1}{S_{i}} and thus we have by Lemma 5.3 that R(\overline{S}) = ∞. So, by Proposition 7.2 it follows that W (U) = ∞ for every routing policy U. Thus the queueing system is unstable in this case and optimal policies do not exist. Therefore we assume in the sequel that ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1. We shall show in Proposition 7.14 that the lower bound R(\overline{S}) is finite and in Theorem 7.15 that there exist policies U with W (U) ≤ \frac{N−1}{2}.

Moreover, we characterize the set M(\overline{S}) and we show that this set contains some special rational point if ∑_{i=1}^{N} \frac{1}{S_{i}} > 1. From this it follows that there exist a periodic policy for which the average waiting time is bounded by R((S_{1}, S_{2}, …, S_{N}))+ \frac{N}{2} −1. A corollary of this result is that there exists a periodic policy which is optimal if N = 2, which was proved in [7]. Finally we give an algorithm to obtain a rational point x ∈ M(\overline{S}) and the corresponding lower bound R(\overline{S}). If N = 2 then the rational point obtained by the algorithm yields an optimal routing policy as in [7]. If N > 2 then in general it is not possible to obtain an optimal policy from the rational point, but it can be used to construct periodic policies with performance close to the lower bound R(\overline{S}).

For given service time S > 1 and d ∈ [0, 1] we define

Definition 7.5

l_{S}(d) = \{ \begin{matrix}0 & if d ∈ [0, \frac{1}{⌈S⌉}] \\ lim_{ε↓0} \frac{L_{S}(d)−L_{S}(d−ε)}{ε} & if d ∈ (\frac{1}{⌈S⌉}, \frac{1}{S}] \\ ∞ & if d ∈ (\frac{1}{S} , 1] \end{matrix} (23)

and

r_{S}(d) = \{ \begin{matrix}0 & if d ∈ [0, \frac{1}{⌈S⌉}) \\ lim_{ε↓0} \frac{L_{S}(d+ε)−L_{S}(d)}{ε} & if d ∈ [\frac{1}{⌈S⌉}, \frac{1}{S}) \\ ∞ & if d ∈ [\frac{1}{S} , 1] \end{matrix} . (24)

From Theorem 5.8 it follows that l_{S}(d) and r_{S}(d) are monotonically non-decreasing in d. Moreover, they assume only countably many values, since they are constant between consecutive best lower approximations of \frac{1}{S}.

The following lemma follows directly from Theorem 6.3 and Lemma 6.5.

Lemma 7.6 If S > 1 is rational then l_{S}(\frac{1}{S}) < ∞. If S > 1 is irrational then l_{S}(\frac{1}{S}) = ∞.

The following proposition gives an necessary and sufficient condition for elements of M(\overline{S}) and thus the set M(\overline{S}) is completely characterized by this.

Proposition 7.7 Let \overline{S} = (S_{1}, S_{2}, …, S_{N}) and x = (x_{1}, x_{2}, …, x_{N}) ∈ H^{N}. Then x ∈ M(\overline{S}) if and only if for every pair i, j ∈ {1, 2, …, N} it holds that either l_{S_{i}}(x_{i}) ≤ r_{S_{j}}(x_{j}) < ∞ or r_{S_{j}}(x_{j}) = ∞.

Proof. We first prove the ” only if ” part. Suppose that x ∈ M(\overline{S}) and there exist i, j ∈ \{1, 2, …, N\} such that r_{S_{j}}(x_{j}) < ∞ and l_{S_{i}}(x_{i}) > r_{S_{j}}(x_{j}). Since ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1 and thus L\overline{S}(x_{1}, x_{2}, …, x_{N}) = R(\overline{S}) < ∞ it follows that 0 ≤ x_{n} ≤ \frac{1}{S_{n}} for n = 1, 2, …, N. Moreover, it follows from (23) and (24) that x_{i} > \frac{1}{⌈S_{i}⌉} > 0 and x_{j} < \frac{1}{S_{j}}. Put y(ϵ) := (y_{1}, y_{2}, …, y_{N}), where y_{i} := x_{i}−ε, y_{j} := x_{j}+ε and y_{l} := x_{l} for l ≠ i, j.

Then L\overline{S}(x)−L\overline{S}(y(ε)) = ∑_{n=1}^{N}(L_{S_{n}}(x_{n})−L_{S_{n}}(y_{n})) = (L_{S_{i}}(x_{i})−L_{S_{i}}(x_{i} −ε))−(L_{S_{j}}(x_{j} +ε)−L_{S_{j}}(x_{j})) and thus

lim_{ε↓0} \frac{1}{ε} · (L\overline{S}(x) − L\overline{S}(y(ε))) = l_{S_{i}}(x_{i}) − r_{S_{j}}(x_{j}) > 0.

So, if ε′ > 0 is an arbitrarily small positive number then y(ε′) ∈ H^{N} and L\overline{S}(x) − L\overline{S}(y(ε′)) > 0, which contradicts the fact that x ∈ M(\overline{S}). The ” if ” part follows from the convexity of the function. □

By Lemma 7.6 and Proposition 7.7 we have the following corollary.

Corollary 7.8 Let x = (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) where \overline{S} = (S_{1}, S_{2}, …, S_{N}) with ∑_{i=1}^{N} \frac{1}{S_{i}} > 1. Then for every j ∈ \{1, 2, …, N\} for which S_{j} is irrational we have that x_{j} < \frac{1}{S_{j}}.

Proof. Since ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1 we have that R(\overline{S}) < ∞ and thus x_{i} ≤ \frac{1}{S_{i}} for i = 1, 2, …, N. Suppose that S_{j} is irrational and x_{j} = \frac{1}{S_{j}}. Then by Lemma 7.6 we have that l_{S_{j}}(x_{j}) = ∞. Since ∑_{i=1}^{N} \frac{1}{S_{i}} > 1 and

∑_{i=1}^{N} x_{i} = 1 there exists some k ≠ j for which x_{k} < \frac{1}{S_{k}}. Then r_{S_{k}}(x_{k}) < ∞ = l_{S_{j}}(x_{j}), which according to Proposition 7.7 contradicts the fact that x = (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) □.

Theorem 7.9 Let \overline{S} = (S_{1}, S_{2}, …, S_{N}) be such that ∑_{i=1}^{N} \frac{1}{S_{i}} > 1. Then there exists some x = (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) and some j ∈ \{1, 2, …, N\} such that for every i ≠ j it holds that x_{i} is either a best lower approximation of \frac{1}{S_{i}} or x_{i} = 0.

Proof. Suppose that x = (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) and there exist k, l ∈ \{1, 2, …, N\} , k < l such that x_{k}, x_{l} ≠ 0 and neither x_{k} is a best lower approximation of \frac{1}{S_{k}} nor x_{l} is a best lower approximation of \frac{1}{S_{l}}. Put r_{0} = 0 and let \frac{1}{⌈S_{k}⌉} = r_{1} < r_{2} < … be the best lower approximations of \frac{1}{S_{k}}. Similarly, put s_{0} = 0 and let \frac{1}{⌈S_{l}⌉} = s_{1} < s_{2} < … be the best lower approximations of \frac{1}{S_{l}}. By Corollary 7.8 we have that 0 < x_{k} < \frac{1}{S_{k}} and 0 < x_{l} < \frac{1}{S_{l}}. Hence there exist n, m ∈ ℤ_{≥0} such that r_{n} < x_{k} < r_{n+1} and s_{m} < x_{l} < s_{m+1}. By Theorem 5.9 we have that the functions L_{S_{k}}(d) and L_{S_{l}}(d) are linear in d on the intervals [r_{n}, r_{n+1}] and [s_{m}, s_{m+1}] respectively. Let x(ε) = (x_{1}, x_{2}, …, x_{k−1}, x_{k} + ε, x_{k+1}, …, x_{l−1}, x_{l} + ε, x_{l+1}, …, x_{N}) and put A = min(r_{n+1} − x_{k}, x_{l} − s_{m}) and B = max(r_{n} − x_{k}, x_{l} − x_{m+1}). Then there exists some C ∈ ℝ such that

L\overline{S}(x(ε)) = R(\overline{S}) + C · ε

for every ε ∈ [B, A]. Since B < 0, A > 0 and L\overline{S}(x(ε)) ≥ R(\overline{S}) for every ε ∈ ℝ it follows that C = 0. Hence x(ε) ∈ M(\overline{S}) for every ε ∈ [B, A]. In particular we have that x(A) ∈ M(\overline{S}) and thus either (x_{1}, x_{2}, …, x_{k−1}, r_{n+1}, x_{k+1}, …, x_{l−1}, x_{l} − A, x_{l+1}, …, x_{N}) ∈ M(\overline{S}) or (x_{1}, x_{2}, …, x_{k−1}, x_{k} + A, x_{k+1}, …, x_{l−1}, s_{m}, x_{l+1}, …, x_{N}) ∈ M(\overline{S}). The theorem follows by induction. □

Corollary 7.10 Let \overline{S} = (S_{1}, S_{2}, …, S_{N}) be such that ∑_{i=1}^{N} \frac{1}{S_{i}} > 1. Then the set M(\overline{S}) contains a point with rational coordinates.

Remark. In fact, if R(\overline{S}) > 0 then in most cases the set M(\overline{S}) consists of only one point, which according to Corollary 7.10 and Theorem 7.9 has rational coordinates and all coordinates except at most one are best lower approximations of the inverse of the service time of the corresponding server.

By Proposition 7.3, Proposition 7.4 and Corollary 7.10 we have the following theorem.

Theorem 7.11 For every \overline{S} = (S_{1}, S_{2}, …, S_{N}) system with ∑_{i=1}^{N} \frac{1}{S_{i}} > 1 there exists a periodic policy U such that W (U) ≤ R(\overline{S}) + \frac{N}{2} − 1.

Proof. By Corollary 7.10 there exists a point (d_{1}, d_{2}, …, d_{N}) ∈ M(\overline{S}) with d_{i} ∈ ℚ_{≥0} for i = 1, 2, …, N. By Proposition 7.4 there exists a periodic policy U such that for i = 1, 2, …, N the routing sequence u^{i} has density d_{i} for i = 1, 2, …, N and \overline{O}(U) ≤ \frac{N}{2} − 1. Then by Proposition 7.3 we have that

W (U) ≤ L\overline{S}(d_{1}, d_{2}, …, d_{N}) + \overline{O}(U) ≤ R(\overline{S}) + \frac{N}{2} − 1.

□

From the sequel it becomes clear how such a policy U can be obtained. By Proposition 7.2 and Theorem 7.11 we obtain that for N = 2 there exist optimal periodic policies if \frac{1}{S_{1}} + \frac{1}{S_{2}} > 1 (see [7]).

Corollary 7.12 For an \overline{S} = (S_{1}, S_{2}) system with \frac{1}{S_{1}} + \frac{1}{S_{2}} > 1 there exists an optimal periodic policy U with W (U) = R(\overline{S}).

Such an optimal periodic policy can be obtained as follows. Find a rational point (d_{1}, d_{2}) ∈ M(\overline{S}). Let u^{1} be the upper bracket sequence of density d_{1} (or any other regular sequence of zeros and ones of density d_{1}). Then we construct the routing policy U by taking u^{1} and replacing every zero by a two. Since d_{1} is rational we have that u^{1} and thus also U is periodic. Moreover, u^{1} is a regular sequence of density d_{1} and u^{2} is a regular sequence of density 1 − d_{1} = d_{2}, since u^{2} is the complement (every zero is an one and every one is a zero) of u^{1}. Hence \overline{O}(U) = 0 and W (U) = L\overline{S}(d_{1}, d_{2}) = R(\overline{S}).

In general if we have a routing policy U such that u^{i} is a regular sequence of density d_{i} for i = 1, 2, …, N and (d_{1}, d_{2}, …, d_{N}) ∈ M(\overline{S}) then W (U) = L\overline{S}(d_{1}, d_{2}, …, d_{N}) = R(\overline{S}) and it follows that this routing policy U is optimal. However, if N > 2 then generally there does not exist a routing policy U such that u^{i} is a regular sequence of density d_{i} for i = 1, 2, …, N (see [2]). So, in that case it is possible that W (U) > R(\overline{S}) for every policy U.

If ∑_{i=1}^{N} \frac{1}{S_{i}} = 1 then M(\overline{S}) consists of the single point (\frac{1}{S_{1}} , \frac{1}{S_{2}} , …, \frac{1}{S_{N}}), which in general is not a rational point. However, from [16] we have the following result.

Proposition 7.13 For every \overline{S} = (S_{1}, S_{2}, …, S_{N}) system with ∑_{i=1}^{N} \frac{1}{S_{i}} = 1 there exists a policy U such that W (U) ≤ R(\overline{S}) + \frac{N}{2} − 1.

We have the following proposition.

Proposition 7.14 For every \overline{S} = (S_{1}, S_{2}, …, S_{N}) system with ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1 we have that R(\overline{S}) ≤ \frac{1}{2}.

Proof. Let x = (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}). Since ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1 we have that 0 ≤ x_{i} ≤ \frac{1}{S_{i}} for i = 1, 2, …, N. So, by Lemma 5.4 and Theorem 5.5 we have that W_{S_{i}}(x_{i}) ≤ \frac{1}{2} for i = 1, 2, …, N. Hence

R(\overline{S}) = ∑_{i=1}^{N} L_{S_{i}}(x_{i}) = ∑_{i=1}^{N} x_{i} · W_{S_{i}}(x_{i}) ≤ ∑_{i=1}^{N} x_{i} · \frac{1}{2} = \frac{1}{2}.

□

By Theorem 7.11, Proposition 7.13 and Proposition 7.14 we have the following theorem.

Theorem 7.15 For every \overline{S} = (S_{1}, S_{2}, …, S_{N}) system with ∑_{i=1}^{N} \frac{1}{S_{i}} ≥ 1 there exists a policy U such that W (U) ≤ \frac{N−1}{2}. Moreover, if ∑_{i=1}^{N} \frac{1}{S_{i}} > 1 then there exists a periodic policy U such that W (U) ≤ \frac{N−1}{2}.

7.2 Algorithms for determining a minimal point

In this subsection we give an algorithm for determining for a given \overline{S} = (S_{1}, S_{2}, …, S_{N}) system with ∑_{i=1}^{N} \frac{1}{S_{i}} > 1 a rational point (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) (recall that in most cases the set M(\overline{S}) consists of only one point and then this rational point is obviously unique) and the corresponding value of R(\overline{S}).

Put

F (\overline{S}) := \{(x_{1}, x_{2}, …, x_{N}) ∈ H^{N} : L\overline{S}(x_{1}, x_{2}, …, x_{N}) < ∞.\}

Then M(\overline{S}) ⊆ F (\overline{S}). Suppose that x = (x_{1}, x_{2}, …, x_{N}) ∈ F (\overline{S}) \ M(\overline{S}). Then according to the characterization of M(\overline{S}) given by Theorem 7.7 we have that there exist i, j ∈ \{1, 2, …, N\}, i ≠ j such that l_{S_{i}}(x_{i}) > r_{S_{j}}(x_{j}) and r_{S_{j}}(x_{j}) < ∞. Hence there exists some ε > 0 such that L\overline{S}(x_{1}, x_{2}, …, x_{i} − ε, …, x_{j} + ε, …, x_{N}) < L\overline{S}(x_{1}, x_{2}, …, x_{N}) < ∞. So, if we have a point x = (x_{1}, x_{2}, …, x_{N}) ∈ H^{N} and we have for all i, j ∈ \{1, 2, …, N\} with i ≠ j that L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) ≥ L\overline{S}(x_{1}, x_{2}, …, x_{N}), where h is a small positive number, then the (Euclidean) distance between x = (x_{1}, x_{2}, …, x_{N}) and the set M(\overline{S}) is small, since this distance is of order h. For a given \overline{S} = (S_{1}, S_{2}, …, S_{N}) system with ∑_{i=1}^{N} \frac{1}{S_{i}} > 1 we can use this property to obtain a point (arbitrarily) close to the set M(\overline{S}). We now give the main steps of the algorithm for obtaining this point. Later we give more details on the implementation of every step.

Sketch of Algorithm.

step 1. Pick an initial point x := (x_{1}, x_{2}, …, x_{N}) ∈ F (\overline{S}) and choose an appropriate initial step size h > 0 and an ” acceptable error ” ε > 0.

step 2. Find i, j ∈ \{1, 2, …, N\} with i ≠ j such that L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) < L\overline{S}(x_{1}, x_{2}, …, x_{N}) or determine that there do not exist such i, j. In the former case go to step 3, in the latter case go to step 4.

step 3. Put x := x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) and return to step 2.

step 4. Reduce the value of the step size h by a reasonable amount (for example h := \frac{h}{2}) and determine whether the new value of h is smaller then ε or not. In the former case go to step 5, in the latter case return to step 2.

step 5. The algorithm terminates by giving as output the point x.

We will show that the point x obtained in this way can be used to obtain a rational point x′ ∈ M(\overline{S}) if the distance between the point x and the set M(\overline{S}) is small enough. We first give some more details on

our implementation of several steps of the algorithm above. In step 1 we suggest to put x_{i} = \frac{\frac{1}{S_{i}}}{∑{N \atop j=1} \frac{1}{S_{j}}}

for i = 1, 2, …, N. It is easily seen that then x ∈ F (\overline{S}). Then for the initial step size h we choose

h = 2^{−(k+1)}, where k = ⌈\frac{log(max_{i=1,2...N} ( \frac{1}{S_{i}} −x_{i}))}{log( \frac{1}{2} )}⌉. We suggest putting ε := \frac{h}{100}, since then the distance

between the obtained point x and the set M(\overline{S}) will usually be small enough to obtain a rational point in M(\overline{S}). However, if it turns out that this distance is not small enough to find the rational point then a smaller value for ϵ should be chosen, while in many other cases it is possible to use a greater value for ϵ. For step 2 the most obvious way to find such i, j is just systematically checking for i = 1, 2, …, N, j = 1, 2, …, N , i ≠ j whether L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) < L\overline{S}(x_{1}, x_{2}, …, x_{N}) until you find such i, j or you have tried all pairs i, j with i ≠ j and none suffices. In this way the value of L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) has to be computed O(N^{2}) times. In practice this is fast enough, since N is usually a rather small number and L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) can be computed quickly by the algorithm described in the previous section. However, it is not really necessary to check all pairs i, j since for example you could decide to go to step 4 and decrease the step size if you have determined that with high probability there do not exist such i, j. Moreover, some time can be gained if the pairs i, j are checked in a smart order. Therefore, we suggest a slightly more sophisticated method for implementing step 2 of the algorithm in case that N is not a small number. Start with computing the left derivatives l_{S_{i}}(x_{i}) and the right derivatives r_{S_{i}}(x_{i}) for i = 1, 2, …, N. Then calculate the difference l_{S_{i}}(x_{i}) − r_{S_{j}}(x_{j}) for all the pairs i, j ∈ {1, 2, …, N} with i ≠ j. Check whether L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) < L\overline{S}(x_{1}, x_{2}, …, x_{N}) for the pairs i, j ∈ {1, 2, …, N} for which l_{S_{i}}(x_{i}) − r_{S_{j}}(x_{j}) > 0 and run through these pairs in order of decreasing value of l_{S_{i}}(x_{i}) − r_{S_{j}}(x_{j}). In the computation of L\overline{S}(x_{1}, x_{2}, …, x_{i} − h, …, x_{j} + h, …, x_{N}) the (intermediate) results for computing the left and right derivatives l_{S_{i}}(x_{i}) and r_{S_{i}}(x_{i}) should be used to increase the efficiency of this method. In step 4 we suggest to reduce the step size by a factor 2.

We illustrate the algorithm to obtain a point x close to the set M(\overline{S}) in the following example.

Example. Let N = 3 and \overline{S} = (\frac{93}{57}, \frac{106}{39}, \frac{183}{20}). Putting x_{i} = \frac{\frac{1}{S_{i}}}{∑{N \atop j=1} \frac{1}{S_{j}}} for i = 1, 2, 3 we obtain the

initial point x = (\frac{368562}{655529}, \frac{221247}{655529}, \frac{65270}{655529}) = (0.562236, 0.337509, 0.100255) ∈ F (\overline{S}) (rounded to 6 decimals) and corresponding value L(x_{1}, x_{2}, x_{3}) = 0.128134. The initial step size h := 2^{−6} = 0.015625 and the error ε is chosen to be \frac{h}{100} = \frac{1}{6400} = 0.00015625. For this step size h we do not find a pair i, j with i ≠ j that suffices. So, h := 2^{−7} and we find that i = 2, j = 1 suffices. Then x_{1} := x_{1} + h = 0.570048, x_{2} := x_{2} − h = 0.329697, and we obtain the new point (x_{1}, x_{2}, x_{3}) = (0.570048, 0.329697, 0.100255) ∈ F (\overline{S}) and corresponding value L(x_{1}, x_{2}, x_{3}) = 0.125732. We do not find a new pair i, j which suffices and thus h := 2^{−8}. Next we find that i = 1, j = 2 suffices and we obtain the new point (x_{1}, x_{2}, x_{3}) = (0.566142, 0.333603, 0.100255) ∈ F (\overline{S}) and corresponding value L(x_{1}, x_{2}, x_{3}) = 0.119799. Continuing the procedure in this way we obtain consecutively (x_{1}, x_{2}, x_{3}) := (0.562236, 0.333603, 0.104161), L(x_{1}, x_{2}, x_{3}) = 0.118669, h := 2^{−9}, h := 2^{−10}, (x_{1}, x_{2}, x_{3}) := (0.561259, 0.333603, 0.105138), L(x_{1}, x_{2}, x_{3}) = 0.118386, h := 2^{−11}, (x_{1}, x_{2}, x_{3}) := (0.561748, 0.3331155, 0.105138), L(x_{1}, x_{2}, x_{3}) = 0.118202, h := 2^{−12}, (x_{1}, x_{2}, x_{3}) := (0.561504, 0.333359, 0.103138), L(x_{1}, x_{2}, x_{3}) = 0.117865, h := 2^{−13}. Since the new step size h := 2^{−13} is smaller than the chosen error ε = \frac{1}{6400}, the algorithm stops. The distance between the last obtained point x = (x_{1}, x_{2}, x_{3}) = (0.561504, 0.333359, 0.103138) ∈ F (\overline{S}) and the set M(\overline{S}) is of order ε and thus L(x_{1}, x_{2}, x_{3}) = 0.117865 is an approximation of R(\overline{S}), the lower bound for the average waiting time in the \overline{S} system.

So, as illustrated above we have an algorithm to obtain a point (arbitrarily) close to the set M(\overline{S}) and thus an approximation of R(\overline{S}). We now discuss a method to obtain a rational point in the set M(\overline{S}) from this and if we have found this rational point then we can calculate the exact value of R(\overline{S}) by the algorithm of the previous section.

Recall that by Theorem 7.9 there exists a point (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) and some j ∈ \{1, 2, …, N\} such that x_{i} is 0 or a best lower approximation of \frac{1}{S_{i}} for every i ≠ j. Hence x_{i} is a rational number of relatively low denominator for every i ≠ j and x_{j} = 1 − ∑_{i≠j} x_{i} is also a rational number. Let (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}) be a point close to the set M(\overline{S}) obtained by the algorithm demonstrated above and let x_{1}^{i}, x_{2}^{i}, … be the convergents of x_{i}^{∗}. Then for every i ≠ j it is very likely that x_{i} = x_{k_{i}}^{i}, where k_{i} is a relatively small positive integer since the denominator of x_{i} is relatively small. Let ε be the error used in the algorithm to determine (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}). Then for every i ∈ {1, 2, …, N} we use the continued fraction algorithm to determine the convergents x_{1}^{i}, x_{2}^{i}, … of x_{i}^{∗} until we have that | x_{k_{i}}^{i} − x_{i}^{∗} |< ε for some k_{i} ∈ ℕ. We put y_{i} := x_{k_{i}}^{i} for i = 1, 2, …, N. Then y_{i} is a rational number for i = 1, 2, …, N. Let y_{j} be the one with the greatest denominator among them. Put y_{j} = 1 − ∑_{i≠j} y_{i}. Then ∑_{i=1}^{N} y_{i} = 1 and if ε was chosen small enough then (y_{1}, y_{2}, …, y_{N}) is likely to be a rational point in the set M(\overline{S}). In fact, if the set M(\overline{S}) consists of the single point (x_{1}, x_{2}, …, x_{N}) as is usually the case, then we should have that y_{i} = x_{i} for i = 1, 2, …, N. In that case we have for every i ≠ j that y_{i} is either 0 or a best lower approximation of \frac{1}{S_{i}}. In general we can verify whether the obtained rational point (y_{1}, y_{2}, …, y_{N}) is an element of M(\overline{S}) or not by the condition of Proposition 7.7. If (y_{1}, y_{2}, …, y_{N}) ∈ M(\overline{S}) then the exact value of R(\overline{S}) can be calculated by R(\overline{S}) = L(y_{1}, y_{2}, …, y_{N}). If it turns out that (y_{1}, y_{2}, …, y_{N}) ∉ M(\overline{S}) then the algorithm could be modified. First of all it is possible to choose a smaller value for the error ε and try again.

It is also possible to exhaustively search for a rational point (x_{1}, x_{2}, …, x_{N}) ∈ M(\overline{S}) for which x_{i} is either 0 or a best lower approximation of \frac{1}{S_{i}} for every i ≠ j by using the enumerations (see (18),(19) and (20)) of the best lower approximations of \frac{1}{S_{i}} for i = 1, 2, …, N. For N = 2 this enumeration of possible values for the x_{i} and the fact that the function L(x_{1}, x_{2}) is convex in x_{1} and x_{2} is used in [7] to find a rational point in M(\overline{S}). However, for larger values of N this is more complicated and takes much more time. On the other hand, if you first apply the above algorithm to obtain a point (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}) close to the set M(\overline{S}) then you approximately know where you should start the search. This should reduce the time it takes to find the rational point by an exhaustive search.

We illustrate the algorithm to find a rational point (y_{1}, y_{2}, …, y_{N}) ∈ M(\overline{S}) from a point (x_{1}^{∗}, x_{2}^{∗}, …, x_{N}^{∗}) close to the set M(\overline{S}) by applying the continued fraction algorithm.

Example. We continue the previous example in which we obtained the point (x_{1}^{∗}, x_{2}^{∗}, x_{3}^{∗}) = (0.561504, 0.333359, 0.103138) for the \overline{S} = (\frac{93}{57}, \frac{106}{39}, \frac{183}{20}) system by taking ε = \frac{1}{6400}. We apply the continued fraction algorithm to x_{1}^{∗} = 0.561504 (rounded to 6 decimals) and we find that x_{1}^{∗} = [0, 1, 1, 3, 1, 1, 3, …] with convergents \frac{0}{1}, \frac{1}{1}, \frac{1}{2}, \frac{4}{7}, \frac{5}{9}, \frac{9}{16}, \frac{32}{57}, . . .. Since for the 6-th convergent \frac{32}{57} we have that | \frac{32}{57} − x_{1}^{∗} |< ε we stop the continued fraction expansion of x_{1}^{∗} and put y_{1} = \frac{32}{57}. Similarly, we obtain y_{2} = \frac{1}{3} and y_{3} = \frac{2}{19}. According to the algorithm we should put y_{1} := 1 − y_{2} − y_{3}, but the value of y_{1} does not change by this, since we already have y_{1} + y_{2} + y_{3} = 1. So, we have obtained the rational point (y_{1}, y_{2}, y_{3}) = (\frac{32}{57}, \frac{1}{3}, \frac{2}{19}) and next we verify that (y_{1}, y_{2}, y_{3}) ∈ M(\overline{S}) by the conditon of Proposition 7.7. So, we calculate the left derivatives l_{S_{i}}(y_{i}) and the right derivatives r_{S_{i}}(y_{i}) for i = 1, 2, 3. We obtain l_{S_{1}}(y_{1}) = \frac{34}{19}, l_{S_{2}}(y_{2}) = 0, l_{S_{3}}(y_{3}) = \frac{3}{2}, r_{S_{1}}(y_{1}) = \frac{34}{19}, r_{S_{2}}(y_{2}) = \frac{51}{13} and r_{S_{3}}(y_{3}) = \frac{87}{20}. Since l_{S_{i}}(y_{i}) ≤ r_{S_{j}}(x_{j}) for every i ≠ j we have indeed that (y_{1}, y_{2}, y_{3}) ∈ M(\overline{S}). Moreover, y_{2} and y_{3} are best lower approximations of \frac{1}{S_{2}} and \frac{1}{S_{3}} respectively, as expected. This follows directly from the fact that l_{S_{2}}(y_{2}) < r_{S_{2}}(y_{2}) and l_{S_{3}}(x_{3}) < r_{S_{3}}(x_{3}). We have R(\overline{S}) = L(y_{1}, y_{2}, y_{3}) = \frac{2551}{21660}. So, for the \overline{S} = (\frac{93}{57}, \frac{106}{39}, \frac{183}{20}) system we have that W (U) ≥ \frac{2551}{21660} for every routing policy U. Moreover, it follows from Proposition 7.4 and Theorem 7.11 that it is easy to obtain (by constructing a billiard sequence) a periodic policy U′ with densities (d_{1}, d_{2}, d_{3}) = (y_{1}, y_{2}, y_{3}) = (\frac{32}{57}, \frac{1}{3}, \frac{2}{19}) (and thus a period of 57) for which W (U′) ≤ R(\overline{S}) + \frac{N}{2} − 1 = \frac{13381}{21660}.

8 Appendix: An extension of Little’s Law for routing policies

Stidham proved in [24] the Little relation under the assumption that W, the limiting average of the waiting times, and L, the limiting average of the number of customers, do exist. In our optimal routing problem we do not want to restrict the set of policies to those for which these limits exist. Even if the limiting density does exist then the limiting averages L and W may fail to exist (see Example 8.3). Here we show that Little’s relation can be replaced with the inequalities of Theorem 8.2 if L and W are defined in terms of limsups as in section 3.

The results in this appendix are valid for any input-output queueing system and thus we have a more general setting than before. However, we recall that the objective is to show the validity of (3), (4) and(6) for the particular deterministic queueing system considered in this paper. For convenience we use notation similar to that used in the paper.

We suppose that customers arrive at (or are admitted by some routing policy to) the queueing system at moments t_{n} ∈ ℝ, n = 1, 2 … where 0 ≤ t_{1} ≤ t_{2} ≤ . . .. Let W_{n} be the waiting time in the system of the n -th arriving customer and let B(t) be the number of customers waiting in the system at time t. Then we define L := lim sup_{T →∞} \frac{1}{T} ·∫_{t=0}^{T} B(t)d(t) as the time average number of customers in the system and W := lim sup_{n→∞} \frac{1}{T} · ∑_{n=1}^{T} W_{n} as the average waiting time of the arriving customers. Moreover, we put A(t) :=| n ∈ ℕ : t_{n} ≤ t |, the number of arrivals before time t and D(t) :=| n ∈ N : t_{n} + W_{n} ≤ t |, the number of departures before time t. From the definition it is clear that

A(t) = B(t) + D(t) for every t ∈ ℤ_{≥0}.

We put \overline{λ} := lim sup_{t→∞} \frac{A(t)}{t} as the upper arrival rate and \underline{λ} := lim inf_{t→∞} \frac{A(t)}{t} as the lower arrival rate. We assume that \overline{λ} < ∞. If \underline{λ} = \overline{λ} then λ := lim_{t→∞} \frac{A(t)}{t} is the arrival rate.

Lemma 8.1 If W < ∞ then

lim inf_{t→∞} \frac{D(t)}{t} = lim inf_{t→∞} \frac{A(t)}{t} and lim sup_{t→∞} \frac{D(t)}{t} = lim sup_{t→∞} \frac{A(t)}{t}. (25)

Moreover,

lim sup_{t→∞} \frac{1}{A(t)} ∑_{n=1}^{A(t)} W_{n} = lim sup_{t→∞} \frac{1}{A(t)} ∑_{n:t_{n}+W_{n}≤t} W_{n}. (26)

Proof. Since W < ∞ we have lim_{n→∞} \frac{W_{n}}{n} = 0. Thus lim_{n→∞} \frac{W_{n}}{t_{n}} = 0, since \overline{λ} < ∞. Hence, for every ε > 0 there exists an n_{0} ∈ ℕ such that W_{n} < t_{n}ε for every n > n_{0}. Let t_{0} ∈ R_{≥0} be chosen so large that A(t_{0}) > n_{0}. Then

A(t_{0}) ≥ D(t_{0}) =| n : t_{n} + W_{n} ≤ t_{0} | ≥| n ≤ n_{0} : t_{n} + W_{n} ≤ t_{0} | + | n > n_{0} : t_{n}(1 + ε) ≤ t_{0} |=

| n ≤ n_{0} : t_{n} + W_{n} ≤ t_{0} | − | n ≤ n_{0} : t_{n} · (1 + ε) ≤ t_{0} | + | n : t_{n} ≤ t_{0}/(1 + ε) | . (27)

Dividing (27) by t_{0} and taking liminfs for t_{0} → ∞ we obtain

lim inf_{t_{0}→∞} \frac{A(t_{0})}{t_{0}} ≥ lim inf_{t_{0}→∞} \frac{D(t_{0})}{t_{0}} ≥ lim inf_{t_{0}→∞} \frac{A(t_{0})/(1 + ε)}{t_{0}}.

Since ε was arbitrary, it follows that lim inf_{t→∞} \frac{D(t)}{t} = lim inf_{t→∞} \frac{A(t)}{t}. Analogously it follows that lim sup_{t→∞} \frac{D(t)}{t} = lim sup_{t→∞} \frac{A(t)}{t}. Moreover, since A(t) → ∞ as t → ∞ it also follows from (27) that

lim sup_{t→∞} \frac{1}{A(t)} ∑_{n=1}^{A(t)} W_{n} ≥ lim sup_{t→∞} \frac{1}{A(t)} ∑_{n:t_{n}+W_{n}≤t} W_{n} ≥ \frac{1}{1 + ε} lim sup_{t→∞} \frac{1}{A(t)} ∑_{n=1}^{A(t)} W_{n}.

This implies (26) since ϵ was arbitrary. □

Remark. The proof of this lemma is similar to the proof of Little’s Law by Stidham in [24]. The main difference is that the existence of certain limits is not assumed, but that instead of that liminfs and limsups are used.

By Lemma 8.1 we can prove that the following extension of Little’s Law holds.

Theorem 8.2 Suppose that W < ∞ for some input-output queueing system as described above. Then, for the upper arrival rate \overline{λ} we have that

L ≤ \overline{λ} · W. (28)

Moreover, for the lower arrival rate \underline{λ} we have that

L ≥ \underline{λ} · W (29)

and if the arrival rate λ exists then

L = λ · W (30)

Proof. Using a standard argument in the derivation of Little’s Law, more precisely by considering the total number of waiting time units up to time t (see [22] page 102 or [24]), we find the inequalities

∑_{n∈ℕ:t_{n}+W_{n}≤t}W_{n} ≤ ∫_{s=0}^{t} B(s)ds ≤ ∑_{n=1}^{A(t)} W_{n}. (31)

By the second inequality we have

\overline{λ} · W = lim sup_{t→∞} \frac{A(t)}{t} · lim sup_{n→∞} \frac{1}{n} ∑_{k=1}^{n} W_{k} = lim sup_{t→∞} \frac{A(t)}{t} · lim sup_{t→∞} \frac{1}{A(t)} ∑_{k=1}^{A(t)} W_{k} ≥

lim sup_{t→∞} \frac{1}{t} ∑_{k=1}^{A(t)} W_{k} ≥ lim sup_{t→∞} \frac{1}{t} ∫_{s=0}^{t} B(s)ds = L.

Similarly, (26) and the first inequality imply

\underline{λ} · W = lim inf_{t→∞} \frac{A(t)}{t} · lim sup_{n→∞} \frac{1}{n} ∑_{k=1}^{n} W_{k} = lim inf_{t→∞} \frac{A(t)}{t} · lim sup_{t→∞} \frac{1}{A(t)} ∑_{k=1}^{A(t)} W_{k} =

lim inf_{t→∞} \frac{A(t)}{t} · lim sup_{t→∞} \frac{1}{A(t)} ∑_{n:t_{n}+W_{n}≤t} W_{n} ≤ lim sup_{t→∞} \frac{1}{t} ∑_{n:t_{n}+W_{n}≤t} W_{n} ≤ lim sup_{t→∞} \frac{1}{t} ∫_{s=0}^{t} B(s)ds = L.

By combining the first and second assertion we have L = λ · W if λ exists. □

We now apply Theorem 8.2 for routing to a deterministic queueing system as described in section 3. If we consider the (S_{1}, S_{2}, …, S_{N}) system in total, then λ, is equal to 1 and independent of the routing policy U. Hence (4) follows immediately from (30). Moreover, if we consider a single queue i of the system then the arrival rate λ is equal to the density d_{i} (if this exists) of the routing sequence u^{i} corresponding to this queue. Thus (30) also implies (6).

In section 3 we defined the average waiting time W and the average buffer content L by limsups instead of limits. The following example shows that this is necessary, since in general the limits do not exist (even if you assume that the routing sequence has a density and thus the arrival rate exists).

Example 8.3 Consider a single deterministic queue and assume that the density d of the routing sequence exists and is rational, d = \frac{p}{q} with gcd(p, q) = 1 say. Suppose that the service time S is such that

\frac{1}{⌈S⌉} < d < \frac{1}{S} .

Let w be the upperbracket sequence with period word ω = (ω_{1}, …, ω_{q}) and with average workload L(d). We construct a policy u = (u_{1}, u_{2}, …) which consists of blocks of type ω^{k} alternated with blocks of type ϖ^{l} where ϖ = (ϖ_{1}, …, ϖ_{q}), with ϖ_{k} = 1(1 ≤ k ≤ p) and ϖ_{k} = 0(p + 1 ≤ k ≤ q).

Choose (p, q) and S such that

L(ϖ^{∞}) > L(d).

Choose a sequence {ε_{k} > 0}_{k=1}^{∞} with lim_{k→∞} ε_{k} = 0 and define inductively unbounded sequences t_{k}, t′_{k}. Let t_{k} = t′_{k−1} + m_{k}q and define on the interval t_{k} < t < t′_{k} the u_{t} as ω^{m_{k}}. Take m_{k} sufficiently large such that

|\frac{1}{t_{k}} ∫_{s=0}^{t_{k}} B(s)ds − L(d)| < ε_{k}.

Let t′_{k} = t_{k} + n_{k}q and define on the interval t_{k} < t < t′_{k} the u_{t} as ϖ^{n_{k}} and take n_{k} sufficiently large such that

|\frac{1}{t′_{k}} ∫_{s=0}^{t′_{k}} B(s)ds − L(ϖ^{∞})| < ε_{k}.

Then, since the fraction of ones in each ω and ϖ is equal to d, we have

lim_{t→∞} \frac{κ_{u}(t)}{t} = d.

Moreover, lim inf_{t→∞} \frac{1}{t} ∫_{s=0}^{t} B(s)ds = L(d) < L(ϖ^{∞}) = lim sup_{t→∞} \frac{1}{t} ∫_{s=0}^{t} B(s)ds.

The conclusion is that the existence of the limiting density does not imply the existence of the limiting average waiting time nor the existence of the limiting average buffer content.

References

[1] Altman, E., B. Gaujal, A. Hordijk. 2000. Admission control in stochastic event graphs. IEEE Trans. Automat. Control 45 854–867.

[2] Altman, E., B. Gaujal, A. Hordijk. 2000. Balanced sequences and optimal routing. J. Assoc. Comput. Mach. 47 752–775.

[3] Altman, E., B. Gaujal, A. Hordijk. 2000. Multimodularity, convexity and optimization properties. Math. Oper. Res. 25 324–347.

[4] Arian, Y., Y. Levy. 1992. Algorithms for generalized round Robin routing. Oper. Res. Lett. 12 313–319.

[5] Baccelli, F., P. Brémaud. 1994. Elements of queueing theory. Springer-Verlag.

[6] Combé, M.B., O.J. Boxma. 1994. Optimization of static traffic allocation policies. Theoretical Computer Science 125 17–43.

[7] Gaujal, B., E. Hyon. 2000. Optimal routing policy in two deterministic queues. Technical Report INRIA RR-3997. To appear in Calculateurs Parallèles.

[8] Hajek, B. 1985. Extremal splittings of point processes. Math. Oper. Res. 10 543–556.

[9] Hardy, G.H., E.M. Wright. 1960. An introduction to the theory of numbers. Fourth edition, Oxford.

[10] Heinis, A. 2001. Arithmetics and combinatorics of words of low complexity. Ph.D.-thesis, Leiden University.

[11] Hordijk, A., G. Koole. 1992. On the assignment of customers to parallel queues. Prob. Engin. Inform. Sci. 6 495–511.

[12] Hordijk, A., D.A. van der Laan. 2000. Periodic routing to parallel queues with bounds on the average waiting time. Report MI no. 2000-44, Leiden University. Available on www.math.leidenuniv.nl/reports/2000-44.shtml.

[13] Hordijk, A., D.A. van der Laan. 2001. Bounds for deterministic periodic routing sequences. Integer programming and combinatorial optimization. K. Aardal, B. Gerards, ed., Proceedings of the 8th international IPCO conference, Springer, 236–250.

[14] Hordijk, A., D.A. van der Laan. 2002. Note on the convexity of the stationary waiting time as function of the density. Leiden University. Submitted to Probab. Engrg. Inform. Sci.

[15] Koole, G., P. Sparaggis, D. Towsley. 1999. Minimizing response times and queue lengths in systems of parallel queues. J. Appl. Probab. 36), 1185–1193.

[16] van der Laan, D. A. 2000. Routing jobs to servers with deterministic service times. Report MI no. 2000-20, Leiden University. Submitted to Math. Oper. Res. Available on www.math.leidenuniv.nl/reports/2000-20.shtml.

[17] Liu, Z., R. Righter. 1998. Optimal load balancing on distributed homogeneous unreliable processors. Oper. Res. 46 563–573.

[18] Lothaire, M. 2002. Algebraic Combinatorics on Words. Cambridge University Press, Cambridge.

[19] Moran, P.A.P. 1968. An Introduction to Probability Theory. Claridon Press Oxford.

[20] Morse, M., G.A. Hedlund. 1940. Symbolic dynamics II. Amer. J. Math. 60 1–42.

[21] Perron, O. 1954. Die Lehre von den Kettenbrüchen. Third edition, Stuttgart.

[22] Ross, S.M. 1970. Applied Probability Models with Optimization Applications. Holden-Day, San Francisco.

[23] Shirakawa, H., M. Mori, M. Kijima. 1989. Evaluation of Regular Splitting Queues. Comm. Statist. Stochastic Models 5 219–234.

[24] Stidham, S., Jr. 1974. A last word on L = λW. Oper. Res. 22 417–421.

[25] Tijdeman, R. 2000. Fraenkel’s conjecture for six sequences. Discrete Math. 222 223–234.