Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A queueing analysis of a multichannel, integrated voice and data communications system Haller, Dennis Raymond 1982

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

Item Metadata

Download

Media
[if-you-see-this-DO-NOT-CLICK]
UBC_1982_A7 H34.pdf [ 4.19MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0065616.json
JSON-LD: 1.0065616+ld.json
RDF/XML (Pretty): 1.0065616.xml
RDF/JSON: 1.0065616+rdf.json
Turtle: 1.0065616+rdf-turtle.txt
N-Triples: 1.0065616+rdf-ntriples.txt
Original Record: 1.0065616 +original-record.json
Full Text
1.0065616.txt
Citation
1.0065616.ris

Full Text

A QUEUEING ANALYSIS OF A MULTICHANNEL, INTEGRATED VOICE AND COMMUNICATIONS SYSTEM  by DENNIS RAYMOND HALLER B.E.,  University  of Saskatchewan,  1980  A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE  REQUIREMENTS  FOR THE DEGREE OF  MASTER OF APPLIED SCIENCE in THE  FACULTY OF GRADUATE  Department  We a c c e p t to  THE  of E l e c t r i c a l  this  thesis  the required  ©  Engineering  as conforming standard  UNIVERSITY OF B R I T I S H June  STUDIES  COLUMBIA  1982  D e n n i s Raymond  Haller,  1982  DATA  In  presenting  this  thesis  in  partial  fulfilment  of  the  requirements f o r an advanced degree at the U n i v e r s i t y  of  British  Columbia,  I  it  freely  available  for  permission  agree  for  purposes may or  her  that  the  Library  shall  reference  and  study.  I  extensive  be granted by  representatives.  p u b l i c a t i o n of t h i s t h e s i s allowed without my  Department of  written  Electrical  The U n i v e r s i t y of B r i t i s h 2075 Wesbrook Place Vancouver, Canada V6T 1W5  Date:  28 June  1982  make  further  agree  copying of t h i s t h e s i s f o r the Head of my It for  is  financial  permission.  Engineering Columbia  scholarly  Department or  understood gain  that  that  by  his  copying or  shall  not  be  i i  Abstract A  multichannel  multiserver  queue,  representing shorter  r a d i o communications with  two  distinct  v o i c e and d a t a m e s s a g e s .  average  system  length, i s given  i s modeled as a  customer  Data,  classes  the c l a s s  non-preemptive  with the  priority  over  voice. The chain  balance  using  of  model  w i t h an i n f i n i t e  state  and  queueing  each  messages  property  algorithm  i n the system.  is  used  and  numerical  excellent 0.1  to  solved numerically of  Kotiah.  results.  model  results  are  the  This  d a t a messages b e i n g  less  the  upper  bounds,  high  t o be o f p r a c t i c a l waiting  times  show them t o be state  than  cost.  system  and t o  four-channel  both s i m u l a t i o n  is  produces  less  than  t o the p r o p o r t i o n of  For other  traffic  mixtures,  f o r waiting times, a r e often too  However, t h e l o w e r  bounds  of  the  a r e of g r e a t e r use; the s i m u l a t i o n r e s u l t s  reasonably  values.  intensity  f o r the  original  The LP method  typically  90%.  especially use.  in detail;  traffic  corresponds  the  particular  presented.  r e s u l t s when t h e d a t a .  The  times  o f t h e Markov  improves  analyze  i s treated  Upper  distribution  Exploitation  help  steady  f o r t h e mean w a i t i n g  irreducibility  the numerical  of the queueing  steady  obtained  and the p r o b a b i l i t y  of  case  mean  (LP) t e c h n i q u e  Markov  s e t of  by c o n s i d e r a b l y r e d u c i n g t h e c o m p u t a t i o n a l  Simulation validate  The i n f i n i t e  i s t r u n c a t e d , then  bounds a r e t h e r e b y  of  chain's  space.  programming  customer c l a s s ,  number  about  state  equations  the l i n e a r  lower  i s analyzed as a continuous-time  good  approximations  to  the  true  . . .  111  Table  of  X  Contents  Abstract List  i i  of Figures  v  Acknowledgement  vi  I.  INTRODUCTION  1  II.  SYSTEM ANALYSIS  3  A.  THE APPROACH  3  B.  MARKOV MODELING  3  NUMERICAL TECHNIQUES OF MARKOV MODELING The Markov C h a i n E q u a t i o n s F i n i t e S t a t e Space I n f i n i t e S t a t e Space  6 6 7 8  C. 1. 2. 3. III.  MODEL SELECTION  A.  BASIC ASSUMPTIONS  B.  SERVICE DISCIPLINES  C.  IV.  11 ..  12  1. 2. 3.  ALTERNATING PRIORITY MODELS 14 Previous Investigations 14 Markov C h a i n M o d e l — N o n - e x h a u s t i v e S e r v i c e ..15 Markov C h a i n M o d e l - E x h a u s t i v e S e r v i c e 16  1. 2.  NON-PREEMPTIVE PRIORITY MODELS Previous Investigations Markov C h a i n M o d e l  D.  NUMERICAL  SOLUTION TECHNIQUE  17 17 18 20  A.  THE STATE SPACE  20  B.  THE BALANCE EQUATIONS  21  C.  THE LINEAR PROGRAMMING SOLUTION TECHNIQUE  24  D.  NORMALIZATION  26  E. 1. 2. F. V.  11  CONSTRAINTS  IRREDUCIBILITY OF THE MARKOV CHAIN The S i g n i f i c a n c e o f I r r e d u c i b i 1 i t y Improvements t o t h e LP A l g o r i t h m  28 29 30  IMPLEMENTATION OF THE MODIFIED L P ALGORITHM  31  RESULTS  35  A.  SYSTEM PARAMETERS  B.  THE STEADY STATE PROBABILITY DISTRIBUTION p ( n ) ..38  C.  MEAN WAITING TIMES 1. Definition 2. The L i m i t i n g C a s e s : 3. W a i t i n g Time R e s u l t s  D.  43 43 44 46  a,-M  WAITING TIME SIMULATIONS  E. 1. 2. F. G. 1. 2. VI.  35  51  COMMENTS ON THE WAITING TIME RESULTS Empirical Observations Waiting Times i n a Non-preemptive System  53 53 Priority 54  CONVERGENCE OF UPPER AND LOWER BOUNDS  56  COMPUTATIONAL COSTS LP S o l u t i o n Cost A Comparison w i t h S i m u l a t i o n C o s t s  63 63 65  CONCLUDING REMARKS  67  A.  LIMITATIONS OF THE MODEL  67  B.  SUMMARY AND CONCLUSIONS  69  C.  SUGGESTIONS FOR FURTHER STUDY  72  APPENDIX A - A COMPARISON OF NON-PREEMPTIVE ALTERNATING PRIORITY SERVICE DISCIPLINES,  PRIORITY  APPENDIX B - THE STATE SPACE TRANSITION DIAGRAM  AND 74 77  APPENDIX C SETTING UP THE BALANCE EQUATION COEFFICIENT MATRIX "A": AN EXAMPLE 79 APPENDIX D - A DERIVATION FOR THE GIVEN IN [KOTI 77]  NORMALIZATION  CONDITION 84  BIBLIOGRAPHY  86  Glossary  89  of N o t a t i o n  V  List  of F i g u r e s  P a r a m e t e r s &,  and  o,  The D i s t r i b u t i o n  p ( n ) f o r p = 0.7,  o,=  0.80,  (*,=  0.14) 39  3.  The D i s t r i b u t i o n  p ( n ) f o r p = 0.5,  o,«  0.80,  (*,=  0.14) 41  4.  The D i s t r i b u t i o n  p ( n ) f o r p = 0.5,  o=  0.95,  5.  Waiting  1.  R e l a t i o n s h i p Between  2.  Times a s a F u n c t i o n  of  y  * i :  P -  37  0.7,  0.44) 42 n = .  30  n = .  25  47  c  6.  Waiting  Times as a F u n c t i o n  of  e,  :  p = 0.5,  c  7.  Waiting  Times as a F u n c t i o n  of  B,  :  p -  0.3,  48  n = 20 . ....49 c  8.  C o n v e r g e n c e o f Bounds f o r P r o b a b i l i t i e s p ( 0 ) , p ( 4 ) 58  9.  C o n v e r g e n c e o f W a i t i n g Time o,= 0.80, (*,,= 0.14)  Results:  10. C o n v e r g e n c e of W a i t i n g Time o,= 0.80, 0.14)  Results:  11. C o n v e r g e n c e o f W a i t i n g Time o,= 0.95, (p,= 0.44)  Results:  12. S c h e m a t i c of a 2 - C l a s s  p -  0.7, 59  p =  0.5, 60  p =  0.5,  M u l t i s e r v e r Queueing System  61 ..74  13. S t a t e  Space  for n Z s  78  14. S t a t e  Space  for n < s  78  15. M a t r i x  "A"  F o r n = 6 , s=4 c  Servers  80  vi  Acknowledgement  I would Leung,  for  during  like his  t o thank my guidance  the course  and  s u p e r v i s o r , Dr. constant  of the r e s e a r c h  C.S.K.  availability  and w r i t i n g o f t h i s  thesis. Financial Postgraduate Columbia  assistance Scholarship,  teaching  acknowledged. NSERC r e s e a r c h  in  the  grant  of  an  NSERC  and a U n i v e r s i t y o f B r i t i s h  assistantship  This  form  work A-1052.  is  also  was p a r t i a l l y  gratefully supported  by  1  I.  In  this  study  multichannel  INTRODUCTION  we  radio  analyze  communications  t o b o t h d a t a messages and queued  an  may  interactive  messages  busy,  the  sent  the  message-carrying  If a l l  controller  service  available Our  obtain  In t h i s on  objective  type  is  and  to the  average  the steady  queueing  radio  theory  the  The  solution  equations.  We  the c a s e of  s = 4  assumed t o e x i s t ,  only  channel  such a mobile  or  through  to  radio  a  of  central  channels  incoming  are  r e q u e s t s and imposes  an  resource —  the  state  will  efficiently  analysis  specifically  it will  service discipline assign  In  a  of will  continuous-time  channels. but  times  probability  system.  system for  model  An not  obtain  channel  use,  while  the  and  2  1  in fact  require chain  signaling  included  of the c e n t r a l  on  the  state  numerical r e s u l t s for  auxiliary be  for  based  types  Markov  to  each  distribution  c h a n n e l s become s e r v e r s ,  queueing of t h e  communications  queueing  v o i c e messages become c u s t o m e r s  respectively.  The  be  each  by v o i c e  of a f i n i t e  model t h i s  i n the  numerical  example o f  the c o n t r o l l e r  t h e use  can  channels.  t h e number o f messages  and  way,  type  for transmission  temporarily denies  discipline  some measure o f  message  Requests  an  i s provided  i n which  either  auxiliary  each  One  via  co-ordinated,  Service  network  office  terminal.  a l l o w s a queue t o f o r m . orderly  radio  with a c e n t r a l computer  are  controller.  data  system.  v o i c e m e s s a g e s , and  be a modern m o b i l e  communicate  s  centrally  when a l l r a d i o c h a n n e l s a r e b u s y .  system can  a  i n our  controller  channel i s model. must  not  but a l s o must m a i n t a i n  2  message q u e u e i n g possible  times  service  physical  system  cutoff  priority,  priority.  Only  at acceptable  disciplines,  are:  the  first-come  two o f  most  Among  priority,  these  the  many  r e l e v a n t t o the given  first-served  non-preemptive  the l a s t  levels.  will  (no and  be  priority), alternating  given  serious  further consideration. The this  following  chapter  study, and o u t l i n e s  modeling.  Chapter  alternating  priority  assesses  both  tractability.  III  the  IV  describes  methods u s e t o s o l v e t h e c h o s e n a  selected  Finally,  example  i n Chapter  summarized  previous  to their  VI t h e main  and p o s s i b l e  work priority  analytical  in  detail  Markov  with the  models,  from  i s outlined.  and  and n u m e r i c a l the  numerical  results for  and d i s c u s s e d i n C h a p t e r  results  f u t u r e work  of  done  m o d e l , and n u m e r i c a l  are presented  approach of  techniques  non-preemptive  respect  Chapter  numerical  reviews  and  with  describes the a n a l y t i c a l  this  study  V. are  3  II.  A.  THE  APPROACH  Analytical multiserver Two  SYSTEM ANALYSIS  solutions  queueing  and  alternatives  numerical  of Markov c h a i n m o d e l s . and  execution  significant  The  only  the  A  effort,  while  s i m u l a t i o n language.  simulation  program  the  time  of a n u m e r i c a l  computer p r o g r a m , b o t h  numerical  independent  checks  on  their  one  check  on  the  relied  a  primarily  simulation  B.  on  the  numerical  solution  effort  to provide a d d i t i o n a l  requires  behaviour  is  into  l e n g t h of  acceptable usually  time  a a  confidence  greater  program.  i t being  In t h i s  numerical  require a  As  than  with  any  s i m u l a t i o n programs r e q u i r e  validity, other.  may  actual  usually  system  solution and  versus  solution  give  f o r the measured q u a n t i t i e s  execution  as  of  are  solution  simulation  to  analysis the  However, t h e  run  disciplines.  particularly  numerical  specialized  must  service systems  analytical  straightforward translation  intervals  u n a v a i l a b l e f o r most  t r a d e o f f between  time.  modeling  for  solutions,  simulation i s in i n i t i a l  program  generally  systems with p r i o r i t y  o f t h e more p o p u l a r  simulations  are  acceptable  investigation  approach but verification  have of  to we  also  the  use have used  results.  MARKOV MODELING Many  demand  use  effectively present  probabilistic of  certain  using  a brief  a  systems, system  Markov  in  which  resources,  c h a i n model.  incoming can  be  In t h e  summary of Markov c h a i n m o d e l i n g  customers analyzed  f o l l o w i n g we  techniques,  and  4  for  simplicity,  independent  be  found  essential  discrete-time is,  consider  parameters  t r e a t m e n t s can The  we  or  A state  system,  d  has  t a k e on  infinite  states with  i n the  on  The chain  an  range, state  a  known  system The  space.  For  the  (perhaps  instants  can at  or  i f at  least  example, the  be  are  in  an  state future.  variables  may,  chosen of  depending  one  on  number  variables  a  each  number  of  form  variable  infinite  in  That  states,  infinite  state  be  of  its  finite  d  the  a  has  number  queueing  Markov c h a i n  system  determine can  of  system  model w i l l  underlying  whether be  t i m e between  be  so m o d e l e d  used.  In  successive  i s the  l a b e l l e d by  the  Markov  a  state  An  transitions  integers  example  queueing  occur  or  continuous-  random v a r i a b l e  M|M|s  t r a n s i t i o n s may  the  a discrete-time  dependent) parameter.  which s t a t e  time Markov c h a i n  a  d i s t r i b u t e d continuous  state  whether  present  set  state  be  will  72].  space.  representation  exponentially  which  The  state  also  the  finite  queue l e n g t h s  will  t i m e Markov c h a i n , an  a  there  c h a r a c t e r i s t i c s of  model  its  each v a r i a b l e  s p a c e and,  then  infinite  continuous-time  is  , and  detailed  Markov P r o p e r t y .  a discrete of  time-  [ROSS  chain  that  There w i l l  values.  unrestricted  defined  d  state  and  i t s entire history affects  either  allowable  with More  75],  Markov  property  system. say  - dimensional  an  the  [KLEI  i s the  i s f o r m e d of  the  variables,  discrete  a  a unique c o n f i g u r a t i o n  to c h a r a c t e r i z e  the  of  systems  processes).  [BHAR 6 0 ] ,  continuous-time  Markov c h a i n  state  in  s u m m a r i z e s how  being  stochastic  (stationary  feature  a Markov c h a i n  completely  only  in a  with of  a  system. discrete-  {0,1,2,... },  and  5  the  t i m e between  distributed chain  successive  discrete  m o d e l s may  the  as  (either  i s called  a Markov  which  This  define  as  a digital  communications system.  between  continuous  state  transitions  or d i s c r e t e t i m e ) ,  The p r o c e s s  can s t i l l  successfully  be m o d e l e d  Markov  technique  to  queueing  may  be  processes system f o r  used as  process  t o number  is  not  chain. many  discrete-time  Markov  can  chain,  transition  easily  chain  times.  on The  gives  imbedded  chain  each  probabilities correspond each s t a t e . between  state  therefore  to  of  the  for  imbedded  probabilities  transformation  times. however,  The  of  time  computed  they  again  of the system being  makes use o f  s t a t e s of t h e p a r t i c u l a r imbedded c h a i n  the  on  of number i n  proportion  so t h a t  be  imbedded  chains  chain.  need t o be a d j u s t e d  stationary  This  Markov  probability distribution  system, but i n s t e a d a d i s t r i b u t i o n in  M|G|1  n o r even semi-Markov  Markov  discrete-time  not the g e n e r a l - t i m e  spent  the  i n t h e s y s t e m n ( t ) , t ^ O ) , but i t may  modeled a s a d i s c r e t e - t i m e  these  be  but a d i s c r e t e -  s e t of i n s t a n t s c o n s i s t i n g of a l l s e r v i c e c o m p l e t i o n  Solving  found  model  example  Markov,  is this  i n s t a n t s c a n be  i s a l s o p o s s i b l e by i m b e d d i n g a Markov  respect  then  an imbedded d i s c r e t e - t i m e  o f i n s t a n t s formed of a l l s t a t e  (with  the  operate  a c o n t i n u o u s - t i m e Markov  continuous-time  the  t o systems which i n h e r e n t l y  time  stochastic  The M|M|s  t i m e model set  in  imbedding  represented  Markov  i f a c e r t a i n s e t of time  continuous-time chains.  of  geometrically  Discrete-time  semi-Markov.  chain  together  variable.  for instance,  distribution  arbitrary process  random  be a p p l i e d  in d i s c r e t e - t i m e , If  state transitions i s a  in  relationship  and t h o s e  i n the  6  original C.  general-time  The Markov C h a i n  A  numerical  calculate state  of  the state  possible  to  waiting  time  of  a  Markov  p r o b a b i l i t y that  space.  compute  MODELING  Equations  solution  the s t a t i o n a r y  the  state, state  Denote by  queue  component spends  with  length  the system  i .  The  rate  of steady  representing  i  each  out  state  the proportion  set  of  balance  of  moments  written  for  (or flow) the  state.  p r o b a b i l i t i e s , each of time  the system  equations  is  = 0  Q fJ  the matrix of t r a n s i t i o n t h e n u l l (row) v e c t o r .  Since  jr  i s a p r o b a b i l i t y d i s t r i b u t i o n i t i s n o r m a l i z e d by 1  a discrete-time i s defined  will  defined  i n state  ir  ±  ±  =  time i .  P  (2.2)  a transition probability  is  instant  rates,  1 .  Markov c h a i n  such t h a t  a t the next  currently is  then  (2.1)  with and  P  into  (column by c o l u m n ) a s : £ Q  In  of  of i n t e r e s t .  is  t r a n s i t i o n rate  transition  t h e row v e c t o r  rr  i s in  distributions,  an e q u a t i o n  the t o t a l  the t o t a l  in state  written  model aims t o  d i s t r i b u t i o n s , and o t h e r q u a n t i t i e s  balancing  tr  chain  From t h e s e p r o b a b i l i t i e s i t i s t h e n  a c o n t i n u o u s - t i m e Markov c h a i n ,  each  ii.].  [GROS 74, p.311  NUMERICAL TECHNIQUES OF MARKOV 1.  In  system  the  probability  move t o s t a t e  The s t e a d y  state  the  j , given  matrix process  that  i t  is  probability distribution  through ir P  =  n  (2.3)  7  and  the  normalization  probabilities  can  transitions  that  (2.3)  be  may  although  the  (2.2).  take  be  steady  the  interpreted  the  rewritten  Here  process in a  as  into  form  steady  the  state  state vector  ir  i s not  j r ( I - P )  =  0  proportion  i  structurally  state  .  Note  similar  defined  of  that  to  (2.1)  i n the  same  way:  If  the  s t a t e space  infinite  number of  2.  Finite  Assume that  both  State  (2.1)  one  so  of  s y s t e m s may  the then  iterative  the  s t a t e space are  (2.4)  only  (N-1)  represents  an  (N  so  N  in  equations  Solutions  may  be  these  must be  (2.1)  exactly  states)  systems  of  (2.2)  solved  is finite  (N x N)  normalization  be  or  or  to  linear  equations used t o  (2.4).  obtain  obtained  of  are  replace  The  linear  steady  state  e i t h e r by  direct  or  methods.  Direct  s o l u t i o n s are  more e f f i c i e n t  because  (2.1)  equations.  (2.4)  the  probabilities.  are  that  and  then  Space  Actually  independent,  and  linear  first  equations.  any  is infinite  (2.4)  then  u s u a l l y b a s e d on  when the  specialized  coefficient  data  Gaussian  elimination  matrices  s t r u c t u r e s may  be  are  sparse,  used to  avoid  a  computations which great  v a r i e t y of  which  is  iterative  as  for  a p p l i e d to the the  o r ones  methods  power-iteration  iteration, iterate  involve zeros  [STEW 78]  [WALL 6 6 ] , solution  solution vector  [DUFF 7 7 ] .  jr  In of  the  the  There are simplest  method of  (2.1),  the  i s obtained  from  a of  power-  (k+1)'th the  k'th  8  iterate  as  follows: JL  where  A  rate A  i s a scalar  of c o n v e r g e n c e [STEW 7 8 ] ,  = JL  k + 1  (AQ  k  constant. and,  its  The  although  best  + I)  (2.5)  parameter  A  controls  guidelines exist  value  must  usually  the  for choosing  be  determined  experimentally. Iterative methods full,  methods a r e  whenever  the  o r when t h e y a r e  force  a  zero  Gaussian  coefficient sparse  but  elimination  matrices  have a  Q  or  than  direct  (I - P)  structure  that  a l g o r i t h m to f i l l - i n  are  would  many of  the  system  of  elements. 3.  Infinite  When t h e equations be  which  have  (2.4)  State  state  (2.1)  cannot  Space  space  or  is  (2.4)  developed  technique  considering  There  to  in  then  to  from  the  because constraint  n m of  .  T  This matrix columns,  balance the  seem t o be  [KOTI  of  chain balance Q  infinite  linear and  so i n most  o n l y two  77]  system T  n  =  0  is  numerical best  T  equations structure  are of  or  results.  explained  by  ,  .  (2.6)  i s truncated f i r s t n  (2.1)  (2.1):  equation c o e f f i c i e n t s  with  cases  techniques  s o l v e t r u n c a t e d v e r s i o n s of  of K o t i a h  Q  by-row  the  though approximate,  the t r a n s p o s e  Markov  infinite,  i s also  solved exactly.  to provide useful, The  The  i n g e n e r a l more e f f i c i e n t  chosen lost. these  to  so t h a t In  now  appear  row-  rows  and  m no  coefficients  general  equations.  n £ m With  the  9  >  n  the  problem  standard  i s now v i e w e d  methods  on q u a n t i t i e s be a p p l i e d  of i n t e r e s t .  t o system  in  later  ( s e e IV - C ) .  (m x n)  second  discrete-time modeled  as  additional  a  and h e n c e  corner"  system  be  truncation  will  discussed  Possible  m  was  may  with Markov  northwest by  Seneta by  Wolf  technique are  of both Seneta  probability  , .P , and t h e n m o d i f y  the  also,  and much e n h a n c e d Seneta's  detail  any s y s t e m  developed  using  one  of  "(m x m)  The common a p p r o a c h  the t r a n s i t i o n  columns,  first  also  the  a discrete-time The  bounds  i n more  that  chain  as  extended  is  truncations  Recall  Markov  algorithms  i n [ALLE 7 7 ] .  i s to truncate  rows and  (2.4).  apply.  method  [SENE 6 7 ] , and was r e c e n t l y [WOLF 8 0 ] .  to  and  presumably  be d i s c u s s e d  represented  (2.4)  and lower  technique could  applies  continuous-time  effort,  program  T h i s method o f K o t i a h  technique  linear  linear  t o compute upper  This  (2.4).  (2.7)  t h e p r e s e n t study and w i l l  The  Wolf  an  may be u s e d  used  chain,  as  0  matrix  P  to  and m  the truncated matrix  (m)  in  some s p e c i a l  way.  n  The s o l u t i o n  c o n v e r g e s e l e m e n t w i s e t o JT : lim IT, = ir _  In  [WOLF 80]  matrix  , P Cm; N  Seneta.  ^  several  this  i=1,2,...  possible  modifications  one o f w h i c h particular  upper  l o w e r bounds c a n be f o u n d  /  ir  ±  ( i , j =1,2,...  given  version,  result  n..  c a n be  includes  convergence and  ,m  system  (2.8)  i  Cm) x  are given, For  t o the truncated  ,m).  the  a  [SENE 6 7 , 6 8 ] ,  These  of t h e t r u n c a t e d technique  special in  f o r the r a t i o s computations  kind  which  of of both  of elements require  the  10  inverse  of  the  modifications about  the  s e t s of  to  matrix  ( )P m  ( (m)  listed  convergence  modifications  properties it  is  errors  for  Ifm)"! ~ i I  i = 1 ,2, . . . ,m  .  The and  advantage  Wolf  hand,  to give  method g i v e s o n l y  w i t h unknown m a g n i t u d e s IT  is  F  o  not  the  r  less  possible  to  and  of  both  estimate  the  elements:  judged  to  be  m.  On  state  Consequently, "close  of  Seneta  l o w e r bounds on  approximate  error.  known  For  individual  upper  other  is  of the t e c h n i q u e .  no m a t t e r what t h e t r u n c a t i o n  Wolf's  result  p  of t h e method o f K o t i a h o v e r t h a t  is i t s ability  probabilities  ~ (m) ) •  i n [WOLF 8 0 ] , even  absolute ff  1  enough"  the  state other  probabilities before to  the  v_ ,  the  must  be  (m) convergence determined m .  behaviour by  of  obtaining  the  problem  solutions  under . n s  study  for ever-increasing  11  III. A.  BASIC  ASSUMPTIONS  We c o n s i d e r q u e u e i n g priority  MODEL SELECTION  allocation  models of t h e  s  servers  Customer rate  are  traffic  X  M|M|s  f o r two c u s t o m e r c l a s s e s .  t h e c u s t o m e r s a r e s e r v e d on a The  form  first-come  identical  arrival  f o r customer  Within  and i n d e p e n d e n t  i  (i=1,2).  basis.  of each  Poisson  some  classes,  first-served  i s modeled as a type  with  other.  process  The a r r i v a l s  with  of type 1  i  and  type  arrival The  2 c u s t o m e r s a r e assumed process  service  i s then  times  distributed  with  utilization  factor  total  utilization In  also  of  customer  (? )'  p = p,  the mathematical  class +  which t h i s  lengths,  analysis  but these  probability  is  rate  class  p  ±  = k  2  are exponentially  ±  type  i .  / ( s Kj)  The  and t h e  2  i n the system. of course  a r e assumed t o be l a r g e being  total  p  applies will  of a customer  The  X. = X, + X. •  customer  model we assume t h e r e  t h e number o f c u s t o m e r s a l l o w e d to  for  1  ±  f o r each  is  Poisson, with  each  mean  t o be i n d e p e n d e n t .  blocked  is  no  limit  Physical have  enough  systems  finite so  i s negligible  that .  on  queue the  12  B.  SERVICE D I S C I P L I N E S There  are  considered  for  chiefly a  communications minimize  service  waiting  times,  while  simplest  systems  where  t y p e s may  the  service-time  ratio  Consequently  the  communication  would  greater  usually  server.  average differ  which  will  maximizing  use  of  the d i s t r i b u t i o n s the  exact  be  for  of  20.  80],  would  than  suffer  customer messages,  a  for- voice  interactive  system's  admitted  of  busy  denied  81],  [SING  those with shortest  delay-tomessages.  aspect  makes  resources  of d a t a  service to  time.  service  customers servers  High  i f there  are  i s less wait  however,  i s n o t w o r k - c o n s e r v i n g [KLEI 76, p . 1 1 3 ] ,  f o r each queue.  f o r low p r i o r i t y  customers  is a  one  free  service  t h a n some  in  a  priority  allowed  FCFS  discipline  service  available  t o customers of  with  possible  voice/data  Data  queues,  is  system.  lost.  the  number  7 3 ] , i s no  multiserver  Customers  c  of  service  t i m e s f o r t h e two  short,  greater  [TAYL  always  [KOTI  .  it  s  the  one  73],  a  by a f a c t o r  However, low p r i o r i t y  if  data,  of " u n f a i r n e s s "  quick-response,  of  are  for  service  quite  much  priority,  share  customers  an e l e m e n t  inherently  Cutoff  and  ( F C F S ) , [SLAT  discipline  have  typically  are  be  customer. first-served  i t does  which might  voice  i s to s e l e c t  not  However,  level  goal  t i m e a r e known b e f o r e h a n d , and  the  We  mixed  only  doubt  only  disciplines  assume t h a t  First-come  type,  The  resources.  t i m e o f e a c h new  which  service  multichannel,  system.  message  available  four  cutoff  priority-typed Cutoff  priority  meaning  t o be d e n i e d  that service  13  even  w h i l e some s e r v e r s  resources, priority  and  seems  of  into  maximum  of  controller from is are  priority  k,  according  If either  alternating  priority  section  III -  C.  there  priority  priority,  t o be o n l y  i s unbounded, t h e  service  k  a and  2  particular  class  Because  single  server  waiting  time  yet to  been  proven  so w i l l  be  has a q u i t e  for  s >  behind.  Service  that  [KLEI  76,  allocation  further  a l l  discussed in  known  low  to the  priority priority  average  p.126].  such r e s u l t  but  from  customer  the o v e r a l l  systems  as  rule.  t i m e , t h e n i t i s known  No  to  radio  i s then always  i s given  of p r i o r i t y  Later,  there  the  a s i n g l e queue, w i t h a l l h i g h  systems  1 .  for  simple operating  and  A  its flexibility,  (NPP), more d e s c r i p t i v e l y  for multiserver  this  of  option  mean s e r v i c e  i s minimized  assume t h a t  advantage  NPP  When  i s generalized  viable  If high p r i o r i t y  w i t h the s h o r t e s t  queue.  t h e scheme  similarly  of t h e l i n e .  In t h e c a s e  served  customers head  type.  are  2  together at the f r o n t ,  the  are  customers  k  customers grouped queued  customers  1, t h e n t h e  or  remains  consideration,  Consider  high  from queue  served  priority.  under  head-of-the-line  the  are  classes,  system  Non-preemptive  system  a t t e n d s each queue.  k,  customer cyclic  unless  incoming  to their  s w i t c h e s and a maximum o f  called  of  alternately  t o be e x h a u s t i v e f o r t h a t  is  i s a waste  sacrifice  assumes t h a t  customers  more t h a n two  what  This  "emergency" n a t u r e .  the c o n t r o l l e r  queue 2.  said  an  s e p a r a t e queues  two q u e u e s ,  idle.  an u n w a r r a n t e d  c u s t o m e r s have  Alternating split  stand  for  customer has  i t seems r e a s o n a b l e would  i n I I I - D we  maintain  investigate  its non-  14  preemptive p r i o r i t y detailed  comparison  alternating C.  in greater d e t a i l . of  priority  queueing with  and  a  particular  especially  alternating  priority  a single  s e r v e r have been  analyzed  system.  priority  models  model  et.  al.  (two  queue. any  and  with  some d e g r e e of  Itzhak,  only  success.  [AVI  65]  customer  In t h i s  [SYKE 7 0 ] ,  for  single  then  up  to  k  to  queues, denoted here attempted,  notably  [KUEH 79] this  server  m o d e l , and  extremely The  from the  by  from 2  v  and but  extensions  served  without  relaxed  ±  , has  =1  cyclic from  , and only  [SCHL 81] k  each  this  g e n e r a l i z a t i o n of  queue 2  C(k,,k ,...,k )  v > 2  queues  more g e n e r a l  customers are  [NAIR 76]  priority  [COOP 6 9 , 7 0 ] , [ E I S E 7 2 ] , The  work, however,  in  still service  queue  so on  1 ,  for  v  r e c e n t l y been which  v =2  f o r a l l queues.  i s a p p l i c a b l e only  the  t o the  t o m u l t i p l e s e r v e r s would  ,  All  single  seem  to  difficult.  analytical unknown  particular  by  Avi-  s e r v i c e to  studies  Further  of  alternating  switches  later  71].  case.  k,  i n which  previous  but  the  that  exhaustive  server  customers  2  with  systems  server  i n w h i c h up  the  [EISE  work was  analyzed  delays,  for multiqueue  regime  first  classes)  model was the  The  who  treatment,  intermediate  restriction  be  discipline  a  Previous Investigations  Cyclic  of  NPP  give  ALTERNATING PRIORITY MODELS 1.  and  the  In A p p e n d i x A we  time.  intractability  identities For  of  the  example,  of m u l t i s e r v e r m o d e l s customers  i n the  in service  single  arises at  s e r v e r case  any i t is  15  known t h a t server  is  however, service  attending  the only i s that  servers of  t h e j o b i n s e r v i c e a t any t i m e  2.  about  completely  now  for  the  the  p a r t i c u l a r moment.  system w i t h  such  a  dimensions,  since  the t o t a l  number  s  t h e number o f t y p e t h e number  i,  an i d e n t i f i e r  c,  a counter  four  state  queue n = n  any s y s t e m  five  C(k,,k ) 2  A Markov  space with  s t a t e c a n be  five  described  variables:  1 customers  ^ s , then  0  in service  served  service  served from t h e  cycle.  the possible  ranges  f o r the  variables are:  , (n -s)  c  1f2f3f*«*  f  0  ^  a l l combinations the to  identities,  delays.  a state  i n the current  0,1,2,...  proportional  has  f o r the customers already  q,:  that  priority  o f t h e queue c u r r e n t l y b e i n g  0,1,2,... ,s  say  The  i n the system  Si,:  •  the group of  i n queue 1  current n f i x e d , say  in  Service  no s w i t c h i n g  system  by t h e f o l l o w i n g  q,,  servers,  customers  be from t h e queue  alternating  n, 1 f  s > 1  the  i n s e r v i c e a r e unknown.  Markovian  independent  can  With  Markov C h a i n M o d e l — N o n - e x h a u s t i v e  model  other  knowledge  at that  customers  multiserver  For  moment.  a t l e a s t one must  Consider  Not  that  definite  i s attending  the other  chain  at  i s from t h e queue  l -1f 2 • of these  number  (k,+k ) 2  .  of  s t a t e s c a n e x i s t , b u t a t l e a s t we states  Observe t h a t  with  n = n  (k +k ) 1  2  0  will  be  i s t h e number  16  of i  possible .  configurations  I f i t were n o t f o r t h i s  that  there  given  would  n = n  models.  model  ,  be as  in  exhaustive  "smaller" for  ( I I I - D)  non-preemptive models other  priority  than  the very  i n t h e Markov  a n d so a n u m e r i c a l  Markov C h a i n M o d e l — E x h a u s t i v e  states  and  chain  solution  may  costly.  service  or both queues.  v a r i a t i o n may  a  chain  given  t o both  representation  dimensions.  q  and  there  be a p p l i e d  a r e not  system p o p u l a t i o n  service  four  Service  The r e s u l t i n g n u m e r i c a l model  i n the sense t h a t  with exhaustive Markov  large,  be s e e n  c  t h e same number o f s t a t e s ,  2-class  priority  variables  i t will  t h e number o f s t a t e s  c a n be e x c e e d i n g l y  The  l f  the  alternating 2  3.  factor,  approximately  k., = 1 , k = 1,  become q u i t e  one  0  For  simplest,  be  o f t h e two s t a t e  n = n  0  .  0  C( , ) , 00  either  turns  out t o  many  00  require  a state  state  variables  The c o r r e s p o n d i n g  i , and f o r  n = n  queues,  will  as  to  > s , the p o s s i b l e  possible  F o r example, a  complete  space of are  n,  only s  1  f  ranges of t h e  other v a r i a b l e s a r e : s ^:  0,1,2,... ,s  q, :  0,1,2,...  i  :  , (n -s) 0  1,2.  Again  not a l l combinations  that  the  factor  (ki+k ) 2  replaced  by t h e f a c t o r  model.  Thus  the  same a s i f  the  2  of these for  states the  (since  number o f s t a t e s  k,=t, k =1 2  exist,  C(k,,k )  i = 1 ,2)  we  see  model h a s been  2  for  for fixed  but  this  n = n  0  in the previous a l t e r n a t i n g  C(°°,°°) i s about priority  17  system  C(k ,k ) 1  system  .  2  would  computational  The  solution  therefore  in  of  the  general  exhaustive require  service  much  less  effort.  D. • NON-PREEMPTIVE PRIORITY MODELS 1.  Previous  Analytical  Investigations  studies  of  queueing  models  (s > 1)  those of  cyclic  priority  average  waiting  [COBH 5 4 ] . the  rather  the  time  same  service  have p r o g r e s s e d systems.  of  this analysis  assumption time  that  priority  somewhat  First  f o r members  Unfortunately restrictive  non-preemptive  was o n l y  distribution.  times  Those which a l l o w  t i m e s must d i s a l l o w [BHAT 7 6 ] ,  [WILL 8 0 ] . queueing  all  f o r one c u s t o m e r  (first-come,  [HALF 7 2 ] ,  class  possible  under  The  have  subsequent of  unequal  service service  class  altogether  discipline  i n favor of  [GOLD 8 1 ] ,  first-served).  the  priority  uniformity  o r abandon t h e n o n - p r e e m p t i v e  preemptive p r i o r i t i e s  was  Most  required  66],  than  a l l customer c l a s s e s  improvements t o t h i s work a l s o [DAVI  further  obtained  each  M|M|s  o r no p r i o r i t i e s  absence  of  at  analytical  0  results  f o r the general  service  time  unknown  distribution  particular  times  identities  of  again  customer  can types  be  with  different  attributed in  service  to the at  When a l l c u s t o m e r s have t h e same s e r v i c e  their identities  groups d i s a p p e a r service  of customer c l a s s e s  distributions  time.  distribution,  case  a s members o f d i f f e r e n t  a f t e r t h e y have been a d m i t t e d  any time  priority  to service.  When  f o r e a c h c l a s s a r e d i f f e r e n t , however, t h e n t h e  of the customers a r e maintained  even a f t e r t h e y  have  18  entered  service,  service  will  and  the  have some e f f e c t  w h i c h have n o t y e t been It cyclic upon in  number o f c u s t o m e r s o f e a c h t y p e i n  seems  that  priority  attempts  a t any one t i m e .  restricted  t h e s y s t e m t o one  have  times  restricted  time d i s t r i b u t i o n , be n o t e d  that  with a l l  server.  t o have been 2. A  Markov  less  priority three  Chain  NPP  The  and  number  of s t a t e s  of  it  what  systems  i  Non-preemptive  priority  to a single  multiple  servers.  systems with  of  service  I t should  different  service  [COBH 5 4 ] .  However,  priority,  the  effort  Markov  a multiple  identical,  be ,  for  or. C C  C(k  ,  1 f  been n = n  the 0 0  than  server  seems  0 0  state  ).  k ) 2  . ,  not  we  model  alternating  space r e q u i r e s  see t h a t  only  with the  the state  Consequently  the  > s , is essentially  half  simplest This  the  NPP  Compared  dropped. 0  M|M|s  does  n, s , , q,  model have  2-class  chain  for a given  would  C(1,1)  but have  Model  computational  priority c  allowed  customer types,  time d i s t r i b u t i o n s  independent dimensions:  variables  of the customers  m o d e l s have  have been s o l v e d  solution  model.  alternating  fallen  treated.  numerical  requires  schemes have  a l l customer c l a s s e s  server  service  those  of both  priority  complementary problem i n ' c y c l i c  model  of  solution  the h e t e r o g e n e i t y  but have a l l o w e d  single  times  analytical  for different  times f o r customer c l a s s e s the  at  Cyclic  service  models  waiting  and n o n - p r e e m p t i v e p r i o r i t y  t h e same p r o b l e m , namely  service  the  served.  different  yet  on  alternating  priority  advantage of s i m p l i c i t y  is  19  one  r e a s o n why  the  NPP  model was  selected  for closer  analysis.  20  IV. A.  THE  NUMERICAL SOLUTION TECHNIQUE  STATE SPACE  As  mentioned  i n the  model  requires  priority  dimensions.  For  components  (s, s ;  customers of  types  of  central  controller,  the  determined  Appendix  A).  being  only  customers a t the  q  2  of  assumes  (or  and  the  q,,  q  occurs,  state  number are  2  does not Its  (s, s ;  q,  2  storage),  2's  the  system  is  (see  2  think  2  .  n < s  of  type  The  1  be is  q )  the d i m e n s i o n s When  The  need t o  with  n = s,+s +q +q  queue l e n g t h s ,  the  customer  to  back. 2  of  behaviour  (pooled at  four  for service.  classes  type  2  (i = = n .  ,  1  total As  this  q,  and  (s=  number  2  = s  1  ,2) ,  q,=  0,  q = 2  state  space  0  then: ±  is  are  2  by  then:  0 < s < s and s,+s choice  s  1 f  independent  labelled  2 waiting  a r e a l s o unbounded.  ±  One  be  customer  queue and  three  variable.  given  two  i n the  q,)  0 < s < n and s,+s When n > s  the  of  non-preemptive  which s e l e c t s a w a i t i n g  departure  unbounded  n and  servers)  1 and  with  front  number of c u s t o m e r s model  types  state  one  s  service,  a  by  i s convenient  where  device  the  space  2 in  a separate  totally  there  1 and  whenever by  state  ,  2  c u s t o m e r s of  represented  It  q, q )  2  service  a  chapter,  convenience a state w i l l  number  for  previous  of  (n,s,,q,)  three .  (i=1,2), ,  independent In  what  q,,q  2  Qi Q2 +  dimensions  f o l l o w s we  > 0 = n - s .  for this  choose  rather  t o use  the  21  more c o n v e n i e n t B.  THE  state  steady  state  continuous-time flow) rate  out  of  follow  the for  state.  the  mechanical given  total not  be  approach to  P(s!  s ; 2  i s i n the  states  single  chain  m o d e l s by  This  flow  rate  a trivial the  with  the  into  the  a  of  transition rate  always easy  than given  matter.  in  transition  i s not  greater  construction  obtained  equating  prescription  dimensionality  are  to  one  because  state  from i t s  An  easier  but  more  the  balance  equations  below.  Let  for  •  equations  into a particular state  n e i g h b o u r s may  system  2  balance  Markov  s y s t e m s of  obtaining  is  q i q2)  (s, s ;  BALANCE EQUATIONS  The  (or  vector  state  be  the  (s, s ; 2  stationary q,  q ) 2  in a three-dimensional  indexing  column v e c t o r  q i q2)  variable  of  i  .  state  (i=1,2,3,...  probabilities  x^  .  p r o b a b i l i t y that These  probabilities  space are ) to  the  ordered  form the  Adapting  by  a  infinite  equation  (2.1)  then: x —  with  x —  and  0  CO  currently Q Q. ±± ±  Note t h a t  Q  T  CO  = 0  (4.1)  T  —  b o t h column v e c t o r s .  Given  in state  i  = t r a n s i t i o n rate = t r a n s i t i o n rate  system  is  by  construction,  out of s t a t e i ( n e g a t i v e ) from s t a t e i t o s t a t e j a l l rows of  Q  sum  e q u a t i o n c o e f f i c i e n t s appear a l o n g  All  i s now  (usually  the  then:  balance that  that  —  necessary  row-by-row) and  i s to generate then  from t h e  the  the  to  zero.  c o l u m n s of Q j ±  structure  The Q  .  coefficients of  the  columns  22  of  Q  , deduce The  stated  the general  service  form of t h e b a l a n c e e q u a t i o n s .  d i s c i p l i n e f o r non-preemptive  as f o l l o w s  (assume n > s ) :  select  which  case s e l e c t a type 2 customer.  allowable  state  system.  Combining  arrivals,  a state  (see  be  1 customer, This  due  qi=0  unless service  to  rule  departures  can  be  in  governs  from  these with the t r a n s i t i o n s caused t r a n s i t i o n diagram  ,  the  by s y s t e m  constructed  Appendix B ) . Once  clearly Q.. of  a type  transitions  space  may  At t h e next d e p a r t u r e from t h e  system  the  for service  priority  the  the system's  will  rules  of  transition rates. current  customers  have p o p u l a t i o n + X.  On  I  IT  p  <  S 1  j=  * K !  1  j= j= .j=  +s2*  (s, + 1 (s,  s s  (s, (s,  S  -1 ( s , -1 (s,  s S  (s,  t r a n s i t i o n rates  transitions B.  indicated  are a  s  matter  Recall  n = s +s +q +q  'j= ( s , j = (s, + 1 j= ( s ,  Appendix  a queueing  written 2  (n ± 1 ) .  I  X-2  state,  +S 1 H 1  2  I  r  These  for  expressed i t i s not a d i f f i c u l t  conditional  number  service  1  to  that  have  been  generate  the  i  i s the index  i= ( s , s ; q i q ) 2  •  2  2  The o b j e c t  •  9  2  m 9  2  +  1mf  •  f  2  0  0  q )  n < s n > s  q + D  n < s n > s  )  q1 i +  0  0  q,  2  ) 2  q -D q )  s -1 • 0 0 ) s - 1 9• q1-1 q ) • 0 q -D s 9  n < s n > s, n > s  9 9  2 2  2  state  j  n > 0  n < s n > s n > s,  s  > with  Then:  2 )  2  system  +  1t  m  0 0  0  ) 2  •• qi-1 r  2  2 2  2  2  2  complete  by t h e s t a t e  list  space  qi* (4.2)  of  a l l allowable  t r a n s i t i o n diagram i n  23  Generalizing now  the s t r u c t u r e  o b t a i n the steady  state  of the columns of  balance  2  2  2  we  can  0 < n < s-1  +  2  ,  equations.  (x,n +s,(., s «2) P(S, s ) X, P ( s , - 1 s ) + X P ( s , s -1 ) + (S , + 1 ) * , P(s , + 1 s ) + (S +1) n P ( s , s +1) 2  Q  2  2  2  2  (4.3)  2  (X ,+k + s, i + s . ) P ( s , s ) n = s = X, P ( s , - 1 s ) + X P(s, s -1) + s,m P ( s , s ; 1 0) + ( s , +1 ) »», P ( s , + 1 s - 1 ; 0 1) u  2  2 >  2  2  2  2  2  2  +  u  ( s +1) 2  2  P(s,-1  2  s +1;  + S K  1 0)  2  2  Pts, s ;  2  (X. ,+X +s , u , + s u ) P ( s , s ; q, q ) X, P ( s , s ; q,-1 q ) + X P ( s , s ; q, + s , (•, P ( s , s ; q , +1 q ) + 6 ( q , ) ( s , + l ) 1*1 P ( s , + 1 S - 1 ; 0 q + D + ( S + 1) t. P ( s , - 1 s + 1 ; q, + 1 q ) + 6(q,) s „ P(s, s ; 0 q + D 2  2  2  2  2  2  2  2  2  2  2  2  as  the  standard matrix  form,  n  , then 2  .  the balance  x  Q  =  2  With  are written  ,  2  increasing  this  (4.6)  0  represent the balance  i = ( s , s ; q, q )  with  equations  of (4.1):  s u c c e s s i v e rows o f states  i s negative,  2  QT  s  conventions:  2  the transpose  The  (4.5)  2  the f o l l o w i n g  2  In  2  2  P ( s , s ; q , q ) = 0 , when any i n d e x P(s, s ) = P(s, s ; 0 0), 6(q,) = 0 q,= 0 \0 otherwise .  i  q "D  2  2  2  H e r e we have u s e d  (4.4)  2  2  2  1)  n > s+1  2  2  0  2  q,  ,  ordered and  o r d e r i n g of s t a t e s ,  first  finally the  equations with  with  n > s  for  increasing increasing  p a r t of matrix  T Q  possesses  blocks  of  generation q  2  a  few  coefficients, of the balance  replacing  convenient.  only  q, Refer  , or  different a fact  which  equations. s,  replacing  t o Appendix  (s+1 x s+1) simplifies  Other s  2  recurring  the automatic  orderings with would  C(1) f o r f u r t h e r  be  index  equally  comments a n d an  24  example. A  finite  including (4.4)  equations  until  parameter, (4.5)  .  with of  system  of of  a l l  those  have  been  balance  equations  t h e form  states  (4.5) with  f o r which  represented  on  The r i g h t - h a n d s i d e s o f t h e s e  n= 0  up t o  n= n +1 .  homogeneous l i n e a r  have a r e c t a n g u l a r c o e f f i c i e n t rows.  The  dimensions  the  n = n  the  ,  a  cutoff side of  contain  viewed  n -truncated c  by  ( 4 . 3 ) and  left-hand  equations  matrix  of  obtained  those.of  Consequently,  equations,  is  states  as a  system  model  would  A, w i t h more c o l u m n s  this  matrix  are  than  derived  in  Appendix C ( 2 ) . C.  THE LINEAR PROGRAMMING As m e n t i o n e d  the is the  techniques the l i n e a r infinite  SOLUTION TECHNIQUE  in the discussion  forsolving  programming linear  o f Markov m o d e l i n g ,  an i n f i n i t e  solution  system  of  of balance Q  T  x  s e t of balance [KOTI  77].  equations  of  equations  From  (4.6),  i s written:  = 0  — oo  one  (4.6)  —  with n o r m a l i z a t i o n : I i=1  1  X-L =  .  (4.7)  T The  finite  first  Nj_ rows and  smaller produced for  matrix  A  i s o b t a i n e d by s e l e c t i n g  N j columns.  the d i f f e r e n c e  (NJ-NJ- ) , t h e b e t t e r  ( s e e Appendix  a given  N  J f  C(2)).  i s determined  Markov  chain  model,  balance  equations.  In g e n e r a l  and  from  Nj i Nj , will  by  the  the  and the  be t h e r e s u l t s  The minimum v a l u e o f both  Q  structure  ^ J N  _  N  I^  of the  by t h e o r d e r i n g o f t h e c o r r e s p o n d i n g  25  Define  x  as t h e f i n i t e  probabilities means t h a t  column v e c t o r  ( x ; i=1,2,...  the n o r m a l i z a t i o n  This  (4.7) c a n no  However, a weaker b u t b r o a d l y steady  /N^}.  i  of the steady truncation longer  be  state of  x^  applied.  applicable condition, derived  s t a t e a r g u m e n t s and ( 4 . 7 ) ,  c a n be u s e d  instead  from  (see IV -  D): B with The  B b  x  = b  (4.8)  a row v e c t o r o f c o n s t a n t n o n - n e g a t i v e a scalar p o s i t i v e constant.  truncated  p r o b l e m may  now be c a s t  coefficients,  as a l i n e a r  program ( L P ) :  M i n i m i z e and m a x i m i z e e a c h {Z, ; k=1,2,... K] subject to the c o n s t r a i n t s : A x = 6 B x = b x > 0 . The  objective functions  combinations interest. these  of  marginal  which case each  and  linear  which  a r e of  desired  using  Z^  then  Little's  minimum  be s o l v e d  i s to l e t the  2K  x  of  four  Law each  times.  be components o f a  ,K),  k=1,2,. . . ,K  i s a linear  (see V - B ) .  ±  times t o o b t a i n  bounds  (k=1,2,...  = P(k) ,  k  P(k)  probabilities  upper  i  any  probability distribution,  probabilities  the  x  b o t h t h e maximum  application  x^  times are  i n terms of t h e  To o b t a i n  Z  solved  probabilities  t i m e t h e LP (4.9) must a l t o g e t h e r  Another  in  may be c h o s e n a s  i f mean w a i t i n g  be e x p r e s s e d  (see V - C ) .  k  state  F o r example,  may  waiting  the  (Z }  (4.9)  combination  The  LP  t h e maximum and  P ( k ) . These n u m e r i c a l  {P CO}, u  for  and  the  of  (4.9)  the  must t h e n be  minimum  values  values  steady  of  form t h e s e t of  t h e s e t o f l o w e r bounds true  state  state  (P^(k)},  probability  26  distribution P Note  that  P (k)  (k)  of the system.  <  P(k)  neither  <  the  general  neither  now  constraints program  k=1,2,... ,K .  u  components  P  £ ^ ) >  distribution  n  o  (4.10)  the components  r  themselves,  since  in  sum t o u n i t y .  NORMALIZATION We  That i s ,  P (k) ,  form a p r o b a b i l i t y  u  D.  a  P(k)  CONSTRAINTS  consider  which w i l l  (4.9) w i l l  the  task  ensure that  of  choosing  any s o l u t i o n  be c o n s i s t e n t w i t h  appropriate  of  the  the n o r m a l i z a t i o n  linear (4.7):  oo  I i=1 Equivalently,  x. = 1  .  (4.7)  1  f o r (4.7) we  write  co  E p(n) = 1 n=0 where  p(n)  system  is  (n>0).  normalization of  the  total  These  (4.11)  probability  conditions,  constraints,  of  n  customers  collectively  are represented  i n the called  as a g e n e r a l i z a t i o n  (4.8): B  with  B b  These  x  = b  (4.12)  the c o e f f i c i e n t matrix, of dimension a c o n s t a n t column v e c t o r ( ^ x 1 ) . N  constraints  N  equalities  are  assumed  involving  a t most o n l y  that  truncation  to  (^  be  the f i r s t  xN j ) ,  non-homogeneous Nj  components o f  x . —  00  Recall balance  the  equations  can  no l o n g e r  In  i t s place,  means  that  of  the o r i g i n a l  be e x a c t l y r e p r e s e n t e d Kotiah  [KOTI  the  77]  infinite  system  normalization  a s a c o n s t r a i n t i n an presents  without  of  (4.7) LP.  proof the  27  following: s-1 E n=0  (1 - n / s ) p ( n )  In A p p e n d i x D we d e r i v e stationary p(n)  probability  exists,  system  with  i s assumed  E  distribution  t o reach  queueing systems.  (4.13);  the reverse  multiserver solve  a steady  (4.13),  (4.13)  number  state.  Kotiah  for a large  need n o t n e c e s s a r i l y be t r u e .  Markov  priority  chain  queue.  model  but w h i c h sum t o a v a l u e  for  words,  the  suggests  that  (unspecified) that  (4.11)  class  implies  Consider  the  I t i s possible to  p(n)  much g r e a t e r  a  i n the system  In o t h e r  However, we know o n l y  non-preemptive  the truncated  for  (4.11).  (4.13) and (4.11) a r e e q u i v a l e n t of  .  (4.13) u n d e r t h e a s s u m p t i o n t h a t  p(n) = 1  r  1 - p  =  that  which  satisfy  one.  Clearly  s u c h a s o l u t i o n v i o l a t e s (4.11) b e c a u s e p h y s i c a l l y a l l v a l u e s o f p(n)  must  included are  not  here,  (n > n + l ) .  that  (4.11) none  of  (4.11),  and  (4.13)  the  four  equivalently,  Kotiah's  normalization  whether  model  are  examples  they a r e  (0 ^ n < n +1)  not  or  considered  equivalent.  in.Kotiah's  We  original  t o s i m i l a r problems. of o b t a i n i n g  an a d d i t i o n a l c o n s t r a i n t must  LP s o l u t i o n s w h i c h be  included:  J  E x i =1  Modifying  rise  the p o s s i b i l i t y  N  or  chain  of  f o r the queueing system  77] seem t o g i v e  To p r e c l u d e  regardless  Markov  Thus  c  [KOTI  violate  non-negative  i n the truncated  equations  observe paper  be  ±  <  n +1 T p(n) n=0 original  conditions  1  <  (4.14)  1  .  (4.15)  LP s o l u t i o n t e c h n i q u e (4.13)  and  (4.15)  to  instead  use  both  of j u s t  28  (4.13) a l o n e ,  then  are  inherently  not  so  should  allow  i t s extension  "well-behaved"  to  models  as those  which  considered  in  [KOTI 7 7 ] . To f i t t h e new variable  y  constraint  , called  a  (4.14) i n t o t h e f o r m  "slack  variable",  is  (4.12) a  introduced  new such  that: N  J  E i=1 This  variable  probability  is  vector  E.  be  x  The finally  1  y  £  0  (4.16) to  the will  of c o e f f i c i e n t by  end  (N^+1)  matrices  A  components. and  B  modified  linear  programming  problem  (4.17)  0  i s t h e ( N x Nj+1) c o e f f i c i e n t balance equations,  matrix  of the  N  I  B  i s t h e ( % x Nj+1) c o e f f i c i e n t m a t r i x normalization constraints.  of the  N  N  x  analysis  truncation  solution  method  special  kind  objective  may  f u n c t i o n o f x,  A  selected  must  written:  the present  Markov  truncated  one.  x >  In  the  have  M a x i m i z e and m i n i m i z e Zy. , a l i n e a r x = |^0j subject to  where,  of  OF THE MARKOV CHAIN  complete be  =  , w h i c h now  increased  IRREDUCIBILITY  + y  appended  The column d i m e n s i o n similarly  x  ^  of s e a r c h Z  k  .  N  and  Nj d e p e n d  (see Appendix C ( 2 ) ) .  i s the simplex  function  chain  NJJ = 2, b u t  algorithm  [LUEN  i s made t o d e t e r m i n e However, we  will  queueing models the simplex  The  on  standard  73], i n  which  t h e optimum  show  that  algorithm  the LP a  of t h e  for  many  need not be  29  applied of  t o the e n t i r e  i t .  This  solution  time.  1.  The  The  problem  results  a  some Markov c h a i n s .  if  and  in  a  i f every  finite  mathematically,  an  s t a t e can  be  of  transition  written:  = |P P,i 0  small  savings  i s said  reached  steps  irreducible  discrete-time  to a  i s a well-known  A Markov c h a i n  number  only  part  i n computer  Irreducibi1ity  irreducibility  of  but  substantial  S i g n i f i c a n c e of  n o t i o n of  only  in  (4.17),  characteristic  t o be  from e v e r y  [BHAR 60,  Markov c h a i n  probability  irreducible other  state  p.14].  i s one  matrix  More  i n which  P  the  cannot  be  •  P  Because  of  the  0 P  2  way  any  continuous-time  represented  as a d i s c r e t e - t i m e c h a i n  definition  holds  of q u e u e i n g  systems are  present  system  NPP  structure  of  the  Consider (4.17). state  j  state  i  with  i s no  the  Since  any  , i t follows zero,  r e p l a c e d by  indeed  balance  now  is  P  II - B ) , Q  .  irreducible  exception, equations  N  (see  Markov c h a i n can  balance  as  Markov  can  equation  that  the  stationary  ,  then  reached  so  s e e n by  the  c o n s t r a i n t s i n the  be  0  be  The  C(3)).  may  x.=  models  chains.  easily  (Appendix  previous  Many Markov  state i if  the  be  f r o m any  other  probability  a l s o must  there  LP  be  of zero  i  probability  of  the  Continuing  this  system reasoning  irreducibility,  we  conclude  i f an  null  that  being  find  x.. = 0  and  then  state j :  using  , j = 1,2,... ,H  irreducible  stationary solution,  in  not  the 1  Markov c h a i n one  of  .  x^=  0 .  property  of  Therefore  we  i s t o have a  i t s s t a t e s may  non-  have  a  30  zero  steady  indirectly  state used  probability.  in  [KOTI  77],  i m p r o v e m e n t s t o K o t i a h ' s LP 2.  Improvements t o  Suppose  we  problem with  apply  m  the  LP  the  solution  a certain  (n-m)  remaining together  m  and  The  the  if  the  any  then  one  zero.  and  so  Nj must  no  of  the  remaining  solutions  has  are  {x }  variables  to  excluded  called  a l l of  choosing (n-N^. ) t h u s been  the  (m-N-j. )  , 1 <  (x^ Z  to  when  zero.  The  variables,  > 0)  f ]  j *  exist  basis  to is  the  one  show  that  much  < N-j-  to  set.  The  of  further  components of  x  m J  to  /n-Nj \m-Nj  (4.13) first  basis The  number of  also  the  Nj. v a r i a b l e s .  f r o m fn\  zero,  constraint i f any  that  , must  first  The  less  guarantees  , i s set i  those  73].  (4.17)  i < N-j-  and  basic  n  for  property  normalization  the  (4.18)  a t most  [LUEN  to  , 1 <  candidates. reduced  basic  Irreducibility  x^  LP  m):  in e f f e c t "searches"  (4.17) can from  (n >  i s set  i  There are  •  x.^  arbitrary  s o l u t i o n of  irreducibility  variables  contain by  of  feasible solutions  solution  are  the  function  (jj^J  our  (4.18)  feasible  would v i o l a t e t h e  basic  then  objective  t o an  variables  as  set.  also  maximum  other  This  variables  completed the  general  algorithm  algorithm  invoke the  basic  a l l the  be  the  can  number of  that  simplex  of  u  subset  basis  which are  which o p t i m i z e s we  =  i s defined  form t h e  solutions  Now  x  -component  kernel  was  method.  n  nonzero v a r i a b l e s  they  solutions. basic  x^  the  which  Algorithm  simplex  constraints  observation,  forms  solution  U A basic  This  b  set  set out  possible  is of  basic  31  From n  This  (4.17) we  - Nj>  is  which  =  an  take  what  recognizing the  the  program  [MURT 81,  p.24  general  to determine  already  known.  simplex  of  are  £B] ' "^  algorithm  works w i t h  The  matrix of  set.  search this The  for  be  REE  to  columns  first  ^gj As an  a  this  means t h a t  " ^  sense  that  necessary the  (m  x m)  of  basic  the  s o l u t i o n program  i n any  .(N  they  the  is  -N  scheme o f  requires  the  to  the  not  known  those  current  during  the  updated.  [MURT  specify  The  matrix. from  be  are  "free"  i n the  Bartels-Golub user  of  basis  L U - f a c t o r i z a t i o n must  the  basis  solutions.  obtained  to  only  in  +1)  formed  to v a r i a b l e s  solution  used  steps  are  a l l basic  square matrix  correspond  optimum, t h e use  part  method"  variables  the  by  centerpiece  is applied  the  L U - f a c t o r i z a t i o n of  which  e a c h new  method  to  gained  simplex  Rj. v a r i a b l e s  to  the  a  (4.17)  algorithm  two  only  i s the  p u r p o s e we  last  applied N  As  LP  The  computer  identities  the  solutions  savings  "revised  However, t h i s  In p r a c t i c e  the  irreducibility.  problems.  the  for  computational  standard  a priori  basis  written  the  of  a p r o h i b i t i v e l y expensive  ALGORITHM  ff.],  (4.19)  algorithm.  MODIFIED LP  the  that:  number  affordable.  Markov c h a i n ' s  set;  , so  been made  so-called  method  columns of  of  i n the  been  the  the  basis  For  have  now  = Nj+2  simplex  is  LP  optimum  basis  the  s p e c i a l s o l u t i o n p r o g r a m was advantage  m  (NJ+1-NJ.) ( N J - N J ) /2  by  THE  ,  reduction  would  a n a l y s i s has  full  solve  =  searched  IMPLEMENTATION OF  A  of  fNj+l-Nj^  be  consequence,  F.  n = Nj+1  extraordinary  must  numerical  find  two  81]. free  32  variables the  first  (Nj+1) a  which  will  complete  basic feasible  solution.  (the s l a c k v a r i a b l e  significance  which  the  first We  have c h o s e n  y ) , and  will  be  basis set, i e .  (Nj-4)  .  explained  the  yield  variables  This choice  has  i n the next  chapter  a  equally  (see V - E ) . Besides important sparsity can  be  the p r o p e r t y  practical of  the  as  is  in  compacted  manipulations sparsity sparse the  (though  .  In  because  can  be  fact  The  extreme  this  t h e number of  very  total  matrix distinct  number  efficiently  method w i l l  preserve  and  s t r u c t u r e s [GUST 72]  can  be  the  some d e g r e e  Consequently,  of  stored  LU-factorization  super-sparsity).  a  LU-factorization  standard  advantage  of  "symbolic"  sructure  In  the  We  of  standard  used  throughout  (N-j-x N j )  have  used  u s i n g an  step  s t r u c t u r e of  submatrix  an  of  A  is  initial  the  steps  we  of  find  t h e LP , call  Then  take of  sparsity with  this  factorization i n [GUST again  (4.17). it  to  Sherman's  changed  matrix.  based  step  a d a p t a t i o n of  algorithm given  factorization i n the  basis  numerical  basis matrix  algorithm, modified  (a s i m p l i f i e d  factored  purely  performed,  peculiarities  initial  [SHER 7 8 a , b ] ) t o d e t e r m i n e  the  the  the  elimination  sparsity.  of  information finally  Gaussian  of  factorization  NSPIV p r o g r a m  the  data  (4.17) i s t h e  compared w i t h t h e  71].  simplex  not  LP  perhaps  computations. The  on  small  [KALA  of the  the  matrix  Such a m a t r i x  form  matrix  of  super-sparse  very  nonzero e n t r i e s .  irreducibility,  aspect  coefficient  classified  coefficients  of  A,  72]. some  In  are  useful  particular  , (which  forms  by  33  far  the  largest part  dominance  by  columns.  proceeds along t o be  the  numerically  employ  any  facility  rows and  stable  matrix.  to minimize  where t h e r e  be  the  is  u s u a l l y a worthwhile  reduce  permutation order the the that  of  A,  columns. this  row  of  operation M|M|2  Kotiah's next M|M|4  of  the  final  published  NPP  we  one  in  time, at  2-class  LP  queue.  queueing  for  A  by  a  in  applied  program 77]  for  numerical model.  it  greatly  efficient and  column first,  likewise for  order a  =  very  f a c t o r of  discussed  but  i s placed  of  results  ordering  can  An  so on; t  the  in locations  row  row  of  selected  process,  in t h i s  solution algorithm.  [KOTI  these  be  column  the  last  the  n  , with  costs.  s e c o n d , and  least  The  results  T  then  and  which the  p r o g r a m , we  apply  may  a row  memory  reversed:  i n t o the  FCFS  chapter  and  modifications  incorporated  n  not  permutation n  II A,  need  Furthermore,  nonzero elements  column p e r m u t a t i o n  the  symmetric  which  require  interchanges.  found e x p e r i m e n t a l l y  and  nor  s i n c e a good o r d e r i n g  i s placed  in execution  All  the  We  strategy  i s a somewhat h e u r i s t i c  time  row  then  Finding  search  i s simply  algorithm  permutation  f o u n d t o be  second-last  reduction  been  was  The  i s , on  "fill-in"  execution  i s guaranteed  A,  zeros.  reduce  pivoting)  any  c r e a t i o n of  to  (no  column  , that  diagonal  LU-factorization  s t a b l e on  The  were o n l y  this  and  exhibits  an  elements  pivoting  row  will  matrix)  [REID 7 4 ] .  c o l u m n s of  permutation solely  diagonal  f o r dynamic  basis  Therefore  complicated  LU-factorization the  of e v e r y  1000 large  ten. s e c t i o n have  To  i t to the  test  the  s o l u t i o n of  successfully duplicated the  system.  techniques The  In  to solve  effectiveness  the the and  34  efficiency  of  the m o d i f i e d  algorithm  will  then  be  assessed.  35  V.  A.  RESULTS  SYSTEM PARAMETERS We now p r e s e n t n u m e r i c a l r e s u l t s  of  the  multiserver  correspondence communications and  type  The  mean  ((,,)•' X,  2  between system  times  numerical  are  2  of  - A) t h a t  (it ) "  type  of  thereby defined  a  ±  may  1  minutes  instead  be  (from Appendix X. / O_L  Because type service o ,  of incoming  of  system  2  order  of  customers  resources  in  and t h e  Recall  from  ,2) , of  (5.1)  incoming  customers rates are  D)  a_2_  "\  t>2  )  any  type  have  .  (5.2)  convenient  on  average  1 customers,  do n o t d i r e c t l y  between  t o have t h e s y s t e m ' s  rates  have  dimension  unit  of time;  f o r example.  2 customers  requirement  are  f o r each  p  a,.  f i t a l l of which  2  of seconds  +  1  X,, X , m i measured  Rather,  A l l mean a r r i v a l  2  S \V  (time)" ,  1  fraction  (oi+o =1)•  -  types  intensity  (i=  ±  i s the  type 1  define  X / X  i  since:  r a t e parameters  the  respectively.  s e c . The mean a r r i v a l  t o t h e system,  Then  2  p  The  and  customer  specified.  case  To make t h e  model  two  traffic  1 arrivals  X = X,+X .  type  0  1 2  we f i x t h e  i n general are  these  directly  ±  which  =  1  2  o =  so t h a t  queueing  of  not  solution  proportion  this  system.  a s d a t a a n d v o i c e messages  = 5 s e c , and X  NPP q u e u e i n g  s = 4 server  i n t r o d u c e d i n c h a p t e r I we i d e n t i f y  customers service  and  (III  2-class  f o rthe  total  the  times  the  the proportions o , ,  reflect  two t y p e s .  service  24  time  the  division  F o r example, i n allotted  equally  36  there  must  customer. the  be We  24  new  type  formalize this  fraction  of  c u s t o m e r s of t y p e  ( £ i  +  *i= as  customers  (from Appendix  (5.1  =  - 5.4) »,  Then,  various  can  show: (o  the  2  ends  = 0.5  a,  to serve c l a s s  i  1  (5.4)  .  (5.5)  when d  = 24/25 = 0.96  between  curve  £,  begins with  at which the  (M/>2)'  =  1 + For  the c u r r e n t system  to  Figure  1  we  see  w h i c h a l a r g e change  at  slope  .  o,  and  for  a = ty=0  with  y  slope  when  a«  >  a,*  n /f l  n^/r<2  .  In  i s unity, o,*,  clearly i n o,  .  2  (Y,/^) ' 1  = 24,  2  /  is  and  o,*  that there  = 0.83  does the d i v i s i o n  the  s y s t e m s a n a l y s t i s more  of a c o m m u n i c a t i o n s f o l l o w s then,  both  sensitive  of work w i t h i n t h e  However,  In what  Referring over  p r o d u c e s o n l y a s m a l l change i n  become  user  .  i s a wide r e g i o n  £,)  while  (5.6)  2  (as m e a s u r e d by  the  serving  by o,*  Only  ]"  2  c ^ p ^ l  at of  as  (5.3)  system  )/(a,n )  M  Each  i  value  the  relationship  »- /i>2 .  H 2 / M 1 and  spent  (i = 1 ,2).  ±  [1 +  1 shows t h e  ratios  between, given  (s „ )  f o r t h e above example, Figure  slope  X. /  =  (i=1,2)  ±  ("work")  2  D),  ±  we  p  type  ( i = 1,2).  P  t h e work e x p e n d e d by  P ±  e a c h new  ) «  1  ±  />  Using  =  for  defining  resources  P/  Identify  i  0 2  arrivals  n o t i o n by  system  i  1  system  to  changes  parameters w i l l  be  a,  in  interested  i s more f a m i l i a r  system  with  specified.  in  . p  1 f  o,.  37  Figure  1 - Relationship  Between P a r a m e t e r s  and  o,  38  B.  THE  STEADY STATE PROBABILITY DISTRIBUTION  We  first  objective number with  d e t e r m i n e upper  functions  in  the  {Z }  system: n=  l o w e r bounds f o r e a c h o f  corresponding to  k  the t r u n c a t i o n  and  the  p ( n ) , n=0,1,2,... n  for  p(n)  the  the  distribution  , n + 1.  Recall  c  infinite  of  set  of  that  balance  c equations,  t h e LP  to  ( s e e IV - B ) .  n=  n +1 £  probabilities  (4.17)  includes In  terms  of  f o r which  the  2  Figure  2 shows t h e upper  the case  />=0.7, o, = 0.B0,  connected  scale by  of  this  and  for  continuous  representation  (s = (q = 2  matter  what s e t o f p a r a m e t e r s  analysis system  the  sums  given  The  be  c  the  .  The  the t a i l  present  queueing  system.  77]  i s on a are  a histogram  characteristic end  in  p(n)  points  strictly  most o b v i o u s on  plot  discrete  of t h e  some  (p,c,) are chosen.  i n [KOTI  A  of t h e M|M|2  upper  degree  Neither more  no  is i t  detailed  FCFS  2-class  t h e same b e h a v i o u r .  a characteristic  (p (n)} u  particular  than that  reveals  Such and  to t h i s  seems t o  n =25  though  flare  This  n > s s-s,) n-s-q,)  l o w e r bounds o b t a i n e d on  curves,  bound.  specific  and  clarity  i s t h e upward  feature  state  2  2  £,=0.14,  s h o u l d be u s e d .  curve  up  0 < n < s ( s = n-s,) (5.7)  2  2  logarithmic  0  2  2  for  n=  individual  P ( s , s ; q i q ) we d e f i n e : n E P ( s s ; 0 0 ) s,=0 n-s s E E P ( s , s ; q, q ) q,=0 s,=0 1  p(n) =  x±  states  a r e computed.  arises  from  t h e way  i n which  T h e r e a r e no c o n s t r a i n t s  (p^(n)}  imposed  on  1  39  Figure  2 - The  Distribution  p(n) 0.14)  for  p =  0.7,  o,=  0.80,  40  n +1 I P > ) n=0  n +1  c  c  ,  p (n ),  optimum  linear  a  Consequently, a  general  bounds In  tendency  to if  (n +1) n  improve.  of convergence  obtained  n =20, w h i l e  has  a , = 0.95  d i f f e r e n c e between t h e  p p,  Figure  tighter  be which  0  for  n  increases.  p(n )  where  0  poor  indeed.  held  constant,  be  said  We  n  0  In g e n e r a l , t h e bounds  later  compare  Figures  about  this  n  for less  Figures  o,  a fixed  cost  (smaller  For a f i x e d  (or  B,)  with  the  possibility  for  n  n even  when  Figure  for  2 a n d 3.  when  />=0.5  is  4  c i , n ) n made  3 a n d 4.  though  complicated. p  that  and  o f t h e bounds o b t a i n e d  behaviour,  a  are f o r  character  with  p(n)  cases  ($,=0.14),  observe  bounds a r e o b t a i n e d  general  more  of these  a,=0.80  bounds a r e o b t a i n e d  compare  geometrically  3 has  1  inconsistent  show t h i s  n  More w i l l  (»3 =0.44).  tighter  The  with  p ( n ) . Both  i s decreased;  smaller;  bounds  as  (see V - F ) .  for  c  generally  for  relative  of  3 and 4 a r e f u r t h e r e x a m p l e s o f t h e u p p e r a n d l o w e r  and  may  the r e s u l t  the  i s increased  c  0  bounds  not  i s only  u  c a n be e x t r e m e l y  c  Figures  and  i n {p (n)}  t h e upper a n d l o w e r  p(n ) will  concept  when  ( s e e IV - C ) .  u  near  i s the  0  problem  flare  for  p^(n ),  programming  ( i e . ( p ( n ) - p ^ ( n ) ) / P^(n) ) t o i n c r e a s e  however, for  o r e a c h minimum,  0  t h e upward  some c a s e s  is  u  unique  ,  u  n=0  b e c a u s e e a c h maximum, of  Z p (n)  p(n)  varies  "large".  Many q u e u e i n g  systems  the exact  expression  An example n ^ s.  that  f o r p(n) i s  i s t h e M|M|s  f o r p(n) FCFS queue,  41  ]0  15  NUMBER IN  Figure  2(T  SYSTEI  3 - The D i s t r i b u t i o n p ( n ) f o r p = 0.5, o,= 0.80, (/»,= 0.14)  42  io-i  p = 0.5 a ,=0.950 =0.442 n =2Q 6  in-I  >-  CQo CC-" CD O c r LO-I •_  —i 10  1 15  1 20  25  30  NUMBER IN SYSTEM  Figure  4 - The D i s t r i b u t i o n  p ( n ) f o r p = 0.5, o,= 0.95, 0.44) '  43  C.  MEAN WAITING TIMES 1.  Def i n i t i o n  An the  important  time  before  customer  being  waiting suited the  a  p e r f o r m a n c e measure of any of  served.  times  mean w a i t i n g t i m e Law  [KLEI  where E ( q )  continuous  =  but  the  In  terms  system  i n the  is  queue  distribution  present  LP method  the average w a i t i n g  time.  i c u s t o m e r s by  W,  i s best Denoting  we  ±  of  have  from  p.17]: E(q. ) / \.  ( i = 1 ,2) ,  i s t h e a v e r a g e number of  i  queue.  entire  of c l a s s  75,  W.  c l a s s must w a i t  interest,  t o o b t a i n bounds on  Little's  a given  The  i s of  queueing  of  the  type  i  (5.8) customers  state probabilities  P(s,  in  s ;  the  qi  2  q ) 2  then:  W.  =  \  1  with  ±  qi q is  expressions represented  one  (5.9)  the  and  This  implementation  infinite Z(W ) i  upper  sum to  limit  Here to be  for  the  n= the  of we n +1 c  = s,  W  i  sum  and  s ;  the  i=1,2  and of  p(n).  , and  (n +1).  2  . between  Each p(n)  a finite  same  define given Then,  of in  (4.11)  remedy. the  W  i  can  was  with  is  an when  being  Truncate  the  be  state  ( I V - D)  objective  i n (5.9)  the  number of  representation  the  (5.9)  q )  difference  normalization  apply  q,  2  same p r o b l e m o c c u r r e d  expression  r e p l a c e d by  P(s,  ±  important  (5.7) as  2  whereas t h e e x a c t  series.  considered.  s,+s  very  exactly  probabilities, infinite  2  s I q s,=0  ±  = n-s,  +  There  n-s I q =0  E n=s+1  1  the  function infinite  44  W.  >  Z(W.)  The  LP method  the lower be  i s used  right-hand, bound  (if n  fact  not  relative large W  be  side  an  of  so t h a t  (5.9).  Then,  true  choosing  of  upper  a  and l o w e r  W  W^OT-M) very  section 2  n  nearly  1  we d e t e r m i n e and  respectively.  1  an  M|M|s  Then  from  W (oi-»0)  =  0,-^-1  entering type  2  an M|M|s customers  choose  n  c  approximation to  The  ±  be d i s c u s s e d  will  problem later  of  i n the  1  .  values  I t i s easy  i n these  Po s„ ,  cases  type  1  for  the  or  both  t o determine system  type 2  is  system  I  (S/>)  k=0  k!  W^d-^O),  (5.11)  (sp. ) s! s  \1~P2  s-1  To c a l c u l a t e  on t h e  t h e LP s o l u t i o n s  the l i m i t i n g  S(i2  Po =  in  [GROS 74 p . 9 8 ] : =  where,  to  W.  0, o  homogeneous  vMc.-M)  2  for  will  o ->  Cases:  and W ( o - » 0 ) because 2  careful  purposes  c  may  (V - F ) .  0,-^0,  as  be  bounds  enough"  The L i m i t i n g  and  We must  as i t c o u l d  a t a l l , depending  ±  of  serve as a  t h e maximum  i  2.  this  n o t be a s t i g h t  Z ( W ) becomes a v e r y c l o s e  on c o n v e r g e n c e  W,  The minimum w i l l  f o r Vl  bound  for practical  "large  (5.10)  On t h e o t h e r hand  n,.  section  In  (5.10).  upper  magnitude  .  t h e maximum a n d minimum v a l u e s  f o r W.^ a l t h o u g h i t w i l l  enough  provide  to find  were g r e a t e r ) .  c  (i=1,2)  i  1  (5.12)  r -'1  k  imagine a  ( S p )  (1-P)  a r e i n the system,  s!  single  homogeneous t y p e 2 s y s t e m . this  (5.13)  S  type  1  No m a t t e r  type  customer how many  1 customer  will,  45  because and  i t Was p r i o r i t y ,  i s guaranteed  waiting  time  go d i r e c t l y  the  next  i s d e n o t e d by  w  free  server.  then  1f  E(w,|n) =  t o t h e head  Therefore,  E(w,) = =  We d e f i n e From  1  we o b t a i n  calculation  Consider  a single  1 system. must  (s/> ) (1 - P ) s!  2  i s somewhat  type 2 customer  until  the  entering  does  not  queue  i t has a chance  Let  t i m e be d e n o t e d by  waiting  exactly 223]  the  for the behaviour  homogeneous service using  same a s t h a t  queue.  as long  A  as there  an a n a l y s i s  a  w  2  2  > 0  the next This  2  an  Cooper  .  M|M|s  declines shows,  (5.15)  SUy  J 0 [[(1-p,) s,.,]E[ E ( w | n ) ] E ( w | n>s) P r ( n > s ) . 2  We d e f i n e  in  i f f n £ s, t h e n : 2  E(w ) = = 2  W (c,-»1) 2  2  2  = E(w ). 2  is  that  E(w |n) = Therefore,  server.  situation  i s one w h i c h  1  2  free  [COOP 72, pp.220-  a r e customers w a i t i n g .  w >0) =  and i n  empties of type 1  customer  customer  ( , - P , )  w  priority,  by Cooper  "polite"  polite  .  o f t h e M|M|s busy p e r i o d , E(w |  Since  2  difficult.  an M|M|s homogeneous  have  t o occupy  discussed  of  more  entirely  customers before this  (5.14)  2  2  1  customer  .  s  2  of W (o ->1)  This  wait  P r ( n > s ) , and t h e n :  pp Su  fact  .  E[ E(w,|n)] E ( w | n>s) P r ( n > s ) .  W^oi-^O) =  type  and:  V M d - ^ O ) = E(w,).  [GROS 74, p.96]  The  line,  customer's  i f f n > s,  n < s n £ s  1  2  the  If this  w, > 0  J 0 | (sx )"  of  1  n < s n > s .  46  Again  using  P r ( n > s ) we  have:  W (o ->1) = 2  There limiting p  :  are  values  of  It  then  define  The  four  1) 0)  =  W,Ui^ W,(o,-»  1) 0)  =  M 2 u,(  (5.18)  f o r these  3.  Waiting  Now  we  two r a t i o s  that:  R, > 1  for  0 < p < 1  R  for  0  <  2  1  <  of w a i t i n g  p  <  time,  W  i  u  2  /  u  , )  (a,—>-0),  W (a ->1), i  two p a r a l l e l  }  (R -1) W ^ C H - ^ O ) ,  and  2  1  lines. vertical  W,(a,-»0).  Time  present  Results  the  computed  upper  and l o w e r  p l o t t e d as a f u n c t i o n of the  parameter  bounds on p,,  for  cases: Figure  The.  results  from  also  shown.  These w i l l  5 6  p = 0.7 0.5  n = 30 25  7  0.3  20  simulation  at  using  (5.19)  (1 -  a, ( o r £ ) form  slope  following three  calculations  as:  2  2  l  have  W^^  these  (5.17)  (R,-1)  of  Making  1 ( 1-/))  lines  values  for fixed  =  These  the  R  that  = fi •  >  2  R, a n d  (5.2)  from  1) 1)  when p l o t t e d v e r s u s  time,  observe  the four  W (c,-» W,(o,-»  i=1,2,  waiting  r e l a t i o n s h i p s between  =  extreme v a l u e s  separation  (5.16)  W ( o i - » 0) W, ( - » 0) W,(o,-» Wj(o,-»  c a n be shown  s  i  /> (oi~ 0)  2  =  2  First and  0  R  .  i  = p ,  we  R, =  W  .  (sp,) (1 - p ! ) s!  some i n t e r e s t i n g  /i,(or>1)  substitutions,  Po s»i,  1  s t u d i e s of t h i s  be d i s c u s s e d  the  c  extreme  the techniques  later  points of  .  queueing in  system a r e  s e c t i o n D.  Pi=0,  section C(2).  =  The  are exact A l l  other  47  48  Figure  6 - Waiting  T i m e s as a F u n c t i o n n = 25 c  of  0,  :  p =  0.5,  49  Figure  7 - Waiting  T i m e s as a F u n c t i o n n = 20 c  of  fi\  :  P =  0.3  i: 50  I values t h e LP  of  the  have been o b t a i n e d  ±  (4.17).  0!=  and  W  0.99  Numerical to  illustrate  known l i m i t i n g  the  graphs,  solutions  cases  the o n l y  u p p e r b o u n d of  p=  0.7  t h e u p p e r bound of  known l i m i t i n g much h i g h e r  n  W  fi,—>1  as  2  value  W  2  were computed  1  they  As  can  failure  of  this  £,=  necessary  of 0.01  approximate seen  from  approximation .  i s so  that a numerical  p,=  be  p > 0.5  0.99  solution  for  pi = 1 .  , for  for  2  W (o —M)  would be  c  fi,=0,  significant  the  numerical  the degree t o which  of  is  through  In  far  fact from  solution  for the  with  t o o b t a i n a more u s e f u l  a  upper  bound. To  generate  selected W,  to ensure  and  0 <  W  < 0.2 it  proportion t o be  .  waiting  be  time  namely  (smaller  n ) c  For  of  cost  the of  also  that lower  p and  (higher n ) c  bounds the  be  is  numerical  thus  together  of  much  very  wide  0 < o,  ^ 0.86  expression  (at l e a s t  it  range .  is  generally  region interest  of  a,  (the  t h a t the e r r o r W.^  (5.9)  n  c  due  could  region). by  of  These  the  p(n)  less  cost  and/or  o n l y by  i n t h e LP  (4.17). linked  These  each  the  obtained at  p  was  c  In a d d i t i o n ,  given  of  obtained  solution.  n  physical  apparent  bounds a r e  directly  in  for  i n the  show what was  values fit  bounds f o r  l a r g e to ensure  tighter  bounds w i l l  equations  of  exact  neglected  with  fixed  numerical  the  results  graphs,  a  messages):  sufficiently  t o t r u n c a t i o n of reasonably  to  is  the parameter  lower  close  region  corresponds  chosen  u p p e r and  reasonably This  of d a t a  i n F i g u r e s 5-7,  that the  were  2  because  had  the data  true  that  increasing Greater with  topics  the will  the  better number  convergence computational be  discussed  51  later be  i n s e c t i o n s F and  a costly  can  be  placed  discussion results D.  o p t i o n , and i n two  will,  G  .  may  very  A more e x t e n s i v e not  required  solution could if  some  faith  helpful empirical observations.  however, be  have been  even be  LP  deferred  until  after  the  This  simulation  presented.  WAITING TIME SIMULATIONS Computer  performed  simulations  f o r two  of  t h e M|M|4  2 - c l a s s NPP  system  were  reasons:  (1)  To on  verify the v a l i d i t y of t h e mean w a i t i n g t i m e s .  (2)  To compare the relative cost and quality of results o b t a i n e d w i t h s i m u l a t i o n s as o p p o s e d t o n u m e r i c a l s o l u t i o n s u s i n g t h e LP method.  The  simulation  confidence c%  results  bands a r o u n d e a c h  confidence  variation range  of  interval  the  will  t i m e s out  contain  of  every  simulation  100  results  independent  batch  simulation  run  customers are  length batch making  run  is  (ie. the the  the  Figures  "measured" mean  waiting  calculated such that  true value  of  the  from on  now  made,  the  in  time.  A  the  given c  which  of  analysis  the  [FISH 7 8 ] . a the  same number of  quantity  long  95%  measured q u a n t i t y  very  interest  enough, s u c c e s s i v e  large  of  "successive A  system.  d i v i d e d i n t o a c e r t a i n number of the  by  statistical  average  have c h o s e n  technique  to pass through  each with  5-7  bounds  simulations.  a v a i l a b l e we  means"  allowed  batches  the  s e v e r a l methods f o r s t a t i s t i c a l  is  mean of  obtained  in  data  such  numerically  indicated  is  simulation  From among the  long  are  the  single number  of  This  very  b a t c h e s of  equal  customers). i s then batch  From  obtained. means  each By  become  52  statistically using  independent.  the  related Then,  C  statistic  k  o b t a i n e d on  standard the  state  system.  Therefore  into  final  the  results  of  first  GPSS  optimizing produced the  by  into  It  20  is  and 12  batches  usually  times  are  considered.  (customer  waiting  confidence  intervals  results  indicate,  narrow  as  of must  p and be  simulation  the  c o u l d be  must  the c o n f i d e n c e  the  width  the  in Figures  runs,  be  of and  a  each  5run  be  intervals like.  desired,  before  of  of t h e c o n f i d e n c e  running events  As  the  everywhere  If for certain then  is  acceptable  obtained. a r e not  Markov  advantage  number  observed  to  specialized  when p r o g r a m  large  can  effort,  s o l v e the  whatever lost  a  f o r t h e means  better r e s u l t s are  borne;  aid  However,  a systems a n a l y s t might 0!  by  customers.  Generally  times)  the  simultaneously  the data  i t i s t o s e t up  effort  the  in  compiled  with  system.  i n programming  and  i n terms of programming  than  empty  introduced  written  easier,  language  gained  be  are The  i s a completely  was  Therefore  4000  simulation  levels  s t a r t - u p behaviour,  76],  different  system  means.  quantity.  E a c h s i m u l a t i o n run  2  queueing  the  measured  itself  [BOBI  simulate a  c h a i n model of  confidence  run  closely  discarded.  W.  of  i s tested  batch  b i a s which might  program  W,  95%  transient  are  GPSS/H.  of  neighbouring  the  any  the  language  for  results  of  independence  p.238], a q u a n t i t y  simulation  batch  compiler  data  mean  to prevent  simulation  specialized  between  every  results  the  The  divided  of  78,  techniques,  overall  initial  d e g r e e of  [FISH  to the c o r r e l a t i o n using  7 are  The  greater  intervals  as  values costs will  on  53  average decrease only  as  N~  where  1 / 2 f  N  i s the  total  number  of  observations. E.  COMMENTS ON There  THE  are  theoretical,  several  w h i c h can  waiting  time graphs  1.  Empirical  Combining bounds f o r  for  be  that  the  the  may  be  used  the  LP  solution algorithm.  values This 0,  use.  for  W,,  has £  , a region  become e v e r These inexpensive  initial  more two  basis  empirical  character  and  of  the  the  numerically  conclude  fact  bound  t o be  reasonable  near  too  the  model,  the  the  p(n)  where a c c e p t a b l e  initial  for  by  s o l u t i o n s of  objective  and  be  observation  generates  generally true  useful  work p e r f o r m e d  f o r LP  that  true  large to  second e m p i r i c a l  (IV - F)  the  is especially  have o b s e r v e d  in  most of  very  is often  e l i m i n a t e much of We  with  obtained  the  basic minimum  functions. p > 0.5  c o m p l e t e LP  , and  solutions  expensive. observations  numerical  times  may  upper  specified and  2  7.  and  empirical  chain  been o b s e r v e d  0.1  waiting  Markov  W,  6,  Furthermore, a  to v i r t u a l l y  solution  the  l o w e r bounds a r e  This  practical  feasible  about  with  we  computed  values.  particular  data  times,  of  this  5,  both  Observations  i n which case  2  made  simulation  state  W,  observations,  in Figures  waiting  confidence steady  WAITING TIME RESULTS  seem  to  approximation  W: ±  set given  Solve in  the  to  allow be  linear  (IV - F ) .  made system  Calculate  a convenient for  the  mean  (4.17) w i t h W.  and  and  the  assume  54  that  these  addition,  quantities  are  procedure,  queueing  is  No  expected.  this support  so why  not  only  i n the p a r t i c u l a r  the  general  classes.  priority,  their  VJ  of  common w i t h In  expressed  W^^  for  with  t h e M|M|s  solely  assignment  any 0,  which  shown  less p  and  Figures  that  of a t y p e  p,=  but  £,  1 .  that .  rate  is  lies  also  5-7  depend with  on  has  in  They  queue  at  p and cannot  the case  Although  would  B , = 0  the in  queue.  FCFS queue w i t h  w a i t i n g time  the  more  both  u .  of  However,  with a p r i o r i t y  In an M|M|s  2 M|M|s  enter  answer  than  p , a s i s usually  of a homogeneous t y p e  service  The  of p r i o r i t y ,  is  the average  1 queue a t  2 arrival  at  non-preemptive  decreasing  that  not  1 c u s t o m e r s have  in  customer c l a s s e s ,  may  heterogeneous  times  i n t e r m s of  System  with  FCFS queue t h a n  i n the system.  average  found  1 customers  type  systems  given  two  effective  chain  results  decrease?  queueing  waiting p and  with  mean number  i n the  mean w a i t i n g t i m e  general,  increasing  of  is  Markov  been  vs.  ±  W,  Because type  customers,  variation  does  This  cases.  decrease  slight,  customer  has  in  evidence,  particular  B ^ i n c r e a s e s more t y p e  the  nature  empirical  i n a Non-preemptive P r i o r i t y  As  while  bounds, and  unknown t r u e v a l u e s .  on  i t s extension to other  system  2  to  theoretical  relatively  type  to the  g e n e r a l c h a r a c t e r of t h e  be  of a l l lower  solely  only  W a i t i n g Times  The  the  it  apply  model.  2.  first  as  to  would a l l o w  first  reasonably c l o s e  based  constrained  are  ,  u  , be  f o r the the  same  range  from  down  to  p i s constant,  the  r a t e c o n t i n u o u s l y i n c r e a s e s from  s>»2  55  to  SMI  »ii/c2 = 24 seen  0,  as  increases.  times  Therefore,  than  the value at  though  1 customers 2 customers  w a i t i n g f o r type  than  they  waiting  behaviour  i s a direct  customers  with  reach  result  shortest  situation,  to  of  average  however,  the  the  p increases.  customers  will  priority than  on  server.  customers the  than  then  t o spend  customers.  *,  p > p*  for  types of customers  will  i n c r e a s e as  p < p*  the system  i  1  getting  there  average  waiting  wait  of t h e i r  of the  own  type p,  X.,  by  in this  the  i s dominated  priority  For  c o n t e x t , a good a s s u m p t i o n  C ( 2 ) by s e t t i n g W  R = 2  (c.-M) = W  1  of  both  increases.  customers.  ie.  just  , the w a i t i n g times  is  section  type 1  (5.20)  time.  from  , the  Since f o r fixed  t h o s e w i t h g r e a t e s t mean s e r v i c e  unproven  In  service  p Sn,  that  dominated  i>).  p, ,  expect  For  spend  d e p e n d s more on c u s t o m e r s  those  as the t r a f f i c  more t i m e  the  This  to  priority  p= p*  say  they a c t u a l l y  - X, = we may  they  service  (greatest  importance  Consequently,  non-priority  increases with  (5.11,  leave  priority  times  A t some p o i n t ,  b e g i n on a v e r a g e  t h e head of t h e l i n e  to  non-preemptive  intensity  free  equations  head o f t h e l i n e .  service  t a k e s on an e v e r - i n c r e a s i n g  a  is  T h i s c a n be  have p r i o r i t y ,  assigning  discipline  for  p, = 0 .  type  more t i m e  to  0,= 1  at  C(2) .  spend  this  time  , from  2  even  do  waiting  W ^ d - M ) and V) (a,->0)  by c o m p a r i n g  5.12) i n s e c t i o n  lower  The  by t y p e p > p*  2  customers,  , the system  Although for  p*  strictly  i s obtained  (5.18):  (d-s-0)  (i=1,2).  (5.21)  56  Both  equations  (i=1,2)  g i v e t h e same =  P*  For  the  current  1 ~  solution,  p* = 0.96, w h i c h  model  practical  significance.  Nevertheless  illustrate  how e x t e n s i v e l y  t h e type  long  service  times,  dominate  (5.22)  (n i > e 2 ) •  V Z / K i  i s t o o h i g h t o be o f  i t  does  2 customers,  the  behaviour  serve  to  with their  very  of t h i s  queueing  system. A.  CONVERGENCE OF UPPER AND LOWER BOUNDS If  t h e LP s o l u t i o n  simulation provide given  as  between  the  confidence  i s t o have an  a method of s y s t e m s a n a l y s i s ,  comparable  computed  technique  or " b e t t e r "  result upper  range  i s seen and  as  lower  o b t a i n e d from  we l o o k more c l o s e l y  results  bounds  of  the  LP method, w h i l e q u e s t i o n s o f c o s t  next  section. The  linear  increasing sequence  sequence of lower  constraints. i n form  exact  solution  the  of  solution  upper  more b a l a n c e  to the i n f i n i t e x^.  function  true steady  data.  results will  A  difference t h e 95%  In t h i s  section  produced  using  be d i s c u s s e d " i n t h e  technique  bounds  cost.  and  guarantees a  a non-  non-decreasing  bounds a s t h e LP i s s o l v e d w i t h more and more  Adding  closer  objective  programming  overall  i f the  over  be a b l e t o  i s s m a l l e r than  simulation  at the q u a l i t y  i t must  a t lower  "better"  advantage  equations  linear  Consequently  c a n be e x p e c t e d  state  we a d d t h e p r o v i s o t h a t  v a l u e as  n  b r i n g s t h e LP (4.17)  system  the  t h e bounds on a p a r t i c u l a r  t o converge c  (4.6) w i t h  increases.  the o b j e c t i v e  steadily To t h i s  f u n c t i o n s must  toward argument  be a b l e t o  57  be  expressed  using {x±;  probabilities probabilities  functions  infinite  subset  interest As class  a  finite  0 £ i £ Nj}.  (p(n);  objective  only  Into  of  of  the  objective  times  for  functions,  is  from  (4.17) and (C.2) a s :  m =  N  m =  [10 + 5 ( n - 3 ) ( n -2)/2.  the  the  computed  c  ,  x  n^ and  error  and  graph,  C(1))  + (n - 3 ) ]  c  i s roughly  c  type,  proportional  we p r e s e n t  bounds f o r W,  functions  by f i n i t e  Figures  and W  different  consider  truncating  Z(vO the  an  2  f o r the  first  in Figure  8 the  with  ever  that  the  i n t h e LP,  + 2  sets  to  expression  of  this  objective  9,  cost  functions  10, and 11.  class  of t h e i r  times  objective for  (5.23)  (see V - G).  of system parameters  t h e mean w a i t i n g the  '  There,  a r e p l o t t e d as a f u n c t i o n  2  truncations  is  .  the o v e r a l l computational  i n d u c e d by s u c h a t r u n c a t i o n  that  over  W.  recall  have  W.  at  to  .  before  bounds.  Recall  function  For  from  obtained  n= n +1. .  be  expansions,  must be a s s e s s e d  W  of  (/>,<»,).  had  infinite  r e s u l t s c a n be i n t e r p r e t e d a s u p p e r and l o w e r  example,  of  Two e x a m p l e s o f  , t h e number o f e q u a t i o n s  h e l p f u l t o know t h a t  three  approximated  the  m  this  class  + 2  Because o b j e c t i v e  the  interpret  c  second  for  the  be d e f i n e d  W,  show t h e c o n v e r g e n c e o f bounds f o r  of  n  To h e l p  t h e LP s o l u t i o n To  fall  p ( 0 ) and p ( 4 ) a s t h e LP i s s o l v e d  between  of  class  we have p l o t t e d  relation  also  state  state p r o b a b i l i t i e s .  n^ .  is  the  second  a r e those which can o n l y  greater  It  A  c  of  examples o f c o n v e r g e n c e b e h a v i o u r  computed bounds  given  this  Q£ n < ( n + 1 ) } .  t o us a r e t h e mean w a i t i n g typical  subset  Also  (V by  recall  58  Figure  8 - Convergence  o f Bounds f o r P r o b a b i l i t i e s p ( 0 ) , p(4)  59  Figure  9 - Convergence of W a i t i n g o,= 0.80, (*,=  Time R e s u l t s : 0.14)  p =  0.7,  60  0.5 a =0 . 8 0 0 P ,=0.142  p =  ~l 5  Figure  1 10  1 15  10 - C o n v e r g e n c e  o,=  1 20  ^  1 25  1 30 s i m .  o f W a i t i n g Time R e s u l t s : 0.80, (*,= 0.14)  p =  0.5,  61  Figure  11 - C o n v e r g e n c e o f W a i t i n g = 0.95, 0 1  Time R e s u l t s : 0.44)  p =  0.5,  62  that  t h e computed minimum o f Z(W ) w i l l i  for or  W .  On t h e o t h e r  ±  may n o t be an upper  truncation affect the  error.  hand,  ±  ±f  There a r e  thus  of  Z(W )  will  i  expansion  for  ZfVT) .  and more c o n s t r a i n t s decrease effect,  toward that  behaviour  there  the  to interpret  terms  true  value error,  maxlzfw.^)}  9-11 show a s t r i k i n g  to  2  shown  by  error  there , i s  no e a s i l y  max{Z(W,)}  maximum practical One  and  must o n l y  c  increases  added  the  t o the w i t h more  maximum  bound  is i t  f o r Vv\ .  i n the  convergence  The maximum o f Z(W ) 2  by t r u n c a t i o n  In  increases  numerical the  error.  Soon a peak  convergence p r o p e r t y of  values i s an  be c a r e f u l  as  dominant  bound  take p l a c e ,  contrast,  bound  indicating  factor. beyond  f o r W,.  t o choose  n  a type  betweeen  the  d e c r e a s e s . For  acceptable large  that  w h i c h we c a n say  Nevertheless,  o f Z(W,) s t e a d i l y  (as  Consequently  as the d i f f e r e n c e  entirely  t h e computed  n • increases  results),  point  to  the f i r s t  made n e g l i g i b l e  difference  steadily.  i s an u p p e r  purposes t h i s  First,  O n l y when  ±  h a s been  distinguished  minimum  W .  the i n t r i n s i c  i s always  c o n v e r g e n c e does  n  ±  2  precise  truncation  of  which  c a u s i n g max{Z(W )}, now an upper  decrease  the  for  2  maximum o f Z(W,) c o n s i s t e n t l y  that  forces  being  f o r W, a n d W .  r e a c h e d , a n d from t h e r e LP method d o m i n a t e s ,  of  a s an upper  seems t o be a f f e c t e d  W,  are  i s the tendency  o f t h e "bounds"  initially  for  opposing  S e c o n d l y , a s t h e LP i s s o l v e d  of t r u n c a t i o n  Figures  the  two  t e n d t o i n c r e a s e as  b e c a u s e more and more n o n z e r o  is  d e p e n d i n g on t h e d e g r e e o f  t h e c o n v e r g e n c e o f t h e computed maximum o f Z ( W ) .  maximum  safe  bound  t h e computed maximum o f Z(W ) may  for W  bound  a l w a y s be a l o w e r  behaviour.  enough s o t h a t t h e  63  two  curves  nearly  connecting  9-11  bounds o b t a i n e d  No  of that G.  for  useful  a  become  experience,  u p p e r and  observed  as  either  or  been  found,  of  t h e LP method of  analysis  convergence  characteristics  different  s e t s of p a r a m e t e r s .  relationship user  user  will  for a given  lower  decreases  has  the  ensure,  n  numerical  in Figures  few  section  be  able  s e t of  bounds w i l l  be  of  2-  the After  to s e l e c t  system  a  value  parameters,  computed.  addition, of  1.  LP  A very using  the  = m  function however,  we the  compare  (m  those  the  which a f f e c t  relative  costs  aspects  of  the  computational of  simulation  LP  cost. and  LP.  S o l u t i o n Cost important  simplex  executed  general  examines s e v e r a l p r a c t i c a l  program, c h i e f l y  solution  J  have  COMPUTATIONAL COSTS  solution  J,  the  least  which w i l l  c  This  In  Z(W,)  also  convergence  assess at  initial n  of  t i g h t n e s s of t h e  of  T h i s was  In c o n s e q u e n c e , t h e  have t o  system  t h a t the  increase.  concrete  however.  this  suggest  for a given value  p and  both  will  limits  horizontal.  Figures  7.  t h e computed  characteristic  a l g o r i t h m i s the average  b e f o r e an x n)  practical  iterations [LUEN 73,  number of  optimum b a s i c s o l u t i o n  LP,  experience  are  required  p.55].  i n w h i c h a l l but  In two  of  our  LP  program  iterations,  i s achieved.  shows t h a t on to  of any  optimize  average each  more s p e c i a l i z e d  the b a s i s v a r i a b l e s  at  For  a  least  objective algorithm are  known  64  a priori,  many fewer p,  parameters linear  fashion  n=  30  the  LP,  c  which It  computational modified A  LP  n  c  number of  more  LP  W  a  roughly  J = 6.5  is  that  through  (over  for  constraints  model  statistics  realized  by  the  parameters  the  given an  in by  enormous  use  of  p  the  from  This ),  1 r  new  basic  solution  function.  required  value  although  and  have  per  reduced  strategy  i n which  is  for  functions.  An  solution  optimizes  found  with  that  very  LP  algorithm,  to  to  the  function  close  summarize  the  above,  independent  To  further  tested  objective  for  total  be  listed  i s roughly  for a general  LP,  We  The  can  objective  functions  is noticeable.  J = m  specialized  task  number  parameters  c  search"  remaining  of  (n +l).  "parallel  iterations .  some d e c r e a s e  this  minimize a  set  a  (n^+4) o b j e c t i v e  1.5  (/>,  for  0 < n <  whenever a s i n g l e b a s i c  objective  number of  approximately  all  for a given  p(n),  required  employing  i s achieved  of  and  2  against  one  functions  W,  average  search  in  number of  s o l u t i o n must m a x i m i z e and  1f  set  the  has  average  (m=45), t o  queueing  been  iteration  than  reduced  i s the  savings  complete  1.0  m  On  ranges  6  c  from t h e s e  ):  optimality economy  that  J  n=  i s apparent  iterations  each  at  particular  objective  considerably at  for this  required.  found t h a t  J = 4  Recall  complete  p,,  have  are  technique.  different  {p,  we  from  (m=l929).  (5.23).  of  p,)  iterations  then,  of to  the  0.0  J has  1.5  when a  p r i m a r i l y d e p e n d s on  the  total  or  been  J = 6  J =  is  for  parallel  i s employed.  Computational iterations  cost  necessary  to optimize  a l l the  objective  number  of  functions.  65  The  only  matrix  a d d i t i o n a l expense  and  i t s LU-factorization.  significant functions  factor  (CPU  n >> c  as  actual  compiled  with  precision  Since  m  0.0  increases  the  or  1.0  very  performance,  time  by  as w e l l .  consider  execution  2.  and  mean  waiting  numerical large  with  i n Figures time.  Additionally,  there  required  24  cost  limited  FORTRAN  be  a  e  was  :  upper a n d l o w e r of  and  Single  when  double  bounds  precision  50%, and o f c o u r s e of  incurs program  :  required  31  objective  £  iterations  functions.  20 to  Total  V/8 c o m p u t e r .  Costs results  for  each  c o m p a r i s o n s o f s i m u l a t i o n and generality  because  a v a i l a b l e to users of e i t h e r may  for  p = 0.5, B = 0.44, n =  Simulation  Rigid  increases  n," .  in  except  9-11 a r e s i m u l a t i o n  s o l u t i o n are of  number o f o p t i o n s  initially  the  cost  to  As a p a r t i c u l a r example  It  c  FORTRAN-H.  19 s e c o n d s on an AMDAHL-470  A Comparison  Included  to  written  Use  a  (n +4)  execution  proportional  used,  about  s e t of  solution  compiler  the run w i t h  minimize  t i m e was  was  together.  (m=794), i n s i n g l e p r e c i s i o n . maximize  LP  , o r when t h e computed  execution  memory c o s t s  an  usually  number o f o b j e c t i v e  i s proportional  was g e n e r a l l y  not  the t o t a l  is itself  optimizing  close  is  the complete  of  s o l u t i o n program  arithmetic  were t o .be  extra  found t h a t  charges)  set-up of the b a s i s  small  we have  s ( s e e 5.23), t h e n c o s t The  near  .  2  a  With  memory m  only  This  optimized.  functions  time p l u s  roughly  unless  are being  objective  i s the i n i t i a l  large  difference  to develop the respective  computer  of  the  technique. in  effort  programs.  66  However, f o r c o m p l e t e n e s s we The from  s i m u l a t i o n data  runs  statistics LP  of  on  functions  computational occur  for  blocks  an  of  n  equal W,,  cost  the  following  f o r e a c h of F i g u r e s 9-11 4000  b e s i d e s w a i t i n g times  solution  objective  20  present  W  .  2  equal  we  t o one  of  and  of  n  To  No  other  place  the  c o n s i d e r o n l y the  precision  t h e above  25  gathered  each.  were c o l l e c t e d .  A single  somewhere between  were  customers  footing,  comparison.  30  .  solution  two with  s i m u l a t i o n s would While  numerical  c solutions of  two  slow,  f o r these  so  cost,  that  which  waiting  the  times?  better  bounds.  solution  £  The  W,  or  is  2  0.8), other  are  the  t h e LP  answer  the  W  of  c  S 0.2  wholly  cases  considered.  (approximate) .  of  by  We  equal  conclude a  For  execution  f o r t h e mean only  solution  answer  than  factor  answered:  unambiguous  the  a  sufficiently  be  i n w h i c h t h e LP two  is  better results  seems t o p r o v i d e b e t t e r r e s u l t s the  can  (4.17)  the is  separated  bounds  question  provides  o,=  For  c o s t over 0.9,  solutions  (p = 0.5,  10  whether  following  method  Figure  c,  values  i n c o s t , t h e c o n v e r g e n c e of  s i m u l a t i o n s and  equal  two  for  produces  depends  on  t h a t the  LP  simulation  r a n g e of p a r a m e t e r s :  p &  of 0.5,  67  VI. A.  LIMITATIONS OF THE MODEL Simplifying  any  modeling  system  the  assumptions  process.  under  study  computational  are necessary  d u r i n g t h e c o u r s e of  They a l l o w t h e o p e r a t i o n o f t h e to  methods.  be  made  amenable  Upon c o m p l e t i o n  physical  t o mathematical  of the modeling  i n the context  applicability  of the o r i g i n a l  of the present a n a l y s i s  physical  such  systems.  In a d d i t i o n ,  chain  equations  further  traditionally  a numerical  reduces  problem.  of a communications  c o n s t r a i n e d by some o f t h e a s s u m p t i o n s  solution  the p o t e n t i a l  or  process  s y s t e m s a n a l y s t must, however, r e - a s s e s s t h e a s s u m p t i o n s  t h e model  is  CONCLUDING REMARKS  of The  system  made f o r  o f t h e Markov  generality  of  the  analysis. P e r h a p s t h e most o b v i o u s provides  only  transient  behaviour  periodic  input  condition. relevant or  to  and  physical  state,  arrivals).  reality  independent  a  solution.  there  is  continuous-time  represents assumption  short  the  the  solutions  for  as the e q u i l i b r i u m Markov  actual  lengths.  a communications The  message an  times arrival  accurate  system  model  is  i n continuous-time,  interarrival  i s usually  message s o u r c e s .  packet  i s that i t  reality,  q u e s t i o n o f how w e l l  for  the  In  time-dependent  systems which o p e r a t e  relatively  when  o f t h e model  may be a s i m p o r t a n t  distribution  However, t h i s  state other  traffic  with  exponential  of  steady  The c h o i c e o f  t o those  steady  a  limitation  Even  in  t h e assumed (Poisson process.  representation  s e r v e s many e q u a l and  assumption  of  exponentially  68  distributed  service  justified.  times  may  I f a more g e n e r a l  required,  one o f t h e f a m i l y  would  have  numerical A LP  greater  of E r l a n g  second  economical  complexity  itself. that  and  LP s o l u t i o n  impossible.  is  model w o u l d  require  a large  be  well  assumption is  available  To  to  that  of  which  which  the blocking  a more c o s t l y  waiting  Unless  solution  of  Otherwise,  the  increasing  n  In g e n e r a l ,  the  renders  this  is  comment  modeling process.  advance  that  If  a Markov  a  chain  then  i t  t h e use of a l t e r n a t e  simulation.  always  violated  infinite  number, s a y customers.  functions  L' i s quite  by  a  physical  queue l e n g t h s .  L, o f  storage  When a l l  L  A  almost  f i n i t e Markov c h a i n  real  positions  positions are  from e n t e r i n g  small,  t h e LP s o l u t i o n r e q u i r e s  equations.  number o f s t a t e s  the  queue.  p r o b a b i l i t y n e g l i g i b l e , L i s chosen  the system  room.  in  messages a r e b l o c k e d  enough s o t h a t  with  require  although  number o f s t a t e v a r i a b l e s ,  allows  f o r waiting,  make  balance  possible  complexity  particularly  have a f i n i t e  arriving  such  consider  techniques,  system w i l l  filled,  times i s  a r i s e s from t h e demands o f  the increased  system  system  of s e r v i c e  F o r example, t h e number o f c h a n n e l s  particular  One  so w e l l  is still  may be made o f t h e e n t i r e Markov c h a i n  modeling  be  d i s t r i b u t i o n s may be u s e d .  model  s e t of c o n s t r a i n t s  s o l u t i o n method  might  not  solution.  ( s ) may be so l a r g e an  practice  representation  A c o n t i n u o u s - t i m e Markov c h a i n it  in  large  a s i f i t had i n f i n i t e an  exact  numerical  would n o t be e c o n o m i c a l .  a truncation  of the  s e t of  Because these b a l a n c e e q u a t i o n s a r e o r d e r e d (total  number  i n the system),  i t i s apparent  69  with  a truncation at  t h e maximum This  total  favors  forced  a  n = n , that L should  number  system of p o o l e d  positions.  The  Markov c h a i n  s t a t e space  B.  SUMMARY AND  a  storage, any  one  itself,  i s not  combined  voice  non-preemptive p r i o r i t y results  are  available  which  some  results  exist  analytical  distributions  t o be i d e n t i c a l ,  programming  technique  bounds  on  quantities  waiting  times  storage  suited  to  a  type.  of  LP s o l u t i o n because  M|M|s  either  used  interest,  First  model  communications messages.  No  systems of t h i s NPP  models  for  require a l l service  to  s = 1. obtain  most n o t a b l y ,  A  linear  numerical the average  class.  method c o u l d n o t of  data  or r e q u i r e  was t h e r e f o r e  of each customer  Markov c h a i n m o d e l . constraint  L  well  f o r queueing  2-class  form  the  f o r the data  related  original  as  and  The most c l o s e l y  Kotiah's  of  we have s e t up a Markov c h a i n q u e u e i n g  type.  time  type.  i n w h i c h any c u s t o m e r  queues f o r each customer  multichannel,  analytical  r e g a r d l e s s of customer  as  CONCLUSIONS  thesis  system, w i t h  interpreted  method o f t r u n c a t i o n , and t h e s t r u c t u r e o f t h e  separate  In t h i s of  i n queue,  t o queue may be a s s i g n e d  system with  be  c  the complexity  of a l l ,  be  applied  in i t s  and s t r u c t u r e o f t h e  the a d d i t i o n a l  normalization  (4.15) was a d d e d : n  c  + 1  E p(n) n=0 This  serves  to  which  the f i r s t  generalize  constraint  <  1  .  (4.15)  t h e LP method t o Markov c h a i n s f o r  (4.13),  70  s-1 I n=0 is  alone  insufficient  improvement the  i s the  Markov  B o t h of  (1 - n/s)  computational property  changes are  related for  thesis to  equation  condition  use  [KOTI  summation  Appendix D  is  of  77] the  counter-example  t o the  A second  heterogeneous to  the  p),  constant  W (o ->0), i  the  ±  time  on  results  are  the  mean  NPP  relations  predicted for  concern  s y s t e m s of in using  the  times  is  waiting only  through  given  pleasing  was  in  result.  (4.13) i s e q u i v a l e n t  to  of  We  with  serves  this  thesis  behaviour refer  is  in  a  especially  the  parameter  (at  the  limiting  values  particular  p = p*  change  further  in  the  illustrates  type.  LP  method  ensuring  negligibly  it  derived proof  time  this  state  a  result  The  steady  as  between  (i=1,2).  i s given  queue  system.  times  A proof  Although  the  intuitively  of  directly  c o u l d be  waiting  queueing  solutions  not  systems.  analytical  waiting  1  affected  and  when  is exploited.  valid  equations,  second  realized  which are  a  A  here.  technique.  (4.13)  mean  of q u e u e i n g  primary  bounds  of  behaviour  behaviour The  of  W (a -»1),  1  waiting  and  LP  p r o p o s i t i o n that  2 - c l a s s NPP  variation  studied  2 - c l a s s M|M|s  important  clarification  one  i t t o be  that  solutions.  a p p l i c a b l e t o LP  of q u e u e i n g  a more g e n e r a l present  the  shows  (4.13)  irreducibility  the  balance  In a d d i t i o n , t h e  (4.11).  of  of K o t i a h ' s  (4.13) w h i c h  in  ,  which are  several results  f o r a wide c l a s s  indicated direct  than  contains  our  savings  widely  Markov c h a i n m o d e l s o t h e r This  1 - p  =  to ensure acceptable  chain's  these  p(n)  by  to  t h a t the  truncation  determine computed error.  71  Herein an  lies  one  objective  exactly  function  i s the  error  were  be  always  Increasing reduces  the  exactly upper of  t h e LP  for  number  of  the  equations  to  functions  span  that  of  true  equations  number o f  which  time  Law  can  like  upper  (m)  be  p(n),  and  lower  state  probabilities.  be  expressed  becomes  the  A  t h e mean  requires  size  more  included.  an  and  second waiting  infinite  more  balance  LP means t h e e x p r e s s i o n s f o r t h e s e  objective  terms.  l e a s t the d i f f e r e n c e as  the  increasing  size the  of size  Adding  LP  objective  o t h e r as the  s u c h as  representation  the  probabilities,  variable  are those,  in  time  can  towards each  component  more n o n z e r o  at  studies.  truncation  For q u a n t i t i e s  functions  exact  state  bounds d e c r e a s e s benefits  each  an  the  be  truncated  p.240],  f o r t h e mean w a i t i n g  functions  which  a  Little's  75,  as a d d i t i o n a l e q u a t i o n s a r e  of o b j e c t i v e  times,  show  error  bounds c o n v e r g e  increases:  more c o n s t r a i n e d class  [KLEI  representations,  objective  lower  in  cannot  empirical  Although  more s e v e r e .  i n terms of a f i n i t e and  through  t h e number o f b a l a n c e  For  error  it  if  computed.  truncation  functions.  of  quantities  finite  be  expansion  h i g h e r o r d e r moments o f t h e w a i t i n g  much  however, w h i c h have bounds c a n  degree  not computed.  f o r these  would  infinite  unknown e x c e p t  r e a s o n why  generalized  an  the  usually  distributions  l i m i t a t i o n s of a n u m e r i c a l a n a l y s i s :  has  computed,  approximation This  of t h e  Nevertheless, between the  LP  effort:  were f o u n d  m.  r o u g h l y as  t h e upper  results and  increases.  lower These  o f t h e LP a r e g a i n e d a t  expense of a d d i t i o n a l c o m p u t a t i o n a l to increase  the  2  computational  the  costs  72  Compared w i t h provide  better  simulation,' the  results  at  less  parameters  p < 0.5,  a, <, 0.9  be  recommended  f o r the  a n a l y s i s of  region.  extrapolation exhaustive only  and  other  formal  suggest  These  with  the  are  two  (2)  the comparison various service As  those  of  results  range  simulation  could  of  employed,  outside the  of  use  of  render  an  Such h e u r i s t i c s  may  techniques  unnecessary.  particular  main  may  great  familiarity  Markov c h a i n  areas  has  model.  which deserve  with  compare effort  the could  of  in  chapter  Kotiah,  those  further  II,  Kotiah. it  Wolf.  study.  two  obtained  of  d i r e c t e d towards a  but  are  have employed  the  One  t o compare the  for  useful  to  Further  convenient  such approximation  might  probabilities  whose a g g r e g r a t e  our  alternate  methods.  search  s t a t e s whose i n d i v i d u a l  required,  Markov c h a i n s  using  two  with  numerical  particularly  the  chain  systems  main  interesting  I t would be  u s e f u l system approximations. somehow combine  the  would be be  Markov  multiserver  A l t h o u g h we  convergence behaviour a l s o be  infinite  solving infinite  which c o u l d  S e n e t a and  explicitly  for  of multiclass, disciplines.  S e n e t a - W o l f , and  a p p r o a c h of  not  heuristic  f o r t r u n c a t i n g and  method  to  is  to  approximate  systems o p e r a t i n g  s o l u t i o n techniques  discussed  techniques  be  use  found  are: t h e study' of models,  and  the  were  FURTHER STUDY  (1)  LP  The  method  analysis  SUGGESTIONS FOR There  .  over  t h e m s e l v e s , however, a f t e r  been a c q u i r e d  C.  Whichever  solutions  cost  of  this  LP  probability  are is  73  important. q ,  but  2  state  F o r example, with  d i f f e r e n t server  from  further  with  configurations,  queueing  fixed  q,,  i n t o the s i n g l e  priority.  those  employed  dependence  (fi ).  of  in W  ±  detail,  perhaps  realistically minimum  performance.  to a true  general  Limiting  thesis  could  of  s y s t e m might  making  the  number o f s e r v e r s  preemptive alternating only  similar  an to  be u s e d t o e s t i m a t e t h e  a single  communications  be made among  include  arguments  applied  multiserver  priority,  and  on t h e s y s t e m ' s m i x t u r e  by  could  comparison might  times.  this  Alternatively,  ±  priority,  A l e s s comprehensive o f mean w a i t i n g  cutoff  chain  p r o f i t a b l y be  a comparison  disciplines:  non-preemptive  o f Markov  of o t h e r m u l t i c l a s s ,  F o r example,  service  priority,  t h e m s e l v e s might  and c o m p a r i s o n  systems.  various  analysis  work i n t h e m e t h o d o l o g y  the techniques  the a n a l y s i s  the  of s t a t e s  2  solutions,  the  sets  (*; q, q ) . Aside  to  combine  model  customer  classes  be s t u d i e d  i n more  correspond  more  s y s t e m , o r by d e t e r m i n i n g  to ensure a given  level  of system  74  APPENDIX A - A COMPARISON OF NON-PREEMPTIVE PRIORITY ALTERNATING PRIORITY SERVICE D I S C I P L I N E S In  this  appendix  service  disciplines,  customers  (denoted  C(°°,1).  Recall  exhaustively, service.  only  and  non-preemptive  NPP), that  two  C(k,,k ) 2  and  the  C(°°,1)  service and NPP  NPP  switching function  system.  are properly exactly  following  we  the  means  that  whenever  specific  for  type 1  priority  queue  1  is  case served  one  customer  admitted for  disciplines,  general  alternating  fact,  quite  i s nearly when  the  different; i t is indistinguishable rules  for  queue  c h o s e n , t h e C(°°,1) s y s t e m c a n be made t o same  as  the  NPP  discipline.  assume f o r sake o f c o n v e n i e n c e , t h a t  work-conserving  identically  two  priority  are in general  In  compare  alternating  t h e p a r t i c u l a r c a s e C(°°,1) t h a t  from t h e  all  discuss  t h e n queue 2 has a t most  The  priority  we  AND  service n<s  disciplines  In  n>s  , because  should  function  .  queue 1  ,  arrivals  Figure  [  central controller  the  s  12 - S c h e m a t i c o f a 2 - C l a s s M u l t i s e r v e r System  x  servers  Queueing  75  To e x p l a i n t h e n e c e s s a r y of  the  diagram  interpreted Figure is  in Figure  assumed t o be a b l e  With  12 .  Each  r u l e s we make  service discipline  use  may be  a s a s e t o f r u l e s by w h i c h t h e c e n t r a l c o n t r o l l e r o f  12 s e l e c t s w a i t i n g  server,  queue s w i t c h i n g  as  well  this  customers  to  as  sense  for service.  the  The c o n t r o l l e r  idle/busy  state  of  each  t h e empty/not-empty s t a t e o f e a c h q u e u e .  information  the  controller  can  direct  waiting  customers t o f r e e s e r v e r s ,  switching  transitions,  represented  by c h a n g e s i n t h e s t a t e v a r i a b l e  and  operations  a l l other  queues i f n e c e s s a r y .  of the c o n t r o l l e r  are  Queue  assumed  to  i , be  instantaneous. In attends  the queue  controller  NPP  discipline  1 (i=l).  will,  for service.  then  type  a  controller  2  Whenever  i f queue  customer  1  is  I f queue  customer  returns  the  is  a  not  1  the c o n t r o l l e r  on  average  queue  switches  at this  a customer  finally  sent  a type 1  and queue 2  i s not,  served  ( i = 2 ) , and t h e  free  spends s l i g h t l y occurs  less  because  time the  a s soon In  need n o t be any f r e e s e r v e r s .  If  becomes i d l e ,  the  identical  a n d t h a t queue 2 i s n o t .  even  1 i n t h e meantime.  to  select  1 ( i = 1 ) t o queue 2 ( i = 2 )  i s i n queue 2 t h e c o n t r o l l e r  i n queue  the  (i=l).  This  1 i s empty  instant there  soon a s a s e r v e r  arrives  1.  from queue  i t s e n s e s t h a t queue  general  as  observing  normally idle  o f t h e C(°°,1) s y s t e m w h i c h . i s n o t  t h e NPP d i s c i p l i n e ,  as  becomes  empty,  immediately  to  controller  controller  server  1 i s empty  t o m o n i t o r queue  In one v e r s i o n  central  server,  reserves if a  i t t o be type  When one t y p e  1  served  customer  2 customer i s  the c o n t r o l l e r  returns to  76  monitor  queue  controller server the  1  (i=l).  would  have  1 customer  To  make t h e  priority  for  and  1  dependent.  That  to  queue 2  independently  and  only  service  NPP  service  Markov c h a i n the  as  described s,,  server  the  q,  to  of  switching  of  the  In  these  explicitly the The  queue  and  to  fact, simple  than  potential  turn  out  NPP  as  of i  to  be  system. select the  even n e c e s s a r y  in a  the  a  operation  state  i s understood  position  empty,  would  systems t h a t  once the  queue  next  d i s c i p l i n e would  by  the  queue 1  1 becomes  same o r d e r  therefore  of  from  f o r the  i t i s not  i s that  non-preemptive  rather  then  above  represented  a  service  switching  f o r the  Ci™,})  NPP  1 until  for  switch  rules  controller  reason  queue  when queue  i n the  the  1.  dependent  exactly  same c u s t o m e r s  as  the  those described  determined,  variable.  i n queue  c o n t r o l l e r should  have been s p e c i f i e d , t h e  completely state  The  model of  above.  observing  becomes a v a i l a b l e  discipline.  long  situation  would have s e l e c t e d  server  this version  c o n t r o l l e r be  (i),  made  i s , the  equivalent  Consequently, for  be  customer.  exactly  so  customers,  must  2  been  just arrived  controller  type  same  C(°°,1) d i s c i p l i n e e q u i v a l e n t  type  when a  this  first  became a v a i l a b l e  type  In  i s not  variable  to operate  as  variables  n,  state the  of  controller an  is  independent  77  APPENDIX B - THE As  a visual  balance  equations  transition crucially state the  a i d to  on  the  space.  state  the  it  diagram.  The  After  development  is  choice  s p a c e of  STATE SPACE TRANSITION  useful utility  of  state  of  NPP  of  such  variables  model  the  to c o n s t r u c t  some e x p e r i m e n t a t i o n the  DIAGRAM  a used  we  i n t o two  steady the  ,  2-dimensional,  with v a r i a b l e s  (s  (2)  n 2: s  ,  3-dimensional,  with v a r i a b l e s  (s, , q  rates at  (Q^  most  states  )  to  four  arrivals Forbidden  transitions  type  or  those  transition system.  13  and  diagrams  The  two  14  split  s )  indicated.  2  q ).  1 f  2  the  two  prohibited  transition  T h e r e can  state,  impossible  the  are  common,  and  one  set  multiserver  d i a g r a m s have o n l y  boundary are  this  1 f  conditional  each of  those  below  for  along  n  each  to  the  be  representing  customer  types.  by  service  the  (for  example,  no  s^O).  i  =  are  from  naturally  ( < 3 i Q 2 0) =  of  are  1 d e p a r t u r e s when Figures  states  transitions  departures  discipline,  segment, t h e  neighbouring  such  and  i n each  represent  pieces:  n < s  typical  space  depends  have c h o s e n  (1)  For  state  diagram, to  state  the  (s+1)  of  2-class  appropriately.  NPP  states  t r a n s i t i o n s between t h e  noted  state  two  space  queueing for  n=s  diagrams  78  Figure  14  - State  Space f o r n ^  s  79  APPENDIX C ~ SETTING UP THE BALANCE EQUATION COEFFICIENT MATRIX "A": AN EXAMPLE This  appendix  structure  of  example how truncated numbered  the  balance  the i n f i n i t e to  of  A  We  concerning  also  equations  show w i t h an  is  ordered  ( s e e (4.9) i n IV - C ) .  appendix  are in  the  the  order  space  of  and  The t h r e e they  are  text.  (1) Recall  that  we  found  multiserver  non-preemptive  dimensional  (see  system  of  balance  of  population  same  state  priority  system  However,  equations  in  increasing  the  III - D).  sequentially  the  details  equations.  form m a t r i x  i n t h e main  further  system  s e c t i o n s of t h i s  referenced Part  presents  the  one d i m e n s i o n .  to  facilitates  (2)  minimizes the e f f o r t required to t r i a n g u l a r components: A = LU (e.g. f i l l - i n of z e r o e l e m e n t s ) .  One  ordering  with  increasing  using  s  2  automatic  the balance  Figure  The  up and s o l v e a  must  be  ordered i n order  with result  equations  equations,  factorize A by m i n i m i z i n g  was t o i n d e x  increasing  with  which:  generation of the balance  satisfactory  n , then .  three-  n , but w i t h i n a group of s t a t e s  (1)  increasing  be  S t a t e s c a n be i n d e x e d  n , an o r d e r i n g s h o u l d be c h o s e n  found  to set  states  the 2-class  the states  q, ,  f o r the case  of  and  first  then  s = 4  (4.3 - 4.5) o f I V - B  into the  is  with  servers, seen  in  15.  This  diagram  displays  coefficient  matrix  Q  equations.  The shaded  T  the  for squares  upper  the  left-hand  infinite  set  r e p r e s e n t nonzero  corner of  of the balance  coefficients.  Figure  15  - Matrix  "A"  For  T\.=6, S=4  Servers  81  Indicated which n > s  along  n = 0,1,2,...  .  = 4 , display  a very  easily  seen  submatrices equation matrix only  t h e t o p and s i d e a r e t h e g r o u p s  when  the  coefficients  five  different is  structure,  be  of  into  balance  that the e n t i r e using  The number o f  s .  n = n  is  square  represented  With  truncated matrix  up t o any p r e s e l e c t e d c u t o f f  This  actual  submatrices.  independent the  the  i t i s seen  could  (s+1 x s+1)  predictable  A  such  c a n be  a  easily  .  c  (2) The  figure  shows f o r t h e p a r t i c u l a r  infinite  matrix  equations  and  of  n > s  for  f o r states with  blocked  When  written  states  structure.  are  s+1 = 5 .  for  (five)  Part  regular matrix  are  submatrices  equations,  coefficients  of dimension  of c o e f f i c i e n t s  generated  The b a l a n c e  of  Nj  the balance Before  number  variables.  equations  will  be  n > s ,  configurations  n = n  f o r (q, q ) 2  .  of c o n f i g u r a t i o n s f o r 0  The  q,=0  number  f o r which  of  first  Since  s,+s  (s, s ) 2  variables  0 ^ n < n +1  line  Nj .  the  to  N-j.  encloses a l l  must  determine (s, s ; qi 2  For each  n < s  and s , + s  = n .  2  and t h e r e f o r e t h e r e a r e 2  is  s t a t e s f o r any g i v e n  c  truncated  space  q2=0,  t  how  c  ^ 0 .  0  = 6  ,n =6 .  i n the s t a t e  qi+q2 = n-s ,  (s+1)(n -s+1)  states  we  states since  then  be  n =0,1,2,..  and  population  (n+1)  would  n  The h e a v y b l a c k  for  of s t a t e s which e x i s t  any f i x e d  then  coefficents  deriving  for  number  of  case  = s  for  i s equal  0  q ) , 2  there For  (n-s+1)  n £ s , the  (s+1) . n = n  the  There  are  ^ s .  t o t h e number of  Therefore, with  n  £ s , c  82  n +1 E (s+1)(n-s+1) n=s c  N  =  1 + 2 + ... + s +  =  s(s+1)/2  J  or,  N  + (s+1)(n-S+2)(n_-s+3)/2  J  Then Nj =60 The only  f o r t h e example  n  c  number o f e q u a t i o n s  N  x  those  balance are  f o r which  equations  found  already equations  can  equation N  best n  number  Figure  .  bounds  matrix  .  at f i r s t  group,  three  be  the  15).  three  Maximizing  A  will  to  These  number  this  77].  be  of the  equations  N^  variables additional  N^  of balance  example,  then  t h e number o f c o n s t r a i n t s  in this  (n,-s+l)  more  any more t h a n  For  [KOTI  appear  But on e x a m i n a t i o n  included i n the t o t a l  of v a r i a b l e s  possible  truncated by  =43  , there w i l l  c  (see  be  might  =7  c  constraints.  = 4 0 + 3  fixed  n +1  w h i c h do n o t i n v o l v e  included  = 6 .  0 ^ n < n c  i n the  (C.1)  l_  C  for a  way, we a r e a b l e t o o b t a i n t h e In g e n e r a l , f o r a t r u n c a t i o n a t  additional  equations,  have d i m e n s i o n s  (Nj_ x N j ) '  and N  j  the  given  ( C . 1 ) , and N  =  n E° ( s + 1 ) ( n - s + 1 )  1 + 2 + ... + s +  +  (n -s+l) c  n=s or,  N  =  s ( s + l ) / 2 + (s+1 ) ( n - s + 1 ) ( n - s + 2 ) / 2 c  c  .+ ( n , - s + 1 ) .  (C.2)  P a r t (3) Figure  15  also  illustrates  [BHAR 60, p . 1 4 ] o f t h e c o n t i n u o u s - t i m e any from  given any  squares) balance reached  row, t h e s t a t e of on  the  the l e f t  equations from  states  any  with  f o r many q u e u e i n g state.  model.  In  d i a g o n a l c a n be  reached  coefficients  (shaded  nonzero This  irreducibility  Markov c h a i n  on t h e m a t r i x  or r i g h t .  other  the  i s the basic  systems; Hence,  any the  s t r u c t u r e of  state  can  be  Markov c h a i n i s  rreduc i b l e .  84  APPENDIX D - A DERIVATION FOR THE NORMALIZATION IN [KOTI 77] Consider v X  customer = a\  i  ±  types.  average  The  arrival  , (i=1,2...,v).  Kleinrock  [KLEI  with  s  average  , where rate.  customer Z±<*±  The  The f o l l o w i n g  identical  =  servers  arrival >  1  and  rates are is  a n c 5  average  GIVEN  service  t  h  e  times are  r e a s o n i n g i s g u i d e d by t h a t o f  75, p . 1 9 ] .  Assume t h a t number  system  (i=1,2,...,v)  ±  total y  a queueing  CONDITION  a stationary  of customers  probability  i n the system  distribution  p(n) , e x i s t s ,  for  the  with  oo  I n=0 Assume In  a l l customers  addition,  [KLEI time  that  the  76, p . 1 1 3 ] , shorter  service  p(n)  system  must  in particular, that  distribution  is  service  time  additional  interarrival  restriction  on s e r v i c e  customers  have an e q u a l c h a n c e  identical  servers.  First  we  interpreted  show  as:  random  time).  server  i s free  time  interval  is  (X./S)T .  that  Or, t h a t  placed  on  service  when  Beyond t h i s  its  proviso,  either  distributions.  utilization  specific  server  p = 1 - z , where  r , the expected during  c a n have a obtained  discipline  a t any random t i m e ) .  Also  work-conserving  i s that  the  The o n l y individual  o f b e i n g s e r v e d by any o f t h e  the  p = Pr(any  is  sampled. be  0 < p < 1 .  served, be  which  to  or  (D.1)  no c u s t o m e r  t h e r e a r e no o t h e r r e s t r i c t i o n s time  .  are eventually  or longer than  time  = 1  factor is  p , may  busy  z = Pr(any  at  of a r r i v a l s  T , t h e busy  be any  specific  D u r i n g an a r b i t r a r i l y  number  s  t o one  long server  time of the s e r v e r i s  85  T(1-Z) T  , and  will  service  In  be  time  E(y)  the  average  T(1-Z) of  = E[  interval  number  so  the  E(y T  / E(y)  | customer  , the  , there  E  Defining  the  T  o y  E. i  ±  =  x  i  i y i /  s  i s the  during expected  served:  arrivals  roughly  .  matches  the  utilization  ~  1  ±  Now  we  develop  conditional  = Pr(any  1 p(0)  +  server  p(D  1/s)  z combining  i s free  server  ...  Therefore,  k  s  (  .  D  -  2  )  (D.3)  an' a l t e r n a t e e x p r e s s i o n  specific (1-  .  i  for  z  using  (D.1)  probability.  specific  Pr(any  i  as  1 - p  z =  o y  •  ±y±/  z  E  z  z  factor =  /  and:  1 -  =  then  = E[  E(y)  served  in service)] = E ^ ) ^  T(1-Z)  =  i  *  =  of  is equality,  U/s)  z  Here,  type  number  customers  served:  T -> °°  and  .  customers being  U/s)  As  number of  +  =  + (1-  s-1 E n=0  (D.3)  a t any  i s free  ...  ( 1 - 2/s)  random  | number  p(2)  +  and  - n/s)  in  + 0 + 0 +  p(n)  (D.4),  the  system)]  ...  ( S - 1 ) / S ) p(s-1) + 0  (1  time)  ...  (D.4) desired  result  is  obtained:  1 - ft = This  equation  s-1 E n=0  appears  (1  - n/s)  i n the  text  p(n) as  ,  0<p<1  (4.13) i n IV  . -  (D.5) D.  86  BIBLIOGRAPHY [ALLE 77]  B. A l l e n , R.S. A n d e r s s e n , E . S e n e t a , "Computation of S t a t i o n a r y M e a s u r e s f o r I n f i n i t e Markov C h a i n s " TIMS S t u d i e s i n t h e Management S c i e n c e s M.F. N e u t s , e d . , 7 1977 13-23.  [AVI  B. A v i - I t z h a k , W.L. M a x w e l l , L.W. Miller "Queueing w i t h A l t e r n a t i n g P r i o r i t i e s " Opns. Res., J_3 1965 306-318.  65]  [BART 81]  P. B a r t f a i , J . Tomko, P o i n t P r o c e s s e s and Queuing Problems, C o l l o q u i a Mathematica S o c i e t a t i s J a n o s B o l y a i , 24 (1978) North-Holland, New Y o r k , 1981.  [BHAR 60]  A.T. B h a r u c h a - R e i d , E l e m e n t s of t h e T h e o r y of Markov P r o c e s s e s and T h e i r A p p l i c a t i o n s , 1st e d . McGraw H i l l , New Y o r k , 1960.  [BOBI  P.A. B o b i l l i e r , B.C. Kahan, A.R. P r o b s t S i m u l a t i o n w i t h GPSS and GPSSV Prentice-Hall, Englewood C l i f f s , N.J.,  76]  [BUNC 76]  J.R. Bunch, D . J . Rose, Sparse Matrix Academic P r e s s , New Y o r k , 1976.  [COBH 54]  A. Cobham, Problems",  [COOP 69]  R.B. C o o p e r , G. M u r r a y "Queues S e r v e d i n C y c l i c O r d e r " B e l l S y s t . T e c h . J.,- 48(3) 1969  1976.  Computations  " P r i o r i t y Assignment i n W a i t i n g L i n e Opns. Res., 2 1954 70-76.  675-689.  [COOP 70]  R.B. C o o p e r , "Queues S e r v e d i n C y c l i c O r d e r : W a i t i n g Times" B e l l S y s t . T e c h . J . , 49(3) 1970 399-413.  [COOP 72]  R.B. C o o p e r , Macmillan,  [DAVI  R.H. D a v i s , "Waiting-Time D i s t r i b u t i o n of a M u l t i - s e r v e r P r i o r i t y Queueing System" Opns. Res., J_4 1966 1 33-136.  66]  I n t r o d u c t i o n t o Queueing New Y o r k , 1972.  [DUFF 77]  I.S. D u f f , "A S u r v e y o f S p a r s e M a t r i x Proc. IEEE, 65(4) 1977 500-535.  [ E I S E 71]  M. E i s e n b e r g , Opns. Res.,  Theory,  Research"  "Two Queues w i t h C h a n g e o v e r 19(2) 1971 386-401.  Times"  87  [EISE  72]  M. E i s e n b e r g , "Queues w i t h P e r i o d i c Changeover Time" O p n s . Res., 20(2) 1972 440-451.  [EVAN  74]  D.J. Evans, ed., Software f o r Numerical Mathematics, Academic P r e s s , New Y o r k ,  Service  and  1974.  [FISH  78]  G. S. F i s h m a n , Simulation,  [GOLD  81]  H. M. G o l d b e r g , " C o m p u t a t i o n of S t a t e P r o b a b i l i t i e s f o r M|M|s P r i o r i t y Queues w i t h Customer C l a s s e s having D i f f e r e n t Service Rates" INFOR, J_9(1) 1981 48-58.  [GROS  74]  D. G r o s s , C M . Harris F u n d a m e n t a l s of Q u e u e i n g T h e o r y Wiley, New Y o r k , 1974.  [GUST  72]  F.G. G u s t a v s o n , S p a r s e Systems i n [ROSE 7 1 ] ,  [HALF  72]  S. H a l f i n , "A P r i o r i t y Q u e u e i n g M o d e l f o r a M i x t u r e of Two T y p e s o f C u s t o m e r s " SIAM J . A p p l . Math., 23(3) 1972 369-379.  [KALA  71]  J.E. Kalan, " A s p e c t s of L a r g e - S c a l e , In-Core L i n e a r Programming" P r o c . A n n u a l ACM C o n f e r e n c e , C h i c a g o , 1971 304-313.  [KLEI  75]  L. K l e i n r o c k , Q u e u e i n g S y s t e m s , Volume I : Theory, Wiley, New Y o r k , 1975.  [KLEI  76]  L. K l e i n r o c k , Queueing Computer A p p l i c a t i o n s ,  [KOTI  73]  T.C.T. K o t i a h , N.B. S l a t e r , "On T w o - S e r v e r Queues w i t h Two T y p e s o f C u s t o m e r s " Opns. Res., 2J_ 1973 597-603.  [KOTI  77]  T.C.T. K o t i a h , "On a L i n e a r Programming T e c h n i q u e f o r t h e S t e a d y - S t a t e B e h a v i o u r of some Q u e u e i n g Systems", Opns. Res., 25(2) 1977 289-303.  [KUEH  79]  P . J . Kuehn, " M u l t i q u e u e Systems w i t h N o n e x h a u s t i v e Cyclic Service" B e l l Syst. Tech. J . , 58(3) 1979 671-698.  [LUEN  73]  D.G. L u e n b e r g e r , Introduction to Linear N o n l i n e a r Programming Addison-Wesley, Reading,Mass., 1973.  Principles Wiley, New  of D i s c r e t e Event York, 1978.  "Some B a s i c T e c h n i q u e s of L i n e a r E q u a t i o n s " 41-52.  Systems, Wiley,  for Solving  Volume 11: New Y o r k , 1976. Poisson  and  88  [MURT 81 ]  B.A. M u r t a g h , A d v a n c e d L i n e a r Programming; C o m p u t a t i o n and P r a c t i c e McGraw-Hill, New Y o r k , 1981.  [NAIR 76]  S.S. N a i r , " A l t e r n a t i n g P r i o r i t y Queues w i t h Non-Zero S w i t c h R u l e " Computers a n d Opns. R e s . , 3 1976 337-346.  [REID 74]  J.K. R e i d , " D i r e c t Methods i n [EVAN 7 4 ] , 29-47.  [ROSE 71]  D. J . Rose, R.A. W i l l o u g h b y Sparse M a t r i c e s and T h e i r A p p l i c a t i o n s Plenum P r e s s , New Y o r k , 1971.  [ROSS 72]  S.M. R o s s , Introduction to Probability Academic P r e s s , New Y o r k , 1972.  [SCHL 81]  W. S c h l e e - K S s s l e r , "A S i n g l e S e r v e r Queue w i t h Two Types of Customers and A l t e r n a t i n g S e r v i c e i n P i e c e s of ^ and " i n [BART 8 1 ] , 343-357.  [SENE 67]  E. S e n e t a , " F i n i t e Approximations to I n f i n i t e Non-Negative M a t r i c e s " P r o c . Camb. P h i l . S o c , 63 1967 983-992.  [SENE 68]  E. Seneta, " F i n i t e Approximations to I n f i n i t e Non-Negative M a t r i c e s I I : Refinements and Applicat ions" P r o c . Camb. P h i l . S o c , 64 1968 465-470.  [SHER 78a]  A.H. Sherman, "Algorithms f o r Sparse Elimination with P a r t i a l P i v o t i n g " ACM T r a n s , on M a t h e m a t i c a l S o f t w a r e 4(4) 1978 330-338.  [SHER 78b]  A.H. Sherman, " A l g o r i t h m 533: NSPIV, A F o r t r a n Subroutine f o r Sparse Gaussian E l i m i n a t i o n with Partial Pivoting" ACM T r a n s a c t i o n s on M a t h e m a t i c a l S o f t w a r e 4(4) 1978 391-398.  [SING 81]  R. S i n g h , S. Subba Rao, S.C. Gupta " A n a l y s i s o f a M o b i l e R a d i o C o m m u n i c a t i o n System w i t h Two T y p e s o f C u s t o m e r s a n d P r i o r i t y " I n t . C o n f . on Comm., D e n v e r , 1981 I E E E ( I C C - 1 9 8 1 ) , v.3 57.4.1-57.4.5 .  [SLAT 73]  N.B. S l a t e r , T.C.T. K o t i a h "The S t e a d y - S t a t e o f a M u l t i s e r v e r M i x e d Adv. i n A p p l . P r o b . , 5 1973 614-631.  <  f o r Sparse M a t r i c e s "  Models  Gaussian  Queue"  89  [STEW 78]  [SYKE  70]  W.J. S t e w a r t , "A C o m p a r i s o n o f N u m e r i c a l T e c h n i q u e s i n Markov M o d e l i n g " C o m m u n i c a t i o n s of t h e ACM, 2±(2) 1978  144-152.  J.S. Sykes, " S i m p l i f i e d A n a l y s i s o f an A l t e r n a t i n g - P r i o r i t y Queue w i t h S e t u p T i m e s " Opns. Res., _[8 1970 1182-1 1 92.  [TAYL 80]  I.D.S. T a y l o r , J.G.C. T e m p l e t o n " W a i t i n g Time i n a M u l t i - s e r v e r C u t o f f - P r i o r i t y Queue, and i t s A p p l i c a t i o n t o an U r b a n Ambulance Service" Opns. Res., 28(5) 1980 1168-1188.  [WALL 66]  V . L . W a l l a c e , R.S. R o s e n b e r g " M a r k o v i a n M o d e l s and N u m e r i c a l A n a l y s i s o f Computer System B e h a v i o u r " AFIPS S p r i n g J o i n t Comp. C o n f , 28 1966 141-148  [WILL  T.M. W i l l i a m s , "Nonpreemptive P r i o r i t y Queues" J . O p e r a t i o n a l Res. S o c . 31(12) 1980 1105-1107.  80]  [WOLF 80]  Multi-server  D. W o l f , " A p p r o x i m a t i o n of t h e I n v a r i a n t P r o b a b i l i t y Measure of an I n f i n i t e S t o c h a s t i c M a t r i x " Adv. i n A p p l . P r o b . , 12 1980 710-726.  90  Glossary A  coefficient  A,  first  b,  b  matrix  (N-j-x N ) x  of N o t a t i o n  of the  submatrix  of  right-hand side constant constra int(s)  B  coefficient  matrix  c  counter  c%  general confidence 2  v  number o f s t a t e  E[']  expectation operator  FCFS  first-come, first-served  i,j,k  integer  I  identity  normalization contraints  model  interval  d  equations  A  ^  space  priority  balance  x  ( v e c t o r ) of the n o r m a l i z a t i o n  of the  i n the s t a t e  C(k,,k ,..,k ) cyclic  N  with  v  service  discipline  indices matrix  (m x m)  J  a v e r a g e number o f s i m p l e x objective function  ^  maximum number s e r v e d d u r i n g p h a s e  K  total  L  a fixed  LP  linear  LU  a f a c t o r i z a t i o n of a m a t r i x as a product and upper t r i a n g u l a r m a t r i c e s  m  number o f rows i n t h e LP  M|M|s  queues  i n a Markov c h a i n  ^1  M|G | 1  priority  for simulation results  system  variables  forcyclic  identity  matrix  number o f o b j e c t i v e  iterations  required per  i of c y c l i c  f u n c t i o n s f o r an LP  priority problem  maximum queue l e n g t h program of lower  s i n g l e - s e r v e r queue w i t h a P o i s s o n a r r i v a l and a g e n e r a l s e r v i c e t i m e d i s t r i b u t i o n  process  s - s e r v e r queue w i t h a P o i s s o n a r r i v a l p r o c e s s a n d e x p o n e n t i a l l y d i s t r i b u t e d s e r v i c e times  91  n  (1) number (2)  n  f o r number  f i x e d value of  0  n N  index  of columns  i n t h e LP, of customers  n, number  i n a queueing  system  i n t h e system  t r u n c a t i o n parameter f o r the s e t of balance e q u a t i o n s (1) t o t a l number o f s t a t e s i n a f i n i t e s t a t e s p a c e , (2) t o t a l number o f m e a s u r e d e v e n t s i n a s i m u l a t i o n  c  number N  of b a l a n c e e q u a t i o n s  (rows) i n  number o f s t a t e p r o b a b i l i t y v a r i a b l e s columns of A  N  number  of n o r m a l i z a t i o n  constraints  A associated  (rows) i n  with  B  N  NPP  non-preemptive  p(n)  steady state p r o b a b i l i t y queueing system  p (n),  p (n)  P  discrete-time  £  P,, P  lower  u  submatrices  2  , .P  priority  (m x m)  and upper  of  general discrete  P^(k),  P (k)  P(s,  s )  P(s,  s ; q, q )  q Q  s s  2  P  probability distribution  and upper  bounds on P ( k ) f o r e a c h k  p r o b a b i l i t y of s t a t e  v a r i a b l e f o r number t h e queue  of type  total c  (s, s ; 2  i  cutoff state  t  time  available level  for cutoff  variable  (superscript)  number  of  matrix  transpose  2  customers  waiting  matrix times  servers  priority  f o r number  q )  t r a n s i t i o n rate  r a t i o s of l i m i t i n g v a l u e s of average  s  ±  of  c o n t i n u o u s - t i m e Markov c h a i n  R, , R  matrix  2  2  state in  ±  transition probability  same a s P f s , s ; 0 0)  2  2  in a  P  P(k)  lower  n customers  bounds on p ( n ) f o r e a c h n  Markov c h a i n  truncation  u  for  of type  queues i customers  in service  92  v  (1) number o f q u e u e s  in cyclic  (2) number o f c u s t o m e r  priority,  classes  i n a general  w  random v a r i a b l e  W  mean w a i t i n g  x  an i n d e x e d member o f t h e s e t { P t s , s ; q i  ±  i  ±  for waiting  time of type i customers  time f o r type i customers 2  x  finite  column v e c t o r  (state x^  infinite  x^  a basic  y  (1) s l a c k  system  of v a r i a b l e s  p r o b a b i l i t i e s plus column v e c t o r  q )} 2  i n t h e LP,  the slack  variable)  of the p r o b a b i l i t i e s  solution for a linear  x  i  program  variable,  (2) random v a r i a b l e  for service  time  y_^  random v a r i a b l e  y z  average s e r v i c e time of a type i customer p r o b a b i l i t y t h a t any g i v e n s e r v e r i s f r e e a t any random t i m e  Z, Z^.  one o f t h e o b j e c t i v e  Z(W )  truncation  0  null  i  f o r s e r v i c e t i m e of a t y p e i c u s t o m e r  functions  o f VJ u s e d a s an o b j e c t i v e ±  f r a c t i o n of a r r i v i n g  Oi*  value p,  fi  f r a c t i o n of system of t y p e i  6(')  discrete delta  A  convergence parameter  ±  of vs. Oi  Poisson total  n  exponential  TT_  infinite  customers which a r e of type i  i n a 2 - c l a s s system a t which t h e c u r v e h a s slope=1  Poisson  resources  a l l o c a t e d t o customers  function  arrival  X ±  function  vector  a  ±  f o r t h e LP  rate  row v e c t o r  technique  of type i customers  arrival  service  i n a matrix i t e r a t i o n  rate  rate  of customers  of type i customers  o f Markov c h a i n p r o b a b i l i t i e s  93  m-component  solution  permutation  matrix  utilization  parameter  total  utilization  a critical arbitrary  value time  of a t r u n c a t e d  f o r type  (traffic of  p  interval  Markov c h a i n  model  i customers  intensity)  parameter  f o r NPP m u l t i s e r v e r  systems  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
Japan 7 0
United States 4 0
China 3 3
Germany 1 1
Uganda 1 0
City Views Downloads
Tokyo 7 0
Ashburn 4 0
Shenzhen 2 0
Unknown 2 1
Beijing 1 0

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

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-0065616/manifest

Comment

Related Items