Routing jobs to servers with deterministic service times

by D.A van der Laan

July 5, 2000

Abstract

In this paper we consider the problem of routing deterministic arriving jobs to parallel servers with deterministic (distinct) service times, where we assume that the arrival rate of the jobs is equal to the total service capacity of the servers. Our goal is to find routing policies that minimize the long-run average waiting time of the arriving jobs. We give lower and upper bounds for the minimal long-run average waiting time and we present results on the structure of optimal policies. We derive mathematical programming problems which can be solved to obtain optimal routing policies and for a single queue we have results on routing according to a regular sequence to that queue. Finally we discuss several algorithms to obtain good deterministic routing policies.

Keywords : parallel deterministic servers, deterministic routing policies, regular sequences.

1 Introduction

We consider a queueing system with n ≥ 2 parallel servers each having its own queue. Arriving jobs have to be routed to one of the servers at the moment of arrival. We assume that the arrival of jobs is deterministic with a constant rate. We also assume that the serving times are deterministic, but typically the servers have different rates. We may think of a computer system with several processors which has to perform the incoming jobs. Our goal is to minimize the long-run average waiting time. Similar queueing systems with parallel heterogeneous servers have been considered in literature, but in general Poisson arrivals are assumed and the serving times are exponentially distributed or general. Further in such stochastic models a distinction is made between dynamic and static routing policies. In the dynamic case the policy may depend on time dependent information, for example the number of jobs or the remaining workload in each queue. In the static case the policy should only depend on the base characteristics of the system, such as the arrival rate and service time distributions. However, it is clear that for our deterministic model there is no distinction between dynamic and static policies. The stochastic model that is closest to ours is the static case with allocation according to a fixed (periodic) pattern. This is also called semi-dynamic deterministic routing. Some papers dealing with such models are [5], [20], [6] and [9]. In these papers several algorithms and heuristics are given to obtain reasonable good policies for the models considered.

For this kind of models the optimization procedure actually consist of two steps:

1. Approximate for i = 1, 2, …, n the fraction p_{i}^{∗} of jobs that should be routed to server i in the optimal pattern by fractions p_{i} such that ∑_{i=1}^{n} p_{i} = 1.

2. Construct an allocation pattern with the fractions p_{i}.

Usually most of the attention goes to step 1. In our model we concentrate entirely on step 2 where we assume that the arrival rate is equal to the combined service rate of the n servers, in other words, that the traffic intensity ρ satisfies ρ = 1. For a stochastic model the system overflows if ρ = 1 and waiting times will tend to ∞. However in the deterministic model the system can just be stabilized. The fact that the fractions p_{i} are fixed also implies that with minimizing the long-run average waiting time we also minimize the long-run average sojourn time (which is waiting time plus service time). We think that an optimal allocation pattern for given fractions in our model will at least in the heavy traffic region perform very well for more general service time distributions and arrival processes too.

Consider the following ” most regular ” zero-one valued splitting sequence of asymptotic mean p :

{b_{k}^{p}(ϕ)}_{k=1}^{∞} = ⌊(k + 1)p + ϕ⌋ − ⌊kp + ϕ⌋.  (1)

In (1) ϕ ∈ ℝ is an arbitrary phase. Such a sequence is called a regular, Beatty, Sturmian, or bracket sequence with density p. Such sequences are studied in several areas of mathematics and for more about this sequence see [12], [13], [2], [17], [18], [19], [10] and [11]. Remark that the sequence is periodic if p ∈ ℚ. For a single server let {b_{k}}_{k=1}^{∞} be a zero-one splitting sequence, where the k-th arriving job is routed to the server if and only if b_{k} = 1. In [8] it is shown that if a fraction p of jobs has to be routed to a single exponential server, then the long-run average queue size is minimized, if sequence (1) is used. So according to Little’s theorem the long-run average waiting time of jobs which are routed to that server is minimized by sequence (1). Hajek proved this for an exponential server, but it holds much more generally (see [1] and [3]) and we will see that it also holds in our model. The optimality of the regular sequence for a single queue can be used to prove that a static routing policy is optimal if the corresponding splitting sequences for every single server i are regular sequences with given (optimized) density p_{i} for i = 1, 2, …, n. This is done in [2] and [3] for several models. The integer sequence corresponding to such an optimal policy is called an exactly covering sequence or balanced sequence. However, if n > 2 then in general an exactly covering sequence does not exist for given densities p_{i}. Only for n = 2 there exists a balanced sequence for every pair of fractions (p, 1 − p), because the complement of a regular sequence with density p is a regular sequence with density 1 − p. In [2], [18], [19] and [10] it is studied which densities are ” balanceable ” if n > 2. So the optimal routing policy in our model is in fact known if n = 2. In other cases the policy will be such that the corresponding splitting sequences are simultaneously as regular as possible in some sense.

Our paper is organised as follows. In section 2 we describe the queueing model and some notation is introduced. In section 3 we deduce a fundamental relation between the long-run average waiting time and the total unused work capacity of the system. In section 4 we will find a mathematical programming problem (MPP) which can be used to minimize the long-run average waiting time and we deduce an upper bound for the minimal long-run average waiting time. In section 5 we find some results on the structure of optimal policies. Further we show that the upper bound for the minimal long-run average waiting time is best possible if the fractions p_{i} are linearly independent over ℤ. In section 6 we consider the case that all the fractions p_{i} are rational. We show that in that case we can restrict to proportional periodic policies to find an optimal routing policy and that an optimal periodic policy can be found by solving some linear programming (LP) problem with zero-one variables, which is an integer linear programming problem (ILP). We obtain a lower bound for the minimal long-run average waiting time by solving the LP-relaxation of this ILP. Further we give an upper bound for this case which is a fraction better than the earlier found general upper bound. In section 7 we show that the lower bound on the minimal long-run average waiting time that we obtained in section 6 is attained if the policy is such that for every single queue the corresponding splitting sequence is a regular sequence with appropriate density. Thus the lower bound can be attained if the given fractions are balanceable. Further we deduce an explicit formula for the long-run average waiting time of customers routed to some server i if the corresponding splitting sequence is regular. Finally in section 8 we consider some algorithms to obtain good policies.

2 The queueing model

We consider the following queueing system. Arriving jobs have to be routed at the moment of arrival to one of n ≥ 2 parallel servers, each having its own queue. We assume that the arrival of jobs is deterministic with a constant rate. Starting at time t = 0 one job arrives every time unit. We also assume that the serving times of the n parallel servers are deterministic and that they have a total working capacity of 1. So,

a_{1} + a_{2} + ⋯ + a_{n} = 1,  (2)

where a_{i}^{−1} is the service time per job of server i. Moreover without loss of generality we assume that a_{1} ≥ a_{2} ≥ ⋯ ≥ a_{n} and we denote the system by (a_{1}, a_{2}, …, a_{n}). If policy ψ is applied then for t ∈ ℕ we define W_{t} = W_{t}(ψ) as the waiting time of the t-th arriving job, that is the time between arrival and begin of the serving process of the t-th arriving job. We define the long-run average waiting time if policy ψ is applied as

W = W (ψ) = W (a_{1}, a_{2}, …, a_{n}, ψ) = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=1}^{τ} W_{t}.

Further if policy ψ is applied then for t ∈ ℕ we define V_{t} = V_{t}(ψ) as the sojourn time of the t-th arriving job, that is the time between arrival and end of the serving process of the t-th arriving job. We define the long-run average sojourn time if policy ψ is applied as

V = V (ψ) = V (a_{1}, a_{2}, …, a_{n}, ψ) = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=1}^{τ} V_{t}.

Our goal is to find routing policies which minimize the long-run average waiting time W. Such a policy also minimizes the long-run average sojourn time V. We introduce some more notation. Define for all s ∈ ℤ_{≥0} the variables

u_{i}^{s} = the total amount of time units that server i has not

been used between t = 0 and t = s.

v_{i}^{s} = the total amount of time units from t = s that

server i needs to finish jobs that have been routed to server i before time t = s.

k_{s} = k_{s}(ψ) is the server to which the job arriving at time t = s is routed

if policy ψ is applied.

We have the following lemma.

Lemma 2.1 If policy ψ is applied we have

W = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}(ψ)}^{t}  (3)

and

V = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1}(v_{k_{t}(ψ)}^{t} + a_{k_{t}(ψ)}^{−1}).  (4)

Proof. Note for t ∈ ℕ that W_{t}, V_{t} are resp. the waiting and sojourn time of the job arriving at moment t − 1. Hence W_{t} = v_{k_{t−1}(ψ)}^{t−1} and V_{t} = W_{t} + a_{k_{t−1}(ψ)}^{−1}. Thus

W = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=1}^{τ} W_{t} = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=1}^{τ} v_{k_{t−1}(ψ)}^{t−1} = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}(ψ)}^{t}

and

V = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=1}^{τ} V_{t} = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=1}^{τ}(v_{k_{t−1}(ψ)}^{t−1} + a_{k_{t−1}(ψ)}^{−1}) =

lim sup_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1}(v_{k_{t}(ψ)}^{t} + a_{k_{t}(ψ)}^{−1}).

□

Further we define

W̃ = W̃(a_{1}, a_{2}, ⋯, a_{n}) = inf_{ψ} W (ψ)

as the minimal long-run average waiting time for the the given service rates and

Ṽ = Ṽ(a_{1}, a_{2}, ⋯, a_{n}) = inf_{ψ} V (ψ)

as the minimal long-run average sojourn time for the the given service rates.

3 The relation between the waiting time and the unused capacity

In this section we will find a relation between W and the total amount of unused work capacity S of the system as t → ∞. First we prove the following relation between the u_{i} and the v_{i}.

Lemma 3.1 For all t ∈ ℤ_{≥0} we have

∑_{i=1}^{n} a_{i} · u_{i}^{t} = ∑_{i=1}^{n} a_{i} · v_{i}^{t}.

Proof. The proof is done by induction on t. If t = 0, then u_{1} = u_{2} = ⋯ = u_{n} = v_{1} = v_{2} = ⋯ = v_{n} = 0 and so the relation holds trivially. Assume that the relation holds for t′ := t − 1. Further we assume that at time t′ the incoming job is routed to server l. Then

u_{l}^{t} = u_{l}^{t′} and v_{l}^{t} = v_{l}^{t′} + a_{l}^{−1} − 1.  (5)

Moreover for all k ≠ l we have

u_{k}^{t} = u_{k}^{t′} + max(0, 1 − v_{k}^{t′}) and v_{k}^{t} = max(0, v_{k}^{t′} − 1) = v_{k}^{t′} + max(−v_{k}^{t′}, −1).  (6)

So, by the induction hypothesis,

∑_{i=1}^{n} a_{i} · v_{i}^{t} − ∑_{i=1}^{n} a_{i} · u_{i}^{t} = ∑_{i=1}^{n} a_{i} · (v_{i}^{t} − v_{i}^{t′}) − ∑_{i=1}^{n} a_{i} · (u_{i}^{t} − u_{i}^{t′}) =

a_{l}(v_{l}^{t} − v_{l}^{t′}) − a_{l}(u_{l}^{t} − u_{l}^{t′}) + ∑_{k≠l} a_{k} {(v_{k}^{t} − v_{k}^{t′}) − (u_{k}^{t} − u_{k}^{t′})} =

1 − a_{l} − ∑_{k≠l} a_{k} = 0

and the induction step is complete. □

Remark that for t ∈ ℤ_{≥0}

S^{t} := ∑_{i=1}^{n} a_{i} · u_{i}^{t}

represents the total unused work capacity until time t, and ∑_{i=1}^{n} a_{i} · v_{i}^{t} the total remaining workload measured in amount of jobs at time t. So, we have proved that S^{t} = ∑_{i=1}^{n} a_{i} · v_{i}^{t} is equal to the total remaining workload in jobs at time t. Further S^{t} is monotonically nondecreasing in t, because the u_{i}^{t} are monotonically non-decreasing for i ∈ {1, 2, …, n}. For a policy ψ we define the total unused work capacity S as follows:

S = S(ψ) = S(a_{1}, a_{2}, …, a_{n}, ψ) = lim_{t→∞} S^{t}.

Thus we have

S = ∑_{i=1}^{n} lim_{t→∞} a_{i}u_{i}^{t} = lim_{t→∞} ∑_{i=1}^{n} a_{i}u_{i}^{t} = lim_{t→∞} ∑_{i=1}^{n} a_{i}v_{i}^{t}.  (7)

We define

S̃ = S̃(a_{1}, a_{2}, …, a_{n}) = inf_{ψ} S(ψ)

as the minimal total unused work capacity for the given service rates.

The following fundamental relation exists between W and S.

Theorem 3.2 For all (a_{1}, a_{2}, …, a_{n}) systems and policies ψ it holds that W < ∞ if and only if S < ∞. Further if W < ∞ then lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} exists and

W = lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} = S − \frac{n − 1}{2}.

Before we prove Theorem 3.2 we derive some lemmata.

Lemma 3.3 Let f : ℤ_{≥0} → ℝ be bounded. Suppose there exist H ⊆ ℤ_{≥0} and a, b ∈ ℝ_{>0} such that

\begin{matrix}f(n + 1) − f(n) = a & for & n ∈ H, \\ f(n + 1) − f(n) = −b & for & n ∈ ℤ_{≥0} \ H. \end{matrix}

Let H_{N} = #(n ∈ ℤ_{≥0} : n < N, n ∈ H),

A_{N} = \{ \begin{matrix}0 & if H_{N} = N \\ \frac{1}{N−H_{N}} · ∑_{\{n∉H,n<N\}} f(n) & if H_{N} < N \end{matrix} and

B_{N} = \{ \begin{matrix}0 & if H_{N} = 0 \\ \frac{1}{H_{N}} · ∑_{\{n∈H,n<N\}} f(n) & if H_{N} > 0 \end{matrix}

for N = 1, 2, . . .. Then

lim_{N→∞}(A_{N} − B_{N}) = \frac{a + b}{2}.

Proof. Because f is bounded, lim_{N→∞} H_{N} = ∞ and lim_{N→∞}(N − H_{N}) = ∞. So there exists an N_{0} ∈ ℕ such that A_{N} = \frac{1}{N−H_{N}} · ∑_{\{n∉H,n<N\}} f(n) and B_{N} = \frac{1}{H_{N}} · ∑_{\{n∈H,n<N\}} f(n) for N ≥ N_{0}. Let f̃ : ℝ_{≥0} → ℝ be the continuous piecewise linear extension of f, f̃(x) = f(⌊x⌋) + (x − ⌊x⌋) · (f(⌊x⌋ + 1) − f(⌊x⌋)) for x ∈ ℝ_{≥0}. Let

C_{N} = \frac{1}{N − H_{N}} · ∑_{\{n∉H,n<N\}} ∫_{n}^{n+1} f̃(t)dt and

D_{N} = \frac{1}{H_{N}} · ∑_{\{n∈H,n<N\}} ∫_{n}^{n+1} f̃(t)dt

for N ≥ N_{0}. If n ∈ H then ∫_{n}^{n+1} f̃(t)dt = ∫_{n}^{n+1}(f(n) + a · (t − n))dt = f(n) + \frac{a}{2}, hence D_{N} = B_{N} + \frac{a}{2} for N ≥ N_{0}. If n ∈ ℤ_{≥0} \ H then

∫_{n}^{n+1} f̃(t)dt = ∫_{n}^{n+1}(f(n) − b · (t − n))dt = f(n) − \frac{b}{2},

hence C_{N} = A_{N} − \frac{b}{2} for N ≥ N_{0}. So it suffices to prove that lim_{N→∞}(C_{N} − D_{N}) = 0.

Because f is bounded, we can choose m, M ∈ ℝ such that f(n) ∈ [m, M] for all n ∈ ℤ_{≥0}. Put P_{N} = {f(0), f(1), …, f(N −1)} for N = 1, 2, . . .. Define step functions g_{N}^{−} : [m, M] → ℤ_{≥0} and g_{N}^{+} : [m, M] → ℤ_{≥0} by

g_{N}^{−}(x) = \{ \begin{matrix}0 & if x ∈ P_{N} \\ #\{t ∈ [0, N) : f̃(t) = x, f̃′(t) < 0\} & else \end{matrix}

and

g_{N}^{+}(x) = \{ \begin{matrix}0 & if x ∈ P_{N} \\ #\{t ∈ [0, N) : f̃(t) = x, f̃′(t) > 0\} & else \end{matrix} .

If n ∈ H then

∫_{f(n)}^{f(n+1)} x · dx = ∫_{f(n)}^{f(n)+a} x · dx = a · ∫_{n}^{n+1} f̃(t)dt,

whence ∫_{m}^{M} x · g_{N}^{+}(x)dx = ∑_{n∈H,n<N} ∫_{f(n)}^{f(n+1)} xdx = a · ∑_{{n∈H,n<N}} ∫_{n}^{n+1} f̃(t)dt for N = 1, 2, . . .. Similarly if n ∈ H we have

∫_{m}^{M} g_{N}^{+}(x)dx = ∑_{n∈H,n<N} ∫_{f(n)}^{f(n+1)} dx = a · H_{N}.

So

D_{N} = \frac{∫_{m}^{M} x · g_{N}^{+}(x)dx}{∫_{m}^{M} g_{N}^{+}(x)dx} if N ≥ N_{0}.  (8)

Analogously it follows that

C_{N} = \frac{∫_{m}^{M} x · g_{N}^{−}(x)dx}{∫_{m}^{M} g_{N}^{−}(x)dx} if N ≥ N_{0}.  (9)

Since f̃ is continuous, |g_{N}^{−}(x) − g_{N}^{+}(x)| ≤ 1 for N = 1, 2, … and x ∈ [m, M]. Hence

| ∫_{m}^{M} x · g_{N}^{−}(x)dx − ∫_{m}^{M} x · g_{N}^{+}(x)dx| ≤

∫_{m}^{M} |x|dx ≤ max(m^{2}, M^{2})  (10)

and

| ∫_{m}^{M} g_{N}^{−}(x)dx − ∫_{m}^{M} g_{N}^{+}(x)dx| ≤ M − m  (11)

for N = 1, 2, . . .. Further

lim_{N→∞} ∫_{m}^{M} g_{N}^{−}(x)dx = lim_{N→∞} b · (N − H_{N}) = ∞  (12)

and

lim_{N→∞} ∫_{m}^{M} g_{N}^{+}(x)dx = lim_{N→∞} aH_{N} = ∞.  (13)

From (8) and (9) it follows that

C_{N} − D_{N} = \frac{∫_{m}^{M} x · g_{N}^{−}(x)dx − ∫_{m}^{M} x · g_{N}^{+}(x)dx}{∫_{m}^{M} g_{N}^{−}(x)dx}+

\frac{\frac{∫_{m}^{M} x·g_{N}^{+} (x)dx}{∫_{m}^{M} g_{N}^{+} (x)dx} · (∫_{m}^{M} g_{N}^{+}(x)dx − ∫_{m}^{M} g_{N}^{−}(x)dx)}{∫_{m}^{M} g_{N}^{−}(x)}.  (14)

From (10) and (12) we obtain

lim_{N→∞} \frac{∫_{m}^{M} x · g_{N}^{−}(x)dx − ∫_{m}^{M} x · g_{N}^{+}(x)dx}{∫_{m}^{M} g_{N}^{−}(x)dx} = 0.

So, by (8),(11) and (14) we have

| lim_{N→∞}(C_{N} − D_{N})| ≤ (M − m) · lim_{N→∞} \frac{D_{N}}{∫_{m}^{M} g_{N}^{−}(x)dx}.  (15)

Because m ≤ D_{N} ≤ M for N ≥ N_{0} it follows from (12) and (15) that

lim_{N→∞}(C_{N} − D_{N}) = 0.

□

Corollary 3.4 Let f, H, a, b be as in Lemma 3.3. Further for N = 1, 2, … let H_{N}, A_{N}, B_{N} as in Lemma 3.3 and let

E_{N} = \frac{1}{N} · ∑_{n=0}^{N−1} f(n).

Then

lim_{N→∞}(E_{N} − B_{N}) = \frac{a}{2}.

Proof. Since f is bounded we have that lim_{N→∞} \frac{H_{N}}{N−H_{N}} = \frac{b}{a}. Hence lim_{N→∞} \frac{N}{N−H_{N}} = \frac{a+b}{a} and thus

lim_{N→∞} \frac{N − H_{N}}{N} = \frac{a}{a + b}.  (16)

So, by Lemma 3.3 and (16) we have that

lim_{N→∞}(E_{N} − B_{N}) = lim_{N→∞}(\frac{N − H_{N}}{N} · A_{N} + \frac{H_{N}}{N} · B_{N} − B_{N}) = lim_{N→∞} \frac{N − H_{N}}{N} (A_{N} − B_{N}) =

lim_{N→∞} \frac{N − H_{N}}{N} · lim_{N→∞}(A_{N} − B_{N}) = \frac{a}{a + b} · \frac{a + b}{2} = \frac{a}{2}.

□

For t ∈ ℤ_{≥0} put I_{t} = {0, 1, …, t − 1}. Then if policy ψ is applied we define for i ∈ {1, 2, …, n} and t ∈ ℤ_{≥0} that

N_{i}^{t} = N_{i}^{t}(ψ) = ∑_{{t′∈I_{t}:k_{t′}(ψ)=i}} 1.

Hence N_{i}^{t} is the number of jobs among the first t incoming jobs that are routed to server i.

Lemma 3.5 If in an (a_{1}, a_{2}, …, a_{n}) system a policy ψ is applied such that for some i ∈ {1, 2, …, n} the function f : ℤ_{≥0} → ℝ defined by f(t) = v_{i}^{t} − u_{i}^{t} is bounded then

lim_{τ→∞}\{\frac{∑_{t=0}^{τ−1} v_{i}^{t}}{τ} − \frac{∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t}}{N_{i}^{τ}} \} = \frac{1}{2a_{i}} − \frac{1}{2}.

Proof. If k_{t} = i then we have by (5) that

f(t + 1) − f(t) = \frac{1}{a_{i}} − 1.

If k_{t} ≠ i then we have by (6) that

f(t + 1) − f(t) = −1.

So f satisfies the conditions of Corollary 3.4 with H = \{t : k_{t} = i\}, a = \frac{1}{a_{i}} − 1 and b = 1. Hence

lim_{τ→∞}\{\frac{∑_{t=0}^{τ−1}(v_{i}^{t} − u_{i}^{t})}{τ} − \frac{∑_{\{t∈I_{τ}:k_{t}=i\}}(v_{i}^{t} − u_{i}^{t})}{N_{i}^{τ}}\} = \frac{1}{2a_{i}} − \frac{1}{2}.  (17)

Since u_{i}^{t+1} > u_{i}^{t} implies that v_{i}^{t+1} = 0 it follows from the boundedness of f that lim_{t→∞} u_{i}^{t} =: L < ∞ and thus

lim_{τ→∞} \frac{∑_{t=0}^{τ−1} u_{i}^{t}}{τ} = lim_{τ→∞} \frac{∑_{\{t∈I_{τ}:k_{t}=i\}} u_{i}^{t}}{N_{i}^{τ}} = L.  (18)

By (17) and (18) we have that

lim_{τ→∞}\{\frac{∑_{t=0}^{τ−1} v_{i}^{t}}{τ} − \frac{∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t}}{N_{i}^{τ}} \} = \frac{1}{2a_{i}} − \frac{1}{2}.

□

Corollary 3.6 If in an (a_{1}, a_{2}, …, a_{n}) system a policy ψ is applied with S(ψ) < ∞ then we have for every server i ∈ {1, 2, …, n} that

lim_{τ→∞}\{\frac{∑_{t=0}^{τ−1} v_{i}^{t}}{τ} − \frac{∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t}}{N_{i}^{τ}} \} = \frac{1}{2a_{i}} − \frac{1}{2}.

Proof. Since S < ∞ we have for every i ∈ {1, 2, …, n} that lim_{t→∞} a_{i} · u_{i}^{t} := L_{i} ≤ S < ∞. It follows that a_{i} · v_{i}^{t} ≤ S and a_{i} · u_{i}^{t} ≤ L_{i} for every t ∈ ℤ_{≥0}. Define f_{i} : ℤ_{≥0} → ℝ by f_{i}(t) = v_{i}^{t} − u_{i}^{t} as in Lemma 3.5. Then f_{i}(t) ∈ [−\frac{L_{i}}{a_{i}} , \frac{S}{a_{i}}] for every t ∈ ℤ_{≥0} and thus f_{i} is bounded. Now apply Lemma 3.5 . □

If lim_{t→∞} \frac{N_{i}^{t}}{t} exists for i ∈ \{1, 2, …, n\} then we define

p_{i} = lim_{t→∞} \frac{N_{i}^{t}}{t}

as the fraction of jobs that is routed to server i.

Lemma 3.7 For every (a_{1}, a_{2}, …, a_{n}) system and policy ψ we have S < ∞ if and only if W < ∞. Further if W < ∞ then lim_{t→∞} \frac{N_{i}^{t}}{t} exists for all i ∈ \{1, 2, …, n\} and

p_{i} = lim_{t→∞} \frac{N_{i}^{t}}{t} = a_{i}  (19)

for i = 1, 2, …, n.

Proof. Suppose S < ∞. Then there exists M_{0} ∈ ℝ such that ∑_{i=1}^{n} a_{i}v_{i}^{t} < M_{0} for t ∈ ℤ_{≥0}. It follows that a_{i}v_{i}^{t} < M_{0} for i = 1, 2, …, n and t ∈ ℤ_{≥0} and thus v_{i}^{t} < M := \frac{M_{0}}{min_{i=1}^{n} a_{i}}. Hence v_{k_{t}}^{t} < M for all t ∈ ℤ_{≥0} and thus W ≤ M. Suppose S = ∞. Let L(t) be the total number of waiting jobs at time t ∈ ℝ_{≥0}. It is clear that L(t) ≥ S^{⌊t⌋} − n for every t ∈ ℝ_{≥0} and thus lim_{t→∞} L(t) = ∞. So the limiting time-average number of waiting jobs satisfies

L := lim_{t→∞} \frac{1}{t} · ∫_{0}^{t} L(t)dt = ∞.  (20)

Let J_{k}(t) = 1 for t ∈ ℝ_{≥0}, if the k-th arriving job is waiting in one of the queues at time t and else J_{k}(t) = 0. Then,

W_{k} = ∫_{0}^{∞} J_{k}(t)dt,  (21)
L(t) = ∑_{k=1}^{∞} J_{k}(t).  (22)

Let U(t) := ∑_{k=1}^{t+1} W_{k} be the sum of the waiting times of jobs arriving in [0, t] for t ∈ ℝ_{≥0}. Then for all T ∈ ℝ_{≥0} we have by (21) and (22)

∫_{0}^{T} L(t)dt = ∫_{0}^{T} ∑_{k=1}^{∞} J_{k}(t)dt = ∑_{k=1}^{∞} ∫_{0}^{T} J_{k}(t)dt =

∑_{k=1}^{T +1} ∫_{0}^{T} J_{k}(t)dt ≤ ∑_{k=1}^{T +1} ∫_{0}^{∞} J_{k}(t)dt = ∑_{k=1}^{T +1} W_{k} = U(T).  (23)

Hence by (20) and (23) we have

lim_{t→∞} \frac{1}{t} · U(t) = ∞.

Thus

W = lim sup_{t→∞} \frac{1}{t} · ∑_{k=1}^{t} W_{k} = lim sup_{t→∞} \frac{1}{⌊t⌋ + 1} · U(t) = lim_{t→∞} \frac{1}{t} · U(t) = ∞.

The first part of the lemma is proved and for the second part we assume that W < ∞ and thus S < ∞. Let \overline{p_{i}} = lim sup_{t→∞} \frac{N_{i}^{t}}{t} for i ∈ \{1, 2, …, n\}. We will show that \overline{p_{i}} = a_{i} for i ∈ {1, 2, …, n}. We have that

∑_{i=1}^{n} \overline{p_{i}} = ∑_{i=1}^{n} lim sup_{t→∞} \frac{N_{i}^{t}}{t} ≥ lim sup_{t→∞} ∑_{i=1}^{n} \frac{N_{i}^{t}}{t} = 1.

Hence if there exists an i ∈ \{1, 2, …, n\} with \overline{p_{i}} ≠ a_{i} then it follows that there exists a k ∈ \{1, 2, …, n\} with \overline{p_{k}} > a_{k}. Let a_{k} < β < \overline{p_{k}}. Then for all t_{0} ∈ ℤ_{≥0} there exist t ≥ t_{0} such that \frac{N_{k}^{t}}{t} > β and thus N_{k}^{t} > β · t = a_{k} · t + t · (β − a_{k}). Hence

a_{k} · v_{k}^{t} ≥ N_{k}^{t} − a_{k} · t > t · (β − a_{k}) ≥ t_{0} · (β − a_{k}).

Thus v_{k}^{t} ≥ \frac{β−a_{k}}{a_{k}} · t_{0} and it follows that lim sup_{t→∞} v_{k}^{t} = ∞ and thus S = ∞, which is a

contradiction. So \overline{p_{i}} = a_{i} for i ∈ \{1, 2, …, n\}. Let \underline{p_{i}} = lim inf_{t→∞} \frac{N_{i}^{t}}{t} for i ∈ \{1, 2, …, n\}. We have to show that \underline{p_{i}} = a_{i} for i ∈ \{1, 2, …, n\}. Analogously as above it follows that ∑_{i=1}^{n} \underline{p_{i}} ≤ 1. Thus if \underline{p_{i}} ≠ a_{i} for an i ∈ \{1, 2, …, n\} then there exist a k ∈ \{1, 2, …, n\} such that \underline{p_{k}} < a_{k}. Let \underline{p_{k}} < β < a_{k}. Then for all t_{0} ∈ ℤ_{≥0} there exist t ≥ t_{0} such that \frac{N_{k}^{t}}{t} < β and thus N_{k}^{t} < β · t = a_{k} · t − t · (a_{k} − β). Hence

a_{k} · u_{k}^{t} ≥ a_{k} · t − N_{k}^{t} ≥ t_{0} · (a_{k} − β).

Thus u_{k}^{t} ≥ \frac{a_{k}−β}{a_{k}} · t_{0} and it follows that lim sup_{t→∞} u_{k}^{t} = lim_{t→∞} u_{k}^{t} = ∞ and thus S = ∞, which

is a contradiction. So, if S < ∞ then \underline{p_{i}} = \overline{p_{i}} = a_{i} for i ∈ \{1, 2, …, n\}. Hence lim_{t→∞} \frac{N_{i}^{t}}{t} exists and p_{i} = lim_{t→∞} \frac{N_{i}^{t}}{t} = a_{i} for i ∈ \{1, 2, …, n\}. □

Remark. The argument that W < ∞ implies S < ∞ is a simplification of a proof of Little’s theorem by Stidham in [16].

Proof of Theorem 3.2.

The first part of the theorem follows from Lemma 3.7. We now assume that S < ∞. From (19) and Corollary 3.6 it follows for every i ∈ {1, 2, …, n} that

lim_{τ→∞} \frac{1}{τ} · (∑_{t=0}^{τ−1} a_{i} · v_{i}^{t} − ∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t}) =

a_{i} · lim_{τ→∞}\{\frac{∑_{t=0}^{τ−1} v_{i}^{t}}{τ} − \frac{∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t}}{N_{i}^{τ}} \} = a_{i} · (\frac{1}{2a_{i}} − \frac{1}{2}) = \frac{1}{2} − \frac{1}{2}a_{i}.  (24)

Because S^{t} is monotonically non-decreasing in t and bounded it follows that

S = lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} S^{t} = lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} ∑_{i=1}^{n} a_{i} · v_{i}^{t} = lim_{τ→∞} ∑_{i=1}^{n} ∑_{t=0}^{τ−1} \frac{a_{i} · v_{i}^{t}}{τ} .

Thus it follows from (24) that

S − lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} = lim_{τ→∞} ∑_{i=1}^{n} \frac{1}{τ} · (∑_{t=0}^{τ−1} a_{i} · v_{i}^{t} − ∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t}) =

∑_{i=1}^{n}( lim_{τ→∞} \frac{1}{τ} · (∑_{t=0}^{τ−1} a_{i} · v_{i}^{t} − ∑_{\{t∈I_{τ}:k_{t}=i\}} v_{i}^{t})) = ∑_{i=1}^{n}(\frac{1}{2} − \frac{1}{2} · a_{i}) = \frac{n − 1}{2}.

So, lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} exists and

W = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} = lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} = S − \frac{n − 1}{2}.

□

The following proposition shows that minimizing the long-run average waiting time W also minimizes the long-run average sojourn time V and vice versa.

Proposition 3.8 For all (a_{1}, a_{2}, …, a_{n}) systems and policies ψ it holds that V < ∞ if and only if S < ∞ and

V = W + n if S < ∞.

Proof. It is clear that V < ∞ if and only if W < ∞ and so it follows from Theorem 3.2 that V < ∞ if and only if S < ∞. Let ψ be a policy such that S < ∞. Then by (19) it follows that

lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} a_{k_{t}}^{−1} = lim_{τ→∞} ∑_{i=1}^{n} a_{i}^{−1} \frac{N_{i}^{τ}}{τ} = ∑_{i=1}^{n} a_{i}^{−1}a_{i} = n.

Hence

V = lim sup_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1}(v_{k_{t}}^{t} + a_{k_{t}}^{−1}) = W + lim_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} a_{k_{t}}^{−1} = W + n.

□

From now on we will only consider W and not V, but from Proposition 3.8 it can be deduced what the results imply for V.

4 An upper bound for the minimal long-run average waiting time

In this section we derive an upper bound for the minimal long-run average waiting time W̃. Further we show that for every (a_{1}, a_{2}, …, a_{n}) system an optimal policy exists and we give a MPP such that from an optimal solution of the MPP an optimal policy can be obtained and vice versa.

Lemma 4.1 For all s ∈ ℤ_{≥0} we have

u_{i}^{s} = max_{t∈I_{s+1}}(u_{i}^{t} − v_{i}^{t}) = max_{t∈I_{s+1}}(t − a_{i}^{−1} · N_{i}^{t}).

Proof. The proof of the first equality is done by induction on s. It holds for s = 0. Suppose that it holds for s′ = s. If k_{s} = i then by (5) we have u_{i}^{s+1} = u_{i}^{s} and v_{i}^{s+1} > v_{i}^{s}. So, by the induction hypothesis,

u_{i}^{s+1} = u_{i}^{s} = max_{t∈I_{s+1}}(u_{i}^{t} − v_{i}^{t}) = max_{t∈I_{s+2}}(u_{i}^{t} − v_{i}^{t}).

If k_{s} ≠ i and v_{i}^{s} ≤ 1, then by (6) we have u_{i}^{s+1} ≥ u_{i}^{s} and v_{i}^{s+1} = 0. Thus, by the induction hypothesis,

u_{i}^{s+1} − v_{i}^{s+1} ≥ u_{i}^{s} = max_{t∈I_{s+1}}(u_{i}^{t} − v_{i}^{t}).

Hence u_{i}^{s+1} = u_{i}^{s+1} − v_{i}^{s+1} = max_{t∈I_{s+2}}(u_{i}^{t} − v_{i}^{t}). Further if k_{s} ≠ i and v_{i}^{s} > 1 then by (6) we have u_{i}^{s+1} = u_{i}^{s} and v_{i}^{s+1} = v_{i}^{s} − 1 ≥ 0. So, by the induction hypothesis,

u_{i}^{s+1} − v_{i}^{s+1} ≤ u_{i}^{s} = max_{t∈I_{s+1}}(u_{i}^{t} − v_{i}^{t}).

Hence

u_{i}^{s+1} = u_{i}^{s} = max_{t∈I_{s+1}}(u_{i}^{t} − v_{i}^{t}) = max_{t∈I_{s+2}}(u_{i}^{t} − v_{i}^{t})

and the induction step is complete.

For the second equality it suffices to show that u_{i}^{t} − v_{i}^{t} = t − a_{i}^{−1} · N_{i}^{t} for all t ∈ ℤ_{≥0}. Because for all t ∈ ℤ_{≥0} we have

(u_{i}^{t+1} − v_{i}^{t+1}) − (u_{i}^{t} − v_{i}^{t}) = \{ \begin{matrix}1 − a_{i}^{−1} & if k_{t} = i \\ 1 & if k_{t} ≠ i \end{matrix}  (25)

it follows by induction on t that

u_{i}^{t} − v_{i}^{t} = u_{i}^{0} − v_{i}^{0} + N_{i}^{t} · (1 − a_{i}^{−1}) + (t − N_{i}^{t}) · 1 = t − a_{i}^{−1} · N_{i}^{t}  (26)

for all t ∈ ℤ_{≥0}. □

We define for i ∈ {1, 2, …, n} the variables

d_{i}(ψ) := lim_{t→∞} a_{i} · u_{i}^{t},

the total amount of unused work capacity of server i if policy ψ is applied. It is clear that

S = ∑_{i=1}^{n} d_{i}(ψ).  (27)

Lemma 4.2 For every (a_{1}, a_{2}, …, a_{n}) system and applied policy ψ we have

d_{i}(ψ) = sup_{t∈ℤ_{≥0}}(a_{i} · t − N_{i}^{t})

for all i ∈ {1, 2, …, n}.

Proof. From Lemma 4.1 it follows that

d_{i}(ψ) = lim_{s→∞} a_{i} · u_{i}^{s} = lim_{s→∞} max_{t∈I_{s+1}}(a_{i} · t − N_{i}^{t}) = sup_{t∈ℤ_{≥0}}(a_{i} · t − N_{i}^{t}).

□

Let d_{i} ∈ ℝ_{≥0} be given. It follows from Lemma 4.2 for a policy ψ that d_{i}(ψ) ≤ d_{i} if and only if t · a_{i} − N_{i}^{t}(ψ) ≤ d_{i} for all t ∈ ℤ_{≥0} and this is true if and only if N_{i}^{t}(ψ) ≥ t · a_{i} − d_{i} for all t ∈ ℤ_{≥0}. Hence N_{i}^{t}(ψ) ≥ max(⌈t · a_{i} − d_{i}⌉, 0) for all t ∈ ℤ_{≥0}, because N_{i}^{t}(ψ) ∈ ℤ_{≥0}. So suppose that for given d_{1}, d_{2}, …, d_{n} ∈ ℝ_{≥0} there exists a policy ψ with d_{i}(ψ) = d_{i} for i = 1, 2, …, n. Then

t = ∑_{i=1}^{n} N_{i}^{t}(ψ) ≥ ∑_{i=1}^{n} max(⌈t · a_{i} − d_{i}⌉, 0) for t = 0, 1, ….

Thus

t ≥ ∑_{i=1}^{n} max(⌈t · a_{i} − d_{i}⌉, 0) for t = 0, 1, …  (28)

is a necessary condition for the existence of a policy ψ such that d_{i}(ψ) = d_{i} for i = 1, 2, …, n and we have proved the following lemma.

Lemma 4.3 If a policy ψ is applied to an (a_{1}, a_{2}, …, a_{n}) system then

t ≥ ∑_{i=1}^{n} max(⌈t · a_{i} − d_{i}(ψ)⌉, 0) for t = 0, 1, ….

On the other hand, (28) is not sufficient for the existence of a policy ψ with d_{i}(ψ) = d_{i} for i ∈ \{1, 2, …, n\}. For example, if a_{i} = \frac{p}{q} with gcd(p, q) = 1 then, by Lemma 4.2, q · d_{i}(ψ) = q · sup_{t∈ℤ_{≥0}}(a_{i} · t − N_{i}^{t}) ∈ ℤ. So, in that case q · d_{i} ∈ ℤ is another necessary condition. However, we will show that there exists a policy ψ with d_{i}(ψ) ≤ d_{i} for i = 1, 2, …, n if d_{1}, d_{2}, …, d_{n} fulfill (28). To do so we use the following greedy algorithm to construct such a policy ψ. We denote this algorithm as the GG (General Greedy) algorithm.

GG Algorithm. Let d_{1}, d_{2}, …, d_{n} ∈ ℝ_{≥0} be given. Then we determine ψ inductively in the following way. Suppose k_{0}(ψ), k_{1}(ψ), …, k_{t−1}(ψ) have been determined. Then for j = 1, 2, …, n put q_{j}(t) = min{t′ ∈ ℤ_{≥0} : t′ · a_{j} > d_{j} − t · a_{j} + N_{j}^{t}(ψ)}. Choose k_{t}(ψ) such that k_{t}(ψ) = i ∈ {1, 2, …, n} for which q_{i}(t) = min_{j∈{1,2,... ,n}} q_{j}(t).

Theorem 4.4 Let ψ be a policy obtained by applying the GG algorithm. Then we have d_{i}(ψ) ≤ d_{i} for i = 1, 2, …, n if d_{1}, d_{2}, …, d_{n} fulfill (28).

Proof. Suppose there exists an j ∈ {1, 2, …, n} with d_{j}(ψ) > d_{j}. Then there exist t ∈ ℤ_{≥0} for which N_{j}^{t}(ψ) < t · a_{j} − d_{j} and thus t · a_{j} > d_{j} and q_{j}(t) = 0. Let t′ = min{t ∈ ℤ_{≥0} : q_{j}(t) = 0}. Then N_{j}^{t′}(ψ) ≤ ⌈t′ · a_{j} − d_{j}⌉ − 1. Thus from ∑_{i=1}^{n} N_{i}^{t′}(ψ) = t′ ≥ ∑_{i=1}^{n} max(⌈t′ · a_{i} − d_{i}⌉, 0) it follows that there exists a k ≠ j with N_{k}^{t′}(ψ) ≥ max(⌈t′ · a_{k} − d_{k}⌉, 0) + 1. Hence N_{k}^{t′}(ψ) ≥ 1 and N_{k}^{t′}(ψ) ≥ t′ · a_{k} − d_{k} + 1. Let t_{0} = max{0 ≤ t < t′ : k_{t}(ψ) = k}. Then we have N_{j}^{t_{0}}(ψ) ≤ N_{j}^{t′}(ψ) < t′·a_{j} −d_{j} and thus q_{j}(t_{0}) ≤ t′−t_{0}. Moreover N_{k}^{t_{0}}(ψ) = N_{k}^{t′}(ψ)−1 ≥ t′·a_{k}−d_{k} and thus q_{k}(t_{0}) ≥ t′ −t_{0} +1 > q_{j}(t_{0}). This contradicts the fact that the GG algorithm is applied. □

Put

D = D(a_{1}, a_{2}, …, a_{n}) = {(d_{1}, d_{2}, …, d_{n}) ∈ ℝ^{n} : d_{1}, d_{2}, …, d_{n} fulfill condition (28)}.

Lemma 4.5 Let d_{1}, d_{2}, …, d_{n} ∈ ℝ such that

∑_{i=1}^{n} d_{i} = n − 1 and 0 ≤ d_{i} < 1 + a_{i} for i = 1, 2, …, n.  (29)

Then (d_{1}, d_{2}, …, d_{n}) ∈ D.

Proof. Because d_{i} ≥ 0 for i = 1, 2, …, n we have max(⌈−d_{i}⌉, 0) = 0 for i = 1, 2, …, n. Hence ∑_{i=1}^{n} max(⌈−d_{i}⌉, 0) = 0. Further by d_{i} < 1 + a_{i} we have for t = 1, 2, … that

max(0, ⌈t · a_{i} − d_{i}⌉) = ⌈t · a_{i} − d_{i}⌉ < t · a_{i} − d_{i} + 1

for i = 1, 2, …, n. Hence

∑_{i=1}^{n} max(⌈t · a_{i} − d_{i}⌉, 0) < ∑_{i=1}^{n}(t · a_{i} − d_{i} + 1) =

t − (n − 1) + n = t + 1

and ∑_{i=1}^{n} max(⌈t · a_{i} − d_{i}⌉, 0) ∈ ℤ_{≥0}. So, ∑_{i=1}^{n} max(⌈t · a_{i} − d_{i}⌉, 0) ≤ t and condition (28) is fulfilled. □

Particular d_{1}, d_{2}, …, d_{n} that fulfill (29) are for example that d_{i} = 0 for an arbitrary i ∈ {1, 2, …, n} and d_{j} = 1 for all j ≠ i. Another example is d_{i} = 1 − a_{i} for i = 1, 2, …, n. Hence D ≠ ∅ for every (a_{1}, a_{2}, …, a_{n}) system. Further it is obvious that if (d_{1}, d_{2}, …, d_{n}) ∈ D then (d_{1} + e_{1}, d_{2} + e_{2}, …, d_{n} + e_{n}) ∈ D for every e_{1}, e_{2}, …, e_{n} ∈ ℝ_{≥0}. From the condition for t = 0 it follows from (28) that d_{i} ≥ 0 for i = 1, 2, …, n if (d_{1}, d_{2}, …, d_{n}) ∈ D. Thus inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i} ≥ 0.

Theorem 4.6 For every (a_{1}, a_{2}, …, a_{n}) system we have

S̃ = inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i} ≤ n − 1.

Proof There exist (d_{1}, d_{2}, …, d_{n}) ∈ D with ∑_{i=1}^{n} d_{i} = n − 1 and thus we have inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i} ≤ n − 1. So, it remains to prove that S̃ = inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i}. According to Lemma 4.3 we have for every policy ψ that d_{1}(ψ), d_{2}(ψ), …, d_{n}(ψ) fulfill condition (28). Hence,

S(ψ) = ∑_{i=1}^{n} d_{i}(ψ) ≥ inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i}

and thus

S̃ = inf_{ψ} S(ψ) ≥ inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i}.

On the other hand, if (d_{1}, d_{2}, …, d_{n}) ∈ D then according to Theorem 4.4 there exists a policy ψ with d_{i}(ψ) ≤ d_{i} for i = 1, 2, …, n and thus S(ψ) ≤ ∑_{i=1}^{n} d_{i}. Hence,

S̃ = inf_{ψ} S(ψ) ≤ inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i}.

□

From Theorem 3.2 and Theorem 4.6 we have the following corollary which gives an upper bound for the minimal long-run average waiting time W̃ for every (a_{1}, a_{2}, …, a_{n}) system.

Corollary 4.7 For every (a_{1}, a_{2}, …, a_{n}) system we have

W̃ = S̃ − \frac{n − 1}{2}  (30)

and

0 ≤ W̃ ≤ \frac{n − 1}{2}.

Lemma 4.8 D ⊆ ℝ^{n} is closed for every (a_{1}, a_{2}, …, a_{n}) system.

Proof. For t = 0, 1, … put

D^{t} = D^{t}(a_{1}, a_{2}, …, a_{n}) = {(d_{1}, d_{2}, …, d_{n}) ∈ ℝ^{n} : t ≥ ∑_{i=1}^{n} max(0, ⌈t · a_{i} − d_{i}⌉)}.

Then D = ∩_{t=0}^{∞}D_{t}. So it suffices to show that D_{t} ⊆ ℝ^{n} is closed for t = 0, 1, . . .. Let t ∈ ℤ_{≥0} be fixed and suppose \underline{b} = (b_{1}, b_{2}, …, b_{n}) ∈ ℝ^{n}\D^{t}. Put m_{i} = ⌈t · a_{i} − b_{i}⌉ − 1 for i = 1, 2, …, n. Then m_{i} ∈ ℤ and t · a_{i} − b_{i} = m_{i} + δ_{i} with δ_{i} ∈ (0, 1] for i = 1, 2, …, n. Let 0 < ε < min_{i=1}^{n} δ_{i} and \underline{c} = (c_{1}, c_{2}, …, c_{n}) ∈ ℝ^{n} with ∥ \underline{c} − \underline{b} ∥_{∞}< ε. Then

⌈t · a_{i} − c_{i}⌉ ≥ ⌈t · a_{i} − b_{i} − ε⌉ = ⌈m_{i} + δ_{i} − ε⌉ =
m_{i} + 1 = ⌈t · a_{i} − b_{i}⌉ for i = 1, 2, …, n.

Hence,

∑_{i=1}^{n} max(⌈t · a_{i} − c_{i}⌉, 0) ≥ ∑_{i=1}^{n} max(⌈t · a_{i} − b_{i}⌉, 0) > t

and thus \underline{c} ∈ ℝ^{n}\D^{t}. So, ℝ^{n}\D^{t} is open and D^{t} ⊆ ℝ^{n} is closed for t = 0, 1, …. □

Theorem 4.9 For every (a_{1}, a_{2}, …, a_{n}) system we have

S̃ = min_{ψ} S(ψ).  (31)

Proof. Let H = {(d_{1}, d_{2}, …, d_{n}) ∈ ℝ^{n} : ∑_{i=1}^{n} d_{i} ≤ n − 1} and D′ = D ∩ H. Then D′ is closed, because D and H are closed. Further D′ ≠ ∅, because (1 − a_{1}, 1 − a_{2}, …, 1 − a_{n}) ∈ D′. Let (d_{1}, d_{2}, …, d_{n}) ∈ D′. As observed in the Proof of Theorem 4.6 we have d_{i} ≥ 0 for i = 1, 2, …, n. So, 0 ≤ d_{i} ≤ n − 1 for i = 1, 2, …, n and thus D′ is bounded. Hence D′ is compact. Because a continuous function assumes a minimum value on a compact set there exists (d′_{1}, d′_{2}, …, d′_{n}) ∈ D′ for which

∑_{i=1}^{n} d′_{i} = min_{(d_{1},d_{2},... ,d_{n})∈D′} ∑_{i=1}^{n} d_{i} = min_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i}.  (32)

Because (d′_{1}, d′_{2}, …, d′_{n}) ∈ D it follows from Theorem 4.4 that there exists a policy ψ′ with d_{i}(ψ′) ≤ d′_{i} for i = 1, 2, …, n. So, if d_{i}(ψ′) ≠ d′_{i} for some i ∈ {1, 2, …, n} then ∑_{i=1}^{n} d_{i}(ψ′) < ∑_{i=1}^{n} d′_{i}. This contradicts the minimality of ∑_{i=1}^{n} d′_{i}, because (d_{1}(ψ′), d_{2}(ψ′), …, d_{n}(ψ′)) ∈ D′. Hence d_{i}(ψ′) = d′_{i} for i = 1, 2, …, n and according to (32) and Theorem 4.6 we have

S(ψ′) = ∑_{i=1}^{n} d_{i}(ψ′) = ∑_{i=1}^{n} d′_{i} = inf_{(d_{1},d_{2},... ,d_{n})∈D} ∑_{i=1}^{n} d_{i} = S̃.

□

We define a policy ψ to be optimal for a given (a_{1}, a_{2}, …, a_{n}) system if and only if S(ψ) = S̃ and thus W (ψ) = W̃. Consider the following MPP.

minimize S  = ∑_{i=1}^{n} d_{i}

subject to:

∑_{i=1}^{n} max(0, ⌈t · a_{i} − d_{i}⌉) ≤ t for t = 0, 1, …
d_{i}  ∈ ℝ_{≥0} for i = 1, 2, …, n

(33)

It follows from Theorem 4.4,Theorem 4.6 and Theorem 4.9 that for every (a_{1}, a_{2}, …, a_{n}) system an optimal solution of (33) exists and that from an optimal solution of (33) an optimal policy can be obtained by applying the GG algorithm to that solution. Conversely, if ψ is an optimal policy then d_{1}(ψ), d_{2}(ψ), …, d_{n}(ψ) give an optimal solution of (33). Further, suppose that d_{1}, d_{2}, …, d_{n} fulfill the constraints of (33). Then (d_{1}, d_{2}, …, d_{n}) ∈ D and a policy ψ can be obtained with d_{i}(ψ) ≤ d_{i} for i = 1, 2, …, n by applying the GG algorithm. Then we have

S̃ ≤ S(ψ) = ∑_{i=1}^{n} d_{i}(ψ) ≤ ∑_{i=1}^{n} d_{i}.  (34)

Moreover the d_{i}(ψ) also fulfill the constraints of (33). So the same procedure can be applied to the d_{i}(ψ). So, this may be a way to obtain iteratively better policies and in section 6 we will give an example of this.

5 The structure of optimal policies

Let ψ be a given policy. Then for all s ∈ ℤ_{≥0} we define the policy ψ^{s} by k_{t}(ψ^{s}) = k_{t+s}(ψ) for t = 0, 1, …. Thus ψ^{s} is a shift of policy ψ for s = 0, 1, . . ..

Lemma 5.1 Let ψ be a policy with k_{0}(ψ) = j. Then we have d_{j}(ψ^{1}) ≤ d_{j}(ψ) + 1 − a_{j} and d_{i}(ψ^{1}) = d_{i}(ψ) − a_{i} for all i ≠ j.

Proof. By Lemma 4.2 we have that

d_{j}(ψ^{1}) = sup_{t∈ℤ_{≥0}}(t · a_{j} − N_{j}^{t}(ψ^{1})) = sup_{t∈ℤ_{≥0}}(t · a_{j} − (N_{j}^{t+1}(ψ) − 1)) =

sup_{t∈ℤ_{≥1}}(t · a_{j} − N_{j}^{t}(ψ)) + (1 − a_{j}) ≤ sup_{t∈ℤ_{≥0}}(t · a_{j} − N_{j}^{t}(ψ)) + (1 − a_{j}) = d_{j}(ψ) + 1 − a_{j}.

Further for every i ≠ j we have sup_{t∈ℤ_{≥1}}(t · a_{i} − N_{i}^{t}(ψ)) ≥ a_{i} and thus by Lemma 4.2 we have

d_{i}(ψ^{1}) = sup_{t∈ℤ_{≥0}}(t · a_{i} − N_{i}^{t}(ψ^{1})) = sup_{t∈ℤ_{≥1}}((t − 1) · a_{i} − N_{i}^{t}(ψ)) =

sup_{t∈ℤ_{≥0}}(t · a_{i} − N_{i}^{t}(ψ)) − a_{i} = d_{i}(ψ) − a_{i}.

□

Corollary 5.2 For every policy ψ we have S(ψ^{t}) ≤ S(ψ) for every t ∈ ℤ_{≥0}.

Proof. By Lemma 5.1 we have

S(ψ^{1}) = ∑_{i=1}^{n} d_{i}(ψ^{1}) ≤ ∑_{i=1}^{n}(d_{i}(ψ) − a_{i}) + 1 = ∑_{i=1}^{n} d_{i}(ψ) = S(ψ).

By induction we have S(ψ) ≥ S(ψ^{1}) ≥ S(ψ^{2}) ≥ …. □

If policy ψ is applied in an (a_{1}, a_{2}, …, a_{n}) system then for every t ∈ ℤ_{≥0} and i ∈ {1, 2, …, n} we put

h_{i}^{t} = h_{i}^{t}(ψ) = d_{i}(ψ) − t · a_{i} + N_{i}^{t}(ψ).

Observe that by Lemma 4.2 we have h_{i}^{t}(ψ) ≥ 0 for every policy ψ, t ∈ ℤ_{≥0} and i ∈ {1, 2, …, n}. Further we have the following lemma.

Lemma 5.3 For every policy ψ , t ∈ ℤ_{≥0} and i ∈ {1, 2, …, n} we have that h_{i}^{t} ≥ a_{i} · v_{i}^{t}. Moreover h_{i}^{t} − a_{i} · v_{i}^{t} is monotonically non-increasing in t and lim_{t→∞}(h_{i}^{t} − a_{i} · v_{i}^{t}) = 0.

Proof. From (26) we have that a_{i} · v_{i}^{t} = a_{i} · u_{i}^{t} + N_{i}^{t} − t · a_{i} and thus

h_{i}^{t} − a_{i} · v_{i}^{t} = d_{i} − a_{i} · u_{i}^{t} for every t ∈ ℤ_{≥0}.  (35)

Thus the lemma follows from the fact that u_{i}^{t} is monotonically non-decreasing in t and d_{i} = lim_{t→∞} a_{i} · u_{i}^{t}. □

We also have the following lemma.

Lemma 5.4 If ψ is an optimal policy then for every t ∈ ℤ_{≥0} we have that ψ^{t} is an optimal policy and d_{i}(ψ^{t}) = h_{i}^{t}(ψ) for i = 1, 2, …, n.

Proof. By Lemma 5.1 and induction it follows for every t ∈ ℤ_{≥0} that d_{i}(ψ^{t}) ≤ h_{i}^{t}(ψ) for i = 1, 2, …, n. Suppose that there exists an i ∈ {1, 2, …, n} for which d_{i}(ψ^{t}) < h_{i}^{t}(ψ). Then

S(ψ^{t}) = ∑_{i=1}^{n} d_{i}(ψ^{t}) < ∑_{i=1}^{n} h_{i}^{t}(ψ) = S(ψ),

which contradicts the fact that ψ is an optimal policy. Hence d_{i}(ψ^{t}) = h_{i}^{t}(ψ) for i = 1, 2, …, n and S(ψ^{t}) = S(ψ) = S̃. □

Corollary 5.5 Let ψ be an optimal policy in an (a_{1}, a_{2}, …, a_{n}) system. Then d_{1} := h_{1}^{t}(ψ), d_{2} := h_{2}^{t}(ψ), …, d_{n} := h_{n}^{t}(ψ) is an optimal solution of (33) for every t ∈ ℤ_{≥0}.

Lemma 5.6 Let ψ be an optimal policy in an (a_{1}, a_{2}, …, a_{n}) system. Then for every i ∈ {1, 2, …, n}, ε > 0 and t_{0} ∈ ℤ_{≥0} there exist t ∈ ℤ_{≥t_{0}} such that h_{i}^{t}(ψ) < ε.

Proof. By Lemma 5.4 and Lemma 4.2 we have that

sup_{t∈ℤ_{≥t_{0}}}(d_{i}(ψ^{t_{0}}) − h_{i}^{t}(ψ)) = sup_{t∈ℤ_{≥t_{0}}}(h_{i}^{t_{0}}(ψ) − h_{i}^{t}(ψ)) =

sup_{t∈ℤ_{≥t_{0}}}((t − t_{0})a_{i} + N_{i}^{t}(ψ) − N_{i}^{t_{0}}(ψ)) = sup_{t∈ℤ_{≥0}}(t · a_{i} − N_{i}^{t}(ψ^{t_{0}})) = d_{i}(ψ^{t_{0}}).

So, for every ε > 0 there exist t ∈ ℤ_{≥t_{0}} such that h_{i}^{t}(ψ) < ε. □

Lemma 5.7 Suppose that for some policy ψ we have for a t_{0} ∈ ℤ_{≥0} that there exists a j ∈ {1, 2, …, n} such that h_{j}^{t_{0}}(ψ) ≥ 1, N_{j}^{t_{0}}(ψ) ≥ 1 and k_{t_{0}}(ψ) = l ≠ j. Let t̃= max{t < t_{0} : k_{t}(ψ) = j}. Consider the policy φ defined by k_{t}(φ) = k_{t}(ψ) for every t ∈ ℤ_{≥0}, t ≠ t̃, t_{0}, kt̃(φ) = l and k_{t_{0}}(φ) = j. Then we have that d_{l}(φ) ≤ d_{l}(ψ) and d_{i}(φ) = d_{i}(ψ) for every i ∈ {1, 2, …, n} \ {l}.

Proof. Since N_{l}^{t}(φ) ≥ N_{l}^{t}(ψ) for every t ∈ ℤ_{≥0} we have by Lemma 4.2 that d_{l}(φ) ≤ d_{l}(ψ). Further it is obvious for i ∈ {1, 2, …, n} \ {j, l} that d_{i}(φ) = d_{i}(ψ). So it remains to prove that d_{j}(φ) = d_{j}(ψ). Because N_{j}^{t}(φ) ≤ N_{j}^{t}(ψ) for every t ∈ ℤ_{≥0} we have by Lemma 4.2 that d_{j}(φ) ≥ d_{j}(ψ). If d_{j}(φ) > d_{j}(ψ) then

d_{j}(φ) = t_{0} · a_{j} − N_{j}^{t_{0}}(φ) = t_{0} · a_{j} − N_{j}^{t_{0}}(ψ) + 1 > d_{j}(ψ) ⇒

h_{j}^{t_{0}}(ψ) = d_{j}(ψ) − t_{0} · a_{j} + N_{j}^{t_{0}}(ψ) < 1,

which is a contradiction. Thus d_{j}(φ) = d_{j}(ψ). □

Theorem 5.8 For every ε > 0 and i ∈ {1, 2, …, n} there exists an optimal solution d_{1}, d_{2}, …, d_{n} of (33) with d_{i} < ε and d_{j} < 1 for all j ≠ i.

Proof. Without loss of generality we can assume i = 1. Let d_{1}^{∗}, d_{2}^{∗}, …, d_{n}^{∗} be an optimal solution of (33) and ψ an optimal policy obtained by applying the GG algorithm to this optimal solution. Then according to Corollary 5.5 it is sufficient to show that for every ε > 0 there exists a t ∈ ℤ_{≥0} such that h_{1}^{t}(ψ) < ε and h_{j}^{t}(ψ) < 1 for j = 2, 3, …, n. Suppose this does not hold. Then there exists an 0 < ε < a_{1} such that for all t ∈ ℤ_{≥0} for which h_{1}^{t} < ε there exists an i ∈ {2, 3, …, n} with h_{i}^{t} ≥ 1. Let t′ = min{t ∈ ℤ_{≥0} : N_{i}^{t}(ψ) ≥ 1} for all i ∈ {2, 3, …, n} and J = {t ∈ ℤ_{≥0}, t ≥ t′ : h_{1}^{t} < ε}. Then by Lemma 5.6 we have that J ≠ ∅ and it follows for every t ∈ J that there exists an i ∈ {2, 3, …, n} such that h_{i}^{t} ≥ 1 and N_{i}^{t} ≥ 1. By Lemma 5.1 we have for t ∈ J that k_{t}(ψ) = 1, because h_{1}^{t} < ε < a_{1} and h_{1}^{t+1} ≥ 0. We construct a new policy ϕ from policy ψ by changing some of the k_{t}(ψ) in the following way. Let J = {c_{0}, c_{1}, c_{2}, … } with c_{0} < c_{1} < c_{2} < …. We start with k_{t}(ϕ) = k_{t}(ψ) for every t ∈ ℤ_{≥0} and then we do consecutively for s = c_{0}, s = c_{1} , … the following. Let i ∈ {2, 3, …, n} : h_{i}^{s} ≥ 1 and t̃ = max{t < s : k_{t}(ψ) = i}. For the new policy ϕ we take kt̃(ϕ) = 1 = k_{s}(ψ) and k_{s}(ϕ) = i = kt̃(ψ). Then by Lemma 5.7 and induction we have that d_{1}(φ) ≤ d_{1}(ψ) and d_{i}(φ) = d_{i}(ψ) for i = 2, 3, …, n. If d_{1}(φ) < d_{1}(ψ) then S(φ) = ∑_{i=1}^{n} d_{i}(φ) < ∑_{i=1}^{n} d_{i}(ψ) = S(ψ), which contradicts the fact that ψ is an optimal policy. Hence, d_{i}(φ) = d_{i}(ψ) for i = 1, 2, …, n and φ is also an optimal policy. Thus for every t ∈ ℤ_{≥0} we have that

h_{1}^{t}(φ) = d_{1}(ψ) − t · a_{1} + N_{1}^{t}(φ) ≥ d_{1}(ψ) − t · a_{1} + N_{1}^{t}(ψ) = h_{1}^{t}(ψ)

and for every t ∈ J we have that h_{1}^{t}(φ) = h_{1}^{t}(ψ) + 1 ≥ 1. So for every t ≥ t′ we have that h_{1}^{t}(φ) ≥ ε. However, by Lemma 5.6 we have that φ is not an optimal policy, which is a contradiction. □

From Lemma 5.3 , Lemma 5.6 and Theorem 5.8 we have the following property of optimal policies.

Corollary 5.9 If in an (a_{1}, a_{2}, …, a_{n}) system an optimal policy ψ is applied then for all t ∈ ℤ_{≥0}, i ∈ {1, 2, …, n} and ε > 0 there exist t′ ∈ ℤ_{≥0}, t′ > t such that a_{i} · v_{i}^{t′} < ε and a_{j} · v_{j}^{t′} < 1 for all j ≠ i.

If d_{i} < 1 then max(0, ⌈t · a_{i} − d_{i}⌉) = ⌈t · a_{i} − d_{i}⌉ for every t ∈ ℤ_{≥0}. So, to obtain an optimal policy for an (a_{1}, a_{2}, …, a_{n}) system we can, according to Theorem 5.8, solve the following MPP instead of (33).

minimize S  = ∑_{i=1}^{n} d_{i}

subject to:

∑_{i=1}^{n}⌈t · a_{i} − d_{i}⌉ ≤ t for t = 0, 1, …
0 ≤ d_{i} < 1  for i = 1, 2, …, n

(36)

From an optimal solution d_{1}, d_{2}, …, d_{n} of (36) an optimal policy ψ can be obtained by applying the GG algorithm. Further the GG algorithms can be used to search iteratively for better solutions of (36). We now introduce a simple greedy algorithm which in fact is a (special) GG algorithm and thus has the above properties. We denote this algorithm as the SG (Special Greedy) algorithm and in the SG algorithm we completely fix the k_{t}. This in contrary to the GG algorithm, where there is sometimes a freedom in the choice of k_{t}.

SG Algorithm. The servers are ordered such that a_{1} ≥ a_{2} ≥ … ≥ a_{n} and let d_{1}, d_{2}, …, d_{n} ∈ ℝ_{≥0} be given. Then the SG algorithm determines ψ inductively in the following way. Suppose k_{0}(ψ), k_{1}(ψ), …, k_{t−1}(ψ) have been determined. Then k_{t}(ψ) := i ∈ \{1, 2, …, n\} for which \frac{h_{i}^{t}}{a_{i}} is minimal, where h_{i}^{t} = d_{i} − t · a_{i} + N_{i}^{t}(ψ) for i = 1, 2, …, n. In case of a tie the server with the lowest index is chosen.

Proposition 5.10 The SG algorithm is a special GG algorithm.

Proof. For the GG algorithm we have that

q_{i}(t) = min{t′ ∈ ℤ_{≥0} : t′ · a_{i} > d_{i} − t · a_{i} + N_{i}^{t}(ψ)} =

⌊\frac{d_{i} − t · a_{i} + N_{i}^{t}(ψ)}{a_{i}}⌋ + 1 = ⌊\frac{h_{i}^{t}}{a_{i}} ⌋ + 1 for i = 1, 2, …, n.

So, for an i ∈ \{1, 2, …, n\} for which \frac{h_{i}^{t}}{a_{i}} is minimal also q_{i}(t) is minimal. Thus the SG algorithm is a special GG algorithm. □

Now we have the following on the structure of optimal policies. For every (a_{1}, a_{2}, …, a_{n}) system there exists an optimal policy ψ which is obtained by applying the SG algorithm to an optimal solution d_{1}, d_{2}, …, d_{n} of (36). This optimal policy ψ can be represented in the following way. For i ∈ {1, 2, …, n} we represent server i as a point P_{i} on a circle that moves from t = 0 clockwise over the circle with an angular momentum of a_{i} · 2π radians per time unit. So, the angular momentum is directly proportional to the work capacity a_{i} of the server. At t = 0 the point P_{i} starts d_{i} · 2π radians before the top of the circle. Then the order k_{0}(ψ), k_{1}(ψ), … in which the arriving jobs are routed to the servers if policy ψ is applied is the order in which the points representing the servers pass the top of the circle. If several points pass the top of the circle at exactly the same moment then the convention for the SG algorithm is used, namely that the server with the lowest index of the tied servers comes first in order. Such sequences k_{0}(ψ), k_{1}(ψ), … obtained by applying the SG algorithm on d_{1}, d_{2}, … d_{n} where d_{i} < 1 for i = 1, 2, …, n are in the literature known as billiard sequences (see for example [4]). Namely, if a billiard ball bounces in an n - dimensional cube and a sequence of the integers {1, 2, …, n} (the integers correspond to the sides of the cube and opposite sides correspond to the same integer) is constructed by writing down a integer if the ball bounces against the side of the cube corresponding to that integer then such a sequence is a billiard sequence. It is clear that the sequence obtained from the SG algorithm is a billiard sequence for some well chosen initial position and direction of the billiard ball. Observe that in the circle representation the constraints ∑_{i=1}^{n}⌈t · a_{i} − d_{i}⌉ ≤ t of (36) imply that the starting points on the circle corresponding with the d_{i} must be such that the total number of passages through the top of the circle in the time-interval [0, t) is smaller or equal than t for t = 0, 1, . . .. Further remark that for GG algorithms the same representation can be used. The only difference for a GG algorithm is that if for some t_{0} ∈ ℤ_{≥0} several points P_{i_{1}}, P_{i_{2}}, …, P_{i_{k}} pass the top of the circle in the time-interval [t_{0}, t_{0} + 1) then the choice of order of the routing to the corresponding servers i_{1}, i_{2}, …, i_{k} is free.

According to the following theorem the upper bound of Corollary 4.6 is best possible if the work capacities a_{1}, a_{2}, …, a_{n} are linearly independent over ℤ.

Theorem 5.11 If the work capacities a_{1}, a_{2}, …, a_{n} are linearly indepent over ℤ and ψ is a policy such that d_{i} = d_{i}(ψ) ≤ z_{i} for i = 1, 2, …, n with ∑_{i=1}^{n} z_{i} = n − 1 then d_{i} = z_{i} for i = 1, 2, …, n

Proof. Let ε > 0 be an arbitrary small positive number. We have that 1, a_{2}, a_{3}, …, a_{n} are linearly independent over ℤ, because ∑_{i=1}^{n} a_{i} = 1 and a_{1}, a_{2}, …, a_{n} are linearly independent over ℤ. So, according to Kronecker’s theorem on inhomogeneous simultaneous Diophantine approximation, there exist m_{i} ∈ ℤ, t ∈ ℕ such that |t · a_{i} − m_{i} − (z_{i} + \frac{ε}{2})| < \frac{ε}{2} for i = 2, 3 …, n where ε is some positive number less than \frac{1}{n}. Then

t · a_{i} = m_{i} + z_{i} + θ_{i}  (37)

with θ_{i} ∈ (0, ε) for i = 2, 3, …, n. Further

t · a_{1} = t − ∑_{i=2}^{n} t · a_{i} = t − ∑_{i=2}^{n} m_{i} − ∑_{i=2}^{n} z_{i} − ∑_{i=2}^{n} θ_{i} =

t − M_{1} − (n − 1 − z_{1}) + θ_{1} = m_{1} + z_{1} + θ_{1}  (38)

where M_{1} := ∑_{i=2}^{n} m_{i} ∈ ℤ, m_{1} := t − M_{1} − n + 1 ∈ ℤ and θ_{1} := − ∑_{i=2}^{n} θ_{i} ∈ (−δ, 0) with δ = (n − 1) · ε. By Lemma 4.2 we have that t · a_{1} − N_{1}^{t} ≤ d_{1} ≤ z_{1}. Hence by (38) we have m_{1} + z_{1} + θ_{1} − N_{1}^{t} ≤ z_{1} and thus

N_{1}^{t} ≥ m_{1}.  (39)

For i = 2, 3, …, n we have t·a_{i}−N_{i}^{t} ≤ d_{i} ≤ z_{i} by Lemma 4.2. Thus by (37) m_{i}+z_{i}+θ_{i}−N_{i}^{t} ≤ z_{i}. So, N_{i}^{t} ≥ m_{i} + θ_{i} whence

N_{i}^{t} ≥ m_{i} + 1 for i = 2, 3, …, n.  (40)

Because ∑_{i=1}^{n} m_{i} = ∑_{i=1}^{n}(t · a_{i} − z_{i} − θ_{i}) = t − n + 1, we have by (39) and (40) that

t = ∑_{i=1}^{n} N_{i}^{t} ≥ m_{1} + ∑_{i=2}^{n}(m_{i} + 1) = ∑_{i=1}^{n} m_{i} + n − 1 = t.

Hence N_{1}^{t} = m_{1} and N_{i}^{t} = m_{i} + 1 for i = 2, 3, …, n. From N_{1}^{t} = m_{1} and (38) it follows that t · a_{1} − N_{1}^{t} = z_{1} + θ_{1} with θ_{1} ∈ (−δ, 0) where δ can be made arbitrarily small. So, by Lemma 4.2 d_{1} = z_{1}. Analogously it follows that d_{i} = z_{i} for i = 2, 3, …, n. □

Corollary 5.12 If a_{1}, a_{2}, …, a_{n} are linearly independent over ℤ then S̃ = n − 1 and W̃ = \frac{n−1}{2}. In that case all d_{1}, d_{2}, …, d_{n} that fulfill (29) are optimal solutions of (33). If furthermore d_{i} < 1 for i = 1, 2, …, n then those d_{i} are also an optimal solution for (36).

Conjecture 5.13 Let q := dim_{ℚ}(a_{1}ℚ+a_{2}ℚ+…+a_{n}ℚ) be the irrationality degree of a_{1}, a_{2}, …, a_{n}. Then S̃ ≥ \frac{n+q}{2} − 1.

From Theorem 3.2, W̃ ≥ 0 and Corollary 5.12 it follows that the conjecture is true in the extremal cases q = 1 and q = n.

6 The optimal policy in case of rational a_{i}

In this section we consider the case that all the work capacities a_{i} are rational, i.e a_{i} ∈ ℚ for i = 1, 2, …, n. Then there exist T ∈ ℕ, x_{i} ∈ ℕ such that a_{i} = \frac{x_{i}}{T} for i = 1, 2, …, n and gcd(x_{1}, x_{2}, …, x_{n}) = 1. By (2) we have that T = ∑_{i=1}^{n} x_{i} and we denote T as the period of the system, because T has the following property.

Theorem 6.1 T = min{t ∈ ℕ : there exist periodic policies with period t which are optimal }.

Proof. In the previous section we have shown that a policy ψ obtained from applying the SG algorithm to an optimal solution of (36) is optimal and we have given a circle representation for such a policy ψ. From the circle representation it follows that if a_{i} = \frac{x_{i}}{T} then in T time-units the point P_{i} representing server i makes exactly a_{i} · T = x_{i} turns around the circle. So, at t = T the point P_{i} has passed the top of the circle exactly x_{i} times and is at the same place on the circle as where it started at t = 0. Hence, if a_{i} = \frac{x_{i}}{T} for i = 1, 2, …, n then the optimal policy ψ is periodic with period T and from T consecutively arriving jobs exactly x_{i} are routed to server i for i = 1, 2, …, n. In other words for policy ψ we have for all t ∈ ℤ_{≥0} that

k_{t+T} (ψ) = k_{t}(ψ)  (41)

and

N_{i}^{t+T} (ψ) = N_{i}^{t}(ψ) + x_{i} for i = 1, 2, …, n.  (42)

So, indeed there exist optimal policies with period T. We still have to show that there do not exist t′ ∈ ℕ, t′ < T such that optimal policies with period t′ exist.

Suppose there exists an optimal policy ψ′ with period t′ < T. Then there exist m_{i} ∈ ℕ such that for all t ∈ ℤ_{≥0} we have N_{i}^{t+t′}(ψ′) = N_{i}^{t}(ψ′) + m_{i} for i = 1, 2, …, n. Then it follows that

p_{i} = \frac{m_{i}}{t′} for i = 1, 2, …, n.  (43)

Because ψ′ is optimal it follows from Corollary 4.6 that S(ψ′) ≤ n − 1. So, S(ψ′) < ∞ and by Lemma 3.7 we have p_{i} = a_{i} = \frac{x_{i}}{T} for i = 1, 2, …, n. So, by (43) it follows that \frac{m_{i}}{t′} = \frac{x_{i}}{T} and thus x_{i} = \frac{m_{i}·T}{t′} for i = 1, 2, …, n. Because T > t′ there exists a prime number p such that ord_{p}(T) > ord_{p}(t′). Hence we have that

ord_{p}(x_{i}) = ord_{p}(m_{i}) + ord_{p}(T) − ord_{p}(t′) ≥ ord_{p}(T) − ord_{p}(t′) ≥ 1

and thus p|x_{i} for i = 1, 2, …, n. Hence gcd(x_{1}, x_{2}, …, x_{n}) ≥ p > 1, which is a contradiction. □

So, if all the work capacities a_{i} are rational, a_{i} = \frac{x_{i}}{T} with x_{i}, T ∈ ℕ and gcd(x_{1}, x_{2}, …, x_{n}) = 1, then we can restrict to policies ψ for which (41) and (42) hold to obtain optimal policies. We will denote policies for which (41) and (42) hold as proportional periodic (p.p) policies. Observe that a p.p policy ψ is characterized by k_{0}(ψ), k_{1}(ψ), …, k_{T −1}(ψ) and therefore we denote ψ with ψ = (k_{0}(ψ), k_{1}(ψ), …, k_{T −1}(ψ))^{∞}.

Further we will render such a system with rational work capacities as (x_{1}, x_{2}, …, x_{n}) instead of (a_{1}, a_{2}, …, a_{n}). We have the following lemma which states that the performance of p.p policies is invariant under shifts.

Lemma 6.2 For an p.p policy ψ in an (x_{1}, x_{2}, …, x_{n}) system we have that

S(ψ^{t}) = S(ψ) for every t ∈ ℤ_{≥0}.

Proof. For a p.p policy ψ we have that ψ is the same policy as ψ^{mT} for m ∈ ℤ_{≥0}. Hence, S(ψ) = S(ψ^{T}) = S(ψ^{2T}) = … and the lemma follows from Lemma 5.2. □

Moreover, it is convenient to multiply some of the earlier introduced variables with the period T, because we then get integers. If policy ψ is applied to an (x_{1}, x_{2}, …, x_{n}) system then we define for i = 1, 2, …, n the variables

s_{i} = s_{i}(ψ) := T · d_{i}(ψ) = lim_{t→∞} x_{i} · u_{i}^{t}.

We have the following lemma.

Lemma 6.3 If s_{i} < ∞ for i ∈ {1, 2, …, n} then s_{i} = max_{t∈ℤ_{≥0}}(t · x_{i} − T · N_{i}^{t}) and s_{i} ∈ ℤ_{≥0}.

Proof. It is obvious that s_{i} ≥ 0 and (t · x_{i} − T · N_{i}^{t}) ∈ ℤ for all t ∈ ℤ_{≥0}. So, if s_{i} < ∞ then we have by Lemma 4.2 that

s_{i} = d_{i} · T = T · sup_{t∈ℤ_{≥0}}(t · a_{i} − N_{i}^{t}) = max_{t∈ℤ_{≥0}}(t · x_{i} − T · N_{i}^{t}) ∈ ℤ_{≥0}.

□

Because

S · T = T · ∑_{i=1}^{n} d_{i} = ∑_{i=1}^{n} s_{i}  (44)

we have the following corollary. Corollary 6.4 For an (x_{1}, x_{2}, …, x_{n}) system we have

S · T ∈ ℤ_{≥0} if S < ∞.  (45)

Further by Corollary 4.7 and Theorem 3.2 we have the following corollary. Corollary 6.5 For an (x_{1}, x_{2}, …, x_{n}) system we have

2T · W ∈ ℤ_{≥0} if W < ∞.  (46)

Further we have

S̃ · T ∈ ℤ_{≥0}  (47)

and

2T · W̃ ∈ ℤ_{≥0}.  (48)

Moreover the factors 2 in (46) and (48) can be deleted if n is odd. We have for t ∈ ℤ_{≥0} that S^{t} · T = ∑_{i=1}^{n}(a_{i} · T) · v_{i}^{t} = ∑_{i=1}^{n} x_{i} · v_{i}^{t}. It follows that it is convenient to define for t ∈ ℤ_{≥0} and i ∈ {1, 2, …, n} the variables

w_{i}^{t} = x_{i} · v_{i}^{t} which is T times the remaining workload in server i at time t. We note the following properties of w_{i}^{t}: w1 S^{t} · T = ∑_{i=1}^{n} w_{i}^{t}. w2 w_{1}^{0} = w_{2}^{0} = ⋯ = w_{n}^{0} = 0. w3 If t′ = t − 1 and k_{t′} = l, then w_{l}^{t} = w_{l}^{t′} + T − x_{l} and w_{k}^{t} = max(w_{k}^{t′} − x_{k}, 0) = w_{k}^{t′} +

max(−x_{k}, −w_{k}^{t′}) for k ≠ l. w4 w_{i}^{t} ∈ ℤ_{≥0} for i ∈ {1, 2, …, n} and t ∈ ℤ_{≥0}. w5 S^{t} · T − S^{t′} · T = ∑_{k≠l} max(x_{k} − w_{k}^{t′}, 0).

Proof. The properties w1,w2 and w3 are obvious and property w4 follows from w3. So it only remains to prove property w5. We have S^{t} · T − S^{t′} · T =^{1} ∑_{i=1}^{n}(w_{i}^{t} − w_{i}^{t′}) =^{3} T − x_{l} + ∑_{k≠l} max(−x_{k}, −w_{k}^{t′}) =∑_{k≠l}{x_{k} + max(−x_{k}, −w_{k}^{t′})} = ∑_{k≠l} max(x_{k} − w_{k}^{t′}, 0). □

From properties w1 and w4 it follows that S^{t} · T ∈ ℤ_{≥0} for all t ∈ ℤ_{≥0}. If a p.p policy ψ is applied then the w_{i}^{t} have some more interesting properties. To illustrate this we first give an example. We calculate the w_{i}^{t} for the situation that n = 3 , (x_{1}, x_{2}, x_{3}) = (4, 3, 2), so T = 9, and we apply the policy ψ = (1, 2, 1, 3, 2, 1, 2, 1, 3)^{∞}. See Table 1 for the results.

Table 1

\begin{matrix}t & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ k_{t} & 1 & 2 & 1 & 3 & 2 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 3 & 2 & 1 & 2 & 1 & 3 \\ w_{1}^{t} & 0 & 5 & 1 & 6 & 2 & 0 & 5 & 1 & 6 & 2 & 7 & 3 & 8 & 4 & 0 & 5 & 1 & 6 \\ w_{2}^{t} & 0 & 0 & 6 & 3 & 0 & 6 & 3 & 9 & 6 & 3 & 0 & 6 & 3 & 0 & 6 & 3 & 9 & 6 \\ w_{3}^{t} & 0 & 0 & 0 & 0 & 7 & 5 & 3 & 1 & 0 & 7 & 5 & 3 & 1 & 8 & 6 & 4 & 2 & 0 \\ S^{t} · T & 0 & 5 & 7 & 9 & 9 & 11 & 11 & 11 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 \end{matrix}

Table 1 contains all the calculated w_{i}^{t} until the end of the second period. Note that the w_{i}^{t} for t = 8 and t = 17 are the same. It follows that it is not necessary to calculate the w_{i}^{t} for t > 17, because the k_{t} have also period 9. So for all t ≥ 8 we have w_{i}^{t} = w_{i}^{T +t}, or in other words the w_{i}^{t} are periodical with period T = 9 from moment t = 8 on. Further it follows that S^{t} ·T = ∑_{i=1}^{3} w_{i}^{t} is constant from t = 8. In this example S^{t} · T = 12 for all t ≥ 8 and thus S^{t} = \frac{4}{3} for t ≥ 8. So S = \frac{4}{3}. In the next theorem we show that these properties hold generally.

Theorem 6.6 If a p.p policy ψ is applied to an (x_{1}, x_{2}, …, x_{n}) system then for all t ∈ ℤ_{≥T −1} we have S = S^{t}, d_{i}(ψ) = a_{i} · u_{i}^{t}, s_{i}(ψ) = x_{i} · u_{i}^{t},

v_{i}^{t} = v_{i}^{t+T} and w_{i}^{t} = w_{i}^{t+T}  (49)

for i = 1, 2, …, n. Further for all t ∈ {T, 2T, 3T, … } we have

d_{i}(ψ) = a_{i} · v_{i}^{t} and s_{i}(ψ) = w_{i}^{t}.  (50)

Proof. We consider an arbitrary server i. Because a p.p policy is applied we know that in the first period exactly x_{i} jobs are routed to server i. Assume in the first period an arriving job is routed to server i at moments t_{i}^{1}, t_{i}^{2}, …, t_{i}^{x_{i}} with 0 ≤ t_{i}^{1} < t_{i}^{2} < … < t_{i}^{x_{i}} < T. After the first period this is periodically repeated, so the arriving jobs are routed to server i at moments t_{i}^{1} + m · T, t_{i}^{2} + m · T, …, t_{i}^{x_{i}} + m · T with m ∈ ℤ_{≥0}. We first show that from time t = t_{i}^{x_{i}} server i is constantly in use for processing jobs. Let t > t_{i}^{x_{i}} be an arbitrary moment and t_{0} = max(0, t − T). Then exactly x_{i} jobs have been routed to server i in the interval [t_{0}, t) , because a p.p policy is applied and t > t_{i}^{x_{i}}. Since server i could not start earlier than at time t_{0} with the processing of those jobs, server i is busy with those jobs at least until time t_{0} + x_{i} · a_{i}^{−1} = t_{0} + x_{i} · \frac{T}{x_{i}} = t_{0} + T ≥ t. So server i is busy at any arbitrary moment t > t_{i}^{x_{i}},

whence u_{i}^{t_{i}^{x_{i}}} = u_{i}^{t_{i}^{x_{i}}+1} = · · · . Because t_{i}^{x_{i}} ≤ T − 1 for i = 1, 2, …, n, we have for i = 1, 2, …, n that u_{i}^{T −1} = u_{i}^{T} = · · ·. Hence S^{T −1} = S^{T} = ⋯ = S and it follows for all t ∈ ℤ_{≥0}, t ≥ T − 1 that S = S^{t} and d_{i}(ψ) = a_{i} · u_{i}^{t}, s_{i}(ψ) = x_{i} · u_{i}^{t} for i = 1, 2, …, n. Further if t ≥ t_{i}^{x_{i}}, t ∈ ℕ and k_{t} ≠ i, then v_{i}^{t} ≥ 1 and thus w_{i}^{t} ≥ x_{i}. Hence we have by property w3 for t ∈ ℕ, t ≥ t_{i}^{x_{i}} that

\begin{matrix}w_{i}^{t+1} = w_{i}^{t} + T − x_{i} & if k_{t} = i, \\ w_{i}^{t+1} = w_{i}^{t} − x_{i} & if k_{t} ≠ i \end{matrix}

and w_{i}^{t+T} = w_{i}^{t} + x_{i}(T − x_{i}) − (T − x_{i})x_{i} = w_{i}^{t}. This implies that w_{i}^{T +t} = w_{i}^{t}, v_{i}^{T +t} = v_{i}^{t} for i ∈ {1, 2, …, n} and t ≥ T − 1.

Thus v_{i}^{T} = v_{i}^{2T} = v_{i}^{3T} = … and we only have to show that a_{i} · v_{i}^{T} = d_{i}(ψ) for i = 1, 2, …, n to complete the proof. From the proof of Lemma 4.1 we have for t ∈ ℤ_{≥0} and i ∈ {1, 2, …, n} that a_{i} · u_{i}^{t} − a_{i} · v_{i}^{t} = a_{i} · t − N_{i}^{t}(ψ). Hence a_{i} · u_{i}^{T} − a_{i} · v_{i}^{T} = a_{i} · T − N_{i}^{T} (ψ) = 0, because ψ is a p.p policy. So a_{i} · v_{i}^{T} = a_{i} · u_{i}^{T} = d_{i}(ψ) and w_{i}^{T} = T · a_{i} · v_{i}^{T} = T · d_{i}(ψ) = s_{i}(ψ) for i = 1, 2, …, n. □

By Theorem 3.2 we have the following corollary.

Corollary 6.7 If a p.p policy is applied in an (x_{1}, x_{2}, …, x_{n}) system then for all t ∈ ℤ_{≥T −1} we have

W = S^{t} − \frac{n − 1}{2}.

By Theorem 6.6 and Corollary 6.7 we have according to Table 1 in the (4, 3, 2) example that s_{1} = 2, s_{2} = 3, s_{3} = 7 and the long-run average waiting time W equals S^{8} − 1 = \frac{4}{3} − 1 = \frac{1}{3}. We can compute W also in a more direct way. Namely, note that the total waiting time for jobs that arrive consecutively at the moments t_{0}, t_{0} + 1, …, t_{0} + t_{1} with t_{0}, t_{1} ∈ ℤ_{≥0} equals ∑_{t=t_{0}}^{t_{0}+t_{1}} v_{k_{t}}^{t} =

∑_{t=t_{0}}^{t_{0}+t_{1}} \frac{w_{k_{t}}^{t}}{x_{k_{t}}} . If a p.p policy is applied, then it follows from Theorem 6.6 that ∑_{t=t_{0}}^{t_{0}+T −1} \frac{w_{k_{t}}^{t}}{x_{k_{t}}} is independent of t_{0} if t_{0} ≥ T −1. Thus from t = T −1 on the total waiting time of T consecutively arriving jobs is constant if a p.p policy is applied and W can be computed by the formula

T · W = ∑_{t=t_{0}}^{t_{0}+T −1} \frac{w_{k_{t}}^{t}}{x_{k_{t}}} for t_{0} ≥ T − 1.  (51)

In (51) it is convenient to take t_{0} = T, so that the total waiting time of the T jobs that arrive in the second period is computed. If we do so for the (4, 3, 2) example we find that T · W = ∑_{t=9}^{17} \frac{w_{k_{t}}^{t}}{x_{k_{t}}} = \frac{2}{4} + \frac{0}{3} + \frac{3}{4} + \frac{1}{2} +\frac{0}{3} + \frac{0}{4} + \frac{3}{3} + \frac{1}{4} + \frac{0}{2} = 3 (see Table 1). So W = \frac{3}{T} = \frac{1}{3} , as expected.

If a p.p policy ψ is applied in an (x_{1}, x_{2}, …, x_{n}) system then for i ∈ {1, 2, …, n} we put

t_{i} = min{t ∈ ℤ_{≥0} : u_{i}^{t} = lim_{t→∞} u_{i}^{t}}.  (52)

So t_{i} is the moment from which server i has no idle periods anymore and from the proof of Theorem 6.6 follows that t_{i} ∈ {0, 1, …, T − 1} for i = 1, 2, …, n.

Proposition 6.8 If a p.p policy is applied in an (x_{1}, x_{2}, …, x_{n}) system, then for each i ∈ {1, 2, …, n} there exists at least one moment t′ in each period for which w_{i}^{t′} = 0.

Proof. Let i ∈ {1, 2, …, n} be arbitrary. It is clear that w_{i}^{t_{i}} = 0. Further from the proof of Theorem 6.6 it follows that w_{i}^{t+T} = w_{i}^{t} for all t ≥ t_{i}. So, for all m ∈ ℤ_{≥0} we have w_{i}^{t_{i}+m·T} = w_{i}^{t_{i}} = 0. □

For an optimal p.p policy we have the following stronger result.

Theorem 6.9 If an optimal p.p policy is applied in an (x_{1}, x_{2}, …, x_{n}) system, then for each i ∈ {1, 2, …, n} there exists at least one moment t′ in each period such that w_{i}^{t′} = 0 and w_{j}^{t′} ≤ T − 1 for all j ≠ i.

Proof. By property w2 the statement holds for the first period. So, by (49) we only have to proof that for each i ∈ {1, 2, …, n} there exist t′ ∈ {T − 1, T, T + 1, … } such that w_{i}^{t′} = 0 and w_{j}^{t′} ≤ T −1 for all j ≠ i. Let 0 < ε < \frac{1}{T} . Then by Corollary 5.9 there exist t′ ∈ \{T −1, T, T +1, … \} such that a_{i} · v_{i}^{t′} < ε and a_{j} · v_{j}^{t′} < 1 for all j ≠ i. Hence w_{i}^{t′} < T · ε < 1 and w_{j}^{t′} < T for all j ≠ i and from property w4 it follows that w_{i}^{t′} = 0 and w_{j}^{t′} ≤ T − 1 for all j ≠ i. □

At the end of section 4 we said that a GG algorithm may be used to obtain iteratively better policies. In fact it is mainly practical in case of rational a_{i}, because if an obtained policy ψ is a p.p policy we can calculate the d_{i}(ψ) quickly. Namely, in that case we have by Theorem 6.6 that d_{i}(ψ) = a_{i} · v_{i}^{T} for i = 1, 2, …, n and v_{i}^{T} can quickly be determined. So, we want to get p.p policies and we will use the SG algorithm. If we start with a feasible solution d_{1}, d_{2}, …, d_{n} of (33) for which d_{i} < 1 for i = 1, 2, …, n we have no problem since according to (41) and (42) the SG algorithm always yields a p.p policy in that case. On the other hand if the SG algorithm is applied to a feasible solution d_{1}, d_{2}, …, d_{n} of (33) for which d_{i} ≥ 1 for some i = 1, 2, …, n then it is possible that the obtained policy ψ is not a p.p policy. However, it is easily seen that the obtained policy ψ is always ultimately proportional periodic, i.e there exists a t ∈ ℤ_{≥0} such that ψ^{t} is a p.p policy. In this case we think it is best to take d_{1}(ψ^{t}), d_{2}(ψ^{t}), …, d_{n}(ψ^{t}) as new feasible solution of 33 instead of d_{1}(ψ), d_{2}(ψ), …, d_{n}(ψ). Namely, ψ^{t} is a p.p policy and according to Corollary 5.2 we have that policy ψ^{t} is at least as good (and probably better) than policy ψ. We now give an example of obtaining iteratively better policies by using the SG algorithm.

We apply the SG algorithm to an (7, 6, 3, 2, 1) system and we start with the feasible solution d_{1} = d_{2} = … = d_{5} = \frac{18}{19} of (33). Then applying the SG algorithm to this solution yields the policy ψ_{1} := (1, 2, 1, 3, 2, 1, 4, 2, 1, 3, 2, 1, 2, 1, 5, 4, 3, 2, 1)^{∞} and we have d_{1}(ψ_{1}) = \frac{12}{19}, d_{2}(ψ_{1}) = \frac{7}{19}, d_{3}(ψ_{1}) = \frac{10}{19}, d_{4}(ψ_{1}) = \frac{12}{19} and d_{5}(ψ_{1}) = \frac{14}{19}. Next we find the policy ψ_{2} = (2, 1, 3, 2, 1, 4, 1, 2, 3, 1, 2, 1, 2, 5, 1, 4, 3, 2, 1)^{∞} with d_{1}(ψ_{2}) = \frac{12}{19}, d_{2}(ψ_{2}) = \frac{7}{19}, d_{3}(ψ_{2}) = \frac{10}{19}, d_{4}(ψ_{2}) = \frac{11}{19} and d_{5}(ψ_{2}) = \frac{13}{19}. Next we find the policy ψ_{3} = (2, 1, 3, 2, 1, 4, 1, 2, 3, 1, 2, 1, 5, 2, 4, 1, 3, 2, 1)^{∞} with d_{1}(ψ_{3}) = \frac{12}{19}, d_{2}(ψ_{3}) = \frac{7}{19}, d_{3}(ψ_{3}) = \frac{10}{19}, d_{4}(ψ_{3}) = \frac{10}{19} and d_{5}(ψ_{3}) = \frac{12}{19}. Next we find the policy ψ_{4} = (2, 1, 3, 2, 1, 4, 1, 2, 3, 1, 2, 5, 1, 2, 4, 1, 3, 2, 1)^{∞} with d_{1}(ψ_{4}) = \frac{12}{19}, d_{2}(ψ_{4}) = \frac{7}{19}, d_{3}(ψ_{4}) = \frac{10}{19}, d_{4}(ψ_{4}) = \frac{10}{19} and d_{5}(ψ_{4}) = \frac{11}{19}. Finally applying the SG algorithm to this feasible solution of (33) yields again policy ψ_{4} and the iterative process stops. We say that policy ψ_{4} is stable under applying the SG algorithm. However, policy ψ_{4} is not an optimal policy for this system.

Namely, we have found s_{1} = 0, s_{2} = 8 , s_{3} = 18, s_{4} = 6, s_{5} = 15 as an optimal solution of (59). Hence S̃ = \frac{47}{19} for this system, while S(ψ_{4}) = \frac{50}{19}.

If at the beginning of the iterative process a better start solution is used then in general it will take less iterations before a stable policy is obtained and the obtained stable policy will often be better. Therefore it is a good idea to obtain a reasonable good policy and corresponding feasible solution of (33) by some algorithm and then applying the iterative process to this solution. Another idea is to apply the iterative process on several feasible solutions of (33) (which can be obtained by different algorithms) and then see which one yields the best stable policy. In section 8 we will give several algorithms that can be applied to this problem.

For given s_{i} ∈ ℤ_{≥0} with i ∈ {1, 2, …, n} we have that

max(0, ⌈t · a_{i} − d_{i}⌉) = max(0, ⌈t · a_{i} − \frac{s_{i}}{T} ⌉) =

max(0, ⌈\frac{t · x_{i} − s_{i}}{T} ⌉) for all t ∈ ℤ_{≥0}.  (53)

So, by Lemma 6.3 we can solve the following MPP instead of (33) to obtain an optimal policy for an (x_{1}, x_{2}, …, x_{n}) system.

minimize S · T  = ∑_{i=1}^{n} s_{i}

subject to:

∑_{i=1}^{n} max(0, ⌈\frac{t·x_{i}−s_{i}}{T} ⌉) ≤ t for t = 0, 1, …
s_{i}  ∈ ℤ_{≥0} for i = 1, 2, …, n

(54)

If an optimal p.p policy ψ is applied then s_{1} := s_{1}(ψ) = w_{1}^{T}, s_{2} := s_{2}(ψ) = w_{2}^{T}, …, s_{n} := s_{n}(ψ) = w_{n}^{T} is an optimal solution of (54). In fact, by (35), Corollary 5.5 and Theorem 6.6 we have the following lemma.

Lemma 6.10 If an optimal p.p policy is applied then for all t ∈ {T − 1, T, T + 1, … } we have that s_{1} := w_{1}^{t}, s_{2} := w_{2}^{t} , …, s_{n} := w_{n}^{t} is an optimal solution of (54).

By Theorem 6.9 and Lemma 6.10 we have analogously to Theorem 5.8 the following theorem.

Theorem 6.11 For every i ∈ {1, 2, …, n} there exists an optimal solution s_{1}, s_{2}, …, s_{n} of (54) with s_{i} = 0 and s_{j} ≤ T − 1 for all j ≠ i.

Corollary 6.12 For every (x_{1}, x_{2}, …, x_{n}) system we have that

S̃ ≤ n − 1 − \frac{n − 1}{T}.

Proof. From Theorem 6.11 follows that S̃ · T ≤ (n − 1)(T − 1) and thus S̃ ≤ n − 1 − \frac{n−1}{T}. □

The upper bound of Corollary 6.12 is a fraction better than the general upper bound of Theorem 4.6. In Theorem 6.14 we will improve the upper bound a little more in case there exist i ∈ {1, 2, …, n} with gcd(x_{i}, T) > 1.

If s_{i} ≤ T − 1 then for all t ∈ ℤ_{≥0} we have

max(0, ⌈\frac{t · x_{i} − s_{i}}{T} ⌉) = ⌈\frac{t · x_{i} − s_{i}}{T} ⌉.  (55)

Further we have for all t ∈ ℤ_{≥0} and m ∈ ℕ that

⌈\frac{(t + m · T) · x_{i} − s_{i}}{T} ⌉ = m · x_{i} + ⌈\frac{t · x_{i} − s_{i}}{T} ⌉.  (56)

If s_{i} ≤ T − 1 for i = 1, 2, …, n then by (55) and (56) we have for all t ∈ ℤ_{≥0} and m ∈ ℕ that ∑_{i=1}^{n} max(0, ⌈\frac{t·x_{i}−s_{i}}{T} ⌉) ≤ t if and only if ∑_{i=1}^{n}⌈\frac{(t+m·T)·x_{i}−s_{i}}{T} ⌉ ≤ t + m · T. So, by Theorem 6.11 and (55) we can to obtain an optimal policy for an (x_{1}, x_{2}, …, x_{n}) system solve the following MPP instead of (54).

minimize ST = ∑_{i=1}^{n} s_{i}

subject to:

∑_{i=1}^{n}⌈\frac{t·x_{i}−s_{i}}{T} ⌉ ≤ t for t = 0, 1, …, T − 1
s_{i}  ∈ ℤ_{≥0} for i = 1, 2, …, n
s_{i}  ≤ T − 1 for i = 1, 2, …, n

(57)

From an optimal solution s_{1}, s_{2}, …, s_{n} of (57) an optimal p.p policy ψ such that w_{i}^{T} = s_{i}(ψ) = s_{i} for i = 1, 2, …, n can be obtained by applying the SG algorithm to d_{i} = \frac{s_{i}}{T} for i = 1, 2, …, n to determine k_{0}(ψ), k_{1}(ψ), …, k_{T −1}(ψ).

Lemma 6.13 Let s_{1}, s_{2}, …, s_{n} be an optimal solution of (57). Then

gcd(x_{i}, T) | s_{i} for i = 1, 2, …, n.  (58)

Proof. There exists an optimal p.p policy ψ such that s_{i}(ψ) = s_{i} for i = 1, 2, …, n. For every policy it follows from properties w2 and w3 that gcd(x_{i}, T) | w_{i}^{t} for all t ∈ ℤ_{≥0} and i ∈ {1, 2, …, n}. Hence by (50) we have that gcd(x_{i}, T) | w_{i}^{T} = s_{i} for i = 1, 2, …, n. □

Theorem 6.14 For every (x_{1}, x_{2}, …, x_{n}) system we have that

S̃ ≤ n − 1 − \frac{D(x_{1}, x_{2}, …, x_{n})}{T}

with D(x_{1}, x_{2}, …, x_{n}) = ∑_{i=1}^{n} gcd(x_{i}, T) − min_{i∈{1,2,... ,n}} gcd(x_{i}, T).

Proof. Let j ∈ {1, 2, …, n} such that gcd(x_{j}, T) = min_{i∈{1,2,... ,n}} gcd(x_{i}, T). Then by Theorem 6.11 there exists an optimal solution s_{1}, s_{2}, …, s_{n} of (57) for which s_{j} = 0. Further for all i ≠ j we have by Lemma 6.13 that gcd(x_{i}, T)|s_{i} and thus s_{i} ≤ T − gcd(x_{i}, T). Hence

S̃ · T = ∑_{i=1}^{n} s_{i} ≤ ∑_{i≠j}(T − gcd(x_{i}, T) = T · (n − 1) − D(x_{1}, x_{2}, …, x_{n}).

So, S̃ ≤ n − 1 − \frac{D(x_{1},x_{2},... ,x_{n})}{T}. □

We will show that (57) is equivalent to a linear problem with zero-one variables and thus an integer linear problem (ILP). In the sequel we denote for z ∈ ℤ with z (mod T) the integer a ∈ {0, 1, …, T − 1} for which there exists a k ∈ ℤ such that z = a + k · T. Then for all t ∈ ℤ_{≥0}, s_{i} ∈ {0, 1, …, T − 1} we have

∑_{i=1}^{n}⌈\frac{t · x_{i} − s_{i}}{T} ⌉ ≤ t ⇔ ∑_{i=1}^{n} \frac{t · x_{i} − s_{i} + (s_{i} − t · x_{i}) (mod T)}{T} ≤ t ⇔

∑_{i=1}^{n} s_{i} ≥ ∑_{i=1}^{n}{(s_{i} − t · x_{i}) (mod T)}.

So, the following MPP is equivalent to (57).

minimize ST = ∑_{i=1}^{n} s_{i}

subject to:

∑_{i=1}^{n} s_{i}  ≥ ∑_{i=1}^{n}{(s_{i} − t · x_{i}) (mod T)} for t = 0, 1, …, T − 1
s_{i}  ∈ ℤ_{≥0} for i = 1, 2, …, n
s_{i}  ≤ T − 1 for i = 1, 2, …, n

(59)

For i = 1, 2, …, n, t = 0, 1, …, T −1 and j = 0, 1, …, T −1 we put e_{it}(j) = (j −t·x_{i}) (mod T). Further we define for i = 1, 2, …, n and j = 0, 1, …, T − 1 zero-one variables λ_{ij} by

λ_{ij} = \{ \begin{matrix}1 & if s_{i} = j \\ 0 & if s_{i} ≠ j \end{matrix} .

The λ_{ij} correspond to the variables s_{i} of (59). If s_{i} ∈ {0, 1, …, T − 1} for i = 1, 2, …, n then we have ∑_{i=1}^{n} s_{i} = ∑_{i=1}^{n} ∑_{j=0}^{T −1} j · λ_{ij} and

∑_{i=1}^{n}{(s_{i} − t · x_{i}) (mod T)} = ∑_{i=1}^{n} e_{it}(s_{i}) = ∑_{i=1}^{n} ∑_{j=0}^{T −1} e_{it}(j) · λ_{ij} for t = 0, 1, …, T − 1.

Hence, (57) and (59) are equivalent to the following ILP.

minimize ST  = ∑_{i=1}^{n} ∑_{j=0}^{T −1} j · λ_{ij}

subject to:

∑_{i=1}^{n} ∑_{j=0}^{T −1}(e_{it}(j) − j) · λ_{ij} ≤ 0  for t = 0, 1, …, T − 1
∑_{j=0}^{T −1} λ_{ij}  = 1  for i = 1, 2, …, n
λ_{ij}  ∈ {0, 1}  for i = 1, 2, …, n
and j = 0, 1, …, T − 1

(60)

Thus solving this ILP yields an optimal policy in case the a_{i} are rational. By solving the LP - relaxation of (60) we can get a lower bound for S̃ and thus for W̃. The LP - relaxation of (60) is the following LP -problem.

minimize  ∑_{i=1}^{n} ∑_{j=0}^{T −1} j · λ_{ij}

subject to:

∑_{i=1}^{n} ∑_{j=0}^{T −1}(e_{it}(j) − j) · λ_{ij}  ≤  0 for t = 0, 1, …, T − 1
∑_{j=0}^{T −1} λ_{ij}  =  1 for i = 1, 2, …, n
λ_{ij}  ≥  0 for i = 1, 2, …, n
and j = 0, 1, …, T − 1

(61)

Put F_{i} = {0, gcd(x_{i}, T), 2 gcd(x_{i}, T), …, (T − gcd(x_{i}, T))} for i = 1, 2, …, n. Then we have the following theorem.

Theorem 6.15 For every (x_{1}, x_{2}, …, x_{n}) system an optimal solution of (61) is given by

λ_{ij}^{∗} = \{ \begin{matrix}0 & if j ∉ F_{i} \\ \frac{gcd(x_{i},T)}{T} & if j ∈ F_{i} \end{matrix}  (62)

and the value of (61) is

\frac{nT}{2} − \frac{C(x_{1}, x_{2}, …, x_{n})}{2}, where C(x_{1}, x_{2}, …, x_{n}) = ∑_{i=1}^{n} gcd(x_{i}, T).

Proof. Let t ∈ 0, 1, …, T − 1 be fixed. Then for every i ∈ {1, 2, …, n} we have that

{e_{it}(j) : j ∈ F_{i}} = {0, gcd(x_{i}, T), 2 gcd(x_{i}, T), …, (T − gcd(x_{i}, T))} = F_{i}

and thus ∑_{j∈F_{i}} e_{it}(j) = ∑_{j∈F_{i}} j. Hence

∑_{i=1}^{n} ∑_{j=0}^{T −1}(e_{it}(j) − j) · λ_{ij}^{∗} = ∑_{i=1}^{n} ∑_{j∈F_{i}}(e_{it}(j) − j) · \frac{gcd(x_{i}, T)}{T} = ∑_{i=1}^{n} 0 = 0

for t = 0, 1, …. Further for every i ∈ {1, 2, …, n} we have that

∑_{j=0}^{T −1} λ_{ij}^{∗} = ∑_{j∈F_{i}} \frac{gcd(x_{i}, T)}{T} = \frac{T}{gcd(x_{i}, T)} · \frac{gcd(x_{i}, T)}{T} = 1.

Thus (62) is a feasible solution of (61) and the value of this solution is

∑_{i=1}^{n} ∑_{j=0}^{T −1} j · λ_{ij}^{∗} = ∑_{i=1}^{n} ∑_{j∈F_{i}} j · \frac{gcd(x_{i}, T)}{T} = ∑_{i=1}^{n}\{\frac{gcd(x_{i}, T)}{T} · ( ∑_{k=0}^{\frac{T}{gcd(x_{i},T)} −1} k · gcd(x_{i}, T)) =

∑_{i=1}^{n} \frac{gcd(x_{i}, T)}{2} · (\frac{T}{gcd(x_{i}, T)} − 1) = \frac{nT}{2} − \frac{1}{2} · C(x_{1}, x_{2}, …, x_{n}).

We consider the following dual problem of (61).

maximize  ∑_{i=1}^{n} z_{i}

subject to:

∑_{t=0}^{T −1}{(j − e_{it}(j)) · y_{t}} + z_{i} ≤ j for i = 1, 2, …, n
and j = 0, 1, …, T − 1
y_{t}  ≥  0 for t = 0, 1, …, T − 1

(63)

We claim that an optimal solution of (63) is given by

y_{t}^{∗} = \frac{1}{T}  for t = 0, 1, …, T − 1 and
z_{i}^{∗} = \frac{T}{2} − \frac{gcd(x_{i},T)}{2} for i = 1, 2, …, n. (64)

Namely, let i ∈ {1, 2, …, n} be fixed. Then for every j ∈ {0, 1, …, T − 1} we have that

∑_{t=0}^{T −1}(e_{it}(j) · y_{t}^{∗}) ≥ \frac{1}{T} · ∑_{t=0}^{T −1}\{−t · x_{i} (mod T)\} = \frac{gcd(x_{i}, T)}{T} · ∑_{k=0}^{\frac{T}{gcd(x_{i},T)} −1} k · gcd(x_{i}, T) =

\frac{gcd(x_{i}, T)}{2} · (\frac{T}{gcd(x_{i}, T)} − 1) = \frac{T}{2} − \frac{gcd(x_{i}, T)}{2}.

Hence

∑_{t=0}^{T −1}(j − e_{it}(j)) · y_{t}^{∗} + z_{i}^{∗} = j − ∑_{t=0}^{T −1}(e_{it}(j) · y_{t}^{∗}) + \frac{T}{2} − \frac{gcd(x_{i}, T)}{2} ≤ j

for i = 1, 2, …, n and j = 0, 1, …, T − 1. So, (64) is a feasible solution of (63) and the value of this solution is

∑_{i=1}^{n} z_{i}^{∗} = ∑_{i=1}^{n}(\frac{T}{2} − \frac{gcd(x_{i}, T)}{2}) = \frac{nT}{2} − \frac{1}{2} · C(x_{1}, x_{2}, …, x_{n}).

This lower bound for the value of (63) is equal to the earlier obtained upper bound for the value of (61). So, by the duality theorem of linear programming, due to von Neumann, we have that (62) is an optimal solution of (61), (64) is an optimal solution of (63) and the optimal value of both (61) and (63) is \frac{nT}{2} − \frac{1}{2} · C(x_{1}, x_{2}, …, x_{n}). □

By Theorem 6.15 and Theorem 3.2 we have the following lower bound on S̃ and W̃ in case of rational a_{i}.

Corollary 6.16 For every (x_{1}, x_{2}, …, x_{n}) system we have that

S̃ ≥ \frac{n}{2} − \frac{C(x_{1}, x_{2}, …, x_{n})}{2T}  (65)

and

W̃ ≥ \frac{1}{2} − \frac{C(x_{1}, x_{2}, …, x_{n})}{2T}, where C(x_{1}, x_{2}, …, x_{n}) = ∑_{i=1}^{n} gcd(x_{i}, T).  (66)

The lower bounds of Corollary 6.16 can be attained in some cases and in the next section we give a criterion for this. In case of n = 2 the lower bounds of Corollary 6.16 can always be attained.

Corollary 6.17 For every (x_{1}, x_{2}) system the lower bounds of Corollary 6.16 can be attained and we have that S̃ = 1 − \frac{1}{T} and W̃ = \frac{1}{2} − \frac{1}{T}.

Proof. By definition we have that gcd(x_{1}, x_{2}) = 1 and T = x_{1} + x_{2}. Hence gcd(x_{1}, T) = gcd(x_{2}, T) = 1. Hence Corollary 6.16 yields that S̃ ≥ 1 − \frac{1}{T}. By Corollary 6.12 we have that S̃ ≤ 1 − \frac{1}{T}. So, S̃ = 1 − \frac{1}{T}, W̃ = 1 − \frac{1}{T} and every optimal policy attains the lower bounds of Corollary 6.16. □

Remark. By Theorem 6.11 and Corollary 6.17 we have for every (x_{1}, x_{2}) system that both s_{1} = 0, s_{2} = T − 1 and s_{1} = T − 1, s_{2} = 0 are optimal solutions of (57) and in fact it is easily seen that all the optimal solutions of (57) are the pairs of s_{1}, s_{2} ∈ ℤ_{≥0} such that s_{1} + s_{2} = T − 1. Thus there are exactly T optimal solutions of (57) and it is easily seen that every optimal solution corresponds to exactly one optimal p.p policy. Namely, there is never freedom of choice when the GG algorithm is applied to such a solution. So, if ψ is such an optimal p.p policy for an (x_{1}, x_{2}) system then all the optimal policies for that system are given by ψ^{0}, ψ^{1}, …, ψ^{T −1}. Namely, these T shifts of policy ψ are mutually different and by Lemma 6.2 they are all optimal. Thus in an (x_{1}, x_{2}) system all the optimal policies are cyclic shifts of each other.

7 The optimality of regular policies

In this section we will show that to minimize W the applied policy ψ should be as regular (balanced) as possible in some way. We first give some definitions. Let ψ be the applied policy. Then for i ∈ {1, 2, …, n} we define the splitting sequence of the routing to server i

\underline{δ}(i) = (δ_{t}(i))_{t=0}^{∞}, where δ_{t}(i) = \{ \begin{matrix}1 & if k_{t}(ψ) = i \\ 0 & if k_{t}(ψ) ≠ i \end{matrix} .

Further we define the support of this sequence by the set

A(i) := {t ∈ ℤ_{≥0} : δ_{t}(i) = 1}.

Lemma 7.1 Let t^{∗} ∈ ℤ_{≥0} be such that for some i ∈ {1, 2, …, n} and some t ∈ ℤ_{≥0} we have that t^{∗} ≤ t, v_{i}^{t^{∗}} = 0 and u_{i}^{t^{∗}} = u_{i}^{t}. Then

v_{i}^{t} = \frac{1}{a_{i}} · (N_{i}^{t} − N_{i}^{t^{∗}}) − (t − t^{∗}) = \frac{1}{a_{i}} · ∑_{t′=t^{∗}}^{t−1} δ_{t′}(i) − (t − t^{∗}).

Proof. If u_{i}^{t} = u_{i}^{t+1} for t ∈ ℤ_{≥0} then by (25) we have

v_{i}^{t+1} − v_{i}^{t} = \{ \begin{matrix}\frac{1}{a_{i}} − 1 & if k_{t} = i \\ −1 & if k_{t} ≠ i \end{matrix}  (67)

Since u_{i}^{t^{∗}} = u_{i}^{t^{∗}+1} = … = u_{i}^{t} the lemma follows from (67) by induction. □.

For any N ∈ ℕ we mean by an N -block a set of N consecutive non-negative integers. We say that the splitting sequence \underline{δ}(i) is a regular (the term Beatty is also used in the literature) sequence with density p if for every N -block ω we have that ∑_{t∈ω} δ_{t}(i) , the number of ones in the N -block , equals ⌊Np⌋ or ⌈Np⌉. In that case we also say that the corresponding set A(i) is a regular set. We have the following lemma (see e.g [18]).

Lemma 7.2 If \underline{δ}(i) is a regular sequence with density d then A(i) is of the form \{⌊k · \frac{1}{d} +β⌋\}_{k=1}^{∞} for some −1/d ≤ β < 0 or of the form \{⌈k· \frac{1}{d} +β⌉\}_{k=1}^{∞} for some −1−1/d < β ≤ −1. Conversely, if the support is of this form then the corresponding zero-one sequence is a regular sequence.

Corollary 7.3 \underline{δ}(i) is a regular sequence with density d if and only if there exists a θ ∈ ℝ such that δ_{t}(i) = ⌊(t + 1)d + θ⌋ − ⌊td + θ⌋ or δ_{t}(i) = ⌈(t + 1)d + θ⌉ − ⌈td + θ⌉ for t = 0, 1, …

Further we say the splitting sequence is balanced if the number of ones in any two N-blocks differ by at most one. The corresponding set A(i) is then a balanced set. It is obvious that every regular sequence is balanced. The converse is not always true. For example the sequence 1(10)^{∞} is balanced, but not regular. However, in [18] it is shown that the converse is true for periodic sequences and for sequences with irrational density. Further it is shown that every balanced sequence is eventually regular, i.e if the sequence is balanced then there exists a t′ ∈ ℤ_{≥0} such that the sequence coincides with a regular sequence for every integer t ≥ t_{0}.

In general the density of the splitting sequence \underline{δ}(i) is defined as lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} δ_{t}(i) if this limit exists. It is obvious that this is just p_{i}, the fraction of jobs that are routed to server i. Hence, Lemma 3.7 has the following corollary.

Corollary 7.4 Let ψ be a policy applied to an (a_{1}, a_{2}, …, a_{n}) system with W (ψ) < ∞. Suppose that the splitting sequence \underline{δ}(i) is a regular sequence for some i ∈ \{1, 2, …, n\}. Then \underline{δ}(i) is a regular sequence with density d = a_{i}.

In the sequel when we say that the splitting sequence \underline{δ}(i) is regular or balanced for the applied policy ψ in an (a_{1}, a_{2}, …, a_{n}) system then we mean that the sequence is regular or balanced respectively with the appropriate density d = a_{i}.

If for i ∈ \{1, 2, …, n\} the splitting sequence \underline{δ}(i) is regular then the following theorem yields a nice bound for the maximal waiting time of jobs routed to server i.

Theorem 7.5 If for i ∈ \{1, 2, …, n\} the splitting sequence \underline{δ}(i) is regular then v_{i}^{t} < 1 for every t ∈ A(i).

Proof. Suppose that v_{i}^{t} > 0 for some t ∈ A(i) and let t^{∗} = max{t′ < t : v_{i}^{t′} = 0}. Then v_{i}^{t^{∗}} = 0, u_{i}^{t^{∗}} = u_{i}^{t^{∗}+1} = … = u_{i}^{t} and thus v_{i}^{t} = \frac{1}{a_{i}} · ∑_{t′=t^{∗}}^{t−1} δ_{t′}(i) − (t − t^{∗}) by Lemma 7.1. Because \underline{δ}(i) is regular we have that ∑_{t′=t^{∗}}^{t} δ_{t′}(i) ≤ ⌈a_{i} · (t − t^{∗} + 1)⌉ and thus

∑_{t′=t^{∗}}^{t−1} δ_{t′}(i) ≤ ⌈a_{i} · (t − t^{∗} + 1)⌉ − 1 < a_{i} · (t − t^{∗} + 1).

So, v_{i}^{t} < t − t^{∗} + 1 − (t − t^{∗}) = 1. □

Corollary 7.6 If for i ∈ \{1, 2, …, n\} the splitting sequence \underline{δ}(i) is regular then v_{i}^{t} < \frac{1}{a_{i}} for every t ∈ ℤ_{≥0}.

The following lemma implies a bound on the total time a server is idle when the splitting sequence is regular.

Lemma 7.7 If a policy ψ is applied such that for some i ∈ {1, 2, …, n} the splitting sequence \underline{δ}(i) is regular then d_{i}(ψ) ≤ 1.

Proof. Since \underline{δ}(i) is regular we have for every t ∈ ℤ_{≥0} that N_{i}^{t} ≥ ⌊t · a_{i}⌋. Hence by Lemma 4.2 we have that d_{i} ≤ 1. □

If for an (a_{1}, a_{n}, …, a_{n}) system there exists a policy ψ such that for every i ∈ {1, 2, …, n} the splitting sequence \underline{δ}(i) is balanced then we say that the (a_{1}, a_{2}, …, a_{n}) system is balanceable. The policy ψ is then called a balanced policy. Because every balanced sequence is eventually a regular sequence we have for a balanceable system also that there exists a policy ϕ such that for every i ∈ \{1, 2, …, n\} the splitting sequence \underline{δ}(i) is a regular sequence. Namely, one can take ϕ = ψ^{s} for some s ∈ ℤ_{≥0}, s large enough. We define such a policy ϕ to be a regular policy. Observe that for a regular policy the set of regular sets {A(i)}_{i=1}^{n} is an exact cover of ℤ_{≥0}. Therefore it is also said that there exists an exact cover set for balanceable densities (a_{1}, a_{2}, …, a_{n}).

Further if Q is a finite set, a so-called alphabet and I ⊆ ℤ is a subinterval of ℤ then a mapping W : I → Q is called a I - word or just word. Thus a word is a sequence of letters from the alphabet Q. A subword of W is the restriction of W to some interval J ⊆ I. For a finite (sub)word W we denote the length of W by |W |. Further for a letter a ∈ Q the number of a’s in W is denoted by |W |_{a} and the support set of letter a is denoted by S_{a} := {t ∈ I : W (t) = a}. For an I -word W we have that letter a has density d if for any non-decreasing sequence of finite subintervals I_{i} with union I we have that \frac{|I_{i}∩S_{a}|}{|I_{i}|} tends to d. A policy ψ for an (a_{1}, a_{2}, …, a_{n}) system can be identified with a ℤ_{≥0} - word or ℕ - word on the alphabet {1, 2, …, n} by taking W (t) = k_{t}(ψ) for t = 0, 1, … or W (t) = k_{t−1}(ψ) for t = 1, 2, … respectively. In the literature also the terms balanced word, regular word and Beatty word are used. Each of these terms has the obvious meaning. For example a balanced word is a word such that for every letter a ∈ Q it holds for any two finite subwords W and W′ with |W | = |W′| that ||W |_{a} − |W′|_{a}| ≤ 1. Thus a balanced policy corresponds to a balanced word (with the appropriate densities of the letters) and in the same way a regular policy corresponds to a regular (Beatty) word.

Remember that I_{t} = {0, 1, …, t − 1}. For i = 1, 2, …, n and t ∈ ℤ_{≥0} we put A^{t}(i) := A(i) ∩ I_{t}. Note that |A^{t}(i)| = N_{i}^{t}. If lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}} exists for i ∈ \{1, 2, …, n\} then we define

z_{i} := lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}}

as the long-run average waiting time of jobs routed to server i.

Lemma 7.8 If for an (a_{1}, a_{2}, …, a_{n}) system the applied policy ψ is such that

lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}}

exists and is finite for i = 1, 2, …, n then W (ψ) = ∑_{i=1}^{n} a_{i} · z_{i}.

Proof.

W (ψ) = lim sup_{τ→∞} \frac{1}{τ} ∑_{t=0}^{τ−1} v_{k_{t}}^{t} = lim sup_{τ→∞} \frac{1}{τ} ∑_{i=1}^{n} ∑_{t∈A^{τ} (i)} v_{i}^{t} ≤

∑_{i=1}^{n} lim sup_{τ→∞} \frac{1}{τ} ∑_{t∈A^{τ} (i)} v_{i}^{t} ≤ ∑_{i=1}^{n} lim sup_{τ→∞} \frac{∑_{t∈A^{τ} (i)} v_{i}^{t}}{N_{i}^{τ}} = ∑_{i=1}^{n} z_{i} < ∞.

Hence, (19) holds and

W (ψ) = lim_{τ→∞} \frac{1}{τ} ∑_{i=1}^{n} ∑_{t∈A^{τ} (i)} v_{i}^{t} = lim_{τ→∞} ∑_{i=1}^{n} a_{i} ∑_{t∈A^{τ} (i)} \frac{v_{i}^{t}}{N_{i}^{τ}} =

∑_{i=1}^{n} a_{i} · lim_{τ→∞} ∑_{t∈A^{τ} (i)} \frac{v_{i}^{t}}{N_{i}^{τ}} = ∑_{i=1}^{n} a_{i} · z_{i}.

□

If a_{i} = \frac{p}{q} with p, q ∈ ℕ then we say that the routing to server i is proportional periodic with period q if from every q consecutively arriving jobs exactly p jobs are routed to server i.

If the routing to server i is proportional periodic with period q then we have by the argument used in the proof of Theorem 6.6 that server i has no idle periods from some moment t ∈ ℤ_{≥0}, t < q and thus we can define t_{i} as in (52). Then we have the following lemma.

Lemma 7.9 If for some i ∈ {1, 2, …, n} the routing to server i is proportional periodic with period q then we have that t_{i} ∈ ℤ_{≥0}, t_{i} < q, v_{i}^{t_{i}} = 0 and for every t ≥ t_{i} we have that

v_{i}^{t} = \frac{q}{p} · ∑_{t′=t_{i}}^{t_{i}+t−1} δ_{t′}(i) − (t − t_{i})  (68)

and v_{i}^{t+q} = v_{i}^{t}.

Proof. By the arguments used in the proof of Theorem 6.6 it follows that t_{i} ∈ ℤ_{≥0}, t_{i} < q, v_{i}^{t_{i}} = 0. Further u_{i}^{t_{i}} = u_{i}^{t_{i}+1} = . . .. So, by Lemma 7.1 we have that v_{i}^{t} = \frac{q}{p} ·∑_{t′=t_{i}}^{t_{i}+t−1} δ_{t′}(i)−(t−t_{i}) for every t ≥ t_{i}. Hence for every t ≥ t_{i} we have that

v_{i}^{t+q} − v_{i}^{t} = \frac{q}{p} · ∑_{τ=t_{i}+t}^{t_{i}+t+q−1} δ_{τ}(i) − q = \frac{q}{p} · p − q = 0.

□

Corollary 7.10 If a_{i} = \frac{p}{q} and the routing to server i is proportional periodic with period q then lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}} exists and

z_{i} = \frac{1}{p} · ∑_{t∈B^{t′}} v_{i}^{t}  (69)

for any t′ ≥ t_{i}, where B^{t′} = {t′, t′ + 1, …, t′ + q − 1} ∩ A(i). By Lemma 7.8 and Corollary 7.10 we have the following theorem. Theorem 7.11 If a p.p policy ψ is applied to an (x_{1}, x_{2}, …, x_{n}) system then

lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}}

exists and is finite for i = 1, 2, …, n and W (ψ) = ∑_{i=1}^{n} a_{i} · z_{i}. We have the following theorem which gives an explicit formula for the long-run average waiting time of customers routed to some server i if the routing to that server i is regular. Theorem 7.12 If policy ψ is applied to an (a_{1}, a_{2}, …, a_{n}) system such that for some i ∈ \{1, 2, …, n\} the splitting sequence \underline{δ}(i) is a regular sequence then

lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}}

exists. Moreover, if a_{i} = \frac{p}{q} with gcd(p, q) = 1 then z_{i} = \frac{1}{2} − \frac{1}{2p} and if a_{i} is irrational then z_{i} = \frac{1}{2}. Proof. We first treat the case that a_{i} is rational, a_{i} = \frac{p}{q} with gcd(p, q) = 1. Since ⌈q · a_{i}⌉ = ⌊q · a_{i}⌋ = p we have by definition for the splitting sequence \underline{δ}(i) that every q -block contains exactly p ones. Thus the routing to server i is proportional periodic with period q. So, by Corollary 7.10 we have that lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}} exists and (69) holds. Let f : ℤ_{≥0} → ℝ_{≥0} be the function given by f(t) = v_{i}^{t} for t ∈ ℤ_{≥0}. We have for t′ ≥ t_{i} that

z_{i} = \frac{1}{p} · ∑_{t∈B^{t′}} v_{i}^{t} = \frac{1}{p} · ∑_{t∈B^{t′}} f(t).  (70)

Let C = \{0, \frac{1}{p}, …, \frac{p−1}{p}\}. We claim that f maps B^{t′} bijectively to C for t′ ≥ t_{i}. By this claim and (70) we have that

z_{i} = ∑_{k=0}^{p−1} \frac{1}{p} · \frac{k}{p} = \frac{1}{p^{2}} · \frac{1}{2}p · (p − 1) = \frac{1}{2} − \frac{1}{2p}.

Hence, for the rational case it suffices to prove the claim. We first prove that f(t) ∈ C for every t ∈ A(i). By (5), (6) and induction we have that p · v_{i}^{t} ∈ ℤ_{≥0} for every t ∈ ℤ_{≥0}. Further by Theorem 7.5 we have that v_{i}^{t} < 1 for every t ∈ A(i). Hence f(t) = v_{i}^{t} ∈ C for every t ∈ A(i). Since |B^{t′}| = |C| = p it suffices to show that f is injective on B^{t′}. Suppose t_{i} ≤ t_{a} < t_{b} and v_{i}^{t_{a}} = v_{i}^{t_{b}}. Let P = N_{i}^{t_{b}} − N_{i}^{t_{a}}. By (68) we have that \frac{q}{p} · P = t_{b} − t_{a} and thus q · P = p · (t_{b} − t_{a}). Since gcd(p, q) = 1 it follows that there exists a positive integer k such that P = k · p and t_{b} − t_{a} = k · q ≥ q. Because |t_{1} − t_{0}| < q if t_{0}, t_{1} ∈ B^{t′} it follows that f is injective on B^{t′} and the claim is proved. Now we consider the case that a_{i} is irrational. If the routing to server i is according to some arbitrary splitting sequence b = (b_{0}, b_{1}, b_{2}, …) of zeros and ones then it is clear that v_{i}^{t} depends on b_{0}, b_{1}, …, b_{t−1}, but not on b_{t}, b_{t+1}, . . .. We define for t = 1, 2, … the functions f_{t} : {0, 1}^{t} → ℝ_{≥0} by f_{t} = f_{t}(b_{0}, b_{1}, …, b_{t−1}) := v_{i}^{t} if the routing to server i is according to the splitting sequence (b_{0}, b_{1}, …). Further we put f_{0} = 0. It is clear that these functions f_{t} have the following properties:

f_{t}(b_{0}, b_{1}, …, b_{t−1}) ≥ f_{t−1}(b_{1}, b_{2}, …, b_{t−1})  (71)

for every t ∈ ℕ and

f_{t+k}(0, 0, …, 0, b_{0}, b_{1}, …, b_{t−1}) = f_{t}(b_{0}, b_{1}, …, b_{t−1})  (72)

for every k, t ∈ ℕ.

Since \underline{δ}(i) is a regular sequence we have by Corollary 7.3 that there exists a θ ∈ ℝ such that δ_{t}(i) = ⌊(t + 1)a_{i} + θ⌋ − ⌊t · a_{i} + θ⌋ or δ_{t}(i) = ⌈(t + 1)a_{i} + θ⌉ − ⌈t · a_{i} + θ⌉ for t = 0, 1, . . .. We assume that for some θ ∈ ℝ we have that

δ_{t}(i) = ⌊(t + 1)a_{i} + θ⌋ − ⌊t · a_{i} + θ⌋ for t = 0, 1, ….  (73)

Let b_{t}(θ) = ⌊(t + 1)a_{i} + θ⌋ − ⌊t · a_{i} + θ⌋ for t ∈ ℤ. Then we have that

b_{t}(θ) = b_{t}(θ + 1) for every t ∈ ℤ, θ ∈ ℝ  (74)

and

b_{t−m}(θ + m · a_{i}) = b_{t}(θ) for every t, m ∈ ℤ, θ ∈ ℝ.  (75)

If the routing to server i is according to (73) then v_{i}^{t} = f_{t}(b_{0}(θ), b_{1}(θ), …, b_{t−1}(θ)) for every t ∈ ℤ_{≥0}. For t ∈ ℤ_{≥0}, θ ∈ ℝ we define g(θ, t) := f_{t}(b_{0}(θ), b_{1}(θ), …, b_{t−1}(θ)) and g′(θ, t) := f_{t}(b_{−t}(θ), b_{−t+1}(θ), …, b_{−1}(θ)). Then we have by (75) that g(θ, t) = g′(θ + t · a_{i}, t). Further by (74) we have that g(θ, t) and g′(θ, t) are both periodic in θ with period 1. Moreover by (71) we have that g′(θ, t) is non-decreasing in t. Hence g′_{∞}(θ) := lim_{t→∞} g′(θ, t) exists and by Corollary 7.6 we have that 0 ≤ g′_{∞}(θ) ≤ \frac{1}{a_{i}} for every θ ∈ ℝ. Further g′_{∞}(θ) is also periodic in θ with period 1. If the routing to server i is according to (73) for some fixed θ = θ_{0} then we have that

lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} = lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} g(θ_{0}, t) =

lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} g′(θ_{0} + t · a_{i}, t) = lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} g′_{∞}(θ_{0} + t · a_{i}).

Since g′_{∞}(θ) is periodic in θ with period 1 and a_{i} is irrational we have by the ergodic theorem of Weyl and Von Neumann (see for example [15]) that

lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} g′_{∞}(θ_{0} + t · a_{i}) = ∫_{0}^{1} g′_{∞}(θ)dθ.

So, if the routing to server i is according to (73) for some θ ∈ ℝ then lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} = ∫_{0}^{1} g′_{∞}(θ)dθ and in particular lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} exists and is independent of θ. By Lemma 7.7 we have that lim_{t→∞} u_{i}^{t} = \frac{d_{i}}{a_{i}} ≤ \frac{1}{a_{i}}. Further by Corollary 7.6 we have that v_{i}^{t} < \frac{1}{a_{i}} for every t ∈ ℤ_{≥0}. So, v_{i}^{t} −u_{i}^{t} ∈ [−\frac{1}{a_{i}} , \frac{1}{a_{i}}] for every t ∈ ℤ_{≥0} and thus the condition of Lemma 3.5 is satisfied for the considered server i. So, because lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} exists and by Lemma 3.5, we have

that z_{i} = lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}} exists and

z_{i} = lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} − \frac{1}{2a_{i}} + \frac{1}{2} = ∫_{0}^{1} g′_{∞}(θ)dθ − \frac{1}{2a_{i}} + \frac{1}{2}.  (76)

Now we consider the case that for some θ ∈ ℝ we have that

δ_{t}(i) = ⌈(t + 1)a_{i} + θ⌉ − ⌈t · a_{i} + θ⌉ for t = 0, 1, ….  (77)

Then it follows analogously to the case that the routing to server i is according to (73) that lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}} exists and that z_{i} is independent of θ.

Choose a θ ∈ ℝ such that 1, a_{i}, θ are linearly independent over ℤ. Then ⌈t · a_{i} + θ⌉ = ⌊t · a_{i} + θ⌋ + 1 for every t ∈ ℤ_{≥0} and thus

⌈(t + 1)a_{i} + θ⌉ − ⌈t · a_{i} + θ⌉ = ⌊(t + 1)a_{i} + θ⌋ − ⌊t · a_{i} + θ⌋ for t = 0, 1, ….

Hence the routing to server i according to (73) is exactly the same as the routing to server i according to (77) for such θ. So, splitting sequences according to (77) have the same z_{i} as splitting sequences according to (73) and thus (76) also holds for splitting sequences according to (77). Thus lim_{t→∞} \frac{∑_{τ∈A^{t}(i)} v_{i}^{τ}}{N_{i}^{t}} exists if the splitting sequence \underline{δ}(i) is regular and z_{i} is the same for every regular splitting sequence.

To complete the proof it now suffices to show that z_{i} = \frac{1}{2} for a particular regular splitting sequence with density a_{i}. Let the routing to server i be such that N_{i}^{t} = ⌈t · a_{i}⌉ for every t ∈ ℤ_{≥0}. Then we have for the corresponding splitting sequence \underline{δ}(i) that

δ_{t}(i) = N_{i}^{t+1} − N_{i}^{t} = ⌈(t + 1) · a_{i}⌉ − ⌈t · a_{i}⌉ for t = 0, 1, ….

Hence \underline{δ}(i) is according to (77) with θ = 0 and thus \underline{δ}(i) is indeed a regular sequence. By Lemma 4.2 we have for the applied policy ψ that d_{i}(ψ) = 0 and thus u_{i}^{t} = 0 for every t ∈ ℤ_{≥0}. So, by (26) we have for every t ∈ ℤ_{≥0} that

v_{i}^{t} = \frac{N_{i}^{t}}{a_{i}} − t = \frac{⌈t · a_{i}⌉ − t · a_{i}}{a_{i}} .  (78)

Since a_{i} is irrational we can apply the ergodic theorem of Weyl and von Neumann again and by (78) we have that

lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} = lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} \frac{⌈t · a_{i}⌉ − t · a_{i}}{a_{i}} = ∫_{0}^{1} \frac{x}{a_{i}} dx = \frac{1}{2a_{i}} .  (79)

Hence by (76) we have that z_{i} = \frac{1}{2}. □

Remark. For the irrational case we have used the same technique as in the proof of Theorem 3.2 in [3] .

The following Theorem gives a criterion for the attainability of the lower bounds of Corollary 6.16.

Theorem 7.13 If for an (x_{1}, x_{2}, …, x_{n}) system the fractions (\frac{x_{1}}{T} , \frac{x_{2}}{T} , …, \frac{x_{n}}{T}) are balanceable then the lower bounds of Corollary 6.16 can be attained, i.e

S̃ = \frac{n}{2} − \frac{C(x_{1}, x_{2}, …, x_{n})}{2T}  (80)

and

W̃ = \frac{1}{2} − \frac{C(x_{1}, x_{2}, …, x_{n})}{2T}, where C(x_{1}, x_{2}, …, x_{n}) = ∑_{i=1}^{n} gcd(x_{i}, T).  (81)

Moreover, every regular policy attains the lower bounds of Corollary 6.16 and is optimal.

Proof. Let ψ be a regular policy for the system. If for some i ∈ \{1, 2, …, n\} we write a_{i} = \frac{x_{i}}{T} as \frac{p}{q} with gcd(p, q) = 1 then p = \frac{x_{i}}{gcd(x_{i},T)}. Hence by Theorem 7.12 we have that z_{i} = \frac{1}{2} − \frac{gcd(x_{i},T)}{2x_{i}} for i = 1, 2, …, n. So, by Lemma 7.8 we have that

W (ψ) = ∑_{i=1}^{n} a_{i} · z_{i} = \frac{1}{2} · ∑_{i=1}^{n} a_{i} − \frac{∑_{i=1}^{n} gcd(x_{i}, T)}{2T} = \frac{1}{2} − \frac{C(x_{1}, x_{2}, …, x_{n})}{2T}.

Thus ψ attains the lower bounds of Corollary 6.16 and ψ is an optimal policy. □

In fact it holds much more general that a regular policy is optimal if the given (optimized) fractions are balanceable. Namely, in [1] and [3] the following is shown for the more general case of stochastically independent stationary interarrival and service times. Let p be fixed. Then, if you want to route at least a fraction p of the arriving jobs (customers) to a certain server, then the best way to route to that server is according to a regular splitting sequence of density p. More precisely, the authors have shown the following: Let f_{k} = f_{k}(b_{1}, b_{2}, …, b_{k}) : ℤ_{≥0}^{k} → ℝ be a sequence of functions with the following properties:

f_{k} is multimodular on ℤ_{≥0}^{k},  (82)

for every sequence {b_{k}}

f_{k}(b_{1}, b_{2}, …, b_{k}) ≥ f_{k−1}(b_{2}, b_{3}, …, b_{k}) for every k ∈ ℕ,  (83)

For every sequence {b_{k}} there exists a sequence {c_{k}} such that

for every k, m ∈ ℕ, k > m, f_{k}(c_{1}, c_{2}, …, c_{k−m}, b_{1}, b_{2}, …, b_{m}) = f_{m}(b_{1}, b_{2}, …, b_{m}) (84)

and

f_{k}(b_{1}, b_{2}, …, b_{k}) is non-decreasing in b_{i} for i = 1, 2, …, k.  (85)

Then a regular sequence of density p minimizes

lim sup_{N→∞} \frac{1}{N} · ∑_{k=1}^{N} f_{k}(b_{1}, b_{2}, …, b_{k})

among all splitting sequences (b_{1}, b_{2}, …) of density at least p. Moreover, let {T_{k}}_{k∈ℕ} be the sequence of arrival times, with the convention that T_{1} = 0 and the queue is empty at time 0 and let (b_{1}, b_{2}, …) be a splitting sequence of integers, where b_{i} gives the number of customers admitted to the queue at time T_{i}. Further let {τ_{k}} be the sequence of interarrival times and {σ_{k}} the sequence of service times in the server and let E_{σ,τ} denote the expectation w.r.t the service times and interarrival times. Then it is proved in [2] that the functions E_{σ,τ}W_{k}(b_{1}, b_{2}, …, b_{k}), where W_{k}(b_{1}, b_{2}, …, b_{k}) is the workload in the queue at time T_{k} under control sequence (b_{1}, b_{2}, …) have the above properties if {τ_{k}} and {σ_{k}} are stochastically independent stationary sequences. Note that (84) is fulfilled because E_{σ,τ}W_{k}(0, 0, …, 0, b_{1}, b_{2}, …, b_{m}) = E_{σ,τ}W_{m}(b_{1}, b_{2}, …, b_{m}) if k > m. The multimodularity of the workload in case of fixed deterministic interarrival times and service times is explicitly proved in [3] and it follows in particular that the sequence of functions f_{t} that we defined in the proof of Theorem 7.12 have the above properties. So, for our case we have for every server i that routing to server i according to a regular splitting sequence of density a_{i} minimizes lim sup_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} (and also lim sup_{τ→∞} \frac{∑_{t∈A^{τ} (i)} v_{i}^{t}}{N_{i}^{τ}} ), given that at least a fraction a_{i} of the arriving jobs has to be routed to server i. The fact that multimodular functions are minimized by regular sequences originates from [8], in which the optimality of the regular splitting sequence is proved in case of an exponential server queue.

Further we want to note that in [2] it is concluded that not only the regular splitting sequences are optimal, but also the slightly more general balanced sequences if the traffic intensity is less than one. Then namely with probability one the queue becomes empty after some time. In that case only the ” right tail ” of the splitting sequence matters and thus a balanced sequence is just as good as a regular sequence since every balanced sequence is eventually regular. However, in our deterministic case it can happen that a queue never empties after some moment, although the queue is stable. Therefore in our case it can happen that a balanced (but not regular) splitting sequence of a certain density behaves worse than a regular sequence of the same density. For example in case of a_{i} = \frac{1}{2} and thus service time 2, we compare for server i the regular splitting sequence (10)^{∞} with the balanced (but not regular) splitting sequence 1(10)^{∞}. Then for the regular sequence we have that v_{i}^{t} = 0 if t ∈ ℤ_{≥0} is even and v_{i}^{t} = 1 if t ∈ ℤ_{≥0} is odd. Hence lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} = \frac{1}{2} and z_{i} = 0. For the balanced sequence we have that v_{i}^{0} = 0, v_{i}^{t} = 2 for t ∈ ℕ even and v_{i}^{t} = 1 for t ∈ ℕ odd. Hence lim_{τ→∞} \frac{1}{τ} · ∑_{t=0}^{τ−1} v_{i}^{t} = \frac{3}{2} and z_{i} = 1. So, for this example we see for the balanced sequence that indeed the queue never becomes empty after t = 0 and that the balanced sequence is worse than the regular sequence of the same density.

Now we know that if the fractions (a_{1}, a_{2}, …, a_{n}) are balanceable then a policy corresponding to a regular word with these fractions is optimal, the natural question is which sets of fractions (a_{1}, a_{2}, …, a_{n}) with ∑_{i=1}^{n} a_{i} = 1 are balanceable. This problem in general is studied in [2] and [10] and in [7], [14], [18] and [19] and several other papers it is studied for several special cases. See [19] for other references. We mention here some of the results. In case n = 2 every pair of fractions (p, 1 − p) is balanceable. This is easily seen since if a sequence of zeros and ones is balanced with density p then the complementary sequence is ” automatically ” balanced with density 1−p. For the rational case if n = 2 we have seen in Corollary 6.17 that the lower bounds of Corollary 6.16 can be attained and now it follows that the regular policies attain those lower bounds. In the irrational case of n = 2 we have by Corollary 5.12 that W̃ = \frac{1}{2} and it follows by Theorem 7.12 that the regular policies are indeed optimal. So, for n = 2 the problem is completely solved and we know the optimal policies for our queueing system. For n > 2 it is much more complicated. In fact it is then rather rare that a set of fractions is balanceable, especially if most of the fractions are mutually different. If most of the fractions are equal to each other then it is more likely that they are balanceable. For example if they are all equal to \frac{1}{n} or there are only two distinct fractions then they are always balanceable. If they are all equal to \frac{1}{n} then the corresponding regular optimal policy is just the round robin policy which has average waiting time W = 0 for the corresponding (1, 1, …, 1) system. Further if the fractions are balanceable and one of them is irrational then they have to be all irrational and all the regular words in this case are classified in [7]. Note that Conjecture 5.13, Theorem 3.2, Theorem 7.12 and Lemma 7.8 imply that if irrational fractions (a_{1}, a_{2}, …, a_{n}) are balanceable then dim_{ℚ}(a_{1}ℚ + a_{2}ℚ + … + a_{n}ℚ) = 2. This follows indeed from the classification in [7]. Further for n > 2 it is known that if the fractions are distinct then they must be all rational. In fact for every n > 2 there is exactly one set of distinct balanceable fractions known. Namely, the fractions \{\frac{2^{n−1}}{2^{n}−1}, \frac{2^{n−2}}{2^{n}−1}, …, \frac{1}{2^{n}−1}\} corresponding to a (2^{n−1}, 2^{n−2}, …, 1) system. For example for n = 4 the fractions (\frac{8}{15}, \frac{4}{15}, \frac{2}{15}, \frac{1}{15}) are balanceable and (abacabadabacaba)^{∞} is a regular word on the alphabet {a, b, c, d} with those fractions. Hence the corresponding policy (1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1)^{∞} is optimal for an (8, 4, 2, 1,) system. It is natural to make the following conjecture which is known as Fraenkel’s conjecture.

Conjecture 7.14 A set of distinct fractions {a_{1}, a_{2}, …, a_{n}} with n ≥ 3 and ∑_{i=1}^{n} a_{i} = 1 is balanceable if and only if

\{a_{1}, a_{2}, …, a_{n}\} = \{\frac{2^{n−1}}{2^{n} − 1}, \frac{2^{n−2}}{2^{n} − 1}, …, \frac{1}{2^{n} − 1}\}.

For n = 3 the conjecture is proved in [10] and [17] and for n = 4 in [2]. Further in [18] and [19] the conjecture is proved for n = 5 and n = 6. Further in [10] and [17] all the regular words corresponding to the balanceable fractions for n = 3 are classified. The same is done in [10] for n = 4 except for a special case. Namely, not for rational fractions such that for the corresponding (x_{1}, x_{2}, x_{3}, x_{4}) system gcd(x_{i}, T) > 1 for some i ∈ {1, 2, 3, 4}. Finally we remark that a set of fractions (a_{1}, a_{2}, …, a_{n}) is balanceable if and only if there exists a solution d_{1}, d_{2}, …, d_{n} of (36) such that all the inequalities ∑_{i=1}^{n}⌈t · a_{i} − d_{i}⌉ ≤ t for t = 0, 1, … hold with equality. From such a solution if it exists a regular word with the given fractions can be obtained by applying the SG algorithm to the solution.

8 Algorithms to find good policies

For large systems it is hard to find an optimal policy by solving the mathematical programming problem. In this section we will consider some greedy algorithms that can be used to obtain rather good (but not necessarily optimal) policies. We apply these algorithms in the rational case, but they can also be applied to the general case. However, in the rational case the obtained policy ψ will be (ultimately) periodic and W (ψ) can be determined, while in case of irrational a_{i} the performance W (ψ) can only be estimated. Further in the rational case we can try to improve the obtained policy by iteratively using the SG algorithm, as we showed in section 6.

The first greedy algorithm that we consider is based on the fact that to minimize W we have to minimize S. So, when at some time t_{0} ∈ ℤ_{≥0} we have to route the incoming job to a server then it may be a good idea to determine k_{t_{0}} in such a way that S^{t_{0}+1} is minimized. We call an algorithm that follows this rule an OSSM (One Step S Minimalization) algorithm. We have (see property w5 of the w_{i}^{t} for the rational case and the irrational case is similar) that

S^{t_{0}+1} − S^{t_{0}} = ∑_{k≠k_{t_{0}}} max(a_{k} − a_{k} · v_{k}^{t_{0}}, 0).  (86)

So, defining

r_{i}^{t_{0}} = max(a_{i} − a_{i} · v_{i}^{t_{0}}, 0),  (87)

for i ∈ {1, 2 …, n} it follows from (86) that at time t_{0} an OSSM algorithm routes the job to a server l for which

r_{l}^{t_{0}} = max_{i∈{1,2,... ,n}} r_{i}^{t_{0}}.  (88)

Applying this rule we still have to choose to which server the job is routed if r_{i}^{t_{0}} is maximal for several servers i. First we consider the case that r_{1}^{t_{0}} = r_{2}^{t_{0}} = ⋯ = r_{n}^{t_{0}} = 0. Then S^{t_{0}+1} = S^{t_{0}} no matter to which server the job is routed. Therefore in this case we let the algorithm already minimize S^{t_{0}+2} instead of S^{t_{0}+1}. This can be done by redefining the variables r_{i}^{t_{0}} as r_{i}^{t_{0}} = max(2a_{i} − a_{i} · v_{i}^{t_{0}}, 0) and then choose the server for which the new r_{i}^{t_{0}} is maximal. If for the new r_{i}^{t_{0}} it again holds that r_{1}^{t_{0}} = r_{2}^{t_{0}} = ⋯ = r_{n}^{t_{0}} = 0, then the r_{i}^{t_{0}} can be redefined as r_{i}^{t_{0}} = max(3a_{i} − a_{i} · v_{i}^{t_{0}}), etc. Now we still have to consider the case that r_{i}^{t_{0}} is maximal for the servers i_{1}, i_{2}, …, i_{m} with m > 1 and that r_{i_{1}}^{t_{0}} = r_{i_{2}}^{t_{0}} = ⋯ = r_{i_{m}}^{t_{0}} > 0. An OSSM algorithm has to route the job to one of these m servers i_{1}, i_{2}, ⋯, i_{m} and we introduce two variants of the OSSM algorithm, denoted by OSSM1 and OSSM2. If we assume without loss of generality that a_{i_{1}} ≥ a_{i_{2}} ≥ ⋯ ≥ a_{i_{m}} then OSSM 1 routes the job to server i_{1} , the fastest server among them, while OSSM2 routes the job to server i_{m}, the slowest server among them. We only consider these two variants, but other variants are possible. We have the following theorem for every OSSM algorithm.

Theorem 8.1 In case n = 2 a policy ψ obtained by applying an OSSM algorithm is optimal.

Proof. It suffices for both the rational and irrational case to show that S^{t}(ψ) < 1 for every t ∈ ℤ_{≥0}. Namely, then in the rational case we have that S(ψ)·T ≤ T −1 and thus S(ψ) ≤ 1− \frac{1}{T}.

Hence ψ is optimal by Corollary 6.17. For the irrational case it follows that S(ψ) ≤ 1 and thus ψ is optimal by Corollary 5.12. So if ψ is not an optimal strategy then there exists a t_{0} ∈ ℕ such that S^{t_{0}} = a_{1} · v_{1}^{t_{0}} + a_{2} · v_{2}^{t_{0}} ≥ 1, but S^{t_{0}−1} = a_{1} · v_{1}^{t_{0}−1} + a_{2} · v_{2}^{t_{0}−1} < 1. We may assume that k_{t_{0}−1} = 1 without loss of generality. Then S^{t_{0}} = S^{t_{0}−1} + r_{2}^{t_{0}−1} and r_{1}^{t_{0}−1} ≥ r_{2}^{t_{0}−1} > 0. Thus v_{1}^{t_{0}−1} < 1 and v_{2}^{t_{0}−1} < 1. Hence

1 ≤ a_{1} · v_{1}^{t_{0}} + a_{2} · v_{2}^{t_{0}} = a_{1} · v_{1}^{t_{0}−1} + 1 − a_{1} < 1,

which is a contradiction. □

Remarks.

1. In the rational case we can multiply with T as usual and thus the integer numbers (r_{i}^{t_{0}})^{∗} := T · r_{i}^{t_{0}} = max(x_{i} − w_{i}^{t_{0}}, 0) for i = 1, 2, …, n instead of the r_{i}^{t_{0}} could be used when k_{t_{0}} is determined by an OSSM algorithm.

2. Note that the OSSM2 algorithm yields the policy (1, 2, 1, 3, 2, 1, 2, 1, 3)^{∞} for the (4, 3, 2) system that we used in section 6 as example (see Table 1), while the OSSM1 algorithm yields the policy (1, 2, 1, 3, 2, 1, 1, 2, 3)^{∞} for this system.

The next greedy algorithm we consider follows the rule that the incoming job is routed to the server that is the first that can start with the processing of that job. So at time t the algorithm routes the job to a server i for which v_{i}^{t} (or \frac{w_{i}^{t}}{x_{i}} in the rational case) is minimal. If for several servers i_{1}, i_{2}, …, i_{m} it holds that v_{i}^{t} is minimal then the job will be routed to a server which is the fastest of those m servers. So, if those m servers are ordered such that a_{i_{1}} ≥ a_{i_{2}} ≥ … ≥ a_{i_{m}} then the job is routed to server i_{1}. We will denote this as the SWT (Shortest Waiting Time) algorithm. Just as the OSSM algorithms the SWT algorithm gives an optimal policy in case n = 2.

Theorem 8.2 In case n = 2 a policy ψ obtained by applying the SWT algorithm is optimal.

Proof. It suffices again to show that S^{t}(ψ) < 1 for every t ∈ ℤ_{≥0}. We prove this by induction on t. For t = 0 it is obvious. So suppose it holds for t = t′. We may assume that k_{t′} = 1 without loss of generality. Suppose that the induction hypothesis does not hold for t = t′ + 1 and thus S^{t′+1} ≥ 1. Then analogously to the proof of Theorem 8.1 it follows that max(a_{2} − a_{2} · v_{2}^{t′}, 0) = r_{2}^{t′} > 0 and thus v_{2}^{t′} < 1. Because the SWT algorithm is applied we have that v_{1}^{t′} ≤ v_{2}^{t′} < 1. Hence

1 ≤ a_{1} · v_{1}^{t′+1} + a_{2} · v_{2}^{t′+1} = a_{1} · v_{1}^{t′} + 1 − a_{1} < 1,

which is a contradiction. □

Remark. The SWT and the SG algorithm are closely related. Namely, if h_{i}^{t} = a_{i} · v_{i}^{t} for i = 1, 2, …, n then it is clear that the SWT algorithm and the SG algorithm route the job arriving at time t to the same server. In Lemma 5.3 we saw that h_{i}^{t} − a_{i} · v_{i}^{t} is monotonically non-increasing in t and lim_{t→∞}(h_{i}^{t} − a_{i} · v_{i}^{t}) = 0 for i = 1, 2, …, n. So, if ψ is a policy obtained by using the SWT algorithm and φ is the policy obtained by applying the SG algorithm to d_{1}(ψ), d_{2}(ψ), …, d_{n}(ψ) then ψ and φ practically coincide after some time. In the rational case we can say more. Then we have for i = 1, 2, …, n that h_{i}^{t} = a_{i} · v_{i}^{t} for every t ≥ t_{i}, where t_{i} ≤ T − 1. Hence k_{t}(φ) = k_{t}(ψ) for every t ∈ ℤ_{≥t′} for some 0 ≤ t′ ≤ T − 1. In fact in most cases we have that φ = ψ or φ = ψ^{T}. However, if φ′ is the policy obtained by applying the SG algorithm to d_{1}(φ), d_{2}(φ), …, d_{n}(φ) then there might not exist a t ∈ ℤ_{≥0} such that φ′ = ψ^{t}.

The last algorithm we consider is based on the fact that for some server i the splitting sequence \underline{δ}_{i} should be as regular as possible. We denote this algorithm as the GR (Greedy Regular) algorithm. We assume without loss of generality that the servers are ordered such that a_{1} ≥ a_{2} ≥ … ≥ a_{n}. The GR algorithm is such that \underline{δ}(1), the splitting sequence of the routing to server 1, is a regular sequence. Namely, the GR algorithm constructs a policy ψ such that N_{1}^{t}(ψ) = ⌈t · a_{1}⌉ for every t ∈ ℤ_{≥0}. Now \underline{δ}(1) is a regular sequence and we would like the algorithm to construct a policy such that \underline{δ}(2), \underline{δ}(3), … are also regular sequences. However, from the previous section we know that this is in general not possible. Therefore we let the GR algorithm construct a policy ψ such that for every i ∈ {2, 3, …, n} we have the following. Let W be the word on the alphabet {1, 2, …, n} corresponding to policy ψ and W′ be the word on the alphabet {i, i + 1, …, n} obtained from W by omitting the letters 1, 2, …, i − 1. Then the support of letter i in the word W′ is a regular set.

GR Algorithm. Policy ψ is inductively determined in the following way. Suppose k_{0}(ψ), k_{1}(ψ), …, k_{t−1}(ψ) have been determined. Then

k_{t}(ψ) := min\{i ∈ \{1, 2, …, n\} : \frac{a_{i}}{∑_{j=i}^{n} a_{j}} · (1 + ∑_{j=i}^{n} N_{j}^{t}(ψ)) > N_{i}^{t}(ψ)\}.

Remarks.

1. Note that for i = n it always holds that \frac{a_{i}}{∑_{j=i}^{n} a_{j}} · (1 + ∑_{j=i}^{n} N_{j}^{t}(ψ)) > N_{i}^{t}(ψ).

2. The GR algorithm is very similar to Algorithm 2 in [5] which is denoted as the CGRR (Conditional Generalized Round Robin) policy and which is such that

k_{t}(ψ) := min\{i ∈ \{1, 2, …, n\} : \frac{a_{i}}{∑_{j=i}^{n} a_{j}} · ∑_{j=i}^{n} N_{j}^{t}(ψ) ≥ N_{i}^{t}(ψ)\}.

Both algorithms share the property that the routing to server 1 is regular and that for every other server i the routing is regular with respect to the servers with index number ≥ i. These properties are proved in [5]. Further if a_{1}, a_{2}, …, a_{n} are rational then both algorithms construct a p.p policy. It is likely that both algorithms have on average the same performance. The main difference is that for the GR algorithm we have that N_{1}^{t} = ⌈t · a_{1}⌉ for every t ∈ ℤ_{≥0}, while for the CGRR policy N_{1}^{t} = ⌊t · a_{1}⌋ or N_{1}^{t} = ⌈t · a_{1}⌉.

In case n = 2 it is obvious that a policy obtained by the GR algorithm is regular. So, from the previous section we have the following theorem.

Theorem 8.3 In case n = 2 a policy ψ obtained by applying the GR algorithm is optimal.

Example. We apply the OSSM1,OSSM2,SWT and GR algorithm to an (7, 5, 3, 2) system. For these algorithms we give the obtained policy ψ , W (ψ) , the policy ψ′ we get after applying the SG algorithm iteratively to d_{1}(ψ), d_{2}(ψ), d_{3}(ψ), d_{4}(ψ) and W (ψ′). For OSSM1 we get that ψ = 1, 2, 1, 3, 2, 1, 4, 1,(2, 3, 1, 2, 1, 1, 2, 3, 4, 1, 2, 1, 3, 2, 1, 1, 4)^{∞} and W (ψ) = \frac{1}{2}. Further ψ′ = (1, 2, 1, 3, 2, 1, 4, 1, 2, 3, 1, 2, 1, 2, 1, 3, 4)^{∞} and W (ψ′) = \frac{1}{2}. For OSSM2 we get that ψ = 1, 2, 1, 3, 2, 1, 4, 1, 2, 3, 1, 2, 1,(4, 3, 1, 2, 1, 2, 1, 3, 1, 2, 4, 1, 2, 3, 1, 1, 2)^{∞} and W (ψ) = \frac{23}{34}. Further ψ′ = (1, 2, 1, 3, 1, 2, 4, 1, 3, 2, 1, 1, 2, 4, 3, 1, 2)^{∞} and W (ψ′) = \frac{21}{34}. For the SWT algorithm we get that ψ = 1, 2, 3, 1, 4,(2, 1, 3, 2, 1, 1, 2, 4, 3, 1, 2, 1, 2, 1, 3, 4, 1)^{∞} and W (ψ) = \frac{19}{34}. Further ψ′ = (2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 1, 2, 4, 3, 1, 2, 1)^{∞} (note that ψ′ = ψ^{T}) and W (ψ′) = \frac{1}{2}. Finally for the GR algorithm we have that ψ = (1, 2, 1, 3, 1, 2, 3, 1, 2, 1, 4, 2, 1, 3, 1, 2, 4)^{∞} with W (ψ) = \frac{23}{34}. Further ψ′ = (1, 2, 1, 3, 1, 2, 1, 2, 3, 1, 4, 2, 1, 3, 1, 2, 4)^{∞} with W (ψ′) = \frac{23}{34}.

From this example it follows for the rational case that a policy ψ obtained by applying one of the OSSM algorithms or the SWT algorithm is in general not a p.p policy. However, ψ is eventually a p.p policy since the v_{i}^{t} get in a loop. In fact ψ^{T} is always a p.p policy and therefore it suffices to determine k_{t}(ψ) for t = 0, 1, …, 2T − 1 to obtain ψ and W (ψ). It is also possible in the rational case to modify the algorithms such that always a p.p policy is obtained. This can be done by imposing that at moment t ≤ T − 1 the incoming job may not be routed to server i if N_{i}^{t} = x_{i}. In this way we get for the obtained policy ψ that N_{i}^{T} (ψ) = x_{i} for every i ∈ {1, 2, …, n}. Then we determine ψ by ψ := (k_{0}(ψ), k_{1}(ψ), …, k_{T −1}(ψ))^{∞}. Then ψ is a p.p policy and the algorithm can be stopped after k_{0}(ψ), k_{1}(ψ), …, k_{T −1}(ψ) have been determined. Another advantage is that the d_{i}(ψ) and s_{i}(ψ) can be determined by Theorem 6.6 if ψ is a p.p policy. Further the performance of the obtained policy does not change by this modification since the d_{i}(ψ) will not change.

For several systems with rational a_{i} we have calculated the long-run average waiting time W for policies obtained by applying the several algorithms. We denote with W (OS1), W (OS2), W (SW T), W (GR) the long-run average waiting time for the policy obtained by applying the OSSM1, OSSM2, SW T, GR algorithm respectively. In fact we give T ·W (OS1) where T is the period of the system and next to T · W (OS1) we give between parentheses T times the average waiting time of the policy we get after applying the SG algorithm iteratively on the solution of (59) obtained by applying the OSSM1 algorithm. For the other algorithms we do the same. Further for some of those systems we have also determined the optimal long-run average waiting time W̃ in some way. For example by solving (59) or (60) or using the fact that the fractions a_{i} are balanceable, etc. However, for the ”larger” systems we could not do this. Then we denote with ≥ … the lower bound following from Corollary 6.16 for the corresponding system. The results are in Table 2.

Table 2

(x_{1}, x_{2}, …, x_{n})  T  T · W̃ T · W (OS1) T · W (OS2) T · W (SW T) T · W (GR)
(105,84,54)  243  189  201 (189)  189 (189)  189 (189)  207 (195)
(1000,17,5)  1022  954  963 (954)  963 (954)  968 (954)  966 (966)
(10000,66,1)  10067 9850  9851 (9850)  9851 (9850)  9885 (9850) 9899 (9899)
(10000,2,1)  10003 6666  6667 (6666)  6666 (6666)  9996 (9994) 6667 (6667)
(41,41,41,33)  156  75  80 (75)  78 (75)  78 (75)  108 (108)
(59,59,30,25)  173  143\frac{1}{2}  154\frac{1}{2} (143\frac{1}{2}) 154\frac{1}{2} (143\frac{1}{2}) 143\frac{1}{2} (143\frac{1}{2}) 179\frac{1}{2} (179\frac{1}{2})
(118,95,69,35)  317  351\frac{1}{2}  351\frac{1}{2} (351\frac{1}{2}) 351\frac{1}{2} (351\frac{1}{2}) 361\frac{1}{2} (361\frac{1}{2}) 391\frac{1}{2} (384\frac{1}{2})
(1000,13,1,1)  1015 ≥ 503\frac{1}{2} 1238\frac{1}{2} (1170\frac{1}{2}) 1238\frac{1}{2} (1170\frac{1}{2}) 1453\frac{1}{2} (1438\frac{1}{2}) 903\frac{1}{2} (903\frac{1}{2})
(553,447,301,259)  1560 ≥ 777 2022 (1983)  2022 (1983)  2043 (1989) 2094 (2018)
(1000,3,2,1)  1006 ≥ 500  667 (667)  834 (834)  1487 (1480)  668 (667)
(5,4,3,2,1)  15  5  7 (7)  6 (6)  6 (6)  7 (7)
(13,12,9,5,2)  41  31  36 (36)  36 (36)  37 (35)  48 (42)
(1000,513,102,14,3) 1632 ≥ 757 2480 (2431)  2480 (2431)  2585 (2440) 2848 (2677)
(10000,3,3,1,1)  10008 ≥ 4996 7498 (7498)  7498 (7498) 19976 (19964) 7498 (7498)
(7,6,5,4,3,2,1)  28  12  21 (18)  15 (15)  15 (15)  18 (17)
(4,4,4,3,3,3,3)  24  0  12 (12)  12(12)  12(12)  12(12)
(33,33,33,33,33,  269  130  244 (162)  244 (154)  262 (130)  330 (330)

26,26,26,26)

(129,101,98,87,82, 694 ≥ 340 1340 (1274) 1406 (1302) 1332 (1263) 1789 (1402)

61,52,38,29,17)

We make a few remarks about these results. First of all we see that none of these algorithm always yields an optimal policy and further it is also clear that for all these algorithms there exist systems for which this particular algorithm yields a better policy than the other algorithms. Further it seems that the various algorithms always yield a policy ψ with W (ψ) ≤ \frac{n−1}{2} and thus the obtained policies always satisfy the upper bound of Corollary 4.7. By Corollary 5.12 this would imply that these algorithms yield optimal policies in case that the service capacities a_{1}, a_{2}, …, a_{n} are linearly independent over ℤ. Often the GR algorithm yields the worse policy of these algorithms. An explanation is that if the GR algorithm is applied then k_{t}(ψ) only depends on N_{1}^{t}(ψ), N_{2}^{t}(ψ), …, N_{n}^{t}(ψ), but not on the order of the routing of the foregoing jobs. So, the GR algorithm uses less information in choosing the server to which the arriving job is routed than the other algorithms. However, the GR algorithm performances rather good if a_{1} is very large compared to the other fractions a_{2}, a_{3}, …, a_{n}. The reason for this is that the routing to server 1 is regular and thus optimal and most of the arriving jobs are routed to server 1 in this case. So, the routing to the other servers has not much influence on W and thus the GR algorithm yields a rather good policy in such cases. We note that on the contrary the SWT algorithm yields inferior policies if a_{1} is very large compared to the other fractions (see for example the (10000, 3, 3, 1, 1) system), but rather good results if the a_{i}’s have similar size (sometimes even the best result). This can be explained by the fact that for systems with large a_{1} in the beginning the SWT algorithm routes too many arriving jobs to other servers than the fast server 1. Therefore the splitting sequence of server 1, \underline{δ}(1) becomes rather irregular if the SWT algorithm is applied to such systems. It seems even that in general it holds that W (SW T) ↑ \frac{n−1}{2} if a_{1} ↑ 1. We think that the OSSM algorithms on average have the best performance of the considered algorithms. There is in most cases not much difference in the performance of the OSSM1 and OSSM2 algorithm. However, for some systems (see the (1000, 3, 2, 1) system and the same difference occurs for all the (x, 3, 2, 1) systems with x large) a remarkable difference in performance occurs. We notice that applying the SG algorithm iteratively to a solution obtained by one of these algorithm often gives a small improvement. Sometimes the improvement is rather large like in the (33, 33, 33, 33, 33, 26, 26, 26, 26) system for the OSSM algorithms and especially for the SWT algorithm. Moreover it occurs regularly that from a nearly optimal policy an optimal policy can be obtained by using the SG algorithm in this way.

We now discuss an argument for the fact that in general these greedy algorithms and similar greedy algorithms do not yield optimal policies. For this we consider the (4, 4, 4, 3, 3, 3, 3) system with the corresponding balanceable set of fractions (\frac{1}{6}, \frac{1}{6}, \frac{1}{6}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}, \frac{1}{8}). In tables 2 and 3 we see that for this system none of the considered algorithms yields an optimal policy. The reason for this is that a policy obtained by applying such an algorithm always starts with 1, 2, 3, i.e the first three arriving jobs are routed to the three fast servers. In fact it is clear that policies obtained by applying an OSSM algorithm or SWT algorithm have the SFQ (Shorter Faster Queue) property, i.e an arriving job is never routed to some server i if there exist a faster server j (thus a_{i} < a_{j}) for which the remaining workload at that moment is smaller or equal than for server i. However, optimal policies do not always have this property. For example for this system a policy is optimal if and only if it corresponds to a regular word on the alphabet {1, 2, 3, 4, 5, 6, 7} with the above densities for the letters. In [10] the regular words with these densities are classified and it follows that there exist no regular words with these densities which have 1, 2, 3 as subword. Hence policies starting with 1, 2, 3 and policies that have the SFQ property are not optimal for this system. The most obvious regular word and corresponding optimal policy for these fractions is (1, 4, 2, 5, 3, 6, 1, 7, 2, 4, 3, 5, 1, 6, 2, 7, 3, 4, 1, 5, 2, 6, 3, 7)^{∞}, i.e the policy that alternately routes the arriving jobs to the next fast and the next slow server. So, if we put an one for a fast server and a zero for a slow server then this policy corresponds to the regular sequence (10)^{∞} which has density \frac{1}{2} = 3 · \frac{1}{6} which is the fraction of jobs that has to be routed to one of the fast servers. This construction to obtain regular words can be used in general for systems with only two distinct fractions. It is clear that corresponding optimal policies have in general not the SFQ property. Also for systems with fractions that are not balanceable the optimal policies do not always have the SFQ property. For systems in which some of the fractions are equal to each other it seems a good idea to first apply the several algorithms to the altered system in which these fractions are taken together. From the best obtained policy for the altered system a good policy for the original system can be obtained in the same way we just obtained a regular policy for the (4, 4, 4, 3, 3, 3, 3) system. For example for the (10000, 3, 3, 1, 1) system this means that first a good (optimal) policy ψ for the (5000, 3, 1) system is obtained and then from policy ψ follows a policy ψ′ for the original (10000, 3, 3, 1, 1) system.

We conclude that the considered algorithms and similar greedy algorithms yield in general policies that are not optimal. However, by applying the several algorithms and possibly using the SG algorithms iteratively we can obtain good policies quickly by taking the best one obtained. It seems that from the algorithms we considered the OSSM algorithms give in most cases the best result.

Acknowledgement. The author thanks A. Hordijk and R. Tijdeman for their helpful comments.

References

[1] E. Altman, B. Gaujal and A. Hordijk. Admission control in stochastic event graphs, Technical Report 3179, INRIA, 1997. To appear in IEEE Trans. Automat. Control.

[2] E. Altman, B. Gaujal and A. Hordijk. Balanced sequences and Optimal Routing, Technical Report 3180, INRIA, 1997. To appear in J. ACM.

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

[4] P. Arnoux, C. Mauduit, I.Shiokawa and J. Tamura. Complexity of sequences defined by billiards in the cube, Bull. Soc. Math. France 122 (1994), 1-12.

[5] Y. Arian and Y. Levy, Algorithms for generalized round Robin routing, Oper. Res. Lett. 12 (1992), 313-319.

[6] M.B. Combé and O.J. Boxma, Optimization of static traffic allocation policies, Theoret. Comput. Sci. 125 (1994), 17-43.

[7] R. Graham, Covering the positive integers by disjoint sets of the form {[nα + β] : n = 1, 2, … }, J. Combin. Theory Ser. A 15 (1973), 354-358.

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

[9] A. Hordijk, G.M. Koole, J.A. Loeve, Analysis of a customer assignment model with no state information, Probab. Engrg. Inform. Sci. 8 (1994), 419-429.

[10] R. Morikawa, On eventually covering families generated by the bracket function i-v, Bull. Fac. Liberal Arts Nagasaki Univ. 23 no. 1 (1982), 17-22, 24 no. 1 (1983), 1-9, 25 no. 1 (1984), 1-11, 25 no. 2 (1985), 1-8, 26 no. 1 (1985), 15-17, 36 no. 1 (1995), 1-17.

[11] R. Morikawa, Disjoint sequences generated by the bracket function i-vi, Number theory and combinatorics. Japan, 1984. World Sci. Publishing, Singapore (1985), 305-321 and Bull. Fac. Liberal Arts Nagasaki Univ. 26 no. 1 (1985), 1-13, 28 no. 2 (1988), 1-24, 30 no. 1 (1989), 1-10, 32 no. 2 (1992), 181-185, 34 no. 1 (1993), 1-23.

[12] M. Morse and G.A. Hedlund, Symbolic dynamics, Amer. J. Math. 60 (1938), 815-866.

[13] M. Morse and G.A. Hedlund, Symbolic dynamics II - Sturmian trajectories, Amer. J. Math. 62 (1940), 1-42.

[14] J. Simpson, Disjoint covering systems of rational Beatty sequences, Discrete Math. 92 (1991), 361-369.

[15] Y.G. Sinai, Introduction to Ergodic Theory, Princeton University Press, Princeton, N.J. (1976).

[16] S. Stidham, Jr. , A last Word on L = λW, Oper. Res. 22 (1974), 417-421.

[17] R. Tijdeman, On comlementary triples of Sturmian bisequences, Indag. Math. (N.S) 7 (1996), 419-424.

[18] R. Tijdeman, Fraenkel’s conjecture for six sequences, Report W98-24, Leiden University, The Netherlands, 1998. To appear in Discrete Math.

[19] R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, Algebraic Number Theory and Diophantine Analysis, Edited by F. Halter-Koch and R.F. Tichy, Walter de Gruyter, Berlin (2000), 467-483.

[20] T.P. Yum, The design and analysis of a semi-dynamic deterministic routing rule, IEEE Trans. Comm. 29 (1981), 498-504.

D.A van der Laan: Mathematical Institute, Leiden University, P.O. Box 9512, 2300 RA Leiden, The Netherlands; email: dvdlaan@math.leidenuniv.nl