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

Простейшей одноканальной моделью с вероятностным входным потоком и процедурой обслуживания является модель, которая «может характеризоваться показательным распределением длительностей интервалов между поступлениями заявок и распределением длительностей обслуживания». При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид:

f 1 (t) = л*e (-л*t) , (1)

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

f 2 (t)=µ*e -µ*t , µ=1/t об, (2)

где µ-интенсивность обслуживания, t об -среднее время обслуживания одного клиента. Относительная пропускная способность обслуженных заявок относительно всех поступающих вычисляется по формуле:

Эта величина равна вероятности, что канал обслуживания свободен. Абсолютная пропускная способность (А) -- среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:

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

Пример. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания для мойки автомобилей. Заявка -- автомобиль, прибывший в момент, когда пост занят, -- получает отказ в обслуживании. Интенсивность потока автомобилей л =1,0 (автомобиль в час). Средняя продолжительность обслуживания t об =1,8 часа. Требуется определить в установившемся режиме предельные значения: относительной пропускной способности q;

• - абсолютной пропускной способности А;
• - вероятности отказа Р.

Определим интенсивность потока обслуживания по формуле 2: .Вычислим относительную пропускную способность: q =.Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост автомобилей. Абсолютную пропускную способность определим по формуле: А=лЧq=1Ч0,356=0,356. Это говорит о том, что система способна осуществить в среднем 0,356 обслуживания автомобилей в час. Вероятность отказа: Р отк =1-q=1-0,356=0,644. Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании. Определим номинальную пропускную способность данной системы А ном: А ном = (автомобилей в час).

Однако в подавляющем большинстве случаев система массового обслуживания является многоканальной, то есть параллельно может обслуживаться несколько заявок. Процесс СМО, описываемый данной моделью, характеризуется интенсивностью входного потока л, при этом параллельно может обслуживаться не более n клиентов. Средняя продолжительность обслуживания одной заявки равняется 1/м. «Режим функционирования обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов - повышение скорости обслуживания заявок за счет обслуживания одновременно n клиентов.» Решение такой системы имеет вид:

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

P отк =P n =*P 0 . (7)

Заявка получает отказ, если приходит в момент, когда все каналов заняты. Величина Р отк характеризует полноту обслуживания входящего потока; вероятность того, что заявка будет принята к обслуживанию (она же - относительная пропускная способность системы) дополняет Р отк до единицы:

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

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

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

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

• - вероятности числа занятых каналов ВЦ;
• - вероятности отказа в обслуживании заявки;
• - относительной пропускной способности ВЦ;
• - абсолютной пропускной способности ВЦ;
• - среднего числа занятых ПЭВМ на ВЦ.

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

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

Предельные вероятности состояний найдем по формулам Эрланга:

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

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

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

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

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех - остальные полтора будут простаивать. Пропускную способность ВЦ при данных л и м можно увеличить только за счет увеличения числа ПЭВМ.

Краткая теория

Пусть в n-канальную систему массового обслуживания (СМО) поступает с интенсивностью простейший поток требований. Длительность обслуживания распределена по показательному закону со средним временем обслуживания . Если же все каналы обслуживания заняты, то вновь поступившее требование становится в очередь за ранее поступившими не обслуженными требованиями. Освободившийся канал приступает к обслуживанию очередного требования из очереди. Определим основные характеристики работы такой системы. Так как число требований, стоящих в очереди, может быть бесконечно большим, то и число состояний системы также может быть бесконечно большим.

Вероятность свободного состояния системы:

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

Определим основные характеристики многоканальной СМО с ожиданием. Вероятность получения отказа равна нулю. Относительная пропускная способность -это величина, которая дополняет вероятность отказа до единицы: . Абсолютная пропускная способность . Определим среднее число занятых каналов: каждый занятый канал обслуживает в единицу времени в среднем заявок, а вся система - заявок. Тогда:

Коэффициент занятости каналов обслуживания:

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

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

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

Определим среднее время ожидания заявки в очереди . Очередь образуется, если все каналов заняты. Так как интенсивность обслуживания , то поток освобожденных каналов имеет интенсивность . Если заявка поступила в момент, когда заняты все каналов и очереди нет, то время ожидания составит в среднем , а если застанет одно требование в очереди, то , и так далее. Среднее время ожидания заявок в очереди найдем, суммируя произведения среднего времени ожидания на соответствующую вероятность:

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

Формулы Литтла:

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

Коэффициент простоя каналов:

Пример решения задачи

Условие задачи

На строительном складе работают четыре кладовщика. Поток посетителей имеет с интенсивностью 2 заявки в минуту. Время обслуживания имеет показательное распределение со средним значением 1,5 минуты на заявку. Определить показатели работы склада.

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

Решение задачи

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

Абсолютная пропускная способность склада, т. е. количество обслуживаемых в единицу времени требовании, (заявки в минуту). Среднее число занятых кладовщиков . Вероятность образования очереди, т. е. вероятность того, что в момент обращения заказчика все четыре кладовщика заняты:

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

Среднее время простаивания в очереди:

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

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

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

Если сроки со сдачей контрольной работы поджимают, то тогда за деньги на сайте можно выполнить вашу контрольную работу по методам оптимальных решений .

Средняя стоимость решения контрольной работы 700 - 1200 рублей (но не менее 300 руб. за весь заказ). На цену сильно влияет срочность решения (от суток до нескольких часов). Стоимость онлайн-помощи на экзамене/зачете - от 1000 руб. за решение билета.

Все вопросы по стоимости можете задать прямо в чат, предварительно скинув условие задач и сообщив необходимые вам сроки решения. Время ответа - несколько минут.

Примеры близких по теме задач

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

Сетевое планирование - график работ
На примере решения задачи рассмотрены вопросы построения сетевого графика работ, нахождение критического пути и критического времени. Также показано вычисление параметров и резервов событий и работ - ранних и поздних сроков, общих (полных) и частных резервов.

Межотраслевая модель Леонтьева
На примере решения задачи рассмотрена межотраслевая модель Леонтьева. Показано вычисление матрицы коэффициентов прямых материальных затрат, матрицы «затраты-выпуск», матрицы коэффициентов косвенных затрат, векторов конечного потребления и валового выпуска.

1) одноканальная СМО

В предельном (стационарном) режиме система уравнений Колмогорова:

Учитывая нормировочное условие p 0 + p 1 = 1, найдем:

которые выражают среднее относительное время пребывания системы в состоянии S 0 (когда канал свободен) и S 1 (когда канал занят), т.е. определяют соответственно относительную пропускную способность системы q и вероятность отказа P отк:

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

Задача 1. Известно, что заявки в ателье поступают с интенсивностью?=90 (заявок в час), а средняя продолжительность разговора по телефону t об = 2 мин. Определить показатели эффективности работы СМО (телефонной связи) при наличии одного телефонного номера.

Решение.

Интенсивность потока обслуживания?= 1/ t об =1/2 = 0,5(1/мин) = 30 (1/ч).

Относительная пропускная способность СМО q = 30/(30+90) = 0,25, т.е. в среднем только 25% поступающих заявок осуществят переговоры по телефону. Соответственно вероятность отказа в обслуживании составит P отк = 0,75. Абсолютная пропускная способность СМО: Q = 90*0,25 = 22,5, т.е. в среднем в час будут обслужены 22,5 заявки.

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

2) многоканальная СМО

Система уравнений Колмогорова имеет вид:

В стационарном режиме:

Разрешим систему (1) относительно неизвестных p 0 , p 1 ,..., p m . Из первого уравнения:

Из второго с учетом (2):

Аналогично из третьего, с учетом (2) и (3):

и вообще, для любого k ? m:

Введем обозначение:

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

Формула (6) выражает все вероятности p k через p 0 . Воспользуемся условием:

Подставляя (7) в (6), получим, 0 ? k ? m. (8)

Формулы (7) и (8) называют формулами Эрланга. Полагая в формуле (8) k = m, получим вероятность отказа

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

Формулы Эрланга и их следствия (9), (10) выведены для случая показательного закона распределения времени обслуживания. Но исследования последних лет показали, что эти формулы остаются справедливыми при любом законе распределения времени обслуживания, лишь бы входной поток был простейшим. Также формулами Эрланга можно пользоваться (с известным приближением) и в случае, когда поток заявок отличается от простейшего (например, является стационарным потоком с ограниченным последействием). Наконец, формулами Эрланга можно приближенно пользоваться и в случае, когда СМО допускает ожидание заявки в очереди, но когда срок ожидания мал по сравнению со средним временем обслуживания одной заявки.

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

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

или или, учитывая (11) и (5)

При большом числе каналов обслуживания применяют следующие формулы, которые также называются формулами Эрланга:

При больших значениях i:

функция Лапласа.

Вероятность отказа: (9")

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

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

Задача 2. В условиях предыдущей задачи определить оптимальное число телефонных номеров в ателье, если условием оптимальности считать удовлетворение в среднем из каждых 100 заявок не менее 90 заявок на переговоры.

Решение. Интенсивность нагрузки канала по формуле (5) ? = 90/30 = 3, т.е. за время среднего (по продолжительности) телефонного разговора t об = 2 мин. поступает в среднем 3 заявки на переговоры.

Будем постепенно увеличивать число каналов (телефонных номеров) n = 2, 3, 4,... и определим по формулам (7), (10), (11) для получаемой n-канальной СМО характеристики обслуживания. Например, при n = 2

Значения характеристик СМО представим в таблице:

По условию оптимальности q ? 0,9, следовательно, в ателье необходимо установить 5 телефонных номеров (в этом случае q = 0,9). При этом в час будут обслуживаться в среднем 80 заявок (Q = 80,1), а среднее число занятых телефонных номеров (каналов)

Задача 3. Автоматическая телефонная станция обеспечивает не более 120 переговоров одновременно. Средняя продолжительность разговора 60 секунд, а вызовы поступают в среднем через 0,5 секунды. Рассматривая такую станцию как многоканальную систему обслуживания с отказами и простейшим входным потоком, определить: а) среднее число занятых каналов, б) относительную пропускную способность, в) среднее время пребывания вызова на станции с учетом того, что разговор может и не состояться.

Решение. Имеем: m = 120; ? = 1/0,5 = 2; ? = 1/60; ? = ?/? = 120.

Используя таблицы функции Лапласа, получаем:

так как? есть интенсивность входного потока (число заявок в единицу времени), то?t ср = и.

2 . СМО с ожиданием и ограниченным временем ожидания.

Имеется m каналов обслуживания, входной поток - простейший с интенсивностью?, время обслуживания и время ожидания - СВ, распределенные по экспоненциальному закону с параметрами? и? соответственно.

Если занято i каналов и i ? m, то в силу независимости их функционирования интенсивность обслуживания возрастает в i раз: ? i,i-1 = i?. При возникновении очереди каждое состояние рассматриваемой СМО характеризуется занятостью каналов обслуживания. Поэтому интенсивность освобождения каналов становится постоянной u = m?.

Закон распределения времени ожидания определяется интенсивностью? ухода из очереди при наличии в ней одной заявки. В силу независимости поступления заявок (см. определение простейшего потока) интенсивность, с которой заявки отказываются от обслуживания и уходят из очереди, равна r? (для очереди длины r ? 1). Т.о., плотность вероятности перехода системы из состояния S m+r в состояние S m+r-1 равна сумме интенсивностей освобождения каналов обслуживания и отказа от обслуживания: ? m+r,m+r-1 = m? + r?.

Составим уравнения Колмогорова:

i=1,..., m-1, r ? 0.

Если на длину очереди не накладывать ограничений, то система обыкновенных дифференциальных уравнений (1) является бесконечной.

Если в начальный момент времени t = 0 рассматриваемая система находилась в одном из своих возможных состояний S j , то начальные условия для нее выглядят следующим образом.

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

Пример . На станцию технического обслуживания поступает простейший поток заявок с интенсивностью 1 автомобиль за 2 ч. Во дворе в очереди может находиться не более 3 машин. Среднее время ремонта - 2 часа. Дайте оценку работы СМО и разработайте рекомендации по улучшению обслуживания.

Решение:
Определяем тип СМО. Фраза « На станцию» говорит об единственном устройстве обслуживания, т.е. для проверки решения используем сервис Одноканальные СМО .
Определяем вид одноканальной СМО. Поскольку имеется упоминание об очереди, следовательно выбираем «Одноканальная СМО с ограниченной длиной очереди».
Параметр λ необходимо выразить в часах. Интенсивность заявок 1 автомобиль за 2 ч или 0,5 за 1 час.
Интенсивность потока обслуживания μ явно не задана. Здесь приводится время обслуживания t обс = 2 часа.

Исчисляем показатели обслуживания для одноканальной СМО:
Интенсивность потока обслуживания:

1. Интенсивность нагрузки .
ρ = λ t обс = 0.5 2 = 1
Интенсивность нагрузки ρ=1 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.

3. Вероятность, что канал свободен (доля времени простоя канала).


Следовательно, 20% в течение часа канал будет не занят, время простоя равно t пр = 12 мин.

4. Доля заявок, получивших отказ .
Заявки не получают отказ. Обслуживаются все поступившие заявки, p отк = 0.

5. Относительная пропускная способность .
Доля обслуживаемых заявок, поступающих в единицу времени:
Q = 1 - p отк = 1 - 0 = 1
Следовательно, 100% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.

6. Абсолютная пропускная способность .
A = Q λ = 1 0.5 = 0.5 заявок/час.

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

ед.

9. Среднее время простоя СМО (среднее время ожидания обслуживания заявки в очереди).
час.

10. Среднее число обслуживаемых заявок .
L обс = ρ Q = 1 1 = 1 ед.

12. Среднее число заявок в системе .
L CMO = L оч + L обс = 1.2 + 1 = 2.2 ед.

13. Среднее время пребывания заявки в СМО .
час.

Число заявок, получивших отказ в течение час: λ p 1 = 0 заявок в час.
Номинальная производительность СМО: 1 / 2 = 0.5 заявок в час.
Фактическая производительность СМО: 0.5 / 0.5 = 100% от номинальной производительности.

Вывод: станция загружена на 100%. При этом отказов не наблюдается.

Абсолютная пропускная способность – среднее число заявок, которое может быть обслужено в единицу времени. p 0 - вероятность того, что канал свободен, Q - относительная пропускная способность

Интенсивность нагрузки ρ=3 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
2. Время обслуживания .
мин.

Следовательно, 3% в течение часа канал будет не занят, время простоя равно t пр = 1.7 мин.

занят 1 канал:
p 1 = ρ 1 /1! p 0 = 3 1 /1! 0.0282 = 0.0845
заняты 2 канала:
p 2 = ρ 2 /2! p 0 = 3 2 /2! 0.0282 = 0.13
заняты 3 канала:
p 3 = ρ 3 /3! p 0 = 3 3 /3! 0.0282 = 0.13
.

Значит, 13% из числа поступивших заявок не принимаются к обслуживанию.
.

p отк + p обс = 1

p обс = 1 - p отк = 1 - 0.13 = 0.87
Следовательно, 87% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.
.
n з = ρ p обс = 3 0.87 = 2.6 каналов
.
n пр = n - n з = 3 - 2.6 = 0.4 каналов
.

Следовательно, система на 90% занята обслуживанием.
8. Абсолютная пропускная способность для многоканальной СМО .

A = p обс λ = 0.87 6 = 5.2 заявок/мин.
9. Среднее время простоя СМО .
t пр = p отк ∙ t обс = 0.13∙ 0.5 = 0.06 мин.
.

ед.
мин.
.
L обс = ρ Q = 3 0.87 = 2.62 ед.
.
L CMO = L оч + L обс = 1.9 + 2.62 = 4.52 ед.
.
мин.
Число заявок, получивших отказ в течение часа: λ p 1 = 0.78 заявок в мин.
Номинальная производительность СМО: 3 / 0.5 = 6 заявок в мин.
Фактическая производительность СМО: 5.2 / 6 = 87% от номинальной производительности.

Пример №2 . Универсам получает ранние овощи и зелень из теплиц пригородного совхоза. Машины с товаром прибывают в универсам в неопределенное время. В среднем прибывает λ автомашин в день. Подсобные помещения и оборудование для подготовки овощей к продаже позволяют обработать и хранить товар объемом не более m автомашин одновременно. В универсаме работают n фасовщиков, каждый из которых в среднем может обработать товар с одной машины в течение t обсл дня. Определить вероятность обслуживания приходящей автомашины P обс. Какова должна быть емкость подсобных помещений m 1 , чтобы вероятность обслуживания была бы больше или равна заданной величине, т.е. Pобс.> P*обс.
λ = 3; t обс = 0,5; n = 2; m = 2, P* обс = 0,92.
Решение .

Исчисляем показатели обслуживания многоканальной СМО:
Переводим интенсивность потока заявок в часы: λ = 3/24 = 0.13
Интенсивность потока обслуживания:
μ = 1/12 = 0.0833
1. Интенсивность нагрузки .
ρ = λ t обс = 0.13 12 = 1.56
Интенсивность нагрузки ρ=1.56 показывает степень согласованности входного и выходного потоков заявок канала обслуживания и определяет устойчивость системы массового обслуживания.
Поскольку 1.56<2, то процесс обслуживания будет стабилен.
3. Вероятность, что канал свободен (доля времени простоя каналов).

Следовательно, 18% в течение часа канал будет не занят, время простоя равно t пр = 11 мин.
Вероятность того, что обслуживанием:
занят 1 канал:
p 1 = ρ 1 /1! p 0 = 1.56 1 /1! 0.18 = 0.29
заняты 2 канала:
p 2 = ρ 2 /2! p 0 = 1.56 2 /2! 0.18 = 0.22
4. Доля заявок, получивших отказ .

Значит, 14% из числа поступивших заявок не принимаются к обслуживанию.
5. Вероятность обслуживания поступающих заявок .
В системах с отказами события отказа и обслуживания составляют полную группу событий, поэтому:
p отк + p обс = 1
Относительная пропускная способность: Q = p обс.
p обс = 1 - p отк = 1 - 0.14 = 0.86
Следовательно, 86% из числа поступивших заявок будут обслужены. Приемлемый уровень обслуживания должен быть выше 90%.
6. Среднее число каналов, занятых обслуживанием .
n з = ρ p обс = 1.56 0.86 = 1.35 канала.
Среднее число простаивающих каналов .
n пр = n - n з = 2 - 1.35 = 0.7 канала.
7. Коэффициент занятости каналов обслуживанием .
K 3 = n 3 /n = 1.35/2 = 0.7
Следовательно, система на 70% занята обслуживанием.
8. Находим абсолютную пропускную способность .
A = p обс λ = 0.86 0.13 = 0.11 заявок/час.
9. Среднее время простоя СМО .
t пр = p отк t обс = 0.14 12 = 1.62 час.
Вероятность образования очереди .


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

ед.
11. Среднее время простоя СМО (среднее время ожидания обслуживания заявки в очереди).
T оч = L оч /A = 0.44/0.11 = 3.96 час.
12. Среднее число обслуживаемых заявок .
L обс = ρ Q = 1.56 0.86 = 1.35 ед.
13. Среднее число заявок в системе .
L CMO = L оч + L обс = 0.44 + 1.35 = 1.79 ед.
13. Среднее время пребывания заявки в СМО .
T CMO = L CMO /A = 1.79/0.11 = 16.01 час.

Теперь ответим на вопрос: какова должна быть емкость подсобных помещений m 1 , чтобы вероятность обслуживания была бы больше или равна заданной величине, т.е. P обс. > 0.92. Расчет производим исходя из условия:

где
Для наших данных:

Далее необходимо подобрать такое k (см. п.3 "доля времени простоя каналов"), при котором p отк 0.92.
например, при k = m 1 = 4, p отк = 0.07 или p обс = 0.93.