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

 

Рассмотрим сначала простейшую из всех возможных СМО с ожиданием — одноканальную систему (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(мин)

 

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