G/G/1 큐

G/G/1 queue

큐잉 이론에서 G/G/1 큐는 확률의 수학적 이론에서 도착간 시간이 일반(임의) 분포를 가지며 서비스 시간이 일반([1]다른) 분포를 갖는 단일 서버를 가진 시스템에서 큐 길이를 나타냅니다.큐의 진화는 린들리 [2]방정식으로 설명할 수 있습니다.

시스템은 Kendall 표기법으로 기술되어 있습니다.여기서 G는 도착간 시간 및 서비스 시간 모두에 대한 일반 분포를 나타내고 1은 모델이 [3][4]단일 서버를 가지고 있음을 나타냅니다.다른 도착간 및 서비스 시간은 독립적인 것으로 간주되며, 이를 강조하기 위해 모델이 GI/GI/1로 표시될 수 있습니다.

대기시간

Kingman 공식은 G/G/1 [5]큐의 평균 대기 시간에 대한 근사치를 제공합니다.린들리의 적분 방정식은 Wiener-를 사용하여 해결할 수 있는 고정 대기 시간 분포에 의해 충족되는 관계이다.Hopf [6]메서드

다중 서버

일반적인 G/G/k 모델은 알려진 메트릭이 거의 없는 M/G/k 큐를 일반화하므로 결과는 거의 알려져 있지 않다.평균값 분석 기법을 사용하여 M/M/c 대기열 모델의 결과를 조정하고, 과도한 트래픽 근사치, 경험적[7]: 189 [8] 결과 또는 위상 유형 분포별 근사 분포를 사용한 다음, 행렬 분석 방법을 사용하여 근사 시스템을 [7]: 201 해결할 수 있습니다.

헤비테일 작업 사이즈를 가진 G/G/2 큐에서 지연시간 분포의 꼬리는 저부하 하에서 제곱되는 지수 분포의 꼬리처럼, [9][10][11]고부하에서는 지수 분포의 꼬리처럼 동작하는 것으로 알려져 있다.

레퍼런스

  1. ^ Bhat, U. N. (2008). "The General Queue G/G/1 and Approximations". An Introduction to Queueing Theory. pp. 169–183. doi:10.1007/978-0-8176-4725-4_9. ISBN 978-0-8176-4724-7.
  2. ^ Foss, S. (2011). "The G/G/1 Queue". Wiley Encyclopedia of Operations Research and Management Science. doi:10.1002/9780470400531.eorms0878. ISBN 9780470400531.
  3. ^ Kendall, D. G. (1953). "Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain". The Annals of Mathematical Statistics. 24 (3): 338. doi:10.1214/aoms/1177728975. JSTOR 2236285.
  4. ^ Smith, W. L. (1953). "On the distribution of queueing times". Mathematical Proceedings of the Cambridge Philosophical Society. 49 (3): 449. Bibcode:1953PCPS...49..449S. doi:10.1017/S0305004100028620.
  5. ^ Kingman, J. F. C.; Atiyah (October 1961). "The single server queue in heavy traffic". Mathematical Proceedings of the Cambridge Philosophical Society. 57 (4): 902. Bibcode:1961PCPS...57..902K. doi:10.1017/S0305004100036094. JSTOR 2984229.
  6. ^ Prabhu, N. U. (1974). "Wiener-Hopf Techniques in Queueing Theory". Mathematical Methods in Queueing Theory. Lecture Notes in Economics and Mathematical Systems. Vol. 98. pp. 81–90. doi:10.1007/978-3-642-80838-8_5. ISBN 978-3-540-06763-4.
  7. ^ a b Gautam, Natarajan (2012). Analysis of Queues: Methods and Applications. CRC Press. ISBN 9781439806586.
  8. ^ Whitt, W. (2009). "Approximations for the GI/G/m Queue" (PDF). Production and Operations Management. 2 (2): 114–161. doi:10.1111/j.1937-5956.1993.tb00094.x.
  9. ^ Harchol-Balter, M. (2012). "Task Assignment Policies for Server Farms". Performance Modeling and Design of Computer Systems. p. 408. doi:10.1017/CBO9781139226424.031. ISBN 9781139226424.
  10. ^ Whitt, W. (2000). "The impact of a heavy-tailed service-time distribution upon the M/GI/s waiting-time distribution" (PDF). Queueing Systems. 36: 71–87. doi:10.1023/A:1019143505968.
  11. ^ Foss, S.; Korshunov, D. (2006). "Heavy Tails in Multi-Server Queue". Queueing Systems. 52: 31. arXiv:1303.4705. doi:10.1007/s11134-006-3613-z.