Optimal Stochastic Scheduling of a 2-Stage Tandem Queue with Parallel Servers Hyun-Soo Ahn Department of Industrial and Operations Engineering University of Michigan, Ann Arbor, Michigan Izak Duenyas Department of Industrial and Operations Engineering University of Michigan, Ann Arbor, Michigan Rachel Zhang Department of Industrial and Operations Engineering University of Michigan, Ann Arbor, Michigan Technical Report 97-14 November 24, 1997

Optimal Stochastic Scheduling of a 2-Stage Tandem Queue with Parallel Servers Hyun-Soo Ahn, Izak Duenyas1, and Rachel Zhang Abstract We consider the optimal stochastic scheduling of a two-stage tandem queue with two parallel servers. The servers can serve either queue at any point in time and the objective is to minimize the total holding costs incurred until all jobs leave the system. We characterize sufficient and necessary conditions under which it is optimal to allocate both servers to the upstream or downstream queue. We then conduct a numerical study to investigate whether the results shown for the static case also hold for the dynamic case. Finally, we provide a numerical study that explores the benefits of having two flexible parallel servers which can work at either queue versus servers dedicated to each queue. We discuss the results' implications for cross-training workers to perform multiple tasks. 1. Introduction In this paper, we consider stochastic scheduling of a two-stage tandem queueing system with two parallel servers. The objective is to minimize the sum of the holding costs incurred until all jobs in the system at time zero are processed and leave the system. Despite the fact that tandem queueing systems are prevalent in many manufacturing, and communications systems, there have been few papers focusing on the analysis and control of these systems. In manufacturing, these systems arise in a variety of practical situations including Corresponding author: Department of Industrial and Operations Engineering, The University of Michigan, 1205 Beal Avenue, Ann Arbor, MI 48109-2117, ducnyash;,aumich.cdu. 1

worksharing systems with fewer servers than machines, (e.g., Bartholdi et al. 1995, McClain et al. 1997). However, very little is known about the optimal control of tandem queueing systems with multiple servesrs. Among the few works which have considered optimal control of tandem queueuing systems with multiple servers, Rosberg, Varaiya and Walrand (1982) and Hajek (1984) considered a two station tandem queueing system with one flexible server (rate u) and one fixed server dedicated to queue 2 (rate 2 ). Farrar (1993) considered the case of a tandem queue with one fixed server for each stage and one flexible extra server which can be turned on and off. He showed that the control of the extra server can be characterized by a switching curve. He also showed that the optimal allocation policy of an extra server is transition monotone when c <c. Pandelis and Teneketzis (1994a) analyzed optimal multi server stochastic scheduling of two interconnected queues and considered conditions under which exhaustive policy at the first queue is optimal. They showed that there is a sufficient condition described in terms of holding costs and the stochastic ordering of the service time distributions. This paper is very similar to ours; however it differs in several key areas: Our analysis assumes exponential processing times and also we assume that all jobs leaving queue 1 go to queue 2 and therefore our assumptions are less general than theirs; however under our more restrictive assumptions, we are able to derive sufficient and necessary conditions under which exhaustive policy at either queue by both servers is optimal, whereas they only derive sufficient conditions under which it is optimal to allocate both servers to the upstream queue. We further discuss the difference between the results obtained here and in the Pandelis and Teneketzis paper in the beginning of Section 5. In other work on tandem queues, which allows for only a single server, Van Oyen and Teneketzis (1994) considered the control problem of forest networks attended by a single server with switching costs. Iravani et al. (1995) provided a performance analysis of two stage tandem queueing systems attended by a moving server with holding and switching costs, and Iravani et al. (1996) extended the analysis to N-stage tandem queues attended by a moving server. Duenyas et al. (1995) also focused on single flexible server tandem queues and provided a partial characterization of the optimal control policy and some heuristic control rules. In a different context, Weber and Stidham (1987) focused on problems where each queue in a tandem queueing system is allocated a single server but the decision maker can set the optimal service rate (where there is an operating cost associated with higher service rates). Although there have been a few studies in optimal control analysis of systems of queues attended by multiple servers, these studies in general do not focus on tandem queues. Ross (1983) considered the minimization of makespan in a 2-stage tandem queue with 2 servers. (In contrast, we focus on the total expected cost 2

objective). Chang et al. (1991) focused on minimizing the expected weighted total cost of two classes of exponential jobs on multiple processors. They proved that in the optimal policy, there exists a switching curve that changes from the ctu -rule to the LEPT rule based upon the number of jobs in the system. Kampke (1987, 1989) derived conditions under which priority rules such as the cu rule and LEPT rule are optimal in multiserver problems. Other recent references on stochastic scheduling problems (none of which focus on the scheduling of multiple servers on tandem queues) include Agrawal, Hedge and Teneketzis (1990), Gittins (1989), Hofri and Ross (1987), Pandelis and Teneketzis (1994b), Pinedo(1995), Stidham and Weber (1993), Van Oyen and Teneketzis (1992,1996). The rest of this paper is organized as follows. In Section 2, we provide the problem formulation and show that the optimal policy can be complex. Section 3 contains our main result; mainly, the necessary and sufficient conditions under which it would be optimal to allocate both servers to queue 1 or queue 2 under the assumption of exponential processing times. The analysis in Section 3 is performed under the assumption that the two servers are never allowed to idle. In section 4, we prove that only non-idling policies can be optimal for the original problem. Therefore, the results derived in Section 3 also hold for policies where the server is actually allowed to idle. Section 5 is devoted to a numerical study which provides empirical justification for a conjecture that the results derived in Section 3 (for the static problem where the objective is to minimize the total expected cost until all jobs clear the system) also hold for the dynamic version of the problem (where the objective is the minimization of the average cost per unit time). In Section 5, we also focus on the actual benefits of having two flexible servers rather than one server dedicated to each queue, and show that this benefit can be large. 2. Problem Formulation We consider a 2-stage tandem queue where all jobs leaving queue 1 immediately join queue 2. Jobs whose processing is completed at queue 2 leave the system. Initially, there are n1 and n2 jobs in the upstream and downstream queues respectively, and we assume that no external arrivals to the system will occur at any time. The system has two identical servers and the servers can process jobs at either queue at any point in time. Processing times at queue 1 (2) by either server are assumed to be exponentially distributed with mean u-1i (21 ). Once a service begins, it can not be preempted. At any point in time, each one of the servers is either 3

processing a job from queue 1 (PF ), processing a job from queue 2 (P2 ) or has completed processing a job from either queue and is ready to process a new job (which, we denote by state R). There is a positive holding cost h, per job per unit time incurred for holding jobs in queue 1 and a holding cost h2 per job per unit time incurred for holding jobs at queue 2. The objective is to minimize the expected total holding costs incurred until the system clears all of the jobs present at time 0, i.e., to minimize the expression EJ (hlnl (t) + h2n2 ())dt where ni (t), i = 1 and 2, are the number of stage i jobs in the system at time t, and n (0) = ni, = 1 and 2. We will focus on both the non-idling version of the problem where the servers are never allowed to idle unless they have no jobs to work on and also the version where the servers are allowed to idle. We will first focus on the non-idling version of the problem, and then in Section 4, we will show that even when the servers are allowed to idle, it is in fact never optimal to idle unless the servers have no more jobs to work on. We first focus on the non-idling version of the problem. Using the fact that neither server will idle unless it has no more jobs to process, we can formulate the problem of minimizing total expected costs until all jobs clear the system as a Markovian Decision Process. We let (i, j,X,,X 2) be the state of the system, where i denotes the number of jobs in queue 1 and j denotes the number of jobs in queue 2. The vector (XX, X2) denotes the status of each machine where XJX2, P, P2, R}. We note that since the machines are identical, we do not have to distinguish between the machines (i.e., (X1, X2) = (X2, X) ). We define V(i, j, X, X2 ) as the minimal expected total cost incurred until the system is emptied, and let V(0,0, X,, X2) = O. Since only nonpreemptive policies are allowed, at any point in time (except time zero), we only need to make allocation decisions (of allocating a machine to queue 1 or queue 2) for at most one machine. Thus for 0 < i < n,0 < j < n2 + nI - i, the value function, V(i, j, X,, X2 ) satisfies the following dynamic programming equation. V(i, j.P, R) = V(i, j,R,P ) miP ) for i22, j2 V(i, j,,R)=V(ijRPn)= min{V(1 jPI,P) for i>1,j>2 v (i, jP: R ~, R r) - i y(, jR, P 2)J -mi'2( *:, p)_ V(i,O,P, R) =V(i,O,R, P )=V(i,O,P, PI) for i22,j=0 V(i,l,P2,R) = V(i,,R, P2) = V(i,l,P, P2) for il,j = 1 V(l, j,P,R)=V(1, j P2,R)=V(: jP,,P2) for i=l,j>l V(O, j,P2,R) = V(O,j,R,P2) =V(O,j,P2,P2) for i=0, j>2 4

V(i, j, p i, PI ) + jh2 - +V(i - 1, j + 1, P, R) 2P, V(i, j, P,, P2)=ih + V(i-l+ R) F(/, + ~ v~ - 1, + (-1, j, + \P V(i, j - 1,P,,R) P, +/2 P, +/2 P, +/2 V(i, j, P2,P )=ih + jh2 V(i, -1, P,R) 2/2 hi h V(1,0, PI, R) =- + V(,1, P, R), V(O,1, P,R)= 2 P1 /2 At time zero, we assume that we can choose the allocation for both machines, and we have y(,l, "2,n2)= mm{PI, V(n 1,n2,RR) mm {V(nln2,P2,R) (Pn1,P2,) Fig8 1. An exampe of te o l p y. 7 ': ~~~~.optimal policy can be, consider the following example with. = -. =., h. =.-1 and.. = 1.995. The optimal.. 6.,. ';;;:// 5............:............:.:::::::::::::::.::::::::::..::::: 4 1 W @ 9........................... 3 (P )..... -!...... 21......-..' —:~...... 0 1 2 3 4 5 6 7 8 9 n2 Figure 1. An example of the optimal policy. optimal policy can be, consider the following example with,u, =,2 = 1, h2 = 1 and h1 = 1.995. The optimal policy when there are two servers available is shown in Figure 1. As the figure indicates, the policy is rather queue; however, when the number of jobs in queue 1 increases to 7; (i.e., in state (7,2)), it in fact becomes optimal to allocate both servers to queue 2. However, intuition suggests that if the holding cost for holding jobs 5

in queue 1 is sufficiently higher than the holding cost for holding jobs in queue 2, it would be optimal to allocate both servers to queue 1 and vice versa. In the next section, we present the main result of the paper which state the necessary and sufficient conditions for the optimality of allocating both servers to queue 1 or queue 2. 3. The Main Result The main result of the paper is expressed in the following Theorem which states the necessary and sufficient conditions for the optimality of exhaustive service, by both servers at either the upstream or downstream queue. Theorem 1: (A) The optimal policy always allocates both servers to queue 2 as long as there exist unserved jobs at queue 2 at all states (iij) if and only if hi < I1 + ' -- h2. /i1 + 12) (B) The optimal policy always allocates both servers to queue 1 as long as there exist unserved jobs at queue 1 at all states (ij) if and only if h, (1 + 2 )h2. Proof: We give the detailed proofs for the sufficiency and necessity conditions of part (A). For part (B), only the necessity part is shown in detail, since the proof for the sufficiency condition is similar to the proof used in part (A). We provide the proof for part (A) in Section 3.1 and the proof for part (B) in Section 3.2. 3.1 Proof of Theorem 1 part (A). In this subsection, we will prove that if and only if the condition, hi < (1 + ~2 /(/A + 32 ))h2, which we will refer to as condition (A), holds then it is optimal to allocate both servers to the downstream queue (queue 2). We will use induction and direct evaluation of the value function at the boundaries to prove sufficiency. We will first prove two technical propositions and then use these propositions to prove sufficiency. Necessity will be shown by contradiction. 6

Proposition 1. Under condition (A), V(1, j,P2, R) = mmn V(1, j, P, P2),V(1, j, P2, P2)}= V(1, j, P2, P) and ZI (1 =j) = V(l, jP,,P2) - V(l,ij,P2,P2) - V(l, j - l,P,,R) + V(, j - 1,P,R) > 0 for all j > 2. Proof: The result will be shown by induction. First let j=2. For the induction basis of the first claim, it suffices to show that V(1,2,P,,P2) > V(1,2, P2, P2) since V(1,2,P2,R) = min{V(1,2, PI, P2), V(1,2, P2, P2)}. Using the fact that V(0,3, P,,R)= 3h2 /(2u2 ) + V(0,2, P2,R)and V(1,1, P,,R) = V(1,1, P2, R) = V(1,1 PI, P2), we get V(1,2,PIP2) - V(1,2,P2, P) =h +2h2 h +2h2 + l [v(0,3,P2,R)-V(II,P2,R)]+ h2 [V(l,l,P2,R)-v(IrP2,R)] P1 + 1+2 2/'2 +2 1+ 2 hi +2h2 h1 +2h2 + 1 3h2 h 1 h2(2P2 +Pl)- hl(ul +a2). /1 + /2 2/2 /a +/2 L2/2 P1 242(/1 ++/2) where the last inequality follows directly from condition (A). For the induction basis for the second claim, using the fact that V(1,1, P, R) = V(1,1, P2, R) = V(1,1, P,, P2) and the fact (shown above) that V(1,2, P1, P2) - V(1,2, P2, P2 ) is nonnegative, we have Z, (1,2) = V(1,2, P, P2) - V(1,2, P2, P2) - V(1,l, P,, R) + V(1,1, P2, R) > 0. Now to continue the induction, suppose that V(l, j', P2,R)= V(l, j', P2, P2) and Z, (l,j')> O for all j' j. Then at (1, j +1), using the fact that V(O,j + 2,P,R)=(j + 2)h2/212 +V(O,j +1,P,R) and using the induction hypothesis V(1, j, P1, P2) - V(1, j, P2, P2) > 0 give us, V(l, j + 1, P, P2)- V(1, j + 1,P2, P2) h 1 + ( 2 2h,2 (I +,2 j+l + 2 hl + (j +l)h2 h, +( +l)2 Pl F(j + ~2)h, h, +jh h+1I (+ 22 h + h2 PI + P/2 22 PI ^+ 12 2t2 2]2 + /P [V(0, j+ 1, P2,R) - V(l,j - l,P2,R)]+ /P 2 [V(, j,i~,R) - V(1,, P2,R) It also follows from the induction hypothesis that -- [V(0, j + 1,, R) - V(1, j -1, P2, R)] Pi +8 P2 h h + h.....(3.1.2) =h +jhl 2 h + jh2 _ 2 [V(l, j-l,PR)-V(1, j-l,P,R)]+V(1,j,P,, P2)- (1,j, P2,P2) I1 + /2 2P2 P1 + 2 After substituting (3.1.2) into (3.1.1), we have 7

V(, j +, P1, P2) - V(1, +, P2,P2) _A2 212h2 + l(h2 -hl) =V(1,j, P1,R) - V(1,j,P2,R) + [V(, j, P1,P2)-V(,, P2,P2) + V(, j - 1,P2,R) - V(l,j- 1,P,R)]+ A1 + P2 2/2 (1 + #2) /2 2 h2 + 1l(h2 - h) = V(1, j, P1,R)- V(1, j, P2,R) + Zl(1, j) + 1I + 22 2P2(A1 + /2) > V(1, j, P,R)- V(, j, P2, R) = V(,, PI, P)- V(1, j, P2, P2) > 0 where the last inequality follows from condition (A) and the induction hypothesis that Z1 (1, ) is nonnegative. This completes the proof of the first part of the proposition. To show Z. (1, j + 1)> 0, note that in the last argument we also showed (in the last inequality above) that V(1, j + 1, PI, P2 ) - V(1, j + 1, P2,P2 ) > V(1, j, P, P2) - V(1, j, P2, P2). It therefore follows that Zl (1 + j + 1) is nonnegative as well. Proposition 2: Under Condition (A), for all i > 2, and all j 2, the following are true: i) a) V(i,j - 1,P,R) = V(i, j - 1, P1,P2 ) and b) Z2(Ji j-l)= VOji- PIIPI)-V(i" j-11 PIP2)+V(i -1, jP2 R)-V(i-l1 j\P,,^R)2. ii) a) V(i,j,P2 R) = V(i, j, P2,P2) and b) Z (i,j) = V(i,j, P,P2) -V(i,j,P2,P )-V(i, j - l, P, R) +V(i,j- 1, P2,R) 0. Proof: We will show these results by the induction on both i and j. We separate the proof into four parts. We first prove the results for (i, j) = (2,2). Then we prove that the results hold for i = 2 and all j 2. Then, we prove that the results hold at state (i,2) for all i > 2. And finally we prove that the results hold for all (i,j). Part 1 (i = 2, j = 2): To provide the induction basis, let us start with(i, j) = (2,2). To show i.a), we note V(2,1, P,R) =min {V(2,1, P,,P ),V(2,1, P,P2) and we have, 2h + h2 2h + h2 I r 2 r V(2,1, P, P1 ) - V(2,1, PI, P2 ) [V(1,2, P1, R) - V(1,2, P2, R)] + I (1,2, PI, R) - V(2,0, P, R)J 2/1 A1 + P2 P1 + l2 A1 + 2 2h= - 2h- + h [V(1,2, P,R) - (1,2, P2, R)]+ [(1,2, P2, R) - (2,0, P, R)] (3.1.3) 2/1 /1 + P2 /1 + /2 8

Noting the fact that V(2,0, P,,R) = 2h, /2,u1 + V(l,l, P, R), and V(l,2,P2, R)= (h1 + 2h2)/(2P2) + V(l,l, P2, R) (from Proposition 1), after substitutions, we get V(2,1, P1, P ) - V(2,1, P, P2 ) 2h1 + h2 2h1 +h2 2 h +2h2 2h] 2/1 P /1+/ 2 + I +2 L 2P2 212/ + 12 [V(1,1, P2, R) - V(l,l, P1, R)] + [V(l,2, P1, R) - V(1,2, P2, R)] P/1 + /2 Note that V(1,1, P2, R) = V(1,1, P,, R) = V(1,1, P1, P2).Thus, we have the following; V(2,1, P,, P,) - V(2,1, P1, P2 ) =l2h2 + Al (h2 - hl) + [V(1,2, P,,R) - V(1,2,P2,,R)] (3.1.4) 2/1 (1 +/ 2 ) > [V(1,2, P, R) - V(1,2, P2, R)] = V(1,2,P,,P2)- V(1,2, P2,P2) >0. From (3.1.4), we also get V(2,1, P1, P,) - V(2,1, P,, P2) + V(1,2, P2, R) - V(1,2, P,R) = Z2 (2,1) > 0. which also proves i.b). To prove ii.a), we first note that V(2,2, P1, P2) - V(2,2, P2, P2 ) 2h/i +2h2 2h1 +2h2 /Ud _1___3 _ P2 2h, +2h2 2h, + 2h2 + ~ [V(0,3, P,R) - V(2,1, P2, R)]+ [V(2,1, P,,R) - V(2,1, P2, R)] Pi + #2 2#2 pi + #2 Pi +/a2 2h1 +2h2 2/a ++2h2 pi 2h,7 +2h2 _2h, +2h= + a [V(1,3, P,R)-V(2,1, P,,R)+[V(2,P R) - V(2,1, P, R)l (3.1.5) p1 + P2 2#2 pi + #2 From condition i. a), we have V(2,1, PR)=V(2,1, P,) [2h +h2]+ V(1,2, PR)+ 2 V(2,0, P,,R). (3.1.6) Pi +l2 P1i +/a2 A1i + P2 Also from Proposition 1, V(1,3, P, R) = V(,3, P2, P) = [h, + 3h, ]/(2u ) + V(1,2, P2,,R). (3.1.7) Substituting (3.1.6) and (3.1.7) into (3.1.5), we get V(2,2, P, P2) - V(2,2, P2, P2 ) 2h1 + 2h2 2h/ +2h2 I, hi +3h2 2hl +h2 =___ ~ -_ F+ _ -.. 11 +1J2 21/2 P1 +1 2 L 212 P1 +2 j + ' — 2 [V(1,2, P, R) - V(2,0, P, R)]+ [V(2,1, P, R) - V(2,1, P2, R)]. 11 +1 2 P1 + +2 Then by using the fact from (3.1.3) that,2 [V(1,2,P2,R)-V(2,0, PR)]- 2h,1+i2 +h h = [ +V2 Pi, +22 2, (3.1.8) = [V(2,1, Pi, P,) - V(2,1, Pi, P,) + V(1,2, P, R) - V(1,2, P,,R)]= Z, (2,1) > 0. 9

and substituting this identity into (3.1.5), we get V(2,2,P,,P2) - V(2,2,P2,P,) A2h + (h2 -hl) + PI — z' Z2 [(2,1)V(21, R) - V(2,1, P, R)] 2/2 (/i + /2 ) P1 + /2 > [V(2,1, P1, R) - V(2,1, P2, R)]=V(2,1, P,, P2) - V(2,1, P1, P2)= 0. To prove that Z, (2,2) > 0, from the last inequality, we have V(2,2, P,, P2 )-V(2,2, P2, P2) - V(2,1, P1, R) + V(2,1, P2, R) = Z, (2,2) > 0 which is the desired result. Part 2. (i = 2,all j) In Part 1, we showed that the results in Proposition 2 hold for (i = 2, j = 2). We now use the induction to show that Proposition 2 holds for i = 2 and all values of j. Assume that the proposition holds for i = 2 and for allj, < j, we now show that it must also hold for i = 2 and ji = j + 1. (We only show the proof for part i) as the proof for part ii) is identical). We first note that V(2, j, P,P1)-V(2, j, P, P2) 2h + jh2 2h+ jh2 + P' [V(11,,P,,1,R)-V(V(2, 1,,R)]+ 2,,R)] 2/, PI +/a2 P/1 +/2 P/1 +/2 2h1 +jh2 _2h +jh2 + 2 [V(1, j+1,P,R) V(2, j-1,P,R)]+[V(1, +1,P,R)- V(1, j+,P, R)] (3.1.9) 21 JUl +j2 J1 + u2 From the induction hypothesis, we have V(2, j - 1, P,R) = (2h + (j - 1)h2)/(a +,2) +a/ + a2)V(1,, P2,R) +2/(J1 + 12)V(2, j- 2,P,R). (3.1.10) and from Proposition 1, we have V(1, j +1, P2, R) =[h, + (j + 1)h/(22)+V(1, j,P2,R) (3.1.11) After substituting (3.1.10) and (3.1.11) into (3.1.9), we get V(2, j, P, P1 )-V(2, j, P, P2 ) 2hl + jh2 2h, +jh2 2 ihl +(j+l)h2 2h, +(j -)h2 =~u, ~u, + I I - +I_ 2/,1 /i + 2 P1 + 32 212 2l + 32 + 1 _2 [V(1, j, P2, R) - (2, j -2, P,,R)]+[V(l, j +,P, R) - V(, j +, P2, R) Notingfrom(3.1.9) for -1 that Noting from (3.1.9) for j - 1 that 10

-- [V(1, j, P2, R) - V(2, j - 2, P,, R)] P + /2 2h, + ( h + (-, + - )h2 +V2, -,, P) - V(2, j - 1, P ), P2) + V(1, j,P2,R) -V(1, j,P,R) PI +,2 2 I 2h + (j - )h2 2h2 + (j- l)h2 Z2(2 ) (3.1.12) /I, + P,2 2/., we get, V(2, j, P, P ) - V(2, j, P,, P2 ) i2h2 + (h2- hl) + _ 2 Z2 (2,j - )+[V(l, j +l,P,,R) - V(, j +1,P2,R)] 2u (,1 +,2 ) 1I + 12 > V(1, j +1, P,, R)- V(1, j + 1, P, R)2 0. where the first inequality follows from the induction assumption and the second inequality follows from Proposition 1. We have thus shown i.a) and we note that i.b) also follows since the equation above implies V(2,, P1, PI) - V(2, j,P,,P2) - V(1, j + 1, P, R) + V(, j + 1,P2,R) = Z2 (2, j) 0. The proof for part ii) is similar and is omitted. Part 3. (All i,j =2) We showed in Part 1 that Proposition 2 holds for i = 2,j = 2. Suppose that it is in fact optimal to allocate both servers to queue 2 (when queue 2 has 2 or more jobs) for all i, < i,j = 2. Here we prove that the result still holds at (i + 1,2). We again only show the proof for part i), as the proof for ii) is identical. For part i), we need to evaluate V(i + 1,1, P,, P) - V(i + 1,1, P,, P2), V(i+1,1,P1,P )-V(i+1,,P1,P2) (i+l)h, +h2 (i+l )hl +h2 [V(,2, P -(i2 )+ [(,R)-V(i P + [V(i,2, P1I, R) - V(i,2, P2,+ l, - [V(i,2, P,R)] 2/p1 / + /2 P1 + /2 P/ +/ 2 (i + l)h, +h -(i +l)h1 +h2 +[V(i,2 P,,R)-V(i,2, P2, R)] + - [V(i,2,P2,,R)-V(i +1,0, P R)] 2/1 Pi +/P2 /di + #2 First, note that V(i + 1,0, P, R) = (i + )h, /2p, + V(i,, P,, R). Also, we have V(i,2,P2, R) = 2 + V(i,, P2,,R) from the induction hypothesis on i. Thus, 11

V(i + 1,1, P, PI) - V(i + 1,1, P, P2) (i + l)hl +h2 (i + l)hl +h2 u2 ihl + 2h2 (i + l)h 2#, Il +#2 P /I + 2. 22 2,u I + -2 [V(i,l, P2, R) - V(i,, P1, R)J + [V(i,2, P, R) - V(i,2, P2, R)] ]I1 +' 2 Note that V(i,1, P2, R) = V(i,l, P1, R) = V(i,l, P1, P2 ), because of the induction hypothesis on i. Then, V(i +,1,, P,,Pl) - V(i + 1,1, P,P2) =2h2 +,(h2 - h) + [V(i,2, P1,R)- V(i,2, P2,R)]> [V(i,2, P,R) - V(i,2,P2,R)]O. 2/, (jp + 2) To prove Z2 (i + 1,1) > 0, using the inequality in the last equation; V(i + 1,1, P,, P,) - V(i + 1,1, PI, P2) + V(i,2, P2,R) - V(i,2, P1, R) = Z2 (i + 1,1) 0. Part 4. (All i and j) We showed in parts 1, 2 and 3 that the result holds for (i=2 and allj) and (/=2 and all i). To complete the induction argument, now suppose that the proposition holds for (i < i, all j 2 ), and also for (i, = i + 1 and j, < j ), we now show that it also holds for (i + 1, j + 1), and therefore by induction holds for all i and j. We once again omit the argument for ii) as it is similar to that of i). To show i) we again note that V(i + 1,j,P,,P) - V(i + 1, j,P,P2) (i +)h + jh _(i + l)hl + jh + + [V(i,j +,P,,R) -V(i,j+l,P2,R)]+ /P2 [V(i,j +,P,,R) -V(i +,j -,P,,R)] 2p, 1I + ]2 Pi + ]2 P1 + ]2 -(i + 1)h (+ + )jh, + A[ + [V(i,j+lP,,R) V(i, j+ P2,R)]+ 2 [V(i,j+l,P2,R)-V(i+l,j -,P,,R)] (3.1.13) 21u, u1 +,2 A1 + U2 From the induction hypothesis, we have V(i,j +, P,2 R) =[ i+ (j + 1)h/2 (22 )+ V(i,, P2R), (3.1.14) V(i+,j- PR)=((i + )h + (j -1)h2)/(1 +2)+ /(1 +2)(i,j,P2,R)( + /(1)hi + (-)h 1, j -2,P1,R). (3.1.15) After substituting (3.1.14) and (3.1.15) into (3.1.13), we get V(i+, j, P,,P,)-V(i+ 1,, P,, P2) (i + 1)h1 + jh2 (i + 1)h/ + jh2 U2 + (2 ih + l)h2 (i + l)h1 + (j - 1)h2 2p P1 +L/2 P1 +2 L 2,2 P1 +2 \2 + - [V(i j, PR)-V(i+1, j - 2, P,, R)]+ [V(i, j +1, P, R) - V(i, j +1, P2, R)] Pi1+,42J 12

Then using the fact (from (3.13) by replacing j by j-1) that, — 2 [V(i, j, P2,R)-V(i+1, j-2,P,,R)] /1 +/2 (i + l)h1 + (j - 1)h2 (i + 1)h1 + (j - 1)h2 (i=+l~h, + ( j -l~h2 _ (i + l~hl + (y - l~h2 + V(i +v j - l, PI PI) - (i + l' j - l, PI, P2)+V(i'jP2 'R) -V(i, i' PI R) Jl + I2 2/.q (i + 1)hl + (j - 1)h2 (i + 1)h, + (j - 1)h2 (3.1.16) +Z) ( - + 1, j- 1 ) (3.1.16) P1 +P 2 2p, we get V(i+,j,P1,P,)-V(i + 1,j, P, P2) h +,(h -h,) + _ [V(i + l, j - 1, P,P,)-V(i+l, j - 1, P, P2) )+V(i,j, P, R) - V(i,j, Pi,R)] 2/. (p + 2) Pi +P2 + [V(i, j +1, P,R)- V(i,j + 1, P2, R)] u2h2 +-tl(h2 -h1) + 2 Z2(i +, j-1)+[V(i, j +, P,R)-V(i, j +, P2,R)] 2p1 (/l + 2 ) Pi +2 '2 > V(i,j+I,Pl,R)-V(i,j+I,P2,R) 0. To show Z2 (i + 1, j) 0, from the last inequality, V(i + l, j,P, P)) - V(i +, j, P, P)+ V(i,j +l, P2,R) - V(i,j + l, P,R) = Z2 (i+ 1, j)> 0, and therefore we have shown Proposition 2. To complete the proof of Theorem 1 part (A) we note that the sufficiency directly follows from Propositions 1 and 2. We prove necessity by contradiction. Suppose that it is in fact optimal to allocate both servers to queue 2 but that h >(1 + 2 —)h2. Consider a problem instance where i =1, j = 2, one server is working on a job /l1 + #2 from queue 2 and the other server is ready for service. At this point, if we compare the value of assigning the second server to queue 2 as well versus assigning it to queue 1, we get (by simple algebra), V(1,2, P, P2) - V(1,2, P2, P2 ) = ) - h ) <0. However, this contradicts the fact that assigning 2/12(A-1 +/12) both servers to queue 2 is optimal and therefore the necessity is shown as well. * 3.2 Proof of Theorem 1 part (B). In this section, we provide the proof for part (B) of Theorem 1. Since the proof of sufficiency is very similar to that of part (A), we provide a summary of the proof. We give the full details for necessity. The sufficiency proof hinges on the following three propositions which are entirely analogous to Propositions 1 and 2. 13

Proposition 3: Under condition (B), the following are true: i) V(1 jP2R = VIj'PP2) =V(1, j, P, P,) for all j 2. iV( j1,,P2,1 P2) ii) V(2, j, P,R) = min{V(2, j, PI, P ), V(2, j, P, P2)} = V(2, j, PI, P ) and z2(2, j)=V(2, j,, )- V(2,j,,,) + V( + i,P2,R)-V(,j + 1,PR)0o for all j 1. Proposition 4: Under condition (B), the following are true for i, j > 2: i) V(i, j, P2, R)= min{V(i,j,PP2), V(i,j, P2, P2)}= V(i,j, P1 P2) ii) a) V(i + lj -,l^P,R) = V(i + 1, j - 1, P, P ) b) Z2(i + l,j - 1)=V(i + Ij -l,P,PI)- V(i + 1,j -1,P,P2) + V(i, j, P2 R) - V(iJ, P R)< 0 Proof: The proofs of Propositions 3 and 4 are virtually identical to those of Propositions 1 and 2 and are omitted in the interest of space. * The sufficiency in part (B) of Theorem 1 follows directly from Propositions 3 and 4. We now provide the proof of necessity in detail. We will again prove this by contradiction. That is, suppose that an optimal policy allocates servers to queue 1 as long as there are unserved jobs at queue 1 but that h < (1 +,u2 / ul )h2. Now, from Theorem 1 part (A) which was shown above, we already know that when h, < (1 + /u2 /(, + u2 ))h2, it is in fact optimal to allocate both servers to queue 2 and therefore in that case the result follows by contradiction immediately. We therefore need to focus only in the region (1+ 1u2 /(tI + I2 ))< h, < (1 + u2 /1u,)h2 Now, consider the case with ni =1. The optimality of the exhaustive policy at queue 1 impliesV(1,j,P,,R)=V(l,j,P,P2)< (l, j,P2,P2) for all j 2. Then, pick n2 such that n2 = min jN;2 + 2- 1- l >0+2) 2 //2 2#u I + 2/(Mi 2) The existence of a finite n2 >2 is shown easily. We note that n2 can not be 1 since for j = 1, the expression above yields (h2 - h,) / 2/2 which is negative since h1 > (1 + /2 /(u1 + 2 ))h2 > h2. Similarly, when j = 2, the expression above yields (h2 - h,2)(1 + /2 ) + h2u2 which is again negative because h, > (1 + U2 /(#1 + P2 ))h2. On 2/t2 (41 + /U2) the other hand, since /2/( A +,2)<1, lim j,,o (,2 /(/P +,2))' = 0. We note that (h2 -hl)/(2#2)+ h2/(2,)[1- (u,/(u, + 2))1 ] is increasing in j and converges to 14

[l2h2 +,- (h2 - h,))V(2l,ul2 )>O which is strictly positive because of hI < (1+ 2 //,' )h2. Therefore, a finite value of n2 > 2 exists. We now focus on the difference of V(l, n2, P, P2) and V(1, n2, P2, P2) and we have V(1, n2, P1, P2) - V(1, n2, P2, P2 ) h1 + n2h2 hi +n2h2 /al __ =++ + v -V(O, n2 + 1,P2,R)+ 2 V(ln2 -l, P1,R)-V(l,n2 -1,P2,R). (3.2.1) P1 + #2 2/2 P1 + /2 1 + P2 We also note that V(l, n - 1, PI, R) = V(l, n - 1, P,, P2), and V(O, n2 + 1, P2,R) = ( + V(O, n,, P, R). 2#u2 Also, since allocating servers to unserved jobs at queue 1 is optimal, we have V(1,n2 -1,P2,R) =V(l,n -lP,)h P2 l( ) h +(n2 -V(O,n 2P2 R)+ 2 V(1,n2-2,PR). 2(1, = + V(O, n2,P2,R)+ V(1, n2 - 2, P, R). /1 + 2,t1 + #2 /I + P2 which after substitutions yields; V(1, n2,P,,P )-V(1, n2 P2 P2) h, +n2h2 h, + n2h2 [V(O, n P + [V(o,n2 +,I,RPR)-V(1,n -1,P2, R)] P1 + P2 2P2 P1 + P2 hi2h +n2h2 hi +n2h2 + PU(n2l [V(O, n,,P,, R)- V(1, n - 2, P,,R)l t + [V(OnP2Rh)-(1 +n(n2 -P1)hR)J P1 +p 2 2U2 p1 +,2 L 22 ji +2 J + 2 P1 + 2 (3.2.2) Substituting the expression ____1 r ______1 _ +(n2 - 1)h2 h +(n2 -1)h2 U l [FV(O, n2,P2,R)- V(1, n2 -2,P2,R)]= V(1,n2 - 1, PI,P2) -V( P2,P2)- 2 2 2- 2 + 2 2 -/l + /2 /A1 +/ 2 2/u2 (which follows from the optimality of assigning servers to queue 1 as long as there exist unserved jobs in queue 1) into (3.2.2), we get 2 2 h 2 +' I(h 2 -hI V(, n2, P1,)-(ln,P)= 2 [(l,2-1,P,P2)-V(l, 2 1, -P2P2) + - + — ) (3.2.3) 2 21 + 2 2 2(/1 +/2) By recursively applying (3.2.3) to V(1, n2 - 1, P, P2) - V(1, n2 - 1, P, P ), V(1, n - 2, P, P) - V(l,n2 - 2, P2, P2), and so on, we get V(, n2,. P, P2)-V(, n, P2, P2) =-^- p ^T'^up~p2u~p^)]^2 ^*^ At-ug-T"' "' '+2- ) = 2 [(p2 ) 2[V(l,2, PIP2)-V(1,2, P2,P2)] + 2h2 +/P(h2- h,) n2-( P2 + 2h +p(h2 -h) 81 +2 L, ^ u+l2 ' ' ' '2 (PI +2P2) t-= +P2 2 2(P1 + ) PI^~~~~~~~~~~~~~~~~ ^ f ^ T ^+(-" I +2 P, hh + (hh -h,)h P2 [p 2 2 (h2- hl) +P2h2 +p(h2-h) ) 1 2 +p(h2-l) P1 + LP2 P 1 + P2 2P2(P1 + P2) 2P2(P1 +2) (k=1 P1 + 2)j 2P2(P, +P2) 15

After a lot of algebra, this simplifies to V(1, n2,P, P2) - V(1, n2h P2) P h2 + 2 1 (3.2.4) 2/2, 2/p PI/ + 2 However, we note that the right hand side of (3.2.4) is strictly greater than zero from the definition of n2. However, this implies that V(l,n2,P, P2 )>V(l,n2,P,P2), which contradicts the fact that it is optimal to allocate servers to queue 1 when there exist unserved jobs at queue 1. We therefore have also shown the necessity result. * 4. Optimality of Non-Idling Policies In the previous section, we assumed that the servers are never allowed to idle. The only way a server can idle is if there are no more jobs for the server to serve. Unenforced idling is not permitted. In this section, we prove that even when unenforced idling is permitted, it is in fact never optimal for the servers to idle, and thus the optimality results in Theorem 1 extend to policies where idling is permitted. This is stated in the next theorem. Theorem 2: The optimal policy for the problem where idling is permitted is a non-idling policy and the results in Theorem 1 hold when idling is permitted. Proof: It is very straightforward (through a very simple interchange argument) to show that it can never be optimal to have both servers idling at the same time so we only focus on the case where one server is working on a job from either queue and the other one is either ready to start a new job or to idle. We divide the proof into two cases (hi > h2 and hi < h ): Case i) (hi > h2 ) We will prove the result in this case through an interchange argument. In order to set up the interchange argument, we let J. m be the type (i.e., job from queue 1 or queue 2) of the m-th job processed by server 1. For example, if J,m = 1, this means that m-th job server 1 processes is in queue 1. The processing time of the job Jdm is denoted as P.,m Also, we let C (s), s > 0, be the holding cost rate at time s under the policy n and Vn = C (s) dsbe the expected total cost under the policy n. Consider a policy n where one of the servers is working on a job, and the other server is ready to process a job. Under this policy, the second server 16

idles. We will assume, without loss of generality, that the second server idles for a duration of time I, which is no longer than the remaining processing time of the job the first server is processing which we will denote by P1 1 (0). (We note that the second server could idle for a longer duration, in which case, we could make the same argument by dividing the idling periods into two periods 12 and I,and repeating the same argument for both periods (see Figure 2.) We therefore assume without loss of generality that I < P, i (0). Our proof shows that n can not be optimal by constructing a policy n where the idling is postponed to the future. But, since the same argument can be repeated at all times, this means that it is never optimal to idle except when there are no jobs to serve. Now, we show that policy n can not be optimal. We divide the proof into 4 cases depending on which jobs the first server serves at time zero and the second server serves after the completion of its idling period under policy n. pl,l (O) Server 1 JE L J2 J3 I Server 2 _____ J2,1 J2,2 2 I, Figure 2. I>P,1 (0) Case 1. (Jl, =2) Suppose that at time zero, the first server was busy serving a job from queue 2 (i.e., J,1 =2 ) and server 2 idles as in Figure 3.a) under policy f even though there exist other jobs it can process. We compare this policy with another policy n where server 2 first process J2, (where this job can be from either queue) and then idles as in Figure 3.b) (i.e., the idling period is shifted). The two policies are completely identical except for this shift of the idling period and the serving of job J2 by server 2. We denote the time at which the two situations become identical by time t where t = I + Pl. 17

Server 1 Server 2, Server 1 Jl,1 J1,2 Jl, i - I dI J2,12,2 a)Policy n Iii 1 J1,2 Jo, - Server 2 J2,1 2,2 b) Policy n 0 p j,1 t Figure 3. Case 1,2 and 3 Since the two policies are identical after time t, we have, cn(s) = Cn (s), s > t. And also cost rates are identical before time P2, (C (s)=Cn(s), s < P,). But, in the time between P2,1and t, clearly Cn (s)< C (s), P2, s < t. So we have If J2, = 2 then, Vf - n =f C(s)ds - JCn(s)ds=J; (C(s)-Cn(s)4s=f h2ds > If J,1 = Ithen, since h >2 h2 we have Vn - VF C= C (s)ds -o C" (s)ds= (h - h2 )ds 0 So the policy n is better than the policy fn, but this is a contradiction since n was presumed optimal. Case 2. ( J1 = 1, J2, = 1): The analysis in this case is identical to Case 1 and is omitted. Case 3. (Jl, = 1, J, = 2 ) and J21 is available for processing at time 0 (i.e. n2 (0) > 1). The analysis in this case is identical to Case 1 and is therefore omitted. Case 4. J11 = 1, J2,1 = 2, and J2,1 = 2 is not available at time 0. (i.e. n2 (0) = 0, and the job that server 1 is processing in queue 1 will be the first job that will be processed by server 2 in queue 2 under policy n. The choice at time 0 for server 2 here was between idling and serving a job from queue 1 since jobs from queue 2 were not available). In this case, I = P,, since Server 2 is idling to serve the job that Server 1 is going to finish processing. Now consider an alternative policy n where the second server processes J12 (which would have 18

been processed by server 1 after it finished J1 l under n ). and under this revised policy, the server 1 processes the job at queue 2 that will be available when it finishes processing the job at queue 1 (instead of handing it over to server 2 as in 1n). Server 2 idles after finishing processing J12 After time t = P. + I. the two policies are identical (except that server 2 becomes server 1 and vice versa, but that does not change anything since the servers are identical). The system under policy n, and under policy n is shown in Figure 4..1 j= 1.I^ =11-.3 IJ: L2 1,3[ Server 1 Server 2 Server 1 -I - = IJI2 I A1 J., = 2. | J2. l Policy n Policy n..l 1 J2. = 2 =2 2.i, I Server 2 12 1 = 1 pFgrl P1.2 P12 +I Figure 4. Interchange argument for Case 4 Then the difference of costs under the two policies will be. C- _ [jr = C - n (()ds- Ch -h, s 0 from h,. h. Thus. we have shown in each case that a policy n where one of the servers idles at a given time can not be optimal by shifting the idling period to the future. The same argument can be repeated so that the only time idling can occur is when one of the servers has no more jobs to process. ii) h, > hi In this case. the argument is more complicated. We first note that it is obvious that when n, + n2 < 2. (i.e. there are only twao or fewer jobs left in the system), it can not be optimal to idle. So we only need to focus on cases wKith more than 2 jobs in the system. (It is also obvious that in states (0. j) it can not be optimal to idle). Also. we can use the fact that the optimal policy is Markovian (which directly follows from finite state and action spaces), and the obvious fact that it can not be optimal for both servers to be idle at any point in time. We will prove the result by induction on all of the states to show that it can not be optimal to idle in any state. We divide the proof into three parts: 19

Part 1. We first note that it is not optimal to idle in states (0, j, P2,R). We will show that it is not optimal to idle in states (1,, PI,R). First, we note that it is easy to check that the non-idling policy is optimal in state, (1,1, P, R). To proceed the induction on j, we suppose that the claim above is true for j < jI,ji, ~1. In the next step, we show that the claim must also hold at (1, j1 + 1, Pi, R). Let F be a policy that idles in the state (1, j, + 1, PI, R) and let V(1, j, + 1, PI, I) be the value function associated with this policy. The policy n assigns the server to queue 2 in that state and both policies follow the optimal policy in all other states. Note that because of the induction assumption and Theorem 1, this implies that there will be no idling in all other states under both policies and the servers will be assigned to queue 2 when possible. Thus, we have, V(1, j, + 1, P,R)=[h, + h2 (jl + l)]/2 +V(O, I, + 2,R,R) = [h, + h2 (, + l)]/p +V(O, j, + 2, P,R), h +h2j1 +h2 _U2 V(, j2 +l, +P2, R)=l +2 + - V(O, j, +2, PR)+ V( R). -I + U2 P1 + /2 Pi + P2 Then we have 2[h, +h,, + 1)] l 2,,R)-(1, V(1, +, P,R)-(,, + R= [V(,, + 2, P2,R) - V(, j, R) Pi (/I + 2 ) Pi + #2 (4.1.1) Since a non-idling policy is optimal in state (0, j, + 2, P2, R) and in state (1, j, PI, R), we have V(O, j, + 2, P2,,R) = h2 ( + 2)/(2u2 ) + V(0, j + 1, P2,R) (4.1.2) V(1,,,, R)V(1,j,,iPI,R)-=h1 +1h2 +V(O, +l,R,R)= h + +V(O,j, +I,P2,R) (4.1.3) J1 ju1 Substituting (4.1.2) and (4.1.3) into (4.1.1), we have V(1, j1 +, PI,I)-V(1, j1 + 1, P,R) = 2[hi +h 2 ( 1)]+,2 _[V(Oj, + 2, P2,R)- V(1, j,, P,R)] l((Pi + P2) P1i + 2 2 2J1> ~+ j h(j +)+ V(o, j, +, P2,R)- h + 2 - V(O, j +1,P2,R) ]P2 (PI + h2 Pffi +l 2q- I j2[hl +h2(j1 +1)] _ 2 hi +h2jl A 2 h2(jl +2) 0 + >0. 1(L1 + U2 ) U1 + /2 P1 U1 + U2 2/U2 From the last inequality, we have shown that idling can not be optimal in state (1,, + 1, P, R) as well. Part 2. 20

We now show that if a nonidling policy is optimal for all states (i,, jP, PI, R) and (i7 - 1,, P2, R) for all states ((i < i, Vjj) and (i 21, j < j)), then nonidling is also optimal in states (i, j + 1,P,R) and (i-l,j+ l,P2,R). We let H be a policy under which idles at the state (i-l,j+1, P2,R)and let V(i - 1, j + 1,P2,R) be the value function associated with this policy. Once again, V denotes the value function for a policy which does not idle but assign the server to queue 2. We then have (i _ l1, + 1, P2-,R l (i ) + h ( l(i - 1i-) + h2 (j + 1) 1 +V(i - 1, j,R,R) = (i 1) h 2 ( j + 1) l2 l2 The last equality directly follows from the induction hypothesis. ( i.e., the optimal policy is a non-idling policy at (i - 1,, P2, R), j < j.) We compare this with the value function obtained by the non-idling policy n, which is V(i - l,j + 1,P2,R) =V(i-l, j + P,,P,)=[h(i -l)+h2 ( + 1)(2,2 )+V(i - 1, j, P,R). Then we have V(i -1, j+l,P2R)-V(i - +,P2,R), (i- 1)+ h +l) h(i-)+ h2(j +1) P2 2u 2 Thus, we have shown that idling can not be optimal in state (i -1, j + 1,P2,R) as well. The argument for (i, j + 1, P,, R) is identical and is omitted. Part 3. Finally, to complete the induction argument, assuming that the result holds for ((i1 < i, Vjj, P,, R) and (i, < i - 1, lj,, P2, R)), we show that it also holds for (i + 1,0, PI, R) and (i,l, P2, R). The argument for this part is exactly the same as parts 1 and 2 and we omit the details. We have thus shown that idling can not be optimal in any state. * 5. Discussion and Extensions In this section, we discuss the differences between the results obtained here and in Pandelis and Teneketzis, and then discuss some possible extensions that can be considered by future research. As described in the introduction, the paper by Pandelis and Teneketzis considers a similar problem. However, they assume general and not exponential processing times, and in their model jobs leaving queue 1 go to queue 2 with probability p and leave the system with probability 1- p. Denote the processing time at queue 1 by the 21

random variable X1, and the processing time at queue 2 by the random variable X2 Then their main result is stated in the following Theorem 3 (Pandelis and Teneketzis, 1994) Suppose that X1 <s, X2, X1 has nondecreasing likelihood ratio and h, - ph2 > h2, then the policy which allocates both servers to queue 1 (as long as there are jobs to be served in queue 1) is optimal. We now note that when the processing times are exponential and p = 1, as in this paper, this result implies the following Corollary 1 (Pandelis and Teneketzis, 1994) If p, > /22, and h >2 2h2 then the strategy which allocates both servers to queue 1 is optimal. It is straightforward to note that our result, using the exponential assumption, provides a more complete characterization of when it is optimal to allocate both servers to queue 1, and provides the sufficient as well as necessary conditions under which allocating servers to queue 1 or queue 2 is optimal, and is therefore significantly different than the result by Pandelis and Teneketzis. Having described the difference between the results in this paper and in previous literature, we now discuss possible extensions and conjectures. In section 3, we showed the conditions under which it is optimal to allocate both servers to queue 1 or queue 2. However, the results also implied that when (1 + /2 /(/1 + P2 ))h2 < h < (1 + p2 / / )h2, the optimal policy does not necessarily allocate both servers to one of the queues. An interesting question is whether allocating one server to queue 1 and one server to queue 2 under these conditions (at least until one of the queues gets exhausted after which both servers would serve the other queue) is a policy that would perform well. In general, our numerical studies indicate that in these middle cases, the optimal allocation policy actually depends on how many jobs are in queue 1 and queue 2. However, to get a sense of how well simpler policies would perform, we tested two simple heuristic policies in the situations where (+1,2 /(,1 +,2 ))h2 <h <(1+L2/,1 )h2. The first heuristic (which we denote by H(P,, P2) ) allocates one server to each queue so long as both queues have jobs to serve. In cases, where one of the queues has zero jobs, then both servers serve the other queue. We compare this policy against the policy of allocating both servers to queue 2 so long as queue 2 has jobs and only serving queue 1 when one of the servers runs out of jobs to serve at queue 2. (We denote this policy by H(P2, P2) ) 22

We tested these two heuristics against the optimal policy. Since we know the exact policy except when (1 + /,2 /(/ + 12 ))h2 < h < (1 + 2 / u1 )h2, we are only interested in values of h, which fall in this interval for given values of j, u,2,h2. Therefore, for each combination of pu,,Iu2,h2, we chose values of h, which were 5%, 30%, 50%, 70% and 95% of the spread between (l+,u2 I,)h2 and (1 +/, /(pl + 2 ) )h2, plus (1 +u2 l(/I + P2) )h2. For any given choice of h we picked 16 values of (n,,n2 ), n,,n2 E {3,15,3,60}to calculate the average sub-optimality of each heuristic. Case 1. p, = l,/u =2,h/ =1 hi Avg. % Suboptimality (Max) of Avg. % Suboptimality (Max) of H(P,, P) H(P2,P,) 1.73333 (5%) 10.565 (23.934) 0.004 (0.040) 2.06667 (30%) 6.859 (15.966) 0.021 (0.211) 2.33333 (50%) 4.443 (10.590) 0.033 (0.320) 2.6 (70%) 2.435 (5.920) 0.092 (0.895) 2.93333 (95%) 0.456 (1.711) 0.314 (3.079) Case 2.,u = 2, u2 = 1, h2 = 1 h, Avg. Suboptimality (Max) of Avg. Suboptimality (Max) of H(P,, P2) (%~/) H(P, P2 ) (%) 1.341667 (5%) 4.758 (6.765) 0.002 (0.018) 1.38333 (30%) 3.418 (4.862) 0.010 (0.107) 1.41666 (50%) 2.388 (3.406) 0.016 (0.176) 1.45 (70%) 1.396 (2.004) 0.025 (0.266) 1.49166 (95%) 0.221 (0.326) 0.054 (0.576) Case 3. P/u = 1,/2 = 2, h2 =1 h, Avg. Suboptimality (Max) of Avg. Suboptimality (Max) of H(P,,P2) (%~/) H(P2,P2) (%) 1.525 (5%) 8.369 (13.913) 0.003 (0.032) 1.65 (30%) 5.797( 9.704) 0.017 (0.183) 1.75 (50%) 3.935 ( 6.646) 0.028 (0.293) 1.85 (70%) 2.242 ( 3.828) 0.057 (0.594) 1.975 (95%) 0.357 ( 0.606) 0.143 (1.505) Table 1: Results for performance of heuristics when (1 + u, /(ul + u2 ))h, < h, < (1 +u, / /u, )h, In Table 1, we present the results comparing heuristics H(P1, P), H(P2,P2) to the optimal solution. For each value of,, u,,,h and h,, we give the average percentage suboptimality of each heuristic over the 16 cases considered. (We also provide the maximum suboptimality over the 16 problems in parentheses). We note 23

that it is very interesting that in these cases the heuristic H(P2,P ), (i.e. exhaustive service at queue 2 when possible) performs much better than the heuristic H(P, P2), and is in fact very close to optimal. We note that despite the fact that in the region of values considered in this experiment, hi is always greater than h2, it is still much better to allocate both servers to queue 2 rather than queue 1. The average suboptimality of H(P2,P2) over all the cases considered was 0.05% and a maximum suboptimality was 0.31% versus an average of 3.84% and a maximum of 10.57% of H(P, P2). Especially when hl is not significantly greater than (1+,u2 / 1) )h2, the performance of heuristic H(Pi, P2) is very close to the optimal policy, as one would expect. Therefore, we can conclude that in general the simple policy of allocating both servers to queue 2 exhaustively whenever h1 < (1 + /2 / /1 )h2 and allocating both servers to queue 1 exhaustively otherwise will work extremely well. Notice that one way to rewrite this inequality is to rewrite it as p,2h >,u (hi - h2 ). One way to interpret the left side is that this is the rate with which rewards are earned (or costs are reduced) when a server is working in queue 2, similarly the right side is the rate with which costs are reduced (so long as h > h2 ) when the server is working in queue 1. We would like to note that as Theorem 1 indicates this simple intuition does not lead to this policy being optimal in this whole region.. However, as Table 1 indicates, the policy performs extremely well. A second interesting question is whether Theorem 1 remains true if arrivals to queue 1 are introduced and the objective changed to minimizing that of the average cost per unit time. We conjecture that this result carries over to the case with dynamic Poisson arrivals. However, we have not to date been able to prove this result. Our extensive numerical tests yielded no cases where Theorem 1 did not hold in the dynamic case with the average cost minimization objective. In Tables 2 and 3, we provide some of the empirical evidence that we have observed. Table 2 includes the cases where we would expect exhaustive allocation of servers to queue 2 would be optimal since we have h, = a(l + P2/(P +u2 ))h2, where a =, 0.75 and 0.5, and therefore Theorem 1 (if it held under these assumptions) would indicate optimality of this policy. (Note that A denotes the arrival rate of jobs to queue 1. Similarly, in Table 3, we would expect optimality of exhaustive allocation of servers to queue 1 (since we have h1 = a(l + p2 /P2 )h2, a = 1, 1.5, and 2) and in fact this is the case. The final column in Tables 2 and 3 illustrates the benefits of having flexible servers rather than dedicated servers. We note that even when a policy as in Theorem 1 which requires the servers to serve queue 1 or 2 24

exhaustively is implemented, the servers still need to be flexible (or cross trained) since when one queue is exhausted, the server switches to the other queue. Compare this to the case where each server or worker is trained for only one task, which we call the fixed tandem policy. In this case, the server only serves the queue that it is assigned to and idles if it has no jobs to work on. The results in Tables 2 and 3 indicate the benefits of a flexible work force as the fixed tandem policy results in costs which are on average 50% higher. Ai A, 2 h2 1, A 2 l h h Optimal policy Optimal cost Fixed tandem u1 + 2 h2 per unit time (suboptimality in %).45 1 2 1 5/3 5/3 Exhaustive at 2. 1.091 1.654(51.632).45 1 2 1 5/3 5/4 Exhaustive at 2. 0.875 1.313 (50.090).45 1 2 1 5/3 5/6 Exhaustive at 2. 0.659 0.972 (47.627).45 2 1 1 4/3 4/3 Exhaustive at 2. 0.843 1.205 (42.964).45 2 1 1 4/3 1 Exhaustive at 2. 0.745 1.109 (48.735).45 2 1 1 4/3 2/3 Exhaustive at 2. 0.647 1.012(56.380).45 1 1 1 3/2 3/2 Exhaustive at 2. 1.388 2.045 (47.336).45 1 1 1 3/2 9/8 Exhaustive at 2. 1.154 1.739(50.607).45 1 1 1 3/2 3/4 Exhaustive at 2. 0.919 1.432 (55.718) Table 2. Results for dynamic cases when h, < (1 + - 2 )h2. /1 +A2 l Ap, i 2 h2 (1 + Au2 /,i )h,2 hi Optimal policy Optimal cost Fixed tandem per unit time (suboptimality in %).45 1 2 1 3 3 Exhaustive at 1. 1.772 2.745 (54.906).45 1 2 1 3 4.5 Exhaustive at 1. 2.505 3.972 (58.584).45 1 2 1 3 6.0 Exhaustive at 1. 3.239 4.381 (60.525).45 2 1 1 1.5 1.5 Exhaustive at 1. 0.890 1.254 (40.896).45 2 1 1 1.5 2.25 Exhaustive at 1. 1.084 1.471 (35.707).45 2 1 1 1.5 3.0 Exhaustive at 1. 1.280 1.689 (31.984).45 1 1 1 2 2 Exhaustiveat 1. 1.691 2.455 (45.157).45 1 1 1 2 3 Exhaustive at 1. 2.223 3.273 (47.210).45 1 1 1 2 4 Exhaustive at 1. 2.754 4.091 (48.519) Table 3. Results for dynamic cases when h, > (1 + 2 // A )h2 Further research is needed to prove the conjectures presented in this section and to develop results for tandem queues with a larger number of jobs and servers. 25

References: Agrawal, R., Hedge, M., Teneketzis, D., (1990), "Multi-armed bandit problems with multiple plays and switching costs," Stochastics and Stochastic Reports 29, 437-359. Bartholdi, J.J., Bunimovich, L.A., and Eistentein, D., (1995), "Dynamics of 2 and 3-worker bucket brigade production lines," Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0160. Chang, C., Nelson, R. and Pinedo, M., (1991), "Scheduling two classes of exponential jobs on parallel processors: Structural results and worst-case analysis," Advances in Applied Probability, 23, 925-944. Duenyas, I., Gupta, D. and Olsen, T. (1995), "Control of a single server tandem queueing system with setups," Technical Report No. 95-19, University of Michigan, to appear in Operations Research. Farrar, T. (1993), "Optimal use of an extra server in a two station tandem queueing network," (1993), IEEE Transactions on Automatic Control, 38, 1296-1299. Gittins, J.C., (1989) Multi-armed Bandit Allocation Indices, Wiley, New York. Hajek, B., (1984), "Optimal control of two interacting service stations," IEEE Transactions on Automatic Control, AC29, no. 6, 491-499. Hofri, M. and Ross, K., (1987), "On the optimal control of two queues with server setup times and its analysis," SIAM Journal of Computing, 16, 399-420. Iravani, S.M.R., Posner, M.J.M., and J.A. Buzacott, (1995), "Two-stage tandem queue attended by a moving server with holding and switching costs; static and semi-dynamic policy," Technical Report. 95-18, University of Toronto, Department of Industrial engineering, Toronto, Canada. Iravani, S.M.R., Posner, M.J.M., and J.A. Buzacott, (1996), "An N-stage tandem queueing system attended by a moving server with holding and switching costs," Technical Report., 96-09, University of Toronto, Department of Industrial Engineering, Toronto, Canada. Kampke, T., (1987), "On the optimality of static priority policies in stochastic scheduling on parallel machines," Journal of Applied Probability, 24, 430-448. Kampke, T., (1989), "Optimal scheduling of jobs with exponential service times on identical parallel processors," Operations Research, 37, 126-133. McClain, J.O., L.J. Thomas, and K. Schultz, "Management of Worksharing Systems," Technical Report, S.C. Johnson Graduate School of Management, Cornell University, Ithaca, NY, 1997. Pandelis, D. and Teneketzis, D., (1994a), "Optimal multiserver stochastic scheduling of two interconnected priority queues," Advances in Applied Probability, 26, 258-279. 26

Pandelis, D. and Teneketzis, D., (1994b), "Optimal stochastic dynamic scheduling in multi-class queues with tardiness and/or earliness penalties," Probability in the Engineering and Informational Sciences, 8, 491-509. Pinedo, M., (1995), Scheduling: Theory, Algorithms and Systems, Prentice Hall, New Jersey. Rosberg, Z., Varaiya, P, and Walrand, J., (1982), "Optimal control of service in tandem queues," IEEE Transactions in Automatic Control, AC-27, 600-609. Ross, S. (1983) Introduction to Stochastic Dynamic Programming, Academic Press, New York. Stidham, S. and Weber, R., (1993), "A survey of Markov decision models for control of networks of queues," Queueing Systems: Theory and Applications, 13, 291-314. Van Oyen, M and Teneketzis, D., (1992) Optimal scheduling of a finite capacity shuttle under delayed information, Probability in the Engineering and Informational Sciences, 6, 29-61. Van Oyen, M., and Tenektzis, D., (1994), "Optimal Stochastic Scheduling of Forest Networks with Switching Penalties," Advances in Applied Probability, 26, 474-497. Van Oyen, M. and Teneketzis, D., (1996), "Optimal batch services for a polling system under partial information," ZOR: Methods and Models of Operations Research, 44, 401 —419. Weber, R. and Stidham, S. (1987), "Optimal control of service rates in networks of queues," Advances in Applied Probability, 19, 202-217. 27