UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

The G/G/2 queue : cyclic vs. FIFS service order 1975

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

Item Metadata

Download

Media
UBC_1975_A6_7 P05.pdf [ 1.94MB ]
UBC_1975_A6_7 P05.pdf
Metadata
JSON: 1.0079362.json
JSON-LD: 1.0079362+ld.json
RDF/XML (Pretty): 1.0079362.xml
RDF/JSON: 1.0079362+rdf.json
Turtle: 1.0079362+rdf-turtle.txt
N-Triples: 1.0079362+rdf-ntriples.txt
Citation
1.0079362.ris

Full Text

THE G/G/2 QUEUE: CYCLIC V S . FIFS SERVICE ORDER by REINHARD PIATER M.S.E.E., Po l y t e c h n i c I n s t i t u t e of Brooklyn, 1965 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of MATHEMATICS and the INSTITUTE OF APPLIED MATHEMATICS AND STATISTICS We accept t h i s t h e s i s as conforming to the requ i r e d standard. THE UNIVERSITY OF BRITISH COLUMBIA August, 1975 In present ing th is thes is in p a r t i a l fu l f i lment o f the requirements for an advanced degree at the Un ivers i ty of B r i t i s h Columbia, I agree that the L ibrary sha l l make it f ree ly ava i l ab le for reference and study. I fur ther agree that permission for extensive copying of th is thes is for scho la r ly purposes may be granted by the Head of my Department or by h is representa t ives . It is understood that copying or p u b l i c a t i o n of th is thes is for f inanc ia l gain sha l l not be1 allowed without my wri t ten permission. Department of Mathematics The Univers i ty of B r i t i s h Columbia 2075 Wesbrook P l a c e Vancouver, Canada V6T 1WS Date August 31. 1975 A B S T R A C T The r e l a t i v e w a i t i n g times i n a G/G/2 queue are i n v e s t i - gated f o r FIFS vs.' c y c l i c s e r v i c e order. We.will prove that under the FIFS system the expected wait i s shorter given r a t h e r weak c o n d i t i o n s on the a r r i v a l process. How- ever, the wait i s not n e c e s s a r i l y s t o c h a s t i c a l l y l e s s , nor i s the average wait l e s s f o r every r e a l i z a t i o n . This r e s u l t bears on the upper l i m i t s on expected wait i n a G/G/k queue given by Brumelle and Kingman. i i i TABLE OF CONTENTS Page A b s t r a c t i i Table of Contents i i i L i s t of F i g u r e s i v Acknowledgement v Text: I. I n t r o d u c t i o n and Summary 1 I I . The Two Systems - D e f i n i t i o n s and 5 Elementary Notions I I I . The Two Systems - Some P a r t i a l 9 R e s u l t s A. Comparison of R e a l i z a t i o n s 9 B. Comparison of D i s t r i b u t i o n 11 Fu n c t i o n s f o r Wait i n g Times and T o t a l Work IV. Proof o f EW < EW v i a Value 15 Fu n c t i o n s B i b l i o g r a p h y 25 Appendix A: Pro o f s of R e a l i z a t i o n 26 Theorems Appendix B: D i s t r i b u t i o n F u n c t i o n s f o r 31 Waiting Times and T o t a l Work i v LIST OF FIGURES Page F i g . 1. Geometric D e p i c t i o n of 6 Work Loads F i g . 2. P i c t o r i a l R e p r e s e n t a t i o n of 29 Counterexample F i g . 3. Vf» - s e t f o r (W,Q) 31 F i g . 4. Y " -Set f o r (U,L) 34 F i g . 5. An Example of the Non-Monotonic 36 Behavior of U V ACKNOWLEDGEMENT T h i s w o r k was done u n d e r t h e s u p e r v i s o n o f S. L. B r u m e l l e o f t h e U n i v e r s i t y o f B r i t i s h C o l u m b i a , t o whom t h e a u t h o r i s g r a t e f u l f o r t h i s i n t e r e s t i n g p r o b l e m a n d f o r h i s p a t i e n t e n c o u r a g e m e n t d u r i n g p e r i o d s when t h e p r o b l e m a p p e a r e d t o be i n t r a c t a b l e . R e i n h a r d P i a t e r 1 I . I n t r o d u c t i o n and Summary A f a m i l i a r example o f a queuing system i s t h e s e r - v i c i n g o f customers a t a bank. Customers a r r i v e a t the bank a c c o r d i n g t o some p r o b a b i l i t y law. There are k t e l - l e r s w o r k i n g i n p a r a l l e l . A g i v e n customer e i t h e r g e t s s e r v e d i m m e d i a t e l y by one o f t h e t e l l e r s o r e l s e he f i r s t w a i t s i n some l i n e . The s u c c e s s i v e time spans marked o f f by the a r r i v a l o f the customer, h i s b e g i n n i n g o f s e r v i c e , and end o f s e r v i c e a re c a l l e d t h e w a i t i n g time and s e r v i c e t i m e . The method whereby a customer i s a s s i g n e d t o a g i v e n t e l l e r i s c a l l e d t h e s e r v i c e d i s c i p l i n e . F o r example, banks i n Vancouver, B.C. p r i o r t o 1974 had t h e f o l l o w i n g s e r v i c e d i s c i p l i n e : t h e r e were k s e p a r a t e queues, one i n f r o n t o f each t e l l e r , and a g i v e n customer would choose one o f the queues (presumably the s h o r t e s t ) i m m e d i a t e l y upon h i s a r r i v a l . The customer c o u l d a l s o l e a v e t h e bank w i t h o u t b e i n g s e r v e d ( t h i s i s c a l l e d " b a l k i n g " ) o r he c o u l d s w i t c h queues d u r i n g h i s w a i t i n g p e r i o d ("jockey- i n g " ) . D u r i n g 197 4 some Vancouver banks s w i t c h e d over t o the s i n g l e queue system w h e r e i n the p e r s o n i n f r o n t o f the queue would go t o t h e n e x t a v a i l a b l e t e l l e r . T h i s s e r v i c e d i s c i p l i n e i s c a l l e d " f i r s t - i n - f i r s t s e r v e d " ( F I F S ) . 2 Although most phenomena tha t occur i n r e a l - w o r l d queuing systems ( j o c k e y i n g , b a l k i n g , bulk a r r i v a l s , spe- c i a l i z e d s e r v e r s , etc.) have been considered and analysed i n the queuing l i t e r a t u r e , s u b s t a n t i a l a t t e n t i o n i s s t i l l being p a i d to the standard c l a s s i c a l model, which may be described as f o l l o w s : The s e r v i c e d i s c i p l i n e i s FIFS, w i t h no b a l k i n g , the i n t e r a r r i v a l times are independent, i d e n t i c a l l y d i s t r i b u t e d ( i . i . d . ) random v a r i a b l e s indepen- dent of the s e r v i c e times, which themselves are i . i . d . ran- dom v a r i a b l e s , and the k servers a l l work at the same r a t e , independent of the length of the queue. The behavior of t h i s system depends only on the d i s t r i b u t i o n f u n c t i o n of the s e r v i c e times, H(s), and t h a t of the i n t e r a r r i v a l times, G(t) . Of p a r t i c u l a r i n t e r e s t are the w a i t i n g times of cus- tomers, and indeed a good f i g u r e of merit f o r a queuing system i s the l i m i t i n g expected w a i t i n g time. In g e n e r a l , t h i s q u a n t i t y i s d i f f i c u l t to c a l c u l a t e , even f o r a s i n g l e server queue (k=l). M a r s h a l l [ l ] and Kingman [3~] have developed an upper bound f o r the expected w a i t i n g time i n a s i n g l e - s e r v e r queue i n terms of the means and variances of the s e r v i c e and i n t e r a r r i v a l times. For k ~? 1, the s i t - u a t i o n i s considerably more complicated. However, Brumelle f 2 j and Kingman f 3 j have succeeded i n e s t a b l i s h i n g upper bounds f o r the expected w a i t i n g time i n a k-server queue 3 by comparison to a j u d i c i o u s l y chosen s i n g l e - s e r v e r queue i n which the expected w a i t i n g time i s g r e a t e r . Brumelle's s i n g l e server queue was constructed from the k-server queue by a s s i g n i n g a l l a r r i v a l s i n the l a t t e r to the f i r s t s e r v e r , but g i v i n g those a r r i v a l s that would not have gone to the f i r s t server a zero s e r v i c e time. Under t h i s m o d i f i c a t i o n none of the w a i t i n g times i s decreased"*". Kingman, on the other hand, asserted t h a t the expec- ted w a i t i n g time i n a k-server queue cannot decrease i f the s e r v i c e d i s c i p l i n e i s changed from FIFS to one where the a r r i v a l s are assigned c y c l i c a l l y to the k s e r v e r s . (Thus the server would get the i ^ * \ ( i + k ) ^ , (i+2k) . . . a r r i v a l s . This creates k s t o c h a s t i c a l l y i d e n t i c a l s i n g l e - server queues). Since Kingman's bound i s a sharper one than Brumelle's, i t i s important t h a t Kingman's a s s e r t i o n be proved. In t h i s paper the case k=2 i s examined i n depth. We w i l l show tha t i ) the l i m i t i n g expected w a i t i n g time f o r the FIFS system i s l e s s than or equal to that f o r the c y c l i c system, however, Since the s i n g l e - s e r v e r queue thus generated does not have independent i n p u t , Brumelle had to extend Marshall's r e s u l t s . 4 i i ) there e x i s t r e a l i z a t i o n s where the average wait i s l a r g e r f o r the FIFS system, and i i i ) there e x i s t s e r v i c e time and i n t e r a r r i v a l time d i s t r i b u t i o n s f o r which the w a i t i n g times are not s t o c h a s t i c a l l y greater f o r the c y c l i c system. 5 I I . The Two Systems - D e f i n i t i o n s and Elementary Notions We consider a system of two p a r a l l e l servers each th working at u n i t r a t e . The i a r r i v i n g customer (denoted by ) has s e r v i c e time S^ and i n t e r a r r i v a l time T^ (taken to be the time between the a r r i v a l s of £T) and (̂ +3) ) • S^ and T^ are random v a r i a b l e s . We assume th a t the f i r s t customer f i n d s the system empty. I n i t i a l l y , no assumptions are made about the p r o b a b i l i t y 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 i s c a l l e d a r e a l i z a t i o n of the process i f S.=s.,T.=t. f o r a l l i 2 1. Under the FIFS system (hereafter denoted system I ) i s immediately served i f he f i n d s one of the servers i d l e ; otherwise he waits i n queue an amount of time Ŵ u n t i l the f i r s t time a server becomes fre e a f t e r ( i - l ) s t a r t s s e r v i c e . Although t h i s d e s c r i p t i o n suggests a s i n g l e queue of w a i t i n g customers, i t i s more convenient, as i n [2] , to consider each server to have h i s own queue, such t h a t a given customer immediately j o i n s the queue of t h a t server who e v e n t u a l l y serves him. I f we denote by the h y p o t h e t i c a l w a i t i n g time of i f he were to j o i n the other queue, then the p a i r of numbers of (W^,Q^) denotes the remaining work (at the i n s t a n t of 's a r r i v a l ) of the two r e s p e c t i v e s e r v e r s i f ( i - l ) were to be the l a s t customer granted s e r v i c e . These d e f i n i t i o n s y i e l d the f o l l o w i n g r e c u r s i o n r e l a t i o n s h i p s : W . + 1 = m i n f t w . + S . - T . ^ f Q . - T . T } Q i + 1 = max{ [ w . + S . - T ^ [QI-TJ 4 } where the [ ^ o p e r a t o r denotes the diode f u n c t i o n : (1) f x i O f x <0. A u s e f u l schematic a i d i n d e p i c t i n g the process i s shown i n F i g . 1, with the bars being " f e d " s p o r a d i c a l l y on the r i g h t by amounts and being "eaten away" from the l e f t a t a uniform r a t e . i i ^ © arrives T i Q a r r i v e s F i g . 1. Geometric D e p i c t i o n of Work Loads. 7 In the c y c l i c system (hereafter denoted system I I ) customer goes to the f i r s t server i f i i s odd, to the second i f 1 i s even. We define W. to be the current v i s i b l e 1 work of the server t h a t goes to at the time of h i s a r r i - v a l , the work of the other s e r v e r , and o b t a i n the f o l l o w - ing r e c u r s i o n r e l a t i o n s h i p s : W. , = T-T.~| + l + l I l iJ = {"w.+S.-T.l . L l l i J (2) Q. V i We note here b r i e f l y t h a t system I I i s , i n p r i n c i - p l e , simpler than system I , since i t can be reduced to a one-dimensional process by co n s i d e r i n g two-step r e c u r s i o n s 1+2 I W.+S.-T.-T. .,1 . (3) L I I I i + i J I t i s u s e f u l to define two more q u a n t i t i e s : T o t a l Work: L ± = Wi+Qi . Unevenness: = Q̂ ~Ŵ (and, s i m i l a r l y , and i n system I I ) . In comparing system I wit h system I I i t i s at f i r s t i n s t r u c t i v e to assign them the same r e a l i z a t i o n of *£(S^,T^), i = l , 2 , . . ^ and c a l c u l a t e the corresponding set of numbers 8 (V\L ,Q̂ ) and (W^Q^) f o r every i . For every r e a l i z a t i o n we have W,=W,=Wo=Wo=0 and the two systems run i d e n t i c a l l y and W.=b,Q.=a) i n system I I f o r some a,b where a<b. At t h i s p o i n t the two systems p a r t company wi t h system I gaining an immediate advantage i n w a i t i n g time but at the cost of an " i n f e r i o r " s t a t e f o r the next a r r i v a l . A "good" s t a t e , i n t u i t i v e l y , i s one w i t h a high amount of unevenness f o r a given amount of t o t a l work. However, very high unevenness may o c c a s i o n a l l y cause a server to become prematurely i d l e , which i s "bad" since then the t o t a l work i s not being reduced at maximum r a t e . I n t u i t i v e l y , i t i s c l e a r that system I I w i l l tend to have more imbalance i n the two queue lengths than system I and hence be more s u s c e p t i b l e to p a r t i a l server i d l e n e s s . This i m p l i e s more t o t a l work and th e r e f o r e longer w a i t i n g times. However, i t i s d i f f i c u l t to q u a n t i f y these statements f o r a formal proof. In f a c t , the proof presented i n s e c t i o n IV w i l l not be along t h i s l i n e of reasoning. u n t i l some a r r i v a l sees (W.=a,Q.=b) i n system I 9 I I I . The Two Systems - Some P a r t i a l R e s u l t s A. Comparison o f R e a l i z a t i o n s In t h i s s e c t i o n we view the S. and T. as g i v e n num- bers and ignore t h e i r p r o b a b i l i t y laws. No r e s t r i c t i o n s are p l a c e d on them other than t h e i r n o n - n e g a t i v i t y . We w i l l say t h a t an n-block v i o l a t i o n occurs s t a r t i n g a t (T) i f W. > 3> w. . . D r r i . and ask whether i t i s p o s s i b l e f o r an n-block v i o l a t i o n to occur s t a r t i n g a t (T) and, i f so, what i s the minimum such n. These q u e s t i o n s are answered as f o l l o w s (the groundwork and p r o o f s are presented i n Appendix A ) : Lemma JL: Suppose a r r i v a l (T) f i n d s the s t a t e t o be (a,b) i n system I and (b,a) i n system I I wit h a < b . Then an n-block v i o l a t i o n s t a r t i n g a t i s im p o s s i b l e f o r n=l,2,or 3. Since the c o n d i t i o n o f Lemma 1 can be f u l f i l l e d at the very e a r l i e s t a t i=3, i t i s c l e a r t h a t , s t a r t i n g a t (jî , 5-block v i o l a t i o n s cannot occur. However, 6-block v i o l a t i o n s are p o s s i b l e : Theorem 1: The minimum n necessary f o r an n-block v i o l a - . t i o n , s t a r t i n g a t (\) , i s 6. 1 0 L e t us f o r a moment c o n s i d e r the s e r v i c e and i n t e r - a r r i v a l times to be independent random v a r i a b l e s , so t h a t the i n s t a n c e s where an a r r i v a l f i n d s both system I and I I empty are renewal p o i n t s . With a very l i g h t t r a f f i c i n t e n s i t y ( E S / 2 E T « 1 ) the renewal p e r i o d s would encompass o n l y a few a r r i v a l s , which, by Theorem 1 , would tend to favour system I. We w i l l say t h a t a system becomes p a r t i a l l y i d l e i f , when one of the s e r v e r s f i n i s h e s the work of a customer, no new customer i s i n the queue to immediately take h i s p l a c e . A necessary c o n d i t i o n f o r a 6-block v i o l a t i o n i s t h a t system I becomes p a r t i a l l y i d l e b e f o r e (5) a r r i v e s . One may ask whether an n-block v i o l a t i o n (n — 7) i s p o s s i b l e i n which system I never becomes i d l e . The answer i s no: Theorem 2 : I f system I does not become p a r t i a l l y i d l e at any time a f t e r the a r r i v a l of , then an' n-block v i o l a t i o n , s t a r t i n g a t , cannot occur f o r any n. Thus system I i s c e r t a i n l y no worse than system I I i n a f u l l y congested system (no p a r t i a l i d l e n e s s ) . Suppose we have an n-block v i o l a t i o n f o r a g i v e n s e t of numbers ^ ( S ^ , T ^ ) , i = l , 2 , . . . , n ^ . L e t us take the n ordered numbers , S 2 # • . • • S ». permute them i n some way and compute 11 the new w a i t i n g times. For a permutation <5 i n A „ , the group of permutations of { l , . . , n ^ , l e t ,W® be the corresponding w a i t i n g times obtained as above. Consider the conjecture t h a t I f t h i s conjecture was true f o r a l l n and any set of , i t would f o l l o w that the expected wa i t i n system I i s l e s s than or equal t o tha t i n system I I provided t h a t the are independent and i d e n t i c a l l y d i s t r i b u t e d . U n f o r t u n a t e l y , the author has been able to prove t h i s conjecture only f o r the case of n=6. B. Comparison of D i s t r i b u t i o n Functions f o r Waiting Times and T o t a l Work In t h i s s e c t i o n , we make the usual assumptions about the ^(S^ ,T^) , ' i - 1 , 2 , . . ."̂  process, namely th a t the s e r v i c e times are i . i . d . w i t h d i s t r i b u t i o n f u n c t i o n H(s) and independent of the i n t e r a r r i v a l times which are a l s o i . i . d . w i t h d i s t r i b u t i o n f u n c t i o n G ( t ) . We def i n e the f o l l o w i n g two-variable d i s t r i b u t i o n f u n c t i o n s : 12 F i ( x 1 , x 2 ) = P [ W ± ^ x 1 , Q I < x2"] V x r x 2 ' = p [ W i - x i ' Q ± - x 2 ] The f o l l o w i n g r e c u r s i o n r e l a t i o n s h i p s can be d e r i v e d v i a a method given i n (see appendix B): Let U ( x 1 , x 2 ) be the two-dimensional u n i t - s t e p - f u n c t i o n : U ( x 1 , x 2 ) =1 [1 i f x x > 0 and x2"> 0 0 otherwise Then F - ^ x ^ x ^ = F ^ x ^ x ^ = \J(x^,x2) and, f o r i 2 1, ^ i + l ( K l , X 2 ) = u ( x 1 ' x 2 ) j J ^ i ( x 2 ~ S + t ' X l + t ) d H ( s ) d G ( t ) ( 4 ) ! U ( X 1 / X 2 ) | | F i (x 2-s+t,x 2+t)dH(s)dG(t) i f x 1 > x 2 (5) U ( x 1 , x 2 ) jj A i ( x 1 / x 2 , s , t ) d H ( s ) d G ( t ) i f x ^ X2 where A± ( x 1 , x 2 , s , t ) = F i (x 1-s+t.x 2+t)+F, i(x 2-s+t,x 1+t)-F^(x^-s*t:,x 1+t) I t i s shown i n |41 t h a t F.(x,,x„)2 F.,,(x,,x„) L J l 1 2 l + l 1 2 f o r every (x^,x 2) and every i , and t h a t F(x,,x„) = l i m F.(x,,x_) i-»oo ± ± & i s the s t e a d y - s t a t e d i s t r i b u t i o n f u n c t i o n p r o v i d e d t h a t ES<2ET. 13 A s i m i l a r statement may be made f o r system I I . We c o n s i d e r the f o l l o w i n g s e r i e s o f c o n j e c t u r e s (an omitted s u b s c r i p t i n d i c a t e s s t e a d y - s t a t e c o n d i t i o n s ) : A. EWrSEW B. EW.^ EW. f o r a l l i 1 1 C. F(x,<*>)-F(x,oo) f o r a l l x D. (x,oo ) > F.('x, oo ) f o r a l l i , a l l x E. F^ (x.^ ,x 2) > F^ (x^ ,x 2) f o r O^x-^x,, and a l l i . (Note t h a t E=7>D=$>C^A and B=^A.) When i n v e s t i g a t i n g these c o n j e c t u r e s , the author a t f i r s t thought i t p o s s i b l e t o prove c o n j e c t u r e E v i a the r e c u r - s i o n r e l a t i o n s h i p s (4) and (5). However, i t i s not t r u e f o r every p o s s i b l e p a i r of p r o b a b i l i t y d i s t r i b u t i o n s H(s) and G ( t ) . In f a c t , a counterexample can even be produced f o r c o n j e c t u r e C. T h i s i s shown i n appendix B. A random v a r i a b l e X i s s a i d t o be s t o c h a s t i c a l l y l a r g e r than another random v a r i a b l e Y i f , f o r every z, we have p[x:> z ĵ ~Z P [ Y > z j . The f a c t t h a t c o n j e c t u r e C does not h o l d f o r every H(s) and G(t) means t h a t W i s not n e c e s s a r i l y s t o c h a s t i c a l l y l a r g e r than W. The author does b e l i e v e t h a t L i s s t o c h a s t i c a l l y l a r g e r than L. However, as i n d i c a t e d i n appendix B, the r e c u r s i o n r e l a t i o n s h i p s i n v o l v i n g P [ " U L < x^ ,L^:£ x^] are not n e a r l y as simple as those f o r V\L and Q^. Moreover, the non- monotonic behavior of the unevenness q u a n t i t y , a l l u d e d t o i n S e c t i o n II and f u r t h e r i l l u s t r a t e d i n appendix B, makes i t d i f f i c u l t to generate a s u i t a b l e i n d u c t i o n statement i n v o l v i n g the t h . Consequently, the q u e s t i o n whether L i s s t o c h a s t i c a l l y l a r g e r than L i s l e f t as an unsolved problem. 15 IV. Proof o f EW ̂  EW v i a Value F u n c t i o n s As i n s e c t i o n I I , we c o n s i d e r each s e r v e r to have h i s own queue, but assume a t f i r s t some g e n e r a l but f i x e d p o l i c y o f a s s i g n i n g a r r i v a l s to s e r v e r s . We a l s o drop the assumption of an empty system when (T) a r r i v e s . Observing t h i s s t o c h a s t i c p rocess o n l y a t the a r r i v a l epochs, we may e x t r a c t the f o l l o w i n g d i s c r e t e - p a r a m e t e r , t w o - v a r i a b l e continuous s t a t e s t o c h a s t i c p r o c e s s : | z i - ( X i , Y i ) , i = l , 2 , . . . | Z - ^ ^ y ) ^ where = work t h a t ( i ) sees i n f r o n t of t h a t s e r v e r to whom (j^~3^ was assigned, = work t h a t sees i n f r o n t of the other s e r v e r . 1 Under a s t a t i o n a r y p o l i c y the d e c i s i o n t o a s s i g n (\) to a s p e c i f i c s e r v e r depends o n l y on the s t a t e Z^ of the process and not on the p r e v i o u s h i s t o r y . For example, both system I (FIFS) and system I I ( c y c l i c ) c o n s t i t u t e s t a t i o n a r y p o l i c i e s . We note t h a t i f , i n a d d i t i o n t o a s t a t i o n a r y p o l i c y , we a l s o have i . i . d . s e r v i c e times and i . i . d . i n t e r a r r i v a l times, then ^Z^, i=l,2,..."^ i s a Markov Process. I f we leave the p o l i c y open t o c h o i c e and s p e c i f y some c o s t s t r u c t u r e , we have a Markov D e c i s i o n Process. However, i n the f o l l o w i n g e x p o s i t i o n we w i l l not assume t h a t the 1 T h i s i s a s l i g h t change i n order from the s t a t e d e f i n i - t i o n o f S e c t i o n I I I A. 16 i n t e r a r r i v a l t i m e s a r e i . i . d . , a n d c o n s e q u e n t l y t h e r e s u l t i n g p r o c e s s may n o t be M a r k o v . N e v e r t h e l e s s , we w i l l b o r r o w f r o m M a r k o v D e c i s i o n P r o c e s s t h e o r y t h e c o n c e p t o f i m m e d i a t e c o s t and s t a t e v a l u e f u n c t i o n s . We r e s t r i c t o u r a t t e n t i o n now %e-ft©w t o two p o l i c i e s : F I F S and c y c l i c a s s i g n m e n t . We t a k e a s i m m e d i a t e c o s t t h e a c t u a l w a i t i n g t i m e and c o n s i d e r t h e c r i t e r i o n o f t o t a l e x p e c t e d c o s t o v e r a f i n i t e h o r i z o n . The f o l l o w i n g c o n d i t i o n s on t h e { ( S ^ ,T.) , i = l , 2 , . . !} p r o c e s s w i l l be s u f f i c i e n t t o p r o v e s y s t e m I t o be b e t t e r t h a n s y s t e m I I : C-̂ ) { T i \ i s a n Y a r b i t r a r y s e q u e n c e o f n o n - n e g a t i v e random v a r i a b l e s . C 2 ) {s^iis an i . i . d . s e q u e n c e o f n o n - n e g a t i v e random v a r i a b l e s i n d e p e n d e n t o f { T ^ . , F o r c o n v e n i e n c e , we d e n o t e by ^ t h e p o r t i o n o f E u c l i d e a n n - s p a c e i n w h i c h e v e r y c o o r d i n a t e i s n o n - n e g a t i v e . A g i v e n r e a l i z a t i o n o f t h e f i r s t n i n t e r a r r i v a l t i m e s t = ( t ^ , t 2 , . . . , t n ) a n d t h e f i r s t n s e r v i c e t i m e s s = ( s ^ , s 2 , . . . , s n ) c a n t h u s be v i e w e d a s p o i n t s i n ^ and t h e s e q u e n c e o f random v a r i a b l e s T= (T^T.^. . . . ,T ) and S= ( S 1 , S 2 , . . . ,S n) as random v e c t o r s i n l f ^ ^ . 17 We d e f i n e the f o l l o w i n g value f u n c t i o n s f o r k i n : V k ( x , y , t , s ) = ^ (W±| Z^Ury) ,T=t,S=s) (6) L-l V. k(x,y,t) = E s V k ( x , y , t , S ) (7) V. k(x,y) = E T V k(x,y,T) (8) where Ŵ  i s the w a i t i n g time of i n system I... Corresponding d e f i n i t i o n s f o r system I I are made u s i n g the symbol. R e f e r r i n g back to S e c t i o n I I I A, we see t h a t V"n (x,y, t,s_) i s an. n-block sum of w a i t i n g times f o r a gi v e n r e a l i z a t i o n s t a r t - i n g with the s t a t e (x,y). We note t h a t V n(x,y,t,s)=V n(y,x,t,s_) and a l s o t h a t by Lemma 1 V n ( x , y , t , s ) < V n(x,y,t,£) f o r n=l,2, or 3. (9) We w i l l prove t h a t V n ( x , y , t ) < V n ( x , y , t ) (10) f o r any (x,y) € 7R + ) a n Y Ji 6 1R+' a n c i a n Y p o s i t i v e i n t e g e r n. I t i s c l e a r t h a t i f (10) holds then so does V n ( x , y ) < V n ( x , y ) . (11) I f , i n a d d i t i o n , i ) {T^} i s an i . i . d . sequence, and i i ) ES<2ET, then the steady s t a t e w a i t i n g times EW and EW e x i s t and are give n by EW = l i m 1 V (x,y) r\-90o n n EW = l i m 1 V (x,y) (see, f o r i n s t a n c e , Ross [5^) n-*>oo n Thus (10) i s a s t r o n g e r statement than EW < EW. To prove (10), some p r o p e r t i e s of the va l u e f u n c t i o n s are f i r s t e s t a b l i s h e d v i a the f o l l o w i n g lemmas: Lemma 2: V n(x,y,t,s_) i s a non-decreasing f u n c t i o n i n x and y. T h i s i s e a s i l y proved by i n d u c t i o n u s i n g the r e c u r - s i o n r e l a t i o n s h i p : V n ( x , y , t , s ) = x+V n_ 1 ( [ y - t j + , [ x + s 1 - t ] ] , t,£) (12) where t = ( t 2 , t 3 , . . . , t ) € I R ^ 1 and £ = ( s 2 , s 3 , . . . . ,s n) € 1f^n+1. . C o r o l l a r y : V n ( x , y , t ) i s a non-decreasing f u n c t i o n i n x and y. Lemma 3: V n ( x 1 , y 1 , t , s ) + V n ( x 2 , y 2 , t , s ) = V n ( x 1 , y 2 , t , s ) + V n ( x 2 , y 1 , t , s ) f o r any x1,Y1,x2,y2,t,s. 19 Proof: T h i s can be seen i n t u i t i v e l y by c o n s i d e r i n g two c y c l i c queuing systems with d i f f e r e n t i n i t i a l work loads but i d e n t i c a l f u t u r e a r r i v a l s and exchanging t h e i r second s e r v e r s . F o r m a l l y , we proceed by i n d u c t i o n : n=l: Each s i d e i s equal to x-̂ +x,,. We assume the statement f o r i=l,2,...,n-1 and use r e l a t i o n - s h i p (12) : V n ( x 1 , y 1 , t , s ) + V n ( x 2 , y 2 , t , s ) = X l + V - l ( L " Y l _ t J + > [ x i + s i - t i " ] + 't/|) + X2 + " n - l ( [ y 2 - t l T , [ x 2 + S l - t J + ' ^ i ) = x 2 + V i f f y i - t J * [ x 2 + S l - t J + , A t , i ) + X l + V l ( ( Y 2 - t l T ; [ V S l - ^ r ' t r s ) = V ( x 2 , y l f t , s ) + V n ( x 1 , y 2 , t , s ) . C o r o l l a r y : V ^ x ^ y ^ t ) + V n ( x 2 , y 2 , t ) = v n ( x 1 ' Y 2 ' i ) + v n ( x 2 ' Y l ' - ) Lemma 4: L e t (a-^a,,) and (b^,b 2) be s t a t e s g i v e n by a l = [ x + s _ t l _ t 2 l + a 2 = [ [ y - h T ^ - ^ T b i = I y ^ - v ^ ] * b 2 = [ [ x - t i r + s - t 2 ] + where O f x < y , s 2 0, t^Z 0, t 2 2 0. Then a^< a^ and e i t h e r A: a ^ i b 2 and a 2=b 1 or B: a^-£ b^ and a 2=b 2 . Proof: 1) a > [" y - t , + s - t 2 J + > a, (using PLUS 1 and PLUS 3 from appendix A) 2) i f t ^ y then a 2 = b l a n d b 2 ~ a l ^ b y P L U S l f P L U S 3^ which i s case A. I f t^> y then a 2=b 2 and a^< h± (by PLUS 3) which i s case B. The f o l l o w i n g lemma w i l l be e s s e n t i a l i n the f i n a l p r o of o f (10): Lemma 5: L e t c o n d i t i o n s and h o l d f o r the a r r i v a l and service p rocesses and l e t x,y be numbers s a t i s f y i n g O^x-^y. Then V ^ x . y . t ) < V n ( y , x , t ) f o r any t € ]R ̂  and any p o s i t i v e i n t e g e r n. Proof: By i n d u c t i o n . For n=l, V 1 ( x , y , t ) F x < y '= (y,x,t) . 21 For n=2, ~ 2 ( x , y , t ) = x + [y-tj + V 2 ( y , x , t ) = y + The d e s i r e d i n e q u a l i t y f o l l o w s from PLUS 4. Now assume i n d u c t i o n hypothesis f o r i=l,2,...,n-1. I f the present s t a t e i s (x, y ) , then the next two w a i t i n g times w i l l be x and [ y - T - J ] + . and the f u t u r e s t a t e (two steps from now) w i l l be [ x + S i - T i - T 2 ] + ; [ f r - T j * + S 2 - T 2 ] Y ( Hence, V n ( x , y , t ) = x + [ V t 1 f + s^V2 ( [ x + S i - t ' ^ t ^ f t y - t J - f S ^ t J , t) A n _ 2 (13) where t = ( t 3 , . . . , t ) e jf^ + . Denoting by A(x,y,t) the l a s t term of (13), we have V n ( x , y , t ) = x + [y-t 1"] ++ A(x,y,t) V n ( y , x , t ) = y + [ x - t 1 J + + A(y,x,t) We show tha t A (x,y, t) < A (y,x, t) . By d e f i n i t i o n , A(x,y,t) = j j v n _ 2 ( [ x + s 1 - t 1 - t 2 ] + ) f [ y - t 1 ] + + s 2 - t 2 ^ + , t ) d H ( s 1 ) d H ( s 2 ) . [ ( s 1 , s 2 ) :s 12 0 , s 2 r o] 22 D i v i d i n g the r e g i o n o f i n t e g r a t i o n , we have A ( x , y , t ) = | | v n _ 2 ( [ x + s 2 - t 1 - t 2 ] * f [ y - t 1 ] + + s 2 - t J + , t ) d H ( S ; L ) d H ( s 2 ) [ ( s 1 7 s 2 ) :s 1=s 2> o] + J [ J [ v n _ 2 < [ x + s i - V t ^ r [ y - t i T + s 2 - t 2 T - ^ ) ^ [ ( s 1 , s 2 ) :0 £ s 1 < s2~} ^ n _ 2 ( [ x + s 2 - t 1 - t 2 " ] + , [ [ y - t 1 ] + + s 1 - t 2 ] + /t)] d H ( S l ) d H ( s 2 ) . +v F i n a l l y , employing the c o r o l l a r y to Lemma 3: A(x,y,t) = j J \ _ 2 ( [ x + S 2 ~ t l " t 2 ' ] " t * ' [ t Y ~ t J + + S 2 " t 2 ] + ' ̂  d H ( s l } d H ( s 2 ) [ ( B 1 # S 2 ) : S l = s 2 2 0] + f [ ^ n - 2 ( [ x + s l " t l " t 2 " ] + ' [ [ y - t l T * + S l " t 2 T + » i ) d H ( s 1 ) d H ( s 2 ) [{sirs2) :0S s 1 < s 2"] + J | v n _ 2 ( [ x + s 2 - t l - t 2 ] + , [ [ y - t l ] 1 " + s 2 - t 2 ] + , t ) d H ( S l ) d H ( s 2 ) [ ( s l f s 2 ) : 0 £ s 1 < s 2 ] The corresponding integrands of A(x,y,t) can be shown to be l e s s than or equal t o those of A ( y , x , t ) . For example, the r e s p e c t i v e f i r s t i n t egrands a re: "n-2 ( C x + s 2 " t r t 2 l + ' [ [ Y _ t J* + S 2 _ 1 J t) = V n _ 2 ( a 1 , a 2 , t ) and V n - 2 ( L y + s 2 - t r t 2 i ' U ^ l J + s 2 - t 2 J = V n - 2 ( b l ' b 2 ' ^ where a^,a 2,b^, and b 2 are as i n Lemma 4 (with s = s 2 ) . For case A ( i n Lemma 4), we have V 2 ( a r a 2 f | ) < V 2 ( a 2 , a r t ) < V 2 ( b ^ b ^ f ) where the f i r s t i n e q u a l i t y f o l l o w s from the i n d u c t i o n hypo- t h e s i s and the second from Lemma 2. For case B Vn-2 ( a i ' a 2 ' i i ) - v n _ 2 , b2'—^ b Y L e m m a 2- Ap p l y i n g s i m i l a r arguments t o the other i n t e g r a n d s complete the proof of the lemma. We are now ready to prove a s s e r t i o n "(10) : Theorem 3: Suppose the a r r i v a l process | ( S ^ , T ^ ) , i - 1 , 2 . . . ^ obeys c o n d i t i o n s C^,C 2. Then f o r every i n i t i a l s t a t e (x,y) 2 n £ { R + f every t €. 1R + » and every p o s i t i v e i n t e g e r n, we have V n ( x , y , t ) < V n(x,yt-t) . Proof: By i n d u c t i o n . For n=l, V^(x,y,t) = min(x,y) and ' v i ( x , y , t ) = x I f x £ y, then by i n d u c t i v e h y p othesis 24 V n ( x , y , t ) = V n ( x , y , t ) I f y < x then but T h i s completes the pro o f . C o r o l l a r y : Under the standard assumptions of queuing theory ( i . e . i s an i . i . d . sequence, independent of { T ^ , a l s o i . i . d . , E S < 2 E T ) , E W £ E W . Proof: V i a standard d e f i n i t i o n s a n d ' l i m i t theorems (see Ross [ 5 " ] , chapter 5 ) / 1 4 - V EW = l i m E j _ <2 ÎW. ) independent of i n i t i a l c o n d i t i o n s . n*oo \ n l =, *-J By d e f i n i t i o n (8) The d e s i r e d r e s u l t f o l l o w s from Theorem 3. 25 BIBLIOGRAPHY 1. K. T. M a r s h a l l , "Some I n e q u a l i t i e s i n Queuing", Operations Research V o l . 16, 651-665 (1968). 2. S. L. Brumelle, "Some I n e q u a l i t i e s f o r P a r a l l e l - Server Queues", Operations Research V o l . 19, No. 2, 402-413 (1971). 3. J.F.C. Kingman, " I n e q u a l i t i e s i n the Theory of Queues", J . Royal S t a t . S o c , S e r i e s B, V o l . 32, 102-110 (1970). 4. J . K i e f e r and J . Wolfowitz, "On the Theory o f Queues wit h Many S e r v e r s " , Trans. American Math. S o c , V o l . 78, 1-18 (1955). 5. S.M. Ross, " A p p l i e d P r o b a b i l i t y Models w i t h O p t i m i z a t i o n A p p l i c a t i o n s " , Chapter 5,Holden-Day (1970) APPENDIX A: Pr o o f s of R e a l i z a t i o n Theorems I n i t i a l Note: I t i s p o s s i b l e t o prove Theorem 1 d i r e c t l y by u s i n g the r e c u r s i o n r e l a t i o n s h i p s (1) and (2) and con- s i d e r i n g the cases h=3,4,5. For n=3, we have i W i = 0 + 0 + W3 = n t i n l f s ^ - T ^ ^ S ^ T ^ ] I f f . = 0 + 0 •+ W 3 = [ S ^ T ^ T J * The case n=4 i s a l r e a d y long and t e d i o u s . E s s e n t i a l l y , i t i n v o l v e s a case by case e x p l o r a t i o n of 4 d i f f e r e n t s i t u a t i o n s c o r r e s p o n d i n g to the number of ways a r r i v a l s and j o i n the queues i n system I. D i r e c t proof of n=5 was not even attempted s i n c e i t not only i n v o l v e s a d o u b l i n g of the number of s i t u a t i o n s over n=4, but a l s o the i n d i v i d u a l comparisons are more complica- t e d . Lemma 1 avoids these problems. I t i s expedient to f i r s t l i s t some of the p r o p e r t i e s of the £ J + o p e r a t i o n : PLUS 1: [ x 3 + 2 x PLUS 2: I f y 2 0 then QA J* -y]*= J A - y ] * PLUS 3: I f A < B then [ A - x ] + * [ B - X ] + 27 PLUS 4: I f A<B and x 2 0 , then f A ] + + [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 t h a t ^ W. < ^ W*. f o r 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 i J ~- r -i+ W. + W.,, = b + a-T.J l l + l «• i J The d e s i r e d i n e q u a l i t y f o l l o w s from PLUS 4. , 0 = fb+S.-T.-T.^,~| + 1+2 L i i 1+lJ n=3 W W i + 2 * [ b - T i - T i + i l + i f © g ° e s t o same s e r v e r as (iy • i n system I. W. 1+2 < j"a+S .-T .-T .+/1 i f (i~+l) goes to the *• i i i J other s e r v e r . In any case we have W i + 2 < W i + 2 bY P L U S 3- T h i s y i e l d s the d e s i r e d i n e q u a l i t y when combined with the r e s u l t f o r n-2. Proof of Theorem 1: Without l o s s of g e n e r a l i t y we may assume t h a t i f a r r i v a l f i n d s W^=Q^ i n system I he goes to the s e r v e r t h a t ( 1 - d i d not go t o . With t h i s convention system I and I I e x h i b i t i d e n t i c a l behavior ( i n c l u d i n g i d e n t i c a l w a i t i n g times) u n t i l an a r r i v a l (J^J sees i n system I I . At t h i s p o i n t we must have VI.-Q. and Q. =w'. , e s t a b l i s h i n g the £- 1 1 1 1 c o n d i t i o n of Lemma 1. The lowest i f o r which t h i s can hap pen i s i=3. So 5-block v i o l a t i o n s , s t a r t i n g a t , are i m p o s s i b l e . To complete the proof we must show t h a t 6-block v i o l a t i o n s can occur. We do t h i s by e x h i b i t i n g an example i S . l T . l W. l Q i w. 1 Q i 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 — T 6 F i g . 2: P i c t o r i a l R e p r e s e n t a t i o n of Counterexample. s, arrive. her* I ft© arriire heme •I <2> arrives here Proof of Theorem 2: We w i l l prove a str o n g e r r e s u l t : W. + W.,, < W. + W. , , f o r any i . 1 l + l l l + l JL To show t h i s , we note t h a t s i n c e system I i s never p a r t i a l l y i d l e ( a f t e r ), the t o t a l work i n I can never be g r e a t e r than t h a t i n I I . 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. (sin c e no i d l e n e s s occurs) l + l - L i i J i i SOW. + W.,< W. + L. - W. - T. = L . - T . . l l + l 1 1 1 1 1 1 30 In system I I , we have Q. = L. + H. - W. 1 1 X 1 and W i + 1 = [ Q i - T j + 2 5 ± - T ± (by PLUS 1) so t h a t 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: D i s t r i b u t i o n F u n ctions f o r Wai t i n g Times and T o t a l Work 1. Waiting Times In K i e f e r and Wolfowitz [ 4 j r e c u r s i o n r e l a t i o n - s h i p s f o r the k- s e r v e r queue are e s t a b l i s h e d v i a the ^ - s e t . In accordance with the terminology of our problem, we d e f i n e M'-set as f o l l o w s : H> ( X l , x 2 , s , t ) = | ( y 1 , y 2 ) : [ w i=y 1,Q i=y 2,S i=s,T i=t)] With t h i s d e f i n i t i o n , we have F i + 1 ( x 1 , x 2 ) = j J P [ ( W i ' Q i ) 6 4'(x1,x2,s,t)J dH(s)dG(t) A t y p i c a l 4* - s e t i s shown F i g . 3. 2 t y. 32 The r e c t a n g l e s formed by the two axes and the p o i n t s A and B (as shown) i n t e r s e c t e d with the r e g i o n above the l i n e v2 = Y;L determine the a c t u a l - s e t . Using the i n c l u s i o n - e x c l u s i o n p r i n c i p l e and n o t i n g t h a t there i s no p r o b a b i l i t y mass below the Y2=Y± x i n e / w e 9 e t p [ ( W i , Q i ) £ <y ( X ; L , x 2 , s , t ) ] =F i (x-^s+t ,x 2+t) + E\ (x 2-s+t ,x 1+t) - F i ( X l - s + t / X ; L + t ) . I f x ^ x 2 then ^ ( x 1 ,x 2 , s , t) = ( x 2 , x 2 , s , t ) . T h i s e s t a b l i s h e s equation (5), The corresponding d e f i n i t i o n may be used f o r system I I ( r e p l a c i n g and by and Q^); here the r e s u l t i n g ^ (x.^ , x 2 , s , t) s e t i s a complete r e c t a n g l e w i t h the upper r i g h t v e r t e x a t (x 2~s+t,x^+t). Hence P^W^Q^e ^ ( x ^ x ^ S j t j ] = F± (x 2~s+t thereby e s t a b l i s h i n g equation (4). 2. Counterexample t o c o n j e c t u r e C Let H(s) and G(t) be such t h a t Pr s..=s] = ( 1 / 2 5 = 2 L 1 J < 1/2 s=4 0 otherwise 33 99/100 t = l P [ T i = t J = ^ 1 / 1 0 0 t = A ( l a r g e ) 0 o t h e r w i s e W i t h t h i s a r r i v a l p r o c e s s b o t h system I and system I I cannot become p a r t i a l l y i d l e u n t i l f o r some i t h e event [ T ^ = A " J t a k e s p l a c e . We p i c k A so l a r g e t h a t the p r o b a b i l i t y t h a t one o f the two systems w i l l n o t empty out c o m p l e t e l y a t t h a t time i s n e g l i g i b l e . Thus, u n t i l ^T^=A * J happens f o r some i , t h e t o t a l work i n system I and I I grows c o n t i n u a l l y and e q u a l l y , w i t h system I I t e n d i n g t o be more u n b a l a n c e d , so t h a t i t w i l l t e n d t o have b o t h s h o r t and l o n g w a i t i n g times ( r e l a t i v e t o system I ) . For example P [w6.= 0 | T ± = l , i = l , . . . ,5^ =3/16 ^ F 6 (0,oo ) ; whi l e P [w 6=0 | T i = l , i = l , . . ,5 J =1/4 = F 6 ( 0,.oo) # Thus t h e d i s t r i b u t i o n f u n c t i o n s f o r the W. and l W. v a r i a b l e s (F.(x,.oo) and F. (x,oo)) s h o u l d i n t e r s e c t I l I f o r s u f f i c i e n t l y h i g h v a l u e s o f i . S i n c e we have a ren e w a l p r o c e s s here ( w i t h t h e event T^=A i n i t i a t i n g a ren e w a l p e r i o d ) , t h e i n t e r s e c t i n g b e h a v i o r o f F^(x,oo) and F\(X,OO) s h o u l d c a r r y o ver t o the s t e a d y - s t a t e d i s - t r i b u t i o n f u n c t i o n s F(x,oo) and F(x,oo ) . 3. Recursion R e l a t i o n s h i p s I n v o l v i n g Work and Unevenness With and d e f i n e d as i n s e c t i o n ' I I and l e t t i n g K i ( x l ' X 2 > = P [ U . * x ^ L . S T x j ; we have K i + 1 ( x 1 ' x 2 ) = [ \ v [ ( U i ' L i > e ^ ( x i ' x2 ' s ' t ) ] d H ( s ) d G ( f c ) where Y ( x ] _ , x 2 f S , t ) = | ( Y 1 f Y 2 ) : [" Ui=Yi ' L i = Y 2 ' S i = s ' T i = ^ [ = ^ [ U i + l * x l ' L i + l £ x 2 ] ] . A t y p i c a l ^ -set' i s shown i n F i g . 4. F i g . 4.'Mr-set f o r (U,L) . Shaded area = T ( 5 , 1 0 , 7 , 9 ) 35 The v e r t i c e s A-E are a l l f u n c t i o n s of x ^ , X 2 , s , t . I t i s c l e a r t h a t the term P J ( U ^ , L ^ ) 6 'VjT (x^ ,x 2 , s , t) J cannot be expressed d i r e c t l y i n terms of K.(,) as was the case f o r (W^,Q^). Rather such an expression would have to take the form of a double i n t e g r a l w i t h very complicated l i m i t s . A f u r t h e r p o t e n t i a l problem i n proving K^(oo,x) 2 K\(<x>,x) i s tha t t h i s statement i s i n i t s e l f an i n s u f f i c i e n t i n d u c t i o n hypothesis: we would need a stronger statement such as K. ( x ^ x ^ l ? K. ( x ^ X j ) to insure t h a t the i n d u c t i o n step goes through. However, the l a s t hypothesis cannot be true s i n c e U. can be negative w h i l e U. cannot be. A l ^ I workable replacement i s hard to f i n d because f u n c t i o n s i n v o l v i n g the unevenness q u a n t i t y tend t o be non-monotonic. As an example consider the f o l l o w i n g f u n c t i o n : f(.x,y)=E [ < E I + 1 - L I + 1 ) | S r . = L . = A , U . = x F U . = y J ' . ' . l l l l J J This i s the expected d i f f e r e n c e i n the next s t a t e work given t h a t the present work i s equal but w i t h system I and I I having unevenness x and y, r e s p e c t i v e l y . The non- monotonic behavior i n x and y can be demonstrated even f o r the M/M/2 queue, w i t h 36 H(s) = 1 - e -s/3 G(t) = 1 ,"t/2 T h i s i s shown i n F i g . 5, which i s a sketch o f the s i g n of f ( x , y ) . - 5 • + - T + 4 + + + + +-+ + + 5 x F i g . 5. An Example of the Non-Monotonic Behavior o f U: Regions where f(x,y) i s p o s i t i v e and nega- t i v e (M/M/2,A=5)

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
China 4 9
Japan 2 0
Turkey 1 0
United States 1 4
City Views Downloads
Beijing 4 0
Tokyo 2 0
Ankara 1 0
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}

Share

Share to:

Comment

Related Items