Analysis of repeated flow in queueing tandem GI|GI|? with feedback by method of markovian summation.pdf Системы массового обслуживания (СМО) с неограниченным числом приборов используются в качестве математических моделей при решении достаточно широкого круга прикладных задач, например при исследовании процессов в социально-экономических системах [1, 2], в телекоммуникационных системах [3, 4] и т.д. Зачастую по различным причинам обслуживаемым объектам требуется возвращение в систему для повторного обслуживания. В таких случаях используются модели СМО с возможностью повторного обслуживания (с обратной связью). В этом классе СМО различают системы с мгновенной и отсроченной обратной связью [5]. В системах с неограниченным числом приборов, как правило, рассматриваются модели с мгновенной обратной связью. Одним из первых исследователей, обративших свое внимание на системы с обратной связью, был Л. Такач [6, 7]. Однако в дальнейшем исследователи не проявляли особого интереса к подобного рода системам в течение достаточно длительного периода. И лишь в последние несколько десятилетий, с развитием телекоммуникационных сетей, появилась потребность построения моделей с обратной связью [8-10]. Для исследования потоков в системах с обратной связью используются различные методы. Однако, как правило, каждый из них применяется при определенных ограничениях. Так, например, метод производящей функции и метод предельной декомпозиции можно использовать лишь в системах с простейшим входящим потоком [11-15]. Особого внимания заслуживает метод асимптотического анализа [16-19], позволяющий аппроксимировать распределение вероятностей исследуемого процесса при определенных условиях в случае, когда аналитическое решение системы уравнений, характеризующих процессы в системах, не представляется возможным. В настоящей работе предлагается применить метод марковского суммирования [20, 21] для исследования потока повторных обращений в двухфазной системе с неограниченным числом приборов на каждой фазе, мгновенной обратной связью на второй фазе, с рекуррентным входящим потоком и неэкспоненциальным обслуживанием. Как правило, исследование процессов в системах массового обслуживания проводится в предположении, что системы функционируют в стационарном режиме. Однако это не всегда соответствует целям исследования. В настоящей работе представлено исследование указанной модели в нестационарном режиме. 29 М.А. Шкленник, А.Н. Моисеев, Л.А. Задиранова 1. Математическая модель Рассмотрим двухфазную систему массового обслуживания с неограниченным числом обслуживающих устройств на каждой фазе (рис. 1). Рис. 1. Двухфазная система массового обслуживания с мгновенной обратной связью Fig. 1. Tandem of queues with instantaneous feedback На вход системы поступает рекуррентный поток заявок, заданный функцией распределения длин интервалов времени между последовательно наступающими событиями A(x) и функционирующий в стационарном режиме. Интенсивность X наступления событий в рекуррентном потоке определяется выражением [ 18] 1 Х = да J[l - A( х)] dx (1) о Обслуживание заявок на первой фазе в каждом из приборов протекает независимо от других, а продолжительность такого обслуживания есть неотрицательная случайная величина с функцией распределения Д(х). По завершении обслуживания на первой фазе заявка может с вероятностью r перейти на вторую фазу либо с вероятностью (1 - п) покинуть систему. На второй фазе время обслуживания также имеет одинаковое распределение для каждого прибора с произвольной функцией распределения Бг(х). По завершении обслуживания на второй фазе заявка может с вероятностью Г2 снова обратиться ко второй фазе, либо с вероятностью (1 - Г2) покинуть систему. Будем называть обращение заявок на вторую фазу «повторным обращением (обслуживанием)» независимо от того, с какой фазы они поступают. Таким образом, в рассматриваемой системе заявки, обратившиеся для обслуживания впервые и повторно, обрабатываются в течение времени, отличающегося по своим характеристикам. Поток заявок, обратившихся к системе для повторного обслуживания, т.е. поступивших на вторую фазу системы, будем называть r-потоком. Ставится задача найти распределение вероятностей числа событий в r-потоке за фиксированный интервал времени [0; T] при условии, что в начальный момент времени система пуста. 2. Метод марковского суммирования Пусть в момент времени = 0 система свободна и в ней нет обслуживаемых заявок. Зафиксируем некоторый момент времени T, причем 0 < t < T. Каждая заявка входящего потока, поступив в систему в момент времени t, будет формировать события r-потока. Последовательность моментов наступления событий в r-потоке, сформированных одной заявкой, поступившей в систему, будем называть локальным r-потоком. 30 Исследование потока повторных обращений в двухфазной системе массового обслуживания GI\\GI\\ Обозначим: - n(t) - число событий r-потока, сформированных всеми заявками входящего потока, поступившими в систему на интервале [0, t]; - £(t) - число событий в r-потоке, сформированных за интервал времени [t, T] одной заявкой, пришедшей в момент времени t; - g(i, t) = P{£(t) = i} - вероятность того, что заявка, поступившая в систему в момент времени t, к моменту времени T сформирует в r-потоке i событий; - z(t) - остаточное время от момента t до момента наступления следующего события во входящем рекуррентном потоке; - P(n, z, t) = P{n(t) = n, z(t) < z} - вероятность того, что к моменту времени t в r-потоке произошло n событий и при этом z(t) < z. Тогда по формуле полной вероятности можно записать следующее равенство: n P(n, z, t + At) = P(n, z + At, t) - P(n, At, t) + A(z) X P(n - i, At, t) g(i, t) + o(At) . i=0 При At стей P(n, z, t) ->0 получим дифференциальное уравнение Колмогорова для распределения вероятноdP(n, z, t) dt dP(n, z, t) dz dP(n, 0, t) dz n + A( z) X i=0 dP(n - i, 0, t) dz g (i, t) (2) с начальным условием P(n, z, 0) = \\R(z), n = 0, [0, n > 0, где R(z) - распределение вероятностей значений случайного процесса z(t) в стационарном режиме. Определим характеристические функции вида (3) H(u, z, t) = X eJunP(n, z, t), n=0 G(u, t) = X eju‘ g(i, t) . i=0 Тогда от задачи (2)-(3) можно перейти к дифференциальному уравнению для характеристической функции исследуемого процесса n(t): dH (u, z, t) dH (u, z, t) dH (u, 0, t) - + - -(A(z)G(u,t)-1) . dt dz dz Характеристическая функция G(u, t) процесса £(t) найдена в работе [21] и имеет вид: rr +» bl(o)bl(a) (l - e-ja(T-t)) G(u,t) = 1 + h(eu - 1)Bi(T-1) + rrr2(eju - 1)eju J --^->-da , 2% -» (1 - r2 e]ub2 (a)) ja где b*(a) = JejazdB(t), b*(a) = JejazdB2(t) . 0 0 Обозначив 1 +» b*(a)b*(a) (1 - e“ja(T-t)) Ф, t) = - J-7---4-- d a. 2% -„ (1 - r2e]ub2 (a)) ja получаем уравнение вида dH(u, z, t) _ dH(u, z, t) dH(u, 0, t) dt с начальным условием dz dz A(z) -1 + A(z)r1 (eju -1) (B1 (T -1) + r2ejuy(u, t)) H(u, z, 0) = R(z) . (4) (5) 31 М.А. Шкленник, А.Н. Моисеев, Л.А. Задиранова Решение задачи (4)-(5) будем искать методом асимптотического анализа [16] при условии высокой интенсивности входящего потока. Для этого запишем функцию распределения длин интервалов времени между событиями входящего потока в виде A(Nz), где N > 0 - параметр высокой интенсивности потока. Тогда, выполнив соответствующие преобразования, уравнение (3) можем переписать в виде: 1 dH (u, z, t) _ dH (u, z, t) dH (u, 0, t) N dt dz dz A(z) -1 + A(z)rr (eju -1) (B (T -1) + r2eJu ф, t) ) 3. Асимптотический анализ первого порядка Используя метод асимптотического анализа, выполним замены -1 = 8, u = sw , И(u,t) - Fi(w,t,s) , тогда уравнение (5) можно переписать в виде: „ dFi(w,z,t,s) _ dFi(w,z,t,s) | dFi(w,0,t,s) 8 - + X dt dz dz x[A(z) -1 + A(z)r (eJws -1)(B(T -1) + r2ejwsq(w,t,s) ) (6) (7) Теорема 1. Пусть параметр X входящего рекуррентного потока определяется выражением (1), а функция R(z) - распределение вероятностей значений случайного процесса z(t) в стационарном режиме. Тогда асимптотическое решение Fr(w, z, t) = lim Fr(w, z, t, s) уравнения (7) имеет вид: F (w, z, t) - R(z) exp < jwr{k T p ,rUr + h +■? b*(a)b2(a) (t + e~jaT -e-j«T-t> : J B1(y)dy + - J -г---Т t +- 2л-а> jal1 - r2b2(a) jV d a t-t ja (8) где bk *(a)-J eJatdBk (t) - преобразование Фурье-Стилтьеса функции распределения Bk (t) времени о обслуживания на фазах системы, k = 1, 2. Доказательство. Доказательство теоремы будем проводить в два этапа. Этап 1. В уравнении (6) выполним предельный переход s ^ 0, получим следующее уравнение: dFr(w, z, t) dFl(w,0, t). 0 - dz dz -[A(z) -1]: решение которого будем искать в виде: F (w, z, t) - R( z)0 1(w, t), где Фі(^, t) - некоторая скалярная функция. Этап 2. Выполним в (7) предельный переход z ^ да, получим s^w^As) = dFi(w.°.t,s) ew-1)( (T-1) + jwt,s)). r)f r)v V f Разложим ejws и функцию ф(^,е, t) в ряд Маклорена: eJW - 1 + jws + O(s2), Ф, s, t) - ao (t) + a1 (t) ■ jws + O(s2), где , ч 1 +“ *, 4 b7 (a) ao(t) -- J bi(a\\ , 2% -„ 1 - r2b2 (a) 1 +” * a1(t) - Г2 - J *1(a) 2^ -да 1 - e -ja(T-t)Л d a. ja f i*,„\\ V ( 1 - e-ja(T-t) \\ b2(a) V1 - r2b2(a) J d a . ja (9) (10) (11) (12) (13) (14) 32 Исследование потока повторных обращений в двухфазной системе массового обслуживания GI\\GI\\ Подставим выражения (9), (11), (12) в уравнение (10), разделим обе части равенства на в и произведем предельный переход в ^ 0. С учетом того, что R'(0) = X [18], получаем дифференциальное уравнение относительно функции Фі(^, t) -f1) = rj фх (w, t) (Bx (T -t) + r2a0 (t)) . Обозначим (15) v(x) = Bi(T - x) + ^(x), тогда решение этого уравнения при начальном условии Фі(^, 0) = 1 имеет вид: (16) ф^,t) = expJwr{k\\^(x)dx f. Подставив в (16) выражение (13) и выполнив несложные преобразования, получим следующее выражение для функции Фі^О: ф (w, t) = exp < Jwr X J Bi(y)dy + -^ J t-t r2 +” b*(a)b*(a) ( e-jaT -e-ja(T-t) ^ 2%. > Ja (l - ^b2 (a)) t + ja da (17) Тогда, подставляя (17) в (9), получаем асимптотическое решение F (w, z, t) = lim F (w, z, t, в) задачи (7) в^0 в виде (8). Теорема доказана. 4. Асимптотический анализ второго порядка В уравнении (5) выполним следующую замену: H (uzt)=HM z t )exp fJuNr' XJv(x)dx 1 • (18) получим уравнение относительно функции Иг(и, z, t) l dH2 (u, z, t) N dH2 (u, z, t) dH2 (u,0, t) dt + jukrxH2 (u, z, t )y(t) = dz dz Выполним в этом уравнении замены 1 ,2 N A(z) -1 + A(z)r (eju -1)(B (T -1) + r2ejup(u, t)) = в , и = Bw , H2(u,z,t) = F2(w,z,t,s), (19) получим 2 dF2(w,z,t,в) dt + jBw\\rxF2 (w, z, t, в) y(t) = dF2(w, z, t, в) dF2(w,0, t, в) A(z) -1 + A(z)r (e]sw -1)(B (T -1) + r2e]swq>(w, t, в)) я я .....v 11 1 I,,,, (20) dz dz ’ ’ . ’-i Теорема 2. Пусть параметр X входящего рекуррентного потока определяется выражением (1), функция ^(z) - распределение вероятностей значений случайного процесса z(t) в стационарном режиме и к = г1Х3(а2 - а2), (21) где а и а2 - конечные математическое ожидание и дисперсия случайной величины с функцией распределения A(x). Тогда асимптотическое решение F2(w,z,t) = limF2(w,z,t,в) уравнения (20) имеет вид: в^ F2 (w, z, t) = R( z) exp < (jw)2 x J H(y)dy+x£[ J 1 2%l ja(1 - r2b*(a)) I T-t te~ ja(T-t) - e~ JaT ^ da ja J 33 М.А. Шкленник, А.Н. Моисеев, Л.А. Задиранова \\2 ( „-ja(T-t) -/аГ Л 2 +да г,г,* Kr22 +да Ъ*(а) + KTL Г ТГ J л ^ г а -да + к Ъ2(а) ѵ 1 - Г2 Ъ2(а) J +да 7 * t - ■ - е j а d а + Г Bi(y)+AjA*» ’-11 2Л-оо(1 - г2Ъ2(а) ) 1 - е -/ОУ Л 2 d а /а J dy (22) да где \\*(а)=І е]Штк (Г) - преобразование Фурье-Стилтьеса функции распределения Вк (t) времени 0 обслуживания на фазах системы, k = 1, 2. Доказательство выполним в три этапа. Этап 1. Положим в (20) s м 0, получим [ A(z) -1] = 0 . 8F2(w, z, t) 8F2(w, 0, t) dz dz Решение уравнения F2(w, z, t) будем искать в виде: (23) F2(w z, t) = R(z) Ф2(w, t) , где Ф2(^, t) - некоторая функция, не зависящая от z. Этап 2. Решение уравнения (20) запишем в виде разложения F2 (w, z, t, s) = Ф2 (w, t) [R(z) + jswy(t)f (z)] + O(s2 ) , (24) где f(z) - некоторая функция. Подставим это выражение в (18). Используя разложения (11) и (12), получим /sw^r^t^ (w, t)R(z) = Ф2 (w, t) {R'( z) + jswf '(z)y(t) + R'(0) [A( z) - 1 ] + +R'(0)jswr1A( z)y(t) + jswf '(0)y(t) [ A( z) - 1]} + O (s2 ). В [18] показано, что R'(z) = R’(0)[1 - A(z)], тогда, приведя подобные и сократив обе части на jsw, получим КЦz) = 1 (z) + f'(0) [A(z) -1] + XrxA(z) + O(s) . Отсюда при s м 0 получаем дифференциальное уравнение относительно неизвестной функции f(z): f'(z) = f '(0)[1 - A(z)] + Krx [A(z) - R(z)]. Проинтегрируем обе части этого уравнения по z от 0 до да, получим уравнение f (да)-f (0) = f' (0) --ч К j [1 - R( z)] dz -1[1 - A( z)] dz Vo решение которого дает результат [18] f' (0) - Kf (да) = (25) где к определяется выражением (21). Этап 3. В уравнении (20) выполним предельный переход при z м да. В силу способа построения функции F2(w, z, t, s) она является монотонно возрастающей и ограниченной сверху функцией по z. Следовательно, lim 8F2(wz,s) zm« dz = 0. ( SW)2 Учитывая это и применяя разложение экспоненты e/sw = 1 + jsw +-----+ O (s3) и функции 2 9(w, s, t) = a0 (t) + a1 (t) • jws + O(s2), получаем 34 Исследование потока повторных обращений в двухфазной системе массового обслуживания GI\\GI\\ ,2 SF2(w,да,t,8) д t - j8wXrly(t)F2 (w, да, t, 8) = SF2(w, 0, t, 8) Sz jewiy(t) - + ( j8w)2 2 ■ r (y(t) + 2r2a0 (t) + 2r2ax (t)) + О (83) + jewlr^t )Ф2 (w, t) + (j8w)2 X^y2(t)f (да)Ф2(w, t) = Подставим сюда разложение (24), при z ^ да получим 2 ЗФ 2(W, t) dt = Ф2 (w, t) jswXryt) - (j8w) Ц. (y(t) + 2г2 (ao (t) + a (t)) + (j8w)2 ^y2 (t) О (83 )- Приведем подобные и сократим на 82, тогда ЗФ 2(w, t) (jw)2 Ф2 (w, t) df (0) X' (y(t) + 2r2(ao(t) + a(t)) + 2w2(t)| ---Xf (да) 0(8) . 3t 2 Учитывая (25) и переходя к пределу при s ^ 0, получим дифференциальное уравнение относительно неизвестной функции Ф2^, t) ЗФ^t) = Ф2(w, t)ri [X(^(t) + 2Г2(ao(t) + ai(t)) + y2(t)k] . Решение этого уравнения с учетом начального условия Ф2(я’, 0) = 1 имеет вид: Ф2^, t) = exp jL Г Xj[y( x) + 2r2 ( a (x) + a (x))] dx + k| y 2( x)dx Тогда в силу (23) имеем (jw)2 F2(w, z, t) = R( z) exp Xj[y( x) + 2r2 (a0( x) + ai( x) )J dx + k| y 2( x)dx о 0 Подставив сюда выражения (13), (14), (15) для функций ao(x), a\\(x) и y(x) и выполнив несложные преобразования, получаем выражение (22), что и требовалось доказать. Вернемся к характеристической функции H(u, z, t) исследуемого процесса. Выполним в (22) обратные замены и получим аппроксимацию H(u,z,t) « R(z)exp + Л Nr, juNriX f Bt(y)dy + І f °i(°)°2(°)> ’-f 2Л-да ja(i - r2b2(a)) b* (a)b* (a) (3 - r2b*2 (a)) Ь;(а)Ь;(а) [ e~jaT -e~ja(T-t^ ja d a f 3r r bi(a)b2(a) (3 - '2ь2 X f B,(y)dy + X -Х f-, V . ,2 2% -да ja (i - r2b2 (a)) ( e-j'a(T-t) - e-j'aT Л t-d a - T-t V ja T + Kf Bi(y) + £ f +да j * T-t ' г bx (a)b2 (a) 2% J- (i - rzb2(a)) i - e -jay \\ у d a ja dy которая имеет место при достаточно больших значениях N. Функция H(u, T) = lim H(u, z, T) есть характеристическая функция числа событий, наступивг^да ших в потоке повторных обращений за интервал времени [0, T]. H(u,T) « exp< juN'X f Bi(y)dy + '2 +J bJ(a)b20 i £[P(n) - F(n)\\ n=0 между соответствующими распределениями числа событий в потоке повторных обращений для гауссовской аппроксимации P(n) и для распределения F(n), полученного в результате имитационного моделирования. В таблице приведены значения расстояний Колмогорова для рассматриваемого численного примера. Как видим, при увеличении параметра N высокой интенсивности входящего потока расстояние Колмогорова между указанными распределениями уменьшается, т.е. точность полученной аппроксимации растет. 36 Исследование потока повторных обращений в двухфазной системе массового обслуживания GI\\GI\\ P(n) P(n) n n P(n) 0.07 0.06 0.05 0.04 0.03 0.02 P(n) И n 0.01 0 0 A □ В в sd 10 20 N = 50 30 40 Рис. 2. Сравнение гауссовской аппроксимации (квадраты) распределения числа событий в потоке повторных обращений n и распределения, полученного в результате имитационного моделирования (закрашенные кружки), для разных значений N параметра высокой интенсивности входящего потока Fig. 2. Comparisons of the Gaussian approximation (squares) and empiric distribution (circles) for various values of parameter N Расстояние Колмогорова А между аппроксимацией и эмпирическим распределением N 5 6 7 10 25 50 100 200 Д 0,0671 0,0541 0,0479 0,0315 0,0227 0,0181 0,0125 0,0086 Если в качестве допустимого значения погрешности принять расстояние Колмогорова А < 0,05, то для рассматриваемого примера можно считать, что полученная аппроксимация применима при N > 7. Таким образом, полученный результат (26)-(28) применим даже для не очень больших значений интенсивности входящего потока. Заключение В работе рассмотрена математическая модель обслуживания заявок в двухфазной системе массового обслуживания GI|GI|w^ GI| да с возможностью повторного обращения заявки ко второй фазе 37 М.А. Шкленник, А.Н. Моисеев, Л.А. Задиранова системы. Методом марковского суммирования получена система уравнений для исследования случайного процесса, описывающего число событий в потоке повторных обращений к системе при нестационарном режиме работы. Методом асимптотического анализа при условии высокой интенсивности входящего потока доказано, что распределение вероятностей числа событий в потоке повторных обращений за фиксированный интервал времени [0; T] может быть аппроксимировано нормальным распределением с математическим ожиданием и дисперсией, вычисляемыми по формулам (27) и (28) соответственно. Проведенные численные эксперименты подтверждают хорошее качество данной аппроксимации.

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