Case 1: $c_1\mu _{12}\leq c_2\mu _2$

We first consider the case where $c_1\mu _{12}\leq c_2\mu _2$, where server 2 ``prefers'' to run its own jobs in a $c\mu$ sense. In this case, we will see that the T1($\infty$) policy typically minimizes mean response time in the class of T1 policies, and the T2(1) policy typically minimizes mean response time in the class of T2 policies. Note that the T1($\infty$) policy and the T2(1) policy are identical, and they also coincide with the policy of following the $c\mu$ rule when $c_1\mu _{12}\leq c_2\mu _2$. Note also that if $T_1=\infty$ minimizes the mean response time of the T1 policy, $T_1=\infty$ is the optimal choice with respect to both mean response time and stability region, since $T_1=\infty$ maximizes the stability region of the T1 policy (see Corollary 4). Likewise, if $T_2=1$ minimizes the mean response time of the T2 policy, $T_2=1$ is the optimal choice with respect to both mean response time and stability region, since the stability region of the T2 policy is independent of its parameter $T_2$ (see Theorem 15).

In fact, when $c_1=c_2$ (and $c_1\mu _{12}\leq c_2\mu _2$), the following theorems hold (the theorem may extend to the case of general $c_1$ and $c_2$ with $c_1\mu _{12}\leq c_2\mu _2$, but the general case is not proved).

Theorem 16   If $c_1=c_2$ and $c_1\mu _{12}\leq c_2\mu _2$, the mean response time of the T1 policy is minimized at $T_1=\infty$.

Proof:Due to Little's law, it is sufficient to prove that the number of jobs completed under the T1($\infty$) policy is stochastically larger than those completed under the T1 policy with $T_1<\infty$ at any moment. Let $N^{\rm inf}(t)=(N_1^{\rm inf}(t),N_2^{\rm inf}(t))$ be the joint process of the number of jobs in queue 1 and queue 2, respectively, at time $t$ when $T_1=\infty$. Let $N^{\rm fin}(t)=(N_1^{\rm fin}(t),N_2^{\rm fin}(t))$ be defined analogously for $T_1<\infty$. With $T_1=\infty$, server 2 processes type 2 jobs as long as there are type 2 jobs, and thus $N_1^{\rm inf}(t)$ is stochastically larger than $N_1^{\rm fin}(t)$ for all $t$. Consequently, the number of jobs completed by sever 1 is stochastically smaller when $T_1<\infty$ than when $T_1=\infty$ at any moment, since server 1 is work-conserving.

As long as server 2 is busy, the number of jobs completed by sever 2 is stochastically smaller when $T_1<\infty$ than when $T_1=\infty$, since $\mu_{12}\leq \mu_2$. Also, using coupling argument, we can show that the system with $T_1=\infty$ has server 2 go idle (both queues empty) earlier (stochastically) than the $T_1<\infty$ system. Thus, when server 2 is idle the number of jobs completed by the $T_1=\infty$ system is stochastically larger. Thus, the number of jobs completed (either by server 1 or by server 2) under the T1($\infty$) policy is stochastically larger than that completed under the T1 policy with $T_1<\infty$.     width 1ex height 1ex depth 0pt

Theorem 17   If $c_1=c_2$ and $c_1\mu _{12}\leq c_2\mu _2$, the mean response time of the T2 policy is minimized at $T_2=1$.

Theorem 17 can be proved in the same way as Theorem 16: in the proof of Theorem 17, the T1 policy with parameter $T_1=\infty$ is replaced by the T2 policy with parameter $T_2=1$, and the T1 policy with parameter $T_1<\infty$ is replaced by the T2 policy with parameter $T_2>1$.

Figure 7.4: The mean response time under the T1 policy as a function of $T_1$ (rows 1 and 3) and the mean response time under the T2 policy as a function of $T_2$ (rows 2 and 4) when $c_1\mu_{12}=c_2\mu_2=1$ and $c_1\neq c_2$. Here, $\rho_2=0.6$ are fixed.

Mean response time of T1 and T2: $c_1\mu_{12}=c_2\mu_2=1$ and $c_1\neq c_2$

$c_1=1$ and $c_2=4$

T1

T2

$c_1=4$ and $c_2=1$

T1

T2

(a) $c_1\mu_1=\frac{1}{4}$

(b) $c_1\mu_1=1$

(c) $c_1\mu_1=4$

Further, even when $c_1\neq c_2$ (and $c_1\mu _{12}\leq c_2\mu _2$), our analysis of the T1 and T2 policies via DR shows that the T1($\infty$) policy minimizes mean response time in the class of T1 policies, and the T2(1) policy minimizes mean response time in the class of T2 policies, for all the cases we have considered. Figure 7.4 shows a subset of such numerical analyses, where $c_1\mu_{12}$ and $c_2\mu_2$ are chosen to be the critical case: $c_1\mu _{12}=c_2\mu _2$. In the top half, $c_1=1$ and $c_2=4$, and in the bottom half, $c_1=4$ and $c_2=1$. Different columns correspond to different $\mu_1$'s. In each plot, mean response time is evaluated at three loads, $\hat\rho_1 = 0.8, 0.9, 0.95$, by changing $\lambda_1$. Although figures are not shown, when $c_1\mu_{12}<c_2\mu_2$, the mean response time under non-optimized T1 and T2 policies becomes much higher than the optimized T1 and T2 policies (T1($\infty$) and T2(1)), as compared to the case of $c_1\mu _{12}=c_2\mu _2$. This makes intuitive sense, since non-optimized policies have a bias toward jobs with smaller $c\mu$ values (less important and/or larger jobs).