Přibližování hustého provozu - Heavy traffic approximation
v teorie front, disciplína v rámci matematické teorie pravděpodobnosti, a přiblížení hustého provozu (někdy teorém omezení silného provozu[1] nebo difúzní aproximace) je shoda modelu ve frontě s a difúzní proces pod některými omezující podmínky na parametrech modelu. První takový výsledek zveřejnil John Kingman kdo ukázal, že když parametr využití an Fronta M / M / 1 je blízko 1 a zmenšenou verzi procesu délky fronty lze přesně aproximovat pomocí a odráží Brownův pohyb.[2]
Silný dopravní stav
Pro proces se obvykle uvádějí aproximace silného provozu X(t) popisující počet zákazníků v systému v daném čase t. K nim se dospěje zvážením modelu pod mezními hodnotami některých parametrů modelu, a proto, aby byl výsledek konečný, musí být model změněn pomocí faktoru n, označeno[3]:490
a limit tohoto procesu je považován za n → ∞.
Existují tři třídy režimu, za kterých se takové aproximace obecně zvažují.
- Počet serverů je pevný a intenzita provozu (využití) se zvyšuje na 1 (zespodu). Aproximace délky fronty je a odráží Brownův pohyb.[4][5][6]
- Intenzita provozu je pevná a počet serverů a míra příjezdu se zvyšuje na nekonečno. Zde limit délky fronty konverguje k normální distribuce.[7][8][9]
- Množství β je fixní kde
- s ρ představující intenzitu provozu a s počet serverů. Intenzita provozu a počet serverů se zvyšují do nekonečna a omezující proces je hybridem výše uvedených výsledků. Tento případ, poprvé publikovaný Halfinem a Whittem, je často znám jako režim Halfin-Whitt[1][10][11] nebo režim založený na kvalitě a efektivnosti (QED).[12]
Výsledky pro frontu G / G / 1
Věta 1. [13] Zvažte posloupnost Fronty G / G / 1 indexováno podle .
Pro frontu
nechat označte čas náhodného příchodu, označte čas náhodné služby; označte intenzitu provozu pomocí a ; nechat označit čekací dobu ve frontě pro zákazníka v ustáleném stavu; Nechat a
Předpokládejme to , , a . pak
pokud:
(A)
b) pro některé , a jsou oba menší než nějaká konstanta pro všechny .
Heuristický argument
- Čekací doba ve frontě
Nechat je rozdíl mezi n-tou dobou služby a n-tou dobou mezi přílety; Let být čekací dobou ve frontě n-tého zákazníka;
Podle definice:
Po rekurzivním výpočtu máme:
- Náhodná procházka
Nechat , s jsou i.i.d; Definovat a ;
Pak máme
dostaneme převzetím limitu .
Tedy čekací doba ve frontě n-tého zákazníka je supremem a náhodná procházka se záporným driftem.
- Brownova aproximace pohybu
Náhodná procházka lze aproximovat pomocí a Brownův pohyb když se velikost skoku přiblíží 0 a časy mezi skokem se přiblíží 0.
My máme a má nezávislé a stacionární přírůstky. Když intenzita provozu přístupy 1 a má sklony k , my máme po výměně s kontinuální hodnotou podle funkční centrální limitní věta.[14]:110 Tak čekací doba ve frontě tohoto zákazníka lze aproximovat převahou a Brownův pohyb se záporným driftem.
- Supremum Brownova pohybu
Věta 2.[15]:130 Nechat být Brownův pohyb s driftem a směrodatná odchylka počínaje počátkem, a nechť
-li
v opačném případě
Závěr
- za hustého provozu
Heuristicky je tedy argumentována věta o omezení provozu (Theorem 1). Formální důkazy se obvykle řídí jiným přístupem, který zahrnuje charakteristické funkce.[4][16]
Příklad
Zvažte Fronta M / G / 1 s mírou příjezdu , průměr doby služby a rozptyl doby služby . Jaká je průměrná čekací doba ve frontě v ustálený stav ?
Přesná průměrná čekací doba ve frontě v ustálený stav darováno:
Odpovídající aproximace hustého provozu:
Relativní chyba aproximace hustého provozu:
Tak když , my máme :
externí odkazy
- Fronta G / G / 1 Sergej Foss
Reference
- ^ A b Halfin, S .; Whitt, W. (1981). „Limity silného provozu pro fronty s mnoha exponenciálními servery“ (PDF). Operační výzkum. 29 (3): 567. doi:10,1287 / opre.29.3.567.
- ^ Kingman, J. F. C.; Atiyah (říjen 1961). "Fronta pro jeden server v silném provozu". Mathematical Proceedings of the Cambridge Philosophical Society. 57 (4): 902. Bibcode:1961PCPS ... 57..902K. doi:10.1017 / S0305004100036094. JSTOR 2984229.
- ^ Gautam, Natarajan (2012). Analýza front: Metody a aplikace. CRC Press. ISBN 9781439806586.
- ^ A b Kingman, J. F. C. (1962). "Ve frontách v hustém provozu". Journal of the Royal Statistical Society. Řada B (metodická). 24 (2): 383–392. doi:10.1111 / j.2517-6161.1962.tb00465.x. JSTOR 2984229.
- ^ Iglehart, Donald L .; Ward, Whitt (1970). "Vícekanálové fronty v hustém provozu. II: Sekvence, sítě a dávky" (PDF). Pokroky v aplikované pravděpodobnosti. 2 (2): 355–369. doi:10.2307/1426324. JSTOR 1426324. Citováno 30. listopadu 2012.
- ^ Köllerström, Julian (1974). "Teorie silného provozu pro fronty s několika servery. I". Journal of Applied Probability. 11 (3): 544–552. doi:10.2307/3212698. JSTOR 3212698.
- ^ Iglehart, Donald L. (1965). "Omezení přibližných difúzí pro mnoho serverových front a problém opraváře". Journal of Applied Probability. 2 (2): 429–441. doi:10.2307/3212203. JSTOR 3212203.
- ^ Borovkov, A. A. (1967). "Zákony o omezení pro procesy služeb ve vícekanálových systémech". Sibiřský matematický deník. 8 (5): 746–763. doi:10.1007 / BF01040651.
- ^ Iglehart, Donald L. (1973). "Slabá konvergence v teorii front". Pokroky v aplikované pravděpodobnosti. 5 (3): 570–594. doi:10.2307/1425835. JSTOR 1425835.
- ^ Puhalskii, A. A .; Reiman, M. I. (2000). „Fronta GI / PH / N s více třídami v režimu Halfin-Whitta“. Pokroky v aplikované pravděpodobnosti. 32 (2): 564. doi:10,1239 / aap / 1013540179.
- ^ Reed, J. (2009). „Fronta G / GI / N v režimu Halfin-Whitt“. Annals of Applied Probability. 19 (6): 2211–2269. arXiv:0912.2837. doi:10.1214 / 09-AAP609.
- ^ Whitt, W. (2004). „Aproximace rušného provozu s vysokou efektivitou pro mnoho serverových front s opuštěním“ (PDF). Věda o řízení. 50 (10): 1449–1461. CiteSeerX 10.1.1.139.750. doi:10,1287 / mnsc.1040.0279. JSTOR 30046186.
- ^ Gross, D .; Shortie, J. F .; Thompson, J. M .; Harris, C. M. (2013). "Hranice a aproximace". Základy teorie front. 329–368. doi:10.1002 / 9781118625651.ch7. ISBN 9781118625651.
- ^ Chen, H .; Yao, D. D. (2001). „Technical Desiderata“. Základy sítí ve frontě. Stochastické modelování a aplikovaná pravděpodobnost. 46. 97–124. doi:10.1007/978-1-4757-5301-1_5. ISBN 978-1-4419-2896-2.
- ^ Chen, H .; Yao, D. D. (2001). "Fronty s jednou stanicí". Základy sítí ve frontě. Stochastické modelování a aplikovaná pravděpodobnost. 46. 125–158. doi:10.1007/978-1-4757-5301-1_6. ISBN 978-1-4419-2896-2.
- ^ Asmussen, S. R. (2003). "Stacionární vlastnosti GI / G / 1". Aplikovaná pravděpodobnost a fronty. Stochastické modelování a aplikovaná pravděpodobnost. 51. 266–301. doi:10.1007/0-387-21525-5_10. ISBN 978-0-387-00211-8.