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

Одноканальная СМО с отказами

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

При этом система массового обслуживания состоит только из одного канала (n=1) и на нее поступает пуассоновский поток заявок с интенсивностью l, зависящей в общем случае от времени: l = l(t).

Заявка, заставшая канал занятым, получает отказ и покидает систему. Обслуживание заявки продолжается в течение случайного времени Т_об., распределенного по показательному закону с параметром m: f(t)= me^-mt (t>0).

Из этого следует, что «поток обслуживания» - простейший, с интенсивностью m. Чтобы представить себе этот поток, вообразим один непрерывно занятый канал, который будет выдавать обслуженные заявки потоком с интенсивностью m.

Требуется найти:

1. абсолютную пропускную способность СМО (А);
2. относительную пропускную способность СМО (q);

рассмотрим единственный канал обслуживания как физическую систему S, которая может находиться в одном из двух состояний: S₀ – свободен и S₁ – занят.

Нарисуем ГСП

Рис. ГСП для одноканальной СМО с отказами.

Рис. График решения уравнения

Из состояния S₀ в S₁ систему, очевидно, переводит поток заявок с интенсивностью l; из S₁ в S₀ – «поток обслуживания» с интенсивностью m.

Вероятности состояний: p₀(t) и p₁(t). Очевидно, для любого момента t: p₀(t) + p₁(t) = 1.

Составим дифференциальное уравнение Колмогорова для вероятности состояний согласно правилу:

d p₀ / d t = -l p₀ + m p₁;

d p₁ / d t = l p₀ - m p₁.

Из этих уравнений одно является лишним, т.к. p₀ и p₁ связаны соотношением
p₀(t) + p₁(t) = 1. учитывая это, отбросим второе уравнение, а первое подставим вместо p₁ выражение (1-p₀):

dp₀ / dt = -lp_o + m(1 – p₀), (3.4)

или

dp₀ / dt = -(m + l)p₀ + m.

Поскольку в начальный момент времени канал свободен, уравнение следует решать при начальных условиях: p₀(0)=1, p₁(0)=0.

Линейное дифференциальное уравнение (3.4) легко может быть решено не только для простейшего потока заявок (l=const), но и для случая, когда интенсивность потока со временем меняется.

Для первого случая решение есть:

p₀ = m / (l + m) + l / (l + m) * e ^{–(l + m)t}.

Зависимость величины p₀ от времени имеет вид, изображенный на рисунке (стр. 30). В начальный момент времени (при t=0) канал заведомо свободен (p₀(0)=1). С увеличением t вероятность p₀ уменьшается и в пределе (при t ∞) равна m / (l + m). Величина p₁(t), дополняющая p₀(t) до 1, изменяется так, как показано на том же рисунке.

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность p₀ есть не что иное, как относительная пропускная способность q. Действительно, p₀ есть вероятность того, что заявка, пришедшая в момент времени t, будет обслужена. Следовательно. Для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно p₀ (q = p₀).

В пределе, при t ∞, когда процесс обслуживания уже установится, предельное значение относительной пропускной способности будет равно: q = m / (l + m).

Зная относительную пропускную способность q, легко найти абсолютную А. Они связаны очевидным соотношением: А = l * q.

В пределе, t ∞, абсолютная пропускная способность тоже установится и будет равна
A = l * m / (l + m).

Зная относительную пропускную способность q (вероятность того, что пришедшая в момент t заявка будет обслужена), легко найти вероятность отказа p_отк = 1 – q или среднюю часть необслуженных заявок среди поданных. При t ∞ p_отк = 1 - m / (l + m) = l / (l + m).

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

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

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

Система с ограниченной длиной очереди.

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

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

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

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

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

…

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

…

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

Нарисуем ГСП для данной системы_:

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

Все интенсивности потоков событий, переводящих систему по стрелкам слева направо, равны l, а справа налево - m. Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево – поток «освобождений» занятого канала, имеющий интенсивность m (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

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

p_k = (l / m)^k * p₀; (k = 1, 2, …m+1);

p₀ = 1 / (1 + (l / m) + (l / m)² + … +(l / m)^m+1),

или с использованием r = (l / m):

p_k = r^k * p₀; (k = 1, 2, …m+1);

p₀ = 1 / (1 + r + r² + … +r^m+1) = (1 + r + r² + … + r^m+1)^-1.

Последняя строка приведенного выражения содержит геометрическую прогрессию с первым членом 1 и знаменателем r; откуда получаем

p₀ = 1 / ((1 - r^m+2) / (1 - r) = (1 - r) / (1 - r^m+2) (3.16)

в связи с чем предельные вероятности принимают вид:

p₀ = (1 – r) / (1 - r^m+2);

p₁ = r * p₀; (3.17)

p₂ = r² * p₀;

…

p_k = r^k * p₀;

…

p_m+1 = r^m+1 * p₀.

Выражение 3.16 справедливо только при r < 1 (при r = 1 она дает неопределенность вида 0/0). Сумма геометрической прогрессии со знаменателем r = 1 равна m+2, и в этом случае
p₀ = 1 / (m + 2).

Определим характеристики СМО:

Вероятность отказа Р_отк, относительную пропускную способность q, абсолютную пропускную способность А, среднюю длину очереди r, среднее число заявок, связанных с системой k, среднее время ожидания в очереди t_ож, среднее время пребывания заявки в СМО t_смо.

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

p_отк = p_m+1 = (r^m+1 (1 - r)) / (1 - r^m+2).

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

q = 1 – P_отк = 1 – r^m+1 * (1 - r) / (1 - r^m+2))

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

А= l * q.

Средняя длина очереди. Найдем среднее число r заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины R – числа заявок, находящихся в очереди:

R = M[R].

С вероятностью p₂ в очереди стоит одна заявка, с вероятностью p₃ – две заявки, вообще с вероятностью p_k в очереди стоят k-1 заявок, и т.д., откуда:

_{m+1 m+1 m+1}

r = M[R] = S r^k * p₀ = r² * p₀ S (k - 1) * r^k-2 = r² * p₀ S k * r^k-1.

^{k=2 k=2 k=2}

Поскольку k*r^k-1 = d*r^k / dr, сумму S k * r^k-1 можно трактовать как производную по r от суммы геометрической прогрессии:

_{m m}

S k * r^{k-1 =} ( S r^k)¢ = ((r-r^m+1) / (1- r))¢ = (1 – (m+1 - mr)r^m) / (1 - r)².

^{k=1 k=1}

_m+1

Подставляя полученное выражение в r² * p₀ S k * r^k-1 и используя p₀ из (3.17), окончательно

^k=2

получим: r = (r² (1 – (m+1 - mr)r^m)) / (1-r)*(1 - r^m+2).

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

Получим далее формулу для среднего числа k заявок, связанных с системой (как стоящих в очереди, так и находящихся на обслуживании). Поскольку k = r + w, где w – среднее число заявок, находящихся на обслуживании, а k известно, то остается определить w. Поскольку канал один, число обслуживаемых заявок может равняться «0» (с вероятностью p₀) или «1» (c вероятностью 1-p₀), откуда:

w = 0 * p₀ + 1(1-p₀) = (r - r^m+2) / (1 - r^m+2),

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

k = r + (r - r^m+2) / (1 - r^m+2).

Среднее время ожидания заявки в очереди.

Обозначим его t_ож; если заявка приходит в систему в какой-то момент времени, то с вероятностью p₀ канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно 0). С вероятностью p₁ она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать обслуживания в течение времени 1/m (среднее время обслуживания одной заявки). С вероятностью p₂ в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно 2/m, и т.д.

Если же k=m+1,т.е. когда вновь приходящая заявка застает канал обслуживания занятым и m заявок в очереди (вероятность этого p_m+1), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:

t_ож = p₁* (1/m) + p₂* (2/m) + p_k* (k/m) + …+ p_m* (m/m),

если подставить сюда выражения для вероятностей, получим:

t_ож = p₀*r* (1/m) + p₀* r²*(2/m) + p₀*r^k* (k/m) + …+ p₀*r^m* (m/m) =
= (p₀r (1-(m+1-mr)r^m)) / m(1-r)² = r/m * ((1-(m+1-mr)r^m)) / (1-r)(1-r^m+2).

Здесь использованы ранее полученные соотношения (производная геометрической прогрессии), а также p₀ из (3.17).

Сравнивая это выражение с …, заметим, что

t_ож = (1 / rm) * r = r / l, иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.

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

Обозначим t_смо математическое ожидание случайной величины – время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди (t_ож) и среднего времени обслуживания (t_обсл.). Если загрузка системы составляет 100%, очевидно, t_обсл = 1/m, в противном случае t_обсл = q/m. Отсюда t_смо = t_смо + t_обсл = r / l + q/m.

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

Определить:

1. вероятность отказа;
2. относительную и абсолютную пропускные способности АЗС;
3. среднее число машин, ожидающих заправки;
4. среднее число машин, находящихся на АЗС (включая обслуживаемую);
5. среднее время ожидания машины в очереди;
6. среднее время пребывания машины на АЗС (включая обслуживание).

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

m = 1 / 1,25 = 0,8; r = l / m = 1/0,8 = 1,25.

По установленным формулам:

p₀ = (1-1,25) / (1-3,05) = 0,122;

p₁ = 1,25*0,122 = 0,152;

p₂ = 1,25*0,122 = 0,191;

p₃ = 1,25*0,122 = 0,238;

p₄ = 1,25*0,122 = 0,297.

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

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

3. Абсолютная пропускная способность СМО A = l * q = 0,703 машин в мин.

4. Среднее число машин в очереди находим по формуле

r = (1,25²(1-(3+1-3,75)1,25³)) / ((1-1,25)(1-1,25²)) = 1,56,

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

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

W = (r - r^m+2) / (1 - r^m+2) = (1,25 – 1,25⁵) / (1 – 1,25⁵) = 0,88,

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

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

t_ож = r / l = 1,56 мин.

Прибавляя к этой величине t_обсл = q/m = 0,703*0,8=0,88, получим среднее время, которое машина проводит на АЗС: t_смо = t_смо + t_обсл = 1,56+0,88 = 2,44 мин.

Дата добавления: 2014-01-07