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

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание — простейший поток с интенсивно­стью λ,. Интенсивность потока обслуживания равна μ, (т. е. в сред­нем непрерывно занятый канал будет выдавать μ обслуженных за­явок). Длительность обслуживания — случайная величина, подчи­ненная показательному закону распределения. Поток обслужива­нии является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.

Предположим, что независимо от того, сколько требований по­ступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N -требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены об­служиваться в другом месте. Наконец, источник, порождающий за­явки на обслуживание, имеет неограниченную (бесконечно боль­шую) емкость.

Граф состояний СМО в этом случае имеет вид, показанный на рис. 2

 

Рисунок 5.2 – Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)

 

Состояния СМО имеют следующую интерпретацию:

S0 — «канал свободен»;

S1 — «канал занят» (очереди нет);

S2 — «канал занят» (одна заявка стоит в очереди);

Sn — «канал занят» (п — 1 заявок стоит в очереди);

SN — «канал занят» (N — 1 заявок стоит в очереди).

Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:

 

(10)

п — номер состояния.

Решение приведенной выше системы уравнений (10) для на­шей модели СМО имеет вид

(11)

 

 

(12)

 

Тогда

Следует отметить, что выполнение условия стационарности

для данной СМО не обязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превы­шать N — 1), а не соотношением между интенсивностями входного потока, т. е. не отношением λ/μ=ρ

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N — 1):

вероятность отказа в обслуживании заявки:

(13)

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

(14)

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

(15)

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

(16)

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

(17)

средняя продолжительность пребывания клиента (заявки) в очереди:

 

(18)

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

(19)

Рассмотрим пример одноканальной СМО с ожиданием.

Пример 2. Специализированный пост диагностики представ­ляет собой одноканальную СМО. Число стоянок для автомоби­лей, ожидающих проведения диагностики, ограниченно и равно 3[(N — 1) = 3]. Если все стоянки заняты, т. е. в очереди уже нахо­дится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток ав­томобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность λ = 0,85 (автомобиля в час). Вре­мя диагностики автомобиля распределено по показательному зако­ну и в среднем равно 1,05 час.

Требуется определить вероятностные характеристики поста ди­агностики, работающего в стационарном режиме.

Решение

1. Параметр потока обслуживаний автомобилей:

2. Приведенная интенсивность потока автомобилей определя­ется как отношение интенсивностей λ, и μ, т. е.

3. Вычислим финальные вероятности системы

4. Вероятность отказа в обслуживании автомобиля:

 

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

6. Абсолютная пропускная способность поста диагностики

(автомобиля в час).

7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

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

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

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

Работу рассмотренного поста диагностики можно считать удов­летворительной, так как пост диагностики не обслуживает автомо­били в среднем в 15,8% случаев (Р_отк = 0,158).

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

Стационарный режим функционирования данной СМО суще­ствует при t →∞ оо для любого n = 0, 1, 2, ... и когда λ < μ. Система алгебраических уравнений, описывающих работу СМО при t →∞ для любого n = 0, 1, 2, ... , имеет вид

 

(20)

Решение данной системы уравнений имеет вид

(21)

где ρ = λ/μ < 1.

Характеристики одноканальной СМО с ожиданием, без огра­ничения на длину очереди, следующие:

• среднее число находящихся в системе клиентов (заявок) на обслуживание:

(22)

средняя продолжительность пребывания клиента в системе:

(23)

среднее число клиентов в очереди на обслуживании:

(24)

 

средняя продолжительность пребывания клиента в очереди:

(25)

Пример 3. Вспомним о ситуации, рассмотренной в примере 2, где речь идет о функционировании поста диагностики. Пусть рассматриваемый пост диагностики располагает неограниченным количеством площадок для стоянки прибывающих на обслужива­ние автомобилей, т. е. длина очереди не ограничена.

 

Требуется определить финальные значения следующих вероят­ностных характеристик:

вероятности состояний системы (поста диагностики);

- среднее число автомобилей, находящихся в системе (на обслу­живании и в очереди);

- среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди);

- среднее число автомобилей в очереди на обслуживании;

- среднюю продолжительность пребывания автомобиля в очереди.

Решение

 

1. Параметр потока обслуживания μ и приведенная интенсив­ность потока автомобилей ρ определены в примере 2:

μ= 0,952; ρ = 0,893.

 

2. Вычислим предельные вероятности системы по формулам

Р₀ = 1 - ρ = 1 - 0,893 = 0,107;

Р₁ = (1 - ρ) . ρ = (1 - 0,893)*0,893 = 0,096;

Р₂ = (1 - ρ) . ρ² = (1 - 0,893)*0,8932 = 0,085;

Р_з = (1 - ρ) . ρ³ = (1 - 0,893)*0,8933 = 0,076;

Р₄ = (1 - ρ) . ρ ⁴ = (1 - 0,893)* 0,8934 = 0,068;

Р₅ = (1 - ρ) . ρ⁵ = (1 - 0,893)*0,8935 = 0,061 и т. д.

Следует отметить, что Р₀ определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаива­ет). В нашем примере она составляет 10,7%, так как Р₀ = 0,107.

3. Среднее число автомобилей, находящихся в системе (на об­служивании и в очереди):

 

4. Средняя продолжительность пребывания клиента в системе:

 

 

5. Среднее число автомобилей в очереди на обслуживание:

 

 

6. Средняя продолжительность пребывания автомобиля в очереди:

 

 

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

q = 1,

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

 

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

А = λ* q = 0,85 * 1 = 0,85.

Следует отметить, что предприятие, осуществляющее диагнос­тику автомобилей, прежде всего интересует количество клиентов, которое посетит пост диагностики при снятии ограничения на длину очереди.

Допустим, в первоначальном варианте количество мест для сто­янки прибывающих автомобилей было равно трем (см. пример 2). Частота m возникновения ситуаций, когда прибывающий на пост диагностики автомобиль не имеет возможности присоединиться к очереди:

 

m=λ*P_N

 

В нашем примере при N = 3 + 1 = 4 и ρ = 0,893

 

m=λ*P₀*ρ⁴=0.85*0.248*0.8934=0.134 автомобиля в час.

 

При 12-часовом режиме работы поста диагностики это эквива­лентно тому, что пост диагностики в среднем за смену (день) будет терять 12 * 0,134 = 1,6 автомобиля. Снятие ограничения на длину очереди позволяет увеличить ко­личество обслуженных клиентов в нашем при мере в среднем на 1,6 автомобиля за смену (12 ч. работы) поста диагностики. Ясно, что ре­шение относительно расширения площади для стоянки автомоби­лей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей кли­ентов при наличии всего трех мест для стоянки этих автомобилей.

 

4.4 Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания

 

В подавляющем большинстве случаев на практике системы мас­сового обслуживания являются многоканальными, и, следователь­но, модели с n обслуживающими каналами (где n > 1) представляют несомненный интерес.

Процесс массового обслуживания, описываемый данной моде­лью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняет­ся l/μ. Входной и выходной потоки являются пуассоновскими. Ре­жим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих ка­налов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения. Конечная цель исполь­зования n параллельно включенных обслуживающих каналов за­ключается в повышении (по сравнению с одноканальной систе­мой) скорости обслуживания требований за счет обслуживания од­новременно n клиентов.

Граф состояний многоканальной системы массового обслужи­вания с отказами имеет вид, показанный на рис. 4.3.

 

 

Состояния данной СМО имеют следующую интерпретацию:

S₀ - все каналы свободны;

S₁ - занят один канал, остальные свободны;

……………………….

S_k - заняты ровно k каналов, остальные свободны;

……………………….

S_n - заняты все n каналов, заявка получает отказ в обслужива­нии.

Уравнения Колмогорова для вероятностей состояний системы Р₀, …, P_k,…, Р_n будут иметь следующий вид:

(26)

 

Начальные условия решения системы таковы:

P₀(0)=1, P₁(0)=P₂(0)=…=P_k(0)=…=P_n(0)=0.

Стационарное решение системы имеет вид:

(27)

где .

 

Формулы для вычисления вероятностей P_k называются форму­лами Эрланга.

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

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

(28)

так как заявка получает отказ, если приходит в момент, когда все n каналов заняты. Величина Р_отк характеризует полноту обслужива­ния входящего потока;

- вероятность того, что заявка будет принята к обслуживанию (она же — относительная пропускная способность системы q) допол­няет Р_отк до единицы:

(29)

 

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

 

A=λ*q=λ*(1-P_отк); (30)

 

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

 

(31)

Оно характеризует степень загрузки системы.

Пример 4. Пусть n-канальная СМО представляет собой вы­числительный центр (ВЦ) с тремя (n = 3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступаю­щих на ВЦ, имеет интенсивность λ = 1 задаче в час. Средняя про­должительность обслуживания t_обсл = 1,8 час. Поток заявок на ре­шение задач и поток обслуживания этих заявок являются простей­шими.

Требуется вычислить финальные значения:

- вероятности состояний ВЦ;

- вероятности отказа в обслуживании заявки;

- относительной пропускной способности ВЦ;

- абсолютной пропускной способности ВЦ;

- среднего числа занятых ПЭВМ на ВЦ.

Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.

Решение

1. Определим параметр μ потока обслуживании:

2. Приведенная интенсивность потока заявок

ρ=λ/μ=1/0.555=1.8

3. Предельные вероятности состояний найдем по формулам Эр-
ланга (27):

 

P₁=1.8*0.186=0.334;

P₂=1.62*0.186=0.301;

P₃=0.97*0.186=0.180.

 

4. Вероятность отказа в обслуживании заявки

P_отк=P₃=0.180

5. Относительная пропускная способность ВЦ

q = 1 - P_отк = 1 - 0.180 = 0,820.

6. Абсолютная пропускная способность ВЦ

А = λ • q = 1 • 0,820 = 0,820.

7. Среднее число занятых каналов — ПЭВМ

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех — остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно счи­тать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (P₃ =0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.

Определим, сколько нужно использовать ПЭВМ, чтобы сокра­тить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу (28):

Составим следующую таблицу:

n
P0	0,357	0,226	0,186	0,172	0,167	0,166
Pотк	0,643	0,367	0,18	0,075	0,026	0,0078

 

Анализируя данные таблицы, следует отметить, что расшире­ние числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение за­дач на 99,22%, так как при п = 6 вероятность отказа в обслужива­нии (Р_отк) составляет 0,0078.

 

4.5 Многоканальная система массового обслуживания с ожиданием

Процесс массового обслуживания при этом характери­зуется следующим: входной и выходной потоки являются пуассоновскими с интенсивностями λ и μ соответственно; параллельно обслуживаться могут не более С клиентов. Система имеет С кана­лов обслуживания. Средняя продолжительность обслуживания одного клиента равна

 

В установившемся режиме функционирование многоканальной СМО с ожиданием и неограниченной очередью может быть описа­но с помощью системы алгебраических уравнений:

(32)

Решение системы уравнений (32) имеет вид

(33) (34)

 

где

(35)

Решение будет действительным, если выполняется следующее условие:

Вероятностные характеристики функционирования в стационар­ном режиме многоканальной СМО с ожиданием и неограниченной оче­редью определяются по следующим формулам:

• вероятность того, что в системе находится n клиентов на обслу­живании, определяется по формулам (33) и (34);

• среднее число клиентов в очереди на обслуживание

(36)

 

• среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди)

Ls=Lq + ρ (37)

• средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди

(38)

• средняя продолжительность пребывания клиента в системе

(39)

Рассмотрим примеры многоканальной системы массового об­служивания с ожиданием.

Пример 5. Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неис­правных механизмов, прибывающих в мастерскую, — пуассоновский и имеет интенсивность λ= 2,5 механизма в сутки, среднее время ремонта одного механизма распределено по показательному закону и равно t = 0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской мо­жет расти практически неограниченно.

Требуется вычислить следующие предельные значения вероят­ностных характеристик системы:

- вероятности состояний системы;

- среднее число заявок в очереди на обслуживание;

- среднее число находящихся в системе заявок;

- среднюю продолжительность пребывания заявки в очереди;

- среднюю продолжительность пребывания заявки в системе.

Решение

1. Определим параметр потока обслуживаний

μ = 1/t=1/0,5 = 2.

2. Приведенная интенсивность потока заявок

ρ = λ/μ = 2,5/2,0 = 1,25,

при этом λ/μ *с= 2,5/2 * 3 = 0,41.

Поскольку λ/μ * с <1 , то очередь не растет безгранично и в сис­теме наступает предельный стационарный режим работы.

3. Вычислим вероятности состояний системы:

4. Вероятность отсутствия очереди у мастерской

5. Среднее число заявок в очереди на обслуживание

6. Среднее число находящихся в системе заявок

L_s = L_q +ρ = 0,111 + 1,25 = 1,361.

7. Средняя продолжительность пребывания механизма в очереди на обслуживание

8. Средняя продолжительность пребывания механизма в мас­терской (в системе)

 

 

Развернуть

Открыть в широком формате