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

Тип работы:
Реферат
Предмет:
Кибернетика


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

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

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

А. П. Кирпичников, А. С. Титовцев ОТКРЫТАЯ ОДНОКАНАЛЬНАЯ СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ И НЕОГРАНИЧЕННОЙ ОЧЕРЕДЬЮ
Рассмотрена математическая модель принципиально новой открытой одноканальной системы массового обслуживания (СМО), являющейся обобщением двух других ранее известных СМО: одноканальной классической СМО (М/М/1) и одноканальной СМО с ограниченной очередью (М/М/1/Е). Авторами была проведена математическая формализация данной модели, исследован характер поведения её вероятностных, числовых и временных характеристик. Математическая формулировка модели и результаты исследований приведены ниже.
В данной СМО действует следующая дисциплина обслуживания. Входящий поток требований, поступающих на обслуживание, содержит заявки двух типов: «нетерпеливые» и «терпеливые». «Нетерпеливые» заявки становятся в очередь до тех пор, пока число заявок, находящихся в очереди не достигнет определённого значения Е. Если же длина очереди больше Е, «нетерпеливая» заявка автоматически получает отказ и уходит не обслуженной. «Терпеливые» заявки становятся в очередь в любом случае и ждут до тех пор, пока не будут обслужены.
Пусть її - интенсивность потока «нетерпеливых» заявок, 1 — интенсивность потока «терпеливых» заявок, тогда І1+І2 =1 — интенсивность входного потока заявок до Е+1-го состояния (рис. 1), т — интенсивность потока обслуженных заявок. Обозначим 1-і
р1 = - приведённая интенсивность потока «нетерпеливых» заявок-
р2 = 12 — приведённая интенсивность потока «терпеливых» заявок, она же приведенная интенсивность входного потока после Е+1-го состояния-
р _ 11 +І2 _ 1 _ рї + р2 — приведённая интенсивность входного потока до Е+1-го состояния.
Считаем, что входной и выходной потоки заявок являются простейшими [1]. Выделяя состояния СМО по числу заявок, находящихся в системе, получим марковский процесс с дискретными состояниями и непрерывным временем, т. е. процесс гибели и размножения, граф состояний которого имеет вид, представленный на рис. 1.
Рис. 1 — Граф состояний открытой одноканальной СМО с отказами и неограниченной очередью
По данному графу запишем систему уравнений Колмогорова для вероятностей равновесных состояний СМО [2].
Po1 = PiM-P11 + P# = Po1 + Р2Ц Р21 + P 2 м = Pi1 + P3M • Pe+11 + Pe+im = Pe1 + Pe+2м Pe+21 + Pe+2Ц = Pe+11 2 + Pe+зМ-
Откуда с учётом условия нормировки X Р| = 1 получим формулы для вероятностей ста-
1=0
ционарных состояний системы Р|:
Рг
(1 -р)0-Р2).
(-~p)(i~pE2+)Pk. k? e+1 1 р2 р1р
(1 -p)(1 -PEL)pE+1p2-E-i, k & gt- E +1
1 -р2 -р1рЕ+1 |
1 -Р2 -Р1Р
Числовые характеристики установившегося режима
1. Вероятности ожидания и вероятность отказа.
Обозначим
РоЖ1 — вероятность ожидания для «нетерпеливой» заявки (1) —
Рож 2 — вероятность ожидания для «терпеливой» заявки () —
Ротк — вероятность отказа (только для «нетерпеливых» заявок).
-1−1 = (1 -Р2)Р (1 -PE).
E+1
Po& gt-k1 = P1 + P2 + * + Pe = Pop Г1 + p + * +PE1] = ^--------
L J 1 -p2-p1p
p (1 -p2 -p1pE).
'-ож 2
P1 + P2 + * + Pe + Pe+1 + * = 1 — Po
Pe+1 + Pe+2 + *
)E+1Po ё1 + p2 +p2 + * ]= 1
1 -p2 -p1pE+1 (1 -p)pE+1
p2 p1p
E+1
2. Среднее число требований, находящихся под обслуживанием.
, p (1 -p2 -p1pE)
n = oPo + 1P1 + 1P2 + * + 1PE+1 + * = 1 — Po = ^-----------Ё+Л = Рож2
1 p2 p1p
Дисперсия этой величины:
On
= n2 — n2 = o2Po + 12P1 + * + 12Pe+1 + * - n2 = Po (1 — Po)= PoPok2-
Если поток обслуживания является простейшим (пуассоновским), то вероятность того, что за время t системой будет обслужено k заявок, определяется формулой [3]:
Вк (1) = ^ є-«-
тогда функция распределения времени обслуживания одной заявки
Робел (0 = 1 — е& quot-И
и плотность распределения
і обел (і) = те-т '- 1.
Среднее время обслуживания одной заявки в системе
1
U™ = l tf o6ct (t)dt = ml te-mtdt
m
а его дисперсия
2
Oo6ot
1 1
toбcлбл ml t Є m dt 2 2 ¦
o mm
3. Среднее число заявок в очереди (средняя длина очереди).
= 0Ро + 0Р1 + 1р 2 + 2Рз + • + Ере+1 + (Е +1) Ре+2 + & lt-
Ер1
1-P
ож1
+
P2_____________
1 -P2 1 -P.
Дисперсия этой величины
P
2 — |2 -2. S = І - І -
2
Ol =
(1-p)'-
: [(1 + p) Рсж1 — E (1 -P2)(E (1 -P) + 2) Po"]
+
+p2
E2 +
2E
1 + p2
1 -P2 (1 -P2)2
+
1 -P
^ж1
+
P2 EP1
1 -P2 1 -P
Найдём функцию распределения времени ожидания обслуживания одной заявки. По определению
F (t) = p ('- & lt- t).
где t — время ожидания обслуживания (случайная величина), но тогда
F (t) = 1 — Р (t & gt- t),
где P (t & gt- t) — вероятность того, что время ожидания в очереди для одной заявки больше некоторого наперёд заданного времени t. А это, в свою очередь, может быть, во-первых, в том случае, если эта заявка, поступив в систему, нашла обслуживающее устройство (прибор) занятым, и за время t предыдущая заявка не была обслужена- во-вторых, в том случае, когда поступившая заявка находит занятым обслуживающее устройство и ещё одну заявку, ожидающую обслуживания в очереди, а за время t либо не было обслужено ни одной, либо была обслужена только одна заявка- в-третьих, если заявка находит занятое устройство и две заявки в очереди, а за время t прибор либо не успевает обслужить ни одной за-
S9
явки, либо обслуживает одну, либо две заявки и так далее. По формуле полной вероятности в этом случае имеем
1 — Рожид (1)= Р1В0 (1) + Р 2 [Во (1) + Ві(1)] + Рз [Во (1) + Ві(1) + В2 (1)] +Ре+1 [Во (1) + Ві(1)+ • + Ве (1)] + Ре+2 [Во (1) + ВіМ+ • + Ве+і (1)]
= е-Й
Рі + Р2
1 + - 1!
+Р3
1+М 1! 2!
+ • +1 2 Л
+ • +
+ • + + • =
/

Е+2
Е+1 Л
1+й+и_+• +М л
1! 2! (Е +1)!
+ & lt-
= в ^ [Р1 + Р2в1 (М*) + Рзв2 (ц!)+ • + Ре+1Эе (М*)+ * ]
(т (т)2 (т)т
где вт (u. t) = 1 ±-------------------------------------------1-+ * ±неполная экспонента,
т^- 1! 2! т!
Рожид (t)= 1 — в-И [Р1 + Р2в1(т) + Рзв2 (М*)+ * + РЕ+1вЕ Н)+ * ]
тогда
Плотность распределения времени ожидания обслуживания одной заявки:
с1Р (t) … ви.. -Е+1
Рожид
іожид (1)
сК
ІРоЄ-т1ЄЕ-1 (11) + Рое-(м-12& gt-1 — ЙГ^РоЄ-т-'-еЕ-1 (-,*) •
е
Р2
Р2
Среднее время ожидания обслуживания одной заявки в очереди:
1 Ер1
1 = Г Ц (1)^ = Рож1 +
Іожид Л Ч ожиді/,/, ~
о ц-1
Й-12 Й-1
Осреднённый квадрат этой величины:
1
ожид
Дисперсия времени ожидания заявки в очереди: 2Рож1
-2 = 12
Фожид
ожид ожид
1-
й2(1-р)'
2Е (1 Р2) + Е (Е + 1}р, 2
(1-Р)2
Р ож1

(1 -Р) (1 -Р2)2 (1 -Р2)
йО-Р)
+
1 ЕР1
1 -р2 1 -р
4. Среднее число требований, находящихся в системе в целом (как в очереди, так и под обслуживанием).
к = 0Ро + 1Р1 + 2Р 2 + 3Рз +…+ (Е + 1) Ре+1 + (Е + 2) Ре+2 + * =
о
Рожі Е (1 Р2) Рс
1 -Р
Дисперсия этой величины
/
+ Е +
V
-2.
к
1 Р2
1
О2 = --& quot-2 |(1 + р) Рожі - Е (1 р2)(Е (1 -р) + 2) Ротк 1 +
(1-Р)
2 2Е 1 + Р2
Е2 ±----------±---------2
1 Р2 (1 -Р2)2
Р стк
Рож1 — Е (1 -р2)Рс
1-Р
¦ +
Е + ¦
1
1 р2
Среднее время пребывания одной заявки в системе:
Ро + Р
ож1
т-1
+
1 (Е + 1) Р1
т-12 т-1
Дисперсия времени пребывания заявки в системе: _ 2 (Ро + Рож1)
а-
т2(1-Р)2
2 (Е +1)(1 -Р2_) + (Е + 1)(Е + 2) Р1
(1-Р)
Ро + Рож1
т (1 -р)
2 2 (Е +1)
1 -Р (1-Р2)2 (1 -Р2)
т
+
1
(Е + 1) Р1
1
р2 1 -р
Далее исследуем характер поведения характеристик рассматриваемой СМО. С этой целью для каждой из функций построим семейство кривых, полученных при нескольких значениях максимальной длины очереди Е. Приведённая интенсивность Р1 может принимать значения от 0 до П & gt- 1, поскольку в случае переполнения очереди «нетерпеливая» заявка получает отказ, а Р2 всегда должно быть меньше 1, иначе очередь будет бесконечной.
Придавая переменной Р2 конкретные значения, получим функции от одной переменной Р1. Представленная модель массового обслуживания обобщает две известные и описанные
в литературе модели: одноканальную классическую СМО (модель М/М/1) [1] и СМО с ограниченной очередью (модель М/М/1/Е) [2].
Как видно (рис. 2), при значениях интенсивности Р2, отличных от 0, начальные значения вероятности ожидания для «нетерпеливой» заявки (при Р1 _ 0) также отличны от 0. Это связано с тем, что даже при отсутствии «нетерпеливых» заявок, обслуживающий аппарат может быть занят «терпеливой» заявкой, и вновь поступившей в систему «нетерпеливой» заявке придётся ждать до тех пор, пока предшествующая «терпеливая» заявка не будет обслужена. Наличие экстремума объясняется тем, что при суммарной интенсивности входного потока требований Р1 +Р2 & gt- 1, в силу ограниченности числа мест в очереди (для «нетерпеливых» заявок), наблюдается увеличение отказов в обслуживании «нетерпеливым» заявкам, поэтому при превышении интенсивностью Р1 определённого предела веро-
т
Рис. 2 — Зависимость вероятности ожидания для «нетерпеливой» заявки от приведённой интенсивности потока «нетерпеливых» заявок р1 при фиксированных значениях интенсивности Р2 и длины очереди Е
ятность ожидания для «нетерпеливой» заявки постепенно снижается. При повышении интенсивности Р2 наблюдается смещение точек экстремума влево, возрастает вероятность ожидания при Р1 = 0, а при значениях Р2, близких к единице, вероятность ожидания для «нетерпеливой» заявки носит монотонно убывающий характер и при увеличении Р1 ассимптотически стремится к нулю. При Р2 = 0 данная модель вырождается в модель М/М/1/Е (рис. 3).
Начальное значение для среднего числа заявок, находящихся под обслуживанием, при Р1 = 0 равно значению интенсивности Р2. С увеличением интенсивности Р1 наблюдается монотонное возрастание среднего числа обслуживаемых заявок, при этом увеличение интенсивности Р2 способствует более резкому возрастанию последнего при незначительном изменении Р1. При большем увеличении интенсивности Р1 среднее число обслуживаемых заявок возрастает более плавно и ассимптотически стремится к единице. Это объясняется тем, что рассматриваемая система является одноканальной и не способна одновременно обслуживать более одной заявки (рис. 4).
Рис. 3 — Зависимость среднего числа заявок, находящихся под обслуживанием, от приведённой интенсивности потока «нетерпеливых» заявок р1 при фиксированных значениях интенсивности р2 и длины очереди Е
Рис. 4 — Зависимость среднего числа заявок, находящихся в очереди, от приведённой интенсивности потока «нетерпеливых» заявок Рі при фиксированных значениях интенсивности Р2 и длины очереди Е
С увеличением интенсивности Р2 стремительное возрастание средней длины очереди начинается при меньших значениях интенсивности Р1, при дальнейшем увеличении Р1 среднее число заявок, ожидающих обслуживания, ассимптотически стремится к определённому значению, которое может превышать значение Е. Данное обстоятельство связано с тем, что согласно дисциплине обслуживания, принятой в данной СМО, ограничение на длину очереди распространяется только на «нетерпеливые» заявки. «Терпеливые» заявки становятся в очередь в любом случае. Разница между предельным значением длины очереди и соответствующим значением Е тем больше, чем больше интенсивность Р2. При значениях Р2, близких к единице средняя длина очереди значительно отличается от той, что была при меньших Р2. Это означает, что использование подобной системы при интенсивных потоках «терпеливых» заявок нежелательно, а использование её при Р2 & gt- 1 приведёт к переполнению очереди.
Среднее число заявок, находящихся в системе в целом, имеет аналогичный характер поведения.
Литература
1. Вентцель Е. С. Теория вероятностей. М.: Наука, 1969. 576 с.
2. КлейнрокЛ. Теория массового обслуживания. М.: Машиностроение, 1979. 432 с.
3. Ивченко Г. И., Каштанов В. А., Коваленко И. Н. Теория массового обслуживания. М.: Высшая школа, 1982. 256 с.
© А. П. Кирпичников — д-р техн. наук, проф., зав. каф. интеллектуальных систем и управления информационными ресурсами КГТУ- А. С. Титовцев — асп. той же кафедры.

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