M/G/k 큐

M/G/k queue

큐잉 이론에서 M/G/k 큐는 확률의 수학적 이론에서 도착이 마르코프(포아송 프로세스에 의해 변조됨)이고 서비스 시간은 일반 분포를 가지며 k개의 서버가 있는 큐 모델입니다.모델명은 Kendall 표기법으로 작성되며 서비스 시간이 기하급수적으로 분산되어야 하는 M/M/c 큐와 단일 서버가 있는 M/G/1 큐의 확장입니다.이 큐잉 시스템의 대부분의 퍼포먼스메트릭은 아직 미해결 상태로 [1]남아 있습니다.

모델 정의

M/G/k 큐로 표현되는 큐는 상태공간이 설정된 {0,1,2,3...}인 확률적 프로세스이며, 여기서 값은 서비스되는 큐의 고객 수에 대응한다.상태 i에서 상태 i + 1로의 이행은 신규 고객의 도착을 나타냅니다.이러한 도착 사이의 시간은 모수 θ로 지수 분포를 가집니다.상태 i에서 상태 i - 1로의 이행은 서비스 제공이 막 끝난 고객의 출발을 나타냅니다.즉, 개별 고객에 대한 서비스 제공에 필요한 시간은 일반적인 분배 기능을 가집니다.도착과 서비스 기간 사이의 시간은 통계적으로 독립적이라고 가정되는 무작위 변수이다.

정상 상태 분포

Tijms 등은 "M/G/[2]k 대기열에서 정상 상태 확률의 정확한 수치 값을 계산하기 위해 계산적으로 다루기 쉬운 방법을 개발할 수 있을 것 같지 않다"고 믿는다.

평균 큐 크기,[3] 정지 분포[4][5] 및 반사된 브라운 운동에[6][7] 의한 근사치에 대한 다양한 근사치가 다른 저자들에 의해 제시되었다.최근 Hamzeh Khazaei 외 [8][9]연구진은 정상 상태 확률에 대한 라플라스 변환을 기반으로 하는 새로운 근사 접근법을 제안했다.이 새로운 어프로치는, 다수의 서버가 있는 경우나, 서비스 시간의 분포에 복수의 변동 계수가 있는 경우에서도, 아직 충분히 정확합니다.

평균 지연/대기 시간

작업의 [5][7][10][11][12][13]평균 지연에 대해서는 여러 가지 근사치가 있습니다.1959년 M/M/C[14][15] 큐의 평균 대기시간을 조정하는 계수를 사용하여 처음 제시되었습니다.이 결과는 킹맨의 [16]혼잡의 법칙이라고도 합니다.

여기서 C는 서비스 시간 분포의 변동 계수입니다.Ward Whitt는 이 근사치를 "서비스 시간 [17]분포에 대한 추가 정보를 제공하더라도 대개 훌륭한 근사치"라고 설명했다.

그러나 모든 [14]경우 처음 두 모멘트만 사용하는 근사치가 정확할 수는 없는 것으로 알려져 있습니다.

마르코프-크레인 특성은 평균 대기 [18]시간에 엄격한 경계를 생성하는 것으로 나타났다.

출발 간격

대기열에 n명의 고객이 있을 때 출발 간격은 n이 무한대 경향이 있기 때문에 직관적인 1/μ [19]결과와 다른 평균을 갖는 것으로 추측된다.

2대의 서버

M/G/2 큐(서버가 2개인 모델)에서는 서비스 시간 분포가 지수 [21]분포의 혼합일 때 분포의 적분[20] 방정식 또는 라플라스 변환을 푸는 것으로 한계 확률을 결정하는 문제를 줄일 수 있습니다.대기시간[22] 분포에 합리적인 Laplace 변환이 있는 경우 큐 길이 및 대기시간[23] 분포의 Laplace 변환을 계산할 수 있습니다.

레퍼런스

  1. ^ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems. 63 (1–4): 3–4. doi:10.1007/s11134-009-9147-4. S2CID 38588726.
  2. ^ Tijms, H. C.; Van Hoorn, M. H.; Federgruen, A. (1981). "Approximations for the Steady-State Probabilities in the M/G/c Queue". Advances in Applied Probability. 13 (1): 186–206. doi:10.2307/1426474. JSTOR 1426474.
  3. ^ Ma, B. N. W.; Mark, J. W. (1995). "Approximation of the Mean Queue Length of an M/G/c Queueing System". Operations Research. 43 (1): 158–165. doi:10.1287/opre.43.1.158. JSTOR 171768.
  4. ^ Breuer, L. (2008). "Continuity of the M/G/c queue". Queueing Systems. 58 (4): 321–331. doi:10.1007/s11134-008-9073-x. S2CID 2345317.
  5. ^ a b Hokstad, Per (1978). "Approximations for the M/G/m Queue". Operations Research. INFORMS. 26 (3): 510–523. doi:10.1287/opre.26.3.510. JSTOR 169760.
  6. ^ Kimura, T. (1983). "Diffusion Approximation for an M/G/m Queue". Operations Research. 31 (2): 304–321. doi:10.1287/opre.31.2.304. JSTOR 170802.
  7. ^ a b Yao, D. D. (1985). "Refining the Diffusion Approximation for the M/G/m Queue". Operations Research. 33 (6): 1266–1277. doi:10.1287/opre.33.6.1266. JSTOR 170637.
  8. ^ Khazaei, H.; Misic, J.; Misic, V. B. (2012). "Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems". IEEE Transactions on Parallel and Distributed Systems. 23 (5): 936. doi:10.1109/TPDS.2011.199. S2CID 16934438.
  9. ^ Khazaei, H.; Misic, J.; Misic, V. B. (2011). "Modelling of Cloud Computing Centers Using M/G/m Queues". 2011 31st International Conference on Distributed Computing Systems Workshops. p. 87. doi:10.1109/ICDCSW.2011.13. ISBN 978-1-4577-0384-3. S2CID 16067523.
  10. ^ Hokstad, Per (1980). "The Steady-State Solution of the M/K2/m Queue". Advances in Applied Probability. Applied Probability Trust. 12 (3): 799–823. doi:10.2307/1426432. JSTOR 1426432.
  11. ^ Köllerström, Julian (1974). "Heavy Traffic Theory for Queues with Several Servers. I". Journal of Applied Probability. Applied Probability Trust. 11 (3): 544–552. doi:10.1017/s0021900200096327. JSTOR 3212698.
  12. ^ Nozaki, S. A.; Ross, S. M. (1978). "Approximations in Finite-Capacity Multi-Server Queues with Poisson Arrivals". Journal of Applied Probability. 15 (4): 826–834. doi:10.2307/3213437. JSTOR 3213437.
  13. ^ Boxma, O. J.; Cohen, J. W.; Huffels, N. (1979). "Approximations of the Mean Waiting Time in an M/G/s Queueing System". Operations Research. INFORMS. 27 (6): 1115–1127. doi:10.1287/opre.27.6.1115. JSTOR 172087.
  14. ^ a b Gupta, V.; Harchol-Balter, M.; Dai, J. G.; Zwart, B. (2009). "On the inapproximability of M/G/K: Why two moments of job size distribution are not enough". Queueing Systems. 64: 5–48. doi:10.1007/s11134-009-9133-x. S2CID 16755599.
  15. ^ Lee, A. M.; Longton, P. A. (1959). "Queueing Processes Associated with Airline Passenger Check-in". Journal of the Operational Research Society. 10: 56–71. doi:10.1057/jors.1959.5.
  16. ^ Gans, N.; Koole, G.; Mandelbaum, A. (2003). "Telephone Call Centers: Tutorial, Review, and Research Prospects" (PDF). Manufacturing & Service Operations Management. 5 (2): 79. doi:10.1287/msom.5.2.79.16071.
  17. ^ 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.
  18. ^ Gupta, V.; Osogami, T. (2011). "On Markov–Krein characterization of the mean waiting time in M/G/K and other queueing systems". Queueing Systems. 68 (3–4): 339. doi:10.1007/s11134-011-9248-8. S2CID 35061112.
  19. ^ Veeger, C.; Kerner, Y.; Etman, P.; Adan, I. (2011). "Conditional inter-departure times from the M/G/s queue". Queueing Systems. 68 (3–4): 353. doi:10.1007/s11134-011-9240-3. S2CID 19382087.
  20. ^ Knessl, C.; Matkowsky, B. J.; Schuss, Z.; Tier, C. (1990). "An Integral Equation Approach to the M/G/2 Queue". Operations Research. 38 (3): 506. doi:10.1287/opre.38.3.506. JSTOR 171363.
  21. ^ Cohen, J. W. (1982). "On the M/G/2 queueing model". Stochastic Processes and Their Applications. 12 (3): 231–248. doi:10.1016/0304-4149(82)90046-1.
  22. ^ Hokstad, Per (1979). "On the Steady-State Solution of the M/G/2 Queue". Advances in Applied Probability. Applied Probability Trust. 11 (1): 240–255. doi:10.2307/1426776. JSTOR 1426776.
  23. ^ Boxma, O. J.; Deng, Q.; Zwart, A. P. (2002). "Waiting-Time Asymptotics for the M/G/2 Queue with Heterogeneous Servers". Queueing Systems. 40: 5–31. doi:10.1023/A:1017913826973. S2CID 2513624.