THE UNIVERSITY OF MICHIGAN INDUSTRY PROGRAM OF THE COLLEGE OF ENGINEERING TWO QUEUES IN TANDEM ATTENDED BY A SINGLE SERVER Miguel Taube Netto A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the University of Michigan Department of Industrial and Operations Engineering 1972 December 1972 IP-848

Doctoral Committee: Professor Herbert P. Galliher (Chairman) Professor Ralph L. Disney Associate Professor Stephen M. Pollock Professor Arch W. Naylor

ABSTRACT TWO QUEUES IN TANDEM ATTENDEDi BY A SINGLE SERVER by Miguel Taube-Netto Chairman: Herbert P. Galliher We consider two service stages in tandem with infinite queue capacities in front of each stage. There is a single server who performs the service in both stages by switching from one stage to the other according to certain switching policies. Switches can occur only after a service completion or, if the server is inactive, at- arrival epochs. The arrival process is assumed to be Poisson and the service processes are independent renewal processes. We analyze the behavior of the system under six different switching policies, namely 1. Switch to the other stage whenever the number of customers in the present stage is zero. 2. The first stage has nonpreemptive priority over the second. 3. The second stage has nonpreemptive priority over the first. 4. Switch to the second stage when it has N customers and come back to the first stage when all N customers are served. 5. Operate as in Item 1 except that the switching from the second to the first stage can take place only when the number of customers in the first station is at least N. 6. Operate as in Item 1, but give nonpreemptive priority for the first stage when it contains at least N customers.

For the steady-state situation, we obtain, for each policy the state probabilities, the Laplace-Stieltjes transform of the distribution of the time a customer waits until the beginning of service in each stage, the distribution of the busy period of the server (except for Item 4) and the busy periods of the stages. For the first three policies we also consider the case of random duration of switching from one stage to the other. An efficient method is provided for calculating numerically the expected values of the busy period of the stages for the policy in Item 1. This method makes use of generating functions, and an iterative technique to find their boundary points in a manner similar to Takacs' analysis of two queues with independent arrivals attended by a single server,

ACKNOWLEDGMENTS The author wishes to express his gratitude and appreciation to his doctoral committee and especially to his chairman, Professor H. P. Galliher for his support and guidance throughout the course of this work. This research would not have been completed without his encouragement during difficult periods. Special thanks are also due to Mrs. Wanita Rasey, typist, for her excellent and prompt work in the preparation of the manuscript and to Dr. Jose Busnardo-Neto in the preparation of computer-generated plots. The author's graduate studies were sponsored by the Brazilian government through the Conselho Nacional de Pesquisas, the Universidade de Brasilia, and the Instituto de Pesquisas Espaciais. -ii

TABLE OF CONTENTS Page ACKNOWLEDGMENTS LIST OF ILLUSTRATIONS v LIST OF TABLES vi CHAPTER I. INTRODUCTION 1 1. The Problem 1 2. Background 5 3. Summary of Results and Organization 9 4. Terminology and Methods 12 CHAPTER II. LEAVING NO BACKLOG 16 1. Introduction 16 2. Stationary Conditions (Instantaneous Switching) 16 3. Determination of U (0,y), U (x,0) and 7(2,,0,0) 18 1 2 4. Expected Number of Customers 25 5. Waiting Times 27 6. Busy Periods 29 7. Alternative Approach for the Calculation of the State Probabilities 32 8. Comparison of the Methods of Sections 3 and 7 33 a. Computations Using the Iteration Scheme of Section 3 34 b. Computations Using the Method of Section 7 36 9. The Case of Random Duration of Switching 38 9.1 Expected Number of Customers 43 9.2 Waiting Times 45 9.3 Alternative Approach for the Calculation of the State Probabilities 45 9.4 Busy Periods 47 CHAPTER III. SIMPLE NONPREEMPTIVE PRIORITY 50 1. Introduction 50 2. The SSP Policy 50 -iii -

Page 5. The FSP Policy 54 3.1 Expected Numbers of Customers and Waiting Times 56 3.2 Busy Periods 57 3.3 The Case of Random Duration of Switching 59 CHAPTER IV. RELUCTANT SWITCHING 68 1. Introduction 68 2. The SSS (Q = N) Policy 69 2 2.1 Calculation of r,m Zk~l ack and ac 76 2.2 Expected Number of Customers and Waiting Times 79 2.3 The SSS (Q = 2) Policy 80 2 2.4 Busy Periods 82 3. The WNFS Policy 84 3.1 Expected Number of Customers and Waiting Times 90 3.2 Busy Periods 91 4. The SFS (Q > N) Policy 94 1 - 4.1 Expected Number of Customers and Waiting Times 98 4.2 Busy Periods 99 CHAPTER V. DISCUSSION 102 1. Numerical Comparison of Policies 102 2, Practical Implications of Availability of Numerical Results 110 3. History of the Work 112 4. Related Topics and Possible Extensions 115 LIST OF REFERENCES 118 -iv

LIST OF ILLUSTRATIONS Figure Page I Illustration of the Iteration Scheme for Finding U (O,y) and U (x,O). 22 ~1 2 II Average Waiting Times in the Stages of the System, For Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity in the First Stage, p, for Constant Total Traffic Intensity (p = 0.1). (a) First Stage; (b) Second Stage. 104 III Average Waiting Times in the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity in the First Stage, p, for Constant Total Traffic Intensity (p = 0.5). (a) First Stage; (b) Second Stage. 105 IV Average Waiting Times in the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity in the First Stage, p, for i Constant Total Traffic Intensity (p = 0.9). (a) First Stage; (b) Second Stage. 106 V Average Busy Period of the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity in the First Stage, p, for Constant Total Traffic Intensity (p = 0.1). (a) First Stage; (b) Second Stage. 107 VI Average Busy Period of the Stages of the Syste, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity to the First Stage, p, for Constant Traffic Intensity (p = 0.5). (a) First Stage; (b) Second Stage. 108 VII Average Busy Period of the Stages of the System, for Policies LIB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity to the First Stage, po, for Constant Traffic Intensity --- 0.9. (:a) Firsi Stage: (b\ Second Stage. 109,-v

LIST OF TABLES Table Page I Results. 11 II Values of Q Obtained by Simulation and By Equation 4.9. 27 2 III Illustration of the Iterative Scheme of Section 3 for p = p = 0.4. 35 1 2 IV Values of e for Different Traffic Intensities. 36 V Values of c Calculated by the Direct Approach, for Different Traffic Intensities and Different Truncations of the Infinite Summations. 37 -vi

CHAPTER I INTRODUCTION 1. The Problem In this study, we consider certain queueing situations in which customers arrive at a two-stage queueing system according to a Poisson process with constant arrival rate, X. Each customer requires two sequential types of servicings. Both servicings are performed by a single server, who switches from one type of service (one stage of the system) to the other, according to some switching rule (policy). The server can even be temporarily removed from the system and, therefore, not available in either stage. The special case of instantaneous switching will recieve most of our attention in this thesis, however, for some switching rules, we shall consider the length of the switching times (or simply the switching times) as random variables with arbitrary distributions with finite moments. The service time processes in each stage are assumed to constitute independent renewal processes with distributions S (t) and S (t). 1 2 These processes are also assumed to be stochastically independent of the arrival and switching time processes. In the analysis of this problem we shall assume infinite queue capacity in front of each service station. A customer arriving at the system will wait for service in the first stage unless the server is ready to service him in that stage, in which case, service immediately begins. When a customer completes service in the first stage, he -1

-2immediately goes to the second stage, where he will join the second queue, except that if the server moves with him (with zero switching time) to the second stage and no other customer is already waiting there, then his service in the second stage will commence without any wait. In each stage, customers are served in their order of arrival. How long customers wait depends somewhat upon the policy which the server follows in switching from stage to stage. We will consider several alternative policies, described below. When a customer is in service in either stage the server waits until the current servicing is completed and then decides whether to remain in the present stage, switch to the other stage or remove himself from the system (the three possible states of the server). When the server is idle (removed or not busy because his present state is empty) he waits in the stage until the next arrival and then decides where to locate himself. A criterion for these decisions by the server could be obtained if we are able to attach a cost structure to the behavior of the system. This structure would include, for instance, the cost of service in each stage, the waiting costs, idle costs and switching costs. With such a quantitative cost description we could use the expected average cost or the expected total discounted cost, as optimization criteria, and apply the techniques of Markov renewal programming (in the case of finite queue capacities) to find an optimal decision policy. However, due to the size of the state space (number of customers in each stage and the state of the server), the amount of calculation is very large. Also, as we may intuitively expect, an optimal policy might be quite complex and difficult to implement.

-3An alternative to this situation is to restrict our attention to "simple" decision policies for which a complete analysis of the behavior of the system is feasible. These policies may be suboptimal, but because we know better their effects on the system, we may consider them for situations where only a qualitative aspect of the costs is known. This is the approach of this study. We consider six policies. In fact three of these policies are particular cases of one of the others, however there are advantages to presenting all of them separately. Since we are only interested in the steady-state effects of each policy, we assume that the policy becomes effective when the system is first emptied. The six policies are: 1. LNB (leaving no backlog). Switch to the other state whenever the number of customers in the present stage reaches the value zero. 2. SSP (second stage priority). Switch to the other stage whenever a service is completed in the present stage. In this case the server follows the customers through the two stages of the system. This is merely an M/G/l queueing situation. 3. FSP (first stage priority). Customers in the first stage have nonpreemptive priority over customers in the second stage. This means that the server switches to the second stage when the first stage becomes empty, and returns to the first stage when, at a departure from the second stage, there is at least one customer in the first stage, or when no customers are left behind in the second stage.

-4For the next two policies, define Qk to be the number of customers in stage k, k = 1,2. 4. SSS (Q = N). Switch to the second stage when Q = N and 2 2 return to the first stage when all of these N customers are attended. (If the initial value of Q is greater than N, the server can, for 2 instance, start by attending all Q customers.) 2 5. SFS (Q > N). The server switches to the second stage only when the first stage becomes empty. He stays in the second stage until it becomes empty, unless the number of customers in the first stage, at service completion epochs in the second stage, is at least N. In this case the server returns to the first stage. SFS (Q > N) stands for switch to the first stage when Q > N. 6. WNFS (wait for N customers in the first stage). Switch to the second stage when the number of customers in the first stage is zero; attend all customers accumulated in the second stage (a total of at least N) and then go back to the first stage if the number of customers in it is at least N, otherwise remove the server from the system until N customers are accumulated in the first stage (this value, by the nature of the arrival process, is reached with probability one in a finite time). Notice that under these policies, except the last one, the server is never removed from the system. Notice also that LNB -W FS (or LNB - W FS), FSP - SFS(Q > 1), SSP SSS(Q = 1) and LNB SSS(Q oo). 1 1 - 2 2 Justifications for considering these switching rules are as follows If the switching costs are negligible when compared with waiting costs,

-5we may use the SSP policy in the case of high waiting cost in the second stage, and the FSP policy in the case of high waiting cost in the first stage. Under the LNB policy, as under the previous ones, the server tends to switch too many times when the traffic intensities are low, however this may be a good policy when the switching costs are a., small and the waiting cost in each stage are of the same order of magnitude. Policies SSS(Q = N), SFS(Q > N) and WNFS, which we call 2 1 "reluctant switching policies," are designed for situations of high change over costs. The policy WNFS is convenient when the server charges for his services even if he is idle (but present) in the system; under this policy the idle periods occur only when the server is removed from the system and, therefore, free of charge. 2. Background In this study it has not been our objective to discover or develop practical applications of the above queueing model. However it seems that this model could represent various practical situations of sequential service operations.'For example: a doctor who first attends his patient for preliminary examination then, in a second phase, takes care of more detailed diagnosis; a repair man who takes care of machine breakdown on a provisory basis, until there are enough machines with provisory repairs to justify a second phase of service where each machine is overhauled; a small computer installation where the compilation and execution of program takes loading and unloading of the compiler (which is stored in a deck of cards). An interesting possible application is the case of two bridges over a river where ships,

-6in order to pass under each bridge must have each one of them open. The automobile traffic over the bridges is interrupted when a ship is passing under it. Suppose that at least one of the bridges must be available for automobile traffic. Suppose that the arrival of ships from one direction (the ships coming from the other direction can be scheduled) is a Poisson process. Here the bridge open to ships represents an available server. The basic feature of our model is the fact that each departure from the first stage corresponds to an arrival at the second stage. This arrival need not be the same unit departing from the first stage. Thus, it is not necessary, as in the examples above, to have a unit (patient, machine, computer program or ship) flowing through the system. We can imagine a situation where a repair man uses a special set of tools for each job. Each set of tools is used only in one job, and they have to be cleaned up by the repair man and returned to a tool crib. The cleaning operating can be performed at any time. Here each completion of a repair generates a set of dirty tools which will joint the queue of the second stage of the system. Numerous investigators have studied sequential queueing systems, but only Nelson [13] has considered the case of a single server. He considers two service centers in tandem with Poisson arrival and exponential service times in each center. A single server switches from one center to the other according to five switching rules, for example: 1) when the server completes service, his next assignment is to perform an operation on that job which has spent the longest time

-7in the system; 2) when the server completes a processing operation, his next assignment is to perform an operation on the job that requires the least service time; 3) the server switches to the other center when the present center is empty. Nelson uses simulation in order to find the mean and the variance of the time in the system, for various values of the traffic intensities of each center. In another paper, Nelson [12] studies the case of assigning a single server to one of two machines in tandem, with the objective of minimizing total in-process inventory cost, over the time period 0 < t < T. He assumes deterministic arrivals and the service times are known a priori. This is a case of what Cooper [6] calls scheduled services (this means that the service times are known when the customer or job enters the system. Nonscheduled services is the case in which the service time is drawn from a certain distribution at the time the service is initiated). Recently, Sahney [17] studied the problem of two machines and one man with setup times, where each job is processed only in one machine. He assumes that all jobs are available for processing at the time zero, and obtains an algorithm to solve the problem of finding the sequence of jobs which minimizes the mean flow time of jobs. This corresponds to the scheduled situation of two parallel service stations and one server. The nonscheduled case, in which the arrivals to each station are independent Poisson processes, is quite relevant to this thesis because the methods of analysis are somewhat related. In Section 3 of Chapter II we shall refer to Takacs' [201 work, where he examines the problem of two queues in parallel, with independent Poisson arrival processes and

-8general renewal service time processes, attended by a single server, who switches, without delay, from one queue to the other when the present queue is empty. He obtains the Laplace-Stieltjes transform of the waiting times in each queue. The case of random length of switching times is studied by Eisenberg [8]. He considers two switching rules (switch when present queue is empty, and the case in which one of the queues has nonpreemptive priority over the other) and finds the LaplaceStieltjes transform of the waiting times. Recently, Eisenberg [9] has extended his retults to a system of queues: that are attended periodically by a single server. Avi-Itzhak, Maxwell and Miller [3] consider the problem studied by Takacs (above), and, by intuitive arguments, find the expectations of queueing times as well as the first two moments of the busy periods. As mentioned earlier, the problem of sequential queues has been studied by numerous investigators. Reich [15] proves that the lifetimes (service time included) of a customer in the two stages of a queueing system, with two exponential service stations in tandem, with infinite queue capacities and Poisson arrivals, are mutually independent. In 1963, Reich [16] generalizes this result for a sequence of m single-channel facilities. In 1964, Burke [4] shows that the waiting times (excluding the service times) in the stages of this system are stochastically dependent and in 1968 [5] he generalizes Reich's result proving the independence of lifetimes in the stages of a sequential queueing system, where the second service time is not necessarily exponential. When intermediate waitingroom capacities in a sequential queueing system are finite

-9the waiting times are quite dependent, since the size of queue depends on whether there is space available downstream. Avi-Itshak and Yadin [2] considered the particular case of two service stations and no intermediate queue, with Poisson arrival and general service distributions. They derived the transforms of the steady-state distributions of the queueing times and the number of customers in the system. Neuts [14] examines the case where the queue capacity in the first stage is infinite and finite in the second stage. The service time distributions in the first and second stages are, respectively, of the general type and exponential. His results include the busy periods, blocked time in the first stage, and the equilibrium conditions of the system. The effect of blocking in the utilization of exponential service stations in series is analyzed by Hunt [11] in one of the pioneering investigations of queues in series. 3. Summary of Results and Organization This thesis is concerned with the description of stochastic aspects of the queueing system above, under each of the indicated policies. We are interested in the state probablities of the system, the waiting times until service begins in each stage, the busy period of the server, and the busy periods of each stage. We assume steady-state conditions. For most of the cases the sufficient condition for existence of the steady state is 1- p - p > 0, 1 2 where p XE[S ] is the traffic intensity in the stage k, k 1,2. kWe de We define:

-10T(k,i,j) = steady-state probability of having i customers in the first stage and J customers in the second stage, just after a departure from stage k. Qk- = expected number of customers in stage k just after departures from stage Q. Wk = time that a customer waits until he commences service in stage k (W includes S and W ). 2 1 1 S B = length of the busy period of the server. Time elapsed since the server started attending a customer who, at his arrival, found the system empty, until the next time the system becomes empty again. B = interval of time during which the server is continuously present at the first stage. B = interval of time during which the server is continuously present at the second stage. In the case of random length of switching times the definitions of BS BI and B are slightly different. In the following table we indicate the number of the page where each result can be found. In the table, R and Z designate, respectively, random and zero switching time. Except where indicated in Table I, the distributions of B, B and BI are found explicitly. For the waiting times, Wk, we only obtained their Laplace-Stieltjes transform and the mean value. Chapter V contains some numerical calculations and concluding remarks.

Table I Results -'- S I III ha]cy, (k; to ) kl Wk B B B.Chapter Policy i Wk II LNB Z 32 26 27 29 30 30 LNB R 45 43 45 47** 47 48 r11' iS4 4 8 - III SSP z 51 52 52 53 53 5 SSP R 51 52 52 53 3 53 S, FSP Z 56 56 57' 57 57 58 FSP R 61 62 64 ** 65 66 SSS (Q = N) 69* 79 80 x 8 83 82 IV WFS 89 90 90 91 92 93 SFS (Q > N) 97 98 99 99 99 100 * Only characterized by the generating function. Conjecture. Unsolved.

-12Each chapter is divided into sections which may be subdivided into subsections. The sections within a chapter are numbered by n(n = 1,2,....) and the subsections are numbered by n.k(n = 1,2,..., k = 1,2,...). The equations are numbered within sections, for example, Equation (3.11) means the 11th equation of section 3 of the present chapter. References to other chapters are made by stating explicity the number of the chapter. 4. Terminology and Methods In addition to the symbols already defined the following designations will be helpful: I-customer: A customer in the system who has not completed service in the first stage. 2-customer: A customer in the system who has completed service in the second stage but not in the first stage. T: Time at which the nth departure occurs (departure from either stage). En: Type of the customer departing at T. Qk,n: Number of k-customers in the system Just after T. hn,n+h n Phn[(Qab) e-(k,ij)] = P[E = kQ]= iQ,= j E -,Q = a,Q =b] 2,n From the assumptions on the arrival and service processes, the stochastic process En Q1 nQ ) is a homogeneous Markov chain, that is, ni, in 2,n the probabilities above are independent of n for all (~,a,b) and (k,i,j). When h = 1 we drop the subscript h in the notation above.

-13The infinite system of linear equations 2 00 00 (iij) = 2 1 rt(.ab) P[(Ia,b) - (k,i,j)] -=1 a=o b=o (k = 1,2; i,j 0,1,,...) with the restriction 2 co 00 I I I TC(kij) = 1 k=i i=o j=o will be referred to as the stationary conditions (in the text the restriction above is always implicit), and the set (T(k,i,j)) as the stationary distribution of the chain. In order to make sure that our policies are comprehensive as described, we will simply confine attention to the stationary distribution, i.e., the steady-state situation. The analysis of each policy starts by writing down the stationary conditions and then obtaining the generating functions 00 00 Uk(xy) = x y^t(k,i,j) (k = 1,2) i=o j=o which are used for finding the expected values k = 1 U (XX 2) IX =X =1 (k,= 1,2). 1 2 ( = 12)

-14Qk. = U (1,l)Qk + U2(1,1) (k=1,2) and Q = Q +Q 1. 2* The waiting time distributions, Wk(t), are characterized by their Laplace-Stieltjes transforms, Wk(s), in terms of Uk(x,y), from which we can obtain the expected values Wk. The distributions of the busy periods, B (t), BI(t) and BII(t), are found in terms of it(k,i,j) and of the distribution of the busy period of an M/G/1 queueing system with appropriate service time distribution. In general, given a random variable V, we use the symbols V(t), V (or E[V]) and V(s) for the distribution of V, the expected value of V, and the Laplace-Stieltjes transform of V(t), respectively. We also define = oo (2t)i -et P. - dS (t) and q = (. t dS (t) 0 1. 2 as the probabilities of having i arrivals during a service time of a 1-customer and 2-customer, respectively. The corresponding generating functions are

00 P(x) = piX = s [(1 -x)] i=o and 00 Q(y) - qI y =s [x(-x)J, i=o which converge for x l < 1 and jy < 1. Additional symbols are defined in the text as they become necessary.

CHAPTER II LEAVING NO BACKLOG 1. Introduction In this chapter we study the LNB policy (Leaving No Backlog). Under this operating rule the server remains in one stage until it is empty (no backlog), then he switches to the other stage. We consider separately the cases of zero switching times and random switching times. We use transform methods in order to find the expected values of pertinent random variables. We also present a direct approach for finding the state probabilities, based on properties of the busy period of an M/G/1 system. 2. Stationary Conditions (Instantaneous Switching) In this case the server becomes immediately available in the second stage after he completes the service of the last customer present in the first stage, and vice-versa. We have i+i (2.1 ) (a) Pi-a+l T(2,a,0)+ Pi t(2,0,0) (i > ), a=l i+1 (b) (,ij) (aj - 1) (i > 0, j > 2), a=1 i (c) =(2, i,)-a = q (2,a,j + 1) + qi t(l,O,j + 1) a=o (i> O, j >0). -16

-17ii Multiplying both sides of these equations by x y and adding separately oo i+l oo (2.2) U (x,y) = Pi-a+1 T(2,a,O)xiy + pi r(2,0,0)x y i=o a=l i=o oo oo i +1 P -a+l 1(l,aj - l)xiy j=2 i=o a=i and 00 00 (2.3) U (x,y) = (l,O,j + 1)xiy 2 i j=o i=o 00 oo i + qi (2,a,j + 1)xiy3, a~ Z Z Zi-a j=o i=o a=o which, in view of the property 00 i+1 o00 (24) Z Z a,i a+l,i+a i=o a=i i=o a=o and the fact that J(1,i,O) = 0, (i > 0), give (x - 1)r(2,o,0) + U(x,0) - U (O,y) (2,5) U (x,y) = 2 yP(x) 1 x - yP(x) and

-18U (O,y) - U (x,O) (2.6) U (x,y) 2 Q(x) 2 y - Q(x) In order to characterize completely the distribution [(t(k,i,j)) by the transforms Uk(x,y), we need to determine U (O,y), U (x,0) and it(2,0,0). 3. Determination of U (O,y), U (x,O) and T(2,0,0) _1 2 Since IQ(x) I < 1 for Ix < 1, it is clear that the denominator of the right-hand side of Equation 2.6, for each x in the domain Ix| < 1, has only one root in the domain lyl < 1, namely y = Q(x). The numerator of Equation 2.6 must vanish when y = Q(x) because jU (x,y)I < 1 if xl < 1 and lyl < 1. Thus, letting Q = Q(x), we get (3.1) U (x,O) = U (,Q). 2 1 If lyl < 1, the inequality Ixl > lyP(x)l holds on the boundary of the domain Ix < 1. Therefore, by Rouche's theorem, the denominator of the right-hand side of Equation 2.5 has just one root in the domain Ixl < 1. If IlY = 1 we prove by the Taylor expansion of P(x) about x = 1, that the inequality |xl > lyP(x)l = IP(x) holds on the boundary of the domain Jxi < 1 + e, for small e, under the restriction p = (d/dx)P(x)I _ < 1, which we shall assume. We have 1 X1 00 P(1 + E) = 1 + p + 1 p(n)(l)n n=2 < 1+p e + ( -p )e = 1 +, 1 1

-19for some E > 0. Hence, by Rouche's theorem, the equation x = P(x) has the same number of roots in the domain Ix < 1 + c as the equation x = 0, namely one root. Since x = 1 is a root of x = P(x) we conclude that x = yP(x) has just one root in the domain Ixl <_ 1, given ly <_ 1. Denote this root by 5(y). When x = 6(y), that is x = yP(x), the numerator of the right-hand side of Equation 2.5 must be zero, since IUl(x,)l < 1 in the domain Ixl < 1 and lyj < 1. Thus, letting 6 = 6(y), we get (3.2) U (0,y) = t (6,0) + (6 - 1)t(2,0,0) 1 2 Next we present an iterative scheme for determining U (x,y) and U (x,y). A similar scheme is used by Takacs [20] in the case of 2 two queues in parallel attended by a single server. Let x0 = x and yo = y with Ixl < 1 and lyj < 1. Define x. and Yi, i > 0, by (3.3) Xi+ - 6(yi) and (3.4) Yi+ = Q(i) Substituting Equations 3.3 and 3.4 into Equations 3.1 and 3.2 we get (3.5) U (O,y ) = X (x.,0) + (2,0,0)(x - 1)

-20and (3.6) U (xi,) = U (Oyi ) 2 1 -1 L+ Adding Equations 3.5 for i = 0,2,...,2N-2, to Equations 3.6 for i = 1,3,...,2N-1, we obtain N (3.7) U (,y)= (2,0, 0)- 1) + U(,y2N) 1 1xn- n=l Similarly, let i = 1,3,...,2N-1 in Equation 3.5 and i = 0,2,...,2N-2 in Equation 3.6. Adding up these equations we get N (3.8) (xO) = t(2,0,0) (x - 1) + 2(x2N) n=l We shall now show that x2N and Y2N tend to one as N tends to infinity, and that the series N \ (2- 1) and (X2n - 1) n=1 n=1 are convergent. We will first study the behavior of the functions x y(1)(x) = P(x and Y(2)(x) = Q(x) which have been used in definitions (3.3) and (3.4). We have the following properties:

y( )(O) =; y()(l) = 1; )() yl)(l) = I-P y()(0) =; y(2) =; i)(0) = q; )() = P Also notice that y()(x) = y(2)(x) implies x - P(x)Q(x) = 0, which, by Rouche's theorem and the condition 1 - p - p > 0, has 1 2 just one root in the domain jxl < 1 (see arguments preceding Equation 3.2). Since x = 1 is a root, we conclude that the graphs of y( )(x) and Y(2)(x) have no intersection in the domain Ixl < 1, except at x = 1. From the preceding properties and the fact that y (x) is convex and y( )(x) is concave (since P(x) is convex), we can sketch the graphs of these functions as in Figure 1. It is clear from the graphs above that the sequences (x n and fYn) converge to one. In order to prove that the series N X (1 - x ) 2n-1 n=1 is convergent we obtain y*(x) =W -p )x+p and y **(x) p x+ (-p),

-22- t kx'I t _._......- f -.. 4.:! / I /!' X j / I f: / )C0 4i Figure T. Illustration of the Iteration Scheme for Finding U (O,y) 1 and U (x,O).

-23which are the equations of the tangents to y( )(x) and y(2)(x), respectively, at x = 1. Define 1 - 1 xi+ I -p Yi -p 1 1 and _ - x x +(l -p) Yil = P2 2 for i = 0,1,..., with x = x and yo = yo. By the convexity of y(1)(x) and the concavity of y(2)(x) we have y( )(x) > y (x) and y(2)(x) < (x). This implies 1 - x = 1 - x 1 - x < 1 - x,.... Therefore it suffices 0 0 2 2 to prove that N \ (i -- ) ~ J', ~ ~ 2n-1 n=i converges. This can be easily seen from the definitions of x. and yi, from which we get n-1 X 2__ n (l y - X2n- 1 a(1 - o 1 N This proves the convergence of E (1 -x ), since 1 - p p > 0. Nn'i 1 2 n-1i n N In a similar way we can prove the convergence of (1 - x ). n= We may now write (3.9) A (y) = (1 2n 1 2n-1 n=and

-24o00 (3.10) A (x) - ( -x ) 2 2n n=1 which are positive and finite for Ix| < 1 and Iyj < 1. Hence, Equations 3.7 and 3.8 become (3.11) U (O,y) = -t(2,0,0)A (y) + U (0,1) 11 1 1 and (3.12) U (x,0) -r(2,0,0)A (x) +U (1,0) 2 2 2 Setting xo = yo = 0 in Equations 3.3 and 3.4 we get x = x 2n 2n+i n = 0,1,..., which implies A (0) = 1 +A (0). Noting that U (0,0) = 0 1 2 1 and U (0,0) = i(2,0,0) we obtain 2 (3.13) U (0,1) = U (1,0) = A (0)>(2,0,0) 1 2 1 which yields (3.14) U (O,y) = [A (0) - A (y)]t(2,0,0) 1 1 1 and (3.15) U (x,0) = [A (0) -A (x)]J(2,0,0). 2 1 2 See remark following Equation 6.6 for the interpretation of A (0). 1

-25The value of j(2,0,0) is found from the condition U (1,1) + 1 U (1,1) = 1, where U (1,1) and U (1,1) are obtained from Equations 2.5 2 1 2 and 2.6 by applying L'Hopital's rule. We get (3.16) (2,0,0) =- (1 - p - ). 21 2 We see that the condition for nonsaturation is 1 - p - p > 0. 1 2 The factor 1/2 in Equation 3.16 is due to the fact that the same customer is considered twice in the embedded chain. At this point we have completed the characterization of the steady-state joint distribution of the number of customers in each stage of the system and the type of departing customer, 7t(k,i,j), which is done by Equations 2.5 and 2.6 where the values of U (0,y), U (x,0) and 1 2 r(2,0,0) are given by Equations 3.14 through 3.16. In Section 7 we shall present a preferable method for finding t(k,i,j). We shall also give an example to show that the approach of this section is very -I -II efficient for calculating B and B 4. Expected Number of Customers In this section we shall calculate the expected values Qk~' Qk.' Q and Q, which are defined in Chapter I. The partial derivatives of Uk(x,y) are obtained from Equations 2.5 and 2.6. The limits of these derivatives, as x and y tend to one, are indeterminate; however L'Hopital's rule can be applied in order to resolve the indeterminacy. The first and second derivatives of U (x,0) and U (0,y), which are necessary in the calculations, can be 2 1

-26obtained by using Equations 3.1 and 3.2. The derivatives of 6(y) are found, by implicit differentiation, from 5(y) = yP[6(y)]. Let X2E[(S + S )2] (4.1) Qo 2(1 -p p) 1 2 This is the expression for the average number of customers waiting in an M/G/l queueing system whose service time distribution is the convolution S *S (t) (Cooper [6], page 164). We get the following 1 2 results: 1 - p (4.2) Q (1 +Qo) p p!1 2 0 1 -p + p 1 2 (2)2 o 2 1 - 1-p +p 1 2 (4.5) Q' =2 ( p4 + 1 1 2 (4. ) (Q - + p + Q ) p 21l2 2 o 1-p P +p 2 Q221 2 (4.8) +p + (1 ) + (2 -p ))Q] 1 22 1 1 - + p p (4.6) Q (p + + p Q 1. 2 1 2 0 (4 7) Q ( + p + ) 2. 2 1 p 2 0 + P 1 2 (4.8) + t- p + (p p + (2 p+)Q0]1- p t Q2 2

-27(4.10) = [ + (p + ) (2+ p +) + 3 + P )Q 1 2(1 -p + ) 1 2 In the following table we compare (when S and S are exponential) 1 2 some values of Q obtained by Nelson [13] through simulation (32,000.2 arrivals), with the values calculated by Equation 4.9, for various values of p and p 1 2 Table II Values of Q Obtained by Simulation and by Equation 4.9 2 p =0.1 p =0.2 p =0.3 p =0.45 p =0.6 p =0.7 p =0.8 1 1 1 1 1 1 1 p =0.8 p =0.7 p =0.6 p =0.45 p =0.3 p =0.2 p =0.1 Simulation 2 2 2 2 2 2 2 Simulation (Nelson [13]) 8.51 8.50 8.86 10.14 13.13 18.04 19.96 Equation 4.9 8.54 8.38 8.73 10.90 13.11 17.96 29.80 5. Waiting Times Let Wk denote the time a customer waits until he commences service in stage k (W includes W and S ). We can find the Laplace-Stieltzes 2 1 1 transform of Wk by an argument that is also available for the M/G/1 queueing system. A customer departing from the first stage will leave behind him i customers who arrived during his waiting time W and his 1 service time S. Thus 1 U(1, 1)~ Z:Ol,.=.. dW * (t) U1 0= 1 1 1~ j-

-28which gives U (x,l) 1 (,l W [X(l - x)] J S [X(l - x)] U (1,91) 11 1 1 or 2U (1 - S/X,1) (5.1) W (s) = I 1~ ~~s (s) 1 where RE(s) > 0 and 1\ - sl < X. Similarly, a customer departing from the second stage will leave behind him (in both stages) i customers who arrived during his waiting time W (which includes his waiting and service time in the first stage) 2 and his service time S. Thus 2 1 7 i(2,a,i - a d) =, U JT(1,TY ~ L 2 2 2 a=o a/.o which implies 2U (1 - s/X,l) (5.2) W (s) 2 2^~~ S (s) 1 where RE(s) > 0 and 2\ - s < \. The expected values of W and W are obtained by differentiation 1 2 of Equations 5.1 and 5.2. We get (.3) W _ (s) = -S orQ = \(W +S ), 1 ds i' s0 1 11 1 1 where Q is given by Equation 4.2. 11

-29d 2 d (5.4) - (W(s) - U -U(x,x) -S 2 dS 2 lSz=O dX 2 X=1 2 - Q -S or Q = \(W + ),.2 2.2 2 2 where Q is given by Equation 4.9..2 6. Busy Periods Clearly there are two different categories of busy periods. First, S the busy period of the server, B, is the time elapsed since the arrival of a customer who finds the system empty, until the departure of a customer who leaves an empty system behind him. Notice that at the completion of a busy period of the server, regardless of the order in which the customers are serviced, all of the customers have completed their two-stage service, which has the distribution S * S (t). 1 2 Therefore, this busy period has the distribution of the busy period of an M/G/1 queueing system whose service time distribution is S * S (t). 1 2 Its expected value is B = (S + S )/(1 - p - p ) (Cooper [6], 1 2 1 2 page 176). We define B and BII as the time the server is continuously busy in the first and second stages, respectively. The busy period B starts immediately when the second stage is emptied and i > 1 customers are present in the first stage. In this case the distribution of BI will be Bi(t), the distribution of the busy period initiated by i customers in an M/G/1 queueing system with service distribution S (t). When i = 0 the busy period starts at the time of 1 the next arrival and it has distribution B (t). Thus 1

-3000 (6.1) BI ) = (1) (2,0,0)B (t) + x(2,i,0)B(t) 2 i=o The Laplace-Stieltzes transform of B (t) is 00 (6.2) B (s) = 1 { (2,0,0)B(s) + t(2,i,)[B(s)] } 2 i=1 = w1T { ( -p - p)[B(s) - 1] +U[B(s),O]} where B(s) = B (s) and B.(s) = [B(s)] since Bi is the sum of i'i 1 independent initial busy periods (that is a busy period initiated by just one customer). The value of U [B(s),O] is given by Equation 3.15. 2 The distribution of the time the server is continuously servicing 2-customers is 00 (6.3) B (t) = U ( 1) j(1,O,j) S (t) 0, 1) 2 1 j=l where S J(t) is the j-fold convolution of the service distribution S (t) 2 with itself. The Laplace-Stieltzes transform of BI(t) is 00 -II 1 VsP (6.4) B (s) (or 17 Tt(lOyj)i2 1 j=l 1 o U [o,S (s)]

— 31The expected values of B and B are (6.5) - B() _-_ = u S- L[ ( - - p - -I d s: S=O U (1,71 2 1 p ____2 1 +I- Ip (o) 2 1 2 1 i A (0) 1-p -p 1 1 2 and (6.6) II = d -B (s) 2 1 2 A (0) l-p -p 1 1 2 where U (0,1) and U (1,0) were obtained from Equation 3.13 and A (0) is given by Equation 3.9. Remark = (...... -p i 1 2 2 [-I -II 1 1 2, =B +B A~ijJ~1-pAS +B 1 1 2 1 This implies that A (0) = B/(B +B ) is the average number of cycles 1 in the busy period of the server (a cycle starts when the server commences service in the first stage and terminates when all the customers, who were served during the busy period in the first stage, have completed service in the second stage).

-327. Alternative Approach for the Calculation of the State Probabilities In this section we present a direct method for obtaining the state probabilities t(k,i,j). It is based on known properties of the busy period of an M/G/1 system. Define b (i) = probability that i departures occur during a busy period of the first stage that starts with m customers (i > m > 1). ai(n) = probability that n arrivals occur during the service time of i 2-customers (i > 1, n > 0). ck(n) =probability that, starting with an empty system, the termination of the kth cycle occurs when there are n customers in the first stage (k > 1, n > 0). We have 00 (7.1) c(n) b1(i)a.(n) (n > 0) i=1 00 00 ck(n) c(m)b (i)ai(n) (k > 1, n>), m=1 i=m where (7.2) b(i) -= (- t)- e dS (t) (i > m > 1) 0 (i - m) and (7.) ai(n) = Li et dS (t) 10 2

-33The state probabilities x(2,n,0) can be written as 00 (7.4) jT(2,n,0) = j(2,0,0) ) ck(n) (n > 0) k=1 where T(2,0,0) = 1/2(1 - p - p ). The probabilities t(l,i,j), and t(2,i,j) for j f 0, can be calculated by Equations 2.1. The average number of cycles during the busy period of the server is oo (75.) c = kck(O) k=l 8. Comparison of the Methods of Sections 3 and 7 With the objective of comparing the iterative approach of Section 3 with the alternative approach of Section 7, we have made a few experimental computations for the case of exponential service time. Evidently, if we need to calculate each value of the state probabilities, the method of the previous section is preferable. However, 00 when we need only U (0,1) = U (1,0) = Z x(2,i,0), as in the cases 1 2 -I -I of the expected values B, B and c (see Section 6), the iterative method of Section 3 has some advantages. We shall illustrate this point by the following computations. Let A = 1 and, consequently, p = S and p = S. We assume 1 1 2 2 that S and S are exponentially distributed and calculate the values 1 2 of c (average number of cycles during the busy period of the server) by each of the methods mentioned above, for various values of p and p. 1 2

-34a. Computations Usin the Iteration Scheme of Section 3 We first obtain P(x) = [x( -x)] = + 1 ) and Q(x) - S[(1 - x)] = i+ (1 -x)p 2 Using Equations 3.3 and 3.4 we get x. = + (1 + )X. - xi Yi P(xi+ 1 +1 1 1+1 and (8.1) y 1 + (1 - x)p Thus 1 + p - (1i + p ) p yi (8.2) xi = (Y-) =2p 1 1 i+1 2p (since jxi+l I < 1 for Yi I < 1). In order to calculate the quantity c = A (0) (see remark following Equation 6.6) we construct Table III 1 from Equations 8.1 and 8.2, where yo = 0. This table corresponds to p =p =0.4. 1 2

-35Table III Illustration of the Iterative Scheme of Section 3 for p = p = 0.4 1 2 i yi x 0 0 1 -- 0 ~2 0.71?28 r -- 3 -- 0.62005 4 0.86807 -- 5 -- ~= 0.80537 6 0.92777 -- 7 -- O- 0.88798 30 0.99959 31 -- 7- 0.99932 00 -(- ) - 1.8787. For other The value of c = A (0) is (1 - x2i ) 1.8787. or other 1 iO2-1 values of p and p we get the values of Table IV, where i(0 0001) is the 1 2 number of terms in the series of A (0) for having an accuracy of 1 0.0001.

-36Table IV Values of c for Different Traffic Intensities p = p+p p p 1 2 1 2 (O L0001) c 0.900 0.800 0.100 9 1.390 t" o0.450 0.450 26 2.295 t" 0.100 0.800 41 2.895 0.500 0.400 0.100 5 1.165 "t 0.250 0.250 7 1.358 1" 0.100 0.400 9 1.516 0.100 0.090 0.010 3 1.010 1" 0.050 0.050 4 1.052 ".0.010 0.090 4 1.091 The values of Table IV were calculated by an IBM 360/67 computer (MTS system of The University of Michigan). The CPU time for calculating all the cases was about six seconds (including compilation of the Fortran program). b_. Computations Using the Method of Section 7 We first find ( i-m- _ I. i b ( i = i m 1 + p 1 + P (i > m > 1) fbo Eiu m 2m i-m ai from Equation 7.2, and a;(n) = (L+i)r > T r 1

-37from Equation 7.3. Next, we use Equations 7.1 for calculating ck(n). Equation 7.5 is then used for obtaining c. Table V gives the values of c (for the same values of the traffic intensities of Table IV), where N is the number of terms of the summations of Equations 7.1 through 7.5, and t is the approximated CPU time (in seconds) for compiling the Fortran program and calculating the values of c, for all traffic intensities. Table V Values of c Calculated by the Direct Approach, for Different Traffic Intensities and Different Truncations of the Infinite Summations c p=p +p p p N = 5 N = 10 N = 15 N = 20 1 2 1 2 t = 7 t 27 t = 122 t = 200 0.900 0.800 0.100 0.904 1.033 1.032 1.119 0.450 0.450 1.261 1.640 1.850 1.970 " 0.100 0.800 1.427 1.991 2.309 2.500 0.500 0.400 0.100 1.092 1.150 1.161 1.163 0.250 0.250 1.295 1.354 1.358 -- 0.100 0.400 1.426 1.513 1.516 0.100 0.090 0.010 1.010 1.010 1.010 0.050 0.050 1.052 1.052 1.052 0.010 0.090 1.091 1.091.091 -

-38Comparing the values of c in Tables IV and V we see that this second approach is quite inefficient for high values of the total traffic intensity p = p + p. In the first method the convergence 1 2 is quite satisfactory for all values of p. In using the direct approach for more general cases, we expected to have difficulties with the integrations of Equations 7.2 and 7.3, in addition to the large amount of calculations involved in the recursive relationship (7.1). In using the iterative scheme of Section 3 we, in general, expect no difficulties in obtaining P(x) and Q(x), and the solution of xi+ = 6(y) can be found by simple search techniques, because of concavity of y = x /P(xi+ ). i 1+1 1+1 Hence we conclude that, in general, the iteration scheme of Section 3 is a better method for calculating the expected values of I TII B, B and c. i. The Case of Random Duration of Switching In this section we shall review the previous sections under the assumption that there is a random time Tkg with general distribution Tk(.) for switching the server from stage k to stage g (k,Z = 1,2 and k S p). Define (9.1) t - f t dTk (t) i i! kk 0 the probability of having i arrivals during the switching duration TkZ. Also define

-3900 (9.2) (x) = x-t = Tk[X(x - 1)] 1=0 i=o In this case the stationary conditions are i+1 i-a+i (9.3) (a) T(1,i,1) = t b P-a-b+,) a= 1 b=o i+l + + tpb P (O7T(2,0,0) + t p(2 (i > 0) b=l i+l 12 (b) Tr(l,i,j) = Z pi a+(laj-l) (i>0, 12) (c) Tr(2,i,) = b tb qib T(1,Oj + 1) b=o i + Ti-a 7(2,a,j + 1) (i > 0, J > 0) a=o from which we get (x - 1)t21 7(2,0,0) + R (x)U (x,0) - U (0,y) (9.4) (x,y) 1 yP(x and R (x)U (,y) -U (x,0) (9.5) (x,y) 12. 2.(x) 2 Y- Q(x)

-40Notice that in the case of instantaneous switching we have t2 = R (x) = 0 12 R (x) = 1, in which case Equations 9.4 and 9.5 reduce to Equations 2.5 21 and 2.6. By the arguments used to derive Equations 3.1 and 3.2 we get (9.6) U (x,0) = R (x) U (0,Q) 2 12 1 and (9.7) U (O,y) = R ()U (6,0) + (6 - 1) t21 7(2,0,0) 1 21 2 0 where 6 = 6(y) is the inverse function of y = x/P(x). Using Equations 3.3 and 3.4 we get (9.8) U (x,0) = R (x. )U (0,y ) 2 12 1 i+1 and (9.9) U (0,y ) = R (x. )U (x.,0) + (x - 1)t21 7T(2,0,0) 1 1 21 +1 2 1+1 1+1 0 Set i = 0,2,4,... in Equation 9.9 and multiply each resulting equation respectively, by 1, R (x )R (x ), R (x )R (x )R (x )R (x), 12 1 21 1 12 1 21 1 12 3 21 3..., set i = 1,3,5,..., in Equation 9.8 and multiply each resulting equation by R (x), (x)R (x )R (x ), R (x )R (x )R (x ) 21 1 21 1 12 1 21 2 21 1 12 1 21 3 R ( )R (x ),...; adding all together we get 12 2 21 5

-4l(9.10) U (O,y) = -(2,0,0)A (y) + B (y)U (0,1) 1 1 1 1 where 00 (9.11) B (y) = (x )R) (x l) 12 2n+1 212+1 n=o and 00 n-1 (9.12) A (y) = (1-x ) TTR (x )R (x2i) 0 2n- 1 1 2 2i+ 1 21 21+1 n=o i=o Similarly, set i = 0,2,4,..., in Equation 9.8 and multiply each resulting equation, respectively, by 1, R1( (x )R ( x ), R ()R (x) 12 0 21 2 12 0 12 2 R (x )R (x),...; set i = 1,3,5,..., in Equation 9.9 and multiply 12 2 21 4 each resulting equation, respectively, by R (x ), R (x )R (x)R (x ), 12 0 12 0 21 2 12 2 R (x(x (x )R (x )R (x )R (x ),...; adding all together we get 12 0 21 2 12 2 21 4 12 4 (9.13) U (x,0) = -7(2,0,0)A (x) + B (x) U (1,0) 2 2 2 2 where 00 (9.14) B (x) = T |R (x )R (x 121 2n 21 2n+2 n=o and 00 n-1 (9.15) A (x) = t21R (x) (1-x ) R (x.)R (x.) ( ) 2 0 12 21 2Ri* (x212i= n=l i=1

-42where b I Pi = 1 TT^-p i=a when a > b. The values of U (0,1) and U (1,0) can be found from Equations 9.10 1 2 and 9.13 by setting x = y = 0, and noticing that U (0,0) = 0 and U (0,0) = 7r(2,0,0). We have A (0) 2+ (9.16) U (0,1) = B(0 (2,0,0) and U (1,0) = (20,0) ~1 ~~B. (O2 B (0 (2o,) i 2 But when x = y = 0 (x = y = 0) we have x = X = 0,1,2,..., which implies A (0) =t2 [1 + A (0)] and B (0) = t2 B (0). Hence 1 0 2 1 0 2 A (0) (9.17) U (0,1) = U (1,0) = ( (2 0,0) 1 2 B (0) which substituted in Equations 9.10 and 9.13 yields A (0) (9.18) U (0,y) = 1. B (y)- A (y 7r(2,0,0) 1~B (o):, and A (0) (9.19) U (x 0) = ) A () (2,0,0) 2 B (0) 2 2

-43For the case of instantaneous switching we have t21 = R (x) = 0 12 00 R (x) = 1 and, consequently, B (y) = B (x) = 1, A (y) (l- x ) 21 oo 1 2 1 n=o 2n+1 and A (x) = Z (1 - x ). Therefore, Equations 9.18 and.19 reduce 2 n= a2n to Equations 3.14 and 3.15, respectively. In order to determine t(2,0,0) we use the fact that U (1,1) + U (1,1) = 1 and apply L'Hopital's rule to find lim Uk(x,y) k= 1,2 x l y l we get i-p -p (9.20) T(2,0,0) = 9.1. A (0) 2[t21 + X(T + T ) o 12 21 B (0) Notice that, independently of the switching times, 1 - p p > 0 is the condition for the system to be unsaturated. 2 9.1 Expected Number of Customers. Defining' 0 XE[T ] and using Equations 9.6 and 8.7 we obtain (9.21) U1' (0,1) = U(0,y) 1 -(2 1 )l -' p + P') dy1 2 (y p 1 2 1 2 FE[T + 20 U (0,(1) LX2E+[( T )2] U (0,1) + ( + + 2p U (01) 12 21 1 12 21 2 1 1 + 1 p X2E[S2]U (0,1)) + p + 2p t21 r(2,0,0) ~P I 12 +1 + 1-.... + t21'(2,0,0) +L X2E[S2) 1- p 1\2 o. 2 1

-44and (9.22) U" (1,0 U,O) = X2 U[T2 ]U (0,1) + 0 p 2 dX2 2 X-d 12 1 12 2 +2 X2E[S2] + 2 X2E[CT +T )2]U (0,1 2 2 (1 - p -p )1 - P 12 21 1 1 2 1 2 + (e + + 2p U (0,1) + E[]U (0,1 12 21 2 1- 1-1 1 + p + 2p t2 r(2,0,0 + t 21 7r(2 0,0)) 12 1 1 p 2 0 1 2E[S2] + 1 x2E[S2] 1 2 2 where A (0) U (0,1) = B ( r(2,0,0) 1 B (0) 1 and Tr(2,0,0) is given by Equation 9.20. From Equations 9.4 and 9.5 we get (1 - p )A" + X2E[S2 ]A' (9.23) - U (x,y) = Y=1 2(1 - p ) Y=1 1 (9.24) - (x,y) - U(0,1) ay x=I 2 2 1 Y= 1 p B" - 2E[s2]p d^.es U, 2 2 2 2 (9.25) i- 2(Xly) - X — 1 22 YV 2p2

-45(9.26) xU (xy) -2 U (, 1) Y= where A' = ( + 0 )U (O,1) + + t 1T(2,0,) 12 21 1 2 2 0 A" = [X2E[T2 ] + 2p (0 + e ) + 20 e i U (o,1) + 0 p 21 1 12 21 12 21 1 21 2 + 2p t21 7(2,0,0) + p P + U"(,O), i 0 1 2 2 B" = X2E[T2 ]U (0,1) p2_ U"(1,0) 12 1 2 2 The expected values Qk'k.' Q and Q can be obtained by using Equations 9.23 through 9.26. 9.2 Waiting Times. Equations 5.1 through 5.4 still hold for this case of random length of switching. The quantities Q and Q of Equations 5.3 and 5.4 are obtained by the procedure indicated 2 above. 9. Alternate Approach for the Calculation of the State Probabilities. Let b (n), ai(n) and ck(n) be as defined in Section 7, and let tk be defined as in Equation 9.1. We consider the server busy during switching times. We have

-46(9.27) c (n) = 2 (t21b (j)t2aj(n - Q) (n > 0) i=o J=i Q=o and 00 00 00 00 ck(n) = (m)t2ib (J)t2aj(nm=o i=o j=i+m Q=o (k > 1, m >0) These equations represent the fact that new arrivals may occur during the switching times T and T. As in Equation 7.4, the state 12 21 probabilities 7(2,n,0) are given by 00 (9.28) Tr(2,n,0) = 7(2,0,0) ) ck(n) k=1 where Tr(2,0,0) is given by Equation 9.20. The quantity 00 (9.29) c = kck(0) k=1 is the average number of cycles during a busy period of the server The remaining state probabilities are obtained from Equations 9.3.

-47S 9.4 Busy Periods. A busy period of the server, B, commences when the server is idle in the first stage and a new customer arrives, it terminates when, at the end of a switching interval T, the system 21 is empty. B is the time the server is continuously present in the first stage including the switching interval T, B is defined 12 similarly. Let BS be the busy period of the server when the switching is 0 instantaneous. In the case of random duration of switching, in each cycle of the server, additional arrivals have to be served and each S S of them will add a random time to B which has the distribution of B. o o We conjecture that on the average we have (9.3o) -s -- (9.30) B = +( + (T +T )C B + (T T )C 0 12 21 0 12 21 where = (S + S )/(l - p - p ) and C is given by Equation 9.29. 0 1 2 1 2 However, we do not utilize this conjecture. The distribution of B and BI are given by 00 00 (9.31) B (t)= U (1,0) T t U (12,0)tj +j 12 L2 i=1 J=o + 7r(2,0,0)t2 1B *T (t) + 7(2,0,0)t2B *T (t) j j 12 0 1 12 i=l and

-4800 (9.32) BU (t) = 7 (1,0,j):* T (t) U (OJ~/ L-..u 2 21 1 =i1 where Bi*T (t) is the convolution of the busy period distribution of the first stage, initiated by i customers, with the switching time distribution T (t). S*j * T (t) is the convolution of the distribution 12 2 21 T (t) with the j-fold convolution of the service time distribution 21 S (t) with itself. 2 The Laplace-Stieltjes transform of these distributions are,'I 1 E r 0 (9.33) B T ) = (s)R [B() U [ B(s),0] - 7(2,0,0) U K1,0) 12 21 t 2 + T (s) [R [i(s)] - t2] Tr(2o,o) 12 2 1 0 + T (s)t2 B(s)7T(2,0,0 12 0 and (9.34 B (s) =T (S) U [O,S(s)] (0,1) where U (x,0) and U (0,y), R (x), t2o and 71(2,0,0) are given by 2 1 21 0 Equations 9.16, 9.2, 9.1 and 9.20, respectively. The expected values of BI and B are (9.35) BI = — BTs ds s=o s BB(0) 0 + )- 2 12 1 - 12 21 A (0) o ( ))

-49and (9.36) B = -(s) ds s=o B (0) S - + -1 2 21 A (0) 27T(2,0,0) 1 where A (0), B1 (0) and 7T(2,0,0) are given by Equations 9.12, 9.11 and 9.20, respectively. Note: Do not confuse S (0) of Equation 9.11 with the distribution of 1 the initial busy of the first stage at t = 0, which is zero. Notice that when T = T = 0 we have B (0) = t21 = 1 and 21 12 1 0 Tr(2,0,0) = 1/2(1 - P - P ); therefore Equations 9.35 and 9.36 reduce t 2 to Equations 6.5 and 6.6, respectively.

CHAPTER III SIMPLE NONPREEMPTIVE PRIORITY 1. Introduction In this chapter we determine the operating characteristics of the SSP policy (second stage priority) and of the FSP policy (first stage priority). Under the SSP policy the analysis of the behavior of the system is quite simple since each phase of each customer's service is performed without interruption. This is the case of an M/G/1 queueing system. However, in order to be consistent with the analysis of the other policies, we shall choose the Markov chain embedded at departures from either stage. The switching durations can be assumed to be part of the service times, therefore we present only the case of instantaneous switching. This policy could also be called "follow the customer," since the server switches to the second stage when the customer is served in the first stage. By contrast, in the FSP policy the server switches to the first stage at the service completion of 2-customers if one or more 1-customers are present. 2. The SSP Policy Since there is no queue in the second stage, the state of the system is characterized by the pair (k,i) where k = 1,2 indicates the stage from which the customer is departing, and i = 0,1,... is the number of customers left in the system by the departing customer. We denote by 7T(k,i) the steady-state probabilities. We have -50

-51i+l (2.1) (a) Tr(l,i) = 7(2,a)pia + 7(2,0)p. (i > 1) a=1 i+i (b) 7r(2,i) = 7(l,a)qia (i > 0) a= Notice that a customer departing from the first stage is considered 00 to be in the system. The generating functions Uk(x) = Z T7(i,i)x, i=o k = 1,2, are (2.2) U (x) = P(x)[U (x) - 1(2,0)] + xP(x)7r(2,0) ~~~1 2 and (2.3) U (x) = Q(x)U (x) 2 X 1 from which we get x(x - 1)7(22,0)P(x) (2.4) U (x) = 1 x - P(x)Q(x) The value of 7T(2,0) is obtained from Equations 2.3, 2.4 and the condition U (1) + U (1) = 1. We get 1 2 (2.5) 7(2,0) = 1 (1 - ) 2 1 2 The expected number of customers in the system at departure epochs, Q, is given by

-52(2.6) Q = (1)Q + U (1)Q 1 1 2 2 where - i dxk( d| = kT Uk (x) is the expected number of customers in the system just after the completion of service in the kth stage. We have (2.7) Q = 1 + Q 1 i o (2.8) Q P + P+ Q 2 1 2 0 (2.9) ( 1 + 2p + P) + Q 2 1 2 0 where X2E[(S + S )2] Q = 1 2 2(1 - p ) 1 2 Notice that Equation 2.8 is the Pollaczek-Khintchine formula for an M/G/1 queueing system where the service time distribution is the convolution of S (t) with S (t). 1 2 The time a customer waits until he commences service in the first stage, W, and the time he waits until he commences service in 1 the second stage, W, have distributions whose Laplace-Stieltjes transform are given by transform are given by

-53(2.10) W (s) = (1) A 1 s (s) and U s (2.11) W (s) = () ) 2 s (S) 2 where RE(s) > 0 and \I - s| < A. The expected values are (2.12) W - (Q -1)1 A 1 1 and (2.13) W - -s 2 A2 2 S The busy period of the server, B, has distribution 00 B (t) = 1 0 (u) eXu dS*n * S*(u) S Zn f ~n n-i1 1 2 n=1 which is the distribution of the busy period of an M/G/1 system with service time distribution S *S (t). The busy period of the stages, B 1 2 and B, have distributions S (t) and S (t), respectively. 1 2

-543. The FSP Policy Under this policy the server goes to the second stage only when he has finished attending all of the customers in the' first stage. Once in the second stage, the server keeps attending 2-customers who are present as long as no 1-customers have arrived. If an arrival occurs during the service time of a 2-customer, the server completes serving that customer and then switches to the first stage. If he succeeds in finishing all the present 2-customers and no 1-customers are yet present, he goes to the first stage and waits for the next arrival. We first study the instantaneous switching case. The stationary conditions are i+1 (3.1) (a) r(l,i,l) = p. 7(2,0,0) + pi_ (2,a,0) (i > O) i / 2,,+ Pi-a+ ~ a — 1 i+i i+1 (b) 7T(l,i,J) + p ((2,a, - 1) + Z Pi-a+i L i-a+1 a=1 a=1 (i > 0, > 2) (c) 7'(2,i,j) = qir(l,O,j + 1) + qi r7(2,0,j + 1) (i > O, j > 0) from which we obtain

-55x7T(2,0,0) + U (x,y) - U (O,y) - U2(0,y) (3.2) U (x,y) =. 1 yP(x) 1 x - yP(x) and (3.3) U (x,y) = Q(x)[U (O,y) + U (O,y) - 7(2,0,0)]. 2 Y 1 2 From the arguments preceding Equation 3.2 of Chapter II, and Equation 3.2 we get (3.4) U (O,y) + U (,y) = 67(2,0,0) + U (6,y) 1 2 2 where 6 = 6(y), as before, is the inverse function of y = x/P(x). The value of 7r(2,0,0) is obtained from Equation 3.2 by applying L'Hopital's rule whne x and y tend to one) and the condition U (1,1) = U (1,1) = 1/2, 1 2 knowing that ~ (1) = 1 and'() (1 - P ). We get (3.5) 7T(2,0,0) = (1 -p - p). 2 1 2 Remarks This result and the results (3.16) of Chapter II and (2.5) of the previous section are expected, since, under the corresponding policies, the server is active whenever a customer is present in the system. This does not happen when the system is controlled by the policies SSP(Q > N) and WNFS (Chapter IV). Under a SSP(Q > N) policy the server is inactive when he finishes serving all I-customers and there are less than N 2-customers; under a WNFS policy he is inactive

-56when he finishes all 2-customers and there are less than N l-customers. From Equation 3.3 and 3.4, when x = 6 = 6(y), we get (3.6) U (O,y) + U (0,y) = y () (2,0,0) 1 2 y-Q(6) which substituted into Equations 3.2 and 3.3 gives (3.7) U (x,y) = [y - Q(6)]x- [y - Q(x)] + Q(6) - Q(x) yP(x)r(2,0,0) 1 [x - yP(x)][y - Q(6)] and (6 - )Q(x) 1 - P - P (3.8) U (x,y) = ~ ~-L..)1 2 2 y - Q(6) 2 This last equation, for y = 0, gives 1 qi (3.9) 7T(2,i,0) = ( ( - p ) 2 i 2 qo Using Equations 3.1 we can obtain the remaining state probabilities. 3.1 Expected Number of Customers and Waiting Times. The expected values of the number of customers in each stage at departure epochs are found by the same procedure of Section 4 of Chapter II: from Equations 3.7 and 3.8 we find the derivatives of Uk(x,y), as x and y tend to unity, by applying L'Hopital's rule. The derivatives of 6 = 6(y) are calculated from 6(y) = yP[6(y)] by implicit differentiation. Letting

-57X2E[(S + S )2] Q = ~3 2 o 2(1-p -P ) 1 2 we get 1- p - P (3.10) Q = ( + Q ) ll0~ ~~ P1 ^2 1 1 - p (3.12) Q = p 12 2 and (3.13) Q = (P +Q) 1 22 1 0 1- p The quantities Qk' Q k and Q can readily be obtained from the above results. The waiting times W and W are as in Section 5 of Chapter II, i 2 where Uk(x,y), k = 1,2, is given by Equations 3.7 and 3.8. 3.2 Busy Periods S With instantaneous switching the busy period of the server, B has the distribution of the busy period of an M/G/1 system with service time distribution S *S (t). The reasoning for this is as in Section 6 1 2 of Chapter II. The distribution of B is (3.14) B (t) = (2,i,j)Bi(t) + rr(2,0,0)B(t) i=l =o U (1,1) - U (0,1) + Tr(2,0,0) 2 2

-58and its Laplace-Stieltjes transform is (3.15) B (s) = fU [B(s),l] - U (0,1) + Tr(2,0,0)B(s) 2 2 2 2-p -p - q 1 2 o where B(s) is the Laplace-Stieltjes transform of B(t), the busy period of an M/B/1 system with service time distribution S (t). U (x,l) is 1 2 given by Equation 3.8. The expected value of B is 1 -P P (3.16) 2 -p -p q 1 1 2 0 In order to find the distribution of B, we see that, when this busy period starts, the state of system is (1,0,J) with probability ir(l,0,j)/U (0,1) (conditional to the start of BI). The server will complete service of just one 2-customer with probability Cl- q ) and in a time with the distribution S (t); of just two 2-customers with 2 probability (1 - q )qo and distribution S*2(t); of just k 2-customers 0o 2 with probability (1 - q)qo 1 and distribution S*k(t), 1 < k < j, ~0 ~~0 i'~~~2 j > 2; of just j 2-customers with probability q and distribution S* (t). Therefore we get 2 II3c17 l j-iiS (3.17) II(t) = U 1 L E (1 - q)) o s*k(t) J=2 k=l + 71(1,0oj)q J-ls*(t),

-59whose Laplace-Stieltjes transform is (3.18) B (s) q )S (s) 1 - q s (s) 2 u (o,1) 02 1 ( - S (s))U [0,q S (s)] 2 1 0 2 and whose expected value is -TI 1 (3.19) B =.S 2- p p -p - q 1 2 0 The average number of cycles during the busy period of the server is'S 1- qo (3.20) C = B 1+ 1-p.p B +B -P P B — + iI 2 3 The Case of Random Duration of Switching. In this subsection we shall use the notation of Section 8 of Chapter II. The server, after finishing all 1-customers, goes to stage 2. The switching duration is a random variable T with distribution T (t). 12 12 During T some customers may arrive, but the server will attend to 12 the next 2-customer before switching back to the first stage. The stationary conditions are i+l (3.21) (a) (l,i,l) = tl p T(2,0,0) + 2T(2,0,0) t Pi-a+ t'' a p+ 1 a= 1 i+i i-a+1 + t Pi-a-b+ 7(2,a,0) (i > 0) a=l b=o

-60i+1 i+1 i-a+l (b) 7r(l,i,j) = Pi-a (l,a - 1) + a= 1 a= 1 b=o 21 tb Pia b+il7(2, x,j 1) (i> o0, > 2) i (c) 7T(2,i,J) = ta qi-a 7(1,0,j + 1) + qi.(2,0,j + 1) a=o (i > 0, j > 0) which yield (3.22) U xy) = x yPx t xyP(x)(T(2,0,0) + yP(x) ~[(R (x) - t21)7(2,0,0) + R (x) 21 0 21 U (x,y)- U (0,y)- R (x)U (0,y) 2 1 21 2 and (3.23) U (x,y) = Q [R (x)U (o,y) + U (,y) - 7(2,0,0)] 2 Y 12 1 2 Applying the arguments preceding Equation 3.2 of Chapter II to Equation 3.22 we obtain (3.24) U (0,y) -R () (,y) [(6 - l)t21 + R ()](2,0,0) 1 21 2 0 21 + R (6)U (6,y) 21 2

-61R (6)q+(y-q )(6-l)t21+(y-Q )R (6)-R (6)Q(6) (3.25) U (0,y) =- 21~~, - ~~O 0 21 21 1 y(Y-q )+yR2 (6)q t 2-R ((6)Q(6)[(y- )R (6)+q to ] o 21 t0 21 012 00 y yr(2,0,0) Equation 3.23, as y + 0, implies (3.26) U (x,0) aQ(x)R (x) + $Q(x) 2 12 where = -U (0,y) and d = U (O,y) d 1= yo Y O2 y=O This means that i (3.27) tr(2,i,0) 5 SE qtja + B3i a=o The quantities aC and 3 are given by pq (t21 + t21) + poq t21 (3.28) o = 0.. 70r(2,0 0) qo(1 - p q t21t12) 0 0 0 0 0 and ~~1 ^12 (3.29) = 71(2,0,0) - t a. qo The remaining state probabilities are given by Equations 3.21.

-62The quantity 7r(2,0,0) is obtained from Equations 3.23, 3.25 and the fact that U (1,1) = 1/2 (because each customer corresponds 2 to two departures). Letting e = XE[Tk] = XATk we have (l-q )(l-p -p -e -e )+q t12(l-Pp -p (3 30) 7r(2 0 s.2 1 2 2.1 0q 1 2 (3.30) T(2,0,0) ( o 2 (1-q )t 21 +qt21t 12 from which we see that the condition for nonsaturation is q t12 -1 (3.31) + p + (0 e )0+ j < I. 1 2 12 21 - C We notice that (e + e )[l +q t12/1 - q ]- represents the portion of 12 21 0o0 0o the total utilization of the system corresponding to the switching times. The quantity [1 + qoto2/1 - qo]-1 is the "share" of each customer in that portion. Using Equations 3.22, 3.23 and 3.25 we get (3.32) a u(x,y)2 - 1 (2,OQ) _ F0 [11l1 (3.33) = +U-(U'= -e + 1) + L 7T (2,0,o ) ay 2 X2 2-q 1y= 1 (3.34) a U(Xy) = [1 + (] U' 33 Y X) = 2 X r1 6 - qO" " x=1 and

-63p (3.35) U (x,y) A1 + Y= [(1- p )A" + X2E[S2]A'] where A' = -e +[2+ 1t (0 - p ) 1T(2,0,0) 2 21 0 2- 1 21 2 t 2 0 0 J +e + p + (p-e) j e1 u 112 2 2 211- qo J At' X2E[T2 ] + 22E[2 - 2E[(T + T )2] (2,0,0) 2 21 21 21 12 + X2E[(21+ T t+ S )2] - [22E[T2 ] 2 12 2 21 1 2 X2E[(T + tS )~ - X2E[S] 2 21 2 1 - q 2 i and -U(1 = u (oi) 20,0) 1 c (2,oo) a rB"C'rd'C" B'1'1 dy 1 2C. C) J with B' = [- p - p + (i - qt P- 1 2 0 0

-641 - q + B" = + 1 (2t2 + 0 ) + - 2 21 1- p 0 21 (1 -p ff02p + X2 E[S2] + _ 2E[T2 ] e-P )2 21 - 2Et(T + S )2] 21 2 P + 1 2 21 12 -P 2 1 1. [ - (1 -o)p2 [ 0 X2E[S2] _{ - oo (1 p2J + q t (T + S ))2 ] 21 2 1- q ~(p + e ) 00- P 2 21 12 )2 - (1 - q)E[(T + T +e 1L - p 2 21 12 I The expected values of the number of customers at departure epochs are easily found by using Equations 3.32 through 3.35. The waiting times W and W are as in Section 5 of Chapter II, 1 2 2 2 where U (x,y), k = 1,2, is given by Equations 3.22 and 3.23. ThUatnk i e s WadWaeasi eto o hpe I

-65The busy period of the first stage, B, starts at the completion of the switching time T, when the state of the system is (2,i,j), with 21 i > 1 and j > 0, or i = j 0. The probability of the set formed'by all of these states is (3.36) P = U (1,1) - U (0,1) + 7T(2,0,0) 0 2 2 1i - P - - 8 - q(i q ) (t12)2 i+ 1 ~........2 21,0 0 2 (1 - qo)t21 + 1t12 00 00 0 During the switching time T new customers may arrive, say k customers. 21 The server will then be busy in the first stage for a time T plus 12 a busy period initiated by i + k customers, Bi+k where i is the number of l-customers present at the beginning of T. By definition T is 21 12 part of B We have (3.37) B (t) = [ 2i)tk Bi*T(t) i= j=o k=o 00 + E Tr(2,0,o)tlBk *T (t) + 7r(2,0,0)t1B *T (t) LK K12 0 1 12 k= 1 where P is given above. The Laplace-Stieltjes transform of B (t) 0 is

-66T (s) (3.38) BI(s) _= - ~ R [B(s)] U [B(s),l]- U (0,1) ~ ~1.2 P L21 2 2 + 7(2,0,0) [R[B(s)] - tl + B(s)] and the expected value is (3.39) B: = P6 + x U(x,y) + T(2,0,0) (l-p )P 2 21 2 J 1 o Y= 1 1- t2 ~r-T i -tO 1+.......... +12 0 where 9/Dx U (x,y)l _, w(2,0,0) and P are given by Equations 3.32, 2 x=l 0 3.30 and 3.36, respectively. The distribution of the busy period of the second stage' (which includes T ), BI(t), is 21 00 (3.40) BII(t) = ( 1- t2) 7T(1,O,j)T *S (t) 0 21 2 3=1 oo J-1 + t12 Yr(1,0 o)(l qo)q s*k*T (t) J=2 k=1 + Y t12 7(,10, )q J-1S*J*T (t) 0 =21 J=1

-67where the first term of the right-hand side corresponds to the case when new customers arrive during the switching time T, that is, 12 B = S + T (T is considered part of the busy period of the second 2 21 21 stage); the second term corresponds to the cases when the server succeeds I (1)+ + S(k) in completing service of k 2-customers, that is, B S +... +S 2 2 + T where (n) (n =,...,k) have distribution S (t); the third term 21 2 2 corresponds to the cases when all of the present 2-customers are serviced. The Laplace-Stieltjes transform of B (t) is t12 (3.41) B (s) = (1 tl2)T (s)S (t) + 0 0 21 2 1 - qoS (s) 02 U [O,q S (s)] 1 O2 J and the expected value is (3.42) B (s ) = (1 - t )(T2 + S() + ( 2- qO B0 21 20 1 B 12 0 where C' and B' are given following EcUation 3.30*

CHAPTER IV. RELUCTANT SWITCHING 1. Introduction In the two previous chapters we studied three simple policies which are quite likely to be considered for the control of our queueing system. In general we have to balance the behavior of the system, at least qualitatively, in terms of switching costs, waiting costs and service costs. We mentioned that the SSP-policy is good when the waiting cost in the second stage is high, and the FSP-policy if preferable when the opposite occurs; the LNB-policy is better when the switching cost is the critical factor. It is desirable to have some intermediate alternatives, for example, how to avoid high queues in the second stage without incurring high switching costs. To this end we shall now consider more general control rules which can still be qualified as?simple" in the epnse of feasibility of implementation. Under these policies we shall see that the server is comparatively reluctant to switching. We will examine three policies, namely: SSS(Q = N). The server continues available in the first stage until 2 the number of 2-customers reaches the value N. When this happens the server goes to the second stage and serves all the present 2-customers before switching back to the first stage. The label of this policy intends the rule "Switch to the Second Stage when Q = N." Notice that the SSP 2 policy is the SSS (Q = ) policy.-68

-69SFS (Q > N). After finishing all of the 1-customers (end of the busy period of the first stage), the server goes to the second stage. He stays there until all of the present 2-customers are served, unless the number of 1-customers reaches the value N. In this case the server completes the service of the present 2-customer and then goes back to the first stage. The label of this policy intends to rule "Switch to the First Stage when Q > N." The FSP policy is the SFS (Q > 1) policy. WNFS. After finishing all present 2-customers the server switches immediately to the first stage only if the number of I-customers is equal to or greater than N, otherwise he is removed from the system (not available in either stage) and comes back to the first stage only when the number of 1-customers reaches the value N. The server stays in the first stage until all of the 1-customers complete service (end of the busy period of the first stage), then goes to the second stage. The LNB policy is the W FS policy except for the fact that the server is never removed under the LNB policy. (It would be better to define W FS o as the LNB policy.) We shall discuss the effect of these policies on the queue sizes, waiting times and busy periods as we did in Chapters II and III, but only the case of instantaneous switching will be considered. 2. The SSS (Q = N) Policy The stationary conditions are i+i (2.1) (a) (,i,l) = t(2,a,0)pia + 7r(2,O,O)pi (i > 0) ~ I~-(Eq.a+1 2 c a 1 (Eq. 2.1 cent.)

-70i+l (b) Tr(,i,) = 7T(la, - )P0 1) a=! (i >, 2 < j N) (c) TT(l,i,j) = 0 (i > 0, > N + 1) i (d) 7Tr(2,i,j) = 7T(2,a,J + 1)qia (i > 0, 0 < < N- 2) a=o i (e) 7T(2,i,N - 1) = (1,a,N) (i > 0) a=o (f) r(2,i,j) = 0 (i > 0, j > N) 00 When G(x) = E x r(l,a,N) is defined, we obtain the following a=o generating functions: (2.2) U (x,0) - U (0o,) - y GCx) + y rl,0,No - r(2,0,0) + x[U (0,y) + 7T(2,0,0) yN7(1,0,N)] U (x,y) = yP(x) 1 x - yP(x) and yNG(x) - U (x,0) (2.3) U (x,y) = 2 Q(x) 2 y - Q(x)

-71In order to completely characterize the state probabilities 7T(k,i,j) we now need to determine Tr(2,0,0), U (O,y), U (x,O) and 1 2 G(x): Since IU (O,y) < 1 for ly < 1, in particular when y qo, Equation 2.3 yields (2.4) 7(2,0,0) = N 7(1,0,N) = q G(O) and then, by taking the derivatives of U (O,y) at y = 0, we get 2 (2.5) rT(2,0,j) = i 7(2,0,0) q 0 From Equations 2.2 and 2.3, using the arguments preceding Equation 3.2 of Chapter II we get U (6,0)- yG(6) + ) - (1 -6)72,0 0 (0,y) 2 Nq(1 -6)7r'2,0,0) (2.6) U (O,y) U (6,0) -yNG() N _. 2..'l ) M 2 0 -2 16Lx)N+ - 1r(2,0,O) and (2.7) U (x,O) = [Q(x)] G(x) 2 where 6 = 6(y) is, as before, the inverse function of y = x/P(x). At this point it only remains to obtain G(x), since the quantity 7r(2,0,0) is, from Equation 2.4, equal to q G(0). 2 0~~~~~~~~

-72We have 12 8 (2.8) G(x) = U (x,y) 2Y y=o where, from Equation 2.2, we can write N k N k N-k (2.9) N U1(x,y) = P(x) (N) A(x,y) N- B(x,y) (.)ay^ ko k y ay y k=o with A(x,y) = y[U (x,O) - (1 - x)7T(2,0,0)] 2 + [(1 - x)7(1,O,N) - G(x)]yN+l - y(1 - x)U (O,y) ^ A(x,y) U (x,0) + (1 - x)[G(0) - qo - G(x) y=o - ( - x)U (O,y) 1 N N = -{1 - [Q(x)] } G(x) + (1 - x)[G(O) - q] - (1 - x)U (O,y) Ak (x,y) -( - x) U ( ) -(1 - x)kU(k) 1 1 ay y= o dy 1 y=o (2 < k < N) and B(xY) = x - yP(x)

-73-B( )(N k! [P(x)].. ( < k < N),y yNy=o N-k+ 1 Hence (2.10) G(x) (1 - x)[P(x)N qNG(0) + j' u(k) L. k=1i J [P(x)Q(x)N) ] 1x [j The quantities U(k) = (dk/dYk)U (O,y)l are obtained from Equations 1 1 YO 2.6 and 2.7 in terms of G(k) (d/dx)G(x)_, 0 < k < N - 1. Then, by (k) taking the derivatives G) in Equation 2.10, we will have a system of N linear equations and N unknowns, namely G (), G (,...,G(N1) We have (2.11) U(k) = (1 < k < - ) 1- ~ ~fy=o - — <k<Nl dy k The formula for differentiation of a function of a function is (2.12) d g(g) = f(m)(g) (k;a, a,...,a) dx 1 2m= m=o [g ]a 1 (2) a2 [g(k) k.[g()] [g I summed over a + 2a +.. + ka = k and a +a +... + = m. 2 1 2 f() and g(k) denote the derivatives (dm/dgm)f and (d /dx )g, respectively, and

-74(k;a,a,. k! l 2 a!(l:)a la! (2)2 ak! (k'ak 1 2 The coefficients a,a,...,ak and (k;a,a,...,ak)', for each term of 1 2!1 2 the inner sum of Equation 2.2, are given by Table 24.2 or reference 1I for 1 < k < 10. With the above result we rewrite Equation 2,11 as k (2.13) U() = Zy zk G(6) (1 k < N 1) Zo dy yo where k-d1 < k < N - 1 (2.14) ZkR oy NZ P. ay k-Z Yy=o 0 < k <_N- 1 and (2.15)dy G < N (2.1 G(6) = ^ ^ (0 I R I N- 1) with,-^ ~ ^1)^l 2 a)2 a2 ) az (2.16) r = Z (Q;a a...a ) [()] [6() 2 [()] (0 < Q,m < N - 1) summed over a + 2a +...+ Qa = Q and a + a +... a =, 1 1 I 1 2 j and where T, 6(y) dy y=o

-75Hence k (2.17) U(k) = Z k G ( 1 < k < N -l) Q=o m=o (2.18) a (c) (1 - x)[P(x) ac a dxa [P(x)Q(x) N N dx [P(x)Q(x)] - x xo and (2.19) dck ) ck k!'... P-(xi dx x=o Then, using Equation 2.10, we obtain the system of N linear equations with unknowns G(),G(),...,G(N c N-1 k Q (2.20) G() = E ac m a= 1 k= 1 =o0 m=o N (o) + qN( (1 < c < N - 1) oco 0 This is an indeterminate linear system. One additional equation is obtained by using the fact that G(1) = 1/2N (which can be seen from Equations 2.2 and 2.3 and the relatiionship U (1,1) + U (1,1) = 1). 1 2 Equation 2.10 and L'Hopital's rule give

-76N-1 (2.21) qNG( Tr(2,0) - (U P P )I U(k)k = 2 I2 1I k= N-1 k - (1 - r G(m) 2 1 2 L L k'k k=l Z=o m=o 2.1 Calculation of r m Zk%, ck and ac. Our first step is to find the derivatives 6() = (d /dyr )6(y)o We have 6 = yP(6) which y-=o gives (2.22) 6 = - (-6) dy y=o where the derivative of P(s ) are found by using Equation 2.12. For example, using Table 24.2 of Reference 1, and denoting (da/dx )P(x) =o p(k) = k!p we get (1) = p(o) 3) = 6(2)p(1) + [6(1)]2 P() i ( 4) = 6(3)p(1) 36(1) 6(2)p(2) + 6(1) 3 pC3) ~ 4 = 6 +36 6 p [ 6 = 6 P + {3[6( 2]2 + 46(1) S(3)}P 2)+ 6[6(1)]2 P() ([1) ]4 (4). etc.

-77Thus it is possible to determine 6 recursively. We can now calculate rm by Equation 2.16. The derivative of the expression for ZkZ (Equation 2.14) is obtained as follows: (2.23) k [Q(6)] ak ib y=o i where k-i k-i k d N k d (2.24) aki =() k-i [ (6)] (i k-i N dyb y=o dy y=o k-i 1 %E QQN E (k-i,a,a,...,a 1 2 m-o a a [61)] 1[6(2)] 2 [(k-i)]ak-i with QN = m q N, where {q N} is the Nth convolution of {qn} with itself, and (2.25) bi d 1 (;aa,,a ay 1i 2 y=o m=o l [6(1)]al.r[<(i)]ai r[6(i)] i Hence k-Q (2.26) Zk = ) ak i i=o

-78The quantity ick is 0, if c < k (2.27)ck d ck = t ~c^ h[l/P(x)], if c > k dx x=o where c-k ^c-k, k - dc-ck P(x) k (c ( c-k;a,a,...,a ^c-^ Jdx; Zrip~m) Z 12 c-k m=o k a a a.[P1 ] [P 2'' Pc c-k with P ( = m!p, where {p } is the k-fold convolution of {p I with itself. The quantity a is ac (2.28) a = (c) - 2. [(x) - [x/P(x)] c) d a-11 [Q(x) - [x/P(x)]N where

-79da 1 (2.29) N N dxa [Q(x)]N- [x/P(x)Nx=o a m = Z I (a;a,a....,a ) [ N] N t 1 23 a 1 1N a mN a aa [s*Nl l Nla2... [] NJ a 1 2 a ~~~~IsN~we, first get9 G(1 2 since 03 0 because a < N. a aN 2.2 Expected Number of Customers and Waiting Times. Using Equations 2.2, 2.6, 2.7 and the relationship U (1,1) +U (l1,1) i2 1 2 Then, applying L'Hopital's rule in order to evaluate the partial derivatioes of U (x,O) Np G( y 1, w o (l) bt kx 2 2 22 J()= I and d ~ U ^^) = (1- P -P )+ TT(1,O,N) - 7(2,0,0) dy' 21 2 Then, applying L'Hopital's rule in order to evaluate the partial derivatives of Uk(x,y) at x =y = 1, we obtain

1-p - p p (2.30) Q = (p + Q) -+ 2 [1/2(N 1)p2 + 2NG'(1)'] 1 1 1-p 1 - p 2 1 1 (2.31) Q = + 21 2 (2.32) Q (N + 1)p + 2G'(1) 12 2 2 (2.33) - 2 2 2 where 2E[(S + S )2], 1 2 = 2(1- p -P ) 1 2 The expected values Qk Qk and Q can be found easily from the above results. The waiting times, W and W, are given as in Section 5 of 1 2 Chapter II. 2.3 The SSS (Q = 2) Policy The long differentiation procedure used in the determination of G(x), for an arbitrary N, is very simple for N = 2. In this subsection we shall study this case. Equation 2.10 reduces to (2.3l) ) ( = (1 - x)[P(x)]2 [q2G(O) + x/P(x) U ] LP(x)Q(x) ]2 _ 2 o 1

-81where the quantity U(1) = d/dy U (0,y)J is obtained from Equation 2.6 1 y=O in terms of G() = G(0) and G = G'(0). We have (2.35) _U) 6=(1) dU (x,0) + U (1,0) 1 dx 2 x=o 2 which, combined with Equation 2.7, yields (2.36) U1 = 2poqq G() + G 1 001 The quantity G( is calculated from Equation 2.38. We get (2.37) G( ) + 2 ) + ( 1) q po q2 1 O O which, combined with Equations 2.36 and 2.21, determines the quantities G(~) and U() of Equation 2.34. We get!1~~1 (2.38) G(x) = -(1 - - P 2 2 1 2 Q(x) - [P(x) q + P (q + 2q) p) qo + P (q + 2q ) and the probability of an empty system,

-82(2.39) Tr(2,0,0) = (1 -p - p) P 2 2 qO + p (q + 2q) Notice that the nonsaturation condition is still 1 -p - p > 0. 1 2 The expected number of customers given by Equations 2.30 through 2.33 are -.p P P (2.40) Q ='1 (p[ + 2G(1) 11 lp 1 O P (2.41) Q 21 2 (2.42) 1 P + 2G'(1) 12 2 2 (2,43) = 22 2 where, from Equation 2.38, + 2q )(1 - p ) (2.44) G'(l) -= + (3 P P- l Q 2[q0 + p(qo + 2q ) 2 2.4 Busy Periods. The busy period BI during which the server is continuously working in the second stage has distribution (2.45) BII(t) = S (t) 2

-83The busy period B is defined as the time necessary to accumulate N customers in the second stage. During this time the server may be inactive in the first stage. This happens when the first stage becomes empty and the number of customers in the second stage is less than N. We see that if B starts with i 1-customers, its duration has the distribution of the time until the Nth departure from an M/G/l queue having service time distribution S (t), given that the system starts with i customers. Let 0aN be the number of times the first stage becomes empty until just after the N - 1 first departures. Given cN = k, we see that BI has distribution S * A (t), where A(t) = 1 - e is the interarrival distribution and S (t) is the service time distribution of the first i stage. If Q is the number of customers in the first stage at the time 12 the server arrives from the second stage, we have N-i (2.46) B (t) U ((2,i, 0 2 k=o i=o P [ kjQ = i]SN * A*k(t) r N 12 1 In Takacs ([21], page 98), we find (2.47) P [ > Q = i] = P [n < NQ = i +k] r 12 r 12 where r is the number of customers served in a busy period. Thus we have

-84N-1 N-i (2.48) B (t) = U (T) (2,i,0) 2 i=o k=o.[{P[n < NQ = i + k - 1] - P[n < N = + k]] 00 ~S A (t) + (1,0) 7rr(2,i,0) SN (t) 2 i=N where N-1 j]tf 7, = * (( )n-j -XJ, *n P[n< NiQ -j = 2.(... as e(0) (N > ) jo (n- J):! 1 n =o = 0. (N < J) Simplification of the right-hand side of the above equation is not apparent. The busy period of the server, BS, is defined as the time elapsed since the server starts the service of a 1-customer that terminates an empty period of the system, until the system becomes empty again for the first time. This busy period may contain, as for the busy period B, intervals corresponding to situations when the first stage becomes empty and the number of customers in the second stage is less than N. We have not succeeded in finding the distribution B (t), nor its Laplace-Stieltj es transform. 3. The WNFS Policy Under this policy the server switches from the first to the second stage when the first stage is empty and returns to the first stage

-85when all of the second stage is empty and if at least N I-customers are present. Otherwise the server removes himself from the system, and returns to the first stage when N 1-customers are present. As indicated in Section 1, the WNFS policy is a generalization of the LNB policy discussed in Chapter II. For this reason we expect to have a solution procedure similar to the iterative scheme presented in Section 3 of Chapter II. Some difficulties will arise with this type of solution, but as in Chapter II, we are able to find the state probabilities by a direct approach. The stationary conditions are (3.1) (a) Tr(l,i,l) = 0 (i < N - 1) i+1 N-1 (b) 7(1,il) = t(2,a,0)pia+ PiN+ (2,a,) a=N a=o i+1 (i > N- 1) (c) (T li,J3) = 7r(l,a,j - l)pia (i Oj 2) a=1 i (d) 7r(2,i,j) = wr(1,0,j + 1)qi + Tr(2,a,j + 1)qi-a a=o (i > 0,j > 0) The generating functions of {(t(l,i,J)} and (x(2,i,j)} are U (x,O) - U (O,y) + xNH(1) - H(x) (3.2) U (x,y) =;yP(x) 2 1 1 x - yP(x) and

-86Q(x)[U (O,y) - U (x,O)] (3.3) U (x,y) = 2 2 y - Q(x) N-1 where H(x) = Z Tr(2,a,0)x. a=o Using the arguments preceding Equation 3.2 of Chapter II, we obtain (3.4) U (0,y) = U (6,0) + 5NH(1) - H(6) 1 2 and (3.5) U (x,0) = U (,Q), 2 1 where, once again 6 = 6(y) is the inverse function of y = x/P(x), and Q = Q(x). Let x = x and y = y with xj < 1 and Jy < 1. Define x. and Yi, i > 0, by (3.6) xi = 6(i) and (3.7) y (xi Yi+l = Q(xi )x Suibstituting Equations 3.6 and 3.7 into Equations 3.4 and 3.5 we get (3.8) U (O,yi) = U (x ) + X + H(1) - H(x+ ) 1an 2 d+1 l +1 and

-87(3.9) U (xi,0) = U (0'i+ 2 I 1 1+1 Adding Equations 3.8 for i = 0,2,...,2N-2, to Equations 3.9 for i = 1,3,...,2N-1, we obtain N-1 (3.10) U (0,y) = U (,yN )+ Y [xN H(1) - H(x2 )] 1 1 2N2n~ n=o Similarly, let i = 1,3,...,2N-1 in Equation 3.8 and i = 0,2,...,2N-2 in Equation 3.9. Summing these equations we get N (3.11) (xO) = U (N 0) + [xnH(l) - H(x2) 2 2 2N' X2n n=i We proved in Section 3 of Chapter II that the sequences {x2N and {Y 2N converge to unity. The sums in Equations 3.10 and 3.11 are N convergent, since IH(xi)I < 1 for Jxil < 1 and the sums E (x -1) N-1 n=1 and E (x2n+l- 1) are convergent (see Chapter II). n=o Thus we may write (3.12) U (0,y) = U (0,1) - A (y) and (3.13) U (x,0) = U (1,0) - A (x) 2 2 2 where 00 (3.14) A (y) = E [H(x2l) H(N 1 2n+n= n=o

and 00 (3.15) A (x) = [H(x2n) - H(l)] 2 n- X2nH(1) n= 1 Notice that when N = 1 we have H(x) = 7r(2,0,0), consequently Equations 3.12 and 3.13 reduce to Equations 3.11 and 3.12 of Chapter III, respectively. We now discuss the difficulties of determining H(x). First we notice that (3.16) H( (0) H() = = (x,o3 dx x=o dxk xo = U(k)(o,o) (O < k < - l) 2 One method to be attempted is to use Equations 3.5, 3.4 and 3.16 in (k) order to relate the quantities H(k) (0). We have (3.17) U'(x,O) = Q'(x)U'[,Q(x)] 2 1 and (3.18) u'[o,Q(x)] = 6'[Q(x)] U'[6[(x)x)],0] + N[6[Q(x)]]N1 2 - H'([(Q(x)]] Unfortunately Q(0) = qo; this means that, in general, H(k)() will appear as functions of unknown quantities, H (q ).

-89Fortunately, however, the state probabilities t(k,i,j) can be determined by the direct approach of Section 7 of Chapter II, which is based on the properties of the busy period of an M/G/1 system. Let bm(i), ai(n) and ck(n) be as defined in Section 7 of Chapter II. We have 00 (3.19) c (n) = E bN(i)ai(n) i=N N-i1 oo ck(n) = [ Ck (m)] bN(i)ai(n) m=J i=N 00 00 + ck (m)b (i)ai(n) (k > 1), k-1i m m=N i=m where bm(i) and ai(n) are given by Equations 7.2 and 7.3 of Chapter II, respectively. The state probabilities Tr(2,n,0) can be written as 00 (3.20) r(2,n,O) = x(2,0,O) ck(n) (n > 0), k=l where t(2,0,0) is determined by the relationship N-1 N-1 (3.21) NH(1) - H'(1) = N (2,n,O) - nt(2,n,0) n=o n=1 1 = (1- - P ) 2 1 P1 2 which is derived from Equations 3.3 through 3.5 combined with the fact that U (1,1) = 1/2. The remaining state probabilities are found by 2 Equations 5.1.

-.903.1 Expected Number of Customers and Waiting Times. Using Equations 3.4, 3.5 3.21 and the fact that 6'(1) (1 -p )-, we 1 find that U'(0,1) = 1/2 and U'(1,0) =1/2 p.* Next, knowing that 1 2 2 6"(1) (1-p )-2 [2p + 2E[S2](1 - p )'], we obtain 1 1 1 1 Ulf(ol) = 1+ (p + Q)+ 1 11 (-p1 p )2 -p2 1 2 [N(N - l)H(l) - H"(1)] and U"(lO) - I2 2E[S2] + p2U"(O,l) "(o2 2 2 21 where X2E[(S + S)2] Q = 0 2(1 -p -p ) 1 2 These derivatives are then used to obtain the expected values Qk~ from Equations 3.2 and 3.3. It results that formulas 4.1 through 4.10 of Chapter II are also valid for this case if for Qo we substitute Q + ( - p - P2)1 [N(N - l)H(l) - H"()]. The probability distributions and expected values of the waiting times W and W are given as in Section 5 of Chapter II. The values of 1 2 Uk(x,y) are given by Equations 3.2 and 3.3; the quantities Q and Q k 11.2 are obtained as indicated above. -,UTl(0,). U (x,y) and U'(1,0) = U (xy) xo1 2 =OX y=i y=o

-913.2 Busy Periods. For this WNFS policy the busy period of the S server, B, is the time elapsed from the moment the server returns to the system (N I-customers and no 2-customers are present) until the departure of a 2-customer who leaves behind him less than N l-customers and no 2-customers. In order to find the distribution of BS we notice that, if the same realizations of arrivals and services are simulated in an M/G/1 system, with service time equal to the sum of the service times in both stages of our sequential system, and if at the termination of B the sequential system has i customers (1-customers), then the M/G/1 system will also have i customers (assuming N customers were present at the beginning of the simulation), 0 < i < N. This occurs *(N-i) with probability t(2,i,0) (unconditionally) and distribution B (N (t), 0 where B (t) is the distribution of the busy period of an M/G/1 system with service time distribution S * S (t). Hence, conditional to the i 2 set of all possible ways of starting the busy period BS, which has N-1 probability H(1) = Z i(2,i,0), we have i=o N-1 (3.22) B t) = A (2,1,0) B(i) (t) i=o The Laplace-Stieltjes transform is (3.23) ( (s) = 1 [B(s) N H [ ( BL B(s) (3.24) = WL[NH(1) - H'(l)] S +S 1 2 - 2H(1)'

-92because of Equation 5.21 and the fact that B= (S + S )/( - p - p ) 0 1 2 1 2 A similar situation occurs with the distribution of the time during which the server is removed, I(t). We have N-1 (3.25) I(t) = () (2,i,0) A(N)(t) i=o where A(t) 1 - e is the distribution of the interarrival times. We get (3.26) i(s) = \ H [ + s ] and (3.27) I - H(-1 (I - P 2 The busy periods of the first and second stages, B and B, are defined as before. For the first stage we have 00 (5.28) B (t) U- (1,) LH(1)BN(t) + T(2,i,0)B (t) 2 i=N where, as in Equation 6.1 of Chapter II, Bi(t) is the distribution of the busy period initiated by i customers in an M/G/1 system with service time distribution S (t). We get 1

-93(3.29) B (s) U ( ) H(l)[B(s + U s) ] + U [(s),0] where U (x,0) is given by Equation 3.13. Equations 3.2 and 3.21 and the fact that U'(1,0) = 1/2 p, yield 2 2 S S (3.30) B _ (,o) _-' 2 1 where A (0) is given by Equation 3.14. 1 For the second stage we have 00 1 (3.31) B (t) U (O 1)- (l,O,j)S (t). 1 2 1j= (3.32 B,) =U [OS u (s) i and S S S — I I 2 2 2 (3.33) = 2U (0,) 2U (1,0) 2A (0) 1 2 1 The average number of cycles in the busy period of the server is (B A (0) = H(x( 2) o I (35.34() c = - - xnIl H() n B +B H(l) Hl J n=o 00 - kck (0) k=1

-944. The SFS (Q > N) Policy Under this policy the server switches to the other state leaving no backlog in the present state, except when, at departure of a 2-customer, at least N 1-customers are present in which case the server switches to the first stage. The analysis of this policy is similar to the analysis of the WNFS policy. In this case the function H is two-dimensional. The steady-state probabilities are related by i+1 (4.1) (a) (li,l) = r(20,0)pi + r(2a0)Pi.a+ (i > ) a=i i +1 (b) (lij) =- (l,a,j - 1)Pi._+ (O < i < N - 2 a=l j > 2) i + i + (c) r(li, ) = Y (la, - l)P-a+i + r(,a, - 1) a=l a=N (i > N - 1 i j >2) (d) qr(2,i,j) = q.i(l,,j + 1) +Y q. i (2,a,j + 1) a=o (9 < i < - 2 j > o) N-1 (e).rT(2,i,j) = q.Tr(l,0,+j + 1) + q. J,(2,a,j + 1) a=o (i > N- 1 j >).

-95Letting H(xy) = Z E x y t(2,N + a, j) j=1 a=o we get (4.2) U (Xy) (x - 1)t(2,0,0) + U (x,0) - U(O,y) + H(x,y) yP(x) (4.2) u (x,y) = ^1x - yP(x) and U (O,y) - U(x,O) - H(x,y) (4.3) U (xy) =. Q(x) y - Q(x) Notice that the two last equations have the same structure as Equations 2.5 and 2.6 of Chapter II. This is expected since the present policy, for N - o, is the policy studied in Chapter II. Applying once more the arguments of Chapter II we get (4.4) U (O,y) = U (s,0) + (6 - 1)(2,0,0) + H(6,y) and (4.5) U (x,O) = (0,Q) -H(x,Q), 2 1 where Q = Q(x) and 6 = 6(y) is the inverse function of y = x/P(x). Using the same iteration scheme of Chapter II, we find (4.6) U (0,y) = U (0,1) - i(2,0,0)A (y) +B (x,y) 1 1 1 1

-96and (4.7) U (x,O) U(1,o) - i(2,O0,)A (x) + B(x,y) where 00 (4.8) A (y) = ( X2n+l) n=o 00 (4.9) A (x) = E (l - ) n=L 00 (4.10) B (x,y) [FH(x2n+ 2n)- H(x2nl1y2n2)J n=o and 00 (4.11) B (x,y) = j FH(x2,y2nl) - H(xny2n-y )J n=l The value of r(2,,00) can be determined analytically from the equations above and the fact that Uk(l,l) = 1/2. However we can see that its value is 1/2(1 - p - p ) since, under this policy, the server 1 2 is active whenever customers are present in the system (see comments following Equation 3.5 of Chapter III). If we let x = y = 0 in Equations 4.6 through 4.11, we get A (0) = 1 + A (0) and B (0,0) B (0,0) - H(1,1). Thus 1 and 2 1 2 1) (,y) 2 (1 -p-p)A(0) - B (0,0) and

-97(4.13) U (1,0) 2 (1 P -p )A (O) - B (0,0) - H(1,1) 2 1 2 1 1 We shall now obtain the function H(x,y), by finding the state probabilities c(2,i,j), using an approach similar to the determination of the function H(x) of the previous section. Let b (i) and a (n) be as defined in Section 7 of Chapter II, and define ck(m,n) = probability that, starting with an empty system, the termination of the kth cycle occurs when there are m 1-customers and n 2-customers in the system. We have N-1 X (4.14) (a) c (m,n) = I b (i)ai (r)a (m r) r=o i=m+l oo oo N-1 (b) c(m,n) = Z k(u~)bu(i)ain(r)a (m - r) kk_1 ki-n-1 1 u=1 i=I r=o o 00 00 00 N-1 +L L L X -i(uV)bU (i)a i+v-n-1 n=N v=1 i=I r=o v a (m- r) (k > 1) where I = maxu, n -v 1 From this we get where I maxfu + 1, n - v + 1). From this we get v

-9800 (4.15) r(2,m,n) = 2 (1 - P ck(mn) 1 ).2 k-1 With this we can find H(x,y) from its definition. The remaining state probability, if needed, can be found from Equations 4.1. 4.1 Expected Number of Customers and Waiting Times. Let H = H(x,y) x T X ) X:=1 y-= and let H, H, H and H be similarly defined. y xx yy xy Using Equations 4.4 and 4.5 and the fact that'(1) = (1 - p )we find U'(O,1) =1/2 + H and U'(1,O) = 1/2 p - H. Next, knowing 1 Y 2 2 x that 6"(1) = (1 - p )2 [2p + 22E[S2](1 - p )-], we obtain 1 1 1 1 Ut(0,l) = ^~ ~~(p +Q) ++H 1 - p +p ( o 1 -p +p yy 1 2 1 2 and 2p 1 _ UT"(l,O) = - 2E[S23 + p2U,"(O,l) - 2 H - H 2 2 2 2 21 1 -p -p xy xx 1 2 These derivatives are then used to obtain the expected values QkQ from Equations 4.2 and 4.5. We get 1 - (4.16) Q& = (0 + Qo + ~2p xH ) )11 (+1 o 2 xy 1 p + p 1 2 (4.17) Q = ( +p +Qo +2H ) 21 2 o xy 1 -p +p' 1 2

-99p x 2 2 + P (4.~.18) q [l + p + H2 ]~1 2 and (4.19) = (p +Q 2H 22 1 0 xy 1 p + p i 2 The probability distributions and expected values of the waiting times W and W are as in Section 5 of Chapter II. 1 2 4.2 Busy Periods. By the arguments of Section 6 of Chapter II, S the busy period of the server, B, has the distribution of the busy period of an M/G/1 system with service time distribution S * S (t). 1 2 Consequently its expected value is = (S + )/( -p - p ). 1 2 1 2 The distribution of the time the server is continuously serving 1-customers is 00 00 (4.20) BH(t) = U (1,0) [ Z ( )(t) 2 i=N j=l 00 + NJE (2,i,0)Bi(t) + T(2,0,o)B (t) i=1 i=l where Bi(t), as in Section 6 of Chapter II, is the distribution of the busy period of the first stage initiated by i customers. Knowing that U (0,1) = U (1,0) + H(l,1) and B = B = S /(1 - p ) 1 2 1 1 we get

-1001 (4.21) B (s) = (0, 1)H[ (s),l] + U2[(s),0] + (1l- P - P)[(s) -1], which implies (4.22) 2U (0,1) S (- p -p )A () - B (0,) S 1 1 2 1 1 In order to derive the distribution of the busy period of the second station, we first get 00oo n-1 (4.23) A(n) = Z ai(i) = i - x (i) i=n i=o where (i) = n ti dS (t) 2 0 i. 2 Now, noticing that BI starts when the state of the system is (1,0,j) with conditional probability rT(l,0,j)/U (0,1), and that the server can complete service of k 2-customers (1 < k < j - 1) with probability N-1 (4.24) akj = ak_(r)A(N - r) r=o and of j 2-customers with probability N-1 (4.29) aj. = a l(r), r=o

-101we get * 00 j (4.26) B (t) = U (1 0,) ) akj S (t). 1 j=1l k=l Instead of obtaining B from the equation above we can use the relationship 00 (4.27) c = kck(0,0) -I B k=l where ck(0,O) is found by Equation 4.14. We get (4.28) iB -. S B_ i (1- - - p) 1 2

CHAPTER V DISCUSSION 1. Numerical Comparison of Policies In this section we compare the effect of policies LNB, SSP and FSP, for the case of exponential service times, on the average values of the waiting time in the first stage (W ), the waiting time in the.I second stage (W' = W - -S ), the busy period of the first stage (B ) 2 2 1 1 and the busy period of the second stage (BI). We consider three situations of total traffic intensity, p = p + p, representing heavy 1 2 traffic (p = 0.9), normal traffic (p = 0.5) and light traffic (p = 0.1). In each case we obtain curves of the pertinent average value as a function of the traffic intensity in the first stage (p ) which varies from zero to p (p varies from p to zero). 2 Assuming X = 1 and using the formulas of Chapters II and III (see Table I) we get Q = [p2_ p (p - )/(1 - p) 0 1 1 LNB-Policy = (p + Q )( - p )/(l - 2p + p) - p 1 1 0 1 1 1 W' s [p2 + (p - p )(l + p - p ) + ]/(1 - 2p + p ) 2 1 1 1 0 1 B = p /(1 - p)/A (0) 1 1 BI = p /(l- p)/A (0) 2 1 where A (0) is obtained as in the example of Section 8 of Chapter II. 1 -102

-103SSP-Policy W =Q 1 o W' = 0 2 -I B =p BII = p 2 FSP-Policy W1 = (p + Q)(- p)/(l - )- = p(p + Q)/(l - p ) 2 1 0 1 B = p /[2 - p - (1 + p -p )] 1 1 II = p /[2- p- (1 +p - )-] 2 1 The quantities above are plotted in Figures II through VII. From these figures we clearly notice that the effect of different policies on the average busy period is negligible for low values of p. For all policies, the average wait in the first stage is minimized near p = p/2 and in the case of policies LNB and FSP we see that the average wait in the second stage increases surprisingly fast as the traffic intensity in that stage decreases (p increases). 1

V) u In _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ U,in C1~~~~~~~~~~~~~~~~~~~~~~~V In 2 0 C)~ ~ ~ ~ ~ ~ ~ ~~~~~~~~C ~ru~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~tC cv t --. LiJ I^ *:~ I-. z a: LNB FSP FSP ~S - -^ LNB Cr,S'P m a a 5- ~ ~ ~ ( ~ 1 ~6 *. ~ -.80 SSP ^WFFIC~~~~~~~~~~~~~~~~~TWL INENSITY^O OFIFBS STAGEe -WO iWD-,~~* ^ (~. (a) (b) Figure II. Average Waiting Times in the Stages of the System, For Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Tntensity in the First Stage, p, for Constant Total Traffic Intensity (p = 0.1). (a) First Stage; (b) Second Stage. 1 cc cc cccCr~~~~~~~~~~~~~~~~~~C a:~~~~~~ IC INTENKIDSITY OF FIRST STTM -I~O (a) (b) Figure II. Average Waiting Times in the Stages of the System, For Policies LNIB,, SSP and FSP, i h Case of Exponential Services, Plotted as a Function of the Traffic Intensity in the is Stage, pi for Constant Total Traffic Intensity (p = 0.1). (a) First Stage; (b) Secn St age.

\^ SS 5 W - V)\ / ~ oX LLU a: 19~~~~~~~~~~~~~~~~~~~a cc LLJt U)~~~~~~~~~~~~~~~~~~L cr FSP ^ — \ ^^____^/ ^ ^ cc. LNB. (T) Ck~~~~~~~~~~~~~~~~~~~~~~~~~~~~, —. — ^^^ Q= FSPILNB ^o 5 Uj CC~~~~~~~~~~~~~LJ 0. ~ 4 ~ 1 ~ 1 ~ ( ~ +-0 QQ: a: ac ~.0. ~.2.10.9 0 -~TfFFIC INTEITY OF FIRST STAGE - tC1'*.O 9.3.IT.wP. * TWFIC INTENSITY OF FIRST ST C MftC (a) (b) Figure III. Average Waiting Times in the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services Plotted as a Function of the Traffic Intensity in the First Stage, p,for Constant Total Traffic Intensity (P = 0.5). (a) First Stage; (b) Second Stage.

~ 8 o o 8 FSP / 18 c: ^ Q 4 r U)I. 8 ^ / (a) (b ) Figure IV. Average Waiting Times in the Stages of the System, for Policies LNB, SSP and FSP, in the ccCase of Exponential Services, Plotted as a Function of the Traffic Intensity in the First Li c FSP.I.8 LN 8 rrio LNB.* aw FR M TmrIFIC'HTO4SITTOf FIRST ST o, - * TrIc urrOIisiTYr OIRST STXX -W0i (a) (b) Figure IV. Average Waiting Times in the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity in the First Stage, p, for Constant Total Traffic Intensity (p = 0.9). (a) First Stage;(b) Second Stage.

o o o o o tB / t tLNB LNB LLJ.. U.JQ p C. FSP 0 F Tf. z/. f- SSP. (, ( ~ ~~~~~I~~~~~~~~~~~~~~0cp Cf cc / S Uag L CE 1C ~~00.~.6.~O..OB 0 - CC -..00.02 0.06.06 ~ TfIC IMTEITT OF FIRST STAe -W T-qFFIC INTENSITY OF FIRST STGE- R-OM (a) Figure V. Aversage Busy Period of the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity to the First Stage, p, for Constant Total Traffic Intensity (p = 0.1). (a) First Stage; (b) Second Stage. 1

0 0 * ~/ ~9Y UJO 0 UJ — (DOD.. ~~~~. cc CC Ih~~- ~LNB Cl) (1) ZLNB c crc0 Oco LL.' f FSP *" ^ " FSP M^FSP C) ~ ~ ~ ~ ~ ~ ~ ~ ~ 0 ac. * SSP /c SSP 80. / /( 0 r3 V^y^(o f^^ \^ o cc a:~~~~ tLi bJ~~~~~~~~~~~~~ _____________ 0:^ I ~ ~ ~ ~ ~ ~ ~ ~ > I I 0c 0'^. ~ ~ ~ ~ ~ ( ~ ) ~ -0 O..O *10.20 -30 ~'0 ~M~.00.10.0.30.10 T0FFIC INTENSITY OF FIRST ST.iGS - W^ TWFFIC INTDNSIT CT FIRST STtGE - T TIS (a) (b) -Figure VI. Average Busy Period of the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity to the First Stage, p, for Constant Traffic Intensity Cp = 0.5). Ca) First Stage; (b) Second Stage.

o 8 a3 L0 o 0 U) -. c: I-'o / /.J LNB >- / /C FSP' F ~o tl/ a:, ~ o' CCO U H cr 8 ^^ ~.00.$e.9. 1..m.1O TIWFIC INTENSITY OF FIRtST STE -.21 89. 8g CC:'.W.18.i.~ ~ TRRFFIC INTENSITY OF FIRST STAFE - IVA (a) (b) figure VII. Average Busy Period of the Stages of the System, for Policies LNB, SSP and FSP, in the Case of Exponential Services, Plotted as a Function of the Traffic Intensity to the First Stage, p, for Constant Traffic Intensity (p = 0.9). (a) First Stage; (b) Second Stage.

-i102. Practical Implications of Availability of Numerical Results For practical employment and engineering consideration the first question that may be asked is: Are the average values numerically available? We shall now have a few remarks on this question and more general aspects. In the case of policies LNB, SSP and FSP, with instantaneous or with random duration of switching, the average values of all considered queueing properties can be easily calculated by the formulas of Chapters II and IUI,which do not require calculation of the state probabilities. The determination of the values of B and B, in the case of the LNB policy, takes a few more steps since they depend upon the quantity 00 A (0) = U (1,0)/(2,0,0) = 2 Z (2,i,0)/( - p - p ), but, as 1 2i=o 1 2 illustrated in Section 7 of Chapter II, the iterative scheme developed in Section 3 of that chapter is very efficient for finding A (0) without explicit calculation of 7(2,i,0). For policies WNFS and SFS (Q > N) we need first to calculate some of the state probabilities, T(2,1,0), for which we provided methods of solution. These methods depend upon the values of the probabilities b (i) of having i departures from the first stage during the busy m period of that stage started by m customers. These values, in the case of high utilization of the first stage, may be not negligible for large i, therefore the nested summations involved must have large upper limits, which implies a great amount of calculation, as, for example, in the case of Equations 4.14 and 4.15 of Chapter IV, where we have five nested summations. Although a straightforward computer program can be written for these policies, we have not made anyr actual calculations.

-lllFor the SSS (Q = N) policy, even the calculations of average 2 values, for which we provided solutions depending on the function G(.), may be expected to encounter numerical difficulties. In this case the use of special computer languages with capabilities of symbolic differentiation might be helpful. Next we shall comment on the feasibility of the calculation of the distribution of the pertinent random variables: for the state probabilities, except in the case of policy SSS (Q2 = N), we would first find r(2,iO) (0 < i < iT, where iT is some truncating value which depends on desired accuracy) for which we provided recursive schemes of solution, then we use the corresponding stationary conditions for calculating the remaining state probabilities. The distributions, of the waiting times, W (t) and W (t), can be found by numerical inversion I 2 of their Laplace transforms (an efficient algorithm is given by Stehfest [18]) which are given in terms of the functions Uk(xy). The distributions B (t) and BII(t) can also be found by the same approach, although explicit expressions for these distributions are given in terms of the distribution of the busy period of the /G/1 system started by i customers, which may take great amounts of calculation in the case of high utilizations. Evidently, in the case where BI(t) and B (t) are given by simple TI BI expressions like, for example, B (t) = S (t) or B (t)= S (t), we would 2 1 not use this approach. As shown in Table I, we were not able to obtain the distribution of the busy period of the server for the LNB and FSP policies for the case of random duration of switching, and for the SSS (Q = N) policy.

-112The difficulties in these cases are due to the fact that during these busy periods the cycles are not homogeneous in the sense that they are formed, possibly, by the sum of distinct random variables. For example, for the LNB policy with random duration of switching, the switching intervals T are combined with the intervals during which the server 12 is working in each stage. We can say that each customer served during B has his average service time increased to S + S + S where S 1 2 0 0 represents the average "share" of each customer in the total duration of switching. It is not clear how S can be obtained. In the case of the SSP policy, since the server follows the customer through the system, this "share" is simply T + T and, therefore, we can consider 12 21 that the service time distributions in the first and second stages are S * T (t) and S * T (t), respectively. Thus, the busy period BS has 1 12 2 21 distribution equal to the distribution of the busy period of an M/G/1 queueing system whose service time distribution is the convolution S * S T *T (t). 1 2 12 21 3. History of the Work At the beginning of this research we were concerned with two sequential queues with exponential services and interarrival times, where the service rates in each service facility could be controlled, at any time, depending upon the number of customers in each stage of the system. We assumed at most two alternatives for the service rate of each facility (which were allowed to operate simultaneously), each alternative having a corresponding cost rate. Given linear waiting costs and no setup costs, we intended to characterize the optimal

-113policy of changing the service rates, so as to minimize the average cost rate. Our first step was to consider special cases as, for example, the case of "local" optimization, in which the decision of changing the service rate of one facility depends only on the number of customers in the queue in front of that facility, independently of the number of customers in the other (optimization by stages). The answer to this problem turned out to be trivial, since, according to Reich [15] the departure process of a state dependent M/M/1 queueing system is an independent Poisson process with the same rate of the arrival process. With this result we see that the two stages of the system are stochastically independent, therefore, the optimal policy is as characterized by Crabill [7], in each stage. Another case is when the service rate in one of the facilities is constant and the service rate in the other one may vary, depending on the number of customers in both stages of the system. We did some numerical experimentation, using Markov decision programming techniques (Howard's and White's algorithms) in the case of finite queue capacities. These indicated that the optimal policy is approximately the same as the optimization by stages. Some theoretical characterizations were attempted mainly because the algebraic structure of this problem seemed to suggest some simplifications (the matrix of rate of transitions is tridiagonal by blocks, each block being sparse and of simple structure). Fitting to this same algebraic structure is the case of an M/E /l queueing system where the rate in each phase of the Erlang type of service is controllable. For this problem we/were able to

-114generalize one of Crabill's [7] results of the controllable M/M/1 system. In the case of monotone increasing holding costs, under some restrictions, with two alternatives for service rate, it appears that the optimal policy is characterized by the values I and N such that, if the number of customers in the system is n < N, then use the slow service, if n > N, then use of the fast service, if n = N, then use of the slow service when the service is in phase I < I and use the fast service when I > I. However, we do not offer a proof to this effect. Still another interesting problem, which later led us to the problem of this thesis, is the case where the chosen service rate alternatives at a given time, say Ai and i, must be such that a p. + 1 2 1 1 a 2 < c, where a and a are constants and c represents a certain 22 1 2 total service capacity. Analytical results of the cases mentioned above were quite limited and the numerical experimentations did not lead us to any discovery of efficient methods of reducing the cost of the computations to the point of usefulness. However, a simpler form of the problem with limited total service capacity, with the additional restriction of 1k being equal to c/ak or zero, k = 1,2, opened up new possibilities, since in this case simultaneous service in both stages was not allowed (this is the case of a single server). It was then possible to assume more general service time distributions keeping the analytical considerations at a tractable level. Using departure epochs, this problem is a Markov renewal programming problem and, in the case of finite queue capacities,

-115the optimal policy can, at least, in principle, be obtained by Howard's algorithm in any given case. However, in the meantime we became more interested in the behavior of special policies that by their simplicity promise to be of practical significance. This thesis has been concerned with such policies. 4. Related Topics and Possible Extensions Evidently, the six policies studied in this thesis do not constitute all possible "simple" switching policies. We can, for example, imagine the case where the server, upon completing the serving of a customer in one stage, remains in that stage only if the number of customers (Qk) in it is less than the number of customers (QP) in the other stage, otherwise he switches. The "reluctant case" for this policy would be: The server remains in the present stage if k O Q> + N, otherwise he switches. Other policies could be obtained from the combination of the previously defined policies, for example, policies SSS(Q = M) and WNFS 2 N can be followed simultaneously. These new rules can be analyzed by the methods used in this thesis. As mentioned in Section 3 of Chapter II, the methods of analysis for parallel queues [Takacs [20] and Eisenberg [8,9]) are similar to the methods of this thesis and, therefore, we may expect that some more general models, results of the combination of parallel and series queues attended by one server, can be analyzed by similar methodology. An interesting problem to consider would be the case where the second stage of the sequential model receives, besides the customers from the first stage, an independent Poisson stream of customers. We could also consider

-116a parallel system with two service facilities (F and F ), where a customer departing from one service facility, say F, is fed into the queue of facility F, provided that the customer has not received service 2 in facility F. These two models are special cases of a more general situation where a customer, upon completing service in facility Fk, leaves the system with probability pk and goes to facility F~ (k # k; k = 1,2; 9 = 1,2) with probability 1 - pk' provided that the customer has not received service in FR. The dimension of the state space for this model would be quite large, since we have to keep track of all types of customers in the queues and in service. A simple case of this model is when the arrival rate (of customers coming from outside the system) to one of the facilities is zero. This corresponds to -he model of this thesis with the additional condition that a customer departing from the first stage leaves the system with probability p and goes to the second stage with probability 1 - p. There should be no difficulties in extending the results of this thesis to this model, for all of the six policies. An important aspect to be considered is the numerical implementation of the solutions, mainly the ones corresponding to the reluctant policies, in particular policy SSS(Q = N). The assessment of the accuracies in the 2 calculation of the state probabilities is very important since all of the pertinent quantities are expressed in terms of these probabilities. This is a task that we expect to undertake in the near future. At the time this thesis was concluded only a few numerical experimentations were made and no conclusive answers were found. This is why we did not include the case of reluctant policies in the numerical examples of Section 1.

-117The method of analysis of the policy SSS(Q = N) seems to be weak. 2 An alternative approach is to eliminate from the original chain the departure epochs of the second stage, except the last departure. However with this approach we would have a weaker description of the behavior of the system. An intriguing question is whether or not there is any relationship between the iterative scheme of Section 3 of Chapter II and the direct approach shown in Section 7 of the same chapter.

LIST OF REFERENCES i. M. Abramowitz and I. A. Stegun (editors), Handbook of Mathematical Functions, Dover. 2. BAvi-itzhak and M. Yadin, "A Sequence of Two Servers with No Intermediate Queue," Management Science, vol. 11, 553-564 (1965). 3. B. Avi-itzhak, W. L. Maxwell and L. W. Miller, "Queueing with Alternating Priorities," Operations Research, vol. 13, 306-318 (1965). 4. P. J. Burke, "The Dependence of Delays in Tandem Queues," Annals of Mathematical Statistics, vol. 35, 874-875 (1964). 5.,____ "The Output Process of a Stationary M/M/s Queueing System," Annals of Mathematical Statistics, vol. 39, 1144-1152, (1968). 6. R. B. Cooper, Introduction to Queueing Theory, The Macmillan Company, New York, 1972. 7. T. B. Crabill, "Optimal Control of a Queue with Variable Service Rate," Tech. Rep. No. 75 (1969), Dept. of Operations Research, Cornell University. 8. M. Eisenberg, "Two Queues with Change Over Times," Operations Research, vol. 19, 386-401 (1971). 9. _____, "Queues with Periodic Service and Changeover Time," Operations Research, vol. 20, 440-451 (1972). 10. R. A. Howard, Dynamic Probabilistic Systems, vol. II, Chapter 15, Wiley (1971). 11. G. C. Hunt, "Sequential Arrays of Waiting Lines," Operations Research, vol. 4, 674-683 (1956). 12. R. T. Nelson, "Labor Assignment as a Dynamic Control Problem," Operations Research, vol. 14, 369-376 (1966). 13.,_____. "Dual-Resource Constrained Series Service System," Operations Research, vol. 16, 324-341 (1968). 14. M. F. Neuts, "Two Queues in Series with a Finite, Intermediate Waiting Room," Journal of Applied Probability, vol. 5, 123-142 (1968). -118

-11915. E. Reich, "Waiting Times When Queues Are in Tandem," Annals of Mathematical Statistics, vol. 28, 768-773 (1957). 16.,"Note on Queues in Tandem," Annals of Mathematical Statistics, vol. 34, 338-341, (1963). 17. V. K. Sahney, "Single-Server Two-Machine Sequencing with Switching Time," Operations Research, vol. 20, 24-36 (1972). 18. H. Stehfest, "Numerical Inversion of Laplace Transforms," Communications of the ACM, vol. 13, No. 1, (1970). 19. J. S. Sykes, "Simplified Analysis of an Alternating-Priority Queueing Model with Setup Times," Operations Research, vol. 18, 1188-1192 (1970). 20. L. Takacs, "Two Queues Attended by a Single Server," Operations Research, vol. 16, 639-650 (1968). 21., Combinatorial Methods in the Theory of Stochastic Processes, Wiley (1967).

UNIVERSITY OF MICHIGAN 3 9015 03483 5754111111111 39015 03483 5754