Автоматика и телемеханика, № 12, 2011
© 2011 г. А.В. ПЕЧИНКИН, д-р физ.-мат. наук, Р.В. РАЗУМЧИК (Институт проблем информатики РАН, Москва)
О ВРЕМЕННЫХ ХАРАКТЕРИСТИКАХ В ЭКСПОНЕНЦИАЛЬНОЙ СИСТЕМЕ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТРИЦАТЕЛЬНЫМИ ЗАЯВКАМИ И БУНКЕРОМ ДЛЯ ВЫТЕСНЕННЫХ ЗАЯВОК1
Рассматривается система массового обслуживания с пуассоновскими входящими потоками положительных и отрицательных заявок, бесконечным накопителем и экспоненциальным обслуживанием. Отрицательная заявка выбивает положительную заявку из очереди в накопителе и перемещает ее в бункер неограниченной емкости. Если накопитель пуст, то отрицательная заявка покидает систему, не оказывая на нее никакого воздействия. После окончания обслуживания очередной заявки на прибор поступает заявка из накопителя или, если накопитель пуст, из бункера. Для различных комбинаций порядков FIFO и LIFO выбора заявок на обслуживание из очереди в накопителе, выбора заявок на обслуживание из очереди в бункере и выбивания заявок из накопителя в бункер получены выражения для вычисления стационарного распределения времени ожидания начала обслуживания и других временных характеристик.
1. Введение
Хорошо известно, какую важную роль в современной теории массового обслуживания играют системы массового обслуживания (СМО) с отрицательными заявками, впервые введенные Е. Геленбе [1]. Многие ситуации, возникающие в современных телекоммуникационных системах (например, перебои в работе, потеря информации и т.д.), могут быть смоделированы с помощью систем и сетей массового обслуживания с отрицательными заявками.
В [2] была введена СМО с отрицательными заявками и бункером для вытесненных заявок, в которой в отличие от ранее изученных моделей выбитая из накопителя заявка также обслуживается, но только после окончания обслуживания всех невы-битых заявок. Для этой СМО были найдены стационарные распределения основных показателей функционирования, связанных с числом заявок в накопителе и бункере.
В настоящей статье, являющейся продолжением [2], найдено стационарное распределение времени ожидания начала обслуживания заявки в рассматриваемой СМО для 6 различных комбинаций порядков FIFO и LIFO выбора заявок на обслуживание из очереди в накопителе, выбора заявок на обслуживание из очереди в бункере и выбивания заявок из накопителя в бункер. Хотя, как и положено в силу формулы Литтла, среднее значение этой характеристики не зависит от порядков таких выборов, другие временные показатели функционирования будут различными. В конце статьи приводятся результаты численных расчетов по найденным формулам, показывающие зависимость дисперсии стационарного распределения времени ожидания начала обслуживания заявки от рассмотренных комбинаций порядков выбора и значений исходных параметров СМО.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект №11-07-00112).
2. Описание системы
Рассмотрим однолинейную СМО, в которую поступает пуассоновский поток заявок интенсивности Л. Заявки этого потока в дальнейшем будем называть положительными. Для положительных заявок имеется накопитель положительных заявок (далее просто накопитель) неограниченной емкости.
Помимо положительных заявок, в систему поступает пуассоновский поток отрицательных заявок интенсивности Л-. Отрицательная заявка, поступающая в систему, убивает, т.е. вытесняет из накопителя одну (положительную) заявку и перемещает ее в накопитель для вытесненных заявок, или бункер, который также имеет неограниченную емкость. Если в момент поступления отрицательной заявки в накопителе нет положительных заявок, а на приборе обслуживается заявка, то отрицательная заявка просто покидает систему, не оказывая на нее никакого воздействия. То же самое происходит и в том случае, когда в момент поступления отрицательной заявки накопитель пуст, а обслуживающий прибор свободен.
Выбор заявок на обслуживание производится следующим образом. После окончания обслуживания очередной заявки на прибор становится заявка из накопителя. Если же накопитель пуст, на прибор поступает заявка из бункера. Обслуживание заявок не прерывается новыми как положительными, так и отрицательными заявками.
Длительности обслуживания заявок как из накопителя, так и из бункера имеют экспоненциальное распределение с одним и тем же параметром ^.
Далее будем рассматривать следующие дисциплины выбора из накопителя и бункера на обслуживание и вытеснение из накопителя в бункер:
— при поступлении отрицательной заявки вытесняется первая заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается первая заявка из очереди в накопителе или, если накопитель пуст, последняя заявка из очереди в бункере (дисциплина FIRST-FIFO-LIFO);
— при поступлении отрицательной заявки вытесняется последняя заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается последняя заявка из очереди в накопителе или, если накопитель пуст, последняя заявка из очереди в бункере (дисциплина LAST-LIFO-LIFO);
— при поступлении отрицательной заявки вытесняется первая заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается первая заявка из очереди в накопителе или, если накопитель пуст, первая заявка из очереди в бункере (дисциплина FIRST-FIFO-FIFO);
— при поступлении отрицательной заявки вытесняется последняя заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается последняя заявка из очереди в накопителе или, если накопитель пуст, последняя заявка из очереди в бункере (дисциплина LAST-LIFO-FIFO);
— при поступлении отрицательной заявки вытесняется последняя заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается первая заявка из очереди в накопителе или, если накопитель пуст, последняя заявка из очереди в бункере (дисциплина LAST-FIFO-LIFO);
— при поступлении отрицательной заявки вытесняется первая заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается последняя заявка из очереди в накопителе или, если накопитель пуст, последняя заявка из очереди в бункере (дисциплина FIRST-LIFO-LIFO).
Цель настоящей статьи — найти при указанных дисциплинах стационарное распределение времени ожидания начала обслуживания заявки.
Поскольку период занятости данной системы совпадает с периодом занятости СМО M/M/1/то, то необходимым и достаточным условием существования стацио-
нарного режима функционирования является условие р = Л/р < 1. Это условие всюду в дальнейшем будем предполагать выполненным.
3. Вспомогательные результаты
Стационарное распределение вероятностей состояний рассматриваемой СМО не зависит от дисциплины выбора на обслуживание заявок из накопителя и бункера, если дисциплина относится к классу консервативных дисциплин без прерывания обслуживания. Поэтому далее будем пользоваться результатами работы [2]. В ней для дисциплины, при которой выбор заявки из накопителя и бункера на обслуживание и вытеснение из накопителя в бункер происходят в порядке поступления заявок в систему и в бункер, найдены следующие стационарные характеристики, связанные с числом заявок в системе:
— вероятностиpn, n ^ 0, того, что общее число заявок в системе (включая заявки, находящиеся в накопителе, на приборе и в бункере) будет равно n, имеющие вид
(1) Pn = (1 - p)pn, n > 0;
— вероятности pkm, m ^ 0, к ^ u(m) (здесь и далее u(x) — функция Хевисайда), того, что в накопителе и на приборе будет к заявок, а в бункере будет m заявок, представимые в терминах двойной производящей функции (ПФ) P(u,v) = poo +
w w
+ 2 S PkmUkvm в виде
k= 1 m=0
/ A u \
M
(2) P(u,v) = (1 -p) 2 I1
Xu^(u — ui) где
ui,2 =
\ + p + ± s/(X + p + )2 - 4X(p + X~v) 2Л
(напомним, что poo = Po = 1 — p);
— вероятности pk,. , k ^ 0, того, что в накопителе и на приборе будет к заявок, имеющие вид
1 — p, к = 0,
p(1 — q)qk-1, к > 1, q =
(3) = .„.-I А
M + A
Рассмотрим период занятости (ПЗ) системы Ы/Ы/1/<х с входящим потоком интенсивности Л и интенсивностью обслуживания Ь. Обозначим через 0(х; Ь) функцию
оо
распределения (ФР) ПЗ этой системы, а через 7(в; Ь) = / в-8ХйО(х; Ь) преобразова-
0
ние Лапласа-Стилтьеса (ПЛС) ФР С(х; Ь). Тогда (см., например, [3, с. 235])
, 8 + Х + Ь- ^(з + Х + Ь)2 -4А6 7(55 Ь) =-2А-'
Через 0(х, к; Ь) обозначим вероятность того, что ПЗ этой системы будет меньше х и на нем обслужится ровно к заявок. Двойное преобразование (ПЛС по х и ПФ по к)
то оо
7(в, г; Ь) = гк / в-8ХйО(х, к; Ь) задается формулой
к= 1 0
,, 8 + Х + Ь- у/(5 + Л + Ь)2 -4А;Ь
Ь) =-^-•
Наконец, через С*(х) обозначим ФР ПЗ СМО Ы/Ы/1/ж> с параметрами Л* = = Лр/(р + Л-) и р. Отметим, что С*(х) представляет собой также ФР ПЗ СМО Ы/Ы/1/<х с параметрами Л и р + Л-, открываемого заявкой экспоненциальной с параметром р длины. ПЛС ФР 0*(х) имеет вид
* < \ р 1 («) =
р + в + Л[1 - ^(в; р + Л )]
Далее через Иг(х; Ь) будем обозначать ФР Эрланга с параметром Ь и г фазами обслуживания, т.е.
' и(х), г = 0,
Х - -I
Щ(х; Ь)={ [ ЬЧ*-1 -Ыы 1 ^ Ькхк
-в
* М = 1 _ .
(г -1)! ^ к! ' " •
к=0
Напомним, что распределение Эрланга Н'(х; Ь) имеет ПЛС (Ь/(в + Ь))г
4. Дисциплина ^ТЯЗТ-^^О-^/.РО
Начнем с рассмотрения дисциплины ПЯЯТ-ПГО-ЫГО. Как было определено выше, эта дисциплина предполагает, что поступающая в систему отрицательная заявка убивает первую заявка из очереди в накопителе, а в момент окончания обслуживания заявки на приборе на обслуживание выбирается первая заявка из очереди в накопителе или, если накопитель пуст, последняя заявка из очереди в бункере.
Для вычисления стационарного распределения времени пребывания заявки в системе заметим прежде всего, что при наличии в накопителе заявок в силу дисциплины обслуживания времена между соседними уходами заявок из накопителя (на прибор или в бункер) независимы и имеют экспоненциальное распределение с параметром р + Л-. Поэтому условная вероятность того, что от момента прихода заявк
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.