Queuing Systems with Birth-Death Process
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
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