Fórmula de Pollaczek–Khinchine - Wikiwand
For faster navigation, this Iframe is preloading the Wikiwand page for Fórmula de Pollaczek–Khinchine.

Fórmula de Pollaczek–Khinchine

De Viquipèdia

En teoria de cues, una disciplina que s'engloba dins de la teoria de la probablitat, la fórmula de Pollaczek–Khinchine afirma que hi ha una relació entre la longitud de la cua i les transformades de Laplace del temps de servei per una cua de tipus M/G/1 (en què la feina arriba seguint una distribució de Poisson i té una distribució de temps de servei general). El terme també s'usa per denominar les relacions entre la longitud mitjana de la cua i la mitjana del temps d'espera o de servei en aquest model.[1]

La fórmula va ser publicada per primer cop el 1930 per Félix Pollaczek el 1930[2] i readapta en termes probabilístics per Aleksandr Khintxin[3] dos anys més tard.[4][5] En teoria de risc, la fórmula es pot usar per calcular la probabilitat de ruina final (la probabilitat que una companyia d'assegurances faci fallida).[6]

Longitud mitjana de cua

La fórmula afirma que la longitud mitjana de la cua L ve donada per[7]

on

  • és el coeficient de Poisson de la taxa d'arribada
  • és la mitjana en la distribució de temps de servei S
  • és la utilització
  • Var(S) és la variància de la distribució de temps de servei S.

Perquè la longitud mitjana de la cua sigui finita, cal que , ja que, si no és així, la feina arriba a un ritme superior al que abandona la cua. La "intensitat de tràfic" pren valors del 0 a l'1, i és la fracció mitjana del temps en què el servidor està ocupat. Si la taxa d'arribada  és més gran o igual a la taxa de servei , el retard en la cua es fa infinit. Els termes de variància apareixen en l'expressió a causa de la paradoxa de Feller.[8]

Temps mitjà d'espera 

Si s'escriu W pel temps mitjà total, llavors  on   és el temps mitjà d'espera (temps en què el client està esperant) i és la taxa de servei. Utilitzant la llei de Little, que afirma el següent:

On

  • L és la longitud mitjana de cua
  • és la taxa d'arribada del procés de Poisson
  • W és el temps mitjà que s'està tant en cua com sent servit.

així

Es pot escriure una expressió per temps mitjà d'espera com:[9]

Transformada de la longitud de cua

Escrivint π(z) com la funció generatriu de probabilitats del nombre de client en una cua[10]

on g(s) és la transformada de Laplace de la funció densitat de la probabilitat de temps de servei.[11]

Transformada permanent del temps

Anotant W(s) com la transformada de Laplace–Stieltjes de la distribució del temps d'espera

on, un altre cop, g(s) és la transformada de Laplace de la funció densitat de la probabilitat de temps de servei. Es poden obtenir moments enèssims diferenciant al transformada n vegades, multiplicant per (−1)n i avaluant a s = 0.

Referències

  1. Asmussen, S. R.. «Random Walks». A: Applied Probability and Queues. 51, 2003, p. 220–243. DOI 10.1007/0-387-21525-5_8. ISBN 978-0-387-00211-8. 
  2. Pollaczek, F. «Über eine Aufgabe der Wahrscheinlichkeitstheorie». Mathematische Zeitschrift, 32, 1930, pàg. 64–100. DOI: 10.1007/BF01194620.
  3. Khintchine, A. Y «Mathematical theory of a stationary queue». Matematicheskii Sbornik, 39, 1932, pàg. 73–84 [Consulta: 14 juliol 2011].
  4. Takács, Lajos «Review: J. W. Cohen, The Single Server Queue». Annals of Mathematical Statistics, 42, 6, 1971, pàg. 2162–2164. DOI: 10.1214/aoms/1177693087.
  5. Kingman, J. F. C. «The first Erlang century—and the next». Queueing Systems, 63, 2009, pàg. 3–4. DOI: 10.1007/s11134-009-9147-4.
  6. Rolski, Tomasz; Schmidli, Hanspeter; Schmidt, Volker; Teugels, Jozef. «Risk Processes». A: Stochastic Processes for Insurance & Finance, 2008, p. 147–204. DOI 10.1002/9780470317044.ch5. ISBN 9780470317044. 
  7. Haigh, John. Probability Models. Springer, 2002, p. 192. ISBN 1-85233-431-2. 
  8. Cooper, Robert B.; Niu, Shun-Chen; Srinivasan, Mandyam M. «Some Reflections on the Renewal-Theory Paradox in Queueing Theory». Journal of Applied Mathematics and Stochastic Analysis, 11, 1998, pàg. 355–368 [Consulta: 14 juliol 2011].
  9. Harrison, Peter G.; Patel, Naresh M. Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley, 1992, p. 228. ISBN 0-201-54419-9. 
  10. Daigle, John N.. «The Basic M/G/1 Queueing System». A: Queueing Theory with Applications to Packet Telecommunication, 2005, p. 159–223. DOI 10.1007/0-387-22859-4_5. ISBN 0-387-22857-8. 
  11. Peterson, G. D.; Chamberlain, R. D. «Parallel application performance in a shared resource environment». Distributed Systems Engineering, 3, 1996, pàg. 9. DOI: 10.1088/0967-1846/3/1/003.
{{bottomLinkPreText}} {{bottomLinkText}}
Fórmula de Pollaczek–Khinchine
Listen to this article