We first define the performance measures of interest. Consider the
non-work-conserving system. Let
nj(t) be the number of class
j arrivals in (0,t) and n(t) :=
n1(t) +
n2(t). Let the kth arrival join
queue δk, δk ∈
{1,2}. The revenue rate,
can be similarly defined. Also, xi will
denote the mean queue length in queue i and x the mean
number in the system obtained as time averages. Similarly, we will denote the
mean waiting time of a class j customer by
wj, which is obtained as a customer
average.
.
4.1. Non-Work-Conserving System
Consider the PMP system first. Define
δxj to be the queue that an
arriving class j customer to state x will join. For
example, when the system is in state x =
[x1,x2],
δx1 = 1 if
ψj(c1,x1)
≤
ψj(c2,x2)
and δx1 = 2 otherwise. The
transition rate matrix Qx =
{qx:x′} is easily
determined. The previous section contains sufficient conditions for the
ergodicity of this Markov chain, and in the following, we assume that
they hold. Let π = {πx} be the
stationary distribution of this Markov chain. The revenue rate
and the per class rate of social cost are obtained from the
Law of Large Numbers (see Serfozo [18]) as follows:
Closed-form expressions for
are difficult to obtain and we look for approximate results in the form
of computable bounds. First, consider the revenue rate,
.
We use the framework of van Houtum et al. [20] to obtain computable bounds by considering
systems on a truncated state space.
Denote the original non-work-conserving JMCQ system defined over the
state space
by
and let
{x(t)}t≥0 be the CTMC of this
system. Further, let
{xn}n≥0 be the
corresponding uniformized jump chain of the
system obtained from a uniformizing Poisson process of rate d :=
μ1 + μ2 + λ1 +
λ2 (see Bremaud [5]). Since the steady state distribution is
the same both in the CTMC and its corresponding uniformized chain, we
work with {xn}n≥0
in the rest of this section.
Let
be the indicator variable which captures the queue from which ith
customer has departed and let
be the number of departures from the system up to time t. Let
be the revenue rate accrued if each customer is charged while departing
from the system (instead of charging while entering the system). We
claim that
almost surely. We first note that the following two limits exist almost
surely:
Let {τn}n≥0 ↑
∞ be the sequence of the end of busy periods of the stable system
(i.e., return times to 0). Then, for the system that starts
empty,
for each n. Since
exist, we can divide the above by τn and take
limits along this subsequence, to have
almost surely. So, (7) can be written as, almost surely,
We rewrite (9) as
where c(x) is the revenue rate in state x
given by
Following [20], we now establish
precedences between states of
{xn}n≥0. These
precedences are defined on the basis of the n-period revenue
vn(x), which denote the expected
revenue in the first n ≥ 0 periods when starting from state
x. We say that the state
has precedence over state
,
if m and n satisfy the precedence relation
Denote the unit vectors [1,0] and [0,1] by
e1 and e2, respectively. We
claim that state m has precedence over its neighboring states
m + e1 and m +
e2 for all
.
Also, note that the ≤ operation is transitive.
Let P be the set of all ordered pair of states
(m,m + e1) and
(m,m + e2),
.
We want to prove for all n = 0,1,2,…,
We use induction over n to prove (12). Taking n = 1
in (12) leads to
We can easily verify that (13) holds. Assume that (12) holds for
n and we prove it from n + 1. To establish (12) for
n + 1, we have to show for each (m,n) ∈
P,
where p(m,n) denotes the corresponding
transition probabilities of
{xn}n≥0. From (13),
it suffices to show that
In the non-work-conserving system, we can check (15) for all
(m,n) ∈ P. A convenient method of
checking is by grouping terms corresponding to the same event (such as
an arrival or departure). The attractor lines of the different customer
classes divide the state space into many regions, and the transition
probabilities depend on the region in which the state is located. Thus,
we will have to verify (15) for the various regions. We illustrate this
for the region A3 in Figure
2. Let n = m + e1 in (15).
The left-hand side of (15) is
and the right-hand side is
Therefore, proving (15) implies proving
This is true because each term in the above inequality is nonnegative
from the induction hypothesis. Similarly, we can verify (15) for the
remaining regions.
Now, we propose two truncated systems and prove that the revenue
rates in these systems act as bounds for the revenue rate in the
system. To motivate the truncation, we argue that πx
becomes very small for states x away from the attractor lines;
hence, most of the probability mass of {πx} is
concentrated between the attractor lines and close to it and a state space
truncated at some distance from the attractors will provide a good
approximate solution. In the following, we show that if the truncation is
done such that the transition from the states on the threshold lines are
suitably modified, we can obtain bounds on the performance measures defined
earlier, which can be made fairly tight. Specifically, we will consider
the state space of the JMCQ truncated to contain only those states for
which Tl ≤ x1
− x2 ≤ Tr,
where Tl and
Tr are integers with
Tl ≤ 0 and
Tr ≥ ((1 −
a2)/a2)(c2
− c1) > 0. Tl
and Tr will be called the left and right
truncation thresholds, respectively. Denote by
the state space obtained after truncation. Also, let
be the states on the left threshold line (x1 −
x2 = Tl), except the
state [0,|Tl|].
Further, let
be states on the right threshold line (x1 −
x2 = Tr), except the
state [Tr,0], and
.
Figure 4 shows this truncation.
The truncated state space
for the
systems. The modified transitions rates for states on
are shown. The transition rates for the states between the truncation lines
are the same as that of
system shown in Figure 2. (a) Transition rates
for the
system. For states in
,
transitions due to departures from queue 1 (2) are disallowed. (b)
Transition rates for the
system. For states
,
there is a diagonal transition with a rate μ1
(μ2).
Denote the original work-conserving JMCQ system defined over the
state space
by
.
We define systems
over
as follows. For system
,
let Q(u) =
{qx:x′(u)}
be its transition rate matrix obtained from Q as follows:
From the above, for
an arrival will move
toward the attractor line of its class (the attractor lines of all the
classes are included in the truncated state space) and will not cause the
system to go out of
.
For
,
a departure from queue 1 is disallowed, whereas for
a departure from queue 2 is disallowed to keep the system in
.
Other transition rates are the same as that in
.
The transition rate matrix Q(l) =
{qx:x′(l)}
for system
is obtained from Q as follows. As with
,
the transition rates from states
are the same as that in
.
The departures from the states on the threshold lines are modified such
that a departure from one queue that might lead to a state out of
will take away one more customer from the other queue also and, hence, keep
the system state in
.
Let πx(u) and
πx(l) be the stationary
distributions of
,
respectively. For the following, we will assume that both of these systems
are stable and, hence, that their stationary distributions exist. We will
discuss the stability of these systems in Section 5.
Let
{xn(u)}n≥0
and
{xn(l)}n≥0
be the uniformized jump chains of the
systems obtained from a uniformizing Poisson process of rate d :=
μ1 + μ2 + λ1 + λ2.
For these systems, we can write the revenue rate as
In our truncation model, we observe that
{xn(u)}n≥0
is obtained by redirecting transitions to preceding states and
{xn(l)}n≥0
is obtained by redirecting transitions to succeeding states. Thus, from
Theorem 1 in [20], we have the
following result.
Theorem 3: If systems
,
start empty at t = 0, we have
Now, consider the bounds on the mean queue lengths. Choosing
c(x) = x1 in (10), we get the
expression for the mean number in queue 1: x1.
Similarly, choosing c(x) = x2
gives the expression for the mean number in queue 2:
x2. Using induction, we can again prove that
m precedes m + e1 and
m + e2. Let
xi(u) and
xi(l) be the mean
queue lengths in queue i for the
systems, respectively. Thus, we have the following result.
Theorem 4: Let xi,
xi(u), and
xi(l) exist for
i = 1,2. Then,
Further, if we take c(x) = 1 for
x1 > M and zero otherwise, where
,
then [sum ]x
c(x)πx is the tail
probability that the total number of customers in queue 1 exceeds
M. As a result, the stationary number in queue 1 in the
system is stochastically bounded between the stationary number in queue 1
of the
systems. We have a similar result for the stationary number in queue 2 in the
system. In fact, we can show that if all systems start in the same feasible
state, say (0,0), then at any jump epoch, the number in a queue of the
system is stochastically bounded by the number in the corresponding queues
of the
systems.
Remark 1: We can also show that the number in each queue of
almost surely bound the number in the
system at every jump epoch. The proof technique is similar to that used
to show such bounds for the work-conserving system, which we discuss next.
4.3. Sample-Path Approach
Let
be the CTMC of the
systems, respectively. Let
be the corresponding uniformized jump chains of the
systems, respectively, obtained from a uniformizing Poisson process of rate
d := μ1 + μ2 + λ1 +
λ2 (see [5]). Now,
consider the uniformized systems
evolving in parallel and driven by the same event sequence determined by
the Poisson process. We now present a forward induction type of proof (see
Walrand [22, Chap.8]) to show that system
(resp.
)
componentwise dominates
(resp.
)
for all n.
Let t1 < t2 <
t3 < ··· be the event
epochs of the uniformizing Poisson process. Every jump of this Poisson
process corresponds to either an arrival of class j,
j = 1,2 with probability λj
/d, or a potential service completion from queue
i, with probability μi
/d. An arrival will join the queue that minimizes its
cost, possibly different queues in different systems. The
work-conserving property leads to the following queue dynamics at
potential service completion instants. A potential service completion
time from queue i is an actual service completion from that
queue if it is nonempty, and it is an actual service completion in the
“other” queue if queue i is empty and the other is
nonempty. Because the service and interarrival times are exponentially
distributed, we just disallow departures when actual departures are not
possible at potential departure times. Let
be the state of
“just after” tn and let
be the sample path of
up to time tN+. Reference
[22] has more details on the
development of the sample paths. Denote the evolution paths by
in the
system and by
in the
system and let
.
Theorem 5: If the system starts empty at k = 0,
then for any k ≥ 0,
Proof: Assume that (a) and (b) have not failed till
tk. Both (a) and (b) cannot fail for the
first time simultaneously and we consider the events that might lead to
them failing separately. We will consider (a) alone first. For (a) to
fail before (b) at tk′+1, we require that
.
We consider the possible events at
tk′ with this condition. If the
event at tk′ is a potential
departure, the following subcases arise:
1. Potential departure from queue 1: Because
will behave identically with respect to queue 1 when
.
If
,
a departure from queue 1 is disallowed in
and allowed in
,
and (a) is maintained.
2. Potential departure from queue 2:
is necessary to cause an actual departure from queue 1. By
assumption that (b) has not failed until
tk′,
implying
.
will behave identically with respect to queue 1.
Now, consider the case when the event at
tk′+1 is an arrival. For (a) to
fail, the arrival must join queue 1 in
and queue 2 in
.
For this to happen,
must be on the right-hand side of the attractor line for the class of
the arrival, and
must be on its left-hand side. This is clearly not possible because
and the attractor line has a positive slope.
Similar arguments show that (b) cannot fail before (a) at
tk′+1.
Now, consider (c) and (d). Once again, they cannot fail for the first
time simultaneously. We proceed as above and look at events at
tk′+1 when
,
which is required for (c) to fail for the first time and before (d) at
tk′+1.
As previously, first consider a potential departure at
tk′:
1. Potential departure from queue 1: Because
will behave identically with respect to queue 1 when
.
If
,
an actual departure takes place from both the queues in the
system and the inequality is maintained.
2. Potential departure from queue 2:
is necessary to cause an actual departure from queue 1 in
.
However, by assumption that (d) had not failed until
and, hence,
.
will behave identically with respect to queue 1.
For an arrival of class j at
tk′+1, arguments identical to that
from the first part are used to show that (c) does not fail at
tk′+1.
Similar arguments are constructed to show that
could not have happened at tk′ and,
hence, (d) could not have failed before (c) for the first time at
tk′+1. █
Let
be the mean queue lengths in queue i for the
systems, respectively. Also, let
be the mean waiting times in queue i of the
,
and the
systems, respectively.
Theorem 6: Let
exist for i = 1,2. Then,
for i = 1,2, where λi
is the long-run arrival rate into queue i in the
system.
Proof: From Wolff [23],
systems are regenerative and, hence, the mean queue lengths are also time
averages. Hence,
Similarly we can prove the left half of (a).
From Little's law, we write (b) as
Dividing throughout by λi, we get
(b). █
Now, we find the bounds on the revenue rate. In this case, we choose
Tl = 0 and, hence, the left truncation
threshold is the line
.
The revenue processes in
are modified as follows. The
systems will earn revenue exactly like the
system, except for the following cases. We stipulate that when the system is
in a state in
will “gain revenue” (c2 −
c1) and
will “lose revenue” c1 according to the rate
μ2. When the system is in a state in
,
only
will “lose revenue” c2 according to the rate
μ1. Let
be the revenue rates so earned in systems
,
respectively. Then, from the Law of Large Numbers,
Observe that the expressions for
are similar to that for
in (17) except that they are defined on the corresponding
systems, respectively, and the “revenue earnings” are modified for
the states on the threshold line as discussed in the previous paragraph. Let
denote the cumulative revenue in
,
respectively, until time tN.
Theorem 7: If the
systems start empty at time t = 0, then for all N ≥
0,
Proof: Let
be the revenue “earned” in the transition at
tk+1 from
in the
system. We can write the left-hand side of Eq. (22) as
We will show that the following holds for all
tk, the epochs of the uniformizing
process:
For an arrival at
.
A similar expression is written for
and (24) is satisfied. Now, consider potential departures. We consider
four cases corresponding to the state of the queues in
.
Case 1: Both queues are empty. Irrespective of the state of
,
the first term on the right-hand side of (24) is
zero, the second term is nonnegative, the left-hand side is zero, and
(24) is satisfied.
Case 2: Queue 1 is empty and queue 2 is nonempty. This
cannot happen because we choose Tl = 0 in
our truncation of the state space.
Case 3: Queue 1 is nonempty and queue 2 is empty. For a
potential departure from queue 1, queue 1 in
is also nonempty and there is an actual departure from queue 1 in both
and (24) is satisfied. For a potential departure from queue 2, the
following subcases need to be considered:
1. Queue 2 in
is empty. By Theorem 5, queue 1 in
is necessarily nonempty. There will be an actual departure from queue 1
(because of work-conserving service) in both
and (24) is satisfied.
2. Queue 2 in
is nonempty. This means that there will be an actual departure from queue 1 in
and an actual departure from queue 2 in
.
In this case, the left-hand side in (24) is zero and the right-hand side is
c2 − c1 and the inequality is
satisfied.
Case 4: Both queues are nonempty. In this case, both queues of
will be nonempty by Theorem 5. First, consider a potential departure from
queue 1 (resp. queue 2). If
is not on the left (resp. right) truncation threshold, then in both the
systems, there is an actual departure from queue 1 (resp. queue 2) and (24)
is satisfied. If it is on the left (resp. right) threshold, left-hand and
right-hand sides will both be −c2 (resp.
−c1) and the inequality of (24) is
satisfied.
Thus, the inequality of (24) holds, and substituting (24) in the
right-hand side of (23), we get (22) if we start from an empty system.
█
To obtain upper bounds on the cumulative revenue, consider the
systems together. Let
(resp.
)
be the revenue earned in the transition from
(resp.
)
in the
(resp.
)
system at time tk+1.
For an event of the uniformizing process at time
tk, the difference in the behavior between the
systems depends on the slope of the line joining the points
(state of
at tk) and
(state of
at tk). To capture the dependence on this slope,
let
.
The slope of the line joining the points
is less than (resp. greater or equal to) one if τk
< 0 (resp. τk ≥ 0).
A sequence τ1,…,τN can
be associated with a joint sample path in
for epochs t1,…,tN.
Let G = (V,E) be the directed graph induced
by this sequence, where the vertex set V is obtained from
{τk} (τk takes values in
)
and the directed edge set E = {ek =
(τk,τk+1)}. In the
following, our discussion will be based on a graph so obtained from a
sample path. For every ek ∈
E, define lk :=
τk+1 − τk and
.
We will call lk the length of
ek and call
wk its weight.
wk is the excess revenue earned by
over
due
to the event at time tk. Also, define
Sm,n :=
{ek ∈
E|τk =
m,τk+1 = n}; that is,
Sm,n is the set of all directed
edges from
.
Figure 5 shows an example of the
directed graph induced by the τk from a sample
path of the
systems.
Example sequence of τk from a sample path
represented as a directed graph. For clarity in the illustration, self
loops are not shown, as these do not have negative weights. The
remaining edges are renumbered such that their initial order is
maintained. In the example shown, m = 1 and m = 3
have edges with negative weights. Observe that the terms in (25)
corresponding to these states are “canceled” as follows:
[sum ]ek∈S1,−1
wk +
[sum ]ek∈S−1,1
wk +
[sum ]ek∈S1,0
wk = 0 and
[sum ]ek∈S3,1
wk +
[sum ]ek∈S2,3
wk = 0.
Now, consider the possible combination of events in
at epoch tk. They are listed in Table 1 along with the sign of
τk and τk+1 and the
values of lk and
wk. From Table
1, we see that lk ∈
{−2,−1,0,1,2}, wk is negative
only due to events of type 2 (an arrival chooses queue 1 in
and queue 2 in
),
and if wk is negative, then
τk > 0 and lk =
−2. Further, lk > 0 and
τk+1 > 0 are possible only from two events,
those of type 3 and 12. A type 3 event is an arrival joining queue 2 in
and queue 1 in
.
A type 12 event is a potential departure from queue 2 when
is on the right threshold and is, hence, disallowed and an actual
departure from queue 2 in
.
In this case, wk = c2
− c1 and lk = 1.
We are now ready to state the following theorem.
Combinations of Possible Events in
at Epoch tk+1 and the Corresponding
τk, τk+1,
lk, and
wk
Theorem 8: If
start empty at time t = 0, then for all N ≥
0,
Proof: We can write
We will use the sample-path graph G obtained as described
earlier. To prove the theorem, we show that those
Sm,n containing
ek for which
wk = (c1 −
c2) < 0 are offset by edges with
wk > 0 in (25). From Table 1, these sets will be of the form
Sm,m−2, with m
> 0. Consider one such vertex, say m, and let there be
r edges,
{ek1,ek2,…,ekr},
from m to m − 2 with negative weights. This
means that
[sum ]ek∈Sm,m−2
wk ≥ r(c1
− c2). Without loss of generality, we can
assume that k1 < k2 <
··· < kr. Consider
the two possibilities that arise.
Case 1: m = 1. Observe that τ1 = 0
and τk1 = 1. This guarantees that
there must be a right-directed edge ek, an
edge ek with
lk > 0, with 0 < k <
k1 into vertex 1. Now, consider the edge
ekl from 1 to −1
with l > 1. Since
τkl+1 = −1 and
τkl+1 = 1, there must be a
right-directed edge ek into vertex 1 with
kl < k <
kl+1. The right-directed edges obtained
above are due to transitions at different time epochs and, hence, are
distinct. This shows the existence of at least r
right-directed edges into vertex 1. There are two types of
right-directed edge into vertex 1, edges due to events of types 3 and
12, each of which have wk =
c2 − c1. See Table 1. Thus,
Case 2: m > 1. Arguing as in Case 1, we can show
that there are r right-directed edges into vertex m.
The only possible right-directed edges into vertex
m,m > 1, is due to an event of type 12. So,
[sum ]ek∈Sm−1,m
wk ≥ r(c2
− c1) and
See Figure 5 for an illustration of both
cases.
For both of the cases, (25) can be written uniquely split into sums
as in (26) and (27) and the theorem follows. █
The stationary revenue rate
defined in (17)
becomes, by the Law of Large Numbers,
and from Theorems 7 and 8, we can now state the following theorem.
Theorem 9: If systems
start empty at t = 0, we have
