Одноканальная СМО с ожиданием

Рассмотрим сначала простейшую из всех возможных СМО с ожиданием — одноканальную систему на которую поступает поток заявок с интенсивностью к; интенсивность обслуживания (т. е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Рис. 5.4

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

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

— канал свободен,

— канал занят, очереди нет,

— канал занят, одна заявка стоит в очереди,

— канал занят, заявок стоит в очереди,

— канал занят, заявок стоят в очереди.

Граф состояний СМО показан на рис. 5.4. Интенсивности потоков событий, переводящих в систему по стрелкам слева направо, все равны X, а справа налево — Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево — поток «освобождений» занятого канала, имеющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

Изображенная на рис. 5.4 схема представляет собой схему гибели и размножения. Пользуясь общим решением, данным для схемы гибели и размножения в § 8 гл. 4, напишем выражения предельных вероятностей состояний:

Вводя обозначение перепишем формулы (5.1) в виде:

Заметим, что в знаменателе последней формулы (5.2) стоит геометрическая прогрессия с первым членом 1 и знаменателем; суммируя эту прогрессию, находим:

Таким образом, формулы (5.2) окончательно примут вид;

Обратим внимание на то, что формула (5.3) справедлива только при (при она дает неопределенность вида 0/0). Но сумму геометрической прогрессии со знаменателем найти еще проще чем по формуле (5.3): она равна и в этом случае Заметим, что тот же результат мы могли бы получить более сложным способом, раскрывая неопределенность (5.3) по правилу Лопиталя.

Определим характеристики СМО: вероятность отказа Ротк, относительную пропускную способность q, абсолютную пропускную способность А, среднюю длину очереди, среднее число заявок, связанных с системой

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

Находим относительную пропускную способность:

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

Найдем среднее число заявок, находящихся в очереди; определим эту величину как математическое ожидание дискретной случайной величины R — числа заявок, находящихся в очереди:

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

Вынесем в этом выражении за скобки:

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

а для этого выражения мы можем воспользоваться формулой суммы геометрической прогрессии:

Продифференцируем (5.9) по:

Итак, выражение для суммы, стоящей в скобках в правой части (5.8), найдено:

Подставляя его в (5.8), получим:

Учитывая выражение для из (5.4), имеем:

или, окончательно,

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

где — число заявок в очереди, — число заявок под обслуживанием.

По теореме сложения математических ожиданий

где — среднее число заявок в очереди, — среднее число заявок под обслуживанием.

Величину мы только что нашли; найдем величину. Так как канал у нас один, то случайная величина Q может принимать только два значения: 0 или 1. Значение 0 она принимает, если канал свободен; вероятность этого равна

Значение 1 она принимает, если канал занят; вероятность этого равна

Отсюда находим математическое ожидание числа заявок, находящихся под обслуживанием:

Таким образом, среднее число заявок, связанных с СМО, будет

где величина определяется по формуле (5.11).

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

Поэтому среднее время ожидания будет:

Подставляя сюда выражения для получаем:

Преобразуем сумму в скобках, пользуясь формулой (5.10):

или, выражая через:

Сравнивая это выражение с формулой (5.11), замечаем, что

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

Выведем еще формулу для среднего времени пребывания заявки в системе. Обозначим ТСИСТ случайную величину — время пребывания заявки в СМО. Эта случайная величина складывается из двух слагаемых (тоже случайных):

где — время ожидания заявки в очереди, — случайная величина, равная времени обслуживания если заявка обслуживается, и нулю, если она не обслуживается (получает отказ).

По теореме сложения математических ожиданий:

но, в наших обозначениях, Отсюда находим: или, с учетом формулы (5.4),

Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой). Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно Если в очереди уже находится три машины, очередная машина, прибывшая к станции, в очередь не становится, а проезжает мимо.

Поток машин, прибывающих для заправки, имеет интенсивность (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин. Определить:

— вероятность отказа;

— относительную и абсолютную пропускную способности СМО;

— среднее число машин, ожидающих заправки;

— среднее число машин, находящихся на АЗС (включая и обслуживаемую);

— среднее время ожидания машины в очереди;

— среднее время пребывания машины на АЗС (включая обслуживание). Решение. Находим приведенную интенсивность потока заявок:

По формулам (5.4):

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

Относительная пропускная способность СМО Абсолютная пропускная способность СМО (машины в мин.) Среднее число машин в очереди находим по формуле (5.11)

т. е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.

Прибавляя к этой величине среднее число машин, находящихся под обслуживанием

получаем среднее число машин, связанных с АЗС:

Среднее время ожидания машины в очереди, по формуле (5.14) равно

Прибавляя к этой величине получим среднее время, которое машина проводит на АЗС:

До сих пор мы рассматривали работу одноканальной СМО с ожиданием при ограниченном числе мест в очереди.

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

Попытаемся получить вероятности состояний СМО с неограниченной очередью путем предельного перехода (при) из формул (5.4).

Заметим, что при этом знаменатель в последней формуле (5.2) представляет собой сумму бесконечного числа членов геометрической прогрессии.

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

Рис. 5.5

Предположим, что

т. е. что предельный режим существует. Устремим в формулах (5.4) к и выведем формулы для предельных вероятностей состояний в СМО без ограничений по длине очереди. Получим:

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому Среднее число заявок в очереди получим из (5.11) при

Среднее число заявок в системе по формуле (5.12) при будет равно

Среднее время ожидания также получим из формулы (5.14) при

или, в другой форме:

Среднее время пребывания заявки в СМО равно среднему времени ожидания плюс среднее время обслуживания

Пример 2. На железнодорожную сортировочную горку прибывают составы с интенсивностью (состава в час). Среднее время, в течение которого горка обрабатывает состав, равно 0,4 часа. Составы, прибывшие в момент, когда горка занята, становятся в очередь и ожидают в парке прибытия, где имеются три запасных пути, на каждом из которых может ожидать один состав Состав, прибывший в момент, когда все три запасных пути в парке прибытия заняты, становится в очередь на внешний путь. Все потоки событий — простейшие. Найти:

— среднее число составов, ожидающих очереди (как в парке прибытия, так и вне его);

— среднее время ожидания состава в парке прибытия и на внешних путях;

— среднее время нахождения состава на сортировочной станции (включая ожидание и обслуживание);

— вероятность того, что прибывший состав займет место на виешних путях

Решение. В нашем случае, и СМО в среднем «справляется» с поступающим на нее потоком заявок.

Среднее число составов, ожидающих очереди (как в парке прибытия, так и вне его), найдем по формуле (5.17):

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

Среднее число составов, ожидающих вне парка, будет:

Формулу для бесконечной суммы в скобках получаем предельным переходом (при) из формулы (5.10):

Отсюда

Подставляя сюда получим:

Вероятность того, что прибывающий состав займет место на внешних путях, определяется еще проще: она равна вероятности того, что длина очереди будет не меньше трех, т. е.

Среднее время ожидания в парке прибытия определяем, рассматривая различные гипотезы о числе составов, находящихся в системе:

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

Что же касается среднего времени ожидания на внешних путях, то оно равно

т. е. для наших численных данных,

Среднее время пребывания состава на сортировочной станции (считая ожидание и обслуживание) будет равно: