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.

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., P o l y t e c h n i c I n s t i t u t e o f B r o o k l y n , 1965  A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n t h e Department of MATHEMATICS and t h e INSTITUTE OF APPLIED MATHEMATICS AND STATISTICS We a c c e p t t h i s t h e s i s as c o n f o r m i n g t o t h e required standard.  THE UNIVERSITY OF BRITISH COLUMBIA August, 1975  In p r e s e n t i n g t h i s  thesis  an advanced degree at  further  for  of  the  requirements  freely  available  for  t h a t p e r m i s s i o n for e x t e n s i v e copying o f  representatives.  this  thesis for  It  financial  The  of  gain s h a l l not  Mathematics  U n i v e r s i t y of B r i t i s h Columbia  2075 W e s b r o o k P l a c e V a n c o u v e r , Canada V6T 1WS  Date  August  31.  1975  that  this  thesis or  i s understood that copying or p u b l i c a t i o n  written permission.  Department  for  r e f e r e n c e and study.  s c h o l a r l y purposes may be granted by the Head of my Department  by h i s of  agree  fulfilment  the U n i v e r s i t y of B r i t i s h Columbia, I agree  the L i b r a r y s h a l l make it I  in p a r t i a l  be allowed without my 1  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 a r e 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 o r d e r . W e . w i l l prove t h a t under t h e FIFS system the expected w a i t i s s h o r t e r g i v e n r a t h e r weak c o n d i t i o n s on t h e a r r i v a l p r o c e s s . Howe v e r , t h e w a i t i s n o t 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 t h e average w a i t 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 t h e upper l i m i t s on expected w a i t i n a G/G/k queue g i v e n by B r u m e l l e and Kingman.  iii  TABLE OF CONTENTS Page Abstract Table List  i i  of Contents  i i i  of Figures  Acknowledgement  iv v  Text: I.  I n t r o d u c t i o n and Summary  1  II.  The Two Systems - D e f i n i t i o n s and Elementary Notions  5  III.  The Two Systems - Some P a r t i a l Results  9  A.  Comparison o f R e a l i z a t i o n s  9  B.  Comparison o f D i s t r i b u t i o n F u n c t i o n s f o r W a i t i n g Times and T o t a l Work  11  IV.  P r o o f o f EW < EW v i a V a l u e Functions  Bibliography  15  25  A p p e n d i x A:  Proofs of Realization Theorems  26  A p p e n d i x B:  Distribution Functions f o r W a i t i n g T i m e s and T o t a l Work  31  iv  L I S T OF  FIGURES Page  Fig.  1. G e o m e t r i c D e p i c t i o n o f Work L o a d s  6  Fig.  2. P i c t o r i a l R e p r e s e n t a t i o n Counterexample  Fig.  3.  Fig.  4. Y " - S e t f o r (U,L)  34  Fig.  5. An Example o f t h e N o n - M o n o t o n i c Behavior of U  36  of  Vf» - s e t f o r (W,Q)  29  31  V  ACKNOWLEDGEMENT  This Brumelle  w o r k was done u n d e r of the University  the  author  i sgrateful  for  his patient  problem appeared  the supervison  of British  for this  t o be  Columbia,  interesting  encouragement d u r i n g  o f S. L .  periods  problem and when t h e  intractable.  Reinhard  t o whom  Piater  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 q u e u i n g system i s t h e s e r -  v i c i n g o f c u s t o m e r s a t a bank.  Customers a r r i v e a t t h e  bank a c c o r d i n g t o some p r o b a b i l i t y l e r s working served  i n parallel.  immediately  and  There a r e k  A g i v e n customer e i t h e r  The s u c c e s s i v e t i m e  tel-  gets  b y one o f t h e t e l l e r s o r e l s e he  w a i t s i n some l i n e . by  law.  first  spans marked o f f  the a r r i v a l o f the customer, h i s beginning  of service,  end o f s e r v i c e a r e 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  time.  The m e t h o d w h e r e b y a c u s t o m e r i s a s s i g n e d  teller  i s called the service d i s c i p l i n e .  to a given  F o r example,  b a n k s i n V a n c o u v e r , B.C. p r i o r t o 1974 h a d t h e f o l l o w i n g service discipline:  t h e r e were k s e p a r a t e  f r o n t o f each t e l l e r , one  o f t h e queues  upon h i s a r r i v a l . without  being  q u e u e s , one i n  and a g i v e n customer would  (presumably t h e s h o r t e s t )  During  immediately  The c u s t o m e r c o u l d a l s o l e a v e t h e bank  served  (this i s called  " 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 ing").  choose  ("jockey-  197 4 some V a n c o u v e r b a n k s s w i t c h e d  over t o  t h e s i n g l e queue s y s t e m w h e r e i n t h e p e r s o n i n f r o n t o f t h e queue w o u l d 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 . discipline  i s called  "first-in-first  served"  This service (FIFS).  2  A l t h o u g h most phenomena t h a t o c c u r 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 , b u l k a r r i v a l s , c i a l i z e d s e r v e r s , e t c . ) have been c o n s i d e r e d  and  speanalysed  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 b e i n g p a i d t o the s t a n d a r d  c l a s s i c a l model, which may  described  service discipline  as f o l l o w s :  The  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 t i m e s are  be  i s FIFS,  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 independent of the s e r v i c e t i m e s , which themselves are i . i . d . dom  v a r i a b l e s , and  ran-  the k s e r v e r s a l l work a t the same r a t e ,  independent of the l e n g t h of the queue.  The  b e h a v i o r of  t h i s system depends o n l y 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 t i m e s , 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 t i m e s of c u s tomers, and  i n d e e d a good f i g u r e of m e r i t f o r a queuing  system i s the l i m i t i n g e x p e c t e d w a i t i n g time.  In  general,  t h i s q u a n t i t y i s d i f f i c u l t t o c a l c u l a t e , even f o r a s i n g l e s e r v e r queue ( k = l ) .  M a r s h a l l [ l ] and Kingman [3~] have  developed an upper bound f o r the e x p e c t e d 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 o f the means and of the s e r v i c e and  i n t e r a r r i v a l times.  u a t i o n i s c o n s i d e r a b l y more c o m p l i c a t e d .  variances  For k ~? 1, the  sit-  However, B r u m e l l e  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 - s e r v e r  queue  3  by comparison t o 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 t h e e x p e c t e d 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 s e r v e r queue was c o n s t r u c t e d from the k - s e r v e r 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 t o the f i r s t  server,  but g i v i n g those a r r i v a l s t h a t would not have gone t o the f i r s t s e r v e r 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 o t h e r hand, a s s e r t e d t h a t the expected  w a i t i n g time i n a k - s e r v e r queue cannot d e c r e a s e 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 t o one where the a r r i v a l s are a s s i g n e d c y c l i c a l l y t o the k s e r v e r s .  (Thus  the  .. .  s e r v e r would get the i ^ * \  arrivals.  (i+k)^,  (i+2k)  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 e r v e r queues).  single-  S i n c e Kingman's bound i s a s h a r p e r one  than B r u m e l l e ' s , i t i s i m p o r t a n t t h a t Kingman's a s s e r t i o n be proved. In We w i l l i)  t h i s paper t h e case k=2  i s examined i n d e p t h .  show t h a t the l i m i t i n g e x p e c t e d w a i t i n g time f o r the FIFS system i s l e s s than o r e q u a l t o t h a t f o r the c y c l i c system, however,  S i n c e the s i n g l e - s e r v e r queue thus g e n e r a t e d does not have independent i n p u t , B r u m e l l e had t o extend M a r s h a l l ' s results.  4  ii)  t h e r e e x i s t r e a l i z a t i o n s where the average w a i t is larger  iii)  f o r the FIFS system, and  t h e r e 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 t i m e s a r e not s t o c h a s t i c a l l y g r e a t e r f o r the c y c l i c  system.  5  II.  The Two Systems - D e f i n i t i o n s and Elementary  Notions  We c o n s i d e r a system o f two p a r a l l e l s e r v e r s each th working a t u n i t r a t e . by  The i  a r r i v i n g customer  (denoted  ) 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 t o be t h e time between t h e a r r i v a l s o f £T) and (^+3) ) •  S^ and T^ a r e random v a r i a b l e s .  the f i r s t customer no assumptions ing  We assume t h a t  f i n d s t h e system empty.  a r e made about t h e p r o b a b i l i t y law govern-  t h e p r o c e s s *£(S^,T^), i = l , 2 , . .  numbers *£(s^, t^)  . , A given set of  : 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 o f t h e p r o c e s s i f S.=s.,T.=t. Under t h e FIFS system I ) i s  Initially,  (hereafter  f o r a l l i 2 1. denoted  system  i m m e d i a t e l y s e r v e d i f he f i n d s one o f t h e s e r v e r s  i d l e ; o t h e r w i s e he w a i t s i n queue an amount o f time  W^  u n t i l t h e f i r s t time a s e r v e r becomes f r e e a f t e r ( i - l ) starts service.  A l t h o u g h t h i s d e s c r i p t i o n suggests a  s i n g l e queue o f w a i t i n g customers, i t i s more c o n v e n i e n t , as i n [2] , t o c o n s i d e r each s e r v e r t o have h i s own queue, such t h a t a g i v e n customer  i m m e d i a t e l y j o i n s t h e queue  of  t h a t s e r v e r who e v e n t u a l l y s e r v e s him.  by  t h e h y p o t h e t i c a l w a i t i n g time o f  I f we  denote  i f he were t o  j o i n t h e o t h e r queue, t h e n t h e p a i r o f numbers o f (W^,Q^) denotes t h e r e m a i n i n g work ( a t t h e i n s t a n t o f  's  arrival) be  o f t h e two r e s p e c t i v e  the l a s t  yield  customer g r a n t e d  the following  W.  + 1  =  s e r v e r s i f ( i - l ) were t o  service.  recursion  These d e f i n i t i o n s  relationships:  minftw.+S.-T.^fQ.-T.T} (1)  i 1  Q  +  = max{ [ w . + S . - T ^  where t h e [ ^ o p e r a t o r d e n o t e s  [QI-TJ 4 } the diode  function:  f x i O f x A useful  schematic  <0.  aid i n depicting  i n F i g . 1, w i t h t h e b a r s b e i n g r i g h t by amounts at a uniform  and b e i n g  the process  i s shown  "fed" sporadically " e a t e n away" f r o m  on t h e  the l e f t  rate.  Q  F i g . 1. G e o m e t r i c D e p i c t i o n o f Work Loads.  Ti i i ^ © arrives  arrives  7 In t h e c y c l i c system ( h e r e a f t e r denoted system I I ) customer  goes t o t h e f i r s t s e r v e r i f i i s odd, t o t h e  second i f 1 i s even.  We d e f i n e W. t o be t h e c u r r e n t  visible  1  work o f t h e s e r v e r t h a t val, ing  goes t o a t t h e time o f h i s a r r i -  t h e work o f t h e o t h e r s e r v e r , and o b t a i n t h e f o l l o w recursion relationships: W. , = T-T.~| l+l I l iJ  +  (2) Q. V i  = {"w.+S.-T.l . L l l iJ  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 ple,  s i m p l e r t h a n system I , s i n c e i t can be reduced t o a  o n e - d i m e n s i o n a l p r o c e s s by c o 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 . L  I  I  I  (3)  i+iJ  I t i s u s e f u l t o d e f i n e two more q u a n t i t i e s : T o t a l Work:  L  ±  Unevenness: (and, s i m i l a r l y ,  = W +Q . i  i  = Q^~W^ and  i n system I I ) .  In comparing system I w i t h system I I i t i s a t f i r s t i n s t r u c t i v e t o a s s i g n them t h e same r e a l i z a t i o n o f *£(S^,T^), i=l,2,..^  and c a l c u l a t e t h e c o r r e s p o n d i n g s e t o f numbers  8  (V\L ,Q^)  and (W^Q^) f o r every i .  F o r every  realization  we have W,=W,=W =W =0 and t h e two systems r u n i d e n t i c a l l y o  o  sees (W.=a,Q.=b) i n system I  u n t i l some a r r i v a l  and W.=b,Q.=a) i n system I I f o r some a,b where a < b . A t t h i s p o i n t t h e two systems p a r t company w i t h system I g a i n i n g an immediate advantage i n w a i t i n g time b u t a t t h e c o s t o f an " i n f e r i o r " s t a t e f o r t h e 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 h i g h amount o f unevenness f o r a g i v e n amount o f t o t a l work.  However,  v e r y h i g h unevenness may o c c a s i o n a l l y cause a s e r v e r t o become p r e m a t u r e l y  i d l e , which i s "bad"  t o t a l work i s n o t b e i n g reduced Intuitively,  s i n c e then t h e  a t maximum r a t e .  i t i s c l e a r t h a t system I I w i l l  to have more imbalance  tend  i n t h e two queue l e n g t h s than  system I and hence be more s u s c e p t i b l e t o p a r t i a l s e r v e r idleness.  T h i s i m p l i e s more t o t a l work and t h e r e f o r e  longer w a i t i n g times. these statements  However, i t i s d i f f i c u l t t o q u a n t i f y  f o r a formal proof.  In fact,  the proof  p r e s e n t e d i n s e c t i o n IV w i l l n o t be a l o n g t h i s l i n e o f reasoning.  9  III.  The Two Systems - Some P a r t i a l A. In  bers  Comparison o f R e a l i z a t i o n s this  s e c t i o n we v i e w t h e S. and T. a s g i v e n num-  and i g n o r e t h e i r  probability  a r e p l a c e d on them o t h e r t h a n will  Results  s a y t h a t an n - b l o c k  laws.  their  violation  No  restrictions  non-negativity. occurs  starting  We a t (T)  if W. .  and to  .  >  3>  rr  D  w.  i.  a s k w h e t h e r i t i s p o s s i b l e f o r an n - b l o c k occur  such  n.  starting  a t (T) and, i f s o , what i s t h e minimum  These q u e s t i o n s a r e answered as f o l l o w s ( t h e  groundwork a n d p r o o f s a r e p r e s e n t e d Lemma JL: in  Suppose a r r i v a l  (T)  finds  i n Appendix A ) : the state  s y s t e m I and (b,a) i n s y s t e m I I w i t h  n-block  violation  violation  starting  at  a<b.  t o be (a,b) Then an  i s impossible f o r  n = l , 2 , o r 3. S i n c e t h e c o n d i t i o n o f Lemma 1 c a n be f u l f i l l e d a t the v e r y e a r l i e s t a t i=3,  i t i s clear  5-block  occur.  are  violations  cannot  that, starting  However, 6 - b l o c k  at  (ji^,  violations  possible:  Theorem 1:  The minimum n n e c e s s a r y tion,  starting  f o r an n - b l o c k  a t (\) , i s 6.  viola- .  10  Let arrival the  us  f o r a moment c o n s i d e r  t i m e s t o be  the s e r v i c e  i n d e p e n d e n t random v a r i a b l e s ,  i n s t a n c e s where an a r r i v a l  finds  empty a r e r e n e w a l p o i n t s . W i t h  both system  a very l i g h t  ( E S / 2 E T « 1 ) the renewal p e r i o d s would few  arrivals,  system  which,  interso  that  I and  traffic  intensity  encompass o n l y  by Theorem 1 , w o u l d  II  a  tend to favour  I.  We when one new  and  will  say t h a t  a s y s t e m becomes p a r t i a l l y  of the servers  customer  finishes  I becomes p a r t i a l l y  ask w h e t h e r system  f o r a 6-block v i o l a t i o n  an n - b l o c k v i o l a t i o n  I f system at  any  an'  Thus s y s t e m  time a f t e r  f o r any  o f numbers  The  no  i s possible  the a r r i v a l  may  i n which  of  starting  idle , then  at  , cannot  n.  no w o r s e t h a n s y s t e m  (no p a r t i a l  i=l,2,...,n^.  , S2 # • . •• S  One  answer i s no:  II i n  idleness).  have an n - b l o c k v i o l a t i o n  ^(S^,T^),  i s that  arrives.  n o t become p a r t i a l l y  I i s certainly  congested system  Suppose we  numbers  I does  (n — 7)  n-block v i o l a t i o n ,  occur  a fully  b e f o r e (5)  idle  I n e v e r becomes i d l e .  Theorem 2 :  t h e work o f a c u s t o m e r ,  i s i n t h e queue t o i m m e d i a t e l y t a k e h i s p l a c e .  A necessary condition system  idle i f ,  f o r a given set  L e t us t a k e t h e n o r d e r e d  ». p e r m u t e them i n some way  and  compute  11  the new w a i t i n g t i m e s .  F o r a p e r m u t a t i o n <5 i n A „ , t h e  group o f p e r m u t a t i o n s o f { l , . . , n ^ , l e t corresponding the c o n j e c t u r e  w a i t i n g times obtained  ,W®  as above.  be t h e Consider  that  I f t h i s c o n j e c t u r e was t r u e f o r a l l n and any s e t o f  ,  i t would f o l l o w t h a t t h e expected w a i t i n system I i s l e s s than o r e q u a l t o t h a t i n system I I p r o v i d e d 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 .  that the Unfortunately,  the a u t h o r has been a b l e t o prove t h i s c o n j e c t u r e o n l y f o r the case o f n=6.  B.  Comparison o f D i s t r i b u t i o n  Functions  for Waiting  Times and T o t a l Work In t h i s s e c t i o n , we make t h e u s u a l assumptions about the ^ ( S ^ ,T^) , ' i - 1 , 2 , . . ."^ p r o c e s s , namely t h a t t h e s e r v i c e times a r e 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 o f t h e i n t e r a r r i v a l t i m e s which a r e a l s o with d i s t r i b u t i o n  function G(t).  two-variable d i s t r i b u t i o n  i.i.d.  We d e f i n e t h e f o l l o w i n g  functions:  12  F (x ,x ) i  1  Vxr The  = P [ W  2  x  2  '  =  p  W  following  a method g i v e n i n  Let  U ( x , x ) be  , Q  x "]  <  I  2  x  x  recursion  relationships  (see a p p e n d i x  the two-dimensional  2  [1 i f x  x  > 0 and  c a n be  derived  B):  unit-step-function:  x ">  0  2  =1  U(x ,x ) 1  1  [ i- i'Q±- 2]  via  1  ^ x  ±  2  0 otherwise Then F - ^ x ^ x ^ and,  ^i+l  = F ^ x ^ x ^  =  \J(x^,x ) 2  f o r i 2 1,  (  K  l  ,  X  2  )  =  u  (x1'x2)jJ^i  ( x  U(X1/X2)||F  i  2~  S + t  ' l X  + t ) d H ( s ) d G ( t )  ( 4 )  (x -s+t,x +t)dH(s)dG(t) i f x > 2  2  x  1  2  (5) ! U ( x , x ) jj A ( x 1  2  i  1 /  x ,s,t)dH(s)dG(t) 2  i f  x ^  X  2  where A  ±  (x ,x ,s,t) 1  2  It  = F  i  (x -s+t.x +t)+F, (x -s+t,x +t)-F^(x^-s*t:,x +t) 1  2  every  (x^,x ) 2  F(x,,x„) is  2  1  1  i s shown i n |41  t h a t F . ( x , , x „ ) 2 F.,,(x,,x„) l 1 2 l+l 1 2 e v e r y i , and t h a t L  for  i  and  = lim i-»oo  J  F.(x,,x_) ±  ±  &  the s t e a d y - s t a t e d i s t r i b u t i o n  function provided that  ES<2ET.  13  A s i m i l a r s t a t e m e n t may be made f o r s y s t e m I I . We c o n s i d e r (an  omitted  the following  subscript  indicates  series of conjectures  steady-state  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 )  E.  F ^ (x.^ , x ) > F ^ (x^ , x ) 2  (Note t h a t  f o ra l l i , a l l x  2  E=7>D=$>C^A  conditions):  f o r O ^ x - ^ x , , and a l l i .  and  B=^A.)  When i n v e s t i g a t i n g t h e s e c o n j e c t u r e s , first sion  thought  relationships  every p o s s i b l e In C.  i t possible  t o prove c o n j e c t u r e E v i a the r e c u r -  (4) and ( 5 ) .  However,  i t i s not true f o r  p a i r o f 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 ) .  f a c t , a counterexample This  the author a t  i s shown  c a n e v e n be p r o d u c e d  i n a p p e n d i x 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  t h a n a n o t h e r random v a r i a b l e  p[x:> z^j ~Z  f o r conjecture  P [ Y  > zj.  Y i f , f o r every  z, we h a v e  larger  The  fact  and  G ( t ) means t h a t  larger  that  than  nearly  a u t h o r does b e l i e v e  than L.  recursion  W i s not necessarily  relationships  stochastically  L i s stochastically  involving  i n appendix  P["UL<  f o r V\L and Q^.  Section  I I and f u r t h e r  it  difficult  illustrated  to generate a s u i t a b l e  the t h . Consequently,  stochastically  larger  B, t h e  x^ ,L^:£ x^] a r e n o t Moreover,  b e h a v i o r o f t h e unevenness q u a n t i t y ,  in  involving  that  However, as i n d i c a t e d  as s i m p l e as t h o s e  monotonic  f o r e v e r y H(s)  W.  The larger  c o n j e c t u r e C does n o t h o l d  alluded to  i n appendix  induction  t h e non-  B, makes  statement  t h e q u e s t i o n whether L i s  than L i s l e f t  as an u n s o l v e d  problem.  15  IV.  P r o o f o f EW ^ EW v i a V a l u e As i n s e c t i o n  his  I I , we c o n s i d e r  own queue, b u t assume a t f i r s t  policy  of assigning  arrivals  a s s u m p t i o n o f an empty this  stochastic  extract  state  i  where  i  = work t h a t  was  server  arrives.  a t the a r r i v a l  have i . i . d .  sees i n f r o n t o f t h e o t h e r p o l i c y the decision  depends o n l y  on t h e s t a t e  i f , i n addition service  times, then ^Z^, i=l,2,..."^  in  1  server.  to assign  1  (\)  Z^ o f t h e  constitute  to a stationary  t i m e s and i . i . d .  exposition  we w i l l  i s a s l i g h t change i n o r d e r o f S e c t i o n I I I A.  policy,  interarrival  i s a Markov P r o c e s s .  we have a Markov D e c i s i o n  the following  This tion  to  F o r example,  l e a v e t h e p o l i c y open t o c h o i c e and s p e c i f y structure,  server  policies.  We n o t e t h a t we a l s o  e p o c h s , we may  two-variable  s y s t e m I (FIFS) and s y s t e m I I ( c y c l i c )  stationary  Observing  process:  p r o c e s s and n o t on t h e p r e v i o u s h i s t o r y . both  drop the  assigned,  Under a s t a t i o n a r y a specific  We a l s o  ( i ) sees i n f r o n t o f t h a t  (j^~3^  = work t h a t  to servers.  i=l,2,... | Z - ^ ^ y ) ^  i  whom  t o have  some g e n e r a l b u t f i x e d  discrete-parameter,  stochastic  |z -(X ,Y ),  each s e r v e r  s y s t e m when (T)  process only  the following  continuous  to  Functions  some  Process.  I f we cost  However,  n o t assume t h a t t h e  from t h e s t a t e  defini-  16  interarrival p r o c e s s may  times  are  n o t be  i.i.d.,  Markov.  Markov D e c i s i o n Process and  state  value  We FIFS  and  cyclic  expected on  the  prove  theory the  our  attention  time  and a  T  i \ i  sa n  {s^iis  2  an  Euclidean A  Y  n-space  can  thus  n  be  and  viewed  random v a r i a b l e s random v e c t o r s  of  resulting  borrow  immediate  as  than  from cost  of  to  non-negative  independent by  {T^.,  of  ^ the p o r t i o n  coordinate i s  first  n  points i n  conditions  non-  every  n  the  total  sufficient  sequence of  denote  first  cost  system I I :  sequence of  we  policies:  following  be  i.i.d.  T= ( T ^ T . ^ . . . . ,T inlf^^.  The  variables.  of the the  criterion  random  i n which  given realization 2  will  immediate  process w i l l  arbitrary  convenience,  (t^,t ,...,t )  the  %e-ft©w t o t w o  t a k e as  random v a r i a b l e s For  now  horizon.  better  negative C )  We  finite  I t o be  {  concept  c o n s i d e r the  { ( S ^ ,T.) , i = l , 2 , . . !}  C-^)  N e v e r t h e l e s s , we  assignment.  cost over  system  consequently  functions.  restrict  actual waiting  and  non-negative.  interarrival  service  times  ^  the  and  ) and  times  t=  s=(s^,s ,...,s ) 2  sequence  S= ( S , S 1  of  2  n  of  , . . . ,S ) n  as  17  We d e f i n e  the following value  V (x,y,t,s)  =  k  V. (x,y,t) = E k  V. (x,y) = E k  Referring  (7)  k  V (x,y,T)  T  (8)  k  time o f  i n s y s t e m I... C o r r e s p o n d i n g  f o r s y s t e m I I a r e made u s i n g  the state  and  t h a t by Lemma 1  times f o r a given We n o t e t h a t  V ( x , y , t , s ) < V (x,y,t,£)  n  f o r n = l , 2 , o r 3.  n  any (x,y) € i s clear that  n  7R )  a  +  n  Y  Ji  6  1R+'  a n c i  a n  Y  ii)  (9)  p o s i t i v e i n t e g e r n.  i f (10) h o l d s t h e n s o does (11)  n  i n addition, i)  n  (10)  n  V (x,y) < V (x,y). If,  start-  that  n  It  realization  V (x,y,t,s)=V (y,x,t,s_)  V (x,y,t)< V (x,y,t)  for  symbol. n  (x,y).  n  the  I I I A, we s e e t h a t V" (x,y, t,s_) i s  sum o f w a i t i n g  prove  (6)  V (x,y,t,S)  s  ing with  We w i l l  for k i n :  ,T=t,S=s)  ±  back t o S e c t i o n  an. n - b l o c k  also  (W | Z^Ury)  ^ L-l  where W^ i s t h e w a i t i n g definitions  functions  {T^} i s an i . i . d . ES<2ET,  s e q u e n c e , and  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 a r e  g i v e n by EW = l i m 1 V (x,y) r\-90o  n  n  EW = l i m 1 V n-*>oo n Thus  first  e s t a b l i s h e d v i athe following V (x,y,t,s_)  This  EW.  lemmas:  i s a non-decreasing  n  in  function  x and y .  i s easily  proved  by i n d u c t i o n u s i n g t h e r e c u r -  relationship: V (x,y,t,s)  = x+V _  n  where t =  and  t h a n EW <  ( 1 0 ) , some p r o p e r t i e s o f t h e v a l u e f u n c t i o n s  Lemma 2:  sion  ( s e e , f o r i n s t a n c e , Ross [5^)  (10) i s a s t r o n g e r s t a t e m e n t To p r o v e  are  (x,y)  £ =  ( [ y - t j , [ x + s - t ] , t,£) +  n  1  1  3  1f^ n + 1 .  (s ,s ,.. . . ,s ) € 2  3  n  .Corollary:  V (x,y,t) n  in  Lemma 3:  i s a non-decreasing  x and y .  V (x ,y ,t,s) n  1  1  +  = V (x ,y ,t,s) n  for  any  1  2  x ,Y ,x ,y ,t,s. 1  (12)  IR^1  (t ,t , . . . ,t )€ 2  ]  1  2  2  V (x ,y ,t,s) n  +  2  2  V (x ,y ,t,s) n  2  1  function  19  Proof: cyclic but  T h i s c a n be s e e n queuing  future arrivals  Each s i d e  by  work  loads  their  second  induction:  i s e q u a l t o x-^+x,,.  assume t h e s t a t e m e n t  ship  initial  and e x c h a n g i n g  F o r m a l l y , we p r o c e e d  n=l: We  by c o n s i d e r i n g two  systems w i t h d i f f e r e n t  identical  servers.  intuitively  f o r i=l,2,...,n-1  and u s e  relation-  (12) : V (x ,y ,t,s) n  1  =  X  +  X  =  x  +  +  2  +  Corollary:  (  l  V l  +  (  (  (x ,y 2  [  =  2  =  b  i  =  2  t  2  J > [ i +  [ y 2 -  Y  2 -  t  l T  t  x  l T , [  x  +  s  _  t  l  _  [x  i - i " ] 't/|)  + s  t  x  +  S  2  =  +  S  l  where O f x < y ,  x  -  t  ' ^ i )  +  -tJ , t,i) A  [ V S l - ^ r 'trs)  ;  n  t  1  + V (x ,y ,t) n  and  2 l  2  i r  +  s  2  =  v n  (  ( b ^ , b ) be s t a t e s 2  +  -  .  2  y ^ - v ^ ] * [ [  J  t  +  2  [ [ y - h T ^ - ^ T I  l -  +  t,s) + V (x ,y ,t,s)  l f  V^x^y^t)  a  b  _  2  V i f f y i - t J *  L e t (a-^a,,)  a  n  Y  " n - l  l  = V  Lemma 4:  (  +  2  V (x ,y ,t,s)  V-l L" l  l  X  +  1  t 2  ]  +  s 2 0, t ^ Z 0, t 2 0. 2  x 1  ' Y ' i  )  2  g i v e n by  +  v  ( n  x  2 '  Y  l ' -  )  Then a^< a^ and e i t h e r  A: a ^ i b  and  2  a =b 2  1  or  B: a^-£ b ^ and a = b .  Proof:  1) a >  2  [ " y - t , + s - t J > a,  2  =  b  l  which  If  a  n  d  then  b  2~  a  i s case  l  ^  b y  P  L  U  S  l  f  P  L  U  S  3  ^  A.  t^> y then  a =b 2  2  which  The  ( u s i n g PLUS 1 and PLUS 3 f r o m a p p e n d i x A)  +  2  2) i f t ^ y  a  2  and a^< h  (by PLUS 3)  ±  i s case  following  B.  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 o f o f (10): Lemma 5:  Let conditions  and  h o l d f o r t h e a r r i v a l and  s e r v i c e p r o c e s s e s and l e t x , y be numbers s a t i s f y i n g Then  V^x.y.t) <  for  n  any t € ]R ^ and any p o s i t i v e  Proof:  For  V (y,x,t)  By  integer  induction.  n=l, V (x,y,t) 1  F x<y  '=  (y,x,t) .  n.  O^x-^y.  21  For n=2, ~ ( x , y , t ) = x + [y-tj  +  2  V (y,x,t)  = y +  2  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.  assume i n d u c t i o n h y p o t h e s i s present  f o r i=l,2,...,n-1.  Now  I f the  s t a t e i s ( x , y ) , then t h e n e x t two w a i t i n g t i m e s  be x and [ y  -  T  will  and t h e f u t u r e s t a t e (two s t e p s from now)  -J] . +  w i l l be (  [  x + S i  -  T i  -T ]  [fr-Tj*  +  2  ;  + S -T ]Y 2  2  Hence, V (x,y,t) n  = x + [ V t f + s^V 1  ( [ x + S i - t ' ^ t ^ f t y - t J - f S ^ t J , t)  2  A _ where t = ( t , . . . , t ) e jf^ n  3  D e n o t i n g by A ( x , y , t )  2  (13)  .  +  t h e l a s t term o f (13), we have  V (x,y,t)  = x + [y-t "] +  A(x,y,t)  V (y,x,t)  = y + [x-t J +  A(y,x,t)  n  n  +  1  +  1  We show t h a t A (x,y, t) < A (y,x, t) . By  definition,  A(x,y,t)  =  jjv _ ( [x+s -t -t ] f[y-t ] +s -t ^ ,t)dH(s )dH(s ) . +  n  2  1  1  2  [ ( s , s ) : s 2 0 , s r o] 1  2  1  2  +  )  1  +  2  2  1  2  22  Dividing  t h e 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 _ ([x+s -t -t ]*f[y-t ] +s -t  J ,t)dH(  +  n  2  2  1  2  1  +  2  S ; L  )dH(s ) 2  [ ( s 1 7 s 2 ) : s = s > o] 1  +  2  J[J[v _2<[  x  +  s  n  i-V ^r[y- iT+s -t T-^)^ t  t  2  2  [ ( s , s ) :0 £ s < s2~} 1  2  1  +v^ _ ( [ x + s - t - t 2 " ] + , [ [ y - t ] + s - t ] +  n  2  2  Finally,  employing  A(x,y,t)  = jJ\_2 [ 1  #  S  x + S  :  )  2  S l  + f[^ -2 [  1  (  2~ l" 2']" *'[t ~ J t  /t)] d H (  +  2  t  t  Y  t  + + S  2" 2] t  '^  +  d  x + s  l" l" 2"] '[[ t  t  +  y - t  lT*  1  + S  l  l" 2T t  1  2  x  +  2  1  2  2  "  t  r  n-2 L (  y  +  s  t  2 l  2- r 2i t  dH(  2  t  2  )  2  S l  )dH(s )  c a n be shown t o be F o r example, t h e  integrands are:  +  ' [ [  Y  _  t  J*  ' U ^ l J  where a ^ , a , b ^ , and b 2  H( s  1  +  S  2  _  1  J  t) =  V _ (a ,a ,t) n  2  1  2  and V  } d  2  integrands of A(x,y,t)  first  s  l  »i)dH(s )dH(s )  +  +  l  than o r equal t o those o f A ( y , x , t ) .  "n-2 ( C  s  s ) :0£ s < s ]  l f  corresponding  respective  (  2  +  less  H  :0S s < s "]  2  The  2  2  + J | v n _ 2 ( [x+s -t -t ] ,[[y-t ] "+s -t ] ,t) [(s  )dH(s ).  S l  = s 2 0]  n  [{sirs2)  1  t h e c o r o l l a r y t o Lemma 3:  (  [ ( B  1  2  + s  2-  t 2  J  =  V  n-2  ( b  l' 2'^  a r e a s i n Lemma 4 ( w i t h  b  s=s ). 2  2  For V  2  case A ( a  r  a  2  ( i n Lemma 4 ) , we have  | ) <  f  V  where t h e f i r s t thesis For  V  2  ( a  , a  2  r  t )  inequality  and t h e s e c o n d  <  V  2  (b^b^f)  f o l l o w s from t h e i n d u c t i o n  hypo-  f r o m Lemma 2.  case B  n-2 ( i ' 2 ' i i ) a  Applying  a  v  similar  n  _2  , b  2'—^  b  Y  L  e  m  m  a  2  -  arguments t o t h e o t h e r i n t e g r a n d s  complete  t h e p r o o f o f t h e lemma. We a r e now r e a d y Theorem 3:  Suppose t h e a r r i v a l  obeys c o n d i t i o n s C^,C . 2  £  t o prove  assertion  process |(S^,T^),i-1,2...^  Then f o r e v e r y  2 n { R f e v e r y t €. 1R » and e v e r y p o s i t i v e +  +  have V ( x , y , t ) < V (x,yt-t) . n  Proof: For  n  By i n d u c t i o n .  n = l , V ^ ( x , y , t ) = min(x,y) and 'v (x,y,t) i  = x  I f x £ y , t h e n by i n d u c t i v e  "(10) :  hypothesis  initial  s t a t e (x,y)  i n t e g e r n, we  24  V (x,y,t) n  = V (x,y,t) n  If  y < x then  but  T h i s completes Corollary:  the  proof.  Under t h e s t a n d a r d a s s u m p t i o n s  (i.e.  i s an i . i . d .  sequence,  i.i.d.,  ES<2ET),  Proof:  V i a standard d e f i n i t i o n s  Ross [ 5 " ]  independent of { T ^  EW£EW. and'limit  V  4-  = l i m E j _ 2^ W. ) i n d e p e n d e n t o f i n i t i a l n*oo \n , *-J <  I  l=  By d e f i n i t i o n  The  , also  theorems  (see  , c h a p t e r 5) /1  EW  of queuing theory  desired  (8)  result  follows  f r o m Theorem  3.  conditions.  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 Q u e u i n g " , O p e r a t i o n s R e s e a r c h V o l . 16, 651-665 ( 1 9 6 8 ) .  2.  S. L . B r u m e l l e , "Some I n e q u a l i t i e s f o r P a r a l l e l S e r v e r Queues", O p e r a t i o n s R e s e a r c h V o l . 19, No. 2, 402-413 ( 1 9 7 1 ) .  3.  J . F . C . Kingman, " I n e q u a l i t i e s i n t h e T h e o r y o f Queues", J . R o y a l S t a t . S o c , S e r i e s B, V o l . 32, 102-110 ( 1 9 7 0 ) .  4.  J . K i e f e r a n d J . W o l f o w i t z , "On t h e T h e o r y o f Queues w i t h Many S e r v e r s " , T r a n s . A m e r i c a n Math. S o c , V o l . 78, 1-18 (1955).  5.  S.M. R o s s , " A p p l i e d P r o b a b i l i t y M o d e l s 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 " , C h a p t e r 5,Holden-Day (1970)  APPENDIX A:  Initial  Proofs of Realization  Note:  I t i s possible  by u s i n g t h e r e c u r s i o n sidering  the cases  F o r n=3,  we i  W  and Direct  Theorem  (1)  1  and (2)  directly and c o n -  h=3,4,5.  3  = 0  The c a s e n=4  situations  relationships  = 0 + 0 + W  i  involves  t o prove  have  Iff.  it  Theorems  +  0 •+ W  3  =  n t i n l f s ^ - T ^ ^ S ^ T ^ ]  =  [ S ^ T ^ T J *  i s a l r e a d y l o n g and t e d i o u s . a c a s e by c a s e e x p l o r a t i o n  Essentially,  of 4  different  c o r r e s p o n d i n g t o t h e number o f ways join  t h e queues  p r o o f o f n=5  arrivals  i n system I .  was n o t e v e n a t t e m p t e d  since  i t not  only  involves  a d o u b l i n g o f t h e number o f s i t u a t i o n s  n=4,  but also  the i n d i v i d u a l  ted. It  Lemma 1 a v o i d s t h e s e  i s expedient to f i r s t  the £ J  +  comparisons  list  some o f t h e p r o p e r t i e s o f  PLUS 1:  [x3 2 x  PLUS 2:  I f y 2 0 t h e n Q A J * -y]*= J A - y ] *  PLUS 3:  I f A < B then  +  +  [B-X]+  a r e more c o m p l i c a -  problems.  operation:  [A-x] *  over  27  PLUS 4:  I f A<B  then  [B-XJ + < [ B ] + + [ A - X ] +  fA] + +  Proof  and x 2 0 ,  #  o f Lemma 1:  We have W.=a, l  Q.=b, l  We must show t h a t  n=l  W. l  n=2  W.  = a  <b  Q. -a, l  W.=b, l  ^  W. <  ^  a < b.  W*.  f o r n=l,2,3,  = W*. l  = m i n l f a + S . - T . ] ^ [b-TJ"} < [b-T.]"  +1  So W. + W. , < a + f b - T . T * " l  lL + l  i  u  r  ~-  W. l  -i+  + W.,, = b + a-T.J l+l «• i J  The  desired  inequality follows  n=3  W  , 1+2  = fb+S.-T.-T.^,~| L i i 1+lJ  Wi+  0  2  J  f r o m PLUS 4.  +  *  < W. 1+2  [  b  -  T  i -  T  i + i l  +  j"a+S .-T .-T . + /1 *• i i i J  © g ° same s e r v e r a s (iy • i n system I. i  f  e  s  t  o  i f (i~+l) goes t o t h e other server.  In  any  the  c a s e we  desired  have W  <  i + 2  inequality  W  i 2  b  +  Y  P  L  U  S  3  -  This  when c o m b i n e d w i t h  the  yields result  for  n-2.  Proof of  Theorem  Without arrival that  loss  finds not  ( 1 - d i d  II e x h i b i t  pen  generality  W^=Q^ go  of  i s i=3.  we  may  s y s t e m I he  i n  assume t h a t  goes t o  to. With t h i s c o n v e n t i o n  a r r i v a l (J^J  (including  sees  the  if  server  system I  identical  and  waiting  i n system I I .  At  must have VI.-Q. and 1 1 Q. 1=w'. 1 , e s t a b l i s h i n g  p£-o i n t we  condition  of  i d e n t i c a l behavior  t i m e s ) u n t i l an this  1:  Lemma 1. So  The  the  l o w e s t i f o r which t h i s can  5-block v i o l a t i o n s ,  starting  at  ,  hap are  impossible. To violations  complete the can  occur.  p r o o f we We  do  must show t h a t  t h i s by w.  exhibiting  i  S. l  T. l  W. l  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  Q  i  i  Q  1  3  6-block an  example  » k — T  F i g . 2: P i c t o r i a l Representation of Counterexample.  6  s,  •I I  ft©  arrive. her*  <2>  arriire heme  arrives here  P r o o f o f Theorem 2: We w i l l  prove a stronger  W. + W.,, < W. + W. , , 1 l+l l l+l To show t h i s , partially be g r e a t e r  idle  f o r any i . JL  we n o t e t h a t  (after  than t h a t  result:  since  ), the t o t a l  system  I i s never  work i n I c a n n e v e r  in II.  Thus we have L. = L. + k . I l l  (A.2 O ) . I  Now, n. = L. - W. ' * i i I and W. , < r Q . - T . ~ l + = Q--T. l+l- L i iJ i i SOW. l  + W.,< l+l  ( s i n c e no i d l e n e s s  W. + L. - W. - T. = L . - T . . 1 1 1 1 1 1  occurs)  30  In system  I I , we  have Q.  = L. + H.  1  and W  i+1  =[Q -Tj  so t h a t W. i which  +  i  2  + W. L , Z l+l  completes  the  5  ±  1  - T  ±  X  -  W.  1  (by PLUS  1)  W. + L. + A . - W. - T. = L. + A . - T. , l l l l l l l l > proof.  31  APPENDIX B:  Distribution Times  1.  ships  Work  and W o l f o w i t z [ 4 j r e c u r s i o n  relation-  f o r t h e k - s e r v e r queue a r e e s t a b l i s h e d  -set.  v i a the  ^  In accordance w i t h the terminology o f our problem,  we d e f i n e  M'-set  H> (  X l  as f o l l o w s :  ,x ,s,t) = |(y ,y ): 2  1  With t h i s  i + 1  and T o t a l  f o r Waiting  W a i t i n g Times In K i e f e r  F  Functions  (x ,x ) 1  A typical  =  2  definition,  jJ [ P  ( W  i' i Q  ) 6  2  we  t  i  1  i  2  i  have  4'(x ,x ,s,t)J 1  4* - s e t i s shown F i g . 3.  2  [w =y ,Q =y ,S =s,T =t)]  y.  2  dH(s)dG(t)  i  32  The  r e c t a n g l e s f o r m e d by t h e two a x e s and t h e  p o i n t s A and B above t h e l i n e the is  (as shown) i n t e r s e c t e d w i t h v  2 Y;L determine  the actual  =  inclusion-exclusion  principle  =  i  <y (  i  X ; L  x  x  2  then  2  ^  n  e  /  w  9  e  e t  2  2  If x ^  i  ,x ,s,t)]  = F ( x - ^ s + t , x + t ) + E\ ( x - s + t , x + t ) - F i  - s e t . Using  and n o t i n g t h a t t h e r e  no p r o b a b i l i t y mass b e l o w t h e Y2 Y±  p[(W ,Q )£  the region  1  ( x ,x , s , t) = 1  i  (  X l  -s+t  / X ; L  +t).  (x ,x ,s,t).  2  2  2  T h i s e s t a b l i s h e s e q u a t i o n (5), The  corresponding  system I I ( r e p l a c i n g resulting the  ^  d e f i n i t i o n may be u s e d f o r and  (x.^ , x , s , t )  and Q ^ ) ; h e r e t h e  s e t i s a complete r e c t a n g l e w i t h  2  upper r i g h t  by  vertex at  (x ~s+t,x^+t). 2  Hence P ^ W ^ Q ^ e ^ ( x ^ x ^ S j t j ] thereby 2.  establishing  Counterexample  equation (4).  to conjecture C  L e t H ( s ) and G ( t ) be s u c h P  r ..=s] s  L  1  J  = (  1  < 1/2 0  /  that 25 = 2  s=4 otherwise  = F  ±  (x ~s+t 2  33  99/100 P[Ti=tJ  = ^  1  /  1  0  t=l  0  t  0  p r o c e s s b o t h s y s t e m I and s y s t e m  c a n n o t become p a r t i a l l y  event  [T^=A"J  probability completely  takes  (large)  A  otherwise  With t h i s a r r i v a l II  =  place.  idle until We p i c k  A  f o r some i t h e so l a r g e t h a t t h e  t h a t one o f t h e two s y s t e m s w i l l a t t h a t time i s n e g l i g i b l e .  n o t empty o u t  Thus, u n t i l  ^T^=A*J  h a p p e n s f o r some i , t h e t o t a l w o r k i n s y s t e m I a n d I I g r o w s 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 tending t o  be more u n b a l a n c e d , s o t h a t i t w i l l  tend  s h o r t and l o n g w a i t i n g t i m e s For  (relative  whi l e  I  for  t o system I ) .  example P [w 6 .= 0 | T = l , i = l , . . . ,5^ =3/16 ^  F (0,oo )  P [w 6 =0 | T = l , i = l , . . ,5 J  F6(0,.oo)  ±  W.  t o have b o t h  i  =1/4  Thus t h e d i s t r i b u t i o n  functions  variables  =  6  s u f f i c i e n t l y high  values  o f i . S i n c e we h a v e a  ( w i t h t h e e v e n t T^=A  renewal p e r i o d ) , the i n t e r s e c t i n g behavior F\(X,OO) s h o u l d  tribution  #  f o r t h e W. a n d l (F.(x,.oo) a n d F. (x,oo)) s h o u l d i n t e r s e c t l I  renewal process here  and  ;  functions  initiating  o f F^(x,oo)  c a r r y over t o the steady-state F(x,oo) and F(x,oo ) .  a  dis-  3. R e c u r s i o n  Relationships  With  K  i  we have where Y (  = ^ [  ( x  K  x ]  U  A typical  and  i  X  +  _,  (  1  x 2  x  '  x  )  x  [\  =  2  l '  as i n s e c t i o n ' I I and  x^L.ST x j  [  v  (  U  i' i> L  = |(Y1fY2)  fS,t)  i + l * ^  1  defined  = P [ U .*  l' 2>  I n v o l v i n g Work and U n e v e n n e s s  L  i  +  l  £  x 2  e  ^  ;  (  x  i' 2' ' x  : [" i=Yi ' i = Y U  letting  L  s  2  t )  ]  ' i S  d  H (  =  s  s  )d  G ( f c )  ' i ^[ T  =  ] ] .  - s e t ' i s shown i n F i g . 4.  Fig.  4.'M -set r  Shaded a r e a  f o r (U,L) .  = T(5,10,7,9)  35  functions of x ^ , X 2 , s , t .  The v e r t i c e s A-E a r e a l l  I t i s c l e a r t h a t t h e term P J ( U ^ , L ^ ) 6 'VjT (x^ , x , s , t ) J cannot 2  be e x p r e s s e d d i r e c t l y i n terms o f K.(,) as was t h e case for  (W^,Q^).  Rather such an e x p r e s s i o n would have t o t a k e  the form o f a double i n t e g r a l w i t h v e r y c o m p l i c a t e d 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 p r o v i n g K^(oo,x) 2 K\(<x>,x) i s t h a 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 h y p o t h e s i s : we would need a s t r o n g e r statement such as K. ( x ^ x ^ l ? K. ( x ^ X j ) s t e p goes t h r o u g h .  t o insure that the induction  However, t h e l a s t h y p o t h e s i s cannot  be t r u e s i n c e U. can be n e g a t i v e w h i l e U. cannot be. A l  ^  I  w o r k a b l e r e p l a c e m e n t i s h a r d t o f i n d because i n v o l v i n g t h e unevenness  q u a n t i t y t e n d t o be non-monotonic.  As an example c o n s i d e r t h e f o l l o w i n g [ < E  f(.x,y)=E  I  '.'.  functions  +  1  - L  I  +  1  )  |  function:  Sr.=L.=A,U.=x U.=yJ F  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 g i v e n t h a t t h e p r e s e n t work i s e q u a l b u t w i t h system I and I I h a v i n g unevenness  x and y, r e s p e c t i v e l y .  The non-  monotonic b e h a v i o r i n x and y can be demonstrated even f o r the M/M/2 queue, w i t h  36  -s/3  H(s)  = 1 - e  G(t)  = 1  This  i s shown i n F i g . 5, w h i c h i s a s k e t c h  ,"t/2  o fthe  sign of f(x,y).  F i g . 5. An Example of t h e Non-Monotonic B e h a v i o r o f U: R e g i o n s where f ( x , y ) i s p o s i t i v e and negat i v e (M/M/2,A=5)  5  -5  •+-T  +  4 + + + + +-+ + +  x  

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}]}"
                            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:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0079362/manifest

Comment

Related Items