Автоматика и телемеханика, Л- 9, 2006
Системы массового обслуживания
РАС Б 02.50.Fz
© 2006 г. П.П. БОЧАРОВ, д-р техн. наук, Э.А. НАДАЕВ (Российский университет дружбы народов, Москва)
ОБ ОБСЛУЖИВАНИИ НА ЦЕПОЧКЕ ПРИБОРОВ С ПОТЕРЯМИ В ДИСКРЕТНОМ ВРЕМЕНИ1
Рассматривается ш-фазпая система обслуживания без мест для ожидания, функционирующая в дискретном времени. На систему поступает поток заявок Верпулли с параметром а. Длительности обслуживания на каждом приборе распределены геометрически с параметром Ьг. Заявка теряется, если прибор, па который опа поступает, занят. Выведена система уравнений равновесия, при этом для коэффициентов системы уравнений получены рекуррентные формулы, позволяющие алгоритмизировать ее построение. Даются рекуррентные формулы, для вычисления вероятности потери заяки, вероятности простоя системы и некоторых других макрохарактеристик системы. Численно исследуется проблема оптимальной расстановки приборов.
1. Введение
Во многих реальных системах процесс обработки запросов состоит из их последовательной обработки на нескольких обслуживающих устройствах без мест для ожидания. Отсутствие буферных накопителей ведет к потерям запросов как на входе системы, так и в самой системе. Функционирование таких систем хорошо моделируется с помощью многофазных систем массового обслуживания (CMÜ). CMÜ такого типа представляет собой последовательную цепочку приборов без накопителей.
Исследованию многофазных систем с обслуживанием на последовательной цепочке приборов без накопителей и с потерями заявок посвящен ряд публикаций. В [1] для трех приборов с пуассоновским входящим потоком и экспоненциальным распределением времени обслуживания на каждом приборе получены явные выражения для стационарных вероятностей состояний системы. В [2] была рассмотрена m-фазная СМО с рекуррентным входящим потоком и экспоненциально распределенными временами обслуживания на приборах системы: в дальнейшем для удобства изложения условимся кодировать m-фазную СМО такого типа как GI/M/1/0 ^ ^ (M/1/0)m-1. Для данной СМО в [2] был предложен приближенный метод для расчета вероятности потерь па каждой фазе. В [3] для СМО G/M/1/0 ^ (M/1/0)m-1 с ординарным и стационарным входящим потоком получена формула для общей
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант 06-07-89056).
вероятности потерь. В [3] была также изучена проблема оптимальной расстановки приборов. В [4] результаты, полученные в [3]. обобщены на случай нескольких неоднородных групп приборов.
Следует заметить, что несмотря на внешнюю простоту замкнутой формулы для вероятности потерь, полученной в [3]. ее использование при расчетах при близких значениях некоторых (или всех) интеисивиостей обслуживания приводит к значительным вычислительным погрешностям, а в ряде случаев и вовсе к неверным результатам. Поэтому в [5] была предпринята попытка найти иной способ расчета вероятности потерь. На основе подхода, близкого к подходу, использованному в [6]. для СМО Cox/M/1/0 ^ (M/1/0)m-1 с рекуррентным входящим потоком, задаваемым распределением Кокса, в [5] был предложен рекуррентный алгоритм, позволяющий вычислить вероятность потери, интенсивность выхода и некоторые другие показатели производительности системы без непосредственного решения СУР. Подход. предложенный в [5]. эффективен в вычислительном плане и позволяет рассчитать указанные выше характеристики для больших значений параметра m и любых значениях интеисивиостей обслуживания. Кроме того, в [5] изучен вопрос об оптимальной расстановке приборов. В [7] рекуррентный подход работы [5] был распространен на случай СМО PH/PH/l/r ^ (M/1/0)m-1 с первой фазой, определяемой СМО PH/PH/1/r, а также с дополнительными пуассоновскими потоками па каждую фазу и с учетом обратной связи на каждом из приборов.
m
СМО Geom/1/0 ^ (Geom/1/0)m-1 с потерями, функционирующей в дискретном времени, с входным потоком Бериулли и геометрическим распределением времени обслуживания на каждом из приборов. Получены рекуррентный алгоритм для расчета вероятности потери, среднего числа заявок в системе и некоторых других макрохарактеристик СМО, а также выведена явная формула для вероятности простоя системы. Также предложена асимптотическая (при m ^ ж) приближенная формула для вероятности простоя системы. Численно исследуется проблема оптимальной расстановки приборов.
2. Описание системы
Рассмотрим СМО из т последовательно расположенных приборов без мест для ожидания, функционирующую в дискретном времени, которое изменяется в фиксированных интервалах времени (тактах). Величину такта примем равной Н единиц времени, Н > 0, и будем считать, что все возможные изменения в СМО происходят в моменты времени пН, п = 1, 2,...
На первый прибор поступает дискретный поток заявок, являющийся потоком Бернулли с параметром а, гДе а ~ вероятность поступления заявки за один такт времени, 0 < а < 1. Заявка, поступившая на вход системы в момент занятости первого прибора, теряется и вновь не возобновляется.
Длительности обслуживания заявок на приборе г имеют дискретное геометрическое распределение с параметром Ъ^ где Ъ - вероятность обслуживания заявки на приборе г за такт времени, 0 < Ъi < 1, г = 1,т. Так как приб оры 2, 3,...,т также не имеют накопителей, то необходимо задать дисциплину сопряжения приборов, определяющую дальнейшее поведение заявки, закончившей обслуживание на каком-либо из приборов в момент занятости последующего прибора. В нашем случае будем предполагать, что такая заявка теряется.
В отлично от непрерывного времени в дискретном времени за один такт может
п
т
которой завершилось на такте п, покидает систему; 2) заявка на приборе (т — 1),
обслуживание которой завершилось на такте и, помещается на прибор ш; и т.д. до прибора 1; ш) заявка та при боре 1, обслуживание которой завершилось па такте и, помещается па прибор 2; ш + 1) поступает новая заявка, генерация которой завершилась на такте и, и она сразу помещается на прибор 1.
Случай дискретного времени, рассматриваемый в данной работе, является гораздо более сложным для анализа по сравнению с непрерывным случаем. Прежде всего заметим, что в отличие от непрерывного времени в дискретном времени за один такт может произойти ш + 1 событие (обслуживание на каждом из ш приборов и поступление новой заявки).
3. Цепь Маркова и свойства переходной матрицы
Функционирование рассматриваемой системы может быть описано однородной цепью Маркова (ЦМ) {£„, и > 0} по моментам временп иЛ., над пространством состояний
Ет = {(¿1 ,¿2, . . . ,«т)|Ь' = 0, 1, 3 = 1,ш} ,
где для некоторого момента времени компонента г., вектор а хт = (¿1,..., ¿т) соответствует состоянию 3-го прибора, при этом г. = 0 означает, что прибор свободен, а г. = 1 - прибор занят. Очевидно, что Ет = Е1 х Е2 х ... х Ет, где Е. = {0,1}, 3 = 1,ш.
В дальнейшем при указании состояния будем использовать обозначение г; для серии г, г,..., г длины / (/ = 1, ш). Кроме того, условимся обозначать точкой символ, по всем возможным значениям которого произведено суммирование. Условимся также в дальнейшем для краткости называть /-системой многофазную СМО, состоящую из / фаз (приборов).
Ниже будем также использовать векторы типа (х;-1, г;), где символ г; указывает состояние последнего прибора в /-системе. Тогда при / = 1 будем полагать, что (хо, г1) = («1).
Кроме того, ниже будем использовать обозначения а =1 — а и 6; = 1 — 6;. Прежде чем перейти к выводу системы уравнений равновесия (СУР), остановимся на некоторых свойствах матрицы вероятностей переходов для ЦМ {£и,и > 0}.
Рассмотрим последовательность /-систем, / = 1, ш. При фиксированном /, / = 1, ш, для ЦМ, описывающей /-систему, обозначим через К(у;, х;) вероятность перехода из состояния у; в состояние х; при условии, что па приборе / не завершится обслуживание заявки, у;, х; € ЕАналогично для ЦМ, описывающей /-систему, обозначим через Ь(у;, х;) вероятность перехода из со стояния у; в состоян ие х; при условии, что па приборе / завершится обслуживание заявки, у;, х; € Е;.
Покажем теперь, что для введенных выше функций К (у;, х;) и Ь(у;, х;) можно построить рекуррентные соотношения по параметру /, определяющему число фаз в /-системе, / = 1, ш.
Лемма 1. Функция К(у;,х;) при / = 1,ш удовлетворяет, следующим рекуррентным соотношениям:
(1) К((у;_1, 0), (х;_1, 0)) = К(у;_1, х;_1),
(2) К((у;_1, 0), (х;_1, 1)) = £(у;_1, х;_1),
(3) К((у;_1, 1), (х;_1, 0))=0,
(4) К((у;_1, 1), (х;_1, 1)) = 6; (К(у;_1, х;_1) + £(у;_1, х;_1)),
(5) К (уо, хо) = а.
Доказательство леммы 1. Положим х; = (¿1 ,г2,... ,г;) ш у; = (]1,]2,... ,]1)-Пусть = 0 и ¿1 = 0. Это означает, что в некоторый момент времени /-система находилась в состоянии, когда прибор / свободен. Следовательно, с вероятностью, равной 1, за следующий такт не произойдет обслуживание заявки и функция К (у;, х;) будет отлична от нуля. Кроме того, заметим, что переход осуществится в состояние (у;-1, 0), в котором прпбор / свободен. Следовательно, на приборе / — 1 также не произойдет обслуживание. Отсюда следует, что
К((у;-1, 0), (х,_1, 0)) = К(у;-1, х,_1), / =Т~т,
и равенство (1) доказано.
Рассмотрим теперь случай = 0 и г; = 1. Это означает, что в некоторый момент // с вероятностью, равной 1, за следующий такт не произойдет обслуживание заявки и функция К (у ;, х;) будет отлична от нуля. Но в отличие от предыдущего случая па прибор / поступит заявка, следовательно, на приборе / — 1 должно завершиться обслуживание заявки. На основе этих рассуждений получаем, что
К ((у;—1, 0), (х;-1, 1)) = Ь(у,-1, х;-1), / = 1,т,
и равенство (2) доказано.
Далее, пусть = 1 и г; = 0. Это означает, что в некоторый момент времени /-сис-
/
/
/
К(у;, х;) не сопровождается завершением процесса обслуживания заявки на прибо-/
К((у; — 1, 1), (х; —1, 0)) = 0, / = 1т,
и равенство (3) доказано.
Наконец, пусть j; = 1 и г; = 1. Это означает, что в некоторый момент времени //
/
Следовательно, обслуживание на последнем приборе не завершится, что происходит с вероятностью Ь;. Кроме того, следует учесть, что за указанный такт времени /—1
про
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.