On orders and bounds for multimodular functions

Bruno Gaujal^{∗}  Arie Hordijk ^{†}  Dinard van der Laan ^{‡}

April 15, 2002

Abstract

This paper presents several partial orders which can be used to compare the regularity of a stream of customers entering a system of several queues in parallel (cone order, multimodular order, graph order and unbalance). The different notions are compared and are used to derive upper bounds on the waiting times of customers in parallel queues when such sequences are used as routing policies.

1 Introduction

In several papers ([4, 5]), various attemps have been made in order to study the question which of two deterministic periodic admission sequences (periodic sequences of nonnegative integers) gives the smaller average expected waiting time. A partial order, called the cone order is introduced in [4], and it is shown that the average waiting time and more generally any multimodular function is monotone with respect to the cone order. It is natural to define a multimodular order by requiring that any multimodular function is monotone. In contrast to [11], where the convex order for stochastic admission sequences is used, we consider deterministic admission sequences in this paper. Note that deterministic admission sequences can only be ordered for all multimodular functions if they are equal. Therefore we consider multimodular functions with a fixed minimal point as we did with the cone order. In Section 2 we introduce the multimodular order and we show that the cone order is equivalent to the multimodular order. In Subsection 2.3 the shift invariant counterparts of these orders are studied and it is shown that the regular admission sequence is the minimal point.

For the optimal routing problem to N queues a lower bound is obtained by using regular admission sequences (or what is the same bracket sequences) with ’minimizing’ routing fractions (densities) as admission sequences to all queues (see [3]). But generally only in the routing to N = 2 queues, the routing fractions will be balanceable (see [2]) and only in that case the admission sequences can be glued together and be made to a feasible routing policy.

In Section 5 we derive an upper bound for the difference between the average expected waiting time for customers which are routed to one queue with a given periodic admission sequence which has a fixed routing density, and the lower bound corresponding to the regular admission sequence with the same density. In order to do that, we first introduce a combinatorial notion which we call the unbalance of the admission sequence in Section 3. Roughly speaking it measures its ’distance’ to the regular admission sequence. We show that the unbalance is a shift invariant and multimodular function. In Section 6 we derive an upperbound for the average expected waiting time for a routing policy to N queues as a function of its unbalance. For a routing policy the unbalance is the sum of the unbalances of the induced admission sequences to the queues 1, …, N.

∗ENS Lyon, 46 Allée d’Italie, 69007 Lyon, France. Email: Bruno.Gaujal@ens-lyon.fr

†Dept. of Mathematics, Leiden University, P.O.Box 9512, 2300RA Leiden, The Netherlands.

E-mail: hordijk@math.leidenuniv.nl

‡Dept. of Mathematics, Leiden University, P.O.Box 9512, 2300RA Leiden, The Netherlands.

E-mail: dvdlaan@math.leidenuniv.nl

The difference between the upper and lower bound depends on the average interarrival times but it is insensitive for their distributions and the service time distributions. The upper bound is tight for the heavy traffic situation in which the interarrival and service times are deterministic and the traffic load is 1 for each of the queues. This means that the upper bound is correct for the deterministic heavy traffic case. Clearly, it holds for low traffic that the average expected waiting time is close to the lower bound.

The unbalance is a combinatorial notion and the analysis in this chapter is mainly combinatorial, it turns out that the unbalance is also useful in other models than routing to queues. Indeed, the bounds can be generalized from waiting times to similar bounds for sequences of multimodular functions as in [3] (see the remark at the end of Section 5).

For the definition of the unbalance we introduce in Section 3 the graph order, which gives the distance of a given admission sequence to the bracket sequence and thereby defines its unbalance. The relations between the shift invariant orders and the graph order are studied in Section 5. We show through counterexamples that they are not equivalent. This paper is part of a monograph ([6]), in which the reader can find more details.

2 The multimodular order and the cone order

Let D be a multimodular matrix with rowvectors d_{0}, d_{1}, …, d_{n} ∈ ℝ^{n} verifying d_{0} + … + d_{n} = 0 where d_{1}, d_{2}, …, d_{n} are linearly independent over ℝ and let M_{D} ⊂ ℝ^{n} be the corresponding mesh, that is the set of all the points {a_{0}d_{0} + a_{1}d_{1} + ⋯ + a_{n}d_{n}, a_{i} ∈ ℤ, i = 0, ⋯, n}.

Definition 2.1 A function f : M_{D} → ℝ is D-multimodular if and only if for all a ∈ M_{D}, and for all 0 ≤ i < j ≤ n,

f(a + d_{i}) + f(a + d_{j}) ≥ f(a) + f(a + d_{i} + d_{j}).  (1)

For r ∈ M_{D} let

F(D, r) = {f : M_{D} → ℝ s. t. f is D − multimodular and f(r) = min_{x∈M_{D}} f(x)}

be the set of D-multimodular functions with global minimum point in r.

2.1 The cone order

This section is devoted to the definition of the cone order. More on this can be found in [4].

Definition 2.2 A D-atom is a simplex in ℝ^{n}, made of the n + 1 points

p_{0} = a,
p_{1} = a + d_{ξ(0)},
p_{2} = a + d_{ξ(0)} + d_{ξ(1)}  (2)
⋮
p_{n} = a + d_{ξ(0)} + d_{ξ(1)} + ⋯ + d_{ξ(n−1)}

where a ∈ M_{D} (called the root) and ξ is a permutation of {0, ⋯, n}. This atom will be denoted as S(p_{0}, ⋯, p_{n}).

Theorem 2.3 The set of all the D-atoms forms a triangulation of ℝ^{n}, called a multimodular triangulation.

Proof. Let x be a point in ℝ^{n}. We can write x = α_{0}d_{0} + ⋯ + α_{n}d_{n}, with non-negative coordinates, one of which is 0 since d_{0} + ⋯ + d_{n} = 0. We construct a = ⌊α_{0}⌋d_{0} + ⋯ + ⌊α_{n}⌋d_{n} and ξ such that α_{ξ(i)} − ⌊α_{ξ(i)}⌋ ≥ α_{ξ(i+1)} − ⌊α_{ξ(i+1)}⌋. We define β_{n} = 0, β_{n−1} = α_{ξ(n−1)} − ⌊α_{ξ(n−1)}⌋, β_{i} = α_{ξ(i)} − ⌊α_{ξ(i)}⌋ − (α_{ξ(i+1)} − ⌊α_{ξ(i+1)}⌋). All of them verify 0 ≤ β_{i} ≤ 1 and ∑_{i=0}^{n−1} β_{i} ≤ 1. We have x = a + β_{0}d_{ξ(0)} + ⋯ + β_{n−1}(d_{ξ(0)} + ⋯ + d_{ξ(n−1)}). Therefore, x belongs to the atom with root a and permutation ξ.

Now, assume that a point x belongs to the interior of two different atoms with respective roots a and b and permutations ξ and τ. Since everything is shift invariant, we may assume that b = 0 and τ is the identity. We may write

x = a + α_{0}d_{ξ(0)} + ⋯ + α_{n−1}(d_{ξ(0)} + ⋯ + d_{ξ(n−1)})
= β_{0}d_{0} + ⋯ + β_{n−1}(d_{0} ⋯ + d_{n−1})

with ∑_{i=0}^{n−1} β_{i} ≤ 1 and ∑_{i=0}^{n−1} α_{i} ≤ 1. Since x is in the interior of both atoms, we also have β_{i} > 0 and α_{i} > 0 for i = 0, ⋯, n − 1. Therefore, by uniqueness of the decomposition of x, and writing a = a_{0}d_{0} + ⋯ + a_{n}d_{n},

a_{0} + ∑_{j=ξ^{−1}(0)}^{n−1} α_{ξ(j)} = β_{0} + ⋯ + β_{n−1}

a_{1} + ∑_{j=ξ^{−1}(1)}^{n−1} α_{ξ(j)} = β_{1} + ⋯ + β_{n−1}

⋮
a_{n−1} + ∑_{j=ξ^{−1}(n−1)}^{n−1} α_{ξ(j)} = β_{n−1}

a_{n} + ∑_{j=ξ^{−1}(n)}^{n−1} α_{ξ(j)} = 0.

Since the partial sums of the α_{i} or of the β_{i} are smaller than one and since a_{i} are integer numbers, we have a_{i} = 0 for all i = 0, ⋯, n. Both atoms have the same root.

Now, the equality of the partial sums taken one by one implies first that ∑_{j=ξ^{−1}(n)}^{n−1} α_{ξ(j)} = 0. Since α_{i} > 0 for all i, the only possibility is ξ^{−1}(n) = n.

Considering vectors d_{k} and d_{k+1}, we have:

∑_{j=ξ^{−1}(k)}^{n−1} α_{ξ(j)} − ∑_{j=ξ^{−1}(k+1)}^{n−1} α_{ξ(j)} = β_{k} > 0.

This implies that ξ^{−1}(k) > ξ^{−1}(k+1). Thus ξ is the identical permutation. Therefore, both atoms are equal.

Consider one atom S = S(p_{0}, p_{1}, ⋯, p_{n}) containing r = p_{0} as a vertex (the global minimum point of the multimodular functions considered above). Let ξ and τ be the permutations on {0, ⋯ n} such that τ(0) = 0 and

p_{τ(1)} = r + d_{ξ(0)}  (3)
p_{τ(2)} = p_{τ(1)} + d_{ξ(1)}  (4)
⋮ = ⋮  (5)
p_{τ(n)} = p_{τ(n−1)} + d_{ξ(n−1)}  (6)
r = p_{τ(n)} + s_{ξ(n)}.  (7)

Now, we define for all 1 ≤ i ≤ n, b_{i} = ∑_{j=1}^{i} d_{ξ(j)} and b = (b_{1}, ⋯, b_{n}) the n x n matrix for which the i -th column is vector b_{i}. Note that p_{τ(i)} = r +b_{i} for i = 1, 2, …, n. The cone associated with such an atom S, denoted by C(S), contains all the points x of M_{D} such that x = r + c^{t}(x)b for some non-negative column vector c = c(x) in ℕ_{0}^{n}.

Conversely, for any point x in M_{D}, there exists such a cone containing x and we will have x = r + c^{t}(x)b, where the columns of b corrsponding to the support of c(x) are uniquely defined. We shall denote d(r, x) = c_{1}(x) + ⋯ + c_{n}(x) and call it the cone-distance from x to r.

It is easilly seen that there are (n + 1)! atoms with root in r and thus there are exactly (n + 1)! cones corresponding to the given multimodular matrix D and root r. Let C = {C_{i}}_{i=1}^{(n+1)!} be the set of cones corresponding to D and root r = (0, 0, …, 0) (the origin). Note that from the preceding argument and Theorem 2.3 it follows that {∪C_{i} : C_{i} ∈ C} = ℝ^{n}. For C_{i} ∈ C let C′_{i} be the intersection of C_{i} and M_{D}. In the following proposition which follows directly from the definitions and preceding results we elucidate the properties of the objects we have associated to a multimodular matrix D with rowvectors d_{0}, d_{1}, …, d_{n} ∈ ℝ^{n}.

Proposition 2.4 Let C_{i} ∈ C. Then there exist b_{1}, b_{2}, …, b_{n} ∈ ℝ^{n} and a bijection σ : {1, 2, …, n+ 1} → {0, 1, …, n} such that

1. b_{1}, b_{2}, …, b_{n} are linearly independent.

2. b_{j} = ∑_{i=1}^{j} d_{σ(i)} for j = 1, 2, …, n.

3. C_{i} = {∑_{i=1}^{n} λ_{i} · b_{i} : λ_{i} ≥ 0 for i = 1, 2, …, n}.

4. M_{D} = {∑_{i=1}^{n} λ_{i} · b_{i} : λ_{i} ∈ ℤ for i = 1, 2, …, n}.

5. C′_{i} = {∑_{i=1}^{n} λ_{i} · b_{i} : λ_{i} ∈ ℤ_{≥0} for i = 1, 2, …, n}.

For a convex cone C ⊂ ℝ^{n} we say that a set of vectors v_{1}, v_{2}, …, v_{k} are generators of C if v_{1}, v_{2}, …, v_{k} are linearly independent and C = {∑_{i=1}^{k} λ_{i} · v_{i} : λ_{i} ≥ 0 for i = 1, 2, …, k }. In that case we say that C is a k - dimensional cone. In particular we have for b_{1}, b_{2}, …, b_{n} as in Proposition 2.4 that they are generators of the n -dimensional convex cone C_{i}.

Definition 2.5 For x, y ∈ M_{D} we denote x ≤_{C} y if there exists some cone C_{i} ∈ C, with generators b_{1}, b_{2}, …, b_{n}, such that x, y ∈ C_{i} and c(x) ≤ c(y) component-wise in cone C_{i}.

If x ≤_{C} y then we say that x and y are cone ordered and ≤_{C} is called the cone order.

2.2 The multimodular order and the cone order

Definition 2.6 Let the multimodular matrix D and global minimum point r ∈ M_{D} be given. Then for x, y ∈ M_{D} we say that x ≤_{mm} y if f(x) ≤ f(y) for every f ∈ F(D, r).

It is easy to verify that both the multimodular order ≤_{mm} and the cone order ≤_{C} are reflexive, antisymmetric and transitive and thus they are partial orders on M_{D}. The following theorem says that these partial orders on M_{D} are equivalent.

Theorem 2.7 For given multimodular matrix D and global minimum point r ∈ M_{D} we have for x, y ∈ M_{D} that x ≤_{mm} y if and only if x ≤_{C} y.

First we prove that x ≤_{C} y implies x ≤_{mm} y. We have that x and y are in the same cone C and let b_{1}, ⋯, b_{n} be the generators of this cone.

Note that we can assume for x ≤_{C} y that d(x, y) :=| d(r, y) − d(r, x) |= 1. If not, then we prove step by step along the path from x to y along the direction of the generators, say x = x_{1} ≤_{C} ⋯ ≤_{C} x_{m} = y that f(x) = f(x_{1}) ≤ ⋯ ≤ f(x_{m}) = f(y) for f ∈ F(D, r). The proof will now proceed by induction on d(r, x). The property is true if d(x, r) = 0, since r is the argmin of f on S. Now, assume d(x, r) ≥ 1. Pick a point z in cone C such that x = z + b_{i}. (equivalently, we have c(y) + e_{i} = c(x) and c(y) ≤ 0). Note that d(z, r) = d(x, r) − 1 and z ≤_{C} x. By induction, this means f(z) ≤ f(x). Since d(x, y) = 1, there exists some j such that y = x + b_{j}. Now we have two cases.

• If i = j, then by convexity of f,

f(z + b_{i}) − f(z) ≤ f(z + b_{i} + b_{i}) − f(z + b_{i}).

We also know by induction that f(z + b_{i}) − f(z) ≥ 0. Thus f(x) ≤ f(y).

• If i ≠ j, then we choose yet another point, w, such that w = z + b_{j}. We may assume that i > j (the case j < i is similar by inverting the role played by b_{i} and b_{j} in the following).

Since b_{i} is a sum of base vectors, it is also a sum of opposites of base vectors, since all base vectors add up to 0. Note that all these base vectors are distinct from the base vectors involved in b_{j}.

We have:

b_{j} = d_{ξ(1)} + ⋯ + d_{ξ(j)},  (8)
b_{i} = −d_{ξ(i+1)} − d_{ξ(i+2)} − ⋯ − d_{ξ(n+1)}.  (9)

Therefore, by the multimodularity of f,

f(w)−f(z) = f(x+d_{ξ(1)}+⋯+d_{ξ(j)}+d_{ξ(i+1)}+⋯+d_{ξ(n+1)})−f(x+d_{ξ(i+1)}+⋯+d_{ξ(n+1)}) ≤

f(x + d_{ξ(1)} + ⋯ + d_{ξ(j)}) − f(x) = f(y) − f(x).

Since d(r, w) = d(r, z) + 1, we have f(w) − f(z) ≥ 0 by induction. Thus f(y) − f(x) ≥ 0.

To finish the proof of Theorem 2.7 we have to show that x ≤_{mm} y implies that x ≤_{C} y. By translation we can assume without loss of generality that the global minimum point r = (0, 0, …, 0) ∈ M_{D}. Let b_{1}, b_{2}, …, b_{n} be the generators of the cone C_{i} ∈ C as in Proposition 2.4. If x ∈ M_{D} then we have by Proposition 2.4 that there exist unique x_{j} ∈ ℤ such that x = ∑_{j=1}^{n} x_{j} ·b_{j}. Moreover, for x = ∑_{j=1}^{n} x_{j} · b_{j} ∈ ℝ^{n} we say that supp_{i}(x) = {k ∈ {1, 2, …, n} for which x_{k} > 0}. Note that we assume for k ∈ supp_{i}(x) not only that x_{k} ≠ 0 but that x_{k} > 0 which is stronger than in the standard definition of support. For k = 1, 2, …, n we define the function f_{k} : M_{D} → ℤ_{≥0} by

f_{k}(x) = max(x_{k}, 0).  (10)

Proposition 2.8 For every k ∈ {1, 2, …, n} the function f = f_{k} is D -multimodular with global minimum point in r = 0.

Proof. Since f(x) ≥ 0 for every x ∈ M_{D} and f(r) = 0 it follows that r is a global minimum point of f. It remains to prove that f is a D -multimodular function. So, we have to show that for every x ∈ M_{D}, i, j ∈ {0, 1, …, n} with i ≠ j it holds that

f(x + d_{i}) + f(x + d_{j}) ≥ f(x) + f(x + d_{i} + d_{j}).  (11)

According to property 2 of Proposition 2.4 there exists a bijection σ : {1, 2 …, n + 1} → {0, 1, 2, …, n} such that b_{j} = ∑_{i=1}^{j} d_{σ(i)} for j = 1, 2, …, n. From this it follows that d_{σ(1)} = b_{1}, d_{σ(j)} = b_{j} − b_{j−1} for 2 ≤ j ≤ n and d_{σ(n+1)} = − ∑_{i=1}^{n} d_{σ(i)} = −b_{n}. Put l = σ(k), m = σ(k + 1). If i ∉ {l, m} and j ∉ {l, m} then we have for every x ∈ M_{D} that f(x + d_{i}) = f(x + d_{j}) = f(x) = f(x + d_{i} + d_{j}). Hence (11) holds . Suppose that i ∈ {l, m} and j ∉ {l, m}. Then we have for every x ∈ M_{D} that f(x + d_{i}) = f(x + d_{i} + d_{j}) and f(x + d_{j}) = f(x) and thus (11) holds. Suppose that {i, j} = {l, m} and assume without loss of generality that i = l and j = m. If f(x) > 0 then it follows that f(x + d_{i}) = f(x) + 1, f(x + d_{j}) = f(x) − 1 , f(x + d_{i} + d_{j}) = f(x) and thus (11) holds.

If f(x) = 0 then it follows that f(x + d_{i}) ≥ f(x), f(x + d_{j}) = f(x + d_{i} + d_{j}) = f(x) = 0 and thus (11) holds. So, we can conclude that (11) holds in every case and thus f ∈ F(D, r).

For i = 1, 2, …, (n + 1)! let G(C_{i}) be the set of functions {f_{1}, f_{2}, …, f_{n}} for cone C_{i} and let G = ∪_{i=1}^{(n+1)!}G(C_{i}). We have the following corollaries of Proposition 2.8.

Corollary 2.9 For given multimodular matrix D and global minimum point r = (0, 0, …, 0) ∈ ℝ^{n} we have that G ⊆ F(D, r).

Corollary 2.10 If x, y ∈ M_{D}, x ≤_{mm} y and there exists some cone C_{i} ∈ C such that x, y ∈ C_{i} then x ≤_{C} y.

Proof. Let b_{1}, b_{2}, …, b_{n} be the generators of cone C_{i} as in proposition 2.4 and put x = ∑_{i=1}^{n} x_{i}· b_{i} and y = ∑_{i=1}^{n} y_{i} · b_{i}. Then we have by Proposition 2.4 that x_{i}, y_{i} ∈ ℤ_{≥0} for i = 1, 2, …, n. So, for f_{k} ∈ G(C_{i}) we have that f_{k}(x) = x_{k} and f_{k}(y) = y_{k} for k = 1, 2, …, n. Hence by Proposition 2.8 and x ≤_{mm} y we have that 0 ≤ x_{k} = f_{k}(x) ≤ f_{k}(y) = y_{k} for k = 1, 2, …, n. Thus x ≤_{C} y.

Corollary 2.11 If x, y ∈ M_{D}, x ≤_{mm} y then supp_{i}(x) ⊂ supp_{i}(y) for i = 1, 2, …, (n + 1)!.

Corollary 2.11 can be proved in the same way as Corollary 2.10. The following corollary follows immediately from Corollary 2.10 and Corollary 2.11.

Corollary 2.12 If x, y ∈ M_{D}, x ≤_{mm} y and there exists some cone C_{i} ∈ C such that x is an interior point of C_{i} then x ≤_{C} y.

To prove Theorem 2.7 it suffices by Corollary 2.10 to prove that there exists some cone C_{i} ∈ C such that x, y ∈ C_{i} if x ≤_{mm} y. If x = r = 0, y = r = 0 or y = λ · x with λ > 0 then it follows directly that x, y ∈ C_{i} for some C_{i} ∈ C. Suppose that y = λ·x with λ < 0 and x ≠ r. Let C_{i} ∈ C be a cone containing x with generators b_{1}, b_{2}, …, b_{n}. Then x = ∑_{i=1}^{n} x_{i}·b_{i} and y = ∑_{i=1}^{n} λ·x_{i}·b_{i} with x_{i} ≥ 0 for i = 1, 2, …, n. Moreover we have that x_{k} > 0 for some k ∈ {1, 2, …, n} since x ≠ r. Then for f_{k} ∈ G(C_{i}) we have that f_{k}(x) = x_{k} > 0 and f_{k}(y) = 0, which contradicts x ≤_{mm} y. So, we can assume that x and y are linearly independent vectors in ℝ^{n} and let H := span(x, y) the two dimensional subspace that contains x and y. For C_{j} ∈ C let C_{j}^{∗} be the intersection of C_{j} and H. Then we have that the C_{j}^{∗} are convex cones of dimension smaller or equal than two in the subspace H. To prove Theorem 2.7 we have the following lemmas.

Lemma 2.13 Suppose that C_{i}^{∗} = C_{i} ∩ H is a two dimensional cone generated by u and v. Then supp_{i}(u) is not a subset of supp_{i}(v) and supp_{i}(v) is not a subset of supp_{i}(u).

Proof. Let b_{1}, b_{2}, …, b_{n} be the generators of C_{i} as in proposition 2.4. Then u = ∑_{k∈supp_{i}(u)} u_{k}· b_{k} with u_{k} > 0 and v = ∑_{k∈supp_{i}(v)} v_{k} ·b_{k} with v_{k} > 0. For a small positive number ε we have that w := v − ϵ · u ∈ H and if supp_{i}(u) ⊆ supp_{i}(v) then it is easily seen that w = ∑_{k∈supp_{i}(v)} w_{k} · b_{k} with w_{k} > 0 and thus w ∈ C_{i}^{∗}. However, w ∈ C_{i}^{∗} contradicts the fact that u and v are generators of C_{i}^{∗}. If supp_{i}(v) ⊆ supp_{i}(u) we get a contradiction similarly.

Lemma 2.14 Let u, v, w ∈ H with u, v linearly independent and u, w linearly independent. Let A_{1} be the two dimensional cone generated by u and v, A_{2} the two dimensional cone generated by u and w and A_{3} the one dimensional cone generated by u. Let w = a_{1} ·u+a_{2} ·v. Then A_{1} ∩A_{2} = A_{3} if and only if a_{2} < 0.

Proof. It is obvious that A_{3} ⊆ A_{1} ∩ A_{2}. Let x = ν · u + w, where ν ≥ max(−a_{1}, 0). Then it is easily seen that x ∈ A_{2} \ A_{3}. It follows that x = (ν + a_{1}) · u + a_{2} · v and thus x ∈ A_{1} ∩ A_{2} if a_{2} ≥ 0. So, A_{1} ∩ A_{2} = A_{3} implies that a_{2} < 0. Conversely, suppose that

x′ = λ · u + λ′ · w ∈ A_{1} ∩ A_{2}.

Since x′ ∈ A_{2} we have that λ ≥ 0 and λ′ ≥ 0. Moreover,

x′ = λ · u + λ′ · (a_{1} · u + a_{2} · v) = (λ + λ′ · a_{1}) · u + λ′ · a_{2} · v

and since x′ ∈ A_{1} it follows that λ′ · a_{2} ≥ 0. Thus if a_{2} < 0 then λ′ = 0 and x′ ∈ A_{3}. We are now ready to finish the proof of Theorem 2.7 Proof. We have that ∪_{i=1}^{(n+1)!}C_{i}^{∗} = H since ∪_{i=1}^{(n+1)!}C_{i} = ℝ^{n}. Therefore one of the following

two cases holds:

1. There exists some two dimensional cone C_{i}^{∗} such that in the subspace H we have that x is in the interior of cone C_{i}^{∗}.

2. There exist two dimensional cones C_{i}^{∗}, C_{j}^{∗} such that in the subspace H we have that x is on the boundary of C_{i}^{∗}, x is on the boundary of C_{j}^{∗} and x is in the interior of C_{i}^{∗} ∪ C_{j}^{∗}.

Suppose we have case 1 and let a and b be generators of the cone C_{i}^{∗}. Then a, b ∈ C_{i} and x = λ · a + μ · b with λ, μ > 0. Hence x ∈ C_{i} and supp_{i}(x) = supp_{i}(a) ∪ supp_{i}(b). Suppose that y ∉ C_{i}^{∗}. Then y = y_{1} · a + y_{2} · b with min(y_{1}, y_{2}) < 0 and suppose without loss of generality that y_{1} < 0. According to Lemma 2.13 there exist k ∈ supp_{i}(a) \ supp_{i}(b). Then it follows that k ∉ supp_{i}(y), k ∈ supp_{i}(x). Thus supp_{i}(x) is not a subset of supp_{i}(y), but this contradicts Corolary 2.11. Hence y ∈ C_{i}^{∗} and thus x, y ∈ C_{i}. According to Corollary 2.10 it follows that x ≤_{C} y.

Suppose we have case 2. Then there exist a, b ∈ H such that x and a are generators of cone C_{i}^{∗} and x and b are generators of cone C_{j}^{∗}. Let u_{1}, u_{2}, v_{1}, v_{2} be such that y = u_{1} · x + u_{2} · a = v_{1} · x + v_{2} · b. If u_{1} < 0 then it follows analogously to the proof in case 1 that supp_{i}(x) is not a subset of supp_{i}(y), which yields a contradiction again. Thus u_{1} ≥ 0 and analogously it follows that v_{1} ≥ 0. We will prove that y ∈ C_{i}^{∗} ∪ C_{j}^{∗}. Suppose that y ∉ C_{i}^{∗}. Then it follows that u_{2} < 0. Let a_{1}, a_{2} be such that a = a_{1} · x + a_{2} · b. By Lemma 2.14 we have that a_{2} < 0. Then y = (u_{1} +u_{2} ·a_{1})x+(u_{2} ·a_{2})b. Hence v_{2} = u_{2} ·a_{2} > 0. Thus y ∈ C_{j}^{∗} if y ∉ C_{i}^{∗} and thus y ∈ C_{i}^{∗} ∪C_{j}^{∗}. Since x ∈ C_{i}^{∗} ∩ C_{j}^{∗} it follows that x, y ∈ C_{i} or x, y ∈ C_{j}. Hence x ≤_{C} y by Corollary 2.10.

2.3 Shift invariant counterparts

We consider sequences (of nonnegative integers) of a given length T ∈ ℕ and given sum S ∈ ℕ. The set of such sequences is denoted by P (T, S). So, P (T, S) = {(x_{1}, x_{2}, …, x_{T}) : x_{i} ∈ ℤ_{≥0}∀i, ∑_{i=1}^{T} x_{i} = S} and this is a submesh of dimension T − 1 of ℤ^{T}. Let D′ be a multimodular matrix of size T x T induced by the submesh P (T, S).

Let x, x′ ∈ P (T, S). Then we say that x and x′ are conjugate if they are cyclic permutations of each other. It holds that x and x′ are conjugate if there exist finite (possibly empty) sequences v and w such that x = vw and x′ = wv. It is easily seen that this conjugacy is an equivalence relation on P (T, S) and we write x ∼ x′ if x and x′ are conjugate. We denote by x̃ the conjugacy class of x ∈ P (T, S), which is the set of all cyclic permutations of x. By P̃(T, S) we denote the set of conjugacy classes of P (T, S). If x ∼ x′ then we also say that x and x′ are shifts of each other. If x̃ = ỹ then we say that x is a representative of ỹ.

Let f : P (T, S) → ℝ be a function such that f(x) = f(x′) if x ∼ x′. Then we say that f is a shift invariant function. A shift invariant function f : P (T, S) → ℝ induces a function f̃: P̃(T, S) → ℝ by f̃(y) = f(x) where x ∈ P (T, S) is a representative of y ∈ P̃(T, S). We denote by F^{shift}(D′) the set of functions mapping P̃(T, S) to ℝ which are induced by D′ multimodular functions that are shift invariant. We use F^{shift}(D′) to define a partial order ≤_{mms} on P̃(T, S) in the same way as F(D, r) was used to define the partial order ≤_{mm} on M_{D}. The partial order ≤_{mms} is called the shift invariant multimodular order.

Definition 2.15 Let a multimodular matrix D′ induced by the submesh P (T, S) be given. Then for x, y ∈ P̃(T, S) we say that x ≤_{mms} y if f(x) ≤ f(y) for every f ∈ F^{shift}(D′).

Let x ∈ P (T, S). Then we say that x = (x_{1}, x_{2}, …, x_{T}) is regular if the induced infinite sequence x^{∞} := (x_{1}, …, x_{T} , x_{1}, …, x_{T} , …) is a bracket or regular sequence and in that case the conjugacy class x̃ ∈ P̃(T, S) is also called regular. We denote by R(T, S) ⊆ P (T, S) the subset of regular sequences. The following lemma can be proved analogously to the proof for sequences of zeros and ones that is given in [12].

Lemma 2.16 Let T, S ∈ ℕ be given. Then there exists exactly one element in P̃(T, S) which is regular.

We denote by ω̃ = ω̃(T, S) the unique element of P̃(T, S) that is regular. Then we have the following theorem (see [4])

Theorem 2.17 Let a multimodular matrix D′ induced by the submesh P (T, S) be given and let f ∈ F^{shift}(D′). Then a global minimum of f is attained in ω̃(T, S).

Note that the global minimum ω̃(T, S) does not depend on D′.

Corollary 2.18 For every D′ we have that ω̃(T, S) is the smallest element for the partial order ≤_{mms} on P̃(T, S).

We have the multimodular order ≤_{mm} and we have the shift invariant multimodular order ≤_{mms} on P̃(T, S). We also define a shift invariant cone order ≤_{Cs} on P̃(T, S) which is the counterpart of the cone order ≤_{C}.

Definition 2.19 Let D′ be as in Theorem 2.17. Then for u, v ∈ P̃(T, S) we say that u ≤_{Cs} v if and only if there exist representatives u′ of u and v′ of v such that u′ ≤_{C} v′, where ≤_{C} is the cone order for multimodular matrix D′ and root r with r being a representative of ω̃(T, S).

According to Theorem 2.7 it holds that u′ ≤_{C} v′ if and only if f(u′) ≤ f(v′) for every f ∈ F(D′, r). Thus the following corollary follows directly from Theorem 2.7 and the definitions.

Corollary 2.20 Let D′ be as in Theorem 2.17. Then for u, v ∈ P̃(T, S) we have that u ≤_{mms} v if u ≤_{Cs} v.

So, according to Corollary 2.20 the shift invariant cone order implies the shift invariant multimodular order.

3 The graph order and the unbalance

Let u = (u_{1}, u_{2}, …, u_{T}) ∈ P (T, S) and for l = 0, 1, …, T − 1 let u^{(l)} := (u_{l+1}, u_{l+2}, …, u_{T} , u_{1}, u_{2}, …, u_{l}) ∈ P (T, S) be the l-th cyclic permutation of u. For a sequence u ∈ P (T, S) we define a counting function κ_{u} : {0, 1, …, T } → ℤ by κ_{u}(n) = ∑_{t=1}^{n} u_{t} and we define a discrepancy function ϕ_{u} : \{0, 1, …, T \} → ℚ by ϕ_{u}(n) = κ_{u}(n) − n · \frac{S}{T} for n = 0, 1, …, T.

Lemma 3.1 For u ∈ P (T, S) and l ∈ {0, 1, …, T −1} we have that ϕ_{u^{(l)}}(n) ≥ 0 for n = 0, 1, …, T if and only if ϕ_{u}(l) = min_{n=0,1,...,T} ϕ_{u}(n). Moreover, ϕ_{u^{(l)}}(n) ≤ 0 for n = 0, 1, …, T if and only if ϕ_{u}(l) = max_{n=0,1,...,T} ϕ_{u}(n).

Proof. Suppose that ϕ_{u^{(l)}}(n) < 0 for some n ∈ {0, 1, …, T − 1}. Then ϕ_{u}((l + n) (mod T)) = ϕ_{u}(l) + ϕ_{u^{(l)}}(n) < ϕ_{u}(l). Thus ϕ_{u}(l) = min_{n=0,1,...,T} ϕ_{u}(n) implies that ϕ_{u^{(l)}}(n) ≥ 0 for n = 0, 1, …, T. Suppose that ϕ_{u}(l′) < ϕ_{u}(l) for some l ≠ l′ ∈ {0, 1, …, T − 1}. Then ϕ_{u^{(l)}}((l′ − l) (mod T)) = ϕ_{u}(l′) − ϕ_{u}(l) < 0. Thus ϕ_{u^{(l)}}(n) ≥ 0 for n = 0, 1, …, T implies that ϕ_{u}(l) = min_{n=0,1,...,T} ϕ_{u}(n). Analogously it follows that ϕ_{u^{(l)}}(n) ≤ 0 for n = 0, 1, …, T if and only if ϕ_{u}(l) = max_{n=0,1,...,T} ϕ_{u}(n).

We define a partial order ⪯ on P (T, S). This induces partial orders on P̃(T, S) from which we derive bounds for the expected average waiting time.

Definition 3.2 For u, v ∈ P (T, S) we say that u ⪯ v if κ_{u}(n) ≤ κ_{v}(n) for n = 1, 2, …, T.

We have the following (see [12] where it is proved for sequences of zeros and ones).

Proposition 3.3 Let u ∈ R(T, S). Then u′ ∈ R(T, S) if and only if u ∼ u′. Moreover the partial order ⪯ on P (T, S) induces a total order on R(T, S).

Since R(T, S) is finite it follows from Proposition 3.3 that R(T, S) contains a greatest element for this order. We denote this greatest element by ω(T, S) or just ω if no confusion is possible. For this element ω the partial sums κ_{ω}(n) for n = 1, 2, …, T are as great as possible under the restriction that ω is regular. For example ω(7, 4) is the sequence (1, 1, 0, 1, 0, 1, 0). From [12] we have the following lemma which can be used to determine ω(T, S) quickly.

Lemma 3.4

κ_{ω(T,S)}(n) = ⌈n · \frac{S}{T} ⌉ for n = 0, 1, …, T.

We have seen in Proposition 3.3 that the regular sequences R(T, S) form a conjugacy class in P (T, S). It follows that u ∈ R(T, S) if and only if u is a representative of ω̃(T, S) ∈ P̃(T, S). Combining Lemma 3.1, Proposition 3.3 and Lemma 3.4 we obtain the following theorem in which the partial order ⪯ is used to give a characterising property of the conjugacy class R(T, k) = ω̃(T, S) of regular sequences in P̃(T, S).

Theorem 3.5 Every conjugacy class ũ of P (T, S) contains an upper bound of R(T, S), i.e for every u ∈ P (T, S) there exists a v ∈ P (T, S) such that v ∼ u and v ⪰ w for every w ∈ R(T, S).

Proof. For u ∈ P (T, S) let l ∈ {0, 1, …, T − 1} be such that ϕ_{u}(l) = min_{n=0,1,...,T} ϕ_{u}(n). Let v = u^{(l)}. Then v ∼ u and by Lemma 3.1 we have that ϕ_{v}(n) ≥ 0 for n = 0, 1, …, T. Hence κ_{v}(n) ≥ ⌈n · \frac{S}{T} ⌉ for n = 0, 1, …, T. So, by Lemma 3.4 we have that v ⪰ ω(T, S). By Proposition 3.3 we have that ω(T, S) ⪰ w and thus v ⪰ w for every w ∈ R(T, S).

We have the following preorders ⪯\overline{g}, ⪯\underline{g} and ⪯_{g} on P (T, S) called the primal or upper graph order, the dual or lower graph order and the strong graph order respectively.

Definition 3.6 Let u, v ∈ P (T, S). Then u ⪯\overline{g} v if there exist u′, v′ ∈ P (T, S) such that u′ ∈ ũ, v′ ∈ ṽ and 0 ≤ ϕ_{u′}(n) ≤ ϕ_{v′}(n) for n = 0, 1, …, T and u ⪯\underline{g} v if there exist u′′, v′′ ∈ P (T, S) such that u′′ ∈ ũ, v′′ ∈ ṽ and 0 ≥ ϕ_{u′′}(n) ≥ ϕ_{v′′}(n) for n = 0, 1, …, T. Further u ⪯_{g} v if u ⪯\overline{g} v and u ⪯\underline{g} v.

The preorders ⪯\overline{g}, ⪯\underline{g} and ⪯_{g} on P (T, S) are not partial orders. Namely, if u, v ∈ P (T, S) are cyclic permutations of each other then it is easily seen that u ⪯_{g} v and v ⪯_{g} u. Thus these orders are not antisymmetric. However, they induce (see Definition 3.7 ) partial orders on P̃(T, S).

Definition 3.7 Let u, v ∈ P̃(T, S) and u′ ∈ P (T, S) be a representative of u and v′ ∈ P (T, S) be a representative of v. Then we say that u ⪯_{g} v if and only if u′ ⪯_{g} v′ and similar for the orders ⪯\overline{g} and ⪯\underline{g}.

In [12] it is shown that these induced graph orders on P̃(T, S) are partial orders.

For a sequence u ∈ P (T, S) we have a primal unbalance \overline{I}(u) and a dual unbalance \underline{I}(u).

Definition 3.8 Let u ∈ P (T, S). Then the primal unbalance of u is

\overline{I}(u) := \frac{1}{T} · ∑_{n=1}^{T}(κ_{u′}(n) − ⌈n · \frac{S}{T} ⌉),

where u′ ∈ ũ such that ϕ_{u′}(n) ≥ 0 for n = 1, 2, …, T. The dual unbalance of u is

\underline{I}(u) := \frac{1}{T} · ∑_{n=1}^{T}(⌊n · \frac{S}{T} ⌋ − κ_{u′}(n)),

where u′ ∈ ũ such that ϕ_{u′}(n) ≤ 0 for n = 1, 2, …, T.

Remark. For u ∈ P (T, S) the primal unbalance is well defined. Namely, by Lemma 3.1 there exist u′ ∈ ũ such that ϕ_{u′}(n) ≥ 0 for n = 1, 2, …, T. Moreover, if u′, u′′ ∈ ũ are such that ϕ_{u′}(n) ≥ 0 and ϕ_{u′′}(n) ≥ 0 for n = 1, 2, …, T then ∑_{n=1}^{T} κ_{u′}(n) = ∑_{n=1}^{T} κ_{u′′}(n) (see Theorem 3.9). Analogously it follows that the dual unbalance is well defined. It is easily seen that for every sequence u ∈ P (T, S) it holds that \overline{I}(u) ≥ 0 and \underline{I}(u) ≥ 0. Namely, for u′ ∈ P (T, S) we have that ϕ_{u′}(n) ≥ 0 if and only if κ_{u′}(n) ≥ ⌈n · \frac{S}{T} ⌉ and ϕ_{u′}(n) ≤ 0 if and only if κ_{u′}(n) ≤ ⌊n · \frac{S}{T} ⌋. Moreover, a sequence u ∈ P (T, S) is regular if and only if \overline{I}(u) = 0 if and only if \underline{I}(u) = 0 (see [12]).

Theorem 3.9 Let u ∈ P (T, S). Then the following statements are equivalent for l ∈ {0, 1, …, T − 1}.

(i) \overline{I}(u) = \frac{1}{T} · ∑_{n=1}^{T}(κ_{u^{(l)}}(n) − ⌈n · \frac{S}{T} ⌉).

(ii) ∑_{n=1}^{T} κ_{u^{(l)}}(n) = max_{i=0,1,...,T −1} ∑_{n=1}^{T} κ_{u^{(i)}}(n).

(iii) min_{n=0,1,...,T −1} ϕ_{u^{(l)}}(n) = ϕ_{u^{(l)}}(0) = 0.

(iv) ϕ_{u}(l) = min_{i=0,1,...,T −1} ϕ_{u}(i).

Proof. By Lemma 3.1 we have that (iii) implies (iv) and vice versa. We now prove that (ii) implies (iii). Suppose there exists some t ∈ {1, 2, …, T − 1} such that ϕ_{u^{(l)}}(t) = −μ with μ > 0. Let x be the prefix of length t of u^{(l)} and let y be the suffix of length T − t of u^{(l)}. Then u^{(l)} = xy. Let z := yx = u^{((l+t) (mod T))} ∈ ũ. Then ϕ_{u^{(l)}}(n) = ϕ_{z}(n − t) − μ for n = t, t + 1, …, T and ϕ_{u^{(l)}}(n) = ϕ_{z}(n + T − t) − μ for n = 1, 2, …, t − 1. Hence ∑_{n=1}^{T} ϕ_{u^{(l)}}(n) = ∑_{n=1}^{T} ϕ_{z}(n) − T · μ and thus

∑_{n=1}^{T} κ_{u^{(l)}}(n) = ∑_{n=1}^{T} κ_{z}(n) − T · μ < ∑_{n=1}^{T} κ_{z}(n) ≤ max_{i=0,1,...,T −1} ∑_{n=1}^{T} κ_{u^{(i)}}(n),

which contradicts (ii). From the definition of the primal unbalance it follows directly that (iii) implies (i) and to finish the proof we show that (i) implies (ii). Suppose that ∑_{n=1}^{T} κ_{u^{(l)}}(n) < max_{i=0,1,...,T −1} ∑_{n=1}^{T} κ_{u^{(i)}}(n) and let l ≠ l′ ∈ {0, 1, …, T − 1} such that ∑_{n=1}^{T} κ_{u^{(l′)}}(n) = max_{i=0,1,...,T −1} ∑_{n=1}^{T} κ_{u^{(i)}}(n). Since we have proved that (ii) implies (i) it follows that

\overline{I}(u) = \frac{1}{T} · ∑_{n=1}^{T}(κ_{u^{(l′)}}(n) − ⌈n · \frac{S}{T} ⌉) > \frac{1}{T} · ∑_{n=1}^{T}(κ_{u^{(l)}}(n) − ⌈n · \frac{S}{T} ⌉),

which contradicts (i). □ The following result follows immediately from the definitions.

Lemma 3.10 Let u, v ∈ P (T, S). If u ⪯\overline{g} v then \overline{I}(u) ≤ \overline{I}(v). If u ⪯\underline{g} v then \underline{I}(u) ≤ \underline{I}(v). If u ⪯_{g} v then \overline{I}(u) ≤ \overline{I}(v) and \underline{I}(u) ≤ \underline{I}(v).

We have the following theorem, which shows that the primal and dual unbalance are multimodular with respect to the L - triangulation.

Theorem 3.11 The primal unbalance and the dual unbalance are shift invariant and multimodular on P (T, S) with respect to the base d_{1}, d_{2}, …, d_{T} where d_{i} = e_{i} − e_{i+1} for i = 1, 2, …, T − 1, d_{T} = e_{T} − e_{1} and e_{i} is the i -th unit vector of length T for i = 1, 2, …, T.

Proof. For u ∈ P (T, S) let f(u) = \overline{I}(u) and g(u) = \underline{I}(u). Thus f : P (T, S) → ℚ is the primal unbalance function and g : P (T, S) → ℚ is the dual unbalance function. From the definition it follows that if u′, u′′ ∈ P (T, S) are cyclic permutations of each other then f(u′) = f(u′′) and g(u′) = g(u′′). Thus the primal unbalance and dual unbalance are shift invariant. To prove the multimodularity of the primal unbalance function f we have to show that for every u ∈ P (T, S) and i, j ∈ {1, 2, …, T }, i ≠ j it holds that

f(u + d_{i}) + f(u + d_{j}) ≥ f(u) + f(u + d_{i} + d_{j}).  (12)

We first show that for every x ∈ P (T, S) and i ∈ {1, 2, …, T } it holds that

f(x + d_{i}) ≤ f(x) + \frac{1}{T} .  (13)

Put y = x + d_{i}. Without loss of generality we can assume that ∑_{n=1}^{T} κ_{y}(n) = max_{i=0,1,...,T −1} ∑_{n=1}^{T} κ_{y^{(i)}}(n). Then f(y) = \frac{1}{T} · ∑_{n=1}^{T}(κ_{y}(n) − ⌈n · \frac{S}{T} ⌉) and

f(x) = f(y − d_{i}) ≥ \frac{1}{T} · ∑_{n=1}^{T}(κ_{y−d_{i}}(n) − ⌈n · \frac{S}{T} ⌉) ≥ \frac{1}{T} · (∑_{n=1}^{T}(κ_{y}(n) − ⌈n · \frac{S}{T} ⌉) − 1) = f(y) − \frac{1}{T}

by Theorem 3.9. So, (13) holds and next we show that (12) holds. Without loss of generality we assume that min_{n=0,1,...,T −1} ϕ_{u}(n) = ϕ_{u}(0) = 0. Then f(u) = \frac{1}{T} · ∑_{n=1}^{T}(κ_{u}(n) − ⌈n · \frac{S}{T} ⌉) by Theorem 3.9. Suppose that i ≠ T and j ≠ T. Then it is easily seen that κ_{u+d_{i}}(n) ≥ κ_{u}(n), κ_{u+d_{j}}(n) ≥ κ_{u}(n) and κ_{u+d_{i}+d_{j}}(n) ≥ κ_{u}(n) for n = 0, 1, …, T. Hence

min_{n=0,1,...,T −1} ϕ_{u+d_{i}}(n) = min_{n=0,1,...,T −1} ϕ_{u+d_{j}}(n) = min_{n=0,1,...,T −1} ϕ_{u+d_{i}+d_{j}}(n) = min_{n=0,1,...,T −1} ϕ_{u}(n) = 0.

From the definition of the primal unbalance it follows that f(u + d_{i}) = f(u + d_{j}) = f(u) + \frac{1}{T} and f(u + d_{i} + d_{j}) = f(u) + \frac{2}{T} and thus f(u + d_{i}) + f(u + d_{j}) = f(u) + f(u + d_{i} + d_{j}). It remains to show that (12) holds in case i = T or j = T and we may assume that j = T and i ≠ T. Then from the preceding argument we have that f(u + d_{i}) = f(u) + \frac{1}{T}. Moreover by (13) we have that f(u + d_{i} + d_{j}) ≤ f(u + d_{j}) + \frac{1}{T}. Hence

f(u + d_{i}) + f(u + d_{j}) ≥ (f(u) + \frac{1}{T}) + (f(u + d_{i} + d_{j}) − \frac{1}{T}) = f(u) + f(u + d_{i} + d_{j}).

Thus the primal unbalance function f is multimodular and it follows analogously that the dual unbalance function g is multimodular.

Note. Since the primal and dual unbalance functions are shift invariant on P (T, S) they induce functions on P̃(T, S) by \overline{I}(v) = \overline{I}(u) and \underline{I}(v) = \underline{I}(u) if u ∈ P (T, S) is a representative of v ∈ P̃(T, S). Then by Theorem 3.11 we have for these induced primal and dual unbalance functions that they are elements of F^{shift}(D), where D is the multimodular matrix having the multimodular base d_{1}, d_{2}, …, d_{T} as row vectors.

Corollary 3.12 For this multimodular base d_{1}, d_{2}, …, d_{T} we have for u, v ∈ P̃(T, S) that u ≤_{mms} v implies that \overline{I}(u) ≤ \overline{I}(v) and \underline{I}(u) ≤ \underline{I}(v).

4 Relations and counterexamples

4.1 The shift invariant cone order does not imply the graph order

Consider the following example. Let u = (1, 3, 2, 2, 3) ∈ P(5, 11) and v = (2, 1, 3, 2, 3) ∈ P(5, 11). Thus we consider sequences of length 5 and sum 11. It is easily seen that u and v are not ordered for the dual lower graph order (but they are ordered for the primal upper graph order). So, u and v are not graph ordered. However, we show that u and v are ordered for shift invariant multimodular functions with respect to the standard base d_{0}, d_{1}, d_{2}, d_{3}, d_{4} where d_{i} = e_{i}−e_{i+1} for i = 1, 2, 3, 4 and d_{0} = (−1, 0, 0, 0, 1). Namely, for a shift invariant multimodular function f we have that f(u+d_{4}) = f((1, 3, 2, 3, 2)) = f(v) and also f(u + d_{1}) = f((2, 2, 2, 2, 3) = f((2, 2, 2, 3, 2)) = f(u + d_{1} + d_{4}) by shift invariance. By multimodularity we have that f(u + d_{1}) + f(u + d_{4}) ≥ f(u) + f(u + d_{1} + d_{4}) and thus f(u) ≤ f(u + d_{4}) = f(v) for every multimodular shift invariant function f.

Conclusion. The shift invariant multimodular order does not imply the graph order. Thus the shift invariant multimodular order does not imply the shift invariant cone order or the shift invariant cone order does not imply the graph order (or both do not hold).

We now investigate whether u ≤_{Cs} v. To do this we take the regular sequence r = (3, 2, 2, 2, 2) as root of all the cones we consider and we let u′, v′ run through all the shifts of u and v respectively. Then we check whether u′ ≤ v′ for some cone. Doing this we find that u and v are indeed ordered for the shift invariant cone order. Namely, for u′ = (3, 1, 3, 2, 2) and v′ = (2, 1, 3, 2, 3) we have that u′ = r + d_{0} + d_{1} + d_{3} + d_{4} and v′ = r + 2d_{0} + d_{1} + d_{3} + d_{4}. Hence, if we consider the cone generated by b_{1} = d_{0}, b_{2} = d_{0} + d_{1}, b_{3} = d_{0} + d_{1} + d_{3} and b_{4} = d_{0} + d_{1} + d_{3} + d_{4} then u′ = r + b_{4} and v′ = r + b_{1} + b_{4}. By the way, this u′ and v′ is the only pair of shifts that are cone ordered for some cone with root in r. Since u′ ≤_{C} v′ and thus u ≤_{Cs} v we have the following conclusion.

Conclusion. The shift invariant cone order does not imply the graph order.

Remarks. The explanation for the fact that the ordering of u′ and v′ in this cone does not imply the lower graph order is the following. For u′ you have to start with the second coordinate to get the graph for the lower graph order and for v′ you have to start with the first coordinate. This is possible, because for r you have the start at the second coordinate for the lower graph order, while the generating base vectors of this cone ”suggest” the lower graph order for starting at the first coordinate. One of the consequences is that this cone does contain other regular sequences than r. Namely, r + b_{1} = (2, 2, 2, 2, 3) is for example another regular sequence in this cone. It turns out that the cone order in such cones does not imply the graph order. If you consider the mirrored sequences of u and v then you get a similar problem with the upper graph order instead of the lower graph order. Note that u and v are ordered for the unbalance (despite that they are not ordered for the graph order). Namely, for the primal (upper) unbalance \overline{I} we have that \overline{I}(u) = 1 ≤ 2 = \overline{I}(v) and for the dual (lower) unbalance \underline{I} we have that \underline{I}(u) = 1 = \underline{I}(v). Of course this order for the unbalance follows immediately from ũ ≤_{mms} ṽ and Corollary 3.12.

4.2 The shift invariant multimodular order does not imply the shift invariant cone order

A counterexample is given here to show that the shift invariant multimodular order does not imply the shift invariant cone order. In fact it is shown that the shift invariant cone order is not even a partial order, because it is not transitive.

Counterexample. Again we consider sequences in P (5, 11) and we have the same multimodular standard base {d_{i}}_{i=0,1...,5} as before. Let u = (1, 2, 3, 2, 3), v = (2, 2, 3, 3, 1) and w = (2, 1, 0, 4, 4) and as regular sequence we have again r = (3, 2, 2, 2, 2). Now we have for the shift invariant cone order that u ≤_{Cs} v and v ≤_{Cs} w. However, we do not have that u ≤_{Cs} w. Namely, u′ = (3, 2, 3, 1, 2) = r + d_{3} = r + b_{1} and v′ = (2, 3, 3, 1, 2) = r + d_{2} + 2d_{3} + d_{4} + d_{0} = r + b_{1} + b_{4}, where b_{1} = d_{3}, b_{2} = d_{3} + d_{0}, b_{3} = d_{3} + d_{0} + d_{2} and b_{4} = d_{3} + d_{0} + d_{2} + d_{4}. Hence u ≤_{Cs} v. Further v′′ = (3, 1, 2, 2, 3) = r+d_{0}+d_{1} = r+b_{2} and w′′ = (2, 1, 0, 4, 4) = r+4d_{0}+3d_{1}+2d_{2}+2d_{4} = r + b_{1} + b_{2} + 2b_{4}, where b_{1} = d_{0}, b_{2} = d_{0} + d_{1}, b_{3} = d_{0} + d_{1} + d_{2} and b_{4} = d_{0} + d_{1} + d_{2} + d_{4}. Hence v ≤_{Cs} w. However, there exist no cone with root in r such that some shift of u is smaller in that cone than some shift of w. Hence, u and w are not shift invariant cone ordered, while from u ≤_{Cs} v and v ≤_{Cs} w it follows that u and w are ordered for the shift invariant multimodular order.

Remark. So, it turns out that the shift invariant cone order is not a partial order, because it is not transitive. It is natural to consider the smallest preorder which contains the shift invariant cone order and is transitive. It is easily seen that this order implies the shift invariant multimodular order, but we do not know whether the converse is also true.

4.3 The graph order does not imply the shift invariant multimodular order

In this counterexample we show that the graph order does not imply the shift invariant multimodular order. Consider the sequences u = (0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1) ∈ P (32, 15) and v = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1) ∈ P (32, 15). Then we have that u ≤_{g} v. Thus u and v are ordered for the graph order and we have that \overline{I}(u) < \overline{I}(v) and \underline{I}(u) < \underline{I}(v). However, it does not hold that f(u) ≤ f(v) for every shift invariant multimodular function f : P (32, 15) → ℝ. Namely, we consider u and v as period cycles for the splitting sequences corresponding to the admission of arriving customers to some server. Suppose that the interarrival times are deterministic and equal to 1 and the service times are deterministic and equal to (1 + ϵ), where ϵ is a small positive number. For x ∈ P (32, 15) let W (x) be the average waiting time of customers admitted according to x. The average waiting time is multimodular with respect to the standard base of the L - triangulation (see [4]) and since the traffic intensity for the server is smaller than one we have that the average waiting time function W is also shift invariant (see [12]). Thus W is a shift invariant multimodular function. However, for the given interarrival and service times we have that W (u) = \frac{11}{15} · ϵ and W (v) = \frac{10}{15} · ϵ. Thus W (v) < W (u) for these service times and thus u and v are not ordered for the shift invariant multimodular order.

5 Bounding the Difference in Expected Average Waiting Time of Routing Sequences for One Queue

In this section we give a bound for the expected average waiting time for customers routed to a single server queue according to a routing sequence of zeros and ones. This bound depends on the unbalance of the routing sequence. To state the results we first give some definitions and notations.

Let u and v be infinite periodic integer sequences. Then we say that u is equivalent to v, u ∼ v if there exists a finite sequence w such that w is a period cycle of both u and v. For the application as routing sequences it is shown in [12] that equivalent infinite periodic sequences have the same performance. Let P be the set of infinite periodic sequences of zeros and ones (modulo the equivalence relation), R ⊆ P the subset of regular periodic sequences and for d ∈ ℚ, 0 ≤ d ≤ 1 let P(d) ⊆ P be the subset of sequences with density d. We denote the regular sequence in P(d) by ω(d) or just ω. Note that if u′ ∈ P(T, k) is a period cycle of u ∈ P then u ∈ P(\frac{k}{T}). We define the unbalance for infinite periodic sequences of zeros and ones as follows.

Definition 5.1 Let u ∈ P and let u′ ∈ P(T, k) be a period cycle of u. Then we define the (primal) unbalance of u as \overline{I}(u) := \overline{I}(u′).

The unbalance is well defined on P. Namely, if u′ and u′′ are both period cycles of u then \overline{I}(u′) = \overline{I}(u′′).

Let {T_{i}}_{i=1,2,...} be a sequence of arrival times of customers, with the convention that T_{1} = 0. Put δ_{i} := T_{i+1} − T_{i} for i = 1, 2, . . .. Then {δ_{i}} is the sequence of interarrival times. Further these arriving customers are routed to a server according to some routing sequence u = (u_{1}, u_{2}, …) of zeros and ones. For such routing sequences we have the counting function κ_{u}(n) = ∑_{t=1}^{n} u_{t} and we define a partial order ⪯ that is similar as the order on P (T, S). Namely, we say that u ⪯ v if κ_{u}(n) ≤ κ_{v}(n) for n = 0, 1, . . .. Further we define the the following related function ν_{u}(i) : ℤ_{≥0} → ℤ with ν_{u}(j) = min{n ∈ ℤ_{≥0} : κ_{u}(n) = j} and we put τ_{u}(j) = ∑_{i=max(ν_{u}(j−1),1)}^{ν_{u}(j)−1} δ_{i} for j = 1, 2, …. Then τ_{u}(j) is the time elapsed between the routing of the (j − 1)-th and jth customer to the server according to routing sequence u. If we put λ_{u}(j) = ∑_{k=1}^{j} τ_{u}(k) for j = 1, 2, … then λ_{u}(j) is the time at which the j-th customer is routed to the server according to routing sequence u. We have a sequence of service times {σ_{j}}_{j=1,2,...}, where σ_{j} is the service time of the j-th customer that is routed to the server according to the routing sequence. Further we define W_{u}(j) to be the workload for the server at the moment the j-th customer is routed to the server according to routing sequence u. In other words W_{u}(j) is the waiting time for the j -th customer that is routed to the server. We assume that the server starts empty at T_{1} = 0 and thus W_{u}(1) = 0. If the interarrival times {δ_{i}} and service times {σ_{j}} are random variables then we say that \overline{W} (u) is the almost sure long-run average waiting time of customers routed to the server according to routing sequence u if lim_{m→∞} \frac{1}{m} · ∑_{j=1}^{m} W_{u}(j) = \overline{W} (u) with probability one. From ergodic theory we have the following theorem. See [12] for a proof of this theorem.

Theorem 5.2 Suppose that the interarrival times {δ_{i}} of customers arriving at the system are independent and identically distributed (i.i.d.) random variables with mean δ and the service times {σ_{j}} of the considered server are i.i.d. random variables with mean σ and independent of the interarrival times. Further let u′ and u′′ be routing sequences of zeros and ones that are both representatives of some u ∈ P(d) where d ∈ ℚ (thus they have a common period cycle) and \frac{σ}{δ} · d < 1. Then \overline{W} (u′) and \overline{W} (u′′) exist and are finite. Moreover \overline{W} (u′) = \overline{W} (u′′).

Let δ , σ and d be as in Theorem 5.2. Then we say that ρ := \frac{σ}{δ} · d is the traffic intensity for the server. By Theorem 5.2 all the routing sequences which are representative of some u ∈ P(d) have the same long-run average waiting time if the stability condition ρ < 1 is fulfilled. Therefore in this case we denote this long-run average waiting time simply by \overline{W} (u). The following theorem which is obtained by a sample path argument is the main result of this section.

Theorem 5.3 Let the interarrival times {δ_{i}} and the service times {σ_{j}} be as in Theorem 5.2. Further let u ∈ P(d) for some d ∈ ℚ such that ρ < 1 and let ω = ω(d) ∈ P(d) be the regular sequence of density d. Then

\overline{W} (u) ≤ \overline{W} (ω) + \frac{δ}{d} · \overline{I}(u).  (14)

Remark. From the results of [1] and [3] we have that \overline{W} (u) ≥ \overline{W} (ω).

We give an outline of the proof of Theorem 5.3. For a complete proof for this and following results in sections 5 and 6 see [12]. We first assume that the interarrival times {δ_{i}}_{i=1,2,...} and service times {σ_{j}}_{j=1,2,...} are fixed sequences of non-negative real numbers. Then we have the following lemma.

Lemma 5.4 Let u = (u_{1}, u_{2}, …) and v = (v_{1}, v_{2}, …) be routing sequences of zeros and ones and suppose that u ⪯ v. Then

W_{v}(j) + λ_{v}(j) ≤ W_{u}(j) + λ_{u}(j) for every j ∈ ℕ.  (15)

Note that W_{u}(j) + λ_{u}(j) is the moment that the server starts serving the j-th customer that is routed to the server according to u. So, Lemma 5.4 states that if u ⪯ v then the moment when the service of the j -th customer that is routed to the server starts, is for v not later than for u. This can be proved by induction to j.

For every j ∈ ℕ we have that λ_{u}(j) − λ_{v}(j) = ∑_{i=ν_{v}(j)}^{ν_{u}(j)−1} δ_{i}. This is a sum of interarrival times δ_{i}, where the number of terms in the sum is ν_{u}(j) − ν_{v}(j). Therefore, if we put N_{uv}(m) = ∑_{j=1}^{m}(ν_{u}(j) − ν_{v}(j)) for m = 1, 2, …, then we have the following Corollary by Lemma 5.4.

Corollary 5.5 Let u and v be routing sequences with u ⪯ v. For every m ∈ ℕ we have that

∑_{j=1}^{m} W_{v}(j) ≤ ∑_{j=1}^{m} W_{u}(j) + ∑_{j=1}^{m} ∑_{i=ν_{v}(j)}^{ν_{u}(j)−1} δ_{i}.  (16)

In the double sum the number of terms is N_{uv}(m).

In [12] it is shown that if u = (u′)^{∞} and v = (v′)^{∞} for some u′, v′ ∈ P(T, k) and ω(T, k) ⪯ u′ ⪯ v′ then

lim_{m→∞} \frac{N_{uv}(m)}{m} = \frac{T}{k} · (\overline{I}(v) − \overline{I}(u)).  (17)

Let u ∈ P(d) be as in Theorem 5.3. Then by Theorem 3.5 there exist T, k ∈ ℕ with d = \frac{k}{T} and u′′ ∈ P(T, k) such that u′ := (u′′)^{∞} is a representative of u and ω′ ⪯ u′ where ω′ = ω(T, k)^{∞} is a representative of ω(d). By Theorem 5.2 we have that both \overline{W} (u) = \overline{W} (u′) and \overline{W} (ω) = \overline{W} (ω′) exist. We make a coupling between the interarrival times for u′ and ω′ and we also do this for the service times. After the coupling we can apply Corollary 5.5 and (17) and it follows that

\overline{W} (u′) − \overline{W} (ω′) ≤ \frac{δ · T}{k} · (\overline{I}(u) − \overline{I}(ω)) = \frac{δ}{d} · I(u),

which proves Theorem 5.3.

Remark. From the preceding arguments it follows that it is possible to refine Theorem 5.3 as follows: Let u, v ∈ P(d) be as in Theorem 5.3 and let ω′ be a representative of ω(d) as above. Then, if there exist representatives u′ and v′ of u and v respectively such that ω′ ⪯ u′ ⪯ v′ it holds that

\overline{W} (v) − \overline{W} (u) ≤ \frac{δ}{d}(\overline{I}(v) − \overline{I}(u)).  (18)

The reader can check that the condition for (18) is equivalent to the following: there exist T, k ∈ ℕ and period cycles u′′ and v′′ of u and v respectively such that d = \frac{k}{T} , u′′, v′′ ∈ P(T, k) and u′′ ⪯\overline{g} v′′. Moreover, the condition ρ < 1 in Theorem 5.3 is just necessary to apply Theorem 5.2. However, if both the interarrival times and the service times are deterministic then Theorem 5.2 also holds if ρ = 1 (see [14]). In fact we have for that case the following stronger result from which it follows that the bound of Theorem 5.3 is tight.

Theorem 5.6 Suppose that the interarrival times and service times are deterministic and equal to δ respectively σ. Let u ∈ P(d) for some d ∈ ℚ such that δ = dσ, hence ρ = 1, and let ω = ω(d) be the regular sequence of density d. Then

\overline{W} (u) = \overline{W} (ω) + \frac{δ}{d} · \overline{I}(u).  (19)

Proof. (Outline) Let ω′ be a representative of ω(d) as above and let u′ be a representative of u such that ω′ ⪯ u′. Then it can be shown that W_{u′}(j) + λ_{u′}(j) = W_{ω′}(j) + λ_{ω′}(j) = (j − 1)σ for every j ∈ ℕ. Hence we have for every m ∈ ℕ that (16) holds with equality for u′ and ω′ with δ_{i} = δ for i = 1, 2, . . .. From this it follows that (14) also holds with equality.

Remark. The upper bound can be generalized to a sequence of multimodular functions satisfying the relations of section 3 of [3]. Indeed, it follows from the results there that the regular or bracket sequence is the minimal admission sequence. If the density is rational then the corresponding regular admission sequence is periodic. In order to obtain upper bounds as in Theorem 5.3 and Theorem 6.3 we need a generalization of Lemma 5.4, especially the relation (15). It is easily seen that for multimodular functions f_{k} corresponding to W_{u}(j) it suffices that

f_{k}(a_{1}, …, a_{l} + 1, a_{l+1} − 1, …, a_{k}) ≤ f_{k}(a_{1}, …, a_{l}, a_{l+1}, …, a_{k}) + δ,

for 1 ≤ l ≤ k − 1 and some constant δ. Clearly, also other multimodular models do satisfy this relation, e.g. the models of [7].

6 Routing to Parallel Queues

In this section we derive upper bounds for the expected average waiting time for routing arriving customers to N ≥ 2 parallel queues according to some periodic routing policy U = (U_{1}, U_{2}, …). The routing sequence U = (U_{1}, U_{2}, …) can be seen as an ℕ - word on the alphabet {1, 2, …, N}. Further to every letter i ∈ {1, 2, …, N} corresponds a sequence of zeros and ones u^{i} = (u_{1}^{i}, u_{2}^{i}, …) via the support of the letter, i.e. u_{n}^{i} = 1 if and only if U_{n} = i. We call u^{i} the routing or splitting sequence for queue i ([10], [13], [1], [14] and [12]). Extending the notion of unbalance for periodic sequences of zeros and ones we define a (total) unbalance O(U) for periodic integer sequences and corresponding words on some finite alphabet. Then we extend the result of Theorem 5.3 for one queue to multiple queues by using the unbalance O(U) of U.

Let d_{1}, d_{2}, …, d_{N} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Then we denote by Q(d_{1}, d_{2}, …, d_{N}) all the infinite periodic ℕ - words U on the alphabet {1, 2, …, N} for which u^{i} ∈ P(d_{i}) for i = 1, 2, …, N. Further for T, k_{1}, k_{2}, …, k_{N} ∈ ℕ with ∑_{i=1}^{N} k_{i} = T we denote by Q({T }, k_{1}, k_{2}, …, k_{N}) all the ℕ-words on the alphabet {1, 2, …, N} for which every subword of length T contains exactly k_{i} letters i for i = 1, 2, …, N. Note that Q(\{T \}, k_{1}, k_{2}, …, k_{N}) ⊆ Q(\frac{k_{1}}{T} , \frac{k_{2}}{T} , …, \frac{k_{N}}{T}). For example if U = (1, 2, 1, 2, 1, 3, 1, 2, 1, 1, 2, 3)^{∞} then U ∈ Q(\{12\}, 6, 4, 2) ⊆ Q(\frac{1}{2}, \frac{1}{3}, \frac{1}{6}). Further u^{1} = (1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0)^{∞} ∈ P(\frac{1}{2}), u^{2} = (0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0)^{∞} ∈ P(\frac{1}{3}) and u^{3} = (0, 0, 0, 0, 0, 1)^{∞} ∈ P(\frac{1}{6}).

Let ψ be a routing policy and U the corresponding routing sequence. Then for t ∈ ℕ we define W (t) = W_{ψ}(t) as the waiting time of the t -th arriving customer if policy ψ is applied, which is the remaining workload for server U_{t} at the moment that the t-th customer arrives. We assume that all the servers i ∈ {1, 2, …, N} are empty at T_{1} = 0 and thus W (t) = 0 if t = ν_{u^{i}}(1) for some i ∈ {1, 2, …, N}. If the interarrival times and service times of the various servers are random variables then we say that \overline{W} (ψ) = \overline{W} (U) is the almost sure long-run average waiting time of the arriving customers routed according to policy ψ if lim_{τ→∞} \frac{1}{τ} · ∑_{t=1}^{τ} W_{ψ}(t) = \overline{W} (ψ) with probability one. Let {δ_{i}} be the sequence of interarrival times and let {σ_{j}^{i}} be the sequence of service times of server i for i = 1, 2, …, N, i.e σ_{j}^{i} is the service time of the j - th customer that

is routed to server i. We define \overline{W}^{i}(ψ) = \overline{W}^{i}(u^{i}) as the almost sure long-run average waiting time of customers routed to server i if policy ψ is applied in the same way as we did in the previous section. The only differences are that routing sequence u is replaced by routing sequence u^{i} and the sequence of service times {σ_{j}} is replaced with the sequence of service times {σ_{j}^{i}}. From Theorem 5.2 we obtain the following theorem.

Theorem 6.1 Suppose that the interarrival times {δ_{i}} of customers arriving at the system are i.i.d. random variables with mean δ and for every i ∈ {1, 2, …, N} the service times {σ_{j}^{i}} are i.i.d random variables with mean σ_{i}, and independent of the interarrival times. Let ψ be a routing policy that corresponds to some word U ∈ Q(d_{1}, d_{2}, …, d_{N}) such that ρ_{i} := \frac{σ_{i}}{δ} ·d_{i} < 1 for i = 1, 2, …, N. Then \overline{W} (ψ) exists and is finite. Moreover \overline{W} (ψ) = ∑_{i=1}^{n} d_{i} · \overline{W}^{i}(ψ).

Definition 6.2 Let U ∈ Q(d_{1}, d_{2}, …, d_{N}) for some d_{i} ∈ ℚ_{>0} with ∑_{i=1}^{N} d_{i} = 1. Then we define the (total) unbalance of U as

O(U) := ∑_{i=1}^{N} \overline{I}(u^{i}).  (20)

If it is clear from the context what is meant we just say unbalance and not total unbalance. Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 6.1. Further let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Recall that ω(d_{i}) is the regular sequence of density d_{i}. If \overline{W}^{i}(ω(d_{i})) exists and is finite for i = 1, 2, …, N then we put

R̃ = R̃(d_{1}, d_{2}, …, d_{N}) := ∑_{i=1}^{N} d_{i} · \overline{W}^{i}(ω(d_{i})).  (21)

Remark. If the interarrival times and service times are random variables then for the existence of R̃ it suffices that ρ_{i} < 1 for i = 1, 2, …, N, while if the interarrival times and service times are deterministic then it suffices that ρ_{i} ≤ 1 for i = 1, 2, …, N. It is possible to extend the definition of R̃ and some of the results to the case of irrational d_{i}. In general R̃ depends on the distribution of the interarrival times and service times and in some cases it is possible to compute R̃ explicitly. See [8] and [14] for an exact computation in case of deterministic interarrival and service times and see [13] for computations and bounds in general.

Combining Theorem 5.3 and Theorem 6.1 we obtain the following theorem.

Theorem 6.3 Let the interarrival times {δ_{i}} and the service times {σ_{j}^{i}} for i = 1, 2, …, N be as in Theorem 6.1. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Suppose that a routing policy ψ is applied with corresponding word U ∈ Q(d_{1}, d_{2}, …, d_{N}) and ρ_{i} < 1 for i = 1, 2, …, N. Then

\overline{W} (ψ) − R̃ ≤ δ · O(U).

From [3], \overline{W} (ψ) ≥ R̃, which is the lower bound obtained by replacing the routing sequence to queue i by the regular routing sequence with the same density for any queue i. Hence we have the following bounds.

R̃ ≤ \overline{W} (ψ) ≤ R̃ + δ · O(U).  (22)

Remark. Suppose that we have a queueing system where the arrivals are according to a Poisson process with parameter λ. Suppose that the service times of server i are exponentially distributed with parameter μ_{i}. If d_{i}, the fraction of jobs that is routed to server i, equals \frac{1}{q_{i}} for

some q_{i} ∈ ℕ, then \overline{W}^{i}(ω(d_{i})) can be calculated in the following way. For the routing sequence ω(d_{i}) we have that among every q_{i} arriving jobs exactly one job is routed to server i. So, the interarrival times at server i consist of q_{i} Poisson arrivals with parameter λ. Hence the interarrival times for the queue of server i are Erlang distributed, namely according to an E_{λ}^{q_{i}} distribution. Thus \overline{W}^{i}(ω(d_{i})) is the same as the average waiting time for a E_{λ}^{q_{i}}/M/1 queue, where the parameter of the service times is μ_{i}. So (see [9]) if x_{i} is the unique solution in the interval (0, 1) of the equation

x = (\frac{λ}{λ + μ_{i} − μ_{i} · x})^{q_{i}},  (23)

then

\overline{W}^{i}(ω(d_{i})) = \frac{x_{i}}{μ_{i} · (1 − x_{i})}.  (24)

In the following example we have calculated \overline{W}^{i}(ω(d_{i})) for i = 1, 2, 3, 4 by applying (24). Further we have explicitly calculated the lower bound R̃ and upper bound R̃ + δ · O(U) of (22) for \overline{W} (ψ), where U is the word corresponding to the applied routing policy ψ.

Example 6.4 We consider a queueing system with 4 parallel servers where the arrivals are according to a Poisson process with parameter λ = 11. Hence for the mean interarrival time δ we have that δ = \frac{1}{11}. The arriving jobs are routed to the servers according to the policy ψ that corresponds to the word

U = (1, 2, 3, 1, 4, 2, 1, 3, 1, 2, 4, 3)^{∞} ∈ Q(\{12\}, 4, 3, 3, 2) ⊆ Q(\frac{1}{3}, \frac{1}{4}, \frac{1}{4}, \frac{1}{6}).

Then we have that \overline{I}(u^{1}) = \frac{1}{12}, \overline{I}(u^{2}) = 0, \overline{I}(u^{3}) = \frac{1}{12}, \overline{I}(u^{4}) = 0 and thus O(U) = \frac{1}{6}. For every i ∈ {1, 2, 3, 4} the service times are exponentially distributed with parameter μ_{i} and μ_{1} = 4, μ_{2} = μ_{3} = 3 and μ_{4} = 2. Then we find by (24) that \overline{W}^{1}(ω(\frac{1}{3})) = 1.7792 (rounded to 4 decimals) and thus by Theorem 5.3 we have that \overline{W}^{1}(u^{1}) ≤ 1.7792 + 3 · \frac{1}{11} · \frac{1}{12} = 1.8019. Similarly we have that \overline{W}^{2}(ω(\frac{1}{4})) = \overline{W}^{2}(u^{2}) = 2.2105, \overline{W}^{3}(ω(\frac{1}{4})) = 2.2105, \overline{W}^{3}(u^{3}) ≤ 2.2408 and \overline{W}^{4}(ω(\frac{1}{6})) = \overline{W}^{4}(u^{4}) = 3.0732. Hence by (21) we have that

R̃ = \frac{1}{3} · \overline{W}^{1}(ω(\frac{1}{3})) + \frac{1}{4} · \overline{W}^{2}(ω(\frac{1}{4})) + \frac{1}{4} · \overline{W}^{3}(ω(\frac{1}{4})) + \frac{1}{6} · \overline{W}^{4}(ω(\frac{1}{6})) = 2.2105

and R̃ + δ · O(U) = 2.2105 + \frac{1}{11} · \frac{1}{6} = 2.2257. So, by (22) we have that 2.2105 ≤ \overline{W} (ψ) ≤ 2.2257.

The following theorem provides conditions under which the right-hand side inequality of (22) actually holds with equality.

Theorem 6.5 Let the interarrival times {δ_{i}} be deterministic equal to δ and the service times {σ_{j}^{i}} be deterministic equal to σ_{i} for i = 1, 2, …, N. Let d_{i} ∈ ℚ_{>0} for i = 1, 2, …, N with ∑_{i=1}^{N} d_{i} = 1. Let p_{i}, q_{i} ∈ ℕ be such that d_{i} = \frac{p_{i}}{q_{i}} with gcd(p_{i}, q_{i}) = 1 for i = 1, 2, …, N. Suppose that a routing policy ψ is applied with corresponding word U ∈ Q(d_{1}, d_{2}, …, d_{N}) and ρ_{i} = 1 for i = 1, 2, …, N. Then

\overline{W} (ψ) = R̃ + δ · O(U) = δ · (\frac{1}{2} − ∑_{i=1}^{N} \frac{1}{2q_{i}} + O(U)) .

By combining Theorem 5.6 and Theorem 6.1 we get the first equality of Theorem 6.5. See [14] for the second equality which follows from the computation of R̃ for this case.

Example 6.6 We consider a queueing system with 3 parallel servers where the interarrival times are deterministic and equal to δ = 3. The arriving jobs are routed to the servers according to the policy ψ that corresponds to the word

U = (1, 2, 1, 2, 1, 3, 1, 2, 1, 3)^{∞} ∈ Q(\{10\}, 5, 3, 2) ⊆ Q(\frac{1}{2}, \frac{3}{10}, \frac{1}{5}).

All the service times are deterministic and for server 1 they are equal to σ_{1} = 6, for server 2 equal to σ_{2} = 10 and for server 3 equal to σ_{3} = 15. Hence ρ_{i} = 1 for i = 1, 2, 3. Further \overline{I}(u^{1}) = 0, \overline{I}(u^{2}) = \frac{1}{10}, \overline{I}(u^{3}) = \frac{1}{10} and thus O(U) = \frac{1}{5}. So, according to Theorem 6.5 we have that

\overline{W} (ψ) = 3 · (\frac{1}{2} − (\frac{1}{4} + \frac{1}{20} + \frac{1}{10}) + \frac{1}{5}) = \frac{9}{10}

which can be checked by direct calculation.

References

[1] E. Altman, B. Gaujal, and A. Hordijk. Admission control in stochastic event graphs. IEEE Transaction on Automatic Control, 45(5):854–868, 2000.

[2] E. Altman, B. Gaujal, and A. Hordijk. Balanced sequences and optimal routing. Journal of the ACM, 47(4):752–775, 2000.

[3] E. Altman, B. Gaujal, and A. Hordijk. Multimodularity, convexity and optimization properties. Mathematics of Operations Research, 25(2):324–347, 2000.

[4] E. Altman, B. Gaujal, and A. Hordijk. Simplex convexity with application to open-loop stochastic control in networks. In 39th Conf. on Decision and Control. IEEE, 2000.

[5] E. Altman, B. Gaujal, and A. Hordijk. Regular ordering and applications in control policies. Journal of Discrete Event Dynamic Systems, 2002. to appear.

[6] E. Altman, B. Gaujal, and A. Hordijk. Discrete-event control of stochastic networks: Multimodularity and Regularity. in preparation.

[7] B. Gaujal, E. Altman and A. Hordijk. Optimal open-loop control of vacations, polling and service assignment. Queueing Systems, 36:303–325, 2000.

[8] B. Gaujal and E. Hyon. Optimal routing policy in two deterministic queues. Calculateurs Parallèles, 2001. accepted for publication, also available as INRIA RR-3997.

[9] D. Gross and C. Harris. Fundamentals of queueing theory. Series in Probabilty and mathematical statistics. Wiley, 1974.

[10] B. Hajek. Extremal splittings of point processes. Mathematics of Operation Research, 10(4):543–556, 1985.

[11] A. Hordijk. Comparison of queues with different discrete-time arrival processes. Probability in Engineering and Information Sciences, 15:1–14, 2001.

[12] A. Hordijk and D.A. van der Laan. Periodic routing to parallel queues with bounds on the average waiting time. Technical Report MI N. 2000-44, Leiden University, 2000.

[13] H. Shirakawa, M. Mori, and M. Kijima. Evaluation of regular splitting queues. Comm. Statist. Stochastic Models, 5:219–234, 1989.

[14] D.A. van der Laan. Routing jobs to servers with deterministic service times. Technical Report MI N. 2000-20, Leiden University, 2000.