Cua G/G/1

En la teoria de cues, una disciplina dins la teoria matemàtica de la probabilitat, la cua G/G/1 representa la longitud de la cua en un sistema amb un únic servidor on els temps d'interarribada tenen una distribució general (és a dir, arbitrària) i els temps de servei tenen una distribució general (diferent).[1] L'evolució de la cua es pot descriure mitjançant l'equació de Lindley.[2]

El sistema es descriu en la notació de Kendall, on la G denota una distribució general tant per als temps d'interarribada com per als temps de servei, i l'1 que el model té un únic servidor.[3][4] Els diferents temps d'arribada i servei es consideren independents, i de vegades el model es denota GI/GI/1 per emfatitzar-ho. La solució numèrica per al GI/G/1 es pot obtenir discretitzant el temps.[5]

Temps d'espera

La fórmula de Kingman dóna una aproximació del temps mitjà d'espera en una cua G/G/1.[6] L'equació integral de Lindley és una relació satisfeta per la distribució estacionària del temps d'espera que es pot resoldre utilitzant el mètode de Wiener–Hopf.[7]

Múltiples servidors

Es coneixen pocs resultats per al model general G/G/k, ja que generalitza la cua M/G/k per a la qual es coneixen poques mètriques. Els límits es poden calcular mitjançant tècniques d'anàlisi de valor mitjà, adaptant els resultats del model de cua M/M/c, utilitzant aproximacions de trànsit pesat, resultats empírics[8]:189:[9] o aproximant distribucions per distribucions de tipus de fase i després utilitzant mètodes analítics matricials per resoldre els sistemes aproximats. [8]: 201

En una cua G/G/2 amb tasques de cua pesada, se sap que la cua de la distribució de temps de retard es comporta com la cua d'una distribució exponencial al quadrat sota càrregues baixes i com la cua d'una distribució exponencial per a càrregues altes.[10][11][12]

Referències

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