UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

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

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.

Item Metadata

Download

Media
831-UBC_1975_A6_7 P05.pdf [ 1.94MB ]
Metadata
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
831-1.0079362-fulltext.txt
Citation
831-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 W^  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^ ~W^  (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 (ji^ , 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 j^ ~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 W^  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 I^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:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

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"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            data-media="{[{embed.selectedMedia}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0079362/manifest

Comment

Related Items