Об инвариантности стационарного распределения вероятностей состояний открытой сети с многорежимными стратегиями обслуживания и разнотипными заявками

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2011 Управление, вычислительная техника и информатика № 4

УДК 519.21

А.Р. Ерёмина, Ю.В. Малинковский

ОБ ИНВАРИАНТНОСТИ СТАЦИОНАРНОГО РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ ОТКРЫТОЙ СЕТИ С МНОГОРЕЖИМНЫМИ СТРАТЕГИЯМИ ОБСЛУЖИВАНИЯ И РАЗНОТИПНЫМИ ЗАЯВКАМИ

Рассматривается открытая сеть массового обслуживания с многорежимными стратегиями и разнотипными заявками. Входной поток - простейший. Количество работы по обслуживанию заявок и количество работы по переключению прибора с одного режима на другой имеет произвольное распределение. Процессы обслуживания заявок и переключения режимов приборов не зависят друг от друга. Установлена инвариантность стационарного распределения вероятностей состояний сети по отношению к функциональной форме распределений величин работ, требующихся на обслуживание заявок и переключение режимов приборов.

Ключевые слова: сеть массового обслуживания, многорежимные стратегии, стационарное распределение, инвариантность.

Сети массового обслуживания достаточно адекватно описывают функционирование многих реальных объектов в области информационно-вычислительных и логистических систем. Аналитические результаты теории сетей массового обслуживания используются при проектировании новых производственных линий, заправочных станций, планировании графика работы общественного транспорта и т.д., когда реальных объектов не существует или когда эмпирические данные получить довольно трудно и дорого.

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

Сети с разнотипными заявками и многорежимным обслуживанием, когда количество работы по обслуживанию поступающих в узел заявок имеет произвольную функцию распределения, были исследованы в [2]. Для указанных сетей была установлена инвариантность стационарного распределения вероятностей состояний относительно функционального вида распределения количества работы, необходимого для обслуживания требований.

Сети с немедленным обслуживанием заявок (дисциплина ЬСБ8 РЯ) и многорежимным обслуживанием, когда количество работы по обслуживанию поступающих в узел заявок и количество работы по переключению прибора с одного режима на другой являются случайными величинами с произвольной функцией

распределения, были исследованы в [3, 4]. Для указанных сетей была установлена инвариантность стационарного распределения вероятностей состояний относительно функционального вида распределения количества работы, необходимого для обслуживания поступающих заявок и переключения режимов работы обслуживающих приборов. Данные результаты были получены для случая, когда в сети циркулируют требования одного типа.

Однако на практике чаще встречаются сети, в которые поступают требования различных типов. Поэтому в настоящей работе были исследованы аналогичные сети с разнотипными заявками, а результаты, полученные в [3], обобщены для неоднородных сетей.

1. Постановка задачи

Рассматривается открытая сеть массового обслуживания, состоящая из N однолинейных узлов, в которой циркулируют заявки М типов. Поступающий поток заявок - простейший с интенсивностью X. Каждая заявка входного потока независимо от других заявок с вероятностью p0(lu) направляется в l-й узел и становится

____ ____ N M

заявкой типа u (l = 1, N; u = 1, M; Po(l u) = 1). После обслуживания в l-м узле

I=1 u =1

заявка u-го типа мгновенно и независимо от других заявок с вероятностью P(l,u)(k,v) направляется в k-й узел и становится заявкой типа v, а с вероятностью P(l,u)o поки___________________ ____ N M

дает сеть (hk = 1N; u,v = lM; XXP(l,u)(k,v) + P(l,u)o =1).

k=1 v=1

В каждом из N узлов находится единственный прибор, который может работать в rl + 1 режимах: 0, 1, ..., rl (l = 1,N). По истечении времени пребывания в

режиме прибор переходит в другой режим мгновенно.

Дисциплина обслуживания заявок прибором - LCFS PR. Заявка, поступающая в узел, вытесняет заявку с прибора и начинает обслуживаться, а вытесненная заявка становится в начало очереди на обслуживание, сдвигая стоящие в ней заявки. При повторном поступлении на прибор заявка продолжает дообслуживаться оставшееся время в режиме, в котором работал прибор на момент указанного поступления. Таким образом, поступающая в узел заявка имеет абсолютный приоритет перед всеми остальными заявками, находящимися в узле. Нумерация заявок в очереди на каждый узел осуществляется от конца очереди к прибору.

Состояние сети в момент времени t характеризуется вектором x(t) = (x1(t), x2(t), ., xN(t)), где состояние l-го узла в момент времени t есть вектор xl(t) = (xt (t), j (t)) = = (xl1(t), xl2(t), ..., xln(l)(t), j(t)), xl1(t) - тип заявки, стоящей последней в очереди на обслуживание в l-м узле в момент времени t, xl2(t) - тип заявки, стоящей предпоследней в очереди на обслуживание в l-м узле в момент времени t и т.д., xln(l)-1(t) -тип заявки, стоящей первой в очереди на облуживание в l-м узле в момент времени t, xln(l)(t) - тип заявки, находящейся на облуживании в l-м узле в момент времени t, jl(t) - номер режима, в котором работает прибор в l-м узле в момент времени t, n(l) - общее количество заявок в l-м узле. Тогда процесс x(t) обладает не более чем счетным фазовым пространством состояний X = X1 x X2 x . x XN, где Xl = {(0,jl), (xn,jl), (xn, xl2,jl), ...: xlk = 1,M , k = 1, 2, ...; j =0,rt }.

В качестве основного режима работы обслуживающего прибора полагается режим работы 0. Переключение происходит только на соседние режимы.

Время пребывания в основном (нулевом) режиме работы имеет произвольную функцию распределения Ф { (0,и), после чего прибор переходит в режим 1. Для состояния х, у которого 1 < ]1 < г I - 1 время пребывания в режиме ]1 также имеет произвольную функцию распределения Ф {, и), при этом с вероятностью

V

V

прибор 1-го узла переходит в режим Jl + 1, ас вероятностью

- в режим Jl - 1. Время пребывания в последнем г гм режиме имеет

V

произвольную функцию распределения Фі (г,й), после чего прибор переходит в режим г і - 1. Во время переключения прибора с одного режима на другой число заявок в узле не меняется.

При этом

ад

V-1

0

ад

фЛ

1

0

Длительности обслуживания заявок в узлах не зависят от процесса поступления, друг от друга и от длительностей пребывания приборов в режимах и имеют произвольную функцию распределения Б1 (X, й) для і-го узла, зависящую от очереди заявок X в узле, причём

ад

Ь 1

0

Будем предполагать, что матрица (Р(ійх^)), й,V = 1,М, і, к = 0,Ж,

Р(0,й )(0^) = 0, неприводима.

Тогда уравнение трафика

ж м ____ ____

Єій = Р0

к=1 v=1

имеет единственное положительное решение (єій; і = 1, Ж, и = 1, м).

Пусть уік(ґ) - остаточное время обслуживания с момента ґ до момента завершения обслуживания заявки, стоящей в момент времени ґ на к-й позиции в і-м узле, уі(ґ) = (уп(ґ), уЕ(ґ), ..., у іМІ)(ґ)), (і = 1,Ж). Пусть ^(ґ) - остаточное время

пребывания прибора -го узла в режиме І с момента ґ до перехода в соседний режим §(ґ) = §2,^2(^)(ґ),...,^ж,;ж(о(ґ)). Таким обPaзом,

ад

d^9f^ ^ = 11 (Xn’Х2’^’Xlk^ dt = ((()(л*Г;) + Ф(j)/(л^0)^

когда состояние /-го узла есть (xn, x/2, ..., x^, j).

В общем случае процесс x(t) не является марковским, поэтому рассмотрим кусочно-линейный марковский процесс Z(t) = (x(t), y(t), ^(t)), полученный путем добавления к x(t) непрерывных компонент y(t) = (^1 (t), y2(t), ., y^(t)) и £(t).

Под {P(x), x e X} будем понимать стационарное распределение вероятностей состояний процесса x(t).

Введем в рассмотрение стационарные функции распределения вероятностей состояний кусочно-линейного процесса Z(t):

f (x, ^, z) = f (x, Уll, y^... yi,„(i);...; yN 2,..., ,n( n );...; zn , ;N) =

= ijm P {x(t) = x; yn(t) < y^..^ V/,„ (/)(t) < У/,„(/), l =1, N;

£l,jl(t)(t) < Z1,jl,...,^N,jN(t)(t) < ZN,jN } .

Обозначим 3/ (j/ ) = V{ (j/ )/(j * r/) +Ф/ (j/ )/(]i ^ l = 1 N, j/ = 0, Г/.

2. Основной результат

Лемма. Если e/u (/ = 1, N; и = 1,M) является решением уравнения трафика (5), то справедливо следующее равенство:

N M

ZZSkvP

k=1 v=1

Подробное доказательство леммы приведено в [2].

В [5] был рассмотрен случай, когда длительности обслуживания заявок в узлах и длительности пребывания в режимах имеют показательное

распределение, т.е. для /-го узла (x/,и) = 1 -exp-i(x/1,xt2,...,xln(l))u} (И > 0) и

Ф/ (ji,И) = 1 - exp{-(v/ (j/) + ф/ (j/))u} (u > 0). Тогда x(t) - однородный марковский процесс с непрерывным временем и не более чем счетным фазовым пространством состояний X = X1 х X2 х ... х XN, где X/ = {(0, j), (x/1, j/), (x/1, x/2, j), ...:

x/k= 1,M , k = 1, 2, ...;j/ =0,r, }.

Установлено, что при выполнении условий

v/(x/, ji -1)I/(x/, ji)Ф/ (Г“(ЦХ],) = V/CT (Х/X j/ -1)|/(X/, j/ -1)ф/(X/, j/

/ = Щ j = й/', n(/) > 1,

и неравенства

n(/) e/,xw Av (0, k -1)"

Z ^( x)n

xeX / =1

r(/) П-----------------------------------------------—--П

w=1 I/

< OO,

N

где #( х) = Х + н ^1 (х;, Л) + V;(х1, Л) + Ф;(х;, Л)),

г=1

марковский процесс х(/) эргодичен, а его стационарное распределение имеет мультипликативную форму

Р(х) = ^)р2(х2) X ... X рм (хм ),

где

п

Р1(х1 , л) = хп(Х) П

х».

(0,0),

1 ц,

е, х, находятся из (5), а

Р- (0,0) =

о г г

УУхг П— . .

V г =0 ] =0 «=1 -,

П V,

V

Для рассматриваемой в статье модели в силу того, что ц, (х,, Л г) = ц, (х,), V, (х,, Л I) = V, (]1), ф, (х{, ]1) = ф, (]1), условие обратимости (7) выполняется автоматически. Поэтому остается потребовать, чтобы выполнялось условие эргодичности

N

I Ч

хеХ ,=1 V «=1 -,

^ V,

Л

П

< оо.

Тогда стационарное распределение имеет мультипликативную форму Р(х) = Р1(^)Р2 (х2) X ... X РN (XN).

При этом

Р1 (х,, Л ) =

X п(Х) П-

г!^vl

П

Рх (0,0),

где

V «=1 -,

N ____ ____

д(х) = Х + 1(ц-1(х) + !>,О,) +фО,)), а (е1и; / = 1 N, м = 1,М) -

положитель-

=1

ное решение уравнения трафика (5).

Пусть длительность обслуживания заявки прибором /-го узла имеет произвольную функцию распределения Б1 (х1, й), а время пребывания прибора /-го узла в режиме ] 1 - Ф, (, й), причем математические ожидания фиксированы с помощью равенств (1) - (4).

Основной результат формулируется следующим образом.

Справедлива следующая теорема.

Теорема. Процесс £(0 эргодичен, если выполняются соотношения (8). При этом стационарные функции распределения вероятностей состояний Р(х, у, 2) определяются по формулам

Р (х, у, 2) = Р1( х1) Р2 (х2) X ... X РN (XN ) X

N п(,) у,,» N 2;,Л

ПП-

,=1 И=1

,=1

где

Р1(х,, л) =

Xп(,)П

П

1 -,

Рх (0,0),

находятся из (5), а

Рг (0,0) =

£ £ Хг П-------------^Л

Iг=0}=о «=1 Мг(xn,хг2,•••,хг^)к=1 Фг(к) ,

хе X, 1 = 1, г.

Доказательство. В случае, когда х(/) - марковский процесс, существует его стационарное эргодическое распределение. Тогда и в общем случае при выполнении условия (8) существует стационарное эргодическое распределение процесса £(/), так как £(/) получается из х(/) добавлением непрерывных компонент. Строгое доказательство этого факта может быть проведено, если учесть, что процесс £(0 является регенерирующим. Действительно, функционирование сети схематично можно представить как чередование периодов, когда сеть находится в состоянии «0» (в каждом узле сети нет заявок и прибор работает в нулевом режиме), и периодов занятости сети (в противном случае). Далее доказательство сводится к применению предельной теоремы Смита для регенерирующих процессов [6, с.41], при этом учитывается, что среднее время пребывания прибора в режиме равно такое же, как и в марковском случае.

Для упрощения записи введём в рассмотрение операторы:

Ти (хг) = ти(xn,•••,хг,п(г)) = (xn,•••,х1

п,п

и),

Т (хг) = Т (хп,...,хг п(г)) = (хп,...,хг,п(г)_1),

Т(+,и)(х) = Т(+,и)(xl,•••,хг) = ^г^.^хгX где хк = хк при к*I х1 = (Ти (хгXЛX (х) = Т[ (х1,...,хг) = (X,...,хы), где 5ск = хк при к * I, х, = (Т“(х,), ),

Я/1 +1(х) = Я1]1+1(х1,..., хг) = (х^..., хг), где хк = хк при к * I, х1 = (х,, ]1 +1),

Я/1 _1(х) = Я/1 _1(х1,...,хг) = (^,...,хг), где хк = хк при к* I, х1 = (х,,]1 _ 1),

, = 1,г, и = 1М •

Тогда для Е(х, у, г) справедлива следующая система дифференциально -разностных уравнений:

+

ХЕ (х, у, г) = £

г=1

дЕ

дУг,

п

дЕ

дУг

г ,п (г) У

г

+£

г=1

дЕ (х, у, г) дг,

дЕ (х, у, г) дг,

уг,п(г) =0 У

Л

+

г

+Х£ Р0(г,хг,п(г))В1(хг, у,,п(г))Е(Тг (x), У, г) +

г=1

г М

+££ Ру,

г=1 и=1

и )0

(дЕ (Т(+и)(х), у, г)Л

дуг,

п (г )+1

уг, п( г )+1 -

N N М

+М I Мр

і=1 5=1,5фі и =1

5 ,и )

ГдЕ (Г(+,и )(Т,- (X)), У, г) Л

ду

5, П ( 5 )+1

У5, П(5) + 1

N М

+ММ Р(і,

,=1 и =1

+м

и)

ГдЕ (Г(+,и )(Т}- (X)), у, 2)Л

дУі,

п

У Уі, п(і) =0

і=1 »і

Фі

( дЕ (ЛІ -1( X), У, 2)Л

V

ьМ

м ^

Фі

д2і

дЕ

і, Л-1 У

п.іі +1,..ч .. _чЛ

\

52;

X є X.

/2

Разобъем эту систему уравнений на уравнения локального баланса:

N М

ХЕ (X, у, 2) = мм Р(і,и )0

і=1 и=1

(дЕ(Т(+и)(X), У, 2) Л

дУі

п(і)+1

Уі, п (і)+1 -

( дЕ (X, у, 2)Л V дуі ,п(і) У

дЕ

N М

+ М М Р(.

5=1,5ФІ и =1

М

+Мр(і,

и =1

уі, п(і) =0

5 ,и X, п

дуі ,п

Ві

= ^Роу,^^ (і)) ві(X, Уі ,п(і))Е (ТІ(x), У, 2) +

ГдЕ (Т(+,и )(Т1- (X)), у, 2) Л

дУ

5, п( 5 )+1

'ХЛ X ,п(і)) (

дЕ

ґдЕ (Т(+и )(Т - (X)), у, 2)Л

дуі ,п

дЕ

У5, п(5) + 1

У Уі ,п(і) =0

І У

2і,і =0

д2>

V

Фі

^ дЕ (Л/'-1( X), у, 2)Л

д2

і, І -1

Чі-1 =0

Фі

дЕ

д2;

, Іі+1 =0

Покажем, что функции распределения вероятностей Е(х, у, г), определенные формулами (9) - (11), являются решением уравнений (13) - (15), а следовательно, и (12).

Подставим (9) в (13) и разделим обе части полученного соотношения на ХЕ(х, у, г). Получим следствие уравнения трафика (6).

Подставим (9) в (14), приведём подобные слагаемые и разделим обе части полученного соотношения на ХВг(х{,у 1п(Г))Е(Т[(х),у,г). Получим уравнение трафика (5).

Наконец, подставим (9) в (15). Получим тождество.

Теорема доказана полностью.

Из теоремы с учетом равенства P(x) = F(x, -+», -+») вытекает следующее утверждение.

Следствие. Если выполняются соотношения (8), то процесс x(t) эргодичен, а его стационарное распределение {P(x), xeX) не зависит от функционального вида распределений Б{(x{,it), Ф{(k,it) и имеет вид

P( x) = Pi( xi) p2( x2) X... X pN (xN), где p(x) определяются по формулам (10) - (11).

Заключение

Исследованы открытые сети массового обслуживания, в которых циркулируют заявки разных типов, а приборы в узлах могут работать в нескольких режимах. Дисциплиной обслуживания заявок является LCFS PR. Определён вид стационарных функций распределения, плотности распределения и установлены условия инвариантности стационарного распределения вероятностей состояний указанных сетей относительно вида законов распределения величин работ по обслуживанию поступающих заявок и переключению режимов приборов в узлах при фиксированных первых моментах этих законов.

ЛИТЕРАТУРА

1. Малинковский Ю.В., Нуеман А.Ю. Мультипликативность стационарного распределения в открытых сетях с многорежимными стратегиями обслуживания // Весщ НАН Беларуси 2001. № 3. С. 129-134.

2. Малинковский Ю.В., Старовойтов А.Н., Ерёмина А.Р. Инвариантность стационарного распределения вероятностей состояний сетей с многорежимными стратегиями обслуживания, разнотипными заявками и дисциплиной обслуживания LCFS PR // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2009. № 3(8). С. 33-39.

3. Старовойтов А.Н. Инвариантность стационарного распределения состояний открытой сети с многорежимными стратегиями обслуживания // Известия Гомельского государственного университета им. Ф. Скорины. 2005. № 5(32). С. 169-171.

4. Старовойтов А.Н. Об инвариантности стационарных распределений вероятностей состояний открытой сети с многорежимными стратегиями обслуживания // Известия Гомельского государственного университета им. Ф. Скорины. 2006. № 4(37). С. 159-161.

5. Летунович Ю.Е. Стационарное распределение состояний открытой неоднородной сети с многорежимными стратегиями и немедленным обслуживанием // Современные информационные компьютерные технологии: сб. науч. ст. Междунар. науч. конф., Гродно, 21

- 24 апреля 2008 г.: в 2 ч. / ГрГУ им. Я. Купалы; редкол.: Е.А. Ровба, А.М. Кадан (отв. редактор) [и др.]. Гродно, 2008. Ч. 2. С. 97-99.

6. Ивницкий В.А. Теория сетей массового обслуживания. М.: Физматлит, 2004. 772 с.

Ерёмина Александра Рафаэловна

Гродненский государственный университет им. Янки Купалы Малинковский Юрий Владимирович

Гомельский государственный университет им. Франциска Скорины

E-mail: aleksandrae@mail.ru; Malinkovsky@gsu.by Поступила в редакцию 31 мая 2011 г.