Одноканальная смо с ожиданием и ограниченной очередью. Конспект урока "теория систем массового обслуживания". Многоканальная СМО с ограниченной очередью
Рассмотрим теперь одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Рассмотрим систему с ограниченной очередью . Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N -требований (заявок), из которых одна обслуживается, а (N -1) ожидают, Клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте и такие заявки теряются.
Обозначим - вероятность того, что в системе находится n заявок. Эта величина вычисляется по формуле:
Здесь - приведенная интенсивность потока. Тогда вероятность того, что канал обслуживания свободен и в системе нет ни одного клиента, равна: .
С учетом этого можно обозначить
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N-1):
вероятность отказа в обслуживании заявки:
относительная пропускная способность системы:
абсолютная пропускная способность:
А =q ∙λ;
среднее число находящихся в системе заявок:
среднее время пребывания заявки в системе:
;
средняя продолжительность пребывания клиента (заявки) в очереди:
W q =W s - 1/μ;
среднее число заявок (клиентов) в очереди (длина очереди):
L q =λ(1-P N )W q .
Рассмотрим пример одноканальной СМО с ожиданием.
Пример 9.2 . В зону таможенного контроля в пункте пропуска автомобили въезжают по системе электронной очереди. Каждое окно оформления прибытия/убытия представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих оформления, ограниченно и равно 3, то есть (N -1)=3. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль в зону таможенного контроля не пропускается, т.е. в очередь на обслуживание не становится. Поток автомобилей, прибывающих на оформление имеет интенсивность λ =0,85 (автомобиля в час). Время оформления автомобиля распределено по показательному закону и в среднем равно =1,05 час. Требуется определить вероятностные характеристики окна оформления прибытия/убытия пункта пропуска, работающего в стационарном режиме.
Решение.
Интенсивность потока обслуживаний автомобилей:
.
Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей λ и μ, т.е.
.
Вычислим вероятности нахождения п заявок в системе:
;
P 1 =ρ∙P 0 =0,893∙0,248=0,221;
P 2 =ρ 2 ∙P 0 =0,893 2 ∙0,248=0,198;
P 3 =ρ 3 ∙P 0 =0,893 3 ∙0,248=0,177;
P 4 =ρ 4 ∙P 0 =0,893 4 ∙0,248=0,158.
Вероятность отказа в обслуживании автомобиля:
P отк =Р 4 = ρ 4 ∙P 0 ≈0,158.
Относительная пропускная способность окна оформления:
q =1–P отк =1-0,158=0,842.
Абсолютная пропускная способность окна оформления
А =λ∙q =0,85∙0,842=0,716 (автомобиля в час).
Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):
.
Среднее время пребывания автомобиля в системе:
часа.
Средняя продолжительность пребывания заявки в очереди на обслуживание:
W q =W s -1/μ=2,473-1/0,952=1,423 часа.
Среднее число заявок в очереди (длина очереди):
L q =λ∙(1-P N)∙W q = 0,85∙(1-0,158)∙1,423=1,02.
Работу рассмотренного окна оформления можно считать удовлетворительной, так как не обслуживается в среднем 15,8% случаев (Р отк =0,158).
Назначение сервиса СМО . Онлайн-калькулятор предназначен для расчета следующих показателей одноканальных СМО:- вероятность отказа канала, вероятность свободного канала, абсолютная пропускная способность;
- относительная пропускная способность, среднее время обслуживания, среднее время простоя канала.
Инструкция . Для решения подобных задач в онлайн режиме выберите модель СМО. Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Для одноканальной СМО с ограниченной длиной очереди можно указать длину очереди m , а для одноканальной СМО с неограниченной очередью - число заявок в очереди (для расчета вероятности нахождения этих заявок в очереди). см. пример решения . . Полученное решение сохраняется в файле Word .
Классификация одноканальных систем массового обслуживания
Пример №1 . Авто заправочная станция имеет одну бензоколонку. Предполагается что простейший поток автомашин поступает на станцию с интенсивностью λ=11 автомашин/ч. Время обслуживания заявки случайная величина которая подчиняется экспоненциальному закону с параметром μ=14 автомашин/ч. Определить среднее число автомашин на станции.
Пример №2
. Имеется пункт проведения профилактического осмотра машин с одной группой проведения осмотра. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,4 часа. На осмотр поступает в среднем 328 машин в сутки. Потоки заявок и обслуживаний - простейшие. Если машина, прибывшая в пункт осмотра не застает ни одного канала свободным, она покидает пункт осмотра необслуженной. Определить предельные вероятности состояний и характеристики обслуживания пункта профилактического осмотра.
Решение. Здесь α = 328/24 ≈ = 13.67, t = 0.4. Эти данные необходимо ввести в калькулятор.
Имеется 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
операции или эффективности системы массового обслуживания являются следующие.Для СМО с отказами :
Для СМО с неограниченным ожиданием как абсолютная, так и относительная пропускная способности теряют смысл, так как каждая поступившая заявка рано или поздно будет обслужена. Для такой СМО важными показателями являются:
Для СМО смешанного типа используются обе группы показателей: как относительная и абсолютная пропускная способности , так и характеристики ожидания.
В зависимости от цели операции массового обслуживания любой из приведенных показателей (или совокупность показателей) может быть выбран в качестве критерия эффективности.
Аналитической моделью СМО является совокупность уравнений или формул, позволяющих определять вероятности состояний системы в процессе ее функционирования и рассчитывать показатели эффективности по известным характеристикам входящего потока и каналов обслуживания.
Всеобщей аналитической модели для произвольной СМО не существует . Аналитические модели разработаны для ограниченного числа частных случаев СМО. Аналитические модели, более или менее точно отображающие реальные системы, как правило, сложны и труднообозримы.
Аналитическое моделирование СМО существенно облегчается, если процессы, протекающие в СМО, марковские (потоки заявок простейшие, времена обслуживания распределены экспоненциально). В этом случае все процессы в СМО можно описать обыкновенными дифференциальными уравнениями, а в предельном случае, для стационарных состояний - линейными алгебраическими уравнениями и, решив их, определить выбранные показатели эффективности.
Рассмотрим примеры некоторых СМО.
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 мин.