Invariance of the stationary distribution of queuing networks with multimode strategies and negative demands.pdf Сети массового обслуживания используются в качестве адекватных моделей производственных и транспортно-логистических сетей, сетей связи и передачи данных, информационных и компьютерных сетей. Сети джексоновского типа с отрицательными заявками (так называемые «G-сети») были впервые рассмотрены Э. Геленбе в [1, 2]. В них наряду с обычными, «положительными» заявками в сеть поступают «отрицательные» заявки, которые не требуют обслуживания и ведут себя как сигналы (отрицательная заявка уменьшает количество положительных заявок в узле на одну и не оказывает никакого влияния на узел, если в нем нет положительных заявок). Э. Геленбе установил, что для таких сетей стационарное распределение также имеет форму произведения, а уравнение трафика (нелинейное) имеет единственное положительное решение. После этого многими авторами рассматривались различные обобщения G-сетей. В частности, в [3-5] исследовались сети с многорежимными стратегиями, отрицательными заявками и информационными сигналами. В этих работах полагалось, что длительности обслуживания заявок и времена пребывания приборов в режимах имеют показательные распределения. Однако в сетевых моделях, описывающих реальные объекты в экономике, финансах, технике и т.п., указанные распределения чаще всего отличаются от показательного. Так, например, любые технические средства в силу естественного износа или нарушения условий эксплуатации могут полностью прекращать функционирование, требовать ремонта (замены) или продолжать работать с меньшей производительностью. Поэтому большую важность для практических приложений представляет изучение сетей массового обслуживания с многорежимными стратегиями, в которых обслуживающие приборы в узлах могут работать в нескольких режимах, соответствующих различной производительности. Подобные сети позволяют моделировать ситуации, когда обслуживающие приборы частично надёжны, что особенно актуально для реальных сетей, в которых любые технические средства в силу физического износа, нарушения условий эксплуатации и т.д. могут выходить из строя полностью или частично, работая при этом с различной производительностью. Стандартный случайный процесс, описывающий такие сети, не является марковским, что затрудняет их исследование и нахождение стационарного распределения. В [6] была исследована сеть, в которой некоторые узлы доступны для отрицательных заявок и длительности обслуживания имеют показательное распределение, а оставшиеся узлы недоступны для отрицательных заявок и длительности обслуживания имеют произвольную функцию распределения. Была доказана инвариантность стационарного распределения вероятностей состояний указанной сети по отношению к функциям распределения длительностей обслуживания заявок в узлах, недоступных для отрицательных заявок. В [7] рассматривалась сеть с многорежимным обслуживанием и отрицательными заявками одного типа, когда обслуживание имело временную интерпретацию (т.е. скорость обслуживания равна 1). Была установлена инвариантность стационарного распределения относительно функций распределения величин работ, требующихся для переключения режимов функционирования приборов в узлах при фиксированных математических ожиданиях. В данной статье результат, полученный в [7], распространен на случай, когда в сеть с многорежимным обслуживанием поступают положительные и отрицательные заявки различных типов. 1. Описание сети Рассматривается открытая сеть массового обслуживания, состоящая из N однолинейных узлов, в которую поступают два независимых простейших потока положительных и отрицательных заявок с интенсивностями А+ и АГ соответственно. Каждая заявка входного потока положительных заявок независимо от других заявок направляется в 1-й узел и становится заявкой типа u, u = 1,M , с вероятностью N M p0j(i u) (££ Po(lu) = 1). Каждая заявка входного потока отрицательных заявок независимо от других l =1 u =1 NM заявок направляется в l-й узел и становится заявкой типа u с вероятностью рГ(1 u) (££ РГ(1 u) = 1). Отl =1 u =1 рицательная заявка типа u, поступающая в узел сети, обслуживания не требует. Она уменьшает число заявок типа u в этом узле на единицу, если в очереди данного узла есть заявки типа u, и не оказывает никакого влияния на состояние узла в противном случае. После обслуживания в l-м узле положительная заявка типа u независимо от других заявок мгновенно с вероятностью р+ u)(k v) направляется в k-й узел как положительная заявка типа v, с вероятностью Р(Г u)(k v) направляется в k-й узел как отрицательная заявка типа v, а с вероятностью P(l,u)0 покида- N M _ ет сеть (£ £(р+,u)(k,v) + Р(Г,u)(k,v))+P(i,u)o =1; h k =1, N; u v =1,M). Заявки в узлах обслуживаются согласно дисциплине LCFS PR (заявка, поступающая в l-й узел, вытесняет заявку с прибора и начинает обслуживаться, а вытесненная заявка становится первой в очереди на обслуживание). Таким образом, поступающие в узел заявки имеют абсолютный приоритет. Время обслуживания заявки типа u, находящейся в l-м узле, имеет показательное распределение с параметром ц lu . В каждом из N узлов находится единственный прибор, который может работать в rt +1 режимах 0, 1,..., r , l = 1N . Состояние сети в момент времени t характеризуется вектором x(t) = (x1 (t), x2 (t),..., xN (t)), где состояние l-го узла в момент времени t описывается вектором xl (t) = (xl (t), jl (t)) = = (xl1(t), xt2(t),..., xln(l)(t), j(t)); xl1(t) - тип заявки, стоящей последней в очереди на обслуживание в l-м узле в момент времени t; xl 2 (t) - тип заявки, стоящей предпоследней в очереди на обслуживание в l-м узле в момент времени t и т.д.; xl пц)r1(t) - тип заявки, стоящей первой в очереди на облуживание в l-м узле в момент времени t; xl n(l) (t) - тип заявки, находящейся на облуживании в l-м узле в момент времени t; j (t) - режим, в котором работает l-й узел в момент времени t. Процесс x(t) обладает пространством состояний X = X1 X X2 X ... X XN, где Xi ={(0, jiX ^ ji), (xll,ji), (xll,xi2,xlз,ji),...: xk =1,M,k = 1,2,...; ji = ^r}. В качестве основного режима работы обслуживающего прибора полагается режим работы 0. Переключение происходит только на соседние режимы. Во время переключения прибора с одного режима на другой число заявок в узле не меняется. Количество работы, необходимое для переключения прибора l-го узла из основного режима работы в режим 1, является случайной величиной с произвольной функцией распределения Ф , (0, u) и математическим ожиданием ^ (0). При этом если в момент времени t в узле находится n(l) заявок (состояние узла (xl, jl)), то указанная работа выполняется со скоростью v l (xl ,0). Для состояний х1, у которых 1 < jl < rl - 1, количество работы, необходимое для изменения режима jj, также является случайной величиной с произвольной функцией распределения Ф l (jt, u) и математическим ожиданием ^ (jt). Если в момент времени t состояние узла (Xt, jt), то выполнение работы происходит со скоростью v l (Xj) + ф1 (Xj), при этом с вероятностью-V1 ()- прибор l-го узла переходит в режим jl + 1, а с V i (Xt) + Ф1 (xt) Ф1 (xi) вероятностью- прибор l-го узла переходит в режим j, - 1. V i (Xt) + Ф1 (xt) Аналогично количество работы, необходимое для выхода прибора l-го узла из режима работы rl в rl - 1, имеет произвольную функцию распределения Фl (rl, u) и математическое ожидание % (rl). При этом если в момент времени t состояние узла (Xl, j,), то указанная работа выполняется со скоростью Ф1 (xl, rl). Математические ожидания всех вышеперечисленных случайных величин конечны, т.е. (jl) 0, l = 1, N. Через у(t)(t) обозначается количество работы, которое осталось выполнить с момента t для переключения режима обслуживания на соседний режим в l-м узле, если обслуживающий прибор работает в режиме ji, y(t) = (y1,j1W(t),y2,j1(t)(t),...,yN,jN(t) (t)). В силу вышесказанного d У/, it )(t) (xi)j,,,) +Ф1 (xi )I (j,, o)). dt В общем случае процесс x(t) не является марковским, поэтому рассматривается кусочно-линейный марковский процесс C,(t) = (x(t), y(t)), полученный добавлением к x(t) непрерывной компоненты y(t). Под P = {P(x)} понимается стационарное распределение вероятностей состояний процесса x(t), P( x) = lim P{x(t) = x}. t Ia> Функции F(x,z) = F(x, z1,j1,z 2,j2,..., Z n , jN) = = liIm P { = x; ^U (t) < Zj (t) < Z2,j ; ...; VnJk (t) < ZN j } называются стационарными функциями распределения вероятностей состояний кусочно-линейного марковского процесса ^(t). 2. Марковский случай Пусть длительности пребывания в режимах имеют показательное распределение, т.е. для 1-го узла Ф, (xt, ~) = 1 - exp{-(v, (xj, j)) + ф, (xj, j,))~}, (~ > 0). Тогда x(t) - однородный марковский процесс с непрерывным временем и не более чем счётным фазовым пространством состояний X = X1XX2X...Xxn, где Xi ={(0, j,X (xll,j,X (xi^xi2,j,X ...:xm =1 M->k = 1,2,...; j, = 0ri}. В [8] установлено, что при выполнении условий V) (xi, ji - 1)Ф) (Т- (X)), jt) = V) (Г- (x), jt - 1)ф, (X), jt), (3) п(1) ^ п X=1 + k -1 ((1, k) a ./1 П (1, xk ) £ qx п xeX 1=1 (4) 0, jl = 0, rl, l = 1, N. + n(l) 1-П: (1, Xfc ) (8) p i (0,0) = Л(0) Для F (х, z) справедлива следующая система разностно-дифференциальных уравнений: Л (9) F(х,Z) = lu 1 =1 u=1 J Л Л N = 1^1 (X,, ji ) df ( x, z) dzH, df ( x, z) ~z + + 1=1 1, j J zi,k =0 J N M ZZ^luP(l,u)0F(T(J,u)(х), z) 1=1 u=1 N 1+ ZP0+(i,xi,n(1))F(T, (X),z) +XEP-(1 ,u)F(T(+,u)(X),z) + + l =1 NM 1=1 u =1 N N M + E Z Z^ xuP(+x,u )(l, X,n (, ))J 1=1 S=1,5*l u =1 NM 1 =1 u =1 N N M M +Z Z ZZ^ Su P(s,u)(l ,v)J F (T,;,„(Tr (X)), z) + ZZ ц 1«P(+,u)(l, x;,n(l))F (T(+,u )(T1 ( х)) z) + F (T(+,B)(T(+,v)( X)), z) + N M M +£££ц /u p(i ,u)(i ,v)F (T(+,u) (T(+,v)(x)xz)+ 'dF (Rj -1( x), z) 1 =1 u =1 v=1 \ N + £ vl (xl , jl - 1)Ф 1 U , zl,n, + /=1 N _ / + £ф/(x,, j/ + 1)Ф 1 (, z,, /=1 ji+1 dz, 'l,j)-1 -1=0 'dF (Rj +1( x), z) Л , x e X. dz,, +1 =0 Для данных уравнений предполагается, что если аргумент функции F (x, z) не принадлежит фазовому пространству, т.е. если x й X, то F(x, z) = 0. Полученная система разбивается на уравнения локального баланса следующим образом: NM А+ +А- +££ц) F (x, z) = (10) V NM 1=1 u=1 у = ££ ЦluP(lu )0 F(T(+,u ) (x), z) + u) NM 1=1 u=1 + А+ £ P0+(i,x/,n))F(T/- (x), z) + А- ££ p-(i,u)F(T(+,u) (x), z) + l =1 1=1 u =1 N N M +£ £ ЯР(+ 1 =1 X=1,5,1 u =1 NM + 1 =1 u=1 N N M M + £ £ £ £ Ц xu P(-X,u)(l,v)F(T(+,u) (T(+,v) (x)), z) + 1 =1 X=1,x, 1 u =1 v=1 N M M +£££ Ц lup(l ,u )(/,v) F (T(+,u)(T(+,v)( x)), z), 1 =1 u=1 v=1 ( S,u)(l,xhn))F(T(+,u)(ТГ (x)), z) + ££ц iup(i ,i (1 ,u )(/, x; ,n (i)) F (T(1 ,u )(T1 ( x)), z) + dF (x, z) "dz dF (x, z) dz, л (xi, j/ ) (11) 1, j Jzi.n =0 у (- ■ 1)Ф ( ■ ) dF(Rjl-1(x), z) = vl (xl, jl - 1)Ф Aj/, zl,j' J -7- ' \ dzl,j/-1 / { dF (Rj+1( x), z) + ф, (x,, jt + 1)Фj (, zU]i ) 1 h } ' \ dz', (i +1 + Jzij -1 =0 Л +1=0 Функции распределения вероятностей F(x, z), определённые формулами (6)-(8), являются решениями уравнений (10)-(11), а следовательно, и уравнений (9). Действительно, подставим (6) в (10), приведём подобные слагаемые и, учитывая уравнения трафика (1)-(2), получим тождество. Подставляя (6) в (11) и учитывая (3), также получим тождество. Теорема доказана. Из теоремы с учётом равенства P( x) = F (x,+) имеем: Следствие. Если выполняются соотношения (3)-(4), то процесс x(t) эргодичен, а его стационарное распределение {{(x), x e X } не зависит от функционального вида распределения Ф, (j), u ) и имеет вид P(x) = Р1 (x1)Р2 (x2) X ... X Pn (Xn ), где p, (x,) определяются по формулам (7)-(8). Заключение В настоящей работе установлены условия независимости стационарного распределения вероятностей состояний открытых сетей с многорежимными стратегиями обслуживания, положительными и отрицательными заявками разных типов от вида законов распределения величин работ, требующихся для переключения режимов функционирования приборов в узлах, когда дисциплиной обслуживания является LCFS PR (абсолютный приоритет поступающего требования с дообслуживанием). При этом установлено, что стационарное распределение сети имеет форму произведения.

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