Introduction to Queueing Systems and Applications
Explore the fundamentals of queueing systems, including Little's law, impacts of randomness, and product-form solutions. Delve into the history of queueing theory and its applications in traffic control, planning, and facility dimensioning. Understand the classification and characteristics of simple queueing systems.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Chapter 6 Queueing systems Learning objectives : Little's law Impact of the randomness on performances of queueing systems Product-form solutions Textbook : C. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, Springer, 2007 S.M. Ross, Stochastic Process, John Wiley & Sons 1
Plan Introduction Classification of queueing systems Little's law Single stage queuing systems Queuing networks Non Markovian queueing systems 2
Definition of a queueing system Departure of served customers Customer arrivals Departure of impatient customers A queueing system can be described as follows: "customers arrive for a given service, wait if the service cannot start immediately and leave after being served" The term "customer" can be men, products, machines, ... 4
History of queueing theory The theory of queueing systems was developed to provide models for forecasting behaviors of systems subject to random demand. The first problems addressed concerned congestion of telephone traffic (Erlang, "the theory of probabilities and telephone conversations ", 1909) Erlang observed that a telephone system can be modeled by Poisson customer arrivals and exponentially distributed service times Molina, Pollaczek, Kolmogorov, Khintchine, Palm, Crommelin followed the track 5
Interests of queueing systems Queueing theory found numerous applications in: Trafic control (communication networks, air traffic, ) Planing (manufacturing systems, computer programmes, ) Facility dimensioning (factories, ...) 6
Classification of queueing systems 7
Characteristics of simple queueing systems Queueing systems can be characterized with several criteria: Customer arrival processes Service time Service discipline Service capacity Number of service stages 8
Notation of Kendall The following is a standard notation system of queueing systems T/X/C/K/P/Z with T: probability distribution of inter-arrival times X: probability distribution of service times C: Number of servers K: Queue capacity P: Size of the population Z: service discipline 9
Customer arrival process T/X/C/K/P/Z T can take the following values: M : markovian (i.e. Poisson) G : general distribution D : deterministic Ek : Erlang distribution If the arrivals are grouped in lots, we use the notation T[X] where X is the random variable indicating the number of customers at each arrival epoch P{X=k} = P{k customers arrive at the same time} Some arriving customers can leave if the queue is too long 10
Service times T/X/C/K/P/Z X can take the following values: M : markovian (i.e. exponential) G : general distribution D : deterministic Ek : Erlang distribution k exponential servers with parameter Erlang distribution Ekwith parameter 11
Number of servers T/X/C/K/P/Z In simple queueing systems, servers are identical 12
Queue capacity T/X/C/K/P/Z Loss of customers if the queue is full Capacity K 13
Size of the population T/X/C/K/P/Z The size of the population can be either finite or infinite For a finite population, the customer arrival rate is a function of the number of customers in the system: (n). 14
Service discipline T/X/C/K/P/Z Z can take the following values: FCFS or FIFO : First Come First Served LCFS or LIFO : Last Come First Served RANDOM : service in random order HL (Hold On Line) : when an important customer arrives, it takes the head of the queue PR ( Preemption) : when an important customer arrives, it is served immediately and the customer under service returns to the queue PS (Processor Sharing) : All customers are served simultaneously with service rate inversely proportional to the number of customers GD (General Discipline) 15
The concept of customer classes A queueing system can serve several classes of customers characterized by: different arrival processes different service times different costs service priority according to their class (preemption or no for example) 16
Simplified notation We will use the simplified notation T/X/C when we consider a queue where: The capacity is infinite The size of the population is infinite The service discipline is FIFO Hence T/X/C = T/X/C/ / /FIFO M/M/1 : Poisson arrival/Exponential service time / 1 server M/M/C M/D/1 17
Ergodicity A system is said ergodic if its stationary performances equal the time average of any realisation of the system, observed over a sufficiently long period T 1 T ( ) ( ) = E X lim T X t dt = 0 t A regenerative system, i.e. a system with a given state s0that is visited infinitely often, is ergodic. Finite, irreducible and aperiodic CMTC are ergodic. Only ergodic systems will be considered in this course 18
Ergodicity A non ergodic system : X(t) = reward of the state at time t 1 3 unit reward 1 2 1 1 1 1 unit reward 2 4 5 ( ) = E X does not exist T 1/2, with proba 0.5 1, with proba 0.5 1 T ( ) = lim T X t dt = 0 t 19
Little's law 20
Some transient performances THs(T) THe(T) L(T) W(T) A(T) : number of customers arrived from 0 to T D(T) : number of departures between 0 to T THe(T) = A(T)/T : average arrival rate between 0 to T THs(T) = D(T)/T : average departure rate between 0 to T L(T) : average number of customers between 0 to T Wk: sojourn time of k-th customer in the system average sojourn time between 0 to T ( ) ( ) 1 k A T = ( ) A T 1 = W T W k 21
Stability of the queueing system THs(T) THe(T) Queueing system Definition : A queueing system is said stable if the number of customers in the system remains finite. Implication of the stability: lim T ( ) ( ) = lim T TH T TH T e s ( ) ( ) A T D T = lim T 1 22
Little's law For a stable and ergodic queueing system, L = TH W where L : average number of customers in the system W : average response time TH : average throughput rate Queueing system TH TH L W 23
Proof Nb in system A2A3 A6 A1 A5 A4 W1 W2 W3 W4 e(T) 0 Time T D1 D2 D3 D4 24
Proof ( ) T ( ) ( ) A T ( ) A T ( ) A T D T D T 1 1 T ( ) ( ) = = R T TH T R R ( ) A T k k = = 1 1 k k ( ) A T ( ) A T ( ) A T 1 T 1 T 1 T T ( ) ( ) = + 1 still there at R k t dt r T k k = 0 t ( ) ( ) = = k A T = + 1 1 1 k k N T 1 T ( ) ( ) e T = + Q T where N(T) is the number of customers at time T, e(T) total remaining system time of customers present at time T. Letting T go to infinity, the stability implies the proof. 25
M/M/1 queue N(t) : number of customers in the system Poisson arrivals Exponentially distributed service tim 27
Stability condition of M/M/1 queue The M/M/1 queue is stable iff < or equivalently where = = is called the traffic ratio or traffic intensity. The number of customers in the system is unlimited and hence there is no steady state when the system is not stable. 28
Markov chain of the M/M/1 queue When the system is stable, stationary probability distribution exists as the CTMC is irreducible. Let ( ) = = lim t , 0 P N t n n n 29
Steady state distribution of M/M/1 queue = = state 0 : state 0-1: 1 0 2 1 Balance equations = state 0-1-...-n: + 1 n n = Normalization equations: 1 n n=0 With = , = n= n 30
Performance measures of M/M/1 queue (online proof and figures) = Number of customers in the system = ( ) = /( ) Ls = Sojourn time in the system = ( ) = 1/( ) Ws = queue length = 2/( ) = Ls Lq = average waiting time in the queue = /( ) = Ws Wq = departure rate = Server utilization ratio = Server idle ratio = P0= 1 - P{n > k} = Probability of more than k customers = k+1 31
M/M/C queue Exponentially distributed service tim Poisson arrivals N(t) : number of customers in the system N(t) is a birth and death process with The birth rate . The deadth rate is not constant and is equal to N(t) if N(t) C and C if N(t) > C. Stability condition : < c . 32
Steady state distribution of M/M/C queue Stationary probability distribution: a= = offered load = = c = = a/c traffic intensity n= an/n! 0, 0 < n c n a n c 1 n c 1 c a a = + ( ) 0 0! n ! 1 c = n = , 0 n c + c 0 1 2 3 Markov chain of M/M/2 queue 33
Performance mesures of M/M/C queue Ls = Number of customers in the system = Lq + a Ws = Sojourn time in the system = Wq + 1/ Lq = Average queue length = ( ) C 2 1 ( ) , C c a = 1 Wq = Average waiting time = Lq / = Average number of busy server, = a 34
Performance mesures of M/M/C queue C(c,a) = Waiting probability of an incoming customer = c + c+1 + ... c a ( ) a ! 1 n c ( ) Erlang C formula c = = , C c a c 1 c 1 a n + ( ) ! ! 1 c = 0 n wq = random waiting time of a customer (Moment generating funct) ( ) 0, with probability 1 , C c a = w q ( ) ( ) , with probability , EXP c C c a T (T) = Waiting time target = Service level = P(wq T) ( ) ( ) T ( ) c T = 1 , C c a e 35
M/M/C with impatient customers Similar to M/M/C queue except the loss of customers which arrive when all servers are busy. 0 1 2 Markov chain of M/M/2 queue with impatient customers 36
M/M/C with impatient customers Steady state distribution : a= = offered load = c traffic intensity n= an/n! 0, 0 < n c 1 n C a n = 0 ! = 0 n Percentage of lost customers = C Server utilization ratio = (1 C) /C Insensitivity of Erlang Loss system M/GI/C without queue (see Gross & Harris or S. Ross, proof by reversed system) : Pn depends on the distribution of service time T only through its mean, i.e. with = E[T] 37
M/M/C with impatient customers Erlag loss function or Erlang B formula = Percentage of lost customers or overflow probability c ! n a c ( ) = = , B c a c c n ! a n = 0 Accepted load ( ) ( ) 1 , a B c a
M/M/C with impatient customers (optional) Normal approximation for staffing Erlang Loss systems Condition: high offered load (a > 4) and high targeted service level N(t) = number of patients : approximately normally distributed E[N(t)] a In M/M/ system, N(t) =d POISSON(a), i.e. E[N(t)] = a, Var[N(t)] = a Square-Root-Staffing-Formula for a delay probability = + c a a N a c a ( ) ( ) ( ) ( ) = = = = 1 P Delay P N t c P a a Where is the cdf of the standard normal distribution
Computational issues of Erlang B and C formula c a c ! n a c ( ) = ( ) a , B c a ! 1 n c c n ( ) ! a n = , C c a = 0 c 1 c a n + ( ) ! ! 1 c = 0 n ( ) ( ) = , 1/ , : the reciprocal R c a B c a !!! recursion for a given offered load a !!! = 1 0 c n n ! 1 1 ! a n ( ) ( ) ( ) -1 = + + , 1 1, as , = 1 R c a R c a R c a ( ) 1 c a c a c ( ) a = 0, 1 B ( ) ( ) 1 = , 1, B c a R c a ( ) ( ( ) ( ) ) a = 0, 1 C 1 1 = + , 1 1 1, C c a R c a = a c
Bed capacity reducing through merging Impact of clinical organisation Consider the possiblity of combining cardiac and thoracic surgery patients as thoracic patients are relatively few and require similar nursing skills as cardiac patients. The average arrival rate of cardiac patients is 1,91 bed requests per day and that of thoracic patients is 0,42. No additional information is available on the arrival pattern and we assume Poisson arrivals. The average LOS (Length Of Stay) is 7,7 days for cardiac patients and 3,8 days for thoracic patients. What is the number of beds for cardiac patients and thoracic patients in order to have average patient waiting time for a bed E(D) not exceeding 0,5, 1, 2, 3 days? What is the number of beds if all patients are treated in the same nursing unit? Delay in this case measures the time a patient coming out of surgery spends waiting in a recovery unit or ICU until a bed in the nursing unit is available. Long delays cause backups in operating rooms/emergency rooms, surgery cancellation and ambulance diversion. 27
Definition of queueing networks A queueing network is a system composed of several interconnected stations, each with a queue. Customers, upon the completion of their service at a station, moves to antoher station for additional service or leave the system according some routing rules (deterministic or probabilitic). 43
Example of deterministic routing Shortest queue rule 44
Open network or closed network Open network N customers Closed network 45
A production line Raw parts Finished parts 47
Open Jackson Network An open Jackson network (1957) is characterized by: One single class of customers A Poisson arrival process at rate (equivalent to independent external Poisson arrival at each station) One server at each station Exponentially distributed service time with rate i at station i Unlimited capacity at each queue FIFO service discipline at all queues Probabilistic routing 48
Open Jackson Network routing pij(i 0 and j 0) : probability of moving to station j after service at station i p0i: probability of an arriving customer joining station i pi0: probability of a customer leaving the system after service at station i 49
Open Jackson Network stability condition Let ibe the customer arrival rate at station i, for i = 1, ..., M where M is the number of stations. The system is stable if all stations are stable, i.e. i< i, i = 1, ..., M Consider also eithe average number of visits to station i for each arriving customer: ei = i/ 50
