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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА
2011 Управление, вычислительная техника и информатика № 4(17)
УДК 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 & lt- ]1 & lt- г I — 1 время пребывания в режиме ]1 также имеет произвольную функцию распределения Ф {, и), при этом с вероятностью
V ()
V (іі) + Фі (Іі) Фі(Іі)
прибор 1-го узла переходит в режим Jl + 1, ас вероятностью
— в режим Jl — 1. Время пребывания в последнем г гм режиме имеет
V (Іі) + Ф (Іі)
произвольную функцию распределения Фі (г, й), после чего прибор переходит в режим г і - 1. Во время переключения прибора с одного режима на другой число заявок в узле не меняется.
При этом
ад
V-1 (0) = |(1 -Фі(0,и))(їй- (1)
0
ад
((і)+Фі(і))-1 = {(-фі(і, й)))1 ^ і ^ г-1- (2)
фЛ
1(г) = 1(1 -Фі (г, й))й. (3)
0
Длительности обслуживания заявок в узлах не зависят от процесса поступления, друг от друга и от длительностей пребывания приборов в режимах и имеют произвольную функцию распределения Б1 (X, й) для і-го узла, зависящую от очереди заявок X в узле, причём
ад
Ь 1 (Хі1, X2 ,…, X, п (і)) = К1 — (((1, X2 ,…, X, п (і), й))їй. (4)
0
Будем предполагать, что матрица (Р (ійх^)), й, V = 1, М, і, к = 0, Ж,
Р (0,й)(0^) = 0, неприводима.
Тогда уравнение трафика
ж м ____ ____
Єій = Р0(і, й) +ZSЄkvР (k, v)(l, u), і = 1 Ж й = 1 м, (5)
к=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) & lt- y^.^ V/," (/)(t) & lt- У/,"(/), l =1, N-
?l, jl (t)(t) & lt- Z1, jl,… ,^N, jN (t)(t) & lt- 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, v)0 = 1 (6)
k=1 v=1
Подробное доказательство леммы приведено в [2].
В [5] был рассмотрен случай, когда длительности обслуживания заявок в узлах и длительности пребывания в режимах имеют показательное
распределение, т. е. для /-го узла (x/, и) = 1 -exp-i (x/1,xt2,…, xln (l))u} (И & gt- 0) и
Ф/ (ji, И) = 1 — exp{-(v/ (j/) + ф/ (j/))u} (u & gt- 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 (/) & gt- 1,
и неравенства
n (/) e/, xw Av (0, k -1)& quot-
(7)
Z ^(x)n
xeX / =1
r (/) П--------------------------------------------------П
w=1 I/ (xn, xl 2 ,…, x/w, jl) k=1 Ф/ (0, k)
& lt- OO,
N
где #(х) = Х + н1 (х-, Л) + V-(х1, Л) + Ф-(х-, Л)),
г=1
марковский процесс х (/) эргодичен, а его стационарное распределение имеет мультипликативную форму
Р (х) = ^)р2(х2) X … X рм (хм),
где
п (,)
Р1(х1, л) = хп (Х) П
х".
(0,0),
1 ц, (xn, х, 2,…, х,№, Л) к=1 Ф,(0, к)
е, х, находятся из (5), а
Р- (0,0) =
о г г
УУхг П-..
V г =0 ] =0 «=1 -, (xn, х12 ,…, х,№, ]) к=1 Ф, (0, к)
П V,(0, к 1)
V
Для рассматриваемой в статье модели в силу того, что ц, (х, Л г) = ц, (х,), V, (х, Л I) = V, (]1), ф, (х{, ]1) = ф, (]1), условие обратимости (7) выполняется автоматически. Поэтому остается потребовать, чтобы выполнялось условие эргодичности
N (п (,)
I Ч (х)П Хп (,)П-((к)
хеХ ,=1 V «=1 -, (Xn, х, 2 ,…, хЫ) к=1 Ф, (к)
^ V, (к -1)
Л
П
& lt- оо.
(8)
Тогда стационарное распределение имеет мультипликативную форму Р (х) = Р1(^)Р2 (х2) X … X РN (XN).
При этом
Р1 (х, Л) =
(п (,)
X п (Х) П-
г!^vl (к -1)
П
Рх (0,0),
где
V «=1 -, (xl1, х, 2 ,…, х,№) к=1 Ф, (к)
N ____ ____
д (х) = Х + 1(ц-1(х) + !& gt-, О,) +фО,)), а (е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-, Л
ПП-(xll, х,2,…, хы) { (1-Б (xl1,хы, й))П®,(л) I (-Ф (1,й)) (9)
,=1 И=1
,=1
где
Р1(х, л) =
(п (,)
Xп (,)П
П (к -1)
1 -, (xl1, х, 2, & quot-^ х,№) к=1 Ф, (к)
Рх (0,0),
(10)
находятся из (5), а
Рг (0,0) =
?? Хг П-------------^Л
Iг=0}=о «=1 Мг (xn, хг2,•••, хг^)к=1 Фг (к) ,
хе X, 1 = 1, г.
(11)
Доказательство. В случае, когда х (/) — марковский процесс, существует его стационарное эргодическое распределение. Тогда и в общем случае при выполнении условия (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,, п (і ч) Ві (Х1, уі, п (і))
ГдЕ (Г (+, и)(Т, — (X)), У, г) Л
ду
5, П (5)+1
У5, П (5) + 1
N М
+ММ Р (і,
,=1 и =1

и)(і, X, п (і))В (Хі, уі, п (і)) N V, (І -1)
ГдЕ (Г (+, и)(Т}- (X)), у, 2) Л
дУі,
п (і)
У Уі, п (і) =0
і=1 «і (і -1) N Фі(І +1)
Фі (Іі, 2і, І)
(дЕ (ЛІ -1(X), У, 2) Л
V
ьМ
м ^ (і І +1)
Фі (1, 2і, І)
д2і
дЕ (Л1 +'-(X), у, 2)
і, Л-1 У
п. іі +1,.ч. _чЛ

52-
X є X.
/2
Разобъем эту систему уравнений на уравнения локального баланса:
N М
ХЕ (X, у, 2) = мм Р (і, и)0
і=1 и=1
(дЕ (Т (+и)(X), У, 2) Л
дУі
п (і)+1
(12)
(13)
Уі, п (і)+1 —
(дЕ (X, у, 2) Л V дуі, п (і) У
дЕ (X, у, 2)
N М
+ М М Р (.
5=1,5ФІ и =1
М
+Мр (і,
и =1
уі, п (і) =0
5, и X, п (і))
дуі, п (і)
Ві (X, уі, п (і))
= ^Роу,^^ (і)) ві(X, Уі, п (і))Е (ТІ(x), У, 2) +
ГдЕ (Т (+, и)(Т1- (X)), у, 2) Л
дУ
5, п (5)+1
'-ХЛ X, п (і)) (
дЕ (X, у, 2)
ґдЕ (Т (+и)(Т — (X)), у, 2) Л
дуі, п (і)
дЕ (X, у, 2)
У5, п (5) + 1
У Уі, п (і) =0
(14)
І У
2і,і =0
д2& gt-
V (Іі -1) ^і (І і -1)
| Фі(І +1) «і (І і +1)
Фі (І, 2і, І)
^ дЕ (Л/'--1(X), у, 2) Л
д2
і, І -1
Чі-1 =0
Фі (І, 2і, І)
дЕ (ЛЛ+1 (X), у, 2)
д2-
(15)
, Іі+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 г.

ПоказатьСвернуть
Заполнить форму текущей работой