UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The G/G/2 queue : cyclic vs. FIFS service order Piater, Reinhard 1975-01-28

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata


831-UBC_1975_A6_7 P05.pdf [ 1.94MB ]
JSON: 831-1.0079362.json
JSON-LD: 831-1.0079362-ld.json
RDF/XML (Pretty): 831-1.0079362-rdf.xml
RDF/JSON: 831-1.0079362-rdf.json
Turtle: 831-1.0079362-turtle.txt
N-Triples: 831-1.0079362-rdf-ntriples.txt
Original Record: 831-1.0079362-source.json
Full Text

Full Text

THE G/G/2 QUEUE: CYCLIC VS. FIFS SERVICE ORDER by REINHARD PIATER M.S.E.E., Polytechnic Institute of Brooklyn, 1965 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in the Department of MATHEMATICS and the INSTITUTE OF APPLIED MATHEMATICS AND STATISTICS We accept this thesis as conforming to the required standard. THE UNIVERSITY OF BRITISH COLUMBIA August, 1975 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. It is understood that copying or publication of this thesis for financial gain shall not be1 allowed without my written permission. Department of Mathematics The University of British Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1WS Date August 31. 1975 ABSTRACT The relative waiting times in a G/G/2 queue are investi gated for FIFS vs.' cyclic service order. We.will prove that under the FIFS system the expected wait is shorter given rather weak conditions on the arrival process. How ever, the wait is not necessarily stochastically less, nor is the average wait less for every realization. This result bears on the upper limits on expected wait in a G/G/k queue given by Brumelle and Kingman. iii TABLE OF CONTENTS Page Abstract ii Table of Contents iiList of Figures iv Acknowledgement v Text: I. Introduction and Summary 1 II. The Two Systems - Definitions and 5 Elementary Notions III. The Two Systems - Some Partial 9 Results A. Comparison of Realizations 9 B. Comparison of Distribution 11 Functions for Waiting Times and Total Work IV. Proof of EW < EW via Value 15 Functions Bibliography 25 Appendix A: Proofs of Realization 26 Theorems Appendix B: Distribution Functions for 31 Waiting Times and Total Work iv LIST OF FIGURES Page Fig. 1. Geometric Depiction of 6 Work Loads Fig. 2. Pictorial Representation of 29 Counterexample Fig. 3. Vf» -set for (W,Q) 31 Fig. 4. Y" -Set for (U,L) 34 Fig. 5. An Example of the Non-Monotonic 36 Behavior of U V ACKNOWLEDGEMENT This work was done under the supervison of S. L. Brumelle of the University of British Columbia, to whom the author is grateful for this interesting problem and for his patient encouragement during periods when the problem appeared to be intractable. Reinhard Piater 1 I. Introduction and Summary A familiar example of a queuing system is the ser vicing of customers at a bank. Customers arrive at the bank according to some probability law. There are k tel lers working in parallel. A given customer either gets served immediately by one of the tellers or else he first waits in some line. The successive time spans marked off by the arrival of the customer, his beginning of service, and end of service are called the waiting time and service time. The method whereby a customer is assigned to a given teller is called the service discipline. For example, banks in Vancouver, B.C. prior to 1974 had the following service discipline: there were k separate queues, one in front of each teller, and a given customer would choose one of the queues (presumably the shortest) immediately upon his arrival. The customer could also leave the bank without being served (this is called "balking") or he could switch queues during his waiting period ("jockey ing"). During 197 4 some Vancouver banks switched over to the single queue system wherein the person in front of the queue would go to the next available teller. This service discipline is called "first-in-first served" (FIFS). 2 Although most phenomena that occur in real-world queuing systems (jockeying,balking, bulk arrivals, spe cialized servers, etc.) have been considered and analysed in the queuing literature, substantial attention is still being paid to the standard classical model, which may be described as follows: The service discipline is FIFS, with no balking, the interarrival times are independent, identically distributed (i.i.d.) random variables indepen dent of the service times, which themselves are i.i.d. ran dom variables, and the k servers all work at the same rate, independent of the length of the queue. The behavior of this system depends only on the distribution function of the service times, H(s), and that of the interarrival times, G(t) . Of particular interest are the waiting times of cus tomers, and indeed a good figure of merit for a queuing system is the limiting expected waiting time. In general, this quantity is difficult to calculate, even for a single server queue (k=l). Marshall [l] and Kingman [3~] have developed an upper bound for the expected waiting time in a single-server queue in terms of the means and variances of the service and interarrival times. For k ~? 1, the sit uation is considerably more complicated. However, Brumelle f2j and Kingman f3j have succeeded in establishing upper bounds for the expected waiting time in a k-server queue 3 by comparison to a judiciously chosen single-server queue in which the expected waiting time is greater. Brumelle's single server queue was constructed from the k-server queue by assigning all arrivals in the latter to the first server, but giving those arrivals that would not have gone to the first server a zero service time. Under this modification none of the waiting times is decreased"*". Kingman, on the other hand, asserted that the expec ted waiting time in a k-server queue cannot decrease if the service discipline is changed from FIFS to one where the arrivals are assigned cyclically to the k servers. (Thus the server would get the i^*\ (i+k)^, (i+2k) . . . arrivals. This creates k stochastically identical single-server queues). Since Kingman's bound is a sharper one than Brumelle's, it is important that Kingman's assertion be proved. In this paper the case k=2 is examined in depth. We will show that i) the limiting expected waiting time for the FIFS system is less than or equal to that for the cyclic system, however, Since the single-server queue thus generated does not have independent input, Brumelle had to extend Marshall's results. 4 ii) there exist realizations where the average wait is larger for the FIFS system, and iii) there exist service time and interarrival time distributions for which the waiting times are not stochastically greater for the cyclic system. 5 II. The Two Systems - Definitions and Elementary Notions We consider a system of two parallel servers each th working at unit rate. The i arriving customer (denoted by ) has service time S^ and interarrival time T^ (taken to be the time between the arrivals of £T) and (^+3) ) • S^ and T^ are random variables. We assume that the first customer finds the system empty. Initially, no assumptions are made about the probability law govern ing the process *£(S^,T^), i=l,2,.. . , A given set of numbers *£(s^, t^) : s.J 0,t.2 0;i=l,2,...j is called a realization of the process if S.=s.,T.=t. for all i2 1. Under the FIFS system (hereafter denoted system I)is immediately served if he finds one of the servers idle; otherwise he waits in queue an amount of time W^ until the first time a server becomes free after (i-l) starts service. Although this description suggests a single queue of waiting customers, it is more convenient, as in [2] , to consider each server to have his own queue, such that a given customer immediately joins the queue of that server who eventually serves him. If we denote by the hypothetical waiting time of if he were to join the other queue, then the pair of numbers of (W^,Q^) denotes the remaining work (at the instant of 's arrival) of the two respective servers if (i-l) were to be the last customer granted service. These definitions yield the following recursion relationships: W.+1 = minftw.+S.-T.^fQ.-T.T} Qi+1 = max{ [w.+S.-T^ [QI-TJ4} where the [ ^operator denotes the diode function: (1) f xiO f x <0. A useful schematic aid in depicting the process is shown in Fig. 1, with the bars being "fed" sporadically on the right by amounts and being "eaten away" from the left at a uniform rate. i i ^© arrives Ti Q arrives Fig. 1. Geometric Depiction of Work Loads. 7 In the cyclic system (hereafter denoted system II) customer goes to the first server if i is odd, to the second if 1 is even. We define W. to be the current visible 1 work of the server that goes to at the time of his arri val, the work of the other server, and obtain the follow ing recursion relationships: W. , = T-T.~| + l+l I l iJ = {"w.+S.-T.l . L l l iJ (2) Q. Vi We note here briefly that system II is, in princi ple, simpler than system I, since it can be reduced to a one-dimensional process by considering two-step recursions 1+2 I W.+S.-T.-T. .,1 . (3) L I I I i+i J It is useful to define two more quantities: Total Work: L± = Wi+Qi . Unevenness: = Q^~W^ (and, similarly, and in system II). In comparing system I with system II it is at first instructive to assign them the same realization of *£(S^,T^), i=l,2,..^ and calculate the corresponding set of numbers 8 (V\L ,Q^) and (W^Q^) for every i. For every realization we have W,=W,=Wo=Wo=0 and the two systems run identically and W.=b,Q.=a) in system II for some a,b where a<b. At this point the two systems part company with system I gaining an immediate advantage in waiting time but at the cost of an "inferior" state for the next arrival. A "good" state, intuitively, is one with a high amount of unevenness for a given amount of total work. However, very high unevenness may occasionally cause a server to become prematurely idle, which is "bad" since then the total work is not being reduced at maximum rate. Intuitively, it is clear that system II will tend to have more imbalance in the two queue lengths than system I and hence be more susceptible to partial server idleness. This implies more total work and therefore longer waiting times. However, it is difficult to quantify these statements for a formal proof. In fact, the proof presented in section IV will not be along this line of reasoning. until some arrival sees (W.=a,Q.=b) in system I 9 III. The Two Systems - Some Partial Results A. Comparison of Realizations In this section we view the S. and T. as given num-bers and ignore their probability laws. No restrictions are placed on them other than their non-negativity. We will say that an n-block violation occurs starting at (T) if W. > 3> w. . . D rr i . and ask whether it is possible for an n-block violation to occur starting at (T) and, if so, what is the minimum such n. These questions are answered as follows (the groundwork and proofs are presented in Appendix A): Lemma JL: Suppose arrival (T) finds the state to be (a,b) in system I and (b,a) in system II with a<b. Then an n-block violation starting at is impossible for n=l,2,or 3. Since the condition of Lemma 1 can be fulfilled at the very earliest at i=3, it is clear that, starting at (ji^, 5-block violations cannot occur. However, 6-block violations are possible: Theorem 1: The minimum n necessary for an n-block viola- . tion, starting at (\) , is 6. 10 Let us for a moment consider the service and inter-arrival times to be independent random variables, so that the instances where an arrival finds both system I and II empty are renewal points. With a very light traffic intensity (ES/2ET« 1) the renewal periods would encompass only a few arrivals, which, by Theorem 1, would tend to favour system I. We will say that a system becomes partially idle if, when one of the servers finishes the work of a customer, no new customer is in the queue to immediately take his place. A necessary condition for a 6-block violation is that system I becomes partially idle before (5) arrives. One may ask whether an n-block violation (n — 7) is possible in which system I never becomes idle. The answer is no: Theorem 2: If system I does not become partially idle at any time after the arrival of , then an' n-block violation, starting at , cannot occur for any n. Thus system I is certainly no worse than system II in a fully congested system (no partial idleness). Suppose we have an n-block violation for a given set of numbers ^(S^,T^), i=l,2,...,n^. Let us take the n ordered numbers , S2 # • . • • S ». permute them in some way and compute 11 the new waiting times. For a permutation <5 inA„ , the group of permutations of {l,..,n^ , let ,W® be the corresponding waiting times obtained as above. Consider the conjecture that If this conjecture was true for all n and any set of , it would follow that the expected wait in system I is less than or equal to that in system II provided that the are independent and identically distributed. Unfortunately, the author has been able to prove this conjecture only for the case of n=6. B. Comparison of Distribution Functions for Waiting Times and Total Work In this section, we make the usual assumptions about the ^(S^ ,T^) , ' i-1, 2 , . . ."^ process, namely that the service times are i.i.d. with distribution function H(s) and independent of the interarrival times which are also i.i.d. with distribution function G(t). We define the following two-variable distribution functions: 12 Fi(x1,x2) = P[W±^ x1,QI< x2"] Vxrx2' = p[Wi-xi'Q±-x2] The following recursion relationships can be derived via a method given in (see appendix B): Let U(x1,x2) be the two-dimensional unit-step-function: U(x1,x2) =1 [1 if xx > 0 and x2"> 0 0 otherwise Then F-^x^x^ = F^x^x^ = \J(x^,x2) and, for i 2 1, ^i+l(Kl,X2) = u(x1'x2)jJ^i(x2~S+t'Xl+t)dH(s)dG(t) (4) !U(X1/X2)||Fi (x2-s+t,x2+t)dH(s)dG(t) if x1> x2 (5) U(x1,x2) jj Ai(x1/x2,s,t)dH(s)dG(t) if x^ X2 where A± (x1,x2,s,t) = Fi (x1-s+t.x2+t)+F,i(x2-s+t,x1+t)-F^(x^-s*t:,x1+t) It is shown in |41 that F.(x,,x„)2 F.,,(x,,x„) L J l 1 2 l+l 12 for every (x^,x2) and every i, and that F(x,,x„) = lim F.(x,,x_) i-»oo ± ± & is the steady-state distribution function provided that ES<2ET. 13 A similar statement may be made for system II. We consider the following series of conjectures (an omitted subscript indicates steady-state conditions): A. EWrSEW B. EW.^ EW. for all i 1 1 C. F(x,<*>)-F(x,oo) for all x D. (x,oo ) > F.('x, oo ) for all i, all x E. F^ (x.^ ,x2) > F^ (x^ ,x2) for O^x-^x,, and all i. (Note that E=7>D=$>C^A and B=^A.) When investigating these conjectures, the author at first thought it possible to prove conjecture E via the recur sion relationships (4) and (5). However, it is not true for every possible pair of probability distributions H(s) and G(t). In fact, a counterexample can even be produced for conjecture C. This is shown in appendix B. A random variable X is said to be stochastically larger than another random variable Y if, for every z, we have p[x:> z^j ~Z P[Y > zj . The fact that conjecture C does not hold for every H(s) and G(t) means that W is not necessarily stochastically larger than W. The author does believe that L is stochastically larger than L. However, as indicated in appendix B, the recursion relationships involving P["UL< x^ ,L^:£ x^] are not nearly as simple as those for V\L and Q^. Moreover, the non monotonic behavior of the unevenness quantity, alluded to in Section II and further illustrated in appendix B, makes it difficult to generate a suitable induction statement involving the th. Consequently, the question whether L is stochastically larger than L is left as an unsolved problem. 15 IV. Proof of EW ^ EW via Value Functions As in section II, we consider each server to have his own queue, but assume at first some general but fixed policy of assigning arrivals to servers. We also drop the assumption of an empty system when (T) arrives. Observing this stochastic process only at the arrival epochs, we may extract the following discrete-parameter, two-variable continuous state stochastic process: |zi-(Xi,Yi), i=l,2,... | Z-^^y)^ where = work that (i) sees in front of that server to whom (j^~3^ was assigned, = work that sees in front of the other server.1 Under a stationary policy the decision to assign (\) to a specific server depends only on the state Z^ of the process and not on the previous history. For example, both system I (FIFS) and system II (cyclic) constitute stationary policies. We note that if, in addition to a stationary policy, we also have i.i.d. service times and i.i.d. interarrival times, then ^Z^, i=l,2,..."^ is a Markov Process. If we leave the policy open to choice and specify some cost structure, we have a Markov Decision Process. However, in the following exposition we will not assume that the 1This is a slight change in order from the state defini tion of Section III A. 16 interarrival times are i.i.d., and consequently the resulting process may not be Markov. Nevertheless, we will borrow from Markov Decision Process theory the concept of immediate cost and state value functions. We restrict our attention now %e-ft©w to two policies: FIFS and cyclic assignment. We take as immediate cost the actual waiting time and consider the criterion of total expected cost over a finite horizon. The following conditions on the {(S^ ,T.) , i=l, 2 , . . !} process will be sufficient to prove system I to be better than system II: C-^) {Ti\ is anY arbitrary sequence of non-negative random variables. C2) {s^iis an i.i.d. sequence of non-negative random variables independent of {T^., For convenience, we denote by ^ the portion of Euclidean n-space in which every coordinate is non-negative. A given realization of the first n interarrival times t= (t^,t2,...,tn) and the first n service times s=(s^,s2,...,sn) can thus be viewed as points in ^ and the sequence of random variables T= (T^T.^. . . . ,T ) and S= (S1,S2 , . . . ,Sn) as random vectors inlf^^. 17 We define the following value functions for kin: Vk(x,y,t,s) = ^ (W±| Z^Ury) ,T=t,S=s) (6) L-l V.k(x,y,t) = Es Vk(x,y,t,S) (7) V.k(x,y) = ET Vk(x,y,T) (8) where W^ is the waiting time of in system I... Corresponding definitions for system II are made using the symbol. Referring back to Section III A, we see that V"n (x,y, t,s_) is an. n-block sum of waiting times for a given realization start ing with the state (x,y). We note that Vn(x,y,t,s)=Vn(y,x,t,s_) and also that by Lemma 1 Vn(x,y,t,s)< Vn(x,y,t,£) for n=l,2, or 3. (9) We will prove that Vn(x,y,t)< Vn(x,y,t) (10) for any (x,y) € 7R +)anY Ji 6 1R+' anci anY positive integer n. It is clear that if (10) holds then so does Vn(x,y) < Vn(x,y). (11) If, in addition, i) {T^} is an i.i.d. sequence, and ii) ES<2ET, then the steady state waiting times EW and EW exist and are given by EW = lim 1 V (x,y) r\-90o n n EW = lim 1 V (x,y) (see, for instance, Ross [5^) n-*>oo n Thus (10) is a stronger statement than EW < EW. To prove (10), some properties of the value functions are first established via the following lemmas: Lemma 2: Vn(x,y,t,s_) is a non-decreasing function in x and y. This is easily proved by induction using the recur sion relationship: Vn(x,y,t,s) = x+Vn_1 ([y-tj+, [x+s1-t]] , t,£) (12) where t = (t2 , t3 , . . . , t ) € IR^1 and £ = (s2,s3,.. . . ,sn) € 1f^n+1. .Corollary: Vn(x,y,t) is a non-decreasing function in x and y. Lemma 3: Vn(x1,y1,t,s) + Vn(x2,y2,t,s) = Vn(x1,y2,t,s) + Vn(x2,y1,t,s) for any x1,Y1,x2,y2,t,s. 19 Proof: This can be seen intuitively by considering two cyclic queuing systems with different initial work loads but identical future arrivals and exchanging their second servers. Formally, we proceed by induction: n=l: Each side is equal to x-^+x,,. We assume the statement for i=l,2,...,n-1 and use relation ship (12) : Vn(x1,y1,t,s) + Vn(x2,y2,t,s) = Xl + V-l(L"Yl_tJ+> [xi+si-ti"] + 't/|) + X2 + "n-l([y2-tlT,[x2+Sl-tJ+'^i) = x2 + Viffyi-tJ* [x2+Sl-tJ+,At,i) + Xl + Vl((Y2-tlT; [VSl-^r 'trs) = V (x2,ylft,s) + Vn(x1,y2,t,s) . Corollary: V^x^y^t) + Vn(x2,y2,t) = vn(x1'Y2'i) + vn(x2'Yl'-)  Lemma 4: Let (a-^a,,) and (b^,b2) be states given by al = [x+s_tl_t2l+ a2= [[y-hT^-^T bi= I y^-v^]* b2 = [[x-tir+s-t2]+ where Of x<y, s 2 0, t^Z 0, t22 0. Then a^< a^ and either A: a^i b2 and a2=b1 or B: a^-£ b^ and a2=b2 . Proof: 1) a> ["y-t,+s-t2J+> a, (using PLUS 1 and PLUS 3 from appendix A) 2) if t^ y then a2=bl and b2~ al ^by PLUS lf PLUS 3^ which is case A. If t^> y then a2=b2 and a^< h± (by PLUS 3) which is case B. The following lemma will be essential in the final proof of (10): Lemma 5: Let conditions and hold for the arrival and service processes and let x,y be numbers satisfying O^x-^y. Then V^x.y.t) < Vn(y,x,t) for any t € ]R ^ and any positive integer n. Proof: By induction. For n=l, V1(x,y,t) F x<y '= (y,x,t) . 21 For n=2, ~2(x,y,t) = x + [y-tj + V2(y,x,t) = y + The desired inequality follows from PLUS 4. Now assume induction hypothesis for i=l,2,...,n-1. If the present state is (x,y), then the next two waiting times will be x and [y-T-J]+. and the future state (two steps from now) will be [x+Si-Ti-T2]+; [fr-Tj* + S2-T2]Y ( Hence, Vn(x,y,t) = x +[Vt1f + s^V2 ( [x+Si-t'^t^fty-tJ-fS^tJ, t) A n_2 (13where t = (t3, . . . , t ) e jf^ + . Denoting by A(x,y,t) the last term of (13), we have Vn(x,y,t) = x + [y-t1"]++ A(x,y,t) Vn(y,x,t) = y + [x-t1J++ A(y,x,t) We show that A (x,y, t) < A (y,x, t) . By definition, A(x,y,t) = jjvn_2( [x+s1-t1-t2]+)f[y-t1]++s2-t2^+,t)dH(s1)dH(s2) . [(s1,s2) :s12 0,s2r o] 22 Dividing the region of integration, we have A(x,y,t) =||vn_2([x+s2-t1-t2]*f[y-t1]++s2-t J+,t)dH(S;L)dH(s2) [(s17s2) :s1=s2> o] +J[J[vn_2<[x+si-Vt^r[y-tiT+s2-t2T-^)^ [(s1,s2) :0 £ s1< s2~} ^n_2([x+s2-t1-t2"]+,[[y-t1]++s1-t2]+ /t)] dH(Sl)dH(s2). +v Finally, employing the corollary to Lemma 3: A(x,y,t) = jJ\_2([x+S2~tl"t2']"t*'[tY~tJ++S2"t2]+ ' ^ dH (sl} dH (s2) [(B1#S2) :Sl=s22 0] + f[^n-2([x+sl"tl"t2"]+'[[y-tlT*+Sl"t2T+ »i)dH(s1)dH(s2) [{sirs2) :0S s1< s2"] + J|vn_2( [x+s2-tl-t2]+,[[y-tl]1"+s2-t2]+,t) dH(Sl)dH(s2) [(slf s2) :0£ s1< s2] The corresponding integrands of A(x,y,t) can be shown to be less than or equal to those of A(y,x,t). For example, the respective first integrands are: "n-2 (Cx+s2"trt2l+'[[Y_t J* +S2_1J t) = Vn_2(a1,a2,t) and Vn-2(Ly+s2-trt2i 'U^lJ +s2-t2J = Vn-2(bl'b2'^ where a^,a2,b^, and b2 are as in Lemma 4 (with s=s2). For case A (in Lemma 4), we have V2(ara2f|)< V2(a2,art) < V2 (b^b^f) where the first inequality follows from the induction hypo thesis and the second from Lemma 2. For case B Vn-2 (ai'a2'ii) - vn_2 ,b2'—^ bY Lemma 2-Applying similar arguments to the other integrands complete the proof of the lemma. We are now ready to prove assertion "(10) : Theorem 3: Suppose the arrival process |(S^,T^),i-1,2...^ obeys conditions C^,C2. Then for every initial state (x,y) 2 n £ {R+f every t €. 1R + » and every positive integer n, we have Vn(x,y,t) < Vn(x,yt-t) . Proof: By induction. For n=l, V^(x,y,t) = min(x,y) and 'vi(x,y,t) = x If x£ y, then by inductive hypothesis 24 Vn(x,y,t) = Vn(x,y,t) If y < x then but This completes the proof. Corollary: Under the standard assumptions of queuing theory (i.e. is an i.i.d. sequence, independent of {T^ , also i.i.d., ES<2ET), EW£EW. Proof: Via standard definitions and'limit theorems (see Ross [5"] , chapter 5) /1 4- V EW = lim Ej _ <2^IW. ) independent of initial conditions. n*oo \n l=, *-J By definition (8) The desired result follows from Theorem 3. 25 BIBLIOGRAPHY 1. K. T. Marshall, "Some Inequalities in Queuing", Operations Research Vol. 16, 651-665 (1968). 2. S. L. Brumelle, "Some Inequalities for Parallel-Server Queues", Operations Research Vol. 19, No. 2, 402-413 (1971). 3. J.F.C. Kingman, "Inequalities in the Theory of Queues", J. Royal Stat. Soc, Series B, Vol. 32, 102-110 (1970). 4. J. Kiefer and J. Wolfowitz, "On the Theory of Queues with Many Servers", Trans. American Math. Soc, Vol. 78, 1-18 (1955). 5. S.M. Ross, "Applied Probability Models with Optimization Applications", Chapter 5,Holden-Day (1970) APPENDIX A: Proofs of Realization Theorems Initial Note: It is possible to prove Theorem 1 directly by using the recursion relationships (1) and (2) and con sidering the cases h=3,4,5. For n=3, we have iWi = 0 + 0 + W3 = ntinlfs^-T^^S^T^] Iff. = 0 + 0 •+ W3 = [S^T^TJ* The case n=4 is already long and tedious. Essentially, it involves a case by case exploration of 4 different situations corresponding to the number of ways arrivals and join the queues in system I. Direct proof of n=5 was not even attempted since it not only involves a doubling of the number of situations over n=4, but also the individual comparisons are more complica ted. Lemma 1 avoids these problems. It is expedient to first list some of the properties of the £ J+ operation: PLUS 1: [x3+ 2 x PLUS 2: If y 2 0 then QAJ* -y]*= JA-y]* PLUS 3: If A < B then [A-x]+* [B-X]+ 27 PLUS 4: If A<B and x20, then fA]++ [B-XJ+< [B]+ + [A-X]+ # Proof of Lemma 1: We have W.=a, Q.=b, W.=b, Q.-a, a < b. l l l l We must show that ^ W. < ^ W*. for n=l,2,3, n=l W. = a < b = W*. l l n=2 W.+1 = minlfa+S.-T.]^ [b-TJ"} < [b-T.]" So W. + W. L, < a + fb-T.T*" l l+l u iJ ~- r -i+ W. + W.,, = b + a-T.J l l+l «• iJ The desired inequality follows from PLUS 4. ,0 = fb+S.-T.-T.^,~|+ 1+2 L ii 1+lJ n=3 W W i+2 * [b-Ti-Ti+il+ if©g°es to same server as (iy • in system I. W. 1+2 < j"a+S .-T .-T .+/1 if (i~+l) goes to the *• i i i J other server. In any case we have Wi+2 < Wi+2 bY PLUS 3- This yields the desired inequality when combined with the result for n-2. Proof of Theorem 1: Without loss of generality we may assume that if arrival finds W^=Q^ in system I he goes to the server that (1-did not go to. With this convention system I and II exhibit identical behavior (including identical waiting times) until an arrival (J^J sees in system II. At this point we must have VI.-Q. and Q. =w'. , establishing the £- 1111 condition of Lemma 1. The lowest i for which this can hap pen is i=3. So 5-block violations, starting at , are impossible. To complete the proof we must show that 6-block violations can occur. We do this by exhibiting an example i S . l T . l W. l Qi w. 1 Qi 1 2 0 0 0 0 0 2 1 0 0 2 0 2 3 1 0 1 2 2 1 4 2 3 2 2 1 3 5 2 0 0 1 0 0 6 1 3 1 2 0 2 4 3 »k—T6 Fig. 2: Pictorial Representation of Counterexample. s, arrive. her* I ft© arriire heme •I <2> arrives here Proof of Theorem 2: We will prove a stronger result: W. + W.,, < W. + W. , , for any i. 1 l+l l l+l JL To show this, we note that since system I is never partially idle (after ), the total work in I can never be greater than that in II. Thus we have L. = L. + k. (A.2 O). I l l I Now, n. = L. - W. ' *i i I and W. , < rQ.-T.~l+= Q--T. (since no idleness occurs) l+l- L i iJ i i SOW. + W.,< W. + L. - W. - T. = L . - T . . l l+l 111111 30 In system II, we have Q. = L. + H. - W. 11X1 and Wi+1 =[Qi-Tj+ 2 5± - T± (by PLUS 1) so that W. + W. L, Z W. + L. + A. - W. - T. = L. + A. - T. , i l+l l l l l l l l l > which completes the proof. 31 APPENDIX B: Distribution Functions for Waiting  Times and Total Work 1. Waiting Times In Kiefer and Wolfowitz [4j recursion relation ships for the k-server queue are established via the ^ -set. In accordance with the terminology of our problem, we define M'-set as follows: H> (Xl,x2,s,t) = |(y1,y2): [wi=y1,Qi=y2,Si=s,Ti=t)] With this definition, we have Fi+1(x1,x2) = jJP[(Wi'Qi)6 4'(x1,x2,s,t)J dH(s)dG(t) A typical 4* -set is shown Fig. 3. 2 t y. 32 The rectangles formed by the two axes and the points A and B (as shown) intersected with the region above the line v2=Y;L determine the actual -set. Using the inclusion-exclusion principle and noting that there is no probability mass below the Y2=Y± xine/ we 9et p[(Wi,Qi)£ <y (X;L,x2,s,t)] =Fi (x-^s+t ,x2+t) + E\ (x2-s+t ,x1+t) - Fi (Xl-s+t/X;L+t). If x^ x2 then ^ (x1 ,x2 , s , t) = (x2,x2,s,t). This establishes equation (5), The corresponding definition may be used for system II (replacing and by and Q^); here the resulting ^ (x.^ , x2 , s , t) set is a complete rectangle with the upper right vertex at (x2~s+t,x^+t). Hence P^W^Q^e ^(x^x^Sjtj] = F± (x2~s+t thereby establishing equation (4). 2. Counterexample to conjecture C Let H(s) and G(t) be such that Prs..=s] =(1/2 5=2 L 1 J < 1/2 s=4 0 otherwise 33 99/100 t=l P[Ti=tJ = ^ 1/100 t=A (large) 0 otherwise With this arrival process both system I and system II cannot become partially idle until for some i the event [T^=A"J takes place. We pick A so large that the probability that one of the two systems will not empty out completely at that time is negligible. Thus, until ^T^=A*J happens for some i, the total work in system I and II grows continually and equally, with system II tending to be more unbalanced, so that it will tend to have both short and long waiting times (relative to system I). For example P [w6.= 0 | T±=l,i=l, . . . ,5^ =3/16 ^ F6 (0,oo ) ; whi le P [w6=0 | Ti=l,i=l, . . ,5 J =1/4 = F6(0,.oo)# Thus the distribution functions for the W. and l W. variables (F.(x,.oo) and F. (x,oo)) should intersect I l I for sufficiently high values of i. Since we have a renewal process here (with the event T^=A initiating a renewal period), the intersecting behavior of F^(x,oo) and F\(X,OO) should carry over to the steady-state dis tribution functions F(x,oo) and F(x,oo ) . 3. Recursion Relationships Involving Work and Unevenness With and defined as in section' II and letting Ki(xl'X2> = P[U. * x^L.ST xj; we have Ki+1(x1'x2) = [\v [(Ui 'Li> e ^ (xi 'x2 's 't)] dH (s) dG (fc) where Y(x]_,x2fS,t) = |(Y1fY2) : ["Ui=Yi 'Li=Y2 ' Si=s 'Ti=^[ =^[Ui+l* xl'Li+l£ x2]]. A typical ^ -set' is shown in Fig. 4. Fig. 4.'Mr-set for (U,L) . Shaded area = T(5,10,7,9) 35 The vertices A-E are all functions of x^,X2,s,t. It is clear that the term PJ(U^ ,L^) 6 'VjT (x^ ,x2 , s , t) J cannot be expressed directly in terms of K.(,) as was the case for (W^,Q^). Rather such an expression would have to take the form of a double integral with very complicated limits. A further potential problem in proving K^(oo,x) 2 K\(<x>,x) is that this statement is in itself an insufficient induction hypothesis: we would need a stronger statement such as K. (x^x^l? K. (x^Xj) to insure that the induction step goes through. However, the last hypothesis cannot be true since U. can be negative while U. cannot be. A l ^ I workable replacement is hard to find because functions involving the unevenness quantity tend to be non-monotonic. As an example consider the following function: f(.x,y)=E [<EI+1-LI+1)| Sr.=L.=A,U.=xFU.=yJ '.'. l l l l J J This is the expected difference in the next state work given that the present work is equal but with system I and II having unevenness x and y, respectively. The non monotonic behavior in x and y can be demonstrated even for the M/M/2 queue, with 36 H(s) = 1 - e -s/3 G(t) = 1 ,"t/2 This is shown in Fig. 5, which is a sketch of the sign of f(x,y). -5 •+-T + 4 + + + + +-+ + + 5 x Fig. 5. An Example of the Non-Monotonic Behavior of U: Regions where f(x,y) is positive and nega tive (M/M/2,A=5) 


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items