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

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

Примерами таких систем являются различные системы связи, ремонтные мастерские, вычислительные комплексы, различные объекты из сферы обслуживания.

3.1.1. Структура простейшей системы массового обслуживания.

агрегат

Входной

поток но Выходной

поток

заявок

Выходной поток

Рис. 3.1.

Возможные ситуации:

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

2.При поступлении заявки агрегат занят, заявка ставится в очередь в запоминающее устройство (ЗУ), если там есть место.

3.Если в ЗУ нет места, заявка покидает систему массового обслуживания (отказ).

4. При освобождении агрегата заявка из очереди (ЗУ) поступает на обслуживание.

5. Если заявки нет и агрегат свободен, то система простаивает.

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

Заявки поступают в системы обслуживания обычно не регулярно, а случайно, образуя так называемый случайный поток событий. Обслуживание заявок тоже может быть случайным процессом и может зависеть от многих факторов. Эти обстоятельства приводят к тому, что система оказывается загруженной неравномерно, а качество обслуживания заявок зависит от степени загруженности системы.

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

-показатели эффективности использования системы массового обслуживания;

-показатели качества обслуживания заявок.

Рассмотрим три основных типа систем массового обслуживания:

1.Система массового обслуживания с отказом, т.е. рассматривается ситуация, когда заявка покидает систему, если все каналы заняты.

2.Система массового обслуживания с ожиданием, т.е, вариант, когда заявка ставится в очередь и стоит там до тех пор, пока она не будет обслужена.

3.Смешанный тип. В этом случае заявка стоит в очереди определенное время, либо очередь имеет предельную длину.

3.1.2. Система массового обслуживания с отказом. Одноканальная система.

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

Одноканальная система может находиться в одном из двух возможных состояний:

S₀-система свободна;

S₁ -система занята обслуживанием заявки.

Граф переходов из одного состояния в другое и обратно:

µ

λ

Рис. 3.2.

Здесь " λ "-интенсивность входного потока, т.е. среднее число заявок, поступающих на обслуживание в единицу времени, а " μ "-интенснвностъ обслуживания, т.е. количество заявок обслуженных в единицу времени.

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

Р₀=μ/(λ + μ) (3.1)

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

Очевидно, что среднее время свободного состояния системы:

Т=1/λ (3.2)

Средняя длительность периода занятости:

т=1/ μ (3.3)

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

А=λР₀ (3.4)

Вероятность отказа любой очередной заявке:

P₁=l-Р_о (3.5)

Многоканальная система. При тех же исходных данных рассмотрим работу системы массового обслуживания с n-каналами. Для многоканальной системы с отказами граф переходов представлен на рис.3.

μ 2 μ 3 μ n μ

……

λ λ λ λ

Рис. 3.3.

Многоканальная система может находится в одном из н возмож­ных состояний:

S_y – система свободна:

S₁ - один канал системы занят обслуживанием заявки.

S₂ – два канала системы заняты обслуживанием двух заявок.

S_n – n каналов системы заняты обслуживанием n заявок.

Интенсивность обслуживания возрастает пропорционально количеству загруженных каналов.

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

P₀=(1+p/1!+p²/2!+…+pⁿ/n!)^-1 (3.6)

где p= λ / μ – коэффициент нагрузки канала, т. е. среднее число заявок. поступивших в систему за время обслуживания одной заявки.

Вероятность нахождения системы в состоянии, когда к-каналов заняты, а остальные свободны:

P_k=(p^k/k!) Po (3.7)

Заявка получает отказ, когда все каналы заняты. Вероятность отказа:

P_отк=(pⁿ/n!)Po (3.8)

Абсолютная пропускная способность многоканальной системы с отказами:

А= λ (1-Р_отк) (3.9)

Важной характеристикой такой системы является среднее число занятых каналов, которое вычисляется по формуле:

М_к=р(1-Р_отк) (3.1)

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

Одноканальная система. Рассмотрим одноканальную СМО, на вход которой поступает пуассоновский поток заявок с интенсивностью " λ ". Интенсивность обслуживания - " μ ". Пусть имеется m мест для ожидания, т. е. заявка, пришедшая в систему, когда в ней заняты все "m" мест для ожида­ния, покидает систему не обслуженной. Такая система может находится в одном из (m+2) состояний:

μμμμ

……

λλλλ

Рис.3.4.

Вероятность нахождения системы в состоянии "S₀":

Р_о=(1+p+p²+... +р^m+1)^-1

Записав эту геометрическую прогрессию в другом виде:

Р_о=(1-р)/(1-р^m+2)

Для промежуточного состояния "к" вероятность:

Р_к=р^кР_о

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

Р_отк=P_m+1=p^m+1(1-p)/(1-p^m+2)

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

q=1-Рoтк

А= λ (1-Р_отк)

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

Среднее число заявок. находящихся в фазе обслуживания:

M_w=l-P₀

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

M_к=M_r+M_w

Среднее время ожидания:

M_t=M_r/ λ

Если в СМО неограниченное число мест для ожидания, то очередь не будет расти безгранично при условии: р< 1 и тогда любая из заявок рано или поздно будет обслужена, поэтому q = 1, а абсолютная пропу­скная способность А= λ.

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

М_г=р²/(1-р)

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

М_к=М_r+р=р/(1-р)

Среднее время ожидания:

M_t=M_r/ λ

Многоканальная система. Рассмотрим n–канальную СМО с ожиданием при тех же исходных данных. Граф переходов для этой системы:

μ 2 μ n μ n μ n μ n μ

λλλλλλ

Рис.3.5.

Выражения для вероятностей:

где р^~=р/n

Р_отк=P_n+m=n=(p^n+m/n^mn!)P₀

Q=l-Р_отк

А = λ /(1-P_oтк),

M_r=(P₀р^п-1/(n*n!))(1-(m+1-mр^~)*р^~m)/(1-р^~)²)

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

М_с= λ / μ

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

Мк=М_г+М_g

Среднее время ожидания:

M_t=M_r/A

Если в СМО неограниченное число мест для ожидания, то очередь не будет расти безгранично при условии: р=р/n< 1 и тогда любая из заявок рано или поздно будет обслужена, поэтому q = 1, а абсолютная пропускная способность А= λ.

M_r=P₀pⁿ⁺¹/(n*n!)(l-p)²)

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

М_г=А/μ

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

М_К=М_Г+ М_g

Среднее время ожидания:

М_t=М_r/λ

Что Вы должны знать:

(вопросы для самоконтроля

1. Какова функциональная схема СМО?

2. Что является входным потоком в СМО?

3. Какими способами определяются интенсивности входного потока и обслуживания?

4. Зачем нужны характеристики СМО?

5. При каком условии СМО будет работать устойчиво?

6. Каким образом можно оценить деятельность СМО с помощью характеристик?

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

Примеры для закрепления:

Определить оптимальное число телефонных номеров в магазине при условии, что вероятность безотказной работы будет более 0,8, заявки на переговоры поступают с интенсивностью, равной 90 заявок в час, а средняя продолжительность разговора по телефону равна 2 минуты.

1) Решим задачу для одноканальной СМО с отказами.

l=90

t=1/30 (2 минуты равны 1/30 часа)

m=1/t=30

Р_отк=1-Р₀=1-m/(l+m)=90/(90+30)=0,75

q=1- Р_отк=0,25

При одном телефонном номере без ожидания вероятность безотказной работы равна 0,25.

2) Решим эту же задачу при условии, что телефонных номеров два.

n=2

l=90

t=1/30 (2 минуты равны 1/30 часа)

m=1/t=30

r=l/m=3

P₀=(1+p/1!+p²/2!+…+pⁿ/n!)^-1=1/1+3+4,5)=0,118

P_отк=(pⁿ/n!)Po=(3²*0,118)/2=0,53

q=1- Р_отк=0,47

При двух телефонных номерах без ожидания вероятность безотказной работы будет равна 0,47

Продолжите решение этой задачи и найдите, сколько телефонных номеров минимум необходимо для обеспечения безотказной работы с вероятностью не ниже 0,8.

3) Решим эту задачу для одноканальной СМО с ожиданием. Допустим, что длина очереди равна 1.

m=1

l=90

t=1/30 (2 минуты равны 1/30 часа)

m=1/t=30

r=l/m=3

Р_о=(1-р)/(1-р^m+2)=(1-3)/(1-3³)=0,077

Р_отк=P_m+1=p^m+1(1-p)/(1-p^m+2)=3²*0,077=0,66

q=1- Р_отк=0,34

При одном канале и одном месте для ожидания вероятность безотказной работы равна 0,34.

Сколько мест для ожидания необходимо как минимум для достижения вероятности безотказной работы не менее 0,8?