We first consider the stability conditions for the T1 and T2 policies. In the T1 policy, higher values yield the larger stability regions, and in the limit as , the queues under the T1 policy are stable as long as and . In contrast, the T2 policy guarantees stability whenever and for any finite . The T2 policy clearly dominates the T1 policy in this respect. The stability conditions under the T1 and T2 policies are illustrated in Figure 7.3.
More formally, the necessary and sufficient conditions for the stability under the T1 and T2 policies are given by the following theorems.
Proof:We prove only the case when and . The case when or can be proved in a similar way. Let be the joint process of the number of jobs in queue 1 and queue 2, respectively. The expected length of a ``busy period,'' during which , is finite if and only if . This proves the stability condition for queue 1.
Based on the strong law of large numbers,
the necessary and sufficient condition for
stability of queue 2 is ,
where denotes the time average fraction of time that server 2
processes jobs from queue 2 given .
Below, we derive .
be a process
in which behaves the same as except that
it has no transition from
Consider a semi-Markov process of
where the state space is (0,1,2,...,,).
The state denotes there are jobs in queue 1 for
and the state denotes there are at least jobs in queue 1.
The expected sojourn time is
for state 0,
for states ,
for state ,
is the mean duration of the busy period in an M/M/1 queue with arrival rate
and service rate
The limiting probabilities for the corresponding embedded discrete time Markov chain