Wachtlijntheorie - Universiteit Gent

Wachtlijntheorie
Prof. Dr. ir. H. BRUNEEL
Onderzoeksgroep SMACS
Vakgroep Telecommunicatie en Informatieverwerking
Universiteit Gent
Sint-Pietersnieuwstraat 41
9000 Gent
Cursus Wachtlijntheorie
Inhoud / opbouw cursusnota’s
• Algemene inleiding
• H1: Enkele begrippen uit de probabiliteitstheorie
• H2: Wachtlijnmodellen in continue tijd
• H3: Birth-death-wachtlijnsystemen in regime
• H4: Meer algemene geheugenloze systemen in regime
• H5: Wachtlijnmodellen in discrete tijd en hun toepassing bij de
prestatie-analyse van telecommunicatiesystemen
• H6: Elementaire bufferanalyse in discrete tijd
• Appendix
• Lijst van opgaven (oefeningen) bij de cursus
Overzicht hoofdstuk 3
Birth-death-wachtlijnsystemen in regime
• Inleiding
– definitie birth-death-wachtlijnsystemen
– samenvatting definities en resultaten birth-death-processen
• Het M|M|1-wachtlijnsysteem
– met uitvoerige bespreking van de bekomen resultaten
• Het M|M|∞-wachtlijnsysteem
• Het M|M|m-wachtlijnsysteem
• Het M|M|1|K-wachtlijnsysteem
– met uitvoerige bespreking van de bekomen resultaten
• Het M|M|m|m-wachtlijnsysteem
• Slotopmerkingen
Birth-death-wachtlijnsystemen en -processen - 1
• Definitie birth-death-wachtlijnsysteem
– een wachtlijnsysteem is een birth-death-wachtlijnsysteem of
BD-wachtlijnsysteem als “arrivals” en “departures” op
zulkdanige wijze geschieden dat de systeembevolking N(t) een
birth-death-proces of BD-proces vormt
• Definitie (homogeen) birth-death-proces X(t) met continue
tijdsparameter
– stochastisch proces (toevalsproces), d.w.z. een familie van
toevalsgrootheden of een tijdsfunctie waarvan precieze verloop
afhankelijk is van het toeval
– X(t) stelt de “bevolking” voor van een of ander systeem op
tijdstip t
– discrete toestandsruimte ℕ = {0,1,2, ...} of deelverzameling
van ℕ, d.w.z. “waarden” aangenomen door X(t) (“toestanden”)
zijn natuurlijke getallen
Birth-death-wachtlijnsystemen en -processen - 2
– ogenblikkelijke toestandstransities alleen mogelijk tussen
“naburige” toestanden :
• van k naar k+1 : geboorte, birth (B)
(k ≥ 0)
• van k naar k-1 : overlijden, death (D)
(k ≥ 1)
– als X(t) = k, dan geldt, ongeacht t en X(u) voor u <t:
• kans op 1 B tussen t en t + dt → λk⋅dt
• kans op 1 D tussen t en t + dt → µk⋅dt
• kans op meerdere B en/of D tussen t en t + dt →
verwaarloosbaar t.o.v. dt
– λk = geboorte-intensiteit, µk = overlijdensintensiteit of
afsterfintensiteit in toestand k
– bij toepassing in de context van wachtlijnsystemen
“geboorte” ⇔ “arrival” ; “overlijden” ⇔ “departure”
Enkele resultaten i.v.m. BD-processen
• Grafische voorstelling: toestandsdiagram
λ0
0
λ1
1
λk−1
2
...
k-1
λk
k
k+1
...
µ1
µ2
µk
µk+1
• Bewegingsvergelijkingen
– stel Pk(t) ≜ Prob[X(t) = k] , k ≥ 0
– “dynamica” van {Pk(t) , k ≥ 0} wordt bepaald door de
“bewegingsvergelijkingen” van het proces X(t)
– de bewegingsvergelijkingen kunnen uit het toestandsdiagram worden
afgeleid, volgens de regel
d
{probabiliteit binnen S} = netto waarschijnlijkheidsdebiet
dt
doorheen S van buiten naar binnen toe
geldig voor ieder gesloten oppervlak S
Enkele resultaten i.v.m. BD-processen
• Voorbeeld van bewegingsvergelijking
λ0
0
λ1
1
µ1
λk−1
2
...
k-1
µ2
λk
k
µk
S
k+1
...
µk+1
– oppervlak S omheen toestand k ≥ 1:
d
Pk(t) = λk-1 Pk-1(t) + µk+1 Pk+1(t) – ( λk + µk ) Pk(t)
dt
• Oplossen der bewegingsvergelijkingen
– oplossen van de bewegingsvergelijkingen met bijhorende
beginvoorwaarde { Pk(0) , k ≥ 0 } levert in principe de verdeling
{ Pk(t) , k ≥ 0 } voor alle t ≥ 0
– is zeer gecompliceerd, behoudens in enkele speciale gevallen
Regimegedrag van BD-processen - 1
• Eenvoudiger te bepalen en interessanter dan tijdsafhankelijk gedrag
• Gewenst: methode ter bepaling van de limietgrootheden
pk = limt→∞ Pk(t), en de voorwaarden waaronder deze een geldige
waarschijnlijkheidsverdeling vormen
• Antwoord: via balansvergelijkingen + normeringsvoorwaarde
• Balansvergelijkingen of evenwichtsvergelijkingen
– de vergelijkingen die men bekomt door in de tijdsafhankelijke
bewegingsvergelijkingen Pk(t) door pk en d Pk(t) door nul te
dt
vervangen
– rechtstreeks uit het toestandsdiagram volgens de regel: netto
waarschijnlijkheidsdebiet doorheen ieder gesloten oppervlak in
diagram bedraagt nul
– voorbeeld : oppervlak omheen een toestand k ≥ 1:
λ k −1 p k −1 + µ k +1 p k +1 − (λ k + µ k ) p k = 0
Regimegedrag van BD-processen - 2
• Normeringsvoorwaarde
∞
∑ pk = 1
k= 0
• Irreducibel BD-proces
– BD-proces waarbij iedere toestand bereikbaar is vanuit iedere andere
– gewoonlijk het geval in wachtlijntoepassingen
• Limietdistributie van een irreducibel BD-proces
– limietdistributie (regimedistributie) { pk , k ≥ 0 } , onafhankelijk van
de beginvoorwaarden, bestaat als en slechts als het stelsel van de
balansvergelijkingen + de normeringsvoorwaarde een oplossing heeft,
en deze oplossing is de limietdistributie en is uniek
– in de context van de wachtlijntheorie komt deze voorwaarde in de
praktijk neer op de eenvoudige eis p0 > 0
– fysische voorwaarde ρ < 1 is bij BD-wachtlijnsystemen equivalent
met mathematische voorwaarde p0 > 0
Bedoeling van dit hoofdstuk
•
•
•
Regimegedrag bepalen van enkele belangrijke BD-wachtlijnsystemen
Algemene aanpak
1) mathematische beschrijving van het wachtlijnsysteem, b.v. via
Kendall-notatie
2) identificeren van het corresponderende BD-proces, d.w.z. bepalen van
geboorte-intensiteiten λk en overlijdensintensiteiten µk
3) opstellen van toestandsdiagram
4) opstellen van balansvergelijkingen (op zicht uit diagram)
5) bepalen van regimedistributie en evenwichtsvoorwaarde door oplossen
van het stelsel der balansvergelijkingen en de normeringsvoorwaarde
6) afleiden van gewenste kenmerkende grootheden van het systeem
Resultaten: verschaffen inzicht in de kwalitatieve aspecten van
wachtlijnsystemen in het algemeen, hoewel gebruikte analysemethode
alleen toepasbaar is voor Markoviaanse (en BD-)wachtlijnsystemen
Het M|M|1-wachtlijnsysteem
• Meest eenvoudige niet-triviale voorbeeld van BD-wachtlijnsysteem
• Het best bekende wachtlijnmodel in continue tijd
• Definitie: wachtlijnsysteem met
– i.i.d. exponentieel verdeelde interarrivaltijden (Poissonproces)
a(t ) = λ e − λt ,
E[t n ] = 1 λ
– i.i.d. exponentieel verdeelde servicetijden
b(x) = µ e −µx ,
–
–
−
−
E[x n ] = 1 µ
onderling onafhankelijke interarrivaltijden en servicetijden
1 server
oneindige opslagcapaciteit
oneindige klantenpopulatie
M|M|1 – onderliggend BD-proces
• Belangrijke eigenschap: de systeembevolking N(t) in een M|M|1-systeem
is een birth-death-proces, met
– constante geboorte-intensiteiten: λk = λ , k ≥ 0
– constante afsterfintensiteiten: µk = µ , k ≥ 1
• Bewijs
– proces met discrete toestandsruimte ℕ = {0, 1, 2, ...}
– alleen transities tussen naburige toestanden, nl. k → k+1 bij een arrival,
k → k-1 bij een departure
– kans op een transitie k → k+1 = kans op een nieuwe aankomst =
kans dat de aan de gang zijnde interarrivaltijd beëindigd wordt, tussen t
en t+dt = λ dt, omdat interarrivaltijden exponentieel verdeeld zijn met
parameter λ → dit alles ongeacht t en N(u) voor u ≤ t
– kans op een transitie k → k-1 (k ≥ 1) ... = µ dt (analoog)
– kans op meerdere transities tussen t and t+dt is verwaarloosbaar t.o.v.
dt, b.v. 1 arrival + 1 departure → λ dt ⋅ µ dt
M|M|1 – analyse van het systeemgedrag
• Systeembevolking N(t)
– vormt BD-proces met constante geboorte-intensiteiten λ en
constante afsterfintensiteiten µ
– resultaat is van groot belang: legt verband tussen fysisch systeem
(M|M|1) en goedgekend wiskundig concept (BD-proces)
• Tijdsafhankelijk gedrag
– kan in principe bepaald worden door oplossing van de
bewegingsvergelijkingen van onderliggend BD-proces
– valt vrij lastig uit → Pk(t) in termen van Besselse functies
• Regimegedrag
– reflecteert de “echte” werking van het systeem, na een zeker
overgangsverschijnsel
– veel minder gecompliceerd dan het vinden van tijdsafhankelijke
resultaten
M|M|1 - distributie van de systeembevolking - 1
• Toestandsdiagram
λ
λ
0
1
µ
λ
λ
...
2
µ
λ
µ
k-1
µ
λ
k
µ
• Balansvergelijkingen
λ p k −1 = µ p k
...
k+1
µ
µ
k
λ
 λ
p k = p k −1 =   p 0
 µ
µ
⇒
• Bezettingsgraad + evenwichtsvoorwaarde :
λ
ρ = λ⋅x = <1
µ
λ
⇔
λ<µ
M|M|1 - distributie van de systeembevolking - 2
• Normeringsvoorwaarde
∞
∞
k =0
k =0
k
∑ pk = 1 ⇔ p0 ⋅ ∑ ρ = 1
⇒ p0 = 1
∞
∑ ρk > 0
⇔ som convergeert ⇔ ρ < 1
k =0
1
⇒ p0 = 1
= 1 − ρ → klopt met ρ = 1- p0 voor
1− ρ
G|G|1-systeem in regime
• Massafunctie van de systeembevolking
p k = (1 − ρ ) ρ k , k ≥ 0
→ geometrisch met parameter ρ
ρ
ρ
2
• Momenten van de systeembevolking: N =
; σN =
1− ρ
(1 − ρ)2
• Gemiddelde systeemtijd: T =
1µ
x
=
1− ρ 1− ρ
(uit Little : N = λ T )
M|M|1 - distributie van de systeembevolking - 3
• Systeembevolking
– geometrisch verdeeld met parameter ρ (geheugenloos)
pk = (1 – ρ) ρk , k ≥ 0 ; p0 = 1 - ρ
– alleen afhankelijk van de verhouding ρ = λ/µ
intuïtief duidelijk: verdubbel λ en µ …
pk
pk
1
1
0,8
ρ = 0,2
→ “lage” bezettingsgraad
ρ = 0,8
→ “hoge” bezettingsgraad
0,2
0
0
1
2
3
4
5
6
k
0
0
1
2
3
4
5
6
k
M|M|1 - gemiddelde systeembevolking
N=
ρ
1− ρ
N
verticale asymptoot
9
1
•
0
(0 ≤ ρ < 1)
0,5
• voor ρ = 0
•
• voor ρ → 1 → N → ∞
(instabiel systeem)
3
•
0,75 0,9 1
→ N =0
ρ
M|M|1-systeem is instabiel voor ρ = 1: omdat alle interarrivaltijden en
servicetijden onderling onafhankelijk zijn: perfecte coördinatie tussen de
klanten die nodig zou zijn om systeem stabiel te houden bij ρ = 1, ontbreekt
M|M|1 - gemiddelde systeemtijd
T=
T
x
1µ
=
1− ρ 1− ρ
2/µ
1/µ •
0
• waarde van T niet louter bepaald
door de verhouding ρ = λ/µ
verticale
asymptoot
10/µ
•
0,5
(0 ≤ ρ < 1)
• voor ρ → 0 → T = x = 1/µ
verklaring : systeem bijna altijd
ledig (p0 → 1)
⇒ klanten hoeven nooit te wachten
•
4/µ
•
0,75 0,9 1
ρ
• voor ρ → 1 → T → ∞
(instabiel systeem)
Wachtlijngedrag voor hoge bezettingsgraad
• Stabiliteitsvoorwaarde
– performantie wordt blijkbaar op dramatische wijze slechter naarmate de
bezettingsgraad dichter bij 1 komt te liggen
– bezettingsgraad < 1 betekent dat er gemiddeld per tijdseenheid minder
werk in het systeem binnenkomt dan het systeem aankan
– onregelmatigheid van aankomsten en verwerkingen, d.w.z. variantie op
interarrivaltijden en servicetijden kan wel tijdelijke opstapelingen van
werk veroorzaken
– bij hoge ρ kunnen blijkbaar lange wachtrijen en vertragingen optreden
• Praktische betekenis
– er bestaat een “trade-off” tussen goede bezettingsgraad/throughput en
goede bedieningskwaliteit (d.w.z. lage gemiddelde systeemtijd)
– wet van behoud van miserie
– de gierigheid bedriegt de wijsheid
– wie het onderste uit de kan wil, krijgt het deksel op de neus
Invloed van de wachtlijndiscipline
• Toepasbaarheid van de tot nu toe bekomen resultaten
– de bekomen resultaten m.b.t. de systeembevolking (distributie,
gemiddelde waarde, variantie) zijn geldig van zodra het bestudeerde
toestandsdiagram van toepassing is
– veronderstelt dat de (resterende) servicetijd van de klant in de serviceeenheid exponentieel verdeeld is met “overlijdensintensiteit” µ
– geldig voor FCFS, maar ook voor alle andere werkconserverende
wachtlijndisciplines indien althans de volgorde van bediening niet
gebaseerd is op kennis van de individuele bedieningstijden der
klanten (b.v. steeds langste of kortste service eerst)
– gemiddelde systeemtijd werd bekomen uit de stelling van Little, die
van toepassing is voor alle mogelijke wachtlijndisciplines
• Distributie van de systeemtijd
– is wel afhankelijk van de wachtlijndiscipline, omdat individuele
systeemtijden sterk beïnvloed worden door volgorde van bediening
Gemiddelde systeemtijd is ± onafhankelijk van
de wachtlijndiscipline
•
Intuїtieve verklaring
(1)
B A X X X
X
Als B A “voorsteekt”, dan zal systeemtijd van A verhogen en
systeemtijd van B verlagen ten bedrage van 1 servicetijd → gemiddeld
gezien evenveel → T ongewijzigd
(2)
B A3 A2 A1 X
X
Als B A1, A2 en A3 “voorsteekt”, dan ziet elk der klanten A1, A2 en A3
zijn systeemtijd met 1 servicetijd verhogen, terwijl de systeemtijd van B
met 3 servicetijden vermindert → gemiddeld gezien evenveel → T
ongewijzigd
De PASTA-eigenschap - 1
• Gegeven
– wachtlijnsysteem in regimetoestand met Poisson-aankomstproces
(onafhankelijk van het bedieningsproces)
– eindige of oneindige opslagcapaciteit
– 1 of meerdere servers
• Systeembevolking: aantal klanten in het systeem
– op totaal willekeurig ogenblik in regime → N
– zoals waargenomen door een willekeurige aankomende klant in
regime, d.w.z. vlak voor een willekeurig aankomsttijdstip in regime
→ Na
• PASTA-eigenschap: N en Na hebben dezelfde distributie
Prob[N = n] = Prob[N a = n] ,
∀n ≥ 0
De PASTA-eigenschap - 2
•
Interpretaties
– fractie van de tijd dat het systeem n klanten bevat = fractie van de
aankomsten die n klanten in het systeem aantreffen: Poisson
Arrivals See Time Averages
– waarneming van het systeem alleen op Poisson-aankomsttijdstippen
levert zelfde “beeld” als totaal willekeurige waarneming: random
observer property
•
“Bewijs”
– nieuwe Poisson-aankomsten zijn onafhankelijk van vroegere
aankomsten (en bedieningen) en dus van de momentele
systeembevolking: zij hebben geen voorkeur voor bepaalde
waarden van de systeembevolking
– omgekeerd: systeembevolking op tijdstip t onafhankelijk van al dan
niet aankomen van een klant tussen t en t + dt
“ASTA” geldt niet algemeen
• “ASTA” geldt niet algemeen
– N en Na hebben in het algemeen niet dezelfde distributie
– men kan een “verkeerd beeld” krijgen van een systeem als men
het alleen op geselecteerde tijdstippen observeert
~
• Voorbeeld: D|D|1-systeem: t = 4 min en ~x = 3 min constant
...
...
tijd
ρ = ¾ = 0.75
• Distributie van N:
Prob[N=0] = p0 = 0,25
Prob[N=1] = p1 = 0,75
• Distributie van Na:
Prob[Na=0] = 1
Prob[Na=1] = 0
M|M|1 - densiteit van de systeemtijd (FCFS) - 1
• Gegeven
– M|M|1-wachtlijnsysteem in regimetoestand
– klanten worden bediend in volgorde van aankomst (FCFS)
• Gevraagd
– volledige distributie van de systeemtijd van een willekeurige klant
• Definities
C → willekeurige klant aankomend in het systeem, in regime
Na → aantal klanten in het systeem vlak vóór aankomst van C
~s → systeemtijd van klant C, met densiteit s(y)
C
Na
.
.
.
3
2
1
M|M|1 : densiteit van de systeemtijd (FCFS) - 2
• Vanwege de FCFS-discipline : ~s = x1′ + x 2 + ... + x N a + x N a +1
↓ ↓
↓
↓
resterende servicetijd volledige servicetijden
⇒ ~s = som van (Na+1) i.i.d. exponentiële (µ) grootheden
⇒ bij gegeven Na = n → Erlangdistributie van orde n+1
n
µ
(
y
)
s( y | N a = n ) = µ e −µy
n!
⇒ onvoorwaardelijke densiteit via uitmiddeling over Na:
∞
s(y) = ∑ Pr ob[N a = n] s(y | N a = n)
PASTA
n=0
∞
= ∑ (1 − ρ) ρ µ e
n=0
n
(µy) = µ 1 − ρ e − µ (1−ρ)y
( )
n!
n
− µy
exponentiële
(µ(1-ρ))
Het M|M|∞-wachtlijnsysteem
• Definitie
– onderling onafhankelijke exponentiële interarrivaltijden en
servicetijden
– onbeperkt aantal onderling equivalente servers
(µ)
Poisson
λ
wachtlijn overbodig
..
.
a(t ) = λ e − λt
b(x) = µ e −µx
• Corresponderend BD-proces: indien k klanten aanwezig
Prob[1 departure in (t, t +dt)] = µ dt + ... + µ dt - o(dt)
(kµ) dt
Prob[geen departure in (t, t +dt)] = (1- µ dt)k ≈ 1- k µ dt
⇒ BD-proces met λk = λ (k ≥ 0) en µk = kµ (k ≥ 1)
M|M|∞ - distributie van de systeembevolking
• Toestandsdiagram
λ
λ
0
1
µ
λ
...
2
2µ
λ
λ
k-1
3µ
k
kµ
• Analyse: λ pk-1 = k µ pk ,
λ
λ
k+1
(k+1)µ
k≥1
k
 λ 
λ 1
⇒ p k =   p k −1 =  
p0 ,
 kµ 
 µ  k!
k≥0
k
(
λ µ)
∑ pk = p0 ∑
= p 0 e λ µ = 1 ⇒ p 0 = e −λ µ
∞
∞
k!
k
⇒ p k = e −λ µ (λ µ ) k!
k =0
k =0
→ Poissondistributie (λ/µ)
...
M|M|∞ - diverse resultaten
• Evenwichtsvoorwaarde: altijd vervuld
1) p 0 = 1
∞
∑
k =0
(λ µ ) k
k!
altijd > 0
(reeks convergeert voor alle λ, µ)
2) oneindig aantal servers ⇒
ρ=
λµ
=0 <1
∞
3) hoe snel het werk ook binnenkomt in het systeem, de serviceeenheid beschikt altijd over voldoende middelen om dit werk
op te knappen
• Momenten van de systeembevolking
Poissondistributie (λ/µ) ⇒
N = σ 2N = λ µ
M|M|∞ - diverse resultaten
• Systeemtijden: gemiddelde waarde en densiteit
– stelling van Little ⇒
T = N λ =1 µ
– oneindig aantal servers ⇒ geen wachttijden
⇒ systeemtijd = servicetijd ⇒ s(y) = µ e-µy
• Belang van het M|M|∞-systeem
– limiet van het M|M|m-systeem en het M|M|m|m-systeem voor m → ∞
– studie van het vereist aantal servers bij gegeven λ, µ
– studie van “zuivere tijdsvertraging” met exponentiële distributie
– didactisch / pedagogisch
Controleberekening: gemiddeld aantal bezette servers
– stelling van Little ⇒ N s = λ ⋅ x = λ µ
– geen wachtlijn ⇒ N = N s = λ µ (zonder balansvergelijkingen)
Het M|M|m-wachtlijnsysteem
• Definitie
– onderling onafhankelijke exponentiële interarrivaltijden en
servicetijden
– m > 1 onderling equivalente servers, oneindige opslagcapaciteit
corresponderend BD-proces:
(µ)
Poisson
λ
λk = λ ,
1
2
...
k µ ,
µk = 
m µ ,
m
• Toestandsdiagram
λ
0
λ
1
µ
λ
2
2µ
λ
...
k≥0
λ
m-1
3µ (m-1)µ
λ
m
mµ
k≥m
λ
...
m+1
mµ
0≤ k ≤ m
mµ
M|M|m - distributie van de systeembevolking
• Bezettingsgraad + evenwichtsvw. : ρ = λ x m = λ (mµ ) < 1 ⇔ λ < mµ
• Analyse van de distributie van de systeembevolking
k

λ µ)
λ
(
p
k
p
p
p0 , 1 ≤ k ≤ m
p
λ k −1 = µ k ⇒ k =
k −1 =
kµ
k!


k−m
 λ p = mµ p ⇒ p = λ p =  λ 
pm , k ≥ m


k −1
k
k
k −1

 mµ 
mµ
mρ)
(
=
k
⇒ pk
k!
m mρ k
p 0 (0 ≤ k ≤ m) of
p 0 (k ≥ m)
m!
m−1 (mρ)k (mρ)m ∞ k − m 
normering
⇒ p 0 ∑
+
ρ =1
∑
m! k = m
 k =0 k!

m
convergeert
 m−1 (mρ)k
mρ) 
(
⇒ p0 = 1  ∑
+

⇔ρ<1
m! (1 − ρ)
 k =0 k!
M|M|m - diverse resultaten
• Momenten van de systeembevolking
– te berekenen uit de massafunctie pk
ρ (mρ)m
N = ∑ k p k = mρ + p 0
2
m! (1 − ρ)
k=0
∞
∞
σ 2N = ∑ k 2 p k − (N )2 → ingewikkeld resultaat
k =0
• Gemiddelde systeemtijd
– uit de stelling van Little
T=N λ
• Volledige distributie van de systeemtijd voor FCFS-wachtlijndiscipline
– via aparte, vrij ingewikkelde berekening (zie verder)
– densiteit = gewogen som van 2 exponentiëlen met parameters µ en mµ-λ
M|M|m - diverse resultaten
• Volledige distributie van de systeemtijd (FCFS)
– beschouw een willekeurige klant C die in het systeem aankomt
in regime
– N a → systeembevolking vlak vóór de aankomst van klant C
– ~s → systeemtijd van klant C
• Twee gevallen te onderscheiden
1) Na < m: ≥ 1 server vrij ⇒ ~s = x C → exponentieel (µ)
2) Na ≥ m: geen server vrij ⇒ C moet aanschuiven tot Na- m+1
klanten bediend zijn:
~s = y + y + L + y
+x
1
2
N a − m +1
↓ ↓
↓
i.i.d. exponentieel (mµ)
C
↓
exponentieel (µ)
Erlang’s C-formule (delay-formule)
• Kans dat een aankomende klant moet wachten: q
q = Prob[N a ≥ m]
∞
= ∑ pk
k =m
(PASTA)
m 
 (mρ )m   m −1 (mρ )k
ρ
(
)
m
 ∑

= 
+
  k =0 k!

−
ρ
−
ρ
m
!
1
m
!
1
(
)
(
)

 

• Toepassing: telefonie
– telefooncentrale = multiserver-wachtlijnsysteem met wachtruimte
– klanten zijn telefoonoproepen
– servers zijn lijnen in de centrale
– servicetijd = gespreksduur van een klant (tijd dat lijn bezet is)
– de formule (Erlang C) geeft de kans dat in een centrale met m lijnen
alle lijnen bezet zijn wanneer een abonnee een gesprek aanvraagt
M|M|m – gemiddeld aantal bezette servers
• Aantal bezette servers: Ns = min(N, m)
• Gemiddeld aantal bezette servers
∞
N s = ∑ min(k , m) p k
k =0
m
=∑
mρ)
(
k
k =1
k
k!
∞
m mρ k
p0 + ∑ m
p0
m!
k = m +1
 m (mρ)k −1 (mρ)m ∞ k − m−1 
= (mρ) p 0 ∑
+
ρ

∑
k
m
1
!
!
−
)
k = m +1
 k =1 (

m
m−1 (mρ)k
m
ρ)  1/(1-ρ)
(
= (mρ) p 0 ∑
+

m! (1 − ρ)
k =0 k!
= mρ
1/p0
λ
λ
= mρ
• Controle: stelling van Little: N s = λ x = = m
µ
mµ
Het M|M|1|K-wachtlijnsysteem
• Definitie
– onderling onafhankelijke exponentiële interarrivaltijden en
servicetijden
– 1 server
– eindige opslagcapaciteit = K ≥ 1 (wachtlijn + server)
Poisson
λ
λeff
(µ)
K . . . 3 2 1
ν
verloren klanten
γ
bediende
klanten
• Corresponderend BD-proces
λ ,
λk = 
0 ,
µk = µ ,
0 ≤ k ≤ K −1
k = K → klanten worden niet meer binnengelaten
k ≥1
M|M|1|K - distributie van de systeembevolking - 1
• Toestandsdiagram: eindig
λ
0
λ
1
µ
λ
λ
...
2
µ
λ
K-2
µ
µ
λ
K-1
µ
K
µ
• Analyse van de distributie van de systeembevolking (α ≜ λ/µ)
λ p k −1 = µ p k ⇒ p k = (λ µ ) p k −1 = α p k −1 = α k p 0 , 0 ≤ k ≤ K
normering
⇒
K
K
k =0
k =0
k
p
p
=
α
∑ k 0 ∑ = 1 ⇒ p0 = 1
(
(1 − α ) α k 1 − α K +1
⇒ pk = 
1 (K + 1)
K
k
α
∑
k =0
) (α ≠ 1) → afgebroken geometrische
(α = 1)
→ uniforme distributie
M|M|1|K - distributie van de systeembevolking - 2
•
Evenwichtsvoorwaarde: altijd vervuld
–
k
α
∑
altijd > 0 (eindige som)
k =0
–
waarden van λ en µ (of α) spelen geen rol
–
bezettingsgraad ρ = 1 - p0 altijd < 1
–
•
p0 = 1
K
instabiliteit (oneindig lange wachtrijen) a priori uitgesloten vanwege
de eindige capaciteit; het systeem laat niet meer klanten binnen dan
het kan verwerken (zelfregelend systeem)
Gedrag voor grote K
– als α < 1 (λ < µ) herleidt de regimedistributie zich voor K→∞ tot een
geometrische distributie met parameter α (resultaat voor M|M|1)
– als α ≥ 1 (λ ≥ µ) dan gaan voor K→∞ alle pk’s naar nul en bestaat er
geen limietdistributie
M|M|1|K - distributie van de systeembevolking - 3
(
• Algemeen:
)
(1 − α ) α k 1 − α K +1 ,
pk = 
,
1 (K + 1)
0≤ k≤ K
0≤ k≤ K
(α ≠ 1)
(α = 1)
• Voorbeeld: K=4
pk
16
31
8
31
0
α = 0.5
α=1
“onderbelast”
pk “kritisch belast”
4
31
1
2
2
31
3
1
31
4
k
↓
pK > 0, zelfs bij λ < µ
pk
1
5
1
5
1
2
3
4
k
16
31
2
31
1
31
0
α=2
“overbelast”
0
1
8
31
4
31
2
3
4
↓
p0 > 0, zelfs bij λ > µ
k
M|M|1|K – gemiddelde systeembevolking - 1
• Momenten van de systeembevolking
K
– worden gemakkelijkst berekend uit de genererende functie P(z) = ∑ p k z k
k =1
• Gemiddelde systeembevolking
voor α = 1
K/2
K
dP(z)
= ∑ k pk =
N=
(K + 1) α K +1
α
dz z=1 k =0
voor α ≠ 1
−
K +1
1− α
1− α
• Bespreking
1) α = 0 ⇒ N = 0 : systeem altijd ledig
2) α → ∞ ⇒ N → K : systeem altijd vol
α
3) α < 1, K → ∞ ⇒ resultaat van M|M|1: N ∞ =
1− α
4) α < 1:: N < N ∞ , omdat in een eindig systeem sommige klanten
geweigerd worden
M|M|1|K - gemiddelde systeembevolking - 2
α
(K + 1)α K +1
−
N =
, voor α ≠ 1
K +1
1− α
1− α
N
40
K=∞
30
K=20
20
K=10
10
0
N = K / 2 , voor α = 1
K=30
0
1
2
3
4
5
α
M|M|1|K - gemiddelde systeembevolking - 3
N
α
(K + 1)α K +1
−
N =
, voor α ≠ 1
K +1
1− α
1− α
α=1.2
α=1.1
40
α=1
N = K / 2 , voor α = 1
α=∞
30
α=0.95
20
α=0.9
10
α=0.8
0
0
20
40
60
80
100
K
M|M|1|K - diverse resultaten - 1
• Gemiddelde effectieve aankomstintensiteit: λeff
1) via conditionering op het aantal klanten (k) in het systeem
K
K −1
k =0
k =0
λ eff = ∑ λ k p k = λ ∑ p k + 0 ⋅ p K = λ (1 − p K )
2) via PASTA-eigenschap: kans op effectieve aankomst in een
infinitesimaal interval van lengte dt = kans op Poisson-aankomst
in dat interval × Prob[systeem niet vol vlak daarvoor]
λ eff dt = (λ dt ) (1 − p K ) ⇒ λ eff = λ (1 − p K )
• Gemiddelde systeemtijd: via de stelling van Little
T = N λ eff
M|M|1|K - diverse resultaten - 2
• Bezettingsgraad / gemiddeld aantal bezette servers
– uit definitie of stelling van Little
1
1
ρ = N s = λ eff ⋅ = λ (1 − p K ) ⋅ = α(1 − p K )
µ
µ
– uit de evenwichtsdistributie
ρ = Ns = 1 − p0
– resultaat altijd kleiner dan 1
α − α K +1
α K +1 − α
ρ=
of ρ = K +1
K +1
1− α
α −1
• Belasting (load) van het M|M|1|K-wachtlijnsysteem
1
– aangeboden werk (offered load): α = λ ⋅
µ
1
ρ
=
λ
⋅
– uitgevoerd werk (carried load):
eff
µ
M|M|1|K – verlieskans en verliesdebiet
• Definitie verlieskans (overflow-waarschijnlijkheid)
– kans dat een aankomende klant geweigerd wordt
(1 − α)α K
Pr ob[ N a = K ] = p K =
1 − α K +1
• Bespreking
– onderbelast systeem: α < 1 of λ < µ ⇒ er worden soms klanten
verloren, vanwege de “onregelmatigheid” van aankomsten en
bedieningen; voor K >> 1 wordt pK een exponentieel (geometrisch)
dalende functie van K : factor α per extra plaats:
pK ≈ (1 − α) αK
– overbelast systeem: α > 1 of λ > µ ⇒ er worden zeker sommige
klanten verloren; voor K >> 1 wordt pK onafhankelijk van K:
pK ≈ 1- 1/α (p0 > 0) d.w.z. circa 1 op α klanten wordt bediend
• Verliesdebiet (verliesintensiteit): ν = λ - λeff = λ pK
M|M|1|K – verlieskans - 1
1 − α) α K
(
pK =
K +1
pK
1− α
1.00E+00
onderbelaste systemen
1.00E-01
1.00E-02
α = 0.9
1.00E-03
α = 0.8
1.00E-04
1.00E-05
0
20
↑ 40
34
60
↑
66
80
100
K
M|M|1|K – verlieskans - 2
pK
α=1.5
0.1
α=1
10-2
10-3
10-4
α=0.8
0
(α ≠ 1)
1
pK =
K +1
(α = 1)
1− α
0
10-5
1 − α) α K
(
pK =
K +1
20
40
60
α=0.9
80
100
K
M|M|1|K - densiteit van de systeemtijd (FCFS) - 1
• Gegeven
– M|M|1|K-wachtlijnsysteem in regimetoestand
– klanten worden bediend in volgorde van aankomst (FCFS)
• Gevraagd
– volledige distributie (densiteit s(y)) van de systeemtijd van een
willekeurige klant die effectief in het systeem binnenkomt
Poisson
K . . . 3 2 1
• Oplossing
K −1
s(y) = ∑ Prob[N a = n] µ e − µy
n=0
(µy)
n
n!
(zie M|M|1)
met Na = systeembevolking vlak vóór een effectief aankomsttijdstip
M|M|1|K - densiteit van de systeemtijd (FCFS) - 2
• Systeembevolking op verschillende observatietijdstippen
N → systeembevolking op een totaal willekeurig tijdstip
N* → systeembevolking vlak vóór een Poisson-aankomsttijdstip
Na → systeembevolking vlak vóór een effectief aankomsttijdstip
tijd
→ willekeurige tijdstippen
→ Poisson-aankomsttijdstippen
→ 0 ≤ N* ≤ K
→ effectieve aankomsttijdstippen in systeem →
N* < K
M|M|1|K - densiteit van de systeemtijd (FCFS) - 3
• Distributie van Na: berekening in twee stappen
[
]
1) Prob N * = n = Prob[ N = n] = p n (PASTA)
[
2) Prob[ N a = n] = Prob N * = n | N * < K
 pn

= 1 − p K
0
]
0 ≤ n ≤ K −1
n=K
• Gemiddelde systeemtijd
– zelfde resultaat als via de stelling van Little
Het M|M|m|m-wachtlijnsysteem (m-server loss system)
• Definitie
– onderling onafhankelijke exponentiële interarrivaltijden en servicetijden
– aantal servers = opslagcapaciteit = m
(µ)
1
λ ,
λk = 
0 ,
µk = k µ ,
2
...
Poisson
λ
↓
geen wachtlijn
corresponderend BD-proces
m
0 ≤ k ≤ m−1
k=m
1≤k≤m
• Toestandsdiagram: eindig
λ
0
λ
1
µ
λ
2
2µ
λ
...
λ
m-1
3µ (m-1)µ
m
mµ
M|M|m|m - distributie van de systeembevolking
• Analyse van de distributie van de systeembevolking
k
λ p k −1
1  λ
λ
p k −1 =   p 0 , 0 ≤ k ≤ m
= k µ pk ⇒ pk =
kµ
k!  µ 
λ µ)
(
⇒ ∑ p k = 1 ⇒ p0 = 1 ∑
n!
k =0
n=0
m
normering
m
n
altijd > 0
• Evenwichtsdistributie van de systeembevolking
pk =
1 λ
 
k! µ 
k
1 λ
 
n =0 n! µ 
m
∑
n
, 0≤k≤m
(afgebroken Poissondistributie)
Erlang’s B-formule (loss-formule)
• Kans dat een aankomende klant alle servers bezet vindt / verlieskans
Pr ob [ N a = m] = p m =
1 λ
 
mµ
m
1 λ
∑
 
n =0 n! µ 
m
n
, 0≤k≤m
(PASTA)
• Toepassing: telefonie
– telefooncentrale = multiserver-wachtlijnsysteem zonder wachtruimte
– klanten zijn telefoonoproepen
– m servers zijn lijnen in de centrale
– servicetijd = gespreksduur van een klant (tijd dat lijn bezet is)
– de formule (Erlang B) geeft de kans dat in een centrale met m lijnen
(zonder wachtruimte) alle lijnen bezet zijn wanneer een abonnee een
gesprek aanvraagt, d.w.z. kans dat een oproep geweigerd wordt
– formule werd voor het eerst afgeleid in 1917
M|M|m|m – diverse resultaten
• Gemiddelde systeembevolking
m
m
N = ∑ k p = (λ µ ) ∑ p
= (λ µ ) 1 − p
k
k -1
m
k =1
k =1
(
• Gemiddelde effectieve aankomstintensiteit: λeff
λ eff = λ (1 − p m )
• Gemiddelde systeemtijd: T
N 1
T=
=
λ eff µ
• Densiteit van de systeemtijd: s(y)
s( y) = µ e −µy
• Bezettingsgraad
ρ = λ eff x m = λ (1 − p m ) (mµ ) = N m
altijd < 1
)
Slotopmerkingen hoofdstuk 3
• Alle tot nog toe beschouwde wachtlijnsystemen waren birthdeath-wachtlijnsystemen
– M|M|1 , M|M|∞ , M|M|m
– M|M|1|K , M|M|m|m
• Birth-death-karakter was gevolg van
– i.i.d. exponentieel verdeelde interarrivaltijden en servicetijden
– enkelvoudige aankomsten en enkelvoudige bedieningen
• Er zijn nog vele andere birth-death-wachtlijnsystemen
– andere keuzen voor geboorte- en afsterfintensiteiten (λk en µk)
– corresponderende interarrivaltijden en servicetijden en zelfs
aantal servers zijn dan niet noodzakelijk gemakkelijk te
karakteriseren
– zie verder in de oefeningenlessen

Download Report