Имеется n-канальная СМО с неограниченной очередью. Она характеризуется следующими показателями :
Предельные вероятности:
, , . . . , , ,…,
,… (10)
Вероятность того, что заявка окажется в очереди:
(11)
(13)
Среднее время нахождения в очереди:
(15)
Среднее время нахождения заявки в очереди:
Рассмотрим пример решения задачи многоканальной СМО с ожиданием.
Задача . В магазине к кассам поступает поток покупателей с интенсивностью 81 человек в час. Средняя продолжительность обслуживания кассиром одного покупателя tобсл = 2 мин. Определить предельные вероятности состояний и характеристики обслуживания узла расчета.
По условию λ=81(чел./час)= 81/60=1,35 (чел./мин.). По формулам (1, 2):
= λ/μ= λ * tобсл = 1,35 * 2 = 2,7
<1, т.е. при n > = 2,7. Таким образом, минимальное количество кассиров n =3.
Найдем характеристики обслуживания СМО при n=3.
Вероятность того, что в кассах отсутствуют покупатели, по формуле (9):
= (1+2,7+2,7 /2!+2,7 /3!+2,7 /3!(3-2,7)) = 0,025
В среднем 2,5 % времени кассиры будут простаивать.
Вероятность того, что в кассах будет очередь, определим по формуле (11):
P = (2,7 /3!(3-2,7))0,025 = 0,735
Среднее число покупателей, находящихся в очереди рассчитывается по формуле (13):
L = (2,7 /(3*3!(1-2,7/3) ))*0,025 = 7,35 (чел.)
T =7,35/1,35 = 5,44 (мин.)
Определим среднее число покупателей в кассах по формуле (15):
L =7,35+2,7=10,05 (чел.)
Среднее время нахождения покупателей в кассах находится по формуле (16):
T =10,05/1,35=7,44 (мин)
Среднее число кассиров, занятых обслуживанием покупателей, по формуле (12) =2,7.
Коэффициент (доля) занятых обслуживанием кассиров вычисляется по следующей формуле:
Абсолютная пропускная способность узла расчета A=1,35 (чел./мин), или 81 (чел./час), т.е. 81 покупатель в час. Анализ характеристик обслуживания свидетельствует о значительной перегрузке касс при наличии трех кассиров.
Системы массового обслуживания с ограниченной очередью
Имеется n-канальная СМО с ограниченной очередью. Число заявок в очереди ограничено числом m. Если заявка поступает в момент, когда в очереди уже m заявок, она не обслуживается. Такая СМО характеризуется следующими показателями :
Предельные вероятности:
(17)
, , . . . , , ,…,
(18)
Вероятность отказа:
(19)
Относительная пропускная способность:
Абсолютная пропускная способность:
Среднее число занятых каналов:
Среднее число заявок в очереди:
(23)
Среднее число заявок в системе:
Пример оптимизации СМО
Показатели работы системы массового обслуживания могут использоваться для решения оптимизационных задач.
Задача.
Определить оптимальное количество причалов в порту с минимальными затратами, если известно, что за год было обслужено 270 судов. Разгрузка одного судна длится в среднем 12 часов. Пеня за простой судна в порту составляет 100 тыс.р./сут.. Затраты на причал 150 тыс.р./сут. Расчеты приведены в таблице.
Решение.
По условию
λ=270(судов/год)=270/360=0,75(судов/сут.),
tобсл=12ч=12/24=0,5 сут.
По формулам (1, 2):
= λ/μ= λ * tобсл = 0,75 * 0,5 = 1,5
Очередь не будет возрастать до бесконечности при условии /n <1, т.е. при n > = 1,5. Таким образом, минимальное количество причалов n =2.
Найдем характеристики обслуживания СМО порта при количестве причалов n=2.
Вероятность того, что в порту отсутствуют суда, вычислим по формуле (9):
В среднем 1,4 % времени причалы будут простаивать.
Среднее число судов, находящихся в очереди рассчитывается по формуле (13):
Среднее время ожидания в очереди вычисляется по формуле (14):
T =1,93/0,75 = 2,57 (сут.)
Определим среднее число судов в порту по формуле (15):
L =1,93+1,5=3,43 (судна)
Среднее время нахождения судов в порту находится по формуле (16):
T =3,43 /0,75 =4,57 (сут)
Среднее число занятых причалов (12) =1,5.
Анализ характеристик обслуживания свидетельствует о значительной перегрузке порта при наличии двух причалов.
Найдем суммарную пеню за простой судов в порту в сутки. Для этого перемножим пеню за простой судна в порту и среднее число судов в очереди:
= * L .
Определим затраты по обслуживанию причалов в сутки: = *n.
Для двух причалов в сутки
Суммарные затраты составят: С= + =193+300=493(ден.ед.)
Суммарные затраты по условию задачи должны быть минимальны.
Рассчитаем суммарные затраты для количества причалов n = 2, 3, 4. Расчеты приведены в таблице. Как видно из таблицы, минимальные затраты достигаются при n = 3. Следовательно, для минимизации затрат необходимо 3 причала.
Таблица 1.- Расчет оптимального числа причалов
Показатель | Количество причалов | ||
Интенсивность потока судов | 0,75 | 0,75 | 0,75 |
Интенсивность обслуживания судов | 0,5 | 0,5 | 0,5 |
Интенсивность нагрузки причала | 1,5 | 1,5 | 1,5 |
Вероятность, что все причалы свободны | 0,14 | 0,21 | 0,22 |
Среднее число судов в очереди | 1,93 | 0,24 | 0,04 |
Среднее время пребывания судна в очереди, сут. | 2,57 | 0,32 | 0,06 |
Среднее число судов в порту | 3,43 | 1,74 | 1,54 |
Среднее время пребывания судна в порту, сут | 4,57 | 2,32 | 2,06 |
Пеня за простой судна в порту, ден.ед./сут. () | 100,00 | 100,00 | 100,00 |
Затраты по обслуживанию причала в сутки, ден.ед./сут. () | 150,00 | 150,00 | 150,00 |
Суммарная пеня за простой судов в порту в сутки, ден.ед. () | 192,86 | 23,68 | 4,48 |
Суммарные затраты по обслуживанию причалов в сутки, ден.ед. () | 300,00 | 450,00 | 600,00 |
Суммарные затраты, ден.ед.(С) | 492,86 | 473,68 | 604,48 |
Варианты заданий
Таблица 2 - Варианты заданий
Номер варианта | ||||||||||
Задача | ||||||||||
Номер варианта | ||||||||||
Задача |
1. В парикмахерской в зависимости от сложности стрижки, мастер выполняет работу в среднем за 30 мин. Посетители приходят в среднем через 25 мин. За каждый час работы мастер зарабатывает 300 ден.ед.. Очередь ограничена до 4 человек. Если в очереди больше 4 человек, клиент уходит, и потери за час составляют 150 ден.ед. Определить предельные вероятности состояний и характеристики обслуживания. Определить оптимальное количество мастеров.
2. Автомобили подъезжают на АЗС со средней частотой 2 автомобиля за 5 минут. Заправка автомобиля в среднем длится 3 минуты. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество колонок, чтобы средняя длина очереди не превышала 3 авт.
3. Рассматривается круглосуточная работа пункта проведения профилактического осмотра автомашин. На осмотр и выявление дефектов каждой машины затрачивается в среднем 30 минут. На осмотр поступает в среднем 36 машин в сутки. Если машина, прибывшая в пункт осмотра, не застает ни одного канала свободным, она покидает пункт осмотра не обслуженной. Определить вероятности состояний и характеристики обслуживания профилактического пункта осмотра. Определить количество каналов, чтобы относительная пропускная способность была не меньше 0,8.
4. В срочной мастерской по починке обуви в зависимости от сложности ремонта мастеру требуется в среднем 15 мин. Посетители приходят в среднем через каждые 14 мин. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество мастеров, чтобы средняя длина очереди не превышала 5 заказов.
5. В справочной оператор дает справку в среднем за 4 мин. Звонки поступают каждые 3мин. Если операторы заняты, то звонок не обслуживается. Определить вероятности состояний и характеристики обслуживания справочной. Определить количество каналов, чтобы относительная пропускная способность была не меньше 0,75.
6. В зависимости от количества продуктов у покупателя кассиру в магазине требуется в среднем на один чек 2 мин. Покупатели подходят к кассе с интенсивностью 81 человек/час. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество кассиров, чтобы средняя длина очереди не превышала 4 покупателей.
7. Диспетчеру в АТП в зависимости от типа автомобиля требуется в среднем на выдачу одного маршрутного листа 20 минут. Заявки на автомобили поступают в среднем через каждые 30 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество диспетчеров, чтобы средняя длина очереди не превышала 2 заявок.
8. Требуется оценить работу АТС. Если все линий связи заняты, то абонент выбывает из системы. Звонки поступают с интенсивностью 2 вызов/мин.. Продолжительность разговоров распределена экспоненциально, и в среднем равна 1,5 мин. Определить предельные вероятности и показатели эффективности системы. Определить количество операторов, чтобы относительная пропускная способность АТС была не меньше 0,9.
9. В банке в зависимости от сложности запроса клиента кассиру требуется в среднем 10 минут. Клиенты подходят к нему в среднем через каждые 12 минут. Кассир зарабатывает 15000 ден.ед. за месяц. Очередь ограничена до 6 человек. Если в очереди больше 6 человек, клиент уходит, и потери за час составляют 200 ден.ед. Определить предельные вероятности состояний и характеристики обслуживания. Определить оптимальное количество кассиров.
10. В среднем на одну транзакцию у банкомата уходит 2 минуты. Клиенты подходят к нему в среднем через каждые 20 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество банкоматов, чтобы средняя длина очереди не превышала 2 человек.
11. В магазине продавцу в зависимости от покупателя требуется в среднем на одну покупку 10 мин. Покупатели подходят к нему в среднем через каждые 5 мин. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество продавцов, чтобы средняя длина очереди не превышала 5 человек.
12. В отделе заказов мебельной фабрики менеджеру по продажам в зависимости от заказа клиента требуется в среднем на оформление одного заказа 25 минут. Клиенты приходят в среднем через каждые 30 минут. Определить предельные вероятности состояний и характеристики обслуживания. Определить количество менеджеров, чтобы средняя длина очереди не превышала 3 человек.
Порядок выполнения работы
1.Рассчитайте в системе Excel показатели системы массового обслуживания по формулам, приведенным в методичке. Количество каналов обслуживания n=1, 2, 3...k перебирается для нахождения оптимального значения по варианту. Предполагается, что входные потоки и обслуживание соответствуют пуассоновскому распределению.
2.Проведите анализ полученных результатов.
3.Составьте отчет.
1) Цель работы;
2) постановка задачи;
3) результаты расчетов, проведенных в Excel;
4) выводы по выполнению работы.
Контрольные вопросы
1. Что включает в себя понятие система массового обслуживания?
2. Какие существуют виды систем массового обслуживания?
3. Что относится к основным характеристикам и показателям эффективности систем массового обслуживания?
4. Укажите основные свойства (характеристики) входящего потока требований?
5. Перечислите основные особенности и характеристики систем массового обслуживания с ожиданием?
6. Каковы основные характеристики СМО с отказами?
7. Приведите примеры различных видов СМО?
Библиографический список
1. Афанасьев М.Ю. Исследование операций в экономике: модели, задачи, решения. / М.Ю. Афанасьев, Б.П. Суворов.- М.:ИНФРА, 2003.-444с.
2. Вентцель Е.С. Исследование операций. Задачи, приниципы, методология./ Е.С. Вентцель.-М.: Высшая школа, 2001.-208с.
3. Зайченко Ю.П. Исследование операций./ Ю.П. Зайченко.- К.: Вища школа, 1975.-320с.
4. Конюховский П.В. Математические методы исследования операций. / П.В. Конюховский.- СПб.: Питер, 2001.-192с.
5. Кремер Н.Ш., Путко Б.А. Исследование операций в экономике./ Н.Ш. Кремер, Б.А. Бутко, И.М. Тришин.- М.:Банки и биржи, ЮНИТИ, 1997.-407с.
1. Кудрявцев Е.М. GPSS World.Основы имитационного моделирования различных систем.- М.: ДМК Пресс, 2004.- 320 с.
2. Советов В.Я., Яковлев С.А. Моделирование систем. - М.: Высшая школа, 1985
3. Советов В.Я., Яковлев С.А. Моделирование систем: курсовое проектирование. - М.: Высшая школа, 1989
В коммерческой деятельности в качестве одноканалыюй СМО с неограниченным ожиданием является, например, коммерческий директор, поскольку он, как правило, вынужден выполнять обслуживание заявок различной природы: документы, переговоры по телефону, встречи и беседы с подчиненными, представителями налоговой инспекции, полиции, товароведами, маркетологами, поставщиками продукции и решать задачи в товарно-финансовой сфере с высокой степенью финансовой ответственности, что связано с обязательным выполнением запросов, которые ожидают иногда нетерпеливо выполнения своих требований, а ошибки неправильного обслуживания, как правило, экономически весьма ощутимы.
В то же время товары, завезенные для продажи (обслуживания), находясь на складе, образуют очередь на обслуживание (продажу). Длину очереди составляет количество товаров, предназначенных для продажи. В этой ситуации продавцы выступают в роли каналов, обслуживающих товары. Если количество товаров, предназначенных для продажи, велико, то в этом случае мы имеем дело с типичным случаем СМО с ожиданием.
Рассмотрим простейшую одноканальную СМО с ожиданием обслуживания, на которую поступает пуассоновский поток заявок с интенсивностью X и интенсивностью обслуживания р. Причем заявка, поступившая в момент, когда канал занят обслуживанием, ставится в очередь и ожидает обслуживания. Размеченный граф состояний такой системы приведен на рис. 5.17.
Рис. 5.17
Количество возможных состояний ее бесконечно:
So - канал свободен, очереди нет, k = 0;
S - канал занят обслуживанием, очереди нет, k = 1; S 2 - канал занят, одна заявка в очереди, k = 2;
5/, - канал занят (k - 1), заявка в очереди.
Модели оценки вероятности состояний СМО с неограниченной очередью можно получить из формул, выведенных для СМО с ограниченной очередью, путем перехода к пределу при т >
![](https://i1.wp.com/studme.org/htm/img/12/2572/730.png)
Следует заметить, что для СМО с ограниченной длиной очереди в формуле
имеет место геометрическая прогрессия с первым членом 1 и знаменателем р. Такая последовательность представляет собой сумму бесконечного числа членов при т -*? оо. Эта сумма сходится, если прогрессия, бесконечно убывающая при р 1 очередь при t -* оо с течением времени может расти до бесконечности.
Поскольку в рассматриваемой СМО ограничение на длину очереди отсутствует, то любая заявка может быть обслужена, поэтому Pofc = 1, следовательно, относительная пропускная способность Q = р 0 б с = 1, соответственно р ОТК = О, а абсолютная пропускная способность А = XQ = X, L 0 ^ = р.
Вероятность пребывания в очереди k заявок равна
Среднее число заявок в очереди
Среднее число заявок в системе
Среднее время ожидания обслуживания в очереди
Среднее время пребывания заявки в системе
Если в одноканальной СМО с ожиданием интенсивность поступления заявок больше интенсивности обслуживания, % > р, то очередь будет постоянно увеличиваться. В связи с этим наибольший интерес представляет анализ устойчивых СМО, работающих в стационарном режиме при X р, р
Пример 5.18. Булочная «Горячий хлеб» имеет одного контроле- ра-кассира. В течение часа приходят в среднем 54 покупателя. Средняя стоимость одной покупки составляет 7 руб. Среднее время обслуживания контролером-кассиром одного покупателя составляет 1 мин. Определим выручку от продажи, характеристики СМО и проведем анализ ее работы.
Решение
По условиям задачи п = 1; X = 54 ед/ч; р = 60 ед/ч, и поскольку р = Х/р = 0,9, то очередь нс будет расти бесконечно, следовательно, предельные вероятности существуют:
Вероятность того, что контролер-кассир свободен,
Вероятность того, что контролер-кассир занят работой,
Среднее число покупателей в очереди
Среднее время пребывания покупателя в булочной
Среднее число покупателей в булочной
Вероятность того, что в булочной находятся 1, 2, 3,4 человека, а следовательно, ожидают расчета в очереди у контролера-кассира 1, 2, 3 человека соответственно
Вероятность того, что ожидают расчета у контролера-кассира не более трех человек, равна
Доля времени простоя контролера-кассира составляет всего 10% от продолжительности рабочего дня, однако время ожидания обслуживания в очереди ощутимо - 9 мин, поэтому следует уменьшать время обслуживания t of -)C , введя дополнительный кассовый аппарат и соответственно контролера-кассира, иначе покупатели будут уходить в другое торговое предприятие, что приведет к ухудшению экономических показателей хозяйственной деятельности, в частности к уменьшению выручки от продажи хлеба и образованию остатков хлеба па следующий день и к потере его качества.
Пример 5.19. Интенсивность потока автомобилей на АЗС к колонке за бензином АИ-92 составляет 30 автомобилей в час, а среднее время заправки равно 5 мин. Проведем анализ работы системы массового обслуживания АЗС.
Решение
X = 30 ед/ч; = 5 мин = 1/12 ч.
Определим характеристики СМО. Интенсивность нагрузки:
Поскольку р > 1, то АЭС не будет работать в стационарном режиме и очередь будет постоянно увеличиваться, поэтому необходимо ввести еще одну колонку с бензином АИ-92 или уменьшить время обслуживания до величины ~ 1,9 мин, тогда
следовательно, р
Пример 5.20. В парикмахерской работает только один мужской мастер. Среднее время стрижки одного клиента составляет 20 мин. Клиенты в среднем приходят каждые 25 мин. Средняя стоимость стрижки составляет 60 руб. Как в первую смену с 9 до 15 ч, так и во вторую - с 15 до 21 ч работает один мастер. Провести анализ работы системы обслуживания.
Решение
п = 1; X = 2,4 клиента/ч; t Q fc = 20 мин = 1/3 ч.
Интенсивность нагрузки
Долю времени простоя мастера
Вероятность того, что мастер занят работой,
Среднее число клиентов в очереди
Среднее время ожидания в очереди
Среднее время пребывания клиентов в парикмахерской
Система работает вполне удовлетворительно. Поскольку р X = 4 клиента/ч, то интенсивность нагрузки составит р > 1 и очередь будет постоянно увеличиваться, что приведет к неустойчивому режиму работы СМО.
Рассмотрим простейшую СМО с ожиданием - одноканальную систему , в которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (т. е. в среднем непрерывно занятый канал будет выдавать обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Система с ограниченной длиной очереди. Предположим сначала, что количество мест в очереди ограничено числом , т. е. если заявка пришла в момент, когда в очереди уже стоят заявок, она покидает систему необслуженной. В дальнейшем, устремив к бесконечности, мы получим характеристики одноканальной СМО без ограничений длины очереди.
Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):
Канал свободен;
Канал занят, очереди нет;
Канал занят, одна заявка стоит в очереди;
Канал занят, заявок стоят в очереди;
Канал занят, т заявок стоят в очереди.
ГСП показан на рис. 5.8. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны , а справа налево - . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево - поток «освобождений» занятого канала, меющий интенсивность (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).
Рис. 5.8. Одноканальная СМО с ожиданием
Изображенная на рис. 5.8 схема представляет собой схему размножения и гибели. Используя общее решение (5.32)-(5.34), напишем выражения для предельных вероятностей состояний (см. также (5.40)):
или с использованием :
Последняя строка в (5.45) содержит геометрическую прогрессию с первым членом 1 и знаменателем р; откуда получаем:
в связи с чем предельные вероятности принимают вид:
Выражение (5.46) справедливо только при (при она дает неопределенность вида ). Сумма геометрической прогрессии со знаменателем равна , и в этом случае
Определим характеристики СМО: вероятность отказа , относительную пропускную способность , абсолютную пропускную способность , среднюю длину очереди , среднее число заявок, связанных с системой , среднее время ожидания в очереди , среднее время пребывания заявки в СМО
Вероятность отказа. Очевидно, заявка получает отказ только в случае, когда канал занят и все т мест в очереди тоже:
Относительная пропускная способность:
Абсолютная пропускная способность:
Средняя длина очереди. Найдем среднее число заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины - числа заявок, находящихся в очереди:
С вероятностью в очереди стоит одна заявка, с вероятностью - две заявки, вообще с вероятностью в очереди стоят заявок, и т. д., откуда:
Поскольку , сумму в (5.50) можно трактовать как производную по от суммы геометрической прогрессии:
Подставляя данное выражение в (5.50) и используя из (5.47), окончательно получаем:
Среднее число заявок, находящихся в системе. Получим далее формулу для среднего числа заявок, связанных с системой (как стоящих в очереди, так и находящихся на обслуживании). Поскольку , где - среднее число заявок, находящихся под обслуживанием, а известно, то остается определить . Поскольку канал один, число обслуживаемых заявок может равняться (с вероятностью ) или 1 (с вероятностью ), откуда:
и среднее число заявок, связанных с СМО, равно
Среднее время ожидания заявки в очереди. Обозначим его ; если заявка приходит в систему в какой-то момент времени, то с вероятностью канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероятностью она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени (среднее время обслуживания одной заявки). С вероятностью в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно , и т. д.
Если же , т. е. когда вновь приходящая заявка застает канал обслуживания занятым и заявок в очереди (вероятность этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:
если подставить сюда выражения для вероятностей (5.47), получим:
Здесь использованы соотношения (5.50), (5.51) (производная геометрической прогрессии), а также из (5.47). Сравнивая это выражение с (5.51), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Среднее время пребывания заявки в системе. Обозначим матожидание случайной величины - время пребывания заявки в СМО, которое складывается из среднего времени ожидания в очереди и среднего времени обслуживания . Если загрузка системы составляет 100 %, очевидно, , в противном же случае
Пример 5.6. Автозаправочная станция (АЗС) представляет собой СМО с одним каналом обслуживания (одной колонкой).
Площадка при станции допускает пребывание в очереди на заправку не более трех машин одновременно . Если в очереди уже находятся три машины, очередная машина, прибывшая к станции, в очередь не становится. Поток машин, прибывающих для заправки, имеет интенсивность (машина в минуту). Процесс заправки продолжается в среднем 1,25 мин.
Определить:
вероятность отказа;
относительную и абсолютную пропускную способности АЗС;
среднее число машин, ожидающих заправки;
среднее число машин, находящихся на АЗС (включая обслуживаемую);
среднее время ожидания машины в очереди;
среднее время пребывания машины на АЗС (включая обслуживание).
иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Находим вначале приведенную интенсивность потока заявок:
По формулам (5.47):
Вероятность отказа .
Относительная пропускная способность СМО
Абсолютная пропускная способность СМО
Машины в мин.
Среднее число машин в очереди находим по формуле (5.51)
т. е. среднее число машин, ожидающих в очереди на заправку, равно 1,56.
Прибавляя к этой величине среднее число машин, находящихся под обслуживанием
получаем среднее число машин, связанных с АЗС.
Среднее время ожидания машины в очереди по формуле (5.54)
Прибавляя к этой величине , получим среднее время, которое машина проводит на АЗС:
Системы с неограниченным ожиданием . В таких системах значение т не ограничено и, следовательно, основные характеристики могут быть получены путем предельного перехода в ранее полученных выражениях (5.44), (5.45) и т. п.
Заметим, что при этом знаменатель в последней формуле (5.45) представляет собой сумму бесконечного числа членов геометрической прогрессии. Эта сумма сходится, когда прогрессия бесконечно убывающая, т. е. при .
Может быть доказано, что есть условие, при котором в СМО с ожиданием существует предельный установившийся режим, иначе такого режима не существует, и очередь при будет неограниченно возрастать. Поэтому в дальнейшем здесь предполагается, что .
Если , то соотношения (5.47) принимают вид:
При отсутствии ограничений по длине очереди каждая заявка, пришедшая в систему, будет обслужена, поэтому ,
Среднее число заявок в очереди получим из (5.51) при :
Среднее число заявок в системе по формуле (5.52) при
Среднее время ожидания получим из формулы
(5.53) при :
Наконец, среднее время пребывания заявки в СМО есть
Многоканальная СМО с ожиданием
Система с ограниченной длиной очереди . Рассмотрим канальную СМО с ожиданием, на которую поступает поток заявок с интенсивностью ; интенсивность обслуживания (для одного канала) ; число мест в очереди .
Состояния системы нумеруются по числу заявок, связанных системой:
нет очереди:
Все каналы свободны;
Занят один канал, остальные свободны;
Заняты каналов, остальные нет;
Заняты все каналов, свободных нет;
есть очередь:
Заняты все n каналов; одна заявка стоит в очереди;
Заняты все n каналов, r заявок в очереди;
Заняты все n каналов, r заявок в очереди.
ГСП приведен на рис. 5.9. У каждой стрелки проставлены соответствующие интенсивности потоков событий. По стрелкам слева направо систему переводит всегда один и тот же поток заявок с интенсивностью , по стрелкам справа налево систему переводит поток обслуживании, интенсивность которого равна , умноженному на число занятых каналов.
Рис. 5.9. Многоканальная СМО с ожиданием
Граф типичен для процессов размножения и гибели, для которой решение ранее получено (5.29)-(5.33). Напишем выражения для предельных вероятностей состояний, используя обозначение : (здесь используется выражение для суммы геометрической прогрессии со знаменателем ).
Таким образом, все вероятности состояний найдены.
Определим характеристики эффективности системы.
Вероятность отказа. Поступившая заявка получает отказ, если заняты все каналов и все мест в очереди:
Относительная пропускная способность дополняет вероятность отказа до единицы:
Абсолютная пропускная способность СМО:
Среднее число занятых каналов. Для СМО с отказами оно совпадало со средним числом заявок, находящихся в системе. Для СМО с очередью среднее число занятых каналов не совпадает со средним числом заявок, находящихся в системе: последняя величина отличается от первой на среднее число заявок, находящихся в очереди.
Обозначим среднее число занятых каналов . Каждый занятый канал обслуживает в среднем заявок в единицу времени, а СМО в целом обслуживает в среднем заявок в единицу времени. Разделив одно на другое, получим:
Среднее число заявок в очереди можно вычислить непосредственно как математическое ожидание дискретной случайной величины:
Здесь опять (выражение в скобках) встречается производная суммы геометрической прогрессии (см. выше (5.50), (5.51)-(5.53)), используя соотношение для нее, получаем:
Среднее число заявок в системе:
Среднее время ожидания заявки в очереди. Рассмотрим ряд ситуаций, различающихся тем, в каком состоянии застанет систему вновь пришедшая заявка и сколько времени ей придется ждать обслуживания.
Если заявка застанет не все каналы занятыми, ей вообще не придется ждать (соответствующие члены в математическом ожидании равны нулю). Если заявка придет в момент, когда заняты все каналов, а очереди нет, ей придется ждать в среднем время, равное (потому что «поток освобождений» каналов имеет интенсивность ). Если заявка застанет все каналы занятыми и одну заявку перед собой в очереди, ей придется в среднем ждать в течение времени (по на каждую впереди стоящую заявку) и т. д. Если заявка застанет в очереди заявок, ей придется ждать в среднем в течение времени . Если вновь пришедшая заявка застанет в очереди уже заявок, то она вообще не будет ждать (но и не будет обслужена). Среднее время ожидания найдем, умножая каждое из этих значений на соответствующие вероятности:
Так же, как и в случае одноканальной СМО с ожиданием, отметим, что это выражение отличается от выражения для средней длины очереди (5.59) только множителем , т. е.
Среднее время пребывания заявки в системе, так же, как и для одноканальной СМО, отличается от среднего времени ожидания на среднее время обслуживания, умноженное на относительную пропускную способность:
Системы с неограниченной длиной очереди . Мы рассмотрели канальную СМО с ожиданием, когда в очереди одновременно могут находиться не более заявок.
Так же, как и ранее, при анализе систем без ограничений необходимо рассмотреть полученные соотношения при .
Вероятности состояний получим из формул (5.56) предельным переходом (при ). Заметим, что сумма соответствующей геометрической прогрессии сходится при и расходится при . Допустив, что и устремив в формулах (5.56) величину m к бесконечности, получим выражения для предельных вероятностей состояний:
Вероятность отказа, относительная и абсолютная пропускная способность. Так как каждая заявка рано или поздно будет обслужена, то характеристики пропускной способности СМО составят:
Среднее число заявок в очереди получим при из (5.59):
а среднее время ожидания - из (5.60):
Среднее число занятых каналов , как и ранее, определяется через абсолютную пропускную способность:
Среднее число заявок, связанных с СМО, определяется как среднее число заявок в очереди плюс среднее число заявок, находящихся под обслуживанием (среднее число занятых каналов):
Пример 5.7. Автозаправочная станция с двумя колонками () обслуживает поток машин с интенсивностью (машин в минуту). Среднее время обслуживания одной машины
В данном районе нет другой АЗС, так что очередь машин перед АЗС может расти практически неограниченно. Найти характеристики СМО.
Поскольку , очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. По формулам (5.61) находим вероятности состояний:
Среднее число занятых каналов найдем, разделив абсолютную пропускную способность СМО на интенсивность обслуживания :
Вероятность отсутствия очереди у АЗС будет:
Среднее число машин в очереди:
Среднее число машин на АЗС:
Среднее время ожидания в очереди:
Среднее время пребывания машины на АЗС:
СМО с ограниченным временем ожидания. Ранее рассматривались системы с ожиданием, ограниченным только длиной очереди (числом заявок, одновременно находящихся в очереди). В такой СМО заявка, раз ставшая в очередь, не покидает ее, пока не дождется обслуживания. На практике встречаются СМО другого типа, в которых заявка, подождав некоторое время, может уйти из очереди (так называемые «нетерпеливые» заявки).
Рассмотрим СМО подобного типа, предполагая, что ограничение времени ожидания является случайной величиной.
Предположим, что имеется канальная СМО с ожиданием, в которой число мест в очереди не ограничено, но время пребывания заявки в очереди является некоторой случайной величиной со средним значением , таким образом, на каждую заявку, стоящую в очереди, действует своего рода пуассоновский «поток уходов» с интенсивностью заявок стоят в очереди и т. д.
Граф состояний и переходов системы показан на рис. 5.10.
Рис. 5.10. СМО с ограниченным временем ожидания
Разметим этот граф, как и раньше; у всех стрелок, ведущих слева направо, будет стоять интенсивность потока заявок . Для состояний без очереди у стрелок, ведущих из них справа налево, будет, как и раньше, стоять суммарная интенсивность потока обслуживании всех занятых каналов. Что касается состояний с очередью, то у стрелок, ведущих из них справа налево, будет стоять суммарная интенсивность потока обслуживании всех каналов плюс соответствующая интенсивность потока уходов из очереди. Если в очереди стоят заявок, то суммарная интенсивность потока уходов будет равна .
Как видно из графа, имеет место схема размножения и гибели; применяя общие выражения для предельных вероятностей состояний в этой схеме (используя сокращенные обозначения ) запишем:
Отметим некоторые особенности СМО с ограниченным ожиданием сравнительно с ранее рассмотренными СМО с «терпеливыми» заявками.
Если длина очереди не ограничена и заявки «терпеливы» (не уходят из очереди), то стационарный предельный режим существует только в случае (при соответствующая бесконечная геометрическая прогрессия расходится, что физически соответствует неограниченному росту очереди при ).
Напротив, в СМО с «нетерпеливыми» заявками, уходящими рано или поздно из очереди, установившийся режим обслуживания при достигается всегда, независимо от приведенной интенсивности потока заявок, не суммируя бесконечного ряда (5.63). Из (5.64) получаем:
а входящее в эту формулу среднее число занятых каналов можно найти как математическое ожидание случайной величины , принимающей значения с вероятностями :
В заключение заметим, что если в формулах (5.62) перейти к пределу при (или, что то же, при ), то при получатся формулы (5.61), т. е. «нетерпеливые» заявки станут «терпеливыми».
операции или эффективности системы массового обслуживания являются следующие.Для СМО с отказами :
Для СМО с неограниченным ожиданием как абсолютная, так и относительная пропускная способности теряют смысл, так как каждая поступившая заявка рано или поздно будет обслужена. Для такой СМО важными показателями являются:
Для СМО смешанного типа используются обе группы показателей: как относительная и абсолютная пропускная способности , так и характеристики ожидания.
В зависимости от цели операции массового обслуживания любой из приведенных показателей (или совокупность показателей) может быть выбран в качестве критерия эффективности.
Аналитической моделью СМО является совокупность уравнений или формул, позволяющих определять вероятности состояний системы в процессе ее функционирования и рассчитывать показатели эффективности по известным характеристикам входящего потока и каналов обслуживания.
Всеобщей аналитической модели для произвольной СМО не существует . Аналитические модели разработаны для ограниченного числа частных случаев СМО. Аналитические модели, более или менее точно отображающие реальные системы, как правило, сложны и труднообозримы.
Аналитическое моделирование СМО существенно облегчается, если процессы, протекающие в СМО, марковские (потоки заявок простейшие, времена обслуживания распределены экспоненциально). В этом случае все процессы в СМО можно описать обыкновенными дифференциальными уравнениями, а в предельном случае, для стационарных состояний - линейными алгебраическими уравнениями и, решив их, определить выбранные показатели эффективности.
Рассмотрим примеры некоторых СМО.
2.5.1. Многоканальная СМО с отказами
Пример 2.5 . Три автоинспектора проверяют путевые листы у водителей грузовых автомобилей. Если хотя бы один инспектор свободен, проезжающий грузовик останавливают. Если все инспекторы заняты, грузовик, не задерживаясь, проезжает мимо. Поток грузовиков простейший, время проверки случайное с экспоненциальным распределением.
Такую ситуацию можно моделировать трехканальной СМО с отказами (без очереди). Система разомкнутая, с однородными заявками, однофазная, с абсолютно надежными каналами.
Описание состояний:
Все инспекторы свободны;
Занят один инспектор;
Заняты два инспектора;
Заняты три инспектора.
Граф состояний системы приведен на рис. 2.11 .
Рис. 2.11.
На графе: - интенсивность потока грузовых автомобилей; - интенсивность проверок документов одним автоинспектором.
Моделирование проводится с целью определения части автомобилей, которые не будут проверены.
Решение
Искомая часть вероятности - вероятности занятости всех трех инспекторов. Поскольку граф состояний представляет типовую схему "гибели и размножения", то найдем , используя зависимости (2.2).
Пропускную способность этого поста автоинспекторов можно характеризовать относительной пропускной способностью :
Пример 2.6 . Для приема и обработки донесений от разведгруппы в разведотделе объединения назначена группа в составе трех офицеров. Ожидаемая интенсивность потока донесений - 15 донесений в час. Среднее время обработки одного донесения одним офицером - . Каждый офицер может принимать донесения от любой разведгруппы. Освободившийся офицер обрабатывает последнее из поступивших донесений. Поступающие донесения должны обрабатываться с вероятностью не менее 95 %.
Определить, достаточно ли назначенной группы из трех офицеров для выполнения поставленной задачи.
Решение
Группа офицеров работает как СМО с отказами, состоящая из трех каналов.
Поток донесений с интенсивностью можно считать простейшим, так как он суммарный от нескольких разведгрупп. Интенсивность обслуживания
. Закон распределения неизвестен, но это несущественно, так как показано, что для систем с отказами он может быть произвольным.
Описание состояний и граф состояний СМО будут аналогичны приведенным в примере 2.5.
Поскольку граф состояний - это схема "гибели и размножения", то для нее имеются готовые выражения для предельных вероятностей состояния:
Отношение называют приведенной интенсивностью потока заявок . Физический смысл ее следующий: величина представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.
В примере .
В рассматриваемой СМО отказ наступает при занятости всех трех каналов, то есть . Тогда:
Так как вероятность отказа в обработке донесений составляет более 34 % (), то необходимо увеличить личный состав группы. Увеличим состав группы в два раза, то есть СМО будет иметь теперь шесть каналов, и рассчитаем :
Таким образом, только группа из шести офицеров сможет обрабатывать поступающие донесения с вероятностью 95 %.
2.5.2. Многоканальная СМО с ожиданием
Пример 2.7 . На участке форсирования реки имеются 15 однотипных переправочных средств. Поток поступления техники на переправу в среднем составляет 1 ед./мин, среднее время переправы одной единицы техники - 10 мин (с учетом возвращения назад переправочного средства).
Оценить основные характеристики переправы, в том числе вероятность в немедленной переправе сразу по прибытии единицы техники.
Решение
Абсолютная пропускная способность , т. е. все, что подходит к переправе, тут же практически переправляется.
Среднее число работающих переправочных средств:
Коэффициенты использования и простоя переправы:
Для решения примера была также разработана программа. Интервалы времени поступления техники на переправу, время переправы приняты распределенными по экспоненциальному закону.
Коэффициенты использования переправы после 50 прогонов практически совпадают: .
Максимальная длина очереди 15 ед., среднее время пребывания в очереди около 10 мин.
В коммерческой деятельности в качестве одноканальной СМО с неограниченным ожиданием является, например, коммерческий директор, поскольку он, как правило, вынужден выполнять обслуживание заявок различной природы: документы, переговоры по телефону, встречи и беседы с подчиненными, представителями налоговой инспекции, милиции, товароведами, маркетологами, поставщиками продукции и решать задачи в товарно-финансовой сфере с высокой степенью финансовой ответственности, что связано с обязательным выполнением запросов, которые ожидают иногда нетерпеливо выполнения своих требований, а ошибки неправильного обслуживания, как правило, экономически весьма ощутимы.
В то же время товары, завезенные для продажи (обслуживания), находясь на складе, образуют очередь на обслуживание (продажу).
Длину очереди составляет количество товаров, предназначенных для продажи. В этой ситуации продавцы выступают в роли каналов, обслуживающих товары. Если количество товаров, предназначенных для продажи, велико, то в этом случае мы имеем дело с типичным случаем СМО с ожиданием.
Рассмотрим простейшую одноканальную СМО с ожиданием обслуживания, на которую поступает пуассоновский поток заявок с интенсивностью л и интенсивностью обслуживания µ.
Причем заявка, поступившая в момент, когда канал занят обслуживанием, ставится в очередь и ожидает обслуживания.
Размеченный граф состояний такой системы приведен на рис. 3.5
Количество возможных состояний ее бесконечно:
Канал свободен, очереди нет, ;
Канал занят обслуживанием, очереди нет, ;
- - канал занят, одна заявка в очереди, ;
- - канал занят, заявка в очереди.
Модели оценки вероятности состояний СМО с неограниченной очередью можно получить из формул, выделенных для СМО с неограниченной очередью, путем перехода к пределу при m>?:
Рис. 3.5
![](https://i1.wp.com/studwood.ru/imag_/39/154458/image018.png)
![](https://i0.wp.com/studwood.ru/imag_/39/154458/image019.png)
Следует заметить, что для СМО с ограниченной длиной очереди в формуле
имеет место геометрическая прогрессия с первым членом 1 и знаменателем. Такая последовательность представляет собой сумму бесконечного числа членов при. Эта сумма сходится, если прогрессия, бесконечно убывающая при, что определяет установившийся режим работы СМО, с при очередь при с течением времени может расти до бесконечности.
Поскольку в рассматриваемой СМО ограничение на длину очереди отсутствует, то любая заявка может быть обслужена, поэтому, следовательно, относительная пропускная способность, соответственно, а абсолютная пропускная способность
Вероятность пребывания в очереди k заявок равна:
Среднее число заявок в очереди -
Среднее число заявок в системе -
![](https://i1.wp.com/studwood.ru/imag_/39/154458/image021.png)
Среднее время пребывания заявки в системе -
![](https://i0.wp.com/studwood.ru/imag_/39/154458/image022.png)
Среднее время пребывания заявки с системе -
![](https://i0.wp.com/studwood.ru/imag_/39/154458/image023.png)
Если в одноканальной СМО с ожиданием интенсивность поступления заявок больше интенсивности обслуживания, то очередь будет постоянно увеличиваться. В связи с этим наибольший интерес представляет анализ устойчивых СМО, работающих в стационарном режиме при.