Birth-death-wachtlijnsysteem

In de wachtrijtheorie is een birth-death-wachtlijnsysteem of BD-wachtlijnsysteem een wachtrijsysteem dat kan beschreven worden aan de hand van een birth-death-proces.

Bij een BD-wachtlijnsysteem laat men de aankomst van een klant in het systeem overeenkomen met een geboorte uit een BD-proces, het vertrek van een klant komt overeen met een overlijden in een BD-proces. Het proces ${\displaystyle N(t)}$ dat de systeembevolking op een tijdstip ${\displaystyle t}$ weergeeft, vormt dan een BD-proces. Op die manier kan het wachtrijsysteem door een toestandsdiagram gemodelleerd worden, waarna de evenwichtsvergelijking kunnen opgesteld worden. Uit deze evenwichtsvergelijkingen kan men dan de regimedistributie van de systeembevolking en andere interessante karakteristieken afleiden.

Voorbeeld

M|M|1-wachtrijsysteem

Een eenvoudig voorbeeld ter illustratie is het ${\displaystyle \mathrm {M|M|1} }$-wachtrijsysteem. In zo'n systeem is er één bedieningsstation. De tussenaankomsttijden onafhankelijk exponentieel verdeeld, het aankomstproces is dan een poissonproces. De bedieningstijden zijn eveneens exponentieel verdeeld. De opslagcapaciteit en de gebruikerspopulatie worden oneindig verondersteld. De parameter van de exponentiële verdeling van tussenaankomsttijden is ${\displaystyle \lambda }$, die van de bedieningstijden ${\displaystyle \mu }$, de verwachtingswaarden van die verdelingen zijn dan respectievelijk ${\displaystyle 1/\lambda }$ en ${\displaystyle 1/\mu }$. De systeembevolking ${\displaystyle N(t)}$ kan dan gemodelleerd worden als een BD-proces met constante geboorte-intensiteiten ${\displaystyle \lambda _{k}=\lambda ,\ k\geq 0}$, en constante sterfte-intensiteiten ${\displaystyle \mu _{k}=\mu ,\ k\geq 0}$.

Het is inderdaad zo dat de systeembevolking ${\displaystyle N(t)}$ in het systeem slechts kan overgaan naar een waarde 1 hoger of lager dan de huidige waarde, namelijk bij respectievelijke een aankomst of een vertrek van een klant. De geheugenloosheid van de exponentiële distributies van de interarrivaltijden en bedieningstijden, en de statistische onafhankelijkheden zorgen bovendien dat:

• de waarschijnlijk op een aankomst in een infinitesimaal interval van lengte ${\displaystyle \mathrm {d} t}$ is ${\displaystyle \lambda \mathrm {d} t}$, ongeacht de ligging en wat ervoor gebeurde
• de waarschijnlijk op een vertrek in een infinitesimaal interval van lengte ${\displaystyle \mathrm {d} t}$ wanneer een klant in verwerking is, is ${\displaystyle \mu \mathrm {d} t}$, ongeacht de ligging en wat ervoor gebeurde
• de waarschijnlijkheid om meer dan één aankomst en/of vertrek te hebben in een interval ${\displaystyle \mathrm {d} t}$ is verwaarloosbaar.

Deze eigenschappen samen tonen aan dat ${\displaystyle N(t)}$ een BD-proces is met constante geboorte-intensiteit en constante sterfte-intensiteit. Het fysisch wachtrijsysteem kan nu verder bestudeerd worden aan de hand van de wiskundige principes die gelden voor BD-processen. Men kan zoals voor elk BD-proces het systeem voorstellen door een toestandsdiagram, waaruit de evenwichtsvergelijkingen makkelijk af te leiden vallen.

Toestandsdiagram van een ${\displaystyle \mathrm {M|M|1} }$-wachtlijnsysteem

Beschouwt men bijvoorbeeld een oppervlak door de figuur, dan krijgt men de evenwichtsvergelijkingen:

${\displaystyle \lambda p_{k-1}=\mu p_{k},\ k\geq 1}$

daaruit volgt:

${\displaystyle p_{k}={\frac {\lambda }{\mu }}p_{k-1},\ k\geq 1}$

dus

${\displaystyle p_{k}=\left({\frac {\lambda }{\mu }}\right)^{k}p_{0},\ k\geq 0}$

De bezettingsgraad van dit systeem is gegeven door ${\displaystyle \rho =\lambda /\mu }$, de voorwaarde voor een stochastisch regime is dan ${\displaystyle \rho <1}$ of ${\displaystyle \lambda <\mu }$, wat ook volgt uit de normeringsvoorwaarde:

${\displaystyle p_{0}\sum _{k=0}^{\infty }\rho ^{k}=1}$

Deze reeks in het linkerlid convergeert dan en slechts dan, als ${\displaystyle \rho <1}$, en is gelijk aan:

${\displaystyle \sum _{k=0}^{\infty }\rho ^{k}={\frac {1}{1-\rho }}}$

Daaruit vindt men:

${\displaystyle p_{0}=1-\rho }$

De volledige regime-oplossing is dan:

${\displaystyle p_{k}=(1-\rho )\rho ^{k}}$;

het aantal klanten is dus een geometrisch verdeelde toevalsgrootheid met parameter ${\displaystyle \rho }$.

Door middel van verdere eigenschappen van de kansverdelingen kunnen andere grootheden van het wachtrijsysteem wiskundige worden afgeleid.

Andere voorbeelden

Andere voorbeelden van systemen die door midden van de BD-proces kunnen worden gemodelleerd, en dus birth-deatch-wachtrijsystemen zijn, zijn:

• ${\displaystyle \mathrm {M|M|} \infty }$, in zo'n geval zijn er oneindig veel servers en moet een klant nooit wachten. Wanneer er dus ${\displaystyle k}$ klanten aanwezig zijn, zijn er ${\displaystyle k}$ bedieningsstations actief, de sterfte-intensiteit bedraagt dan ook ${\displaystyle \mu _{k}=k\mu }$. Men kan afleiding dat de evenwichtsverdeling van ${\displaystyle p_{k}}$ een poissonverdeling is.
• ${\displaystyle \mathrm {M|M|m} }$, in zo'n geval geldt ${\displaystyle \mu _{k}=k\mu {\text{ voor }}0\leq k\leq m,\ \mu _{k}=m\mu {\text{ voor }}k\geq m}$.
• ${\displaystyle \mathrm {M|M|1|K} }$, waar een systeem niet meer dan ${\displaystyle K}$ klanten kan bevatten, is het systeem volzet wanneer een klant aankomt, dan gaat die verloren. Men kan afleiden dat de verdeling van ${\displaystyle p_{k}}$ een gebroken geometrische verdeling is.
• ${\displaystyle \mathrm {M|M|m|m} }$. Men kan afleiden dat de verdeling van ${\displaystyle p_{k}}$ een gebroken poissonverdeling is. Dit wachtlijnsysteem wordt gebruikt voor de afleiding van Erlangs B-formule.