Анализ в переходном режиме сети с нетерпеливыми положительными и отрицательными заявками различных типов | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/7

Анализ в переходном режиме сети с нетерпеливыми положительными и отрицательными заявками различных типов

Проведено исследование в переходном режиме открытой сети, в которую поступают простейшие потоки положительных и отрицательных заявок различных типов. Обслуживания требуют только положительных заявки. Время пребывания в очереди СМО для положительных и отрицательных заявок ограничено случайными величинами, имеющими экспоненциальное распределение с параметрами, различными для каждого типа заявок. Отрицательная заявка определенного типа, время ожидания в СМО которой закончилось, уменьшает количество положительных заявок такого же типа в СМО на единицу, если такие заявки в ней есть. Для нахождения нестационарных вероятностей состояний сети предложен модифицированный метод последовательных приближений, совмещенный с методом рядов.

Analysis in the transient regime of the network with impatient positive and negative customers of multiple classes.pdf Рассмотрим открытую G-сеть массового обслуживания [1] с n однолинейными системами массового обслуживания (СМО), в которую поступают положительные и отрицательные заявки r типов. В i-ю СМО из внешней среды поступает простейший поток обычных заявок (положительных) с интенсивностью А+ и дополнительный поток отрицательных заявок, который также является простейшим, с интенсивностью , i = 1,п . Все поступающие потоки независимы. Каждая положительная заявка входного потока независимо от других заявок направляется в i-ю СМО как заявка типа c c вероятноr стью p+гс , Z Zp+ic = 1 • Длительности обслуживания положительных заявок в i-й СМО c-го типа расi=1c =1 пределены по экспоненциальному закону с параметром . В сети циркулируют не только положительные заявки, но и отрицательные [2]. Каждая отрицательная заявка входного потока независимо от других отрицательных заявок направляется в i-ю СМО nr как отрицательная заявка типа c c вероятностью p0ic, ZZ p0ic = 1 и через случайное время уничтоl=1 c=1 жает одну положительную заявку типа с. После окончания обслуживания положительной заявки типа c в i-й СМО она направляется в j-ю СМО с вероятностью p+ опять как положительная заявка типа s, п r / \ а с вероятностью p:ф - как отрицательная заявка типа s, и с вероятностью pгс0 = 1 - Z Z [p+ф + p-JS ) j=1c=1 уходит из сети, i, j = 1, п, c, s = 1, r . Каждая положительная заявка типа c, находящаяся в системе, имеет время ожидания, ограниченное экспоненциально распределенной случайной величиной (СВ) с параметром 0ic. Отрицательная заявка, находящаяся в системе, остается в очереди случайное время, имеющее экспоненциальное распределение с параметром ц,-., i = 1, п, c = 1, r. Положительная заявка типа c, время ожидания которой в очереди i истекло, мгновенно переходит в j-ю СМО и становится положительной заявкой типа s c вероятностью п r , nr q +р или отрицательной заявкой типа s c вероятностью q-cjs, а с вероятностью q.c0 = 1 - Z Z (q+s + Я-ф ) уходит из сети, i, j = 1, п, c, s = 1, r . licjs j=1c=1 Такую сеть можно применить при моделировании реальных сетей связи, в которых при передаче запроса (положительной заявки) в систему связи часто устанавливается так называемый тайм-аут, истечение которого означает, что передача запроса не укладывается в планируемый интервал времени, после чего данный запрос удаляется из очереди. Отрицательные заявки при этом могут описывать вирусы в системе, которые начинают действовать через случайное время. Под состоянием сети будем понимать вектор {к, / , t )= (k11, k12,...,k1r , k21, k22, .,k2r ,---,kn1, kn2,---,knr, l11, l12,.",l1r , l21, l22,'",l2r ,-.,ln1, ln2,-",lnr, t) , который образует цепь Маркова с непрерывным временем и счетным числом состояний, здесь кгс и lic соответственно число положительных и отрицательных заявок типа c в i-й СМО в момент времени t, i = 1, n, c = 1, r . Требуется найти вероятности состояний сети в переходном режиме. Следует отметить, что выражения для таких вероятностей состояний в стационарном режиме в форме произведения, когда под состоянием сети понимается вектор типов заявок, были найдены в работах [1-3]. При этом предполагается, что отрицательные заявки фиксированного типа воздействуют только на положительные заявки того же типа. В работе [4] рассматривалась марковская сеть со случайным временем пребывания в очередях различных типов положительных, отрицательных заявок и сигналов, причем очереди в СМО сеть отдельно формировались для этих типов заявок и сигналов. Под состоянием сети понимался вектор числа заявок; также найдено стационарное распределение вероятностей сети в форме произведения. Для нахождения вероятностей состояний G-сети в переходном (нестационарном) режиме ранее применялся приближенный метод, основанный на использовании аппарата многомерных производящих функций [5], при предположении, что СМО сети функционируют в условиях высокой нагрузки. В данной работе это предположение снято. 1. Система разностно-дифференциальных уравнений Колмогорова для вероятностей состояний сети Пусть Iic - нулевой вектор размерности n х r, за исключением компоненты с номером r(i -1)+c, которая равна единице, Iqo - n х r вектор, состоящий из нулей, P (к, Г, t) - вероятность состояния (к, /, t), u(x) - единичная функция Хевисайда. Возможны следующие переходы нашей цепи Маркова процесса в состояние (к, Г, t + At) за время At: 1) из состояния (к - Ijs, T,t), в этом случае в j-ю СМО за время At поступит положительная заявка типа s с вероятностью u (^ )At + o(At), j = 1, n, s = 1, r; 2) из состояния (к, l -1 ^, t), при этом в j-ю СМО за время At поступит отрицательная заявка типа js s с вероятностью X0icu (lic)At + o(At), j = 1, n, s = 1, r; 3) из состояния (к + I;c, l, t), в этом случае за время At положительная заявка типа с после обслуживания или по истечении времени ожидания в i-й СМО уходит из сети во внешнюю среду; суммарная вероятность таких событий равна (ц.с+ q.cq.c0)At + o (At), i = 1,n, c = 1,r; 4) из состояния (к + Iic, l + Iic,t), в данном случае в i-ю СМО после истечения времени ожидания в ней отрицательной заявки типа с она уничтожает в этой СМО положительную заявку своего типа, вероятность такого события равна ц7,At + o(At), i = 1, n, c = 1, r; 5) из состояния (к, l + Iic, t), при этом в i-й СМО время ожидания отрицательной заявки типа c в i-й СМО закончилось, и в момент времени t в ней не было положительных заявок; вероятность такого события равна (1 - u (£,с))A t + o (At), i = 1,n, c = 1,r; 6) из состояния (к + 7JC -, l, t), в данном случае время обслуживания или ожидания положительной заявки типа c в i-й СМО закончилось, и она направляется в j-ю СМО снова как положительная заявка типа 5 с вероятностью (цр+ + 9,9+)м()At + o(At), ,,j = 1,n, c,s = 1,r; 7) из состояния (k + Iic,l -,t), при этом время обслуживания или ожидания положительной заявки типа c в i-й СМО закончилось и она направляется в j-ю СМО как отрицательная заявка типа с; вероятность такого события равна (ц^Р- + 9icqicjs)м (ljS)At + o (At) , ,, j = 1, n, c, s = 1, r; 8) из состояния (k, /, t), в этом случае за промежуток времени At состояние сети не изменилось, при этом в каждую СМО не поступает ни положительные ни отрицательные заявки любого типа, в них за время At не обслужилось, ни ушло из очереди ни одной отрицательной заявки любого типа; вероят- ( n Л ность такого события равна 1 - + ^ + Z[mc + 9с + Ц-] At + o(At) ; V ,=1 J 9) из остальных состояний с вероятностью o(At) . Тогда, используя формулу полной вероятности, получаем, что нестационарные вероятности состояний рассматриваемой сети удовлетворяют следующей системе разностно-дифференциальных уравнений (РДУ): dP(k,l,t] ( п г л п г к г n r j=1 S=1 j=1 S=1 и и . . и г . . и г . . 1 С = 1 1 С = 1 , = 1 С=1 п г ,, j =1 c,s=1 п г ,, j =1 c,s=1 2. Нахождение вероятностей состояний G-сети методом последовательных приближений Систему РДУ (1) можно представить в виде: dpjA=-Л(к до, г, t)+ Z Z (kр = -Л(к)P(k, l, t)+ Z Z Ф+s (k)P(k + 4 -/js, l, t)+ ,, j=1 c, s=1 + Z £ ф^)р(г + /,С , l - /js , t)+ Z Z Ф-cjs (k,Г)р(г + /,С ,Г + I]s , t) , (2) ,, j=1 s,c=1 ,, j=1 s,c=1 где л(к) = г +X- +£x[(nfc +efc)u(kic) +n;M(/fc)]5 Z=1 C=1 = МоЛХ* + 5oA* + 0*9*0) + + )M fe)' ф,Ф- (M) = (lJS) + (\ilcp:qs + егд^, )м (/,,), Ф- * (*)== +(i ■-'«(к)) и; (i ■- 1, представимо в виде сходящегося степенного ряда Pq (к1,/, t )= £ d^^,/)tm , (9) m=0 коэффициенты которого удовлетворяют рекуррентным соотношениям (10) с учетом (11), (12), где К m > 0, (10) (11) d++im(к-I ) = u=0 л(к dq+o (к, I ) = P(h, l,0\ d +Jk, 1) = P(k, :,0)5m0 , D+Jk,1 )=% £ (кУ+~т(к + Ic -Ijs, s,c=1 (12) i,j=1 + £ £ Ф^km (к + 4, 1 - ^ £ Ф-s к 1 К»^ Ic, 1 - ^ ) . i, j=1c,s=1 i, j=1c,s=1 Доказательство. Докажем, что коэффициенты степенного ряда (9) удовлетворяют рекуррентным соотношениям (10). Подставим последовательные приближения (9) в (4). Тогда, учитывая, что - [-ла 1 У(к)t Г л(к )r„.m l! % j= m+1 xmdx = e 0 m = 0,1, 2, j! получим £dq+m(£,l)tm = е^^к,f,0)+££ £Ф+j (k)d+qm(k + Iic -Ijs,0 /=0 i, j=1_c,s=1 m=0 + £ £ ф,1 -Ijs)+ £ £ ф(к,ф;- (к+4,/Ч^) i, j=1 c,s=1 i, j=1 c,s=1 Используя обозначения (10), этот ряд можно переписать в виде: (к I - I ,l ) (к ^ , 1,0) +£Т D+qm(h , 1 ^ m=0 m=0 Поменяв местами индексы суммирования и разлагая e £ dq-Л, 1) „-Л(к m! £ u=m+1 u! л(к)' в ряд по степеням t, будем иметь °°{-Л(к t1^ D„+;(1, 1 )jtm. (13) u+1 qu Л(к m=0 u=0 £ с(к, 1 )tm=]Г[-Л(к11 j^-, 1,0)+£ m=0 Приравнивая в левой и правой части выражения (13) коэффициенты при tm, получим соотношения (10) для коэффициентов ряда (9). Для нахождения радиуса сходимости степенного ряда (9) воспользуемся формулой Коши-Адамара: /1 ^ = lim „к?) - m-рМ+X ^ ък. i) (к, 1 )i=4 m! Ш Из (10) следует, что d++1m (к,1 , m > 0. А(к ) и=0 D+u (к, 1), q > 1, и = 0, m -1, ограничено конечным значением Q (к, 1). Из ограни- Покажем, что P (к,1,0) и р+г(£,1) ченности определения следует, что r X (к J d 00- (к + 4 - 1,, l)+ c,s=1 (к,1) , 1 )■ n + D, = X i,j =1 '00 + X Xф++(1)(к)d0+0-(k + 4,1 -Ijs)+X XX(к, 1)Й0+0-(к +4,1 + Ij,) < ^0+0-(к,г). i, j^c^^ i, j=1с,,=1 Здесь Cgo (к,l*) " некоторая ограниченная величина, а все Д+-(к,Г)= 0,l = 1,2,... Поскольку Dq+--10(к,1 )=-D+-20(к,/■)= ...=^1+0-(к,Г)= ^0+0-(к,1), то из (11) следует, что р+т^(к,l")< C0+0- (к,1), q > 1. Используя метод математической индукции, покажем, что (к, 1 )|< С++Г'ш(, 1),i = 1,2,... v ш! (14) Р+Тц (к, Для m = 1 имеем: (к, 1)= X XX Ф+,(к)d+rn(к + 1с-1,,/)+ i, j =1 с,,=1 + D q-11 \ + X XX ф+с+,1)(кк+-11 (к+1с, 1-1j,)+ X X Ф j (к, ф+Гц (к+i\c, l +1 / i, j=1 c,s=1 i, j=1 c,s=1 X (к)(-А(к + 1c-1, )р(к + 1c-1,,1,0)+ D+Гю (к + 1c-1,,1))+ + XX X Ф ^(к )(-А(к+4 + 1,) р(к+4-1,,1+1, ,0)+ D+~1q (к + 1c, f-1j,))+ = X j=1 i, j=1 c,s=1 + XX XX ф-j, (к,1)(- А(к )р(к + 1c,1 +1j, ,0)+ Р+Тю (к + 1c,1 +1, ))

Ключевые слова

G-сеть, положительные и отрицательные заявки различных типов, модифицированный метод последовательных приближений, совмещенный с методом рядов, G-network, positive and negative customers of multiple classes, modified method of successive approximations, combined with the method of series

Авторы

ФИООрганизацияДополнительноE-mail
Маталыцкий Михаил АлексеевичГродненский государственный университет им. Я. Купалыпрофессор, доктор физико-математических наук, профессор кафедры стохастического анализа и эконометрического моделированияm.matalytski@gmail.com
Копать Дмитрий ЯрославовичГродненский государственный университет им. Я. Купалымагистрант факультета математики и информатикиdk80395@mail.ru
Всего: 2

Ссылки

Gelenbe E., Schassberger R. Stability of G-networks. // Probability and its Applications in Engineering and the Information Sciences. 1992. V. 6. P. 271-276.
Fourneau J., Gelenbe E. G-networks with multiple classes of negative and positive customers. // Theoretical Computer Science. 1996. V. 155. P. 141-156.
Chao X., Pinedo M. On generalized networks of queues with positive and negative arrivals // Probability in the Engineering and Informational Sciences. 1993. V. 7. P. 301-334.
Якубович О.В., Евдокимович В.Е. Сеть массового обслуживания со случайным временем пребывания различных типов положительных, отрицательных заявок и сигналов // Проблемы физики, математики и техники. 2010. № 4. С. 63-67.
Маталыцкий М.А., Науменко В.В. Стохастические сети с нестандартными перемещениями заявок. Гродно : Гродненский гос. ун-т, 2017. 347 с.
Валеев К.Г., Жаутыков О.А. Бесконечные системы дифференциальных уравнений. Алма-Ата : Наука, 1974. 415 с.
Коробейник Ю.Ф. Исследование дифференциальных уравнений бесконечного порядка с полиномиальными коэффициен тами с помощью операторных уравнений интегрального типа // Математический сборник. 1959. Т. 49, № 2. С. 191-206.
Коробейник Ю.Ф. Дифференциальные уравнения бесконечного порядка и бесконечные системы дифференциальных урав нений // Известия АН СССР. Сер. математическая. 1970. Т. 34, № 4. С. 881-922.
 Анализ в переходном режиме сети с нетерпеливыми положительными и отрицательными заявками различных типов | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/7

Анализ в переходном режиме сети с нетерпеливыми положительными и отрицательными заявками различных типов | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2018. № 42. DOI: 10.17223/19988605/42/7