폴라체크-킨차인 공식

Pollaczek–Khinchine formula

큐잉 이론에서, 확률의 수학적 이론 내의 한 분야인 폴라크제크-킨차인 공식은 M/G/1 큐에 대한 큐 길이와 서비스 시간 분포 사이의 관계를 기술한다(여기서 작업은 포아송 프로세스에 따라 도착하고 일반적인 서비스 시간 분포를 가진다).이 용어는 이러한 [1]모델에서 평균 대기열 길이와 평균 대기/서비스 시간 사이의 관계를 나타내기 위해서도 사용됩니다.

이 공식은 1930년[2] 펠릭스 폴라체크에 의해 처음 발표되었고 2년 [4][5]후 알렉산드르 킨친[3] 의해 확률론적 관점에서 재연되었다.파멸 이론에서는 이 공식을 사용하여 최종 파멸 확률(보험 회사가 [6]파산할 확률)을 계산할 수 있습니다.

평균 큐 길이

공식은 시스템 L의 평균 고객 수가 다음과 같이 제공됨을[7] 나타냅니다.

어디에

  • displaystyle \ 포아송 프로세스의 도착 속도입니다.
  • 1 1 서비스 시간 분배 S의 입니다.
  • = / { display \rho = \/ \mu}는 입니다.
  • Var(S)는 서비스 시간 분포 S의 분산입니다.

평균 큐 길이를 한정하려면 < <\ 합니다.그렇지 않으면 작업은 큐에서 나가는 것보다 빨리 도착합니다.「트래픽의 강도」의 범위는 0 ~1 이며, 서버가 비지 상태인 시간의 평균 분율입니다.착신 레이트 서비스 이상일 경우 큐잉 지연은 무한이 됩니다.펠러의 역설로 인해 [8]분산항이 표현에 들어갑니다.

평균 대기시간

고객이 시스템에 머무는 평균 시간을 W로 표기하면 +μ - W=^{-입니다.서 W { W 평균 대기 시간(서비스 대기 시간)이고μ { \ 서비스 속도입니다.'리틀의 법칙'을 사용하여

어디에

  • L은 시스템의 평균 고객 수
  • displaystyle \ 포아송 프로세스의 도착 속도입니다.
  • W는 큐에서 대기시간과 서비스시간 모두 평균입니다.

그렇게

평균 대기 시간에[9] 대한 식을 다음과 같이 쓸 수 있습니다.

큐 길이 변환

[10] 내 고객 수 확률 생성 함수 ((z) 작성

여기서 g(s)는 서비스 시간 확률 밀도 [11]함수의 라플라스 변환입니다.

대기시간 변환

대기 시간 [10]분포의 Laplace-Stieltjes 변환에 대한 W를 쓴다*.

여기서 g(s)는 서비스 시간 확률 밀도 함수의 라플라스 변환입니다.n번째 모멘트는 변환을 n번 미분하고 (-1)n을 곱하고 s = 0에서 평가하여 얻을 수 있습니다.

레퍼런스

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