Analysis of customers flows in the infinite-server queueing tandem with feedback.pdf В теории массового обслуживания решение значительного числа задач проводится в предположении, что входящий поток заявок является стационарным и имеет распределение Пуассона. В большинстве случаев это предположение подтверждается статистическим анализом реальных потоков [1]. Также пуассоновские процессы могут быть использованы для аппроксимации процессов в случае наблюдения достаточно большого числа независимых потоков [2-6]. Большинство задач теории массового обслуживания для моделей с простейшим входящим потоком и экспоненциальным распределением времени обслуживания были решены еще в ХХ в. В 1956 г. Б.А. Севастьянов решил задачу Эрланга для систем с произвольной функцией распределения времени обслуживания М/G/N [7, 8] и показал, что, что при N ^ да распределение числа занятых приборов сходится к пуассоновскому. В 1969 г. Л. Такач [9] показал, что количество клиентов в системе M/G/да имеет распределение Пуассона в стационарном режиме, которое зависит от средней скорости поступления заявок и среднего времени обслуживания вызовов. В работах [10, 11] доказано, что число занятых приборов в системе М/М/да имеет распределение Пуассона. В работе [12] проведено исследование суммарного потока заявок в системе М/М/да с повторным обслуживанием. Исследование процессов числа заявок в многофазных системах и сетях массового обслуживания с рекуррентным обслуживанием представлено в работах [13-15]. Однако исследованию потоков в системах массового обслуживания (СМО) с неограниченным числом обслуживающих приборов с произвольным временем обслуживания, а также многофазных СМО с возможностью повторного обращения заявки в систему посвящено не так уж много работ. В [16] проведено исследование суммарного потока заявок в однофазной системе с входящим MMPP-потоком и повторными обращениями. В работе [17] для исследования системы M/GI/да предложен метод предельной декомпозиции. В работе [18] методом предельной декомпозиции исследованы суммарный и двумерный потоки обращений к системе M/GI/да. В работах [19-21] исследованы потоки обращений в двухфазных СМО с неограниченным числом приборов на каждой фазе и повторными обращениями. В настоящей работе предлагается метод предельной декомпозиции для анализа различных потоков в двухфазной СМО с неограниченным числом обслуживающих приборов и возможностью повторного обращения заявки к любой фазе системы. 1. Математическая модель Рассмотрим двухфазную систему массового обслуживания с неограниченным числом обслуживающих устройств на каждой фазе (рис. 1). На вход системы поступает простейший поток заявок с параметром X. Время обслуживания заявок на первой фазе независимо и имеет одинаковое распределение для каждого прибора с произвольной функцией распределения B1(x). По завершении обслуживания на первой фазе заявка с вероятностью Гц может обратиться к первой фазе для повторного обслуживания, либо с вероятностью Г12 может перейти на вторую фазу, либо с вероятностью (1 - Гц - Г12) может покинуть систему. На второй фазе время обслуживания также имеет одинаковое распределение для каждого прибора с произвольной функцией распределения B2(x). По завершении обслуживания на второй фазе заявка с вероятностью Г21 может обратиться к первой фазе для повторного обслуживания, либо с вероятностью Г22 может повторно обратиться ко второй фазе, либо с вероятностью (1 - Г21 - Г22) может покинуть систему. Я 1-Г11-/ Г Л X B1(x) B2(x) B2(x) Рис. 1. Двухфазная система массового обслуживания с обратной связью Введем следующие обозначения: l(t) - число обращений к системе из внешнего источника (первичные заявки), реализованных к моменту времени t; «12(0 - число обращений ко второй фазе системы после обслуживания на первой фазе; «n(t) - число повторных обращений к первой фазе системы после обслуживания на первой фазе; «21(0 - число повторных обращений к первой фазе системы после обслуживания на второй фазе; «22(0 - число повторных обращений ко второй фазе системы после обслуживания на второй фазе. B1(x) Пусть в начальный момент времени система была пуста. Ставится задача исследования многомерного случайного процесса {l(t, N), nn(t, N), nn(t, N), m\(t, N), «22(t, N)}, описывающего потоки заявок в системе. 1-Г21-Г22 Рис. 2. Однолинейная двухфазная СМО с отказами 2. Метод предельной декомпозиции Входящий поток заявок, интенсивность которого равна X, разделим на N независимых потоков по полиномиальной схеме с равными вероятностями. Интенсивность каждого такого потока будет равна X/N. Определим для заявок каждого из полученных потоков единственную однолинейную двухфазную линию обслуживания с отказами (рис. 2). В этой системе заявки, поступающие в период времени, когда хотя бы одна фаза линии занята, не обслуживаются (теряются). X/N Г21 Г11 -*- Нетрудно доказать, что при N ^ да вероятностью потерь заявок можно пренебречь, и тогда характеристики исходной системы будут сходиться к суммарным характеристикам совокупности N однолинейных двухфазных СМО. Итак, задача нахождения распределения вероятностей числа обращений в двухфазной бесконечнолинейной СМО сводится к решению задачи нахождения распределения вероятностей числа обращений в однолинейной СМО с отказами. 3. Исследование однолинейной двухфазной СМО с отказами В описанной выше однолинейной системе будем рассматривать многомерный случайный процесс {l(t, N), nn(t, N), ni2(t, N), «2i(t, N), n22(t, N)}, описывающий число обращений, реализованных за время t в систему извне, с первой фазы на первую фазу, с первой на вторую фазу, со второй на первую и со второй на вторую фазу соответственно. Введем производящую функцию данного многомерного процесса в виде: да да да да да g(X,yii,y2,У21,У22,t,N) = XX X X X х'Уп У«2У2Т У22 •,"ii,"12,«21,"22,t,N). l=0 «11 =0 n12 =0 «21 =0 «22 =0 Докажем следующее утверждение. Теорема. Пусть функцииfk(x,yii,yi2,У21,У22, t), k = 1, 2 определяются следующими преобразованиями Фурье-Стилтьеса: да Ф1 (a, x, уп, У12, У21, У22) = J (x, уп, У12, У21, У22, t) = 0 _XB* (a )_ (1 - ^УпД' (a)) (1 - Г22У22B2 (a)) - Г12У12Г21У21В1 (a)B2 (a) Х|(1 - Г22 У22 B2*(a)) • ^X - (1 - 11Уп) + у Г21У21 ^ + + B2*(a)Г21У21 Г12У12 - Г1Г(1 - r22У22) j| , (i) да x, Ун, У12, У21, У 22) = J e^dJr (x, Ун, У12, У21, У 22, t ) = 0 _XB*(a )_ (1 - Г11У11В1* (a)) (1 - r22У22B2 (a)) - r12У^УгЛ (a)B2 (a) Х|(1 - ГпУп^Л^) • (y^2r12У12 - -Г(1 -Г22У22) j + +B*(a)Г12У12 fx - (1 - Г11У11) + ^Г21У21 J|, (2) да где Bk (a) = JejaJdBk (t) - преобразование Фурье-Стилтьеса от функции распределения В (t) времени 0 обслуживания на фазах системы, k = i, 2; r = (1 - ru)(1 - r22) - rl2r2l. Тогда производящая функция g(x, yii, yi2, y2i, У22, t, N) многомерного случайного процесса {l(t, N), nii(t, N), nn(t, N), mi(t, N), n22(t, N)} в двухфазной однолинейной системе с повторными обращениями к фазам имеет вид: g(X,У1ЪУ12,У21,У22,^N) = 1 + -1 •!(X - 1)Xt + [r11(У11 - 1) + r12(У12 - 1)]j/1(X,Уl1,Уl2,У21,У22,5)d5 + N I 0 +[%(У21 -1) + -2г(У22 -1)]J/2(X,У11,У12,У21,У22,s)dsl + o(N"2) . (3) 0 J Доказательство. Поскольку процесс {l(t, N), «n(t, N), nu(t, N), m\(t, N), «22(t, N)} не является марковским, введем в рассмотрение дополнительные переменные: процесс k(t) - состояние линии обслуживания, т.е. если k-я фаза линии занята, то k(t) = k, k = 1, 2, а если линия свободна, то k(t) = 0; z(t) - длина интервала времени от момента t до момента окончания текущего обслуживания, если линия занята. Процесс {k(t), l(t, N), nw(t, N), nu(t, N), m^t, N), «22(t, N), z(t)} является марковским. Распределение вероятностей этого процесса обозначим следующим образом: - Po(l, nn, n12, «21, n22, t, N) = P{k(t) = 0, l(t, N) = l, nn(t, N) = nw, n12(t, N) = «12, n21(t, N) = «21, n22(t, N) = n22} - вероятность того, что в момент времени t линия свободна и к этому моменту к системе обратилось l заявок из внешнего источника, «п заявок обратилось для повторного обслуживания с первой фазы на первую, «12 заявок обратилось с первой фазы на вторую, «21 заявок обратилось повторно к первой фазе после обслуживания на второй фазе, n22 заявок повторно обратилось ко второй фазе системы после обслуживания на второй фазе системы; - Pk(l, «и, «12, «21, «22, z, t, N) = P{k(t) = k, l(t, N) = l, «w(t, N) = «11, «12(t, N) = «12, «21(t, N) = «21, «22(t, N) = «22, z(t) < z}, k = 1, 2, - вероятность того, что в момент времени t занята k-я фаза системы, к этому моменту к системе обратилось l заявок из внешнего источника, «п заявок обратилось для повторного обслуживания с первой фазы на первую, «12 заявок обратилось с первой фазы на вторую, «21 заявок обратилось повторно к первой фазе после обслуживания на второй фазе, «22 заявок повторно обратилось ко второй фазе системы после обслуживания на второй фазе системы, и остаточное время обслуживания заявки, находящейся в системе, меньше z. Для распределения вероятностей многомерного процесса {k(t), l(t, N), «n(t, N), «u(t, N), «21(t, N), «22(t, N), z(t)} составим прямую систему дифференциальных уравнений Колмогорова. дР0Ц, пи, п12, n2l, п22, t, N) Пц, nl2, n2l, п22,0, t, N) ----(1 - rii - 12)-z-+ ot oz ч дР (l, Пл, П?, n„, П? ,0, t, N) А +(1 -Ъ -Г22) 2(, П^ П 2,п21 , 22, , , ) --Po(l,П1 ,П2,П21 ,П22,t,N) , (4) dz N ap(i, П1, П2, П21, П22, z, t, N) _ ap(i, П1, П12, П21, П22, z, t, n ) _ St dz dp(l,n,,,n17,n.,n77,0,t,N) А л ,, , „ , . --1( , 11, ^^ , , ) +-Po(l -1,nn,n,2,n21,n22,t,N)Д(z) + dz N D,_,dpp(l, n11 - l, n21, n22 , 0 t, N) , „ D ,_,dP2(l, ^^ nl2, n21 - 1 n22,0, t, N) «ч +r11B1(z)-2-+ r21B1(z)-2- , (5) dz dz dP,(l, n1, n2, n21, n22, z, t, N) _ ap,(l, nu, n12, n21, n22, z, t, N) _ St dz dp(l,ni,^,n21,n22,0,t,N) dp (l,ni,n2 -1,n2i,n22,0,t,N) + (z У + dz dz +f B ф dP2 (l, n11, n12 , n21, n22 - 1, 0, t, N) (6) 22 2 dz Начальные условия для системы (4)-(6) запишем в виде: 10, если l > 0,П\ > 0,n12 > 0,n2X > 0,n22 > 0, pP0(1, nll, n12, n21, ^,0, N)-10,ЛП , п [R (N), если l - ^ - n2 - n21 - n22 - 0, 10, если l > 0, ^ > 0, % > 0, n21 > 0, n22 > 0, Р (l, ni, n2, %, n2, z,0, N) - < [R(z,N), если l -^ -n2 -n21 -n22 - 0, k -1,2, где Ro(N), R^z, N), R2(z, N) - стационарное распределение вероятностей занятости фаз в однолинейной СМО, удовлетворяющее условию нормировки: R (N) + R (да, N) + R (да, N) -1. Введем следующие функции: да да да да да g0 ( X Уш У12, У 21, У 22, t, N ) = XX X X X х1Уп УТ Уа У«2 •P0(1, nl1, nl2, «21, n22, t, N) , l=0 «11 =0 «12 =0 «21 =0 «22 =0 да да да да да gkk У11, Уl2, y2l, y22, t, N ) = XX X X X х1Уп У«2 УГ- У22 •kk1, «ш nl2, n2l, t, N), k = i,2. l=0 «11 =0 «12 =0 «21 =0 «22 =0 Тогда, из уравнений (4)-(6) следует, что эти функции удовлетворяют уравнениям 0 gpC^ У1^ Уl2, У 21, У 22, t, N)=(1 _ г чд gl( X Уl1, Уl2, У 21 , У 22, C, t, N) + 8t 11 12) & +(1 r r ) 0 g2( ^У^ У12, У21, У22, C, t,N) X g (x У У У У t N) (7) +(1 - r21 - r22)----- g0( X, У11, У12 , У21, У22 ,t, N ) , (7) oz N д gl(x, Ун, Уl2, У21, У 22, z, t, N) = 5 gl( X, У-U Уl2, У 21, У 22, Z, t, N) _ д t 8z -д g1( X' У11, У12,У21, У22,0, ^ N) xBi( Z) g0( X, Уц, У12, У21, У22, t, N) + oz N + r v р{_Лд gl(x, Уl1, У12 , У21, У22 , C, t, N) , _ v д frs 5 g2( X, Уl1, У12 , У21, У 22 , C, t, N) m OZ oz д g2 (X Уl1, Уl2, У 21, У 22, z, t, N) = д g2( x, Уll, У12, У21, У22, z, t, N) _ dt 8z дg2(x, Уl1, Уl2, У 21, У 22, 0, t, N) , , .. R r_4°gl( X Уl1, Уl2, У 21, У22А t, N) , - + r12 У12 B2( Z) - + oz oz +r^B (z) 0 g2( X, У11, У12, У21, ^At,N) . (9) Oz Начальные условия для системы (7)-(9) имеют вид: g0(x,У1^У12,У21,У22-0-N) = N) , gk(x, У^ У12 , У21, У 22, z,с, N) = Rk(z, N) , k =i,2. В работе [22] показано, что X 1 - r z Rl(z,N) = ---22 J(1 -Bl(u))du, N r 0 R2( z, N) = ^ J (1 - B2 (v))dv, N r J где r = (1 - -1i )(1 - r22) - -12г21 . Тогда X 1 R,( N) = 1 - Rl(cx>, N) - R2K N) = 1 --• - [(1 - r22)bl + rl2b2 ], N r где bi и b2 - математические ожидания времени обслуживания на первой и второй фазах соответственно. Решение системы уравнений (7)-(9) будем искать в виде: g0 (XУ11,У12, У21 ,У22, t, N)= 1 - -1 F0(x, У11,У12,У21, У22, t) + o(N~2) , (i0) gkk X У^ У2 ъ У22, z, t, N) = -1 Fk(x, Уш У^ У2 ъ У22, z, t) + o(N~2), k = 1, 2, (ii) где Fo(-), Fi() и - некоторые функции, не зависящие от N. Подставив выражения (10), (11) в систему (7)-(9), получим систему уравнений для функций FoQ и FkO, k = i, 2: d F0( - У^ Уl2, У 21 , У 22 , t) --- (1 - rl1 - rl2)fl(X, У^ Уl2, У21 , У 22 , t) dt -(1 - r2l - r22)f2(-, У^ У12 , У21 , У 22 , t) , (12) dFli-Уll,У12,У21,У22,z,t) = dFl(XУ11,У12,У21,У22^1 z,t) , ^xB(z) I dt dz l( ) + (ГпУИВ1(2)-1)./^(-,Уl1,У12 ,У21 ,У22 , t) + r2lУ21B1(z)f2(-, Уl1, У12 , У21 , У22 , t) , (13) d A^ y^ У12, У21, y 22, z, t) = d f2( x Уll, У12, У21, y 22, z, t) + dt dz + (r22У22B2 (z) - 1)f2 У11 , У12 , У21 , У22 , t) + Г\2УХ2В2 (z)f Уl1, У12 , У2^ У22 , t) , (14) где f(x,y„,У,2,У,,Угг,t)-e"'(XУ"'У22'0't). k = 1, 2, dz с начальными условиями: F (x, У11, У12, У21, У22,0)- N-(1 - R0(N)), (15) Fkk X, УП, У!2, У2!, У22,0Ь N -Rk(z, N) , k = 1,2 (16) Решая дифференциальные уравнения (13) и (14) в частных производных первого порядка, найдем вид функций F\(x, yw, У12, У21, У22, z, t) и F2(x, yw, У12, У21, У22, z, t): A, z+t t F1(X У11, У12 , У21, У22 , z, t) - - (1 - r22 ) j (1 - B1 (u))du + j[-(z + t - S) + r 0 0 (rl 1У11B1 (z + t - s) - 1) Уш У12, У21, У22, s) + Г21У21В1 (z + t - s)f2 (Х У11, У12, У21, У22, , (17) - Г F (X, Уl1, У12, У21, У22, z, t) rl2 I (1 - B2(v))dv + + 2* z+t r t +j [rl2 У12 B2 (z + t - s)f1 (X, У11, У12, У21, У22, s) + (r22 У22 B2 (z + t - s) - 1) f2(x, У11, У12, У21, У22, s)]ds . (18) 0 Из уравнения (12) несложно найти вид функции Fo(x, yw, у12, У21, У22, t): F0( X, У11, У12 , У 21 , У 22, t) - - 1_rk ь +-b +1 г t -(1 - rl1 - ^{.j Уш Уl2, У21, У 22, s)ds - (1 ^21 - У^ У21, У22, s)ds . (19) 0 0 Тогда, учитывая (10), (11), получаем g (X, Уll, У12, У 21, У 22, z, t, N)-1 - -1 F0( Ут Уl2, У 21, У 22, t) + ^^ Уl2, У2l, У22, z, t)+F2( Уll, У12, у 21, У 22, z, t)+o(N~2). (20) При z ^да выражения (17), (18) примут вид: - F( X, У11, У12, У21, У22, t)--(1 - r22)bl +-Xt + r t t + (Г1^Уц - 1) j f (X, У11, У12 , У21, У22, s)ds + r2ly21 jf2 (X, У11, У12, У21, У22, s)ds , 0 0 - F2 (X, У11, У12, У21, У22, t) - - rl2b2 + r t t +rl2У12 jf (X, У11, У12, У21, У22, s)ds + (r22У22 - 1) \f2 (X, У11, У12, У21, У22, s)ds . Тогда, учитывая (20), производящая функция g(x, yii, yi2, У21, У22, t, N) многомерного случайного процесса {l(t, N), nw(t, N), ni2(t, N), П21 (t, N), n22(t, N)} в двухфазной однолинейной системе с повторными обращениями к фазам имеет вид: g (X. 711.712.721.722. t,N) = = 1 + ' l(X- 1)Xt + [r11(711 -1)1 + r12(712 -1)]J/1(X'711'712.721.722.s)ds + N I 0 0 t + [r21 (721 - 1) + r22 (722 - 1) ] J /2( X. 711.712.721.722.s)ds [ + o( N ) , 0 J что совпадает с выражением (3) теоремы. Для нахождения неизвестных функцийfi(x,yii,yi2,У21,У22, t) иf2(x,yii,У12,У21,У22, t) продифференцируем равенства (17) и (18) и рассмотрим их при z = 0. Получим систему интегральных уравнений для функций fi(x, yii, У12, У21, У22, t) и f2(x, У11, У12, У21, У22, t): "(1 - Ъ), ■(1 - B1(t)) + xB1(t) /(X 711 . 712.721.722.t) = X r t +r11711 Jb1(t - s)/( X. 711. 712. 721. 722 .s)ds + r21721 Jb1(t - s)/2 (X. 711. 712. 721. 722.s)ds , (21) 0 0 r Л( X. 711. 712.721.722.t) = X~ (1 - B2(t) ) + r t t +r12 712 Jb2(t - s)/ (X. 711.712. 721. 722. s)ds + r22722 Jb2(t - s)/2 (X. 7n. 712. 721. 722. s)ds , (22) 0 0 где bi(t) и b2(t) - плотность распределения времени обслуживания на первой и второй фазах соответственно. Решение системы интегральных уравнений (21)-(22) относительно неизвестных функций fi(x,yii, y 12, У21, У22, t) иf2(x, yii, y 12, У21, У22, t) можно найти, используя преобразование Фурье-Стилтьеса вида: % (а. X. 711.712.721.722) = J^^^^71!^2!^) Л = 0 St = J eJa'dtA (X 711.712.721.722.0, k = 1, 20 Тогда из системы уравнений (21)-(22) можно получить систему для функций 9i(a, x, yii, yi2, У21, У22) и ф2(а, x, yii, y 12, У21, У22): (r1^711B1* (а ) - 1)ф1(а. X. 711. 712. 721.722) + r21 721 B1 (а ) Ф 2 (а . X. 7ц. 712. 721. 722) = X =--(Xr - (1 - r22)(r11711 - 1) + r12r21721 )В1*(а) , (23) r r12712В2 (а)ф1 (а. X. 711. 712. 721. 722 ) + (r22722В2 (а) - 1)Ф2 (а. X. 7и . 712. 721. 722) = X » =--(r12(1 - r22)712 + r12(r22722 - 1)) В2>(а) , (24) r ■В (t) где В* (а) = j-^ j dt = j в]а1Ьк (t)dt, к = 1,2. о St о Решая систему (23)-(24), получим выражения (1) и (2) для функций ф1(а, x, yii, yi2, У21, У22) и ф2(а, x, yii, y 12, У21, У22), определяющие вид функцийfi(x,yii, yi2, У21, У22, t) иf2(x, yii, У12, У21, У22, t). Теорема доказана. 4. Исследование двухфазной СМО с неограниченным числом приборов и повторными обращениями на каждой фазе Определим совместную производящую функцию многомерного процесса {/(0, nii(t), «i2(t), «2i(t), «22(0}, описывающего потоки в двухфазной системе с неограниченным числом линий и повторными обращениями на каждой фазе, в виде: да да да да да G(x, yu, yi2, y21, y22, t) = S E E Х'Уп У12 У2Т Уя «11, «12. «21' «22' t) • /=0 ип =0 и12 =0 =0 «2 =0 Тогда, в силу независимости однолинейных систем, рассмотренных выше, производящая функция G(x, jii, J12, J21, J22, t) определяется выражением G(x,yu,У12,У21,У 22't) = lim g(XУтУ12.У 21'У 22't,N)N = N -да = lim I 1 + Ь •](x " 1)At + [Г11(У11 " 1)1 + Г12(У12 - 1)] J f1(x'У11.У12.У21'У22's)ds + N-да^ N l 0 t 1 2 ^ + [Г21(У21 - 1) + r22 (У22 - 1)] J f2 (x' У11. У12 ' У21' У22's)ds Г + o(N 2) 0 у = exp -j (x -1) А/ + [rn (Уц -1) + Г12(У12 -1)] Jf (x, У11, У12, У21. У22.s)ds + l 0 + [r21 (У21 - 1) + r22 (У22 - 1)] J f2 (X У11. У12. У21. У22.s)ds 1 • 0 J Так как совместная производящая функция многомерного распределения вероятностей процесса {/(t), nii(t), «12(0, «2i(t), «22(f)} не равна произведению производящих функций одномерных распределений, то очевидно, что потоки не являются независимыми, поэтому анализ таких потоков требует их совместного рассмотрения. Заключение В настоящей работе рассмотрена математическая модель обслуживания заявок в неоднородной двухфазной системе массового обслуживания M/GI/да ^ GI/да с возможностью повторного обращения заявки к любой фазе системы. Методом предельной декомпозиции получено аналитическое выражение для производящей функции многомерного потока обращений заявок к фазам системы. Полученное выражение может быть использовано для определения вероятностных характеристик компонент рассматриваемого многомерного потока. Полученные результаты могут быть использованы для анализа потоков в различных социально -экономических системах, где имеет место повторное обращение клиентов к системе при различных условиях, например в торговых или страховых компаниях, а также в технических системах распределенной обработки больших данных и облачных сервисах.

Скачать электронную версию публикации