Системы массового обслуживания с ожиданием

В качестве показателей эффективности СМО с ожиданием, кроме уже известных показателей – абсолютной А и относительной Q пропускной способности, вероятности отказа ρ_отк, среднего числа занятых каналов К будем рассматривать также следующие:

L_сист – среднее число заявок в системе;

Т_сист – среднее время пребывания заявки в системе;

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

Т_оч – среднее время пребывания заявки в очереди;

P_зан – вероятность того, что канал занят(степень загрузки канала).

 

Одноканальная система с неограниченной очередью

(например, телефон- автомат с одной буквой).

Имеется одноканальная СМО с интенсивностью потока заявок λ и потока обслуживания М. Необходимо найти предельные вероятности состояний и показатели эффективности СМО.

Система может находиться в одном из состояний:S₀, S₁ , S₂,…, S_k, по числу заявок, находящихся в СМО. S₀ – канал свободен; S₁ - канал занят, очереди нет; S₂ – канал занят, одна заявка в очереди; …, S_k – канал занят, (k-1) заявок стоит в очереди.

Граф состояний СМО представлен на рисунке 9.7

… …

Sk

… …

S2

S1

S0

λ λ λ λ λ

 

μ μ μ μ μ

Этот процесс гибели и размножения, но с бесконечным числом состояний. Используя формулы(9.5) с учетом бесконечного числа состояний системы, получим:

ρ₀ =(1++( )² +…+()^k+…)^-1= (1+ρ+ρ²+…+ρ^k+…)^-1 (9.7)

Выражение, записанное в скобках(9.7) есть геометрическая прогрессия с суммой, равной , поэтому: ρ₀=1-ρ.

Поэтому предельные вероятности других состояний будут:

ρ₁= ρ(1- ρ); ρ₂ = ρ²(1- ρ);…; ρ_k = ρ^k(1- ρ) (9.8)

Они составляют убывающую прогрессию со знаменателем ρ <1.

- среднее число число заявок в системе L_сист.

Определим по формуле математического ожидания, которая с учетом(9.8) примет вид:

∞ ∞

L_сист.= ∑Кρ_k =(1-ρ) ∑ Кρ^k (9.9)

k-1 k-1

 

Можно показать, что формула (9.9) при (ρ<1) преобразуется к виду:

 

L_сист =(9.10)

- Среднее число заявок в очереди L_оч

 

L_оч = L_сист – L_об (9.11)

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

L_об равно вероятности того, что канал занят:

L_об. = ρ_зан. = 1- ρ₀

L_об. = ρ_зан. = ρ (9.12)

Теперь по формуле (9.11) с учетом(9.10) и (9.12)

L_оч= – ρ = ρ²/(1-ρ) (9.13)

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

Т_сист.= L_сист /λ = (9/14)

 

- среднее время пребывания заявки в очереди

 

Т_оч.= L_оч/λ = ρ²/λ(1-ρ) (9.15)

Формулы (9.14) и (9.15) называются формулами Литтла.

Пример 9.5

В порту имеется один причал. Интенсивность потока судов λ=0.4 (судов в сутки), среднее время разгрузки одного судна t_об =2 суток. Найти показатели эффективности работы причала, и также вероятность того, что ожидают разгрузки не более чем 2 судна.

Решение:

Имеем:

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

ρ₀ ==λt_об =0.4*2=0.8<1

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

Найдем их:

- вероятность того, что причал свободен

ρ₀=1-ρ =1-0.8=0.2

- вероятность того, то он занят

Ρ_зан=1-0.2=0.8

- вероятность того, что у причала находятся 1, 2 ,3 судна(т.е ожидают разгрузки) (9.8)

ρ₁=ρ(1-ρ) =0.8(1-0.8)=0.16

ρ₂=ρ²(1-ρ) =0.8²(1-0.8)=0.128

ρ₃=ρ³(1-ρ) =0.8³(1-0.8)=0.1024

- вероятность того, что ожидают разгрузку не более чем 2 судна

ρ=ρ₁+ ρ₂+ ρ₃=0.16+0.128+0.1024=0.3904

- среднее число судов, ожидающих разгрузки (9.13)

L_оч= ρ²/(1-ρ)=0.8²/(1-0.8)=3.2 (судов)

 

- среднее время разгрузки (9.15)

 

Т_оч.= L_оч/λ = 3.2/0.8= 4(суток)

- среднее число находящихся у причала (9.10)

L_сист ==0.8/(1-0.8)=4 (судна)

- среднее время пребывания у причала (9.14)

Т_сист.= L_сист /λ =4/0.8=5 (суток)

Очевидно,что эффективность разгрузки невысокая. Для ее повышения необходимо уменьшить среднее время разгрузки t_об, либо увеличить число причалов.

 

 

Оценить эффективность работы кафе.

 

T_сист

T_оч

 

 

 

 

T_сист

T_оч

 

 

 

 

ρ

 

 

Пример 9.6

Посетители посещают кафе группами с интенсивностью λ = 1 группа в час.

Обслуживание в кафе продолжается Т _сист = 2/3 часа = 0,6667.

Прежде всего определим приведенную интенсивность потока посетителей

 

ρ = λ / μ = λ / (1 / Т _сист) = 1 / (1 / 0,0667)

 

- среднее число групп посетителей, одновременно обслуживаемых кафе (9.10):

 

L _сист = ρ /(1 - ρ) = 0,6667 / (1 – 0,6667) = 2 группы

 

- среднее время пребывания группы в кафе ( 9.14)

 

Т _сист = L _сист / λ = 2/1 = 2 часа

 

- среднее число групп, находящихся в очереди ( 9.13)

 

L _оч = ρ ² / ( 1 – ρ ) = 0,6667² / ( 1 – 0,6667) = 1,3336 группы

 

- среднее время пребывания группы в очереди (9.15)

 

Т _оч = L _оч / λ = 1,3336 / 1 = 1,3336 часа

 

Такое время ожидания для посетителей не приемлемо. Можно ли уменьшить время обслуживания групп. Построим зависимости времени ожидания в очереди Т _оч и времени пребывания в кафе Т _сист от интенсивности потока групп посетителей. Это можно сделать. Если уменьшить относительную интенсивность потока групп ρ = λ / μ.

Из рис.9.8 видно, что при уменьшении ρ в 2 раза и сохранение одной и той же интенсивности λ = 1, среднее время обслуживания группы Т _сист уменьшится с 2 до 0,5 часа, т.е. в 4 раза. При этом среднее время ожидания групп, находящихся в очереди сократятся ≈ в 8 раз ( 1,3336 до 0,6667 ). Это произойдет за счет увеличения интенсивности обслуживания ( с μ = 1,5 группы в час при ρ = 0,6667 до с μ = 3 группы в час при ρ = 0,3333).

 

 

Многоканальная СМО с неограниченной очередью.

Имеется n – канальная СМО с неограниченной очередью. Поток заявок имеет интенсивность λ, а поток обслуживаний – интенсивность μ. Необходимо найти предельные вероятности и показатели ее эффективности.

Граф состояний системы показан на рис. 9.9

 

λ λ λ λ λ λ λ λ λ

Sn+τ

Sn+1

S n

S k

S 1

S 0

… … … …

… … … …

μ 2 μ k μ (k+1) μ n μ n μ n μ n μ n μ

 

 

S ₀ – в системе нет заявок

S ₁ – занят один канал остальные свободны и т.д.

И до S _n – заняты все каналы, в очереди 1 заявка.

Интенсивность потока обслуживания по мере увеличения заявок от 0 до n, увеличивается от μ до n μ . при числе заявок в СМО большем, чем n, интенсивность потока обслуживания сохраняется равной n μ.

Используя формулы (9.4) для процесса гибели и размножения, получаются формулы предельных вероятностей, состояний n – канальной СМО с неограниченной очередью.

p₀ = ( 1 + (ρ / 1!) + (ρ² / 2!) + . . . + (ρⁿ / n!) + (ρⁿ⁺¹ / n!(n- ρ)) ) ^-1

(9.16)

p₁ = (ρ / 1!) p₀ ; . . .; p_k = (ρ^k / k!) p₀ ; . . . ; p_n = (ρⁿ / n!) p₀ ;

 

p_n+1 = (ρⁿ⁺¹ / n*n!) p₀ ; . . .; p_n+τ = (ρ^n+τ / n^τ *n!) p₀

 

Вероятность того, что заявка окажется в очереди

 

р _оч = (ρⁿ⁺¹ / n!(n- ρ)) p₀ , (9.17)

 

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

_

к = λ / μ = ρ (9.18)

 

- средне число занятых в очереди

 

L _оч = (ρⁿ⁺¹ * p₀) / n*n! (1 – p/n)² (9.19)

 

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

 

L _сист = L _оч + ρ (9.20)

 

Среднее время пребывания заявок в системе и среднее время пребывания заявки в очереди находятся по формулам Лита (9.14), (9.15)

Для СМО с неограниченной очередью при ρ < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа ρ _отк = 0, относительная пропускная спасобность Q = 1, а абсолютная пропускная способность равно интенсивности входящего потока заявок, т.е. А = λ.

 

Пример 9.7

В универсаме к узлу расчета поступает поток покупателей с интенсивностью λ = 81

_

чел/час. Средняя продолжительность обслуживания кассиром одного покупателя t _об = 2 мин.

Определим минимальное количество кассиров n _min , при котором очередь не будет расти до бесконечности и соответствующие характеристики обслуживания при n = n _min .

По условию λ = 81(1/τ) = 81/60 = 1,35 1/мин

_

ρ = λ / μ = λ t _об = 1,35 * 2 = 2,7. Т.о. минимальная СМО при n = 3.

Вероятность того, что в узле расчета отсутствуют покупатели, по формуле 9.26

 

p₀ = ( 1 + (ρ / 1!) + (ρ² / 2!) + (ρ³ / 3!) + (ρ⁴ / 3!(n- ρ)) ) ^-1 = (1 + 1,27 + 2,7² / 2! + 2,7³ / 3! + 2,7⁴ / 3! (3-2,7)) ^-1 = 0,025

 

т.е. в среднем 2,5% времени кассиры будут простаивать.

Вероятность того, что в узле расчета будет очередь по (9.17)

 

р _оч = (ρⁿ⁺¹ / n!(n- ρ)) p₀ = (2,7⁴ / 3! (3 – 2,7)) 0,025 = 0,735

 

- среднее число покупателей, находящихся в очереди по (9.19)

 

L _оч = ((ρⁿ⁺¹ ) / n*n! (1 – p/n)²) p₀ = (2,7⁴ / 3 3! (1 – 2,7 / 3)²) 0,025 = 7,35

 

- среднее время ожидания в очереди по (9.15)

 

Т _оч = L _оч / λ = 7,35 / 1,35 = 5,44 (мин)

 

- среднее число покупателей в узле рассчитано

 

L _сист = L _оч + ρ = 7,35 + 2,7 = 10,05

 

-среднее время нахождения покупателей в узле расчета по (9.14)

 

Т _сист = L _сист / λ = 10,05 / 1,35 = 7,44 (мин)

 

- среднее число кассиров по (9.18)

_

к = λ / μ = ρ = 2,7

 

Абсолютная пропускная способность зла расчета

 

А = λ = 1,35 1/мин или 81(1/час), т.е. 81 покупатель в час

 

Анализ характеристик обслуживания свидетельствует о значительной перегрузке узла расчета при наличии 3 кассиров.

 

 

Литература

 

1. Е.С. Вентцель. «Исследование операций» – М. 2004 г.
2. «Исследование операций в экономике». Под редакцией проф. Н.Ш. Кремера – М. «Юнити», 1997 г.
3. Г.И. Просветов «Математические методы в экономики»– М. 2004 г.
4. Е.М. Кудрявцев «Исследование операций в задачах, алгоритмах и программах» – М. «Радио и связь» 1984 г.