Queuing Systems with Birth-Death Process

Queuing Systems with Birth-Death Process
paly

This article discusses queuing systems with a birth-death process, which is a stochastic process that models the evolution of a system of discrete entities over time. The authors, maglaris.net

  • Uploaded on | 3 Views
  • fikria fikria

About Queuing Systems with Birth-Death Process

PowerPoint presentation about 'Queuing Systems with Birth-Death Process'. This presentation describes the topic on This article discusses queuing systems with a birth-death process, which is a stochastic process that models the evolution of a system of discrete entities over time. The authors, maglaris.net. The key topics included in this slideshow are . Download this presentation absolutely free.

Presentation Transcript


Slide11ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Queuing  Systems ΣΥΣΤΗΜΑΤΑ  ΑΝΑΜΟΝΗΣ Queuing  Systems Διαδικασίες Γεννήσεων-Θανάτων ( Birth-Death), Εξισώσεις Ισορροπίας, Συστήματα Αναμονής Μ/Μ/1 Β.  Μάγκλαρης   < maglaris@netmode.ntua.gr> Β.  Μάγκλαρης   < maglaris@netmode.ntua.gr> Σ.  Παπαβασιλείου   < papavass@mail.ntua.gr> Σ.  Παπαβασιλείου   < papavass@mail.ntua.gr> 22-5-2014 22-5-2014

Slide2Επανάληψη (1 ): Στοχαστικές διαδικασίες • Ανεξάρτητες διαδικασίες • Στάσιμες διαδικασίες • Διαδικασίες  Markov • P[X(t n+1 )= x n+1 /X(t n )= x n ,X(t n-1 )= x n-1 ,…,X(t 1 )= x 1 ]= =P[X(t n+1 )=X n+1 /X(t n )= x n ] • Εργοδικότητα • Διαδικασίες Γεννήσεων-Θανάτων: αποτελούν μια κλάση των διαδικασιών  Markov , με την επιπλέον ιδιαίτερη συνθήκη ότι μεταβάσεις επιτρέπονται μόνο ανάμεσα σε γειτονικές καταστάσεις • Διαδικασία απαρίθμησης γεγονότων • Ανεξάρτητες αυξήσεις – Στάσιμες αυξήσεις

Slide3Επανάληψη (2 ): Η κατανομή  Poisson • n   αφίξεις σε διάστημα  Τ  με πιθανότητα • P n  (T) = e  – λ T  ( λΤ) n  / k ! • E T ( n ) =  λ T • Var T  ( n ) =  λΤ Μέσος ρυθμός αφίξεων :  λ  πελάτες/ sec Η κατανομή  Poisson  σαν όριο της Διωνυμικής Κατανομής

Slide4Επανάληψη (3 ): Ιδιότητες διαδικασίας Poisson • Οι χρόνοι μεταξύ διαδοχικών αφίξεων μιας διαδικασίας Poisson  με ρυθμό  λ , είναι τ.μ εκθετικά κατανεμημένες με μέση τιμή  1/λ • Υπέρθεση ανεξάρτητων διαδικασιών  Poisson   λ 1 , λ 2    διαδικασία  Poisson   λ = λ 1  + λ 2 • Διάσπαση διαδικασίας  Poisson   λ   με πείραμα  Bernoulli   p, q = 1-p      ανεξάρτητες διαδικασίες  Poisson λ 1   = p  λ λ 2  = q  λ

Slide5Διαδικασία Γεννήσεων – Θανάτων(Birth-Death Process) (1/2) • Παραδοχές: – Ανεξαρτησία γεννήσεων-θανάτων – Εξέλιξη βασισμένη στο παρόν  (Markov) • Σύστημα Διαφορικών εξισώσεων Διαφορών – Κατάσταση ισορροπίας  (steady state) – Την χρονική στιγμή  t  όταν το σύστημα καταλήγει σε πληθυσμό  n  > 0   μπορεί να έχουν προηγηθεί οι ακόλουθες μεταβάσεις από την χρονική στιγμή  t -ΔΤ ,  ΔΤ  0: • Μία άφιξη στο διάστημα  ΔΤ , με πιθανότητα  λ n-1 ΔΤ • Μια αναχώρηση, με πιθανότητα  μ n+1 ΔΤ • Τίποτα από τα δύο, με πιθανότητα  1- ( λ n + μ n ) ΔΤ – Η εξίσωση μετάβασης ( Kolmogorov)  προκύπτει από τον τύπο συνολικής πιθανότητας: P n ( t ) =  λ n-1 ΔΤ  P n-1 ( t- ΔΤ ) +  μ n+1 ΔΤ  P n + 1 ( t- ΔΤ ) + [1- ( λ n + μ n ) ΔΤ ]  P n ( t- ΔΤ )

Slide6Διαδικασία Γεννήσεων – Θανάτων(Birth-Death Process) (2/2) Στο όριο ,  ΔΤ      dt : [ P n ( t )  -  P n ( t - dt )]/ dt  =  λ n-1 P n-1 ( t ) +  μ n+1 P n + 1 ( t )  – ( λ n + μ n ) P n ( t ) ή d P n ( t )/ dt =  λ n-1 P n-1 ( t ) +  μ n+1 P n + 1 ( t )  – ( λ n + μ n ) P n ( t ) και σε σταθερή κατάσταση  t     οο  ( αν υπάρχει) :   P n ( t ) =  P n      :  Εργοδικές Πιθανότητες ( λ n + μ n ) P n   =  λ n-1 P n-1  +  μ n+1 P n + 1    (εξισώσεις ισορροπίας)

Slide7Εξισώσεις ΙσορροπίαςΕργοδικές Πιθανότητες   P n (t)   = P n  > 0,   n  = 0,1, … Απείρως επισκέψιμες καταστάσεις  (positive recurrent) • Ερμηνεία Εξισώσεων Ισορροπίας: #{μεταβάσεων προς την κατάσταση  s }  = # {μεταβάσεων εκτός της   s } ( σφαιρική ισορροπία     –  global balance equations ) #{μεταβάσεων  s 1      s 2 }  = # {μεταβάσεων  s 2      s 1 }       ( τοπική ισορροπία  – local balance equations ) • Λόγω  εργοδικότητας : σε μεγάλο χρονικό διάστημα παρατήρησης  Τ,  με  Τ 1   και  Τ 2   τους συνολικούς χρόνους παραμονής στις  s 1 , s 2 : (1) #{μεταβάσεων  s 1      s 2 }  =  T 1  x  r 1 , ,2 (2)   # {μεταβάσεων  s 2      s 1 }  =  T 2  x  r 2, , 1 Όπου   r 1 , 2 , r 2,1   οι μέσοι ρυθμοί μετάβασης από 1   2 και 2  1 • Λόγω  ισορροπίας :  (1) = (2) , r 1 , 2  x   { T 1   /Τ}  =   r 2,1  x   { T 2   /Τ},   ή    r 1 , 2  x   P 1  =  r 2,1  x   P 2

Slide8Ουρά Μ/Μ/1 ( άπειρου μεγέθους)  (1/2) • Σταθεροί μέσοι ρυθμοί αφίξεων (γεννήσεων)  λ n = λ,  Poisson • Σταθεροί μέσοι   ρυθμοί εξυπηρέτησης (θανάτων) μ n  =  μ • Εκθετικοί χρόνοι εξυπηρέτησης  s , E( s ) = 1/ μ • Εργοδικές πιθανότητες καταστάσεων  P n • Μέσος όρος πληθυσμού - κατάστασης Ε ( n )

Slide9Ουρά Μ/Μ/1 ( άπειρου μεγέθους)  ( 2 /2) Η ουρά Μ/Μ/1 • P n  =  (1-ρ) ρ n , n = 0,1,2,… ,  ρ = λ/μ  < 1 • E( n ) =   ρ/(1-ρ) • Νόμος του  Little :   E ( T ) =  E ( n )/ γ  =  E ( n )/ λ • E ( T ) = (1/ μ) / (1-ρ)

Slide10State Dependent M/ M /1  Queues • Συστήματα Μ/Μ/1 με ρυθμούς άφιξης και ρυθμούς εξυπηρέτησης εξαρτώμενους από τον αριθμό των πελατών στο σύστημα (από την κατάσταση του συστήματος) ( State Dependent M / M /1  Queues) λ( n) μ( n) λ(0 ) λ(1 ) λ( n -1 ) μ(1 ) μ(2 ) λ( n) μ( n) μ( n +1 ) 0 1 2 n -1 n n+1