Одноканальная смо с очередью. Одноканальная смо с неограниченной очередью. Пример оптимизации СМО
Для СМО с отказами :
Для СМО с неограниченным ожиданием как абсолютная, так и относительная пропускная способности теряют смысл, так как каждая поступившая заявка рано или поздно будет обслужена. Для такой СМО важными показателями являются:
Для СМО смешанного типа используются обе группы показателей: как относительная и абсолютная пропускная способности , так и характеристики ожидания.
В зависимости от цели операции массового обслуживания любой из приведенных показателей (или совокупность показателей) может быть выбран в качестве критерия эффективности.
Аналитической моделью СМО является совокупность уравнений или формул, позволяющих определять вероятности состояний системы в процессе ее функционирования и рассчитывать показатели эффективности по известным характеристикам входящего потока и каналов обслуживания.
Всеобщей аналитической модели для произвольной СМО не существует . Аналитические модели разработаны для ограниченного числа частных случаев СМО. Аналитические модели, более или менее точно отображающие реальные системы, как правило, сложны и труднообозримы.
Аналитическое моделирование СМО существенно облегчается, если процессы, протекающие в СМО, марковские (потоки заявок простейшие, времена обслуживания распределены экспоненциально). В этом случае все процессы в СМО можно описать обыкновенными дифференциальными уравнениями, а в предельном случае, для стационарных состояний - линейными алгебраическими уравнениями и, решив их, определить выбранные показатели эффективности.
Рассмотрим примеры некоторых СМО.
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 мин.
Рассмотрим одноканальную систему массового обслуживания с ожиданием.
Будем предполагать, что входящий поток заявок на обслуживание есть простейший поток с интенсивностью λ.
Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий.
Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Будем считать, что размер очереди ограничен и не может вместить более m заявок, т.е. заявка, заставшая в момент своего прихода в СМО m +1 заявок (m ожидающих в очереди и одну, находящуюся на обслуживании), покидает СМО.
Система уравнений, описывающих процесс в этой системе, имеет решение:
(0‑1)
Знаменатель первого выражения представляет собой геометрическую прогрессию с первым членом 1 и знаменателем ρ, откуда получаем
При ρ = 1 можно прибегнуть к прямому подсчету
(0‑8)
Среднее число находящихся в системе заявок.
Поскольку среднее число находящихся в системе заявок
(0‑9)
где - среднее число заявок, находящихся под обслуживанием, то зная остается найти . Т.к. канал один, то число обслуживаемых заявок может равняться либо 0, либо 1 с вероятностями P 0 и P 1=1- P 0 соответственно, откуда
(0‑10)
и среднее число находящихся в системе заявок равно
(0‑11)
Среднее время ожидания заявки в очереди .
т.е., среднее время ожидания заявки в очереди равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.
Среднее время пребывания заявки в системе.
Время пребывания заявки в системе складывается из времени ожидания заявки в очереди и времени обслуживания. Если загрузка системы составляет 100%, то =1/μ, в противном случае = q / μ . Отсюда
(0‑13)
Содержание работы .
Подготовка инструментария эксперимента .
Выполняется аналогично в соответствии с общими правилами.
Расчет на аналитической модели .
1. В приложение Microsoft Excel подготовьте таблицу следующего вида.
2. В столбцах для параметров СМО таблицы запишите исходные данные, которые определяются по правилу:
m=1,2,3
(максимальная длина очереди).
Для каждого значения m необходимо найти теоретические и экспериментальные значения показателей СМО для таких пар значений:
= <порядковый номер в списке группы>
3. В столбцы с показателями аналитической модели впишите соответствующие формулы.
Эксперимент на имитационной модели .
1. Установите режим запусков с экспоненциально распределенным временем обслуживания, задав значение соответствующего параметра равным 1.
2. Для каждой комбинации m , и осуществите запуск модели.
3. Результаты запусков внесите в таблицу.
4. Внесите в соответствующие столбцы таблицы формулы для расчета среднего значения показателя P отк , q и А.
Анализ результатов .
1. Проанализируйте результаты, полученные теоретическим и экспериментальным способами, сравнив результаты между собой.
2. Для m=3 постройте на одной диаграмме графики зависимости P отк от на теоретически и экспериментально полученных данных.
Оптимизация параметров СМО .
Решите задачу оптимизации размера числа мест в очереди m для прибора со средним временем обслуживания = с точки зрения получения максимальной прибыли. В качестве условий задачи возьмите:
- доход от обслуживания одной заявки равным 80 у.е./час,
- стоимость содержания одного прибора равным 1у.е./час.
1. Для расчетов целесообразно создать таблицу:
Первый столбец заполняется значениями чисел натурального ряда (1,2,3…).
Все клетки второго и третьего столбцов заполняются значениями и.
В клетки столбцов с четвертого по девятый переносятся формулы для столбцов таблицы раздела 0.
В столбцы с исходными данными разделов Доход, Расход, Прибыль внесите значения (см. выше).
В столбцах с вычисляемыми значениями разделов Доход, Расход, Прибыль запишите расчетные формулы:
- число заявок в единицу времени
N r =A
- суммарный доход в единицу времени
I S = I r *N r
- суммарный расход в единицу времени
E S =E s + E q *(n-1)
- прибыль в единицу времени
P = I S - E S
где
I r - доход от одной заявки ,
E s - расход на эксплуатацию одного прибора ,
E q - расход на эксплуатацию одного места в очереди .
Графики для P отк ,
- таблицу с данными для нахождения наилучшего m и значение m опт,
- график зависимости прибыли в единицу времени от m .
Контрольные вопросы :
1) Дайте краткое описание одноканальной модели СМО с ограниченной очередью.
2) Какими показателями характеризуется функционирование одноканальной СМО с отказами?
3) Как рассчитывается вероятность p 0 ?
4) Как рассчитываются вероятности p i ?
5) Как найти вероятность отказа обслуживания заявки?
6) Как найти относительную пропускную способность?
7) Чему равна абсолютная пропускная способность?
8) Как подсчитывается среднее число заявок в системе?
9) Приведите примеры СМО с ограниченной очередью.
Задачи .
1) Порт имеет один грузовой причал для разгрузки судов. Интенсивность потока составляет 0,5 заходов в сутки. Среднее время разгрузки одного судна 2 суток. Если в очереди на разгрузку стоят 3 судна, то приходящее судно направляется для разгрузки на другой причал. Найти показатели эффективности работы причала.
2) В справочную железнодорожного вокзала поступают телефонные запросы с интенсивностью 80 заявок в час. Оператор справочной отвечает на поступивший звонок в среднем 0,7 мин. Если оператор занят, клиенту выдается сообщение "Ждите ответа", запрос становится в очередь, длина которой не превышает 4 запросов. Дайте оценку работы справочной и вариант ее реорганизации
Рассмотрим теперь одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание поток имеет интенсивность λ. Интенсивность потока обслуживания равна μ (т. е. в среднем непрерывно занятый канал будет выдавать μ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания.
Рассмотрим систему с ограниченной очередью . Предположим, что независимо оттого, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более 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. Эти данные необходимо ввести в калькулятор.
Многоканальная система массового обслуживания с ограниченной очередью
Пусть на вход СМО, имеющей каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью. Интенсивность обслуживания заявки каждым каналом равна, а максимальное число мест в очереди равно.
Граф такой системы представлен на рисунке 7.
Рисунок 7 - Граф состояний многоканальной СМО с ограниченной очередью
Все каналы свободны, очереди нет;
Заняты l каналов (l = 1, n), очереди нет;
Заняты все n каналов, в очереди находится i заявок (i = 1, m).
Сравнение графов на рисунке 2 и рисунке 7 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):
Выражения для финальных вероятностей легко найти из формул (4) и (5). В результате получим:
Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m - 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди p оч равна сумме соответствующих вероятностей:
Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е.:
Относительная пропускная способность равна:
Среднее число заявок, находящихся в очереди, определяется по формуле (11) и может быть записано в виде:
Среднее число заявок, обслуживаемых в СМО, может быть записано в виде:
Среднее число заявок, находящихся в СМО:
Среднее время пребывания заявки в СМО и в очереди определяется формулами (12) и (13).
Многоканальная система массового обслуживания с неограниченной очередью
Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке 7 при.
Рисунок 8 - Граф состояний многоканальной СМО с неограниченной очередью
Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при. При этом следует иметь в виду, что при вероятность р 0 = р 1 =…= p n = 0, т.е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай. При из (26) получим:
Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:
Из (27) получим выражение для вероятности образования очереди заявок:
Поскольку очередь не ограничена, то вероятность отказа в обслуживании заявки:
Абсолютная пропускная способность:
Из формулы (28) при получим выражение для среднего числа заявок в очереди:
Среднее число обслуживаемых заявок определяется формулой:
Среднее время пребывания в СМО и в очереди определяется формулами (12) и (13).
Многоканальная система массового обслуживания с ограниченной очередью и ограниченным временем ожидания в очереди
Отличие такой СМО от СМО, рассмотренной в подразделе 5.5, состоит в том, что время ожидания обслуживания, когда заявка находится в очереди, считается случайной величиной, распределённой по показательному закону с параметром, где - среднее время ожидания заявки в очереди, а - имеет смысл интенсивности потока ухода заявок из очереди. Граф такой СМО изображён на рисунке 9.
Рисунок 9 - Граф многоканальной СМО с ограниченной очередью и ограниченным временем ожидания в очереди
Остальные обозначения имеют здесь тот же смысл, что и в подразделе.
Сравнение графов на рис. 3 и 9 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):
Выражения для финальных вероятностей легко найти из формул (4) и (5) с учетом (29). В результате получим:
где. Вероятность образования очереди определяется формулой:
Отказ в обслуживании заявки происходит, когда все m мест в очереди заняты, т.е. вероятность отказа в обслуживании:
Относительная пропускная способность:
Абсолютная пропускная способность:
Среднее число заявок, находящихся в очереди, находится по формуле (11) и равно:
Среднее число заявок, обслуживаемых в СМО, находится по формуле (10) и равно: