МС лекции (Лекции), страница 6

1.5.2. Схема гибели и размножения

После преобразований уравнений Колмогорова очевидно, что вероятности того, что система не изменит свое состояние не влияют на вероятности состояний (образуют в уравнениях пару слагаемых с противоположными знаками). Поэтому в дальнейшем на графах переходов мы будем указывать только вероятности переходов типа и , и указывать только интенсивности переходов. Тогда в общем случае для марковских систем мы получаем граф переходов следующего вида:

Здесь каждое из средних состояний связано прямой и обратной стрелкой с каждым из соседних состояний. Такой граф называется схемой гибели и размножения. Найдем вероятности состояний установившегося режима для этой схемы

или

отсюда

Аналогично

отсюда

Преобразуем

…

Учитывая, что получаем

Полученные формулы мы будем в дальнейшем использовать для расчета вероятностей состояний различных СМО.

1.5.3. Формула Литтла

Выведем формулу, связывающую (для стационарного режима) среднее число заявок в системе и среднее время пребывания заявки в системе.

Для любой СМО, если в системе установился стационарный режим, то среднее число заявок, прибывших в СМО за единицу времени, равно среднему числу заявок, покидающих ее: оба потока имеют одну и ту же интенсивность .

Обозначим X(t) - число заявок, прибывших в СМО до момента t, Y(t) - число заявок, покинувших СМО до момента t. Обе функции случайны и меняются скачком (на 1) в моменты прихода и ухода заявок. Примерный вид функций приведен на рис.1.1.

Рис.1.1. График функций прихода и ухода заявок из СМО

Очевидно, что для любого момента t: Z(t)=X(t)-Y(t) - число заявок, находящихся в СМО. Рассмотрим интервал времени T и вычислим для него среднее число заявок, находящихся в СМО

Этот интеграл - площадь заштрихованной фигуры, которая состоит из прямоугольников в 1 высотой и с основанием, равным времени пребывания в системе соответствующей заявки (t_i)

Тогда и

- это среднее число заявок, пришедших за время Т. Если разделить сумму всех времен t_i на среднее число заявок, то получим среднее время пребывания заявки в системе тогда

Откуда получаем формулу Литтла: .

Для любой СМО среднее время пребывания заявки в системе равно среднему числу заявок в системе, деленному на интенсивность потока заявок.

Аналогично выводится формула, связывающая среднее число заявок в очереди и среднее время пребывания заявки в очереди

1.5.4. Одноканальная СМО с отказами

Простейшая задача: СМО содержит один канал обслуживания, заявка, поступившая на вход системы и заставшая канал занятым, получает отказ. Граф переходов:

Тогда ,

Исходя из условия и начальных условий , получаем

Для стационарного режима

Получим некоторые характеристики СМО.

Вероятность отказа: заявка получит отказ, если канал занят

Относительная пропускная способность (q) равна среднему числу обслуженных заявок к общему числу поступивших заявок (показывает долю обслуженных заявок):

Абсолютная пропускная способность (А) – число обслуженных заявок в единицу времени

Среднее число занятых каналов (Z) равно среднему числу заявок в системе

Среднее время, проведенное заявкой в системе

1.5.5. Одноканальная СМО с ограниченной очередью

Пусть длина очереди в одноканальной СМО ограничена числом m (M/M/1/m). Тогда граф переходов будет иметь следующий вид:

Используя формулы схемы гибели и размножения, получаем:

Среднее число занятых каналов:

Среднее число заявок в очереди:

Среднее число заявок в системе:

.

Вероятность в отказе:

Относительная пропускная способность:

1.5.6. Многоканальные СМО с ожиданием

Рассмотрим случай S одинаковых каналов обслуживания с интенсивностью обслуживания каждого прибора. При простейшем входном потоке и экспоненциальном времени обслуживания правило выбора канала не влияет на функционирование системы, т.е. на число заявок, находящихся в системе, на время ожидания.

Построим граф переходов:

Интенсивность обслуживания возрастает с ростом числа занятых каналов. Как только все каналы оказываются занятыми заявками, интенсивность обслуживания в системе перестает расти, вновь пришедшие заявки становятся в очередь, ожидая освобождения какого-либо из каналов.

По графу строим уравнения вероятностей состояний:

… где ,

где .

Учитывая

Получим основные характеристики системы:

Абсолютная пропускная способность:

Отсюда среднее число занятых каналов:

Среднее число заявок в очереди:

После преобразований:

Общее число заявок в системе:

Среднее время пребывания в системе:

Все вышеперечисленные формулы справедливы только для стационарного режима. Для того, чтобы многоканальная система с бесконечной очередью имела стационарный режим, должно выполняться условие

1.5.7. Многоканальные СМО с отказами

Имеется S обслуживающих каналов, каждый из которых доступен, когда он свободен, для каждой из поступающих в систему заявок. Если при поступлении очередной заявки все каналы заняты, то заявка получает отказ и теряется (M/M/S/0). Граф переходов:

Уравнения вероятностей состояний здесь такие же, как и для любой многоканальной СМО, только для условия

,

Заявка получает отказ в том случае, если все каналы заняты, тогда вероятность отказа:

Относительная пропускная способность:

Учитывая, что , среднее число занятых каналов равно:

Среднее время, проводимое заявкой в системе:

Если в системе очередь, ограниченная числом мест m (M/M/S/m), то заявка получит отказ в том случае, когда в системе заняты все каналы обслуживания и все места в очереди (S + m заявок). Тогда вероятность отказа:

где

Абсолютная пропускная способность:

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

1.5.8. Многоканальные СМО с взаимопомощью

Очень часто при наличии нескольких каналов обслуживания при поступлении заявки все каналы приступают к ее обслуживанию, если они свободны. При этом интенсивность обслуживания повышается в S раз: , где S - число каналов. После обслуживания заявки все S каналов освобождаются одновременно. Если поступает заявка при условии, что в системе уже находится одна заявка, то часть приборов обслуживает старую заявку, а остальные приступают к обслуживанию новой заявки.

Например: в системе ПВО при появлении вражеской цели-заявки все приборы слежения и уничтожения цели работают, как правило, по одной цели, увеличивая интенсивность обслуживания (уничтожения). С появлением второй цели-заявки часть приборов переключается на эту цель и т.д.

Для марковских систем неважно, как распределены каналы между заявками при условии участия всех приборов в обслуживании.

При поступлении заявки в систему, в которой все каналы заняты, она становится в очередь. Если канал освободился от обслуживания, и в очереди нет заявок, он подключается к обслуживанию других заявок. Граф переходов:

Граф аналогичен графу одноканальной СМО с . Соответственно, . Для стационарного режима должно выполняться условие . Тогда можно использовать все формулы для одноканальной СМО с ожиданием.

Уравнения вероятностей состояний:

Среднее количество заявок в системе:

Среднее количество заявок в очереди:

Среднее время нахождения заявки в системе:

.

Рассмотрим вариант СМО с взаимопомощью с отказами: при поступлении заявки в систему, где все каналы заняты, она получит отказ.

Граф переходов:

Данный граф равносилен одноканальной СМО с

И ограниченной очередью, с количеством мест равным (S-1).

Соответственно, уравнения вероятностей состояний:

.

Вероятность отказа:

Относительная пропускная способность:

.

Среднее число заявок в системе:

1.5.9. Замкнутые СМО

Рассмотрим случай, когда количество заявок, обслуживаемых системой, ограничено. Например, процесс восстановления m единиц оборудования S ремонтными бригадами. Каждая единица оборудования работает в среднем , после чего выходит из строя. Тогда интенсивность выхода из строя единицы оборудования (мы считаем, что время безотказной работы оборудования распределено по показательному закону). После ремонта единица оборудования вновь поступает на вход системы с интенсивностью (может снова выйти из строя).

Если в некоторый момент времени ремонтируются или ожидают ремонта n единиц оборудования, а работают m-n, то вероятность отказа в течение (t, t+dt) равна - интенсивность прихода заявок в систему зависит от количества уже находящихся в системе заявок.

Построим граф переходов для замкнутой СМО с одним каналом обслуживания и m заявками:

Используя схему гибели и размножений, построим уравнения вероятностей состояний:

…

… или

Абсолютная пропускная способность A для данной СМО – среднее количество неисправностей, устраняемых каналом обслуживания в единицу времени, и

,

Где P_зан - вероятность занятости канала, или