2. MODELS

The method we use to derive our results is inductively showing certain properties of the dynamic programming (dp) value function. A general tool for simplifying and generalizing this task is event-based dp, as introduced in [8]. In that article, it is also applied to certain classes of models, which are in essence one- or two-dimensional. Our current interest is in higher-dimensional models. As event-based dp simplifies the current analysis as well, we start with describing the main ideas behind it. After that, we analyze the current class of systems.

Event-based dp is based on two crucial ideas. One is to split up the dp value function into smaller components—the event operators. The other is to give the set of functions that is to be propagated a central place, instead of the model itself. For a general description of event-based dp, see [8]. We restrict ourselves right away to the type of model that is studied in this article.

We take

as the state space (with

). For

, the component x_i, i > 0, represents the number of customers at queue i. The variable x₀ is the state of the environment. Let

be the class of functions from

to

. We will define the event operators—the building blocks of the value function. The operators that we are using in this article are of two types: controlled and uncontrolled; for example, we consider both a regular server that is active as long as there are customers waiting to be served and a server of which the service rate can be controlled. One of the benefits of event-based dp is that we consider both types of operator in the same framework, which makes clear what difference in model assumptions is necessary to deal with different operators.

In giving names to the operators, we use C for “controlled,” A for “arrivals,” D for “departures,” TS for “tandem server,” and M for “multiple.” The operators

are, for all

:

Of course, the operators incorporating one or more tandem servers are only defined for i = 1,…, m − 1; the other operators are defined for i = 1,…, m. Furthermore, for ease of notation, we used c in every operator that involves costs for some action. This c is arbitrary and can be different for each operator.

The coefficients of f in the operators can be interpreted as probabilities, except for the operators with multiple servers: There the coefficients sum to S. We could divide by S to obtain probabilities, but this division could also be part of the environment operator to be introduced next. To keep the notation as simple as possible, we assume the latter.

In addition to these operators dealing with the movements of customers in the system, we introduce an operator for the direct costs and one that determines how the environment (i.e., x₀) changes state and influences the transitions:

for some cost function C and discount factor α ≥ 0,

where x* is equal to x with the zeroth component replaced by y.

We see that

. To see how these operators can constitute the value function V_n, it is best to consider an example that models a simple tandem system of M/M/1 queues (the server at queue i has rate μ_i) with Poisson arrivals (at rate λ) and some arbitrary cost function:

with the parameters of T_env chosen such that it models the well-known concept of uniformization (e.g., see [13, Sec.11.5]), by taking

with p(1) = λ/(λ + [sum ]_i μ_i) and p(i) = μ_i−1 /(λ + [sum ]_j μ_j), i = 2,…, m + 1. That V_n is indeed equal to the value function of the continuous-time tandem server model can be easily seen by writing out (1).

The operator T_env, however, can serve many more purposes. We see that if the environment moves from x₀ to y, which occurs with probability λ(x₀, y) (but, due to the uniformization, we can also see this as a transition rate), then with probability q^j(x₀, y), an event of type j occurs. This is exactly the definition of a Markov arrival stream [4]. A Markov arrival stream can best be interpreted as a Markov arrival process with additional marks indicating the type of event. It is shown in [4] that any marked point process can be approximated arbitrarily close with a Markov arrival stream. This shows the versatility in modeling capacities of T_env. A relatively simple example of the use of T_env can be found in Section 5, where it is used to model parallel on–off processes.

Describing formally how V_n+1 can be constructed from V_n is done in [8]. We will not repeat it here because from (1), the main ideas will be clear. With this construction, many different systems with different criteria can be modeled. The main classes of models are those in discrete time and continuous time (modeled with uniformization). The standard criteria (finite horizon, infinite horizon, discounted, and average costs) can be modeled as well. (Note that for the infinite horizon models there are existence questions to be addressed. We will not deal with them here, but will concentrate on the properties of V_n for finite n.) However, more general systems can be addressed as well, which are not time-homogeneous, which have salvage costs, and so forth.

The next step is formulating sets of functions

such that if

, then so is V_n+1 for particular choices of V_n. For these sets, we show, for some or all of the operators T introduced above, that if

, then also

. From this, it readily follows that if

and

, then also

for all n. The sets

should be chosen such that some useful results can be derived from them. The different sets

and their comparison are the subject of the next section.

Remark 2.1: In [16,8] T_CTS(i) is generalized to a continuously controlled operator of the form min_μ∈[0,1]{c_μ + μf (x − e_i + e_i+1) + (1 − μ) f (x)}, with zero as the only possible action if x_i = 0. The results of the next sections remain the same under this generalization; we have decided not to include it, as it complicates the notation.

3. INEQUALITIES

The sets of functions that we consider are defined by inequalities. Remember that our state space is (m + 1) dimensional. However, we will pose no restrictions on the environment; thus the inequalities are essentially m dimensional. The inequalities are both of first and second order. The two basic second-order properties are directional convexity and multimodularity. We start with directional convexity (dc).

Definition 3.1: A function

is called directional convex if, for all

, y₀ = z₀ = 0,

which we write as DC(y, z).

Later, when studying queuing models, it will become clear that Definition 3.1 is difficult to use in our proofs. Therefore, we derive an alternative characterization of directional convexity. To do so, we define the following inequalities for some function

, for all

, i, j ∈ {1,…, m}, i ≠ j:

The inequalities are easily interpreted: CC stands for componentwise convexity and Super(i, j) is known as supermodularity. Note that CC(i) is equal to Super(i, i).

All functions satisfying a certain inequality A for all x are denoted by

. We also write

. The set of all dc functions is denoted by

.

The characterization of directional convexity is as follows (see also [14]; for completeness, we also supply a proof).

Lemma 3.2:

.

Proof: The inclusion ⊃ follows from the definition of directional convexity: taking y = z = e_i gives CC(i) and taking y = e_i and z = e_j gives Super(i, j). The inclusion ⊂ follows by induction to [sum ]_i(y_i + z_i). If [sum ]_i(y_i + z_i) = 2, then DC(y, z) is either CC(i) for some i or Super(i, j) for some i and j. Assume that [sum ]_i(y_i + z_i) > 2 and suppose that [sum ]_i y_i > 1. Then, for some i, y can be written as y = e_i + u with u ≥ 0. Now DC(y, z) is the sum of

Both inequalities hold by induction. █

Lemma 3.2 greatly simplifies the proofs in the next section: Instead of having to prove DC(y, z) for all possible y and z, we can restrict to y and z being unit vectors.

Next, we define multimodularity. It was introduced in Hajek [6] for the study of assignment rules to a queue, its relation to monotonicity results for tandem queues was recognized in [15, top of p.295]. First, define d₀ = e₁, d_i = −e_i + e_i+1, i = 1,…, m − 1, and d_m = −e_m. Let

.

Definition 3.3: A function

is called multimodular (mm) if for all

, such that

which we write as MM(v,w).

Note that f is only defined on

. The definition makes sense because it follows from

that also

.

The usefulness of multimodularity lies in the fact that the basic transitions given in the operators are elements of

. In the next lemma, we derive a more general characterization of multimodularity, which will help us in comparing multimodularity with directional convexity.

Lemma 3.4: A function f is mm if and only if

for

, 0 < l < k, and v_i ≠ v_j for i ≠ j.

Proof: The “if” part of the proof is trivial; the “only if” part follows by induction to k. For k = 2, (2) is equivalent to mm. Consider some k > 2 and assume that (2) holds up to k − 1. Furthermore, assume that l + 1 < k. This does not restrict generality; by reordering v₁,…,v_k in descending order in the case l + 1 = k, we find l + 1 < k because k > 2. Equation (2) is equal to the sum of

Both inequalities hold by induction, the second in the state x + v_l+1 + ··· + v_k−1. █

With

, we denote the set of mm functions.

An inequality that will prove to be useful is superconvexity, introduced in [8] for the control of various two-dimensional queuing models. It is defined for all i, j = 1,…, m, i ≠ j, as

For m = 2, it is readily seen that

. For general m, we have the following.

Lemma 3.5:

for all i ≠ j.

Proof: If i < j, then SuperC(i, j) is equal to (2) applied in x + e_i with d₀ + ··· + d_i−1 = e_i and d_i + ··· + d_j−1 = −e_i + e_j. If i > j, then it is (2) applied in x + e_i + e_j with d_j + ··· + d_i−1 = e_i − e_j and d_i + ··· + d_m = −e_i. █

Next, we compare the sets of dc and mm functions.

Lemma 3.6:

.

Proof: We first show ⊂. Because of Lemma 3.2, it suffices to show for

that CC(i) and Super(i, j) holds for all i, j. We do this using Lemma 3.4. We have e_i = d₀ + ··· + d_i−1 and −e_i = d_i + ··· + d_m. Equation (2) in x + e_i gives CC(i). To show Super(i, j), assume (without restricting generality) that i < j. In addition to e_i = d₀ + ··· + d_i−1 we need −e_j = d_j + ··· + d_m and e_i − e_j = d₀ + ··· + d_i−1 + d_j + ··· + d_m. Equation (2) in y = x + e_j is equivalent to Super(i, j).

We give a function on

that is dc but that does not satisfy SuperC(1,2). Because of Lemma 3.5, this function is not mm. This function is f (x) = x₁ x₂. Verifying CC(1), CC(2), and Super(1,2) in all x is simple. It is also easily seen that SuperC(1,2) does not hold for any x. █

Remark 3.7: So far, we discussed the second-order property, directional convexity, and compared it to multimodularity. Another natural question is to compare both properties with the traditional convexity on the lattice, defined by the inequality 2f (x) ≤ f (x − y) + f (x + y) that has to hold for each

and x such that x − y,

. In [1, Thm2.2], it is shown that mm implies convexity; it is also easily seen that the function f (x) = x₁ x₂ is not convex (although we just showed in the proof of Lemma 3.6 that x₁ x₂ is dc). On the other hand, g(x) = max{x₁, x₂} is convex ([1], Counterexample 2.1), but g is not supermodular (e.g., Super(1,2) in x = 0 does not hold); thus, it is neither dc. In conclusion, if we denote with

the set of convex functions

, but there is no such ordering between

and

.

This closes the discussion of second-order properties. We continue with first-order properties. Define the following inequalities for some function

, for all

:

Inequality I(i) simply states that f is increasing (in the nonstrict sense) in i. F(i) means that it is advantageous to have customers further down the line. Note that F(i) is only defined for i < m. We introduce the notation

and

.

Lemma 3.8: If i < j, then

and, thus,

.

Proof: The proof simply consists of adding the inequalities that constitute the smaller (left hand) set in each possible state x. █

5. APPLICATIONS

We provide some applications of the comparison of models with different input processes. As a simple first application, consider two models, with value function V_n and V_n′, that are different only in the fact that the first has an operator T_A(1) and the latter has ½T_I + ½T_A(1)T_A(1). Here, T_I is simply the identity operator [i.e., T_I f (x) = f (x)] . We did not discuss it yet, but it is clear that if

for some set

, then also

. An operator that models convex combinations is easily built with T_env; thus, ½T_I + ½T_A(1)T_A(1) falls within our framework. In words, under V_n, arrivals at queue 1 are twice more likely to occur than under V_n′, but each arrival in V_n′ is a batch of size 2. Thus, the resulting load is equal. We would like to show that V_n(x) ≤ V_n′(x). Propagating this for all operators of V_n other than T_A(1) is trivial, as the same operators occur in V_n′. Thus, let us try to show

This is equivalent to

Now, assume that V_n is convex in x₁. Then,

and, thus, (3) holds. Therefore, if the value function is convex in the first component, the model with batch arrivals has greater costs. To check that the value function satisfies CC(1), we use Corollary 4.6, noting that

. This also imposes conditions on the performance measure; for example, if all service operators are controlled, then we have the condition

, which allows for decreasing direct costs. On the other hand, if the operators are uncontrolled, then we need

) or

) and, thus, the direct costs must be increasing in all components.

This example is a nice illustration of how convexity in the first state component can be used to compare systems with different arrival processes. More complex systems can be handled as well, as we show next. We consider the model of [9], in which a single queue is considered with an arrival process consisting of parallel on–off processes. In [9], the number of on–off processes is varied (while keeping the total offered load equal), and it is shown that systems with many on–off sources perform better for direct costs for which the value function is convex. See [9, Lemma3.4]. We generalize this Lemma 3.4 to tandems of queues.

To do so, we first show how to model N on–off sources (in fact, the whole value function) with the environment operator. Consider first the states. The set of all possible states of the on–off sources is {0,…, K}, representing the number of on–off sources that is on. If necessary, we could model an additional environment variable (note that a multidimensional environment can always be written as a one-dimensional environment, because the number of states remains countable), but we will not do so. By

, we denote the state of the queues. As in [9], p is the probability that an on–off source goes on and q is the probability that an on–off source goes off. When a source is on, customers arrive at a rate λ. Furthermore, assume that the service rates of queue 1 up to m are equal to μ₁,…, μ_m and assume that (p + q + λ)K + [sum ]_i μ_i = 1. Then,

Denote with V_n^K(k, x) the value function at stage n of the system with K sources. (With respect to the notation in [9], we dropped the environment variable x and replaced N, n, and k by K, k, and n, respectively.) Using the definition of T_env^K and writing T_i as a generic way to indicate the service operator at queue i, we have the following recursive expression for V_n^K(k, x):

Having modeled the tandem system with an on–off source input, we are ready to compare V_n^K with V_n¹. The equivalent of equation (20) in [9] for tandem systems, which we have to show here, is

for all x, y ≥ 0.

The comparison result follows by taking y = 0 and observing that the coefficients are proportional to the stationary probabilities of the on–off sources. Thus the comparison holds for an initially stationary arrival process. To prove (4), we first have to assume that

. We discuss those parts of the proof of (4) that are different from the proof given in [9] for a single dimension. To prove the terms related to arriving customers, we need

This holds (after cancellation of terms) by directional convexity of the value function.

To propagate the tandem servers, we have to assume that the operators are uncontrolled, thus T_MTS(i) for i < m and T_MD(m). Otherwise, it might occur that the minimizing action on the right-hand side of (4) is different. In conclusion, Lemma 3.4 of [9] and, with that, the related Theorems 3.5 and 3.6 of [9] are generalized to tandem systems with uncontrolled operators and cost functions that belong to

.

Directional convexity is also useful for certain minimization problems involving multiple systems. Here, we consider customers that have to be handled by one of a group of parallel tandem systems. The arrival stream has to be split up in a Bernoulli fashion. Convexity of the objective function allows that the global minimum can be found using a simple minimization procedure such as steepest descent. To prove this convexity, we have to show that the performance measure for a single tandem system is convex in the rate assigned to that system. We will prove this, again using directional convexity in the state. Define the operator T_A(i)^λ, for λ ∈ [0,1] , by T_A(i)^λ f (x) = λf (x + e_i) + λf (x) (with λ = 1 − λ) and let V_n^λ(x) be the value function of a tandem system with uncontrolled operators as defined in Section 2 and by T_A(i)^λ. We would like to show convexity in λ; that is,

If we assume λ₁ ≤ λ₂, then for each of these value functions, if T_A(i)^{[bull ]} occurs, then the arrivals occur with a probability in [λ₁, λ₂] . Thus, we can rewrite T_A(i)^β, β ∈ [λ₁, λ₂] , as T_A(i)^β = λ₁T_A(i) + (λ₂ − λ₁)T_A(i)^γ + λ₂T_I, with γ = (β − λ₁)/(λ₂ − λ₁). Note that if β ∈ [λ₁, λ₂] , then γ ∈ [0,1] . Thus, proving (5) for all α is, given that the standard arrival operator propagates (which is the case for all sets of functions that we considered), equivalent to proving

for all α. This inequality follows from

which we will prove for all y ≥ 0. Note the similarity with (4). Again, the only operator that is not trivial to propagate is T_A(i)^{[bull ]}; it results in

It suffices to show that the left-hand side is smaller than αV_n^α(x + y + e_i) + αV_n^α(x), which is equivalent to

which holds by the directional convexity of V_n^α. Thus, for the same systems as the last example with on–off sources, we have shown that the performance is convex in the arrival rate. This generalizes part (i) of Theorem 2.7 of [11] to multistage systems.