Engsetův vzorec - Engset formula
v teorie front, Engsetův vzorec se používá k určení pravděpodobnosti blokování fronty M / M / c / c / N (v Kendallova notace ).
Vzorec je pojmenován po svém vývojáři, T. O. Engset.
Příklad aplikace
Zvažte flotilu vozidla a operátory. Provozovatelé vstupují do systému náhodně a žádají o použití vozidla. Pokud nejsou k dispozici žádná vozidla, je žádající operátor „zablokován“ (tj. Operátor odjíždí bez vozidla). Majitel vozového parku by si chtěl vybrat malé, aby se minimalizovaly náklady, ale dostatečně velké, aby zajistily tolerovatelnost pravděpodobnosti blokování.
Vzorec
Nechat
- být (celé číslo) počet serverů.
- být (celé číslo) počet zdrojů provozu;
- být míra příchodu nečinného zdroje (tj. míra, při které bezplatný zdroj iniciuje požadavky);
- být průměrná doba zadržení (tj. průměrná doba, kterou server potřebuje ke zpracování požadavku);
Poté pravděpodobnost blokování je dáno[1]
Přeskupením výrazů lze výše uvedený vzorec přepsat na[2]
kde je Gaussian Hypergeometrická funkce.
Výpočet
Existuje několik rekurzí[3] které lze použít k výpočtu numericky stabilním způsobem.
Alternativně jakýkoli číselný balíček, který podporuje Hypergeometrická funkce Některé příklady jsou uvedeny níže.
z scipy.special import hyp2f1P = 1.0 / hyp2f1(1, -C, N - C, -1.0 / (Lambda * h))
MATLAB s Symbolická matematická sada nástrojů
P = 1 / hypergeom([1, -C], N - C, -1 / (Lambda * h))
Neznámá míra příjezdu zdroje
V praxi se často stává, že míra příchodu zdroje není známo (nebo je těžké jej odhadnout) , nabízený provoz na zdroj je známo. V tomto případě lze vztah nahradit
mezi mírou příchodu zdroje a pravděpodobností blokování do vzorce Engset k dosažení rovnice pevného bodu
kde
Výpočet
Zatímco výše uvedené odstraní neznámé z vzorce zavádí další bod složitosti: už nemůžeme přímo vypočítat pravděpodobnost blokování a místo toho musíme použít iterační metodu. Zatímco iterace s pevným bodem je lákavé, ukázalo se, že taková iterace je někdy odlišný při aplikaci na .[2] Alternativně je možné použít jednu z půlení nebo Newtonova metoda, pro které implementace open source je k dispozici.
Reference
- ^ Tijms, Henk C. (2003). První kurz stochastických modelů. John Wiley and Sons. doi:10.1002 / 047001363X.
- ^ A b Azimzadeh, Parsiad; Carpenter, Tommy (2016). Msgstr "Rychlý výpočet Engsetu". Dopisy o operačním výzkumu. 44 (3): 313–318. arXiv:1511.00291. doi:10.1016 / j.orl.2016.02.011. ISSN 0167-6377.
- ^ Zukerman, Moshe (2000). „An Introduction to Queuing Theory and Stochastic Teletraffic Models“ (pdf). Citováno 2012-11-27.