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

Предположим, сначала, что количество мест в очереди ограничено числом m, т. е. если заявка пришла в момент, когда в очереди уже стоят т заявок, она покидает систему необслуженной. В дальнейшем, устремив m к бесконечности, мы получим характеристики одноканальной СМО без ограничений по длине очереди.
Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):
S0 — канал свободен,
S1 — канал занят, очереди нет,
S2 — канал занят, одна заявка стоит в очереди,
Sk — канал занят, k — 1 заявок стоит в очереди,
Sm+1 — канал занят, m заявок стоят в очереди.
Граф состояний СМО показан на рисунке. Интенсивности потоков событий, переводящих в систему по стрелкам слева направо, все равны λ, а справа налево — μ. Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево — поток «освобождений» занятого канала, имеющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).
Изображенная схема представляет собой схему гибели и размножения. Пользуясь общим решением, данным для схемы гибели и размножения в п.4.3, напишем выражения предельных вероятностей состояний:
(20)
Вводя обозначение (λ/μ)= p, перепишем формулы (5.20) в виде:
(21)
Заметим, что в знаменателе последней формулы (21) стоит геометрическая прогрессия с первым членом 1 и знаменателем р; суммируя эту прогрессию, находим:
(22)
Таким образом, формулы (21) окончательно примут вид:
(23)
Обратим внимание на то, что формула (22) справедлива только при р≠1 (при р = 1 она дает неопределенность вида 0/0). Но сумму геометрической прогрессии со знаменателем р = 1 найти еще проще чем по формуле (22): она равна m + 2, и в этом случае р0 =1/(m + 2). Заметим, что тот же результат мы могли бы получить более сложным способом, раскрывая неопределенность (22) по правилу Лопиталя.
Определим характеристики СМО: вероятность отказа Ротк, относительную
пропускную способность q,
абсолютную пропускную способность A, среднюю длину очереди
, среднее число
заявок, связанных с системой
.
Очевидно, заявка получает отказ только в случае, когда канал занят и все m мест в очереди — тоже:
(24)
Находим относительную пропускную способность:
(25)
Абсолютная пропускная способность:
A=λq
Найдем среднее число
заявок, находящихся
в очереди; определим эту величину как математическое ожидание дискретной
случайной величины R —
числа заявок, находящихся в очереди:
С вероятностью р2 в очереди стоит одна заявка, с вероятностью р3 две заявки, вообще с вероятностью рк в очереди стоят k-1 заявок, наконец, с вероятностью рm+1 в очереди стоят m заявок. Среднее число заявок в очереди получим, умножая число заявок в очереди на соответствующую вероятность и складывая результаты:
(26)
Вынесем в этом выражении р2р0 за скобки:
(27)
Выведем формулу для суммы, стоящей в скобках (этой формулой мы будем часто пользоваться в дальнейшем). Очевидно, рассматриваемая сумма представляет собой не что иное, как производную по р суммы
![]()
а для этого выражения мы можем воспользоваться формулой суммы геометрической прогрессии:
(28)
Продифференцируем (5.28) по р:

Итак, выражение для суммы, стоящей в скобках в правой части (27), найдено:
(29)
Подставляя его в (5.27), получим:
![]()
Учитывая выражение для р0 из (5.23), имеем:
![]()
или, окончательно,
(30)
Таким образом, мы вывели выражение для среднего числа заявок, ожидающих
обслуживания в очереди. Выведем теперь формулу для среднего числа
заявок, связанных с системой (как
стоящих в очереди, так и находящихся под обслуживанием). Будем решать задачу
следующим образом: рассмотрим общее число заявок К, связанных с системой, как
сумму двух случайных величин: числа заявок, стоящих в очереди, и числа заявок,
находящихся под обслуживанием:
K=R+ Ω
где R – число заявок в очереди, Ω- число заявок под обслуживанием.
По теореме сложения математических ожиданий
![]()
где
-
среднее число заявок в очереди,
-
среднее число заявок под обслуживанием.
Величину
- мы только что нашли; найдем величину
-.
Так как канал у нас один, то случайная величина Ω может принимать только два значения: 0 или1. Значения 0
она принимает, если канал свободен; вероятность этого равна
![]()
Значение 1 она принимает, если канал занят; вероятность этого равна
![]()
Отсюда находим математическое ожидание числа заявок, находящихся под обслуживанием:
![]()
Таким образом, среднее число заявок, связанных с СМО, будет
(31)
где величина
определяется
по формуле (30).
Выведем выражение еще для одной существенной характеристики СМО с
ожиданием: среднего времени ожидания заявки в очереди. Обозначим его
.
Пусть заявка проходит в систему в какой-то момент времени. С вероятностью
p0 канал
обслуживания будет занят, и ей не придется стоять в очереди, и
заявка будет ждать своего обслуживания в течение времени 1/ μ (среднее время
обслуживания одной заявки). С вероятностью p2 в очереди перед
рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем
будет равно 2/μ,
и т. д. Вообще, с вероятностью pk пришедшая заявка
застанет в системе k
заявок и будет ждать в среднем k/μ
единиц времени; здесь k может быть любым целым числом до m. Что же касается k=m+1, т.е. случая, когда вновь
приходящая заявка застанет канал обслуживания занятым и еще m заявок в очереди
(вероятность этого pm+1),
то время ожидания в этом случае также равно нулю, потому что заявка не станет в
очередь (и не обслуживается). Поэтому среднее время ожидания будет:
![]()
Подставляя сюда выражения для p1,….., pm, получаем:

Преобразуем сумму выражений в скобках, пользуясь формулой (5.29):
![]()
или, выражая р0 через р:
![]()
(32)
Сравнивая это выражение с формулой (30), замечаем, что
![]()
т.е. среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Выведем еще формулу для среднего времени пребывания заявки в системе. Обозначим Тсист случайную величину — время пребывания заявки в СМО. Эта случайная величина складывается из двух слагаемых (тоже случайных):
![]()
где Тож
— время ожидания заявки в очереди, в
случайная
величина, равная времени обслуживания Тоб, если заявка
обслуживается, и нулю, если она не обслуживается (получает отказ). По
теореме сложения математических ожиданий:
![]()
но, в
наших обозначениях, М [Тож]=toж, а
.
Отсюда находим:
(23),
![]()
Пример 1. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой). Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно, m=3). Если в очереди уже находится три машины, очередная машина, прибывшая к станции, в очередь не становится, а проезжает мимо. Поток машин, прибывающих для заправки, имеет интенсивность λ=1 (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин. Определить:
— вероятность отказа;
— относительную и абсолютную пропускную способности СМО;
— среднее число машин, ожидающих заправки;
— среднее число машин, находящихся на АЗС (включая и обслуживаемую);
— среднее время ожидания машины в очереди;
— среднее время пребывания машины на АЗС (включая обслуживание).
Решение. Находим приведенную интенсивность потока заявок:
![]()
По формулам (23):
![]()
![]()
![]()
Вероятность отказа Ротк »0,297.
Относительная пропускная способность СМО q = 1 — Ротк == 0,703. Абсолютная пропускная способность СМО А=λq=0,703 (машины в мин.) Среднее число машин в очереди находим по формуле (30)
![]()
т. е. среднее число машин, ожидающих в очереди на заправку, равно 1,56..
Прибавляя к этой величине среднее число машин, находящихся под облуживанием
![]()
получаем среднее число машин, связанных с АЗС:
![]()
Среднее время ожидания машины в очереди, по формуле (32) равно
(мин).
Прибавляя к этой величине М[Q] = q/m = 0,703/0,8»0,88, получим среднее время, которое машина проводит на АЗС:
(мин).
До сих пор мы рассматривали работу одноканальной СМО с ожиданием при ограниченном числе m мест в очереди.
Теперь снимем это ограничение, т. е. устремим т к бесконечности. При этом число возможных состояний системы станет бесконечным, и граф состояний примет вид, показанный на рисунке.
Попытаемся получить вероятности состояний СМО с неограниченной очередью путем предельного перехода (при m®¥) из формул (23).
Заметим, что при этом знаменатель в последней формуле (.21) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится только, когда прогрессия бесконечно убывающая, т. е. при р < 1. Можно совершенно строго доказать, что р < 1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим; при р ³ 1 такого режима не существует, и очередь при t —>-¥ растет до бесконечности.

Предположим, что
r=l/m<1,
т. е. что предельный режим существует. Устремим в формулах (23) m к ¥' и выведем формулы для предельных вероятностей состояний в СМО без ограничений по длине очереди. Получим:
(33)
При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q = 1, A= lq = l. Среднее число заявок в очереди получим из (30) при m->¥:
(34)
Среднее число заявок в системе по формуле (5.31) при т ->¥ будет равно
(35)
Среднее время ожидания toж также получим из формулы (5.32) при т -¥:
(36)
или, в другой форме:
(37)
Среднее время пребывания заявки в СМО равно среднему времени ожидания плюс среднее время обслуживания toбсл = 1/m:
(38)
Пример 2. На железнодорожную сортировочную горку прибывают составы с интенсивностью l = 2 (состава в час). Среднее время, в течение которого горка обрабатывает состав, равно 0,4 часа. Составы, прибывшие в момент, когда горка занята, становятся в очередь и ожидают в парке прибытия, где имеются три запасных пути, на каждом из которых может ожидать один состав. Состав, прибывший в момент, когда все три запасных пути в парке прибытия заняты, становится в очередь на внешний путь. Все потоки событий — простейшие. Найти:
— среднее число составов, ожидающих очереди (как в парке прибытия, так и вне его);
— среднее время ожидания состава в парке прибытия и на внешних путях;
— среднее время нахождения состава на сортировочной станции (включая ожидание и обслуживание);
— вероятность того, что прибывший состав займет место на внешних путях
Решение. В нашем случае l — 2, m. == 1/0,4 = 2,5, l/m=р = 2/2,5 =>
= 0,8 < 1, и СМО в среднем «справляется» с поступающим на нее потоком заявок.
Среднее число составов, ожидающих очереди (как в парке прибытия, так и вне его), найдем по формуле (30):
![]()
Среднее число составов, ожидающих очереди на внешних путях, подсчитаем так: с вероятностью р5 вне парка прибытия будет ожидать один состав, с вероятностью р6 — два состава и т д., с вероятностью pk(k > 5) — (k — 4) состава.
Среднее число составов, ожидающих вне парка, будет:

Формулу для бесконечной суммы в скобках получаем предельным переходом (при m ®¥) из формулы (29):
![]()
Отсюда ![]()
Подставляя сюда р = 0,8, получим:
![]()
Вероятность того, что прибывающий состав займет место на внешних путях, определяется еще проще: она равна вероятности того, что длина очереди будет не меньше трех, т. е.
![]()
Среднее
время ожидания в парке
прибытия определяем, рассматривая различные гипотезы о
числе составов, находящихся в системе:


Для р = 0,8,m, = 2,5, получаем, что среднее время ожидания в парке прибытия равно
![]()
Что же касается среднего времени ожидания на внешних путях, то оно равно

т. е. для наших численных данных,
0.4*0.41/0.2=0.82(час)=49(мин)
Среднее время пребывания состава на сортировочной станции (считая
ожидание и обслуживание) будет равно:
![]()