Автоматика и телемеханика, № 9, 2008
РАСЗ 02.50.-r
© 2008 г. Р. МАНДЗО, Н. КАСКОНЕ
(Университет Салерно, Италия), Р.В. РАЗУМЧИК (Российский университет дружбы народов, Москва)
ЭКСПОНЕНЦИАЛЬНАЯ СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ И БУНКЕРОМ ДЛЯ ВЫТЕСНЕННЫХ ЗАЯВОК1
Рассматривается система массового обслуживания, в которую поступают пуассоповские потоки положительных и отрицательных заявок. Для положительных заявок имеется накопитель неограниченной емкости. Отрицательная заявка, поступающая в систему, выбивает положительную заявку из очереди в накопителе и перемещает ее в накопитель (неограниченной емкости) для вытесненных заявок, или бункер. Если накопитель пуст, отрицательная заявка покидает систему, не оказывая на нее никакого воздействия. После окончания обслуживания очередной заявки на прибор поступает заявка из накопителя или, если накопитель пуст, из бункера. Длительности обслуживания заявок как из накопителя, так и из бункера имеют экспоненциальное распределение с одним и тем же параметром. Получены соотношения, позволяющие вычислять стационарные распределения очередей в накопителе и бункере.
1. Введение
Появление понятия отрицательных заявок связано с работой Е. Геленбе [1]. В этой работе была рассмотрена однолинейная система массового обслуживания (СМО) неограниченной емкости, в которую, помимо основного потока обычных (положительных) заявок, поступает дополнительный поток отрицательных заявок. Отличие отрицательной заявки от положительной состоит в том, что при поступлении в систему она уничтожает положительную заявку, если таковая имеется.
В дальнейшем стали появляться и появляются до настоящего времени работы, посвященные изучению как систем, так и сетей массового обслуживания с отрицательными заявками. Подробный обзор публикаций вплоть до 2003 г. приведен в 1^1'
В настоящей работе рассматривается несколько отличная от предложенных ранее постановок задач. Исследуется система Ы/Ы/1/ж с дополнительным бункером и потоком отрицательных заявок. Предполагается, что отрицательная заявка в момент поступления в систему не убивает, а вытесняет одну из положительных заявок из очереди в накопителе и помещает ее в бункер. Вытесненные заявки обслуживаются с относительным приоритетом. Прерывание обслуживания не допускается.
2. Описание системы
Рассмотрим однолинейную СМО, в которую поступает пуассоновский поток заявок интенсивности А. Заявки этого потока в дальнейшем будем называть положи-
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 06-07-89056).
тельными. Для положительных заявок имеется накопитель положительных заявок (далее просто накопитель) неограниченной емкости.
Помимо положительных заявок, в систему поступает пуассоновский поток отри-цате л ьных заявок интенсивности А . Отрицательная заявка, поступающая в систему, вытесняет одну (положительную) заявку из накопителя и перемещает ее в накопитель для вытесненных заявок, или бункер, который также имеет неограниченную емкость. Если в момент поступления отрицательной заявки в накопителе нет положительных заявок, а на приборе обслуживается заявка, то отрицательная заявка, не прерывая обслуживание на приборе, покидает систему, не оказывая на нее никакого воздействия. То же самое происходит и в случае, когда в момент поступления отрицательной заявки накопитель и обслуживающий прибор пусты.
Выбор ЗАЯВОК На обслуживание производится следующим образом. После окончания обслуживания очередной заявки на прибор становится заявка из накопителя. Если же накопитель пуст, на прибор поступает заявка из бункера. Обслуживание заявок не прерывается новыми как положительными, так и отрицательными заявками.
Длительности обслуживания заявок как из накопителя, так и из бункера имеют экспоненциальное распределение с одним и тем же параметром у.
Поскольку период занятости для данной системы совпадает с периодом занятости СМО Ы/Ы/1/<х>, то необходимым и достаточным условием существования стационарного режима функционирования является условие р = А/у, < 1. Это уело-вие всюду в дальнейшем будем предполагать выполненным.
Заметим также, что стационарное распределение вероятностей состояний рассматриваемой СМО не зависит от дисциплины выбора на обслуживание заявок из накопителя и бункера, если дисциплина относится к классу консервативных дисциплин без прерывания обслуживания.
3. Система уравнений равновесия
Обозначим через V(Ь) общее число заявок, находящихся в накопителе и на обслуживающем приборе в момент времени Ь, а через ц(Ь) — число заявок в бункере. Положим X(Ь) = (V(Ь), п(£))- Случайный процесс {X(Ь), Ь > 0}, описывающий стохастическое поведение рассматриваемой СМО во времени, является марковским процессом с непрерывным временем и дискретным (счетным) множеством состояний. Множество состояний процесса {X (Ь), Ь > 0} имеет вид
X = {(к,т), т > 0, к > и(т)},
где и(х) - функция Хевисайда. Состояние (к, т) процесса {X(Ь), Ь > 0} означает, что в момент времени Ь в накопителе и та приборе находятся к заявок, а в бункере т
Обозначим через ркт стационарную вероятность состояния (к,т). Стационарное распределение процесса {X(Ь), Ь > 0} существует и удовлетворяет следующей системе уравнений равновесия (СУР):
(1) 0 = — Ароо + урю,
(2) 0 = —(А + у)рю + Ароо + ур20 + урн,
(3) 0 = —(А + у + А-)рко + Арк-!,о + урк+1,о, к > 2,
(4) 0 = —(А + у)р1т + А-р2)ТО-1 + ур2т + Ур1,т+1, т > 1,
(5) 0 = —(А + у + А-)ркт + А-рк+1,т-1 + урк + 1,т + Арк-1,т, к > 2, т > 1,
с условием нормировки
оо оо
(6) poo + Ркт = 1
k=1 m=0
4. Стационарное распределение общего числа заявок в системе
Пусть {pn, n > 0} - стационарное распределение общего числа заявок в системе, включая заявки, находящиеся в накопителе, на приборе и в бункере, т.е.
Pn Pkm, n > 0.
k+m=n
При k + m = 0и k + m = 1 из уравнений (1) и (2) имеем
(7) 0 = -Apo + MPI,
(8) 0 = -(A + M)Pi + Apo + MP2.
В случае k + m = n n > 2, суммируя (3) при k = n, (4) при m = n — 1 и (5) при k + m = n, после несложных выкладок получаем
(9) 0 = —(A + M)pn + Apn-i + Mpn+1, n > 2.
Уравнения (7)-(9) представляют собой СУР для системы M/M/1/те с пуассо-
A
параметром M без учета отрицательных заявок. Следовательно, стационарное распределение общего числа заявок в исходной СМО с отрицательными заявками совпадает со стационарным распределением числа заявок в обычной СМО M/M/1/те, т.е. является геометрическим:
pn = pnpo, n > 0,
где р = A/M - загрузка системы, а
po = poo = 1 — р.
Физический смысл полученного результата очевиден, поскольку с точки зрения общего числа заявок в системе рассматриваемая СМО ничем не отличается от СМО M/M/1/те.
5. Стационарные распределения, связанные с числом заявок в накопителе
В этом разделе будут получены формулы для вычисления некоторых стационарных распределений, связанных с числом заявок в накопителе и на приборе. Достоинством этих формул является простота их использования при реальных вычислениях.
Найдем сначала стационарные вероятности того, что в накопителе и на приборе находится в сумме к, к > 0, заявок и бункер пуст. Для этой цели введем производящую функцию (ПФ)
Ркогк, 0 < г < 1.
к=0
Умножая уравнения (1)-(3) на zk и суммируя то всем значениям к, имеем
0 = (-(Л + у + Л-) + | + Az) Po(z) + Р00 (м + А- - + (А-Р10 + mi)z, откуда получаем
/1Пч (М - + A-)z) - (A-pio + MPii)z2
(10 p0(z) = -^-тг--—т--:-poo.
Az2 — (Л + у + Л )z + у
Знаменатель выражения в правой части (10) представляет собой К В а ДР el l Н ЫЙ трехчлен относительно z. Корни zi 2 уравнения
Az2 — (Л + у + A-)z + у = 0 имеют вид
zi,2 =
Л + у + Л- ± Vх(Л + у + Л-)2 — 4Лу 2A '
Нетрудно убедиться, что zl > 1 и 0 <z2 < 1. № непрерывност и ПФ Ро(^) на отрезке 0 < z < 1 следует, что корень z2 должен являться не только нулем знаменателя, но и нулем числителя дроби в равенстве (10), что дает следующее соотношение:
(11) А-рю + МР11 = Р00(м - (м + А-^).
z2
Подставляя выражение для А-р10 + м-Рп из (11) в (10) и сокращая числитель и знаменатель на общий множитель ^ — z2), получаем с учетом выведенного ранее
равенства р00 = 1 — р окончательное выражение для ПФ Р0^): = (1 — р)--•
В частности, стационарная вероятность р^0 того, что бункер пуст, имеет вид
"-0 = р0<1> = <1 — р) аМ—^—Т) •
здесь и далее
обозначается суммирование по всем возможным значениям дискретного аргумента.
ПФ Р0^) позволяет выписать явное выражение для вероятностей рк0:
Рк0 = (1 — Р) ( Л + — — М + А ) ( Л — и(1 — к)
\ Z2 м
Формулы для стационарных вероятностей ркто, к > 0 т > Т того, что в накопителе и на приборе находится в сумме к, а в бункере еще т заявок, можно найти, используя полученные в следующем разделе выражения для двойной ПФ. Однако эти выражения будут гораздо более трудоемкими для численных расчетов.
Определим теперь стационарное распределение общего числа заявок в накопителе и на приборе. С этой целью введем ПФ
Як М=£ РктZm, к > 0, 0 < Z < 1.
т=0
При k = 0 имеем
(12) Qo(z)= Poo = 1 - p.
При k = 1 из уравнений (2) и (4), проводя обычные преобразования для ПФ, получаем следующее соотношение:
п , Л ^(А + m)z - м^ MP10 - Azpoo
Q2(Z) = (,(м + А-z)J Q1(Z) + (м + A-z)z •
Отсюда, полагая z = 1, имеем
Q2(1) = qQl(1),
или
(13) p2,. = qP1,., где q = А/(м + А-).
Наконец, при k > 2 из уравнений (4) и (5), опуская элементарные выкладки для ПФ, находим
Qfc+i(z)= А + М +_'А Qk(z)--А - Qfc-i(z), k > 2.
М + Az м + Az
Подставляя сюда z = 1 и полагая последовательно k = 2,3,..., имеем Qk (1)= qk-1Ql(1), k > 3,
или
(14) pk. = qk-1p1,., k > 3.
Для нахождения p1,. воспользуемся условием нормировки (6) и соотношениями (13), (14). В результате получаем равенство
poo + P1.Y, qk-1 = 1, k=1
откуда следует, что
(15) P1,. = (1 - poo)(1 - q).
Из (11)-(15) окончательно находим:
Po,. = Poo = 1 - p,
(16) Pk. = p(1 - q)qk-1, k > 1.
Таким образом, получено явное выражение для стационарного распределения общего числа заявок в накопителе и на приборе, являющееся, по сути (т.е. за исключением вероятности po,.), геометрическим.
Из (16), в частности, следует, что среднее число Mv и диспер
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.