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

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

Рис.4

 

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

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

S₀ – канал свободен,

S₁ – канал занят, очереди нет,

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

...........

S_k – канал занят, k – 1 заявок стоит в очереди,

...........

 

S_m+1 – канал занят, m заявок стоят в очереди.

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

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

(5.1)

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

(5.2)

 

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

(5.3)

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

(5.4)

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

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

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

P_отк = (5.5)

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

q = 1– P_отк = (5.6)

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

A = λ q.

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

= M[R].

С вероятностью р₂ в очереди стоит одна заявка, с вероятностью р₃ две заявки, вообще с вероятностью р_k в очереди стоят k – 1 заявок, на­конец, с вероятностью р_m+1 в очереди стоят m заявок. Среднее число заявок в очереди получим, умножая число заявок в очереди на соот­ветствующую вероятность и складывая результаты:

= 1 ·р₂+2· р₃ + … + (k –1) · р_k + … + m·р_m+1 =

= 1 ·ρ²р₀ + 2 ·ρ³р₀ + … + (k –1) ρ^kр₀ +… + m·ρ^m+1р₀. (5.7)

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

= ρ²р₀ [1+ 2 ρ + … + (k –1) ρ^k-2 + … + mρ^m-1 ]. (5.8)

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

= ρ + ρ² + … + ρ^k-1 + … + ρ^m

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

(5.9)

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

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

1+ 2 ρ + … + (k –1) ρ^k-2 + … + mρ^m-1 = (5.10)

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

= ρ²р₀

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

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

(5.11)

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

K = R + Ω

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

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

= M[K] = M[R] + M[ Ω ] = +

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

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

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

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

= 0· p₀ + 1·(1- p₀) =

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

= + (5.12)

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

Выведем выражение еще для одной существенной характеристики СМО с ожиданием: среднего времени ожидания заявки в очереди. Обо­значим _ож. Пусть заявка проходит в систему в какой-то момент времени. С вероятностью р₀ канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероят­ностью p₁ она придет в систему во время обслуживания какой-то заяв­ки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени l/μ (среднее время обслуживания одной заявки). С вероятностью р₂ в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно 2/μ, и т. д. Вообще, с вероятностью p_k пришедшая заявка застанет в системе k заявок и будет ждать в среднем k /μ единиц времени; здесь k может быть любым целым числом до m. Что же касается k = m + 1, т. е. случая, когда вновь приходящая заявка застает канал обслужи­вания, занятым и еще m заявок в очереди (вероятность этого р_m+1), то время ожидания в этом случае также равно нулю, потому что заявка не становится в очередь (и не обслуживается) Поэтому среднее время ожидания будет:

_ож =

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

_ож =

 

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

_ож =

 

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

_ож = (5.13)

 

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

_ож = , (5.14)

 

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

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

T_сист = T_ож + Θ

где T_ож – время ожидания заявки в очереди, Θ – случайная вели­чина, равная времени обслуживания Т_об, если заявка обслуживается, и нулю, если она не обслуживается (получает отказ). По теореме сложения математических ожиданий:

_сист = M[ T_сист ] = M[ T_ож ] + M[Θ],

но, в наших обозначениях, M[ T_ож ] = _ож, а M[Θ] = q _об = q /μ. Отсю­да находим: _сист = _ож + q /μ, или, с учетом формулы (5.4),

_сист = (5.15)

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

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

- относительную и абсолютную пропускную способности GM0;

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

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

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

- среднее время пребывания машины на АЗС (включая обслуживание).

Решение. Находим приведенную интенсивность потока заявок:

μ= 1/1,25 = 0,8; ρ=λ/μ = 1/0,8=1,25.

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

p₀ = , p₁ = 1,25·0,122 0,125,

p₂ = 1,25· p₁ 0,191, p₃ = 1,25· p₂ 0,238,

 

p₄ = 1,25· p₃ 0,297

 

Вероятность отказа Р_отк 0,297.

Относительная пропускная способность СМО q = 1 – Р_отк = 0,703.

Абсолютная пропускная способность СМО А = λ q = 0,703 (машины в мин.)

Среднее число машин в очереди находим по формуле (5.11)

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

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

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

= + 2,44

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

_ож = = l,56 (мин).

Прибавляя к этой величине M[Θ] = q /μ = 0,703/0,8 0,88, получим сред­нее время, которое машина проводит на АЗС:

_сист = 1,56 + 0,88 = 2,44 (мин).

 

 

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

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

Рис.5

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

Заметим, что при этом знаменатель в последней формуле (5.2) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится только, когда прогрес­сия бесконечно убывающая, т, е. при ρ < 1. Можно со­вершенно строго доказать, что ρ < 1 есть условие, при котором в СМО с ожиданием существует предельный установившийся режим; при ρ ≥ 1 такого режима не существует, и очередь при t →∞ растет до бесконечности.

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

ρ = λ/μ < 1,

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

(5.16)

При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому q = 1, A = λ q =λ. Среднее число заявок в очереди получим из (5.11) при m →∞:

(5.17)

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

= + ρ = . (5.18)

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

_ож = (5.19)

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

_ож = (5.20)

Среднее время пребывания заявки в СМО равно среднему времени ожидания плюс среднее время обслуживания _обсл = 1/μ:

_сист = (5.21)

 

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

Найти:

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

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

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

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

Решение. В нашем случае l = 2, μ = 1/0,4 = 2,5, ρ = λ/μ = 2/2,5 = 0,8 < 1, и СМО в среднем «справляется» с поступающим на нее потоком зая­вок.

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

Среднее число составов, ожидающих очереди на внешних путях, подсчи­таем так: с вероятностью р₅ вне парка прибытия будет ожидать один состав, с ве­роятностью р₆ – два состава и т д., с вероятностью p_k (k > 5) – (k – 4) состава.

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

= 1 p₅ + 2 p₆ + … + (k –4) p_k + … = 1(1– ρ) ρ ⁵ + 2(1– ρ) ρ ⁶ + … +

+ … + (k – 4)(1– ρ) ρ^k + … = (1 – ρ) ρ ⁵ [1 + 2 ρ + 3 ρ² + … ]

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

1 + 2 ρ + 3 ρ² + …= . (5.22)

Подставляя сюда ρ = 0,8, получим:

= 1,64.

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

p₄ + p₅ + p₆ + … = (1 – ρ) ρ ⁴ + (1 – ρ) ρ ⁵ + (1 – ρ) ρ ⁶ + … =

= (1 – ρ) ρ ⁴ (1 + ρ + ρ² + …) = ρ⁴ = 0,8⁴ 0,41

 

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

Для ρ = 0,8, μ = 2,5, получаем, что среднее время ожидания в парке прибытия равно

=0,78 (час) 47 (мин)

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

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

0,4×0,41/0,2=0,82 (час) 49 (мин).

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

_сист = 0,82 + 0,78 + 0,4 = 2 (час).