词条 | Pollaczek–Khinchine formula |
释义 |
In queueing theory, a discipline within the mathematical theory of probability, the Pollaczek–Khinchine formula states a relationship between the queue length and service time distribution Laplace transforms for an M/G/1 queue (where jobs arrive according to a Poisson process and have general service time distribution). The term is also used to refer to the relationships between the mean queue length and mean waiting/service time in such a model.[1] The formula was first published by Felix Pollaczek in 1930[2] and recast in probabilistic terms by Aleksandr Khinchin[3] two years later.[4][5] In ruin theory the formula can be used to compute the probability of ultimate ruin (probability of an insurance company going bankrupt).[6] Mean queue lengthThe formula states that the mean queue length L is given by[7] where
For the mean queue length to be finite it is necessary that as otherwise jobs arrive faster than they leave the queue. "Traffic intensity," ranges between 0 and 1, and is the mean fraction of time that the server is busy. If the arrival rate is greater than or equal to the service rate , the queuing delay becomes infinite. The variance term enters the expression due to Feller's paradox.[8] Mean waiting timeIf we write W for the mean time a customer spends in the queue, then where is the mean waiting time (time spent in the queue waiting for service) and is the service rate. Using Little's law, which states that where
so We can write an expression for the mean waiting time as[9] Queue length transformWriting π(z) for the probability-generating function of the number of customers in the queue[10] where g(s) is the Laplace transform of the service time probability density function.[11] Waiting time transformWriting W*(s) for the Laplace–Stieltjes transform of the waiting time distribution,[12] where again g(s) is the Laplace transform of service time probability density function. nth moments can be obtained by differentiating the transform n times, multiplying by (−1)n and evaluating at s = 0. References1. ^{{Cite book | first1 = S. R. | last1 = Asmussen| doi = 10.1007/0-387-21525-5_8 | chapter = Random Walks | title = Applied Probability and Queues | series = Stochastic Modelling and Applied Probability | volume = 51 | pages = 220–243 | year = 2003 | isbn = 978-0-387-00211-8 | pmid = | pmc = }} {{Queueing theory}}{{DEFAULTSORT:Pollaczek-Khinchine formula}}2. ^{{cite journal|last=Pollaczek|first=F.|authorlink=Felix Pollaczek|year=1930|title=Über eine Aufgabe der Wahrscheinlichkeitstheorie|journal=Mathematische Zeitschrift|volume=32|pages=64–100|doi=10.1007/BF01194620}} 3. ^{{cite journal|last=Khintchine|first=A. Y|authorlink=Aleksandr Khinchin|year=1932|title=Mathematical theory of a stationary queue|journal=Matematicheskii Sbornik|volume=39|number=4|pages=73–84|url=http://mi.mathnet.ru/rus/msb/v39/i4/p73|accessdate=2011-07-14}} 4. ^{{cite journal|title=Review: J. W. Cohen, The Single Server Queue|first=Lajos|last=Takács|authorlink=Lajos Takács|journal=Annals of Mathematical Statistics|volume=42|issue=6|year=1971|pages=2162–2164|doi=10.1214/aoms/1177693087}} 5. ^{{Cite journal | last1 = Kingman | first1 = J. F. C. | authorlink1 = John Kingman | title = The first Erlang century—and the next | journal = Queueing Systems | volume = 63 | pages = 3–4 | year = 2009 | doi = 10.1007/s11134-009-9147-4}} 6. ^{{Cite book | first1 = Tomasz | last1 = Rolski| first2 = Hanspeter | last2= Schmidli| first3 = Volker | last3 = Schmidt| first4 = Jozef | last4 = Teugels| doi = 10.1002/9780470317044.ch5 | chapter = Risk Processes | title = Stochastic Processes for Insurance & Finance | series = Wiley Series in Probability and Statistics | pages = 147–204 | year = 2008 | isbn = 9780470317044 | pmid = | pmc = }} 7. ^{{cite book|title=Probability Models|page=192|last=Haigh|first=John|publisher=Springer|year=2002|isbn=1-85233-431-2}} 8. ^{{cite journal|title=Some Reflections on the Renewal-Theory Paradox in Queueing Theory|first1=Robert B.|last1=Cooper|first2=Shun-Chen|last2=Niu|first3=Mandyam M.|last3=Srinivasan|journal=Journal of Applied Mathematics and Stochastic Analysis|volume=11|number=3|year=1998|pages=355–368|url=http://www.cse.fau.edu/~bob/publications/CNS.4h.pdf|accessdate=2011-07-14}} 9. ^{{cite book|first=Peter G.|last=Harrison|authorlink=Peter G. Harrison|first2=Naresh M.|last2=Patel|title=Performance Modelling of Communication Networks and Computer Architectures|publisher=Addison-Wesley|year=1992|page=228|isbn=0-201-54419-9}} 10. ^{{Cite book | first1 = John N. | last1 = Daigle| doi = 10.1007/0-387-22859-4_5 | chapter = The Basic M/G/1 Queueing System | title = Queueing Theory with Applications to Packet Telecommunication | pages = 159–223 | year = 2005 | isbn = 0-387-22857-8 | pmid = | pmc = }} 11. ^{{Cite journal | last1 = Peterson | first1 = G. D. | last2 = Chamberlain | first2 = R. D. | doi = 10.1088/0967-1846/3/1/003 | title = Parallel application performance in a shared resource environment | journal = Distributed Systems Engineering | volume = 3 | pages = 9 | year = 1996 | pmid = | pmc = }} 12. ^{{Cite book | first1 = John N. | last1 = Daigle| doi = 10.1007/0-387-22859-4_5 | chapter = The Basic M/G/1 Queueing System | title = Queueing Theory with Applications to Packet Telecommunication | pages = 159–223 | year = 2005 | isbn = 0-387-22857-8 | pmid = | pmc = }} 1 : Single queueing nodes |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。