The regularities of queues in models with infinite waiting room

E. A. Danielyan ; A. A. Danielyan ; I. E. Danielyan

Proceedings of the Yerevan State University. Physical and mathematical sciences, no. 2 (2006), pp. 3-23.

Résumé

In the present paper the developments of Queueing Theory is described, its belongness to Operations Research and Probability Theory is substantiated. The Regularities of Many Servers Queues with infinite waiting room are explained on the example of $GI|G|s|\infty$ model. The explicit formulas, limit theorems in fixed and heavy traffic conditions, stability, inequalities for the main characteristics, extremal problems are presented. The main attention in future is given to $GI|G|1|\infty$ model with FIFO service discipline. Not only known results are formulated but also some results, which were established by authors. For instance, in $GI | G|1|\infty$ model two groups of assumptions are suggested, which lead to the Little formulas. In particular, $M | G|1|\infty$ model is considered.

Bibliographie

[1] Kleinrok L., Vychislitelnye sistemy s ocheredyami, Mir, M., 1979

[2] Benesh V.E., Matematicheskie osnovy teorii telefonnykh soobschenii, Svyaz, M., 1968

[3] Livshits B.S., Fidlin Ya.V., Kharkevich A.D., Teoriya telefonnykh i telegrafnykh soobschenii, Svyaz, M., 1971

[4] Shtermer X., Belendorf E. i dr., Teoriya teletrafika, Svyaz, M., 1971

[5] Akof R., Sasieni M., Osnovy issledovaniya operatsii, Mir, M., 1971 | MR

[6] Zaichenko Yu.P., Issledovanie operatsii, Vischa shkola, Kiev, 1975

[7] Konvei R.V., Maksvell V.L., Miller L.V., Teoriya raspisanii, Nauka, M., 1975 | MR

[8] Taneev V.S., Gordon V.S., Shafranskii Ya.M., Teoriya raspisanii. Odnostadiinye sistemy, Nauka, M., 1984 | MR

[9] Tarakanov K.V., Ovcharov L.A., Tyryshkin A.N., Analiticheskie metody issledovaniya operatsii, Sov. radio, M., 1974

[10] Novikov O.A., Petukhov S.I., Prikladnye voprosy teorii massovogo obsluzhivaniya, Sov. Radio, M., 1969

[11] Saati T.L., Elementy teorii massovogo obsluzhivaniya i ee prilozheniya, Sov. radio, M., 1965 | MR

[12] Kofman A., Kryuon R., Massovoe obsluzhivanie. Teoriya i prilozheniya, Mir, M., 1966

[13] Gnedenko B.V., Kovalenko I.N., Vvedenie v teoriyu massovogo obsluzhivaniya, Nauka, M., 1987 | MR

[14] Klimov G.P., Stokhasticheskie sistemy obsluzhivaniya, Nauka, M., 1966 | MR

[15] Borovkov A.A., Veroyatnostnye protsessy v teorii massovogo obsluzhivaniya, Nauka, M., 1972 | MR

[16] Gnedenko B.V., Danielyan E.A. i dr., Prioritetnye sistemy obsluzhivaniya, MGU, M., 1973

[17] Ivchenko G.I., Kashtanov V.A., Kovalenko I.N., Teoriya massovogo obsluzhivaniya, Vysshaya shkola, M., 1982

[18] Matveev V.F., Ushakov V.G., Sistemy massovogo obsluzhivaniya, MGU, M., 1973 | MR

[19] Takach L., Kombinatornye metody v teorii sluchainykh protsessov, Mir, M., 1971 | MR

[20] Cohen J.W., On Regenerative Processes in Queueing Theory, v. 121, Lecture Notes in Econ. and Math. Systems, Springer-Verlag, 1976 | MR | Zbl

[21] Prabhu N.U., Stochastic Storage Processes: Queues, Insurance Risk and Dams, v. 15, Appl. of Math., Springer-Verlag, 1980 | MR | Zbl

[22] Kiefer J., Wolfowitz J., “On the theory of queues with many servers”, Trans. Amer. Math. Soc., 78 (1955), 1–18 | DOI | MR | Zbl

[23] Whitt W., “Existence of limiting distributions in the $GI/G/s$ queue”, Math. Operat. Res., 7 (1982), 88–94 | DOI | MR | Zbl

[24] Pollaczek F., Theorie Analytique des Problemes Stochastiques Relatifs a un Groupe de Lignes Telephoniques avec Dispositifd’Attente, Paris, Gauthier-Villars

[25] De Smlt J.H.A., Many Server Queueing Systems, Doctoral Thesis, Technische Hogeschool, Delft, 1971 | MR

[26] De Smlt J.H.A., J. Appl. Prob., 5 (1973), 153–169 | DOI | MR

[27] Kingman J.F.C., J. Appl. Prob., 3:2 (1966), 285–326 | DOI | MR | Zbl

[28] Whitt W., J. Appl. Prob., 9 (1972), 650–658 | DOI | MR | Zbl

[29] Minh Do Le, Manag. Science, 33:9 (1987), 1192–1199 | DOI | Zbl

[30] Stidham S., Opns. Res., 20 (1978), 1106–1114

[31] Stidham S., “$L = \lambda W$: A Discounted Analogue and a New Proof”, Opns. Res., 20 (1972), 1115–1126 | DOI | MR | Zbl

[32] Danielyan E.A., Simonyan E.A., Proceedings of the YSU, 2003, no. 3, 25–29

[33] Simonyan E.A., Modelirovanie, optimizatsiya, upravlenie, 6:2 (2003), 16–21

[34] Koks D., Smit V., Teoriya vosstanovleniya, Sov. radio, M., 1967 | MR

[35] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 1, Mir, M., 1967 | MR

[36] De Smit J.H.A., J. Appl. Prob., 22 (1985), 214–222 | DOI | MR | Zbl

[37] Ushakov V.G., Analiticheskie metody issledovaniya prioritetnykh sistem obsluzhivaniya, Avtoref. dis. na soiskanie uch. stepeni dok. fiz.-mat. nauk, MGU, M., 1995

[38] Marchal W.G., Harris S.M., “A modified erlang approach to approximating $GI/G/1$ queues”, J. Appl. Prob., 13:1 (1976), 118–126 | DOI | MR | Zbl

[39] Teunis J.O., Adv. Appl. Prob., 19 (1987), 240–265 | DOI | MR | Zbl

[40] Kovalenko I.N., Filipova A.A., Teoriya veroyatnostei i matematicheskaya statistika, Vischa shkola, Kiev, 1973

[41] Koen Dzh., Boksma O., Granichnye zadachi v teorii massovogo obsluzhivaniya, Mir, M., 1987 | MR

[42] Hokstad R., “Approximations for the $M/G/m$ Queue”, Opns. Res., 26 r. 510-523 (1978) | DOI | MR | Zbl

[43] Cohen J.W., “On the $M/G/2$ queeing model”, Stoch. Proc. Appl., 12 (1982), 231–248 | DOI | MR | Zbl

[44] Cohen J.W., “On the Analysis of Two-Dimensional Queueing Models”, Messung Modellierung und Bewertung von Rechner Systeme, eds. K. Shulz and K.M. Shulz, Springer-Verlag, Berlin, 1983, 107–121 | DOI

[45] Cohen J.W., “On the Analysis of Two-Dimensional Queueing Problems”, Math. Computer Perform and Reliability, eds. G. lazeolla, P.-J. Courtois and A. Hordijk, North- Holland Publ. Co., Amsterdam, 1984, 17–32 | MR

[46] Tijms H.C., Van Hoorn M.H., Federgruen A., Adv. Appl. Prob., 13 (1981), 186–206 | DOI | MR | Zbl

[47] Van Hoorn M.H., Tijms H.C., “Approximations for the waiting time distribution of the $M/G/c$ queue”, Performance Analysis, 2 (1982), 22–28 | Zbl

[48] Van Hoorn M.H., Algorithms and Approximations for Queueing Systems, Math. Centre Tract Math. Centre, Amsterdam, 1983 | MR

[49] Borovkov A.A., Asimptoticheskie metody v teorii massovogo obsluzhivaniya, Nauka, M., 1980 | MR

[50] Knessl S., Matkowsky B.J., Schuss Z., Tier S., J. Appl. Math., 47:2 (1987), 367–397 | MR | Zbl

[51] Hokstad P., Adv. Appl. Prob., 11 (1979), 210–255 | DOI | MR

[52] Dietrich S., “Approximations for $M/G/s$ queues”, Mathematische Operationsforschung und Statistik, 7 (1976), 587–594 | DOI | MR | Zbl

[53] Knessl C., Matkowsky B.J., Schuss Z., Tier C., “An Integral Equation Approach to the $M|G|2$ Queue”, Appl. Math. Techn. Report, 1985, no. 8422., Northwestern University

[54] Gnedenko D.B., Solovev A.D., Izv. AN SSSR Tekhn. kibern., 1974, no. 6, 113–118 | Zbl

[55] Solovev A.D., Izv. AN SSSR. Tekhn. kibern., 1971, no. 6, 79–90

[56] Danielyan E.A., Geokchyan A.A., Izv. AN SSSR. Tekhn. kibern., 1976, no. 6, 121–131 | Zbl

[57] Popov G.A., “Utochnenie odnoi predelnoi teoremy A.D. Soloveva i D. B. Gnedenko”, Proceedings of the YSU, 1980, no. 2, 133–135 | Zbl

[58] Danielyan E.A., Popov G.A., “Ob odnoi predelnoi teoreme dlya prioritetnykh sistem pri edinichnoi zagruzke”, DAN Arm. SSR, 20:1 (1980), 11–I5

[59] Danielyan E.A., Proceedings of the YSU, 1987, no. 2, 9–16 | Zbl

[60] Danielian E.A., Liese F., Rostock Math. Kolloq., 32 (1987), 67–86

[61] Hooke T.A., Rep. of Opns. Res., 1969, no. 91, Cornell Univ., TR.

[62] Kingman J. F.C., “The single server queue in heavy traffic”, Proc. Camb. Phil. Soc., 57 (1961), 902–904 | DOI | MR | Zbl

[63] Kingman J.F.C., “On queues in heavy traffic”, J. R. Stat. Soc. Ser. B, 1962, no. 24, 383–392 | MR | Zbl

[64] Kingman J.F.C., “The heavy traffic approximation in the theory of queues”, Proceedings of the Symposium on Congestion Theory (University of North Carolina, 1964), eds. Smith Walter L. and Wilkinson William E., Chapel Hill, NC, 1965, 137–169 | MR | Zbl

[65] Prabhu N.U., “Limit theorems for the single server queue with traffic intensity one”, J. Appl. Prob., 7 (1970), 227–233 | DOI | MR | Zbl

[66] Kollerstrom J., “Heavy traffic theory for queues with several servers. I”, J. Appl. Prob., 11 (1974), 544–552 | DOI | MR | Zbl

[67] Prokhorov Yu.V., “Transition phenomena in queueing processes. I”, Litov. mat. sb., 3:1 (1963), 199–206 | MR

[68] Whitt W., Weak Convergence Theorems for Queues in Heavy Traffic, Ph.D. Thesis., Cornel Univ. (Technical Report 2 Dept of Oper. Res. Stanford Univ.), 1968 | MR

[69] A. A. Borovkov, “Nekotorye predelnye teoremy teorii massovogo obsluzhivaniya. II (mnogokanalnye sistemy)”, Teoriya veroyatn. i ee primen., 10:3, 409–436 | MR | Zbl

[70] Theory Probab. Appl., 10:1, 63–73 | DOI | MR | MR | Zbl

[71] Iglehart D.L., Add. Appl. Prob., 5 (1973), 570–594 | DOI | Zbl

[72] Iglehart D.L., Add. Appl. Prob., 2 (1970), 150–177 | DOI | MR | Zbl

[73] Iglchart D.L., Whitt W., Add. Appl. Prob., 2 (1970), 355–369 | DOI

[74] Iglehart D.L., Kennedy D.P., J. Appl. Prob., 7 (1970), 747–753 | DOI | MR | Zbl

[75] Whitt W., J. Appl. Prob., 7 (1970), 370–375 | DOI

[76] Whitt W., J. Appl. Prob., 8 (1971), 74–94 | DOI | MR | Zbl

[77] Whitt W., J. Appl. Prob., 9 (1972), 185–191 | DOI | MR | Zbl

[78] Billingsli P., Skhodimost veroyatnostnykh mer, Nauka, M., 1977 | MR

[79] Demidovich B.P., Lektsii po matematicheskoi teorii ustoichivosti, Nauka, M., 1967 | MR

[80] Kalashnikov V.V., Izv. AN SSSR. Tekhn. kibern., 1974, no. 4, 43–53 | Zbl

[81] Kalashnikov V.V., Izv. AN SSSR. Tekhn. kibern., 1975, no. 3, 103–108 | Zbl

[82] Kalashnikov V.V., Izv. AN SSSR. Tekhn. kibern., 1977, no. 3, 87–96 | Zbl

[83] Kalashnikov V.V., TVP, 22:1 (1977), 89–105 | MR | Zbl

[84] Kalashnikov V.V., Tsitsiashvili G.Sh., Izv. AN SSSR Tekhn. kibern., 1972, no. 2, 41 –49

[85] Kalashnikov V.V., Kachestvennyi analiz povedeniya slozhnykh sistem metodom probnykh funktsii, M. Nauka, 1978 | MR

[86] Tsitsiashvili G.Sh., TVP, 20:2 (1975), 345–358 | MR | Zbl

[87] Zolotarev V.M., TVP, 20:1 (1975), 215–217

[88] Zolotarev V.M., TVP, 20:#4. (1975), 834–847 | MR | Zbl

[89] Zolotarev V.M., TVP, 21:#2. (1976), 260–279 | MR | Zbl

[90] Franken R., Operations forschung und Math. Stat., S11 (1970), 1–23

[91] Petrov B.B., Predelnye teoremy dlya summ nezavisimykh sluchainykh velichin, Nauka, M., 1987 | MR

[92] Nagaev S.V., TVP, 15:# 1 ss. 179-199. 419-441. (1970)

[93] Xing Jin., J. Appl. Prob., 25 r. 596–611 (1988) | MR | Zbl

[94] Xing Jin, Wang Rongxlng, “On Berry-Esseen rate for queue length of the $GI/G/K$ system in heavy traffic”, Acta Math. Sinica, 29 (1986), 651–657 | MR | Zbl

[95] Cohen J.W., The Single Server Queue, Amsterdam: North Holland, 1969 | MR

[96] Danielyan E.A., Simonyan A.P., Vvedenie v teoriyu ocheredei, Izd-vo PAU, Er., 2006

[97] Grigoryan G.S., Danielyan A.A., Matem. v vyssh. Shkole, 2005, no. # 4., Izd-vo GIUA, Er. | MR

[98] Thorisson N., “The queue $GI/G/1$: Finite moments of the cycle variables and uniform rates of convergence”, Stochastic Processes and their Applications, 19 (1985), 85–99 | DOI | MR | Zbl

[99] Spltzer F., “A combinatorial lemma and its application to probability theory”, Trans. Amer. Math. Soc., 82 (1956), 323–339 | DOI | MR

[100] Harrison J.M., Lemoine A.J., “On the virtual and actual waiting time distributions of a $GI/G/1$ queue”, J. Appl. Prob., 13:4 (1970), 833–836 | DOI | MR

[101] Lemoine A.J., “On two stationary distributions for the stable GI/G/1 queue”, J. Appl. Prob., 11:4 (1974), 849–852 | DOI | MR | Zbl

[102] Bronshtein O.I., Dukhovnyi I.M., Modeli prioritetnogo obsluzhivaniya v informatsionno-vychislitelnykh sistemakh, M. Nauka, 1976 | MR

[103] Krakowski M., “Conservation methods in queuing theory”, Rev. Française Automat. Informat. Recherche Opérationnelle, ser V-1, 7 (1973), 63–83 | MR | Zbl

[104] Borovkov A.A., Teoriya veroyatnostei, Nauka, M., 1986 | MR

[105] Iglehart D.L., Ann. Math. Stat., 43:2 (1972), 627–635 | DOI | MR | Zbl

[106] Danielyan E.A., Khachikyan Kh.Z., “Tendentsii v izuchenii modeli $Mr|Gr|1|\infty$ teorii ocheredei”, Uchenye zapiski EGU, 2001, no. # 1., 4–22

[107] Danielyan A.A., “Ekstremalnoe svoistvo vremen ozhidaniya modeli $GI|G|1|\infty$”, Proceedings of the YSU, 2005, no. 3, 47–52 | Zbl

[108] Danielyan A.A., Vestnik RAU, 2005, no. 1, 23–31

[109] Karlin S., Stadden V., Chebysheveskie sistemy i ikh priminenie v analize i statistike, Nauka, M., 1976 | MR

[110] Krein M.G., Nudelman A.A., Problema momentov Markova i ekstremalnye zadachi, Nauka, M., 1973 | MR

[111] Danielian E.A., Optimization of Functionals on Classes of Distributions with Moments' Constraints, Part I, Series 16, TICSP, Tampere, Finland

[112] Danielian E.A., Optimization of Functionals on Classes of Distributions with Moments' Constraints, Part 2, Series 18, TICSP, 2003

[113] Danielyan I.E., Izv. HAH Armenii. Matematika, 37:# 3. (2002), 21–36 | MR | Zbl

[114] Shtoiyan D., Kachestvennye svoistva i otsenki statisticheskikh modelei, Mir, M., 1979

[115] Iglehart D.L., Adv. Arr. Prob., 3:2 (1971), 269–281 | DOI | Zbl

[116] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 2, Mir, M., 1984 | MR

[117] Blomqvist N.A., Scand. J. Statist., 1:1 (1974), 39–40 | MR | Zbl

[118] Danielyan E.A., Izv. AN Arm. SSR. Matematika, 10:3 (1975), 272–287 | MR | Zbl

[119] Ugarid M., Modeli tipa $M | G | 1| \infty$ pri kriticheskoi zagruzke, Avtoref. dis. nasoiskanie uch. stepeni kand. fiz.-mat. Nauk, Er., 1990

[120] Chitchyan R.N., Predelnye teoremy v prioritetnykh modelyakh $M_r|G_r |l|\infty$ v usloviyakh kriticheskoi zagruzki:, Avtoref. diss. na soiskanie uch. stepeni kand. fiz.-mat. nauk., Vilnyus, 1982

[121] Azlarov T.A., Husseinov J.M., Some Limit Theorems for a Queueing System with Absolute Priority in Heavy Traffic, Springer-Verlag, 1976 | MR