The insensitivity of stationarynetwork states probability distribution for the networks with multi-regime servicestrategies, different types of the demands and LCFS PR service discipline..pdf Большую важность для практики представляет изучение сетей массового обслуживания, в которых обслуживающие приборы в узлах могут выходить из строя, так как любые технические средства в процессе их эксплуатации могут отказывать, требуя восстановления (ремонта или замены). Здесь возможны несколько различных постановок: обслуживающий прибор может полностью выходить из строя при обслуживании требования либо при обслуживании требования и в свободном состоянии, либо частично выходить из строя, при этом он продолжает работать, но с меньшей производительностью. Так, в работе [1] были введены в рассмотрение сети массового обслуживания с многорежимными стратегиями, в узлахкоторых приборы могут функционировать в различных режимах. Каждый режимобслуживания характеризуется своими показателями, то есть при переходе прибора в более худший режим его производительность уменьшается. Прибор может частично терять свою работоспособность, как при обслуживании требования, так и в незанятом состоянии. В [2] была установлена инвариантность стационарного распределения вероятностей состояний относительно функционального видараспределения количества работы, необходимого для обслуживания требования, когда дисциплиной обслуживания является «обобщенное разделение процессорасо случайным выбором канала в узле». В [3] для открытой сети с многорежимными стратегиями, несколькими типами заявок и дисциплиной обслуживанияLCFS PR было найдено стационарное распределение в мультипликативной форме. Однако в [3] считалось, что время обслуживания и время пребывания приборав каждом режиме имеют экспоненциальное распределение. На практике указанные предположения чаще всего не выполняются. Поэтому в данной работе рассматриваются аналогичные сети, в которых величина работы по обслуживаниюзаявки имеет произвольный закон распределения.Устанавливается, что стационарное распределение вероятностей состоянийуказанных сетей не зависит от вида законов распределения величин работ по обслуживанию заявок в узлах, если фиксированы первые моменты этих законов.34 Ю.В. Малинковский, А.Н. Старовойтов, А.Р. Еремина1. Постановка задачиВ сети массового обслуживания, состоящей из N однолинейных узлов, циркулируют заявки M типов. Поступающий -----поток заявок - простейший с интенсивностью ƒ, а каждая заявка входного потока независимо от других заявок направляется в l-й узел и становится заявкой u-го типа с вероятностью p0 (l,u). После обслуживания в l-м узле заявка u-го типа независимо от других заявок мгновенно направляется в k-й узел и становится заявкой v-го типа с вероятностью p(l,u)(k,v), а с вероятностью p(l,u)0 покидает сеть, где 0( , )1 11N M l u l u p = ҐТ ҐТ = ; ( , )( , ) ( , )01 11N M l u k v l u k v p p = ҐТ ҐТ - = ; l, k = 1, N; u,v = 1,M .В каждом из N узлов находится единственный прибор, который может работать в rl - 1 режимах, l = 1, N . Дисциплина обслуживания - LCFS PR (заявка, поступающая в l-й узел, вытесняет заявку с прибора и начинает обслуживаться, а вытесненная заявка становится первой в очереди на обслуживание). Таким образом, поступающие в узел заявки имеют абсолютный приоритет. Нумерация заявокв очереди на каждый узел осуществляется от конца очереди к прибору.Состояние сети в момент времени t характеризуется вектором x(t) = (x1(t), x2(t), , xN(t)), где состояние l-го узла в момент времени t описывается векторомxl(t) = (xl (t), jl (t)) = (xl1(t), xl2(t), , xl,n(l)(t), jl(t)), xl1(t) - тип заявки, стоящей последней в очереди на обслуживание в l-м узле в момент времени t и т.д., xl,n(l)-1(t) -тип заявки, стоящей первой в очереди на облуживание в l-м узле в момент времени t, xl,n(l)(t) - тип заявки, находящейся на облуживании в l-м узле в момент времени t, jl(t) - режим, в котором работает l-й узел в момент времени t, n(l) - общееколичество заявок в l-м узле. Тогда процесс x(t) имеет пространство состоянийX = X1  X2  XN, где Xl = {(0, jl), (xl1, jl), (xl1, xl2, jl), (xl1, xl2, xl3, jl), : xlk= 1,M , k = 1, 2, ; jl = 0, rl }.В качестве основного режима работы обслуживающего прибора полагаетсярежим работы 0. Переход возможен только на соседние режимы.Время пребывания в основном режиме работы имеет показательное распределение с параметром Ґнl (xl ,0) , после чего прибор переходит в режим 1. Для состояний xl, у которых 1 ≤ jl ≤ rl -1, время пребывания в режиме jl также имеет показательное распределение, при этом с интенсивностью ƒl(xl) прибор l-го узла переходит в jl -1 режим, а с интенсивностью ƒl(xl) - в jl - 1 режим. Время пребывания в последнем rl-м режиме имеет показательное распределение с параметромϕl (xl , rl ) , после чего прибор переходит в режим rl -1. Во время переключенияприбора с одного режима на другой число заявок в узле не меняется.Для упрощения записи введём в рассмотрение операторы: Tu (xl ) Tu (xl1,..., xl,n(l) ) (xl1,..., xl,n(l) ,u), - = - T (xl ) T (xl1,..., xl,n(l) ) (xl1,..., xl,n(l) 1), − −= = −T(l,u) (x) T(l,u) (x1,..., xN ) (z1, , zN ), - = - = где zk = xk при k ЎБ l, ( ( ), ) zl Tu xl jl = - , Tl (x) Tl (x1,..., xN ) (z1, , zN ), − = − = где zk = xk при k ЎБ l, ( ( ), ) zl T xl jl = − , Инвариантность стационарного распределения вероятностей состояний сетей 351 1( ) ( 1,..., ) ( 1, , ), jl jl Rl x Rl x xN z zN - = - = где zk = xk при k ЎБ l, ( , 1) zl = xl jl - , 1 1( ) ( 1,..., ) ( 1, , ) jl jl Rl x Rl x xN z zN − = − = , где zk = xk при k ЎБ l, ( , 1) zl = xl jl − .Если в момент времени t состояние l-го узла представляет собой вектор(xl , jl ) и сразу после указанного момента в этот узел поступает заявка u-го типа, которая начинает немедленно обслуживаться, то количество работы по её обслуживанию является случайной величиной Ґзl (Tu- (xl )) с функцией распределенияBl (Tu- (xl ), z) и математическим ожиданием Ґуl (Tu- (xl )) < ЎД , Bl (Tu- (xl ),0) = 0.Если в момент времени t состояние l-го узла есть вектор (xl , jl ) , то обслуживание ведётся со скоростью Ґбl (xl , jl ), то есть зависит от состояния узла.Переход прибора из режима обслуживания 0 в режим обслуживания 1 можнотрактовать как частичную потерю работоспособности прибора, влекущую уменьшение скорости обслуживания с Ґбl (xl , 0) на Ґбl (xl , 1) .Полагаем, что матрица (p(l,u)(k,v)), u,v = 1,M , l, k = 0, N , p(0,u)(0,v)=0, неприводима. Тогда уравнение трафика0( , ) ( , )( , )1 1, 1, ; 1, , N M lu l u kv k v l u k v p p l N u M = Ґе = -ҐТ ҐТҐе = = (1)имеет единственное положительное решение Ґеlu , l = 1, N; u = 1,M.Через ƒlk(t) обозначим количество работы, которое осталось выполнить с момента t до завершения обслуживания заявки, стоящей в момент времени t на k-йпозиции в l-м узле, ƒl(t) = (ƒl1(t), ƒl2(t), , ƒlN(t)), (l = 1, N). Из вышесказанногоследует, что , 1 2( )l k ( , , , , ).l l l lk l d t x x x j dt Ґч= −Ґб В общем случае процесс x(t) не является марковским, поэтому рассмотрим кусочно-линейный марковский процесс ƒ(t) = (x(t), ƒ(t)), добавляя к x(t) непрерывную компоненту ƒ(t) = (ƒ1(t), ƒ2(t), , ƒN(t)).Под {P(x), x Ўф X} будем понимать стационарное распределение вероятностейсостояний процесса x(t).ФункцииF(x, y) = F(x, y11, y12 , y1,n(1) ; y21, y22 , ..., y2,n(2) ; ...; yN1, yN2 ,..., yN,n(N) ) tlim { ( ) ; l1( ) l1, l2 ( ) l2 ;...; l,n(l) ( ) l,n(l) , 1, }.Pxt x t y t y t y l N ЎжЎД= = Ґч < Ґч < Ґч < будем называть стационарными функциями распределения вероятностей состояний кусочно-линейного процесса ƒ(t).2. Марковский случайВ [3] рассмотрен случай, когда Bl(xl, z)=1 - exp{- Ґм l(xl)z} (z > 0) с единичнойскоростью обслуживания Ґбl(xl) = 1, то есть Bl(xl, z) является функцией экспоненциально распределенного времени обслуживания. Тогда x(t) - марковский про36 Ю.В. Малинковский, А.Н. Старовойтов, А.Р. Ереминацесс с непрерывным временем. В указанной работе показано, что при выполненииусловий( , 1) Ґнl xl jl − Ґмl (xl , jl )ϕl (T − (xl ), jl ) = Ґнl (T − (xl ), jl −1)Ґмl ( xl , jl −1)ϕl (xl , jl ), (2)l = 1, N, jl = 1, rl , для xl,n(l) , n(l) ЎГ 1, ( )( ) , 1 1 1 2 1(0, 1)( ) , ( , ,..., , ) (0, )llsN n l j n l l x l x X l s l l l ls l k l k q x Ўф = = x x x j = k ⎡ Ґе Ґн − ⎤⎢Ґл ⎥ < ЎД ⎣ Ґм ϕ ⎦ҐТ ҐР ҐР ҐР (3)где ( 1 )1( ) ( , ) ( , ) ( , )Nl l l l l l l l l l q x − x j x j x j = Ґл -ҐТ Ґм - Ґн - ϕ , процесс x(t) эргодичен, а его стационарное распределение имеет мультипликативную формуP(x) = p1(x1) p2 (x2 )Ўї...Ўї pN (xN ), где ( )( ) , 1 1 2 1(0, 1)( , ) (0,0), ( , ,..., , ) (0, )llsn l j n l l x l l l l l s l l l ls l k l k p x j p = x x x j = k Ґе Ґн −= Ґл Ґм ϕ ҐР ҐР Ґеl,xls находятся из (1), а 1, 0 0 1 1 2 1(0, 1)(0,0)( , ,..., , ) (0, )llsr i j i l x l l i j s l l l ls k l k px x x j k ЎД −= = = ⎛ Ґе Ґн − ⎞= ⎜⎜ Ґл ⎟⎟ ⎝ Ґм ϕ ⎠ҐТ ҐТ ҐР ҐР .2. Основной результатЛемма. Если (Ґеlu , l = 1, N; u = 1,M) является решением уравнения трафика (1), то справедливо следующее равенство: ( , )01 11.N M kv k v k v p = ҐТ ҐТҐе = (4)Доказательство. Просуммируем уравнение трафика (1) по u, затем по l и поменяем в правой части порядок суммирования: 0( , ) ( , )( , )1 1 1 1 1 1 1 1, N M N M N M N M lu l u kv k v l u l u l u l u k v p p = = = = = = = ҐТҐТҐе =ҐТҐТ -ҐТҐТҐТ ҐТҐе ( , )( , )1 1 1 1 1 11 , N M N M N M lu kv k v l u l u k v l u p = = = = = ҐТҐТҐе = -ҐТҐТҐе ҐТ ҐТ ( , )01 1 1 11 (1 ).N M N M lu kv k v l u k v p = = = ҐТҐТҐе = -ҐТҐТҐе −Вычитая из обеих частей1 1N M lu l= uҐТҐТҐе , получим равенство (4), которое являетсяобобщением следствия уравнения трафика для классической сети Джексона на случай многих типов заявок. Лемма доказана.Инвариантность стационарного распределения вероятностей состояний сетей 37Для описанных выше открытых сетей, в случае, когда количество работы по обслуживанию поступившей в узел заявки имеет произвольную функцию распределения Bl (xl , z) , имеет местоТеорема. Процесс ƒ(t) эргодичен, если выполняются соотношенияҐнl (xl , jl −1)Ґбl (xl , jl )ϕl (T − (xl ), jl ) = Ґнl (T − (xl ), jl −1)Ґбl ( xl , jl −1)ϕl (xl , jl ), (5)l = 1, N, jl = 1, rl , для xl,n(l) , n(l) ЎГ 1; ( ) ( )( ) 1 2, 1 1 1 1 1 2(0, 1) ( , ,..., )( ) , (0, ) ( , ,..., , )llsN n l j n l n l l l l l ls l x x X l s k l s l l l ls l k x x x q x Ўф = = = k = x x x j ⎡ Ґн − Ґу ⎤⎢Ґл Ґе ⎥ < ЎД ⎣ ϕ Ґб ⎦ҐТ ҐР ҐР ҐР ҐР (6)где ( 1 )1( ) ( ) ( , ) ( , ) ( , )Nl l l l l l l l l l l l q x − x x j x j x j = Ґл -ҐТ Ґу ⋅Ґб - Ґн - ϕ .При этом стационарные функции распределения вероятностей состоянийF(x, y) определяются по формулам( )( ) , 11 2 1 21 1 0( , ) ( ) ( , ,..., ) 1 ( , ,..., , )N n l yl s l l l l l ls l l l ls l s F x y p x − x x x B x x x u du = =ҐР ҐРҐу Ўт − , (7)где( ) ( )( ) 1 2, 1 1 1 1 2(0, 1) ( , ,..., )( , ) (0,0); (0, ) ( , ,..., , )llsn l j n l n l l l l l ls l l l lx l s k l s l l l ls l k x x x p x j p = = k = x x x j Ґн − Ґу = Ґл Ґе ϕ Ґб ҐР ҐР ҐР (8)Ґеl,xls находятся из (1), а ( ) 11 2, 0 0 1 1 1 1 2(0, 1) ( , ,..., )(0,0)(0, ) ( , ,..., , )llsr i j n l i l l l l ls l lx i j s k l s l l l ls k x x x p k xx x j ЎД −= = = = ⎛ Ґн − Ґу ⎞= ⎜⎜ Ґл Ґе ⎟⎟ ⎝ ϕ Ґб ⎠ҐТ ҐТ ҐР ҐР ҐР . (9)Доказательство. Пусть выполнены условия (2), (3), то есть в случае, когдаx(t) - марковский процесс, существует стационарное эргодическое распределениеx(t). Тогда и в общем случае при выполнении условий (5), (6) существует стационарное эргодическое распределение процесса ƒ(t), так как ƒ(t) получается из x(t)добавлением непрерывных компонент, а Ґмl−1(xl , jl ) = Ґуl (xl )Ґбl−1(xl , jl ) . Строгое доказательство этого факта может быть проведено, если учесть, что процесс ƒ(t) является регенерирующим. Действительно, функционирование сети схематичноможно представить как чередование периодов, когда сеть находится в состоянии«0» (в каждом узле сети нет заявок и прибор работает в нулевом режиме), и периодов занятости сети (в противном случае). Далее доказательство сводится к применению предельной теоремы Смита для регенерирующих процессов [4, с.41].Для F(x, y) справедлива следующая система дифференциально-разностныхуравнений: ( )1( , ) ( , ) ( , )Nl l l l l l l v x j x j F x y ⎛ ⎞⎜Ґл - - ϕ ⎟ ⎝ ⎠ҐТ, ( )1 , ( ) , ( ) 0( , ) ( , ) ( , )l n l N l l l l l n l l n l y x j F x y F x y = y y ⎛ ЎУ ⎛ ЎУ ⎞ ⎞ = Ґб ⎜ − ⎜ ⎟ ⎟ - ⎜ ЎУ ⎜ ЎУ ⎟ ⎟ ⎝ ⎝ ⎠ ⎠ҐТ38 Ю.В. Малинковский, А.Н. Старовойтов, А.Р. Еремина, ( ) 1( , )( , )01 1 , ( ) 1 0( (), )( ( ), )l n l N M l u l u l l lu l u l n l y F T x y T x j p y = = - ⎛ ЎУ ⎞- Ґб ⎜⎜ ⎟⎟ - ⎝ ЎУ ⎠ҐТҐТ0( , , ( ) ) , ( )1( , ) ( ( ), ) l n l N l x l l l n l l l p B x y F T − x y -ҐлҐТ , ( ), ( ) 1( , )( , )( , ) , ( )1 1, 1 , ( ) 1 0( ( ()), )( u ( , ) l n l ( , )s n s N N M s u l s s s sulx l l lnl l s s l u s n s y F T T x y T x j p B x y y - −= = ЎБ = - ⎛ ЎУ ⎞- Ґб ⎜⎜ ⎟⎟ - ⎝ ЎУ ⎠ҐТ ҐТ ҐТ , ( ), ( )( , )( , )( , ) , ( )1 1 , ( ) 0( ( ()), )( ( ( )), ) ( , ) l n l l n l N M l u l l u l l lu lx l l lnl l u l n l y F T T x y T T x j p B x y y - −- −= = ⎛ ЎУ ⎞- Ґб ⎜⎜ ⎟⎟ - ⎝ ЎУ ⎠ҐТҐТ11( , 1) ( l ( ), )Njl l l l l v x j F R − x y -ҐТ − - 11( , 1) ( l ( ), ), N jl l l l l x j F R - x y x X ҐТϕ - Ўф . (10)В полученных уравнениях предполагается, что если аргумент функции F(x,y)не принадлежит фазовому пространству, то есть x ∉ X, то F(x,y)=0.Разобьем данную систему на уравнения локального баланса следующим образом: , ( ) 1( , )( , )01 1 , ( ) 1 0( (), )( , ) ( ( ), )l n l N M l u l u l l lu l u l n l y F T x y F x y T x j p y = = - ⎛ ЎУ ⎞Ґл = Ґб ⎜⎜ ⎟⎟ ⎝ ЎУ ⎠ҐТҐТ , , ( )1 , ( ) 0 , ( )( , ) ( , ) ( , )l n l N l l l l l n l y l n l x j F x y F x y = y = y ⎛ ⎛ ЎУ ⎞ ЎУ ⎞ Ґб ⎜ ⎜ ⎟ − ⎟ = ⎜ ⎜ ЎУ ⎟ ЎУ ⎟ ⎝ ⎝ ⎠ ⎠ҐТ0( , , ( ) ) ( , , ( ) ) ( ( ), ) p l xl n l Bl xl yl n l F Tl x y = Ґл − , ( ), ( ) 1( , )( , )( , ) , ( )1, 1 , ( ) 1 0( ( ( )), )( u ( , ) l n l ( , )s n s N M s u l s s s sulx l l lnl s s l u s n s y F T T x y T x j p B x y y - −= ЎБ = - ⎛ ЎУ ⎞- Ґб ⎜⎜ ⎟⎟ - ⎝ ЎУ ⎠ҐТ ҐТ , ( ), ( )( , )( , )( , ) , ( )1 , ( ) 0( ( ( )), )( ( ( )), ) ( , ) l n l l n l M l u l l u l l lu lx l l lnl u l n l y F T T x y T T x j p B x y y - −- −= ⎛ ЎУ ⎞- Ґб ⎜⎜ ⎟⎟ ⎝ ЎУ ⎠ҐТ ; (12)( )1 1( , ) ( , ) ( , )( , 1) ( l ( ), ) ( , 1) ( l ( ), )l l l l l l j j l l l l l l l l v x j x j F x y v x j F R − x y x j F R - x y - ϕ = − -ϕ - . (13)Покажем, что функции распределения вероятностей F(x,y), определенныеформулами (7) - (9), являются решением уравнений (11) - (13), а следовательно, удовлетворяют системе уравнений (10). Действительно, подставляя (7) в (11), деляобе части полученного соотношения на ҐлF(x,y), получим следствие уравнениятрафика (4). Подставляя -----(7) в (12), приводя подобные слагаемые, получим уравИнвариантность стационарного распределения вероятностей состояний сетей 39нение трафика (1). И, наконец, подставляя (7) в (13) и учитывая (5), получим тождество. Теорема доказана.Из доказанной теоремы с учётом равенства P(x)=F(x,-ЎД) вытекает следующееутверждение.Следствие. Если выполняются соотношения (5), (6), то процесс x(t) эргодичен, а его стационарное распределение {P(x), xЎфX} не зависит от функционального вида распределения Bl (xl , z) и имеет вид P(x) = p1(x1) p2 (x2 )Ўї...Ўї pN (xN ), где pl(xl) находятся по формулам (8), (9).ЗаключениеВ настоящей работе установлена независимость стационарного распределениявероятностей состояний открытых сетей с многорежимными стратегиями обслуживания и заявками разных типов от вида законов распределения величин работ, требующихся на обслуживание заявок в узлах, когда дисциплиной обслуживанияявляется LCFS PR (абсолютный приоритет поступающего требования с дообслуживанием). При этом показано, что стационарное распределение сети имеет форму произведения, где каждый множитель - стационарное распределение изолированного узла, помещенного в фиктивную окружающую среду с пуассоновскимпотоком. Этот результат является обобщением работы [3], а именно, снимаетсяограничение на экспоненциально распределенное время обслуживания заявки в узле. Следует отметить, что для описанной сети естественным образом возникаетзадача установления инвариантности стационарного распределения относительнофункции распределения времени пребывания прибора в различных режимах, а также - задача исследования стационарного распределения сети, когда и времяобслуживания, и время пребывания прибора в режимах имеют произвольные распределения.

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