Автоматика и телемеханика, № 4, 2015
© 2015 г. Ю.В. МАЛИНКОВСКИЙ, д-р физ.-мат. наук (malinkovsky@gsu.by) (Гомельский государственный университет им. Ф. Скорины, Национальный исследовательский Томский государственный университет)
СЕТИ ДЖЕКСОНА С ОДНОЛИНЕЙНЫМИ УЗЛАМИ И ОГРАНИЧЕННЫМ ВРЕМЕНЕМ ПРЕБЫВАНИЯ ИЛИ ОЖИДАНИЯ
Рассматривается экспоненциальная сеть массового обслуживания с однолинейными узлами, отличающаяся от сети Джексона только тем, что время пребывания заявок (время ожидания заявками обслуживания) в узлах сети ограничено случайной величиной, имеющей показательное распределение. Заявки, обслуженные в узлах, и заявки, не завершившие обслуживание (не дождавшиеся обслуживания), движутся по сети в соответствии с разными матрицами маршрутизации. Доказывается теорема, обобщающая теорему Джексона для открытых и замкнутых сетей.
1. Введение
Системы массового обслуживания, в которых время ожидания или время пребывания заявок ограничено случайной величиной, имеющей показательное распределение, рассматривались в классической монографии Б.В. Гнеденко, И.Н. Коваленко [1], в которой кратко изложена история вопроса и приведена соответствующая библиография.
Эффективность практического использования сетей массового обслуживания связана с проблемой "узких мест" в сети, т.е. таких узлов сети, в которых загрузка имеет наибольшее значение. При очень большом числе заявок, циркулирующих в сети, в узком месте образуется бесконечная очередь, тогда как в других узлах очереди незначительны либо эти узлы вообще пустуют. Одним из способов преодоления указанного недостатка является введение мгновенных обходов [2], что позволяет более равномерно распределять нагрузку между узлами. Другим способом снижения нагрузки в "узких местах" является помещение в соответствующих узлах резервных приборов [3, 4]. Третьим способом уменьшения нагрузки в "узких местах" сети является введенное впервые Е.А. Ковалевым в [5] ограничение времен ожидания обслуживания заявок в узлах случайными величинами, имеющими показательное распределение. В [6, 7] исследовалось стационарное распределение вероятностей состояний открытых сетей с различными типами положительных, отрицательных заявок и сигналов и временами пребывания положительных заявок в узлах, ограниченными показательно распределенными случайными величинами. Найдено стационарное распределение в форме произведения множителей, характеризующих отдельные узлы в фиктивной окружающей среде. Неоднородные открытые сети с многорежимными стратегиями обслуживания и временами пребывания в режимах, ограниченными показательно распределенными случайными величинами, рассматривались в [8]. Для изоли-
3* 67
рованных узлов в фиктивной среде получены условия обратимости, при выполнении которых стационарное распределение вероятностей состояний сети имеет мультипликативную форму. Доказано, что выходящие из сети потоки заявок являются независимыми простейшими потоками. Наконец, в [9] исследовалась модель открытой сети с различными типами положительных, отрицательных заявок и многорежимными стратегиями обслуживания, в которых время пребывания в каждом узле отрицательных заявок ограничено случайной величиной, имеющей показательное распределение. Однако во всех работах [2-9] предполагалось, что заявки, обслуженные в узлах, и заявки, не дождавшиеся обслуживания, ведут себя одинаково, т.е. их движение по сети определяется одной и той же матрицей маршрутизации. В практических ситуациях, например, "недовольные клиенты", не дождавшиеся обслуживания, могут вообще покинуть сеть или как-то изменить свою маршрутизацию между узлами. Если матрица маршрутизации одна и та же для обслуженных заявок и заявок, не дождавшихся обслуживания, то уравнения Колмогорова и уравнения глобального равновесия оказываются точно такими же, как соответствующие уравнения для сети без ограничения на времена пребывания или ожидания, только с измененными интенсивностями обслуживания, к которым прибавляется некоторый параметр, связанный с параметром показательного распределения случайной величины, ограничивающей время ожидания или время пребывания. В связи с этим математическое решение задачи нахождения стационарного распределения тривиально и может быть выполнено чисто автоматически. В данной статье рассматривается случай различных матриц маршрутизации для обслуженных и "неудовлетворенных" заявок для сети с однолинейными узлами. Доказан аналог теоремы Джексона, в котором используется более сложное уравнение трафика, превращающееся в уравнение трафика для сети Джексона при совпадении упомянутых ранее матриц маршрутизации.
2. Открытые сети с ограниченным временем пребывания заявок в узлах
В сеть массового обслуживания, состоящую из N однолинейных узлов (систем), поступает стационарный пуассоновский поток заявок с интенсивностью Л. Каждая поступающая заявка независимо от других заявок с вероятностью рог направляется в г-й узел (г = Рог = !)• Число мест для ожидания заявок в узле бесконечное. Время обслуживания заявки единственным прибором г-го узла имеет показательное распределение с параметром ¡Лг (г = 1, ТУ). Время пребывания заявки в г-м узле ограничено случайной величиной, условное распределение которой (если в г-м узле находится щ заявок) показательное с параметром ^ (г = 1, ТУ). Другими словами, условная вероятность того, что пребывание каждой заявки в г-м узле закончится в промежутке времени [Ь,Ь + К), если в момент Ь в узле находилось щ заявок, равна + о(/г) при /г —> 0, а условная вероятность завершения пребывания хотя бы одной из этих заявок равна щЬ + о(К). Если заявка поступает в узел, свободный от заявок, она сразу начинает обслуживаться. Для определенности будем предполагать, что заявки обслуживаются в порядке поступления в узлы (дисциплина ГСРБ). Заявка, обслуженная в г-м узле,
мгновенно и независимо от других заявок с вероятностью pij направляется в j-й узел, а с вероятностью Piо покидает сеть (?', j = l,N, J2f=o Pij = 1)• Заявка, время пребывания которой в i-м узле закончилось, мгновенно и независимо от других заявок с вероятностью rij направляется в j-й узел, а с вероятностью 7'io покидает сеть (i,j = 1 ,N, J2f=o rij = !)• Для удобства введем еще узел 0, который отождествим с внешностью сети. Введем также следующие две стохастические квадратные матрицы порядка N + 1:
( о P01 P02 . . . P0N
P = P10 P11 Pl2 . . . P1 N
\PN 0 PN1 PN2 . . . PNN
о P01 P02 . . . P0N
R = r10 r11 r12 . . . r1N
rN0 rN1 rN2 . . . rNN
которые назовем матрицами маршрутизации соответственно обслуженных и "неудовлетворенных" заявок. Итак, роо = гоо = 0, то^ = ро] для остальных Очевидно, матрица Б = (з^, г,;) = 0, N), где для г ф 0
_ + ЩП] _ Vi
Vi + Vi
Vi + V
pij +
Vi + Vi
ij
а 80] = ро] также является стохастической, и по смыслу она управляет движением заявок по узлам 0,1,..., N без учета того, за счет чего (окончания обслуживания или окончания времени пребывания) заявка покидает узел. Будем называть эту матрицу матрицей маршрутизации. Заметим, что в отличие от сети Джексона, в которой матрица маршрутизации не зависит от г = 1, N, матрица маршрутизации ¿> зависит от щ, г = 1, N. Если положить Гго = 1, = 1, -/V, то "неудовлетворенные" заявки после обслуживания в узлах будут покидать сеть, а если положить р^о = 1, г = 1, А?", то, наоборот, покидать сеть будут обслуженные в узлах заявки.
Обозначим через Аь^ интенсивность потока заявок, выходящего из г-го узла (г = 1, Л^). Так как заявки не рождаются и не теряются при прохождении узлов, то в стационарном режиме с точностью до множителя А (на который можно сократить) выполняется следующий закон сохранения:
(1)
£j = P0j +
N
£i sij =
i=1
N
P0j + Х/
i=1
Vipij + Virij i I
Vi + Vi
j = 1, N.
Далее предполагается, что матрица Б неприводима. Для ее неприводимости достаточно (но не необходимо), чтобы неприводимой была хотя бы одна из матриц Р или К. Тогда уравнение (1), которое будем называть уравнением трафика, при фиксированных г = 1,N, будет иметь единственное положительное решение. Если изменять эти параметры, то решения (1) будут функциями от них. Заметим, что в сети Джексона решение уравнения трафика определяется матрицей Р и не зависит от параметров г =
Лемма 1. При выполнении (1)
N N
^ ^ ^гРгО +
, Ьг^гО — У £г-:- —
г=1
г=1
+ "г
Доказательство получается суммированием равенств (1) по j = 1, ./V и учетом
того, что £N=1 'РЧ] = 1 — РгО, N=1 г13 =1 — Гг0- Физический смысл СОСТОИТ В том, что (2), умноженное на Л, выражает равенство интенсивностей выходящего из сети и входящего в сеть потоков заявок.
Состояния сети в момент Ь будем описывать цепью Маркова с непрерывным временем п(Ь) = (п1(Ь),... ,nNгде пг(Ь) - число заявок в г-м узле в момент времени Ь. Пространство состояний этой цепи X = ZN, где Z+ = = {0,1,...}. В силу неприводимости матрицы маршрутизации и положительности интенсивностей выхода из состояний этой цепи в моменты ее скачков цепь п(£), очевидно, - неприводимая цепь Маркова. Назовем р^ = за-
грузкой г-го узла. Интуитивно понятно, что при выполнении условия
M¿+v¿
(3)
рг < 1, г = 1,х,
цепь Маркова п(Ь) является эргодической, что будет доказано позже. Пусть {р(п), п е X} - ее предельное эргодическое распределение, которое в этом случае будет единственным решением глобальных уравнений равновесия
(4)
р(п)
N
N
Л + — Ргг) + ^(1 — т))1^^}
г=1
N
£>(п — ег)Лр0г + ^ Р(п + вг)(^гРг 0 + »гП о) +
г=1
г=1 N N
+ ^ Р(п + ез — ег)(^'рИ + узrjг), п е X,
г=1 ] = 1,]=г
удовлетворяющим условию нормировки ^пех р(п) = 1. Здесь ег - единичный вектор г-го направления, 1д - индикатор события А, равный 1, если А происходит, и 0 в противном случае, причем предполагается, что р(п) = = 0 при п / X. Разобъем (4) на уравнения локального равновесия. Первое уравнение получается, если приравнять интенсивность потока вероятности из состояния п за счет поступления заявок в сеть извне интенсивности потока вероятности в состояние п за счет ухода заявок из сети:
N
(5)
Лр(п) = ^р(п + ег)(^грго + "¿По), п е X.
г=1
Остальные N уравнений локального равновесия получаются, если для каждого узла прира
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.