- вероятность отказа канала, вероятность свободного канала, абсолютная пропускная способность;
- относительная пропускная способность, среднее время обслуживания, среднее время простоя канала.
Инструкция . Для решения подобных задач в онлайн режиме выберите модель СМО. Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Для одноканальной СМО с ограниченной длиной очереди можно указать длину очереди m , а для одноканальной СМО с неограниченной очередью - число заявок в очереди (для расчета вероятности нахождения этих заявок в очереди). см. пример решения . . Полученное решение сохраняется в файле Word .
Классификация одноканальных систем массового обслуживания
Пример №1 . Авто заправочная станция имеет одну бензоколонку. Предполагается что простейший поток автомашин поступает на станцию с интенсивностью λ=11 автомашин/ч. Время обслуживания заявки случайная величина которая подчиняется экспоненциальному закону с параметром μ=14 автомашин/ч. Определить среднее число автомашин на станции.
Пример №2
. Имеется пункт проведения профилактического осмотра машин с одной группой проведения осмотра. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,4 часа. На осмотр поступает в среднем 328 машин в сутки. Потоки заявок и обслуживаний - простейшие. Если машина, прибывшая в пункт осмотра не застает ни одного канала свободным, она покидает пункт осмотра необслуженной. Определить предельные вероятности состояний и характеристики обслуживания пункта профилактического осмотра.
Решение. Здесь α = 328/24 ≈ = 13.67, t = 0.4. Эти данные необходимо ввести в калькулятор.
Рассмотрим многоканальную СМО, на вход которой поступает пуассоновский поток заявок с интенсивностью, а интенсивность обслуживания каждого канала составляет, максимально возможное число мест в очереди ограничено величиной m. Дискретные состояния СМО определяются количеством заявок, поступивших в систему, которые можно записать.
Все каналы свободны, ;
Занят только один канал (любой), ;
- - заняты только два канала (любых), ;
- - заняты все каналов, .
Пока СМО находится в любом из этих состояний, очереди нет. После того как заняты все каналы обслуживания, последующие заявки образуют очередь, тем самым, определяя дальнейшие состояние системы:
Заняты все каналов и одна заявка стоит в очереди,
Заняты все каналов и две заявки стоят в очереди,
Заняты все каналов и все мест в очереди,
Переход СМО в состояние с большими номерами определяется потоком поступающих заявок с интенсивностью, тогда как по условию в обслуживании этих заявок принимают участие одинаковых каналов с интенсивностью потока обслуживания равного для каждого канала. При этом полная интенсивность потока обслуживания возрастает с подключением новых каналов вплоть до такого состояния, когда все n каналов окажутся занятыми. С появлением очереди интенсивность обслуживания более увеличивается, так как она уже достигла максимального значения, равного.
Запишем выражения для предельных вероятностей состояний:
Выражение для можно преобразовать, используя формулу геометрической прогрессии для суммы членов со знаменателем:
Образование очереди возможно, когда вновь поступившая заявка застанет в системе не менее требований, т.е. когда в системе будет находиться требований.
Эти события независимы, поэтому вероятность того, что все каналы заняты, равна сумме соответствующих вероятностей
Поэтому вероятность образования очереди равна:
Вероятность отказа в обслуживании наступает тогда, когда все каналов и все мест в очереди заняты:
Относительная пропускная способность будет равна:
Абсолютная пропускная способность -
Среднее число занятых каналов -
Среднее число простаивающих каналов -
Коэффициент занятости (использования) каналов -
Коэффициент простоя каналов -
Среднее число заявок, находящихся в очередях -
В случае если, эта формула принимает другой вид -
Среднее время ожидания в очереди определяется формулами Литтла -
Рассмотрим одноканальную систему массового обслуживания с ожиданием.
Будем предполагать, что входящий поток заявок на обслуживание есть простейший поток с интенсивностью λ.
Интенсивность потока обслуживания равна μ. Длительность обслуживания – случайная величина, подчиненная показательному закону распределения. Поток обслуживаний является простейшим пуассоновским потоком событий.
Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Будем считать, что размер очереди ограничен и не может вместить более 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 запросов. Дайте оценку работы справочной и вариант ее реорганизации
В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.
Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:
S 0 – система свободна и находится в состоянии простоя;
S 1 – обслуживается одна заявка, канал занят, очереди нет;
S 2 – одна заявка обслуживается, одна в очереди;
S m +1 - одна заявка обслуживается,т в очереди.
Граф состояний такой системы показан на рисунке номер 5:
S 0 S 1 S 2 S m+1
μ μ μ ………. μ μ
Рисунок 5: Одноканальная СМО с ограниченной очередью.
В формуле для р 0 найдем сумму конечного числа членов геометрической прогрессии:
(52)
С учетом формулы для ρ получим выражение:
В скобках находится (m+2) элементов геометрической прогрессии с первым членом 1 и знаменателем ρ. По формуле суммы (m+2) членов прогрессии:
(54)
(55)
Формулы для вероятностей предельных состояний будут иметь вид:
Вероятность отказа в обслуживании заявки определим как вероятность того, что при поступлении заявки в систему ее канал будет занят и все места в очереди также заняты:
(57)
Отсюда вероятность обслуживания (а также и относительная пропускная способность ) равны вероятности противоположного события:
Абсолютная пропускная способность – число заявок, обслуженных системой в единицу времени:
(59)
Среднее число заявок под обслуживанием:
(60)
(61)
Среднее число заявок в системе:
(62)
Одноканальную СМО с ограниченной очередью можно рассмотреть в Mathcad.
Пример :
На стоянке обслуживается 3 машины с интенсивностью потока 0,5 и средним временем обслуживания 2,5 минуты. Определить все показатели системы.
6 Многоканальная смо с неограниченной очередью
Пусть дана система S, имеющаяп каналов обслуживания, на которые поступает простейший поток требований интенсивностью λ. Пусть поток обслуживания также простейший и имеет интенсивность μ. Очередь на обслуживание не ограничена.
По числу заявок, находящихся в системе, обозначим состояния системы: S 0 ,S 1 ,S 2 ,…,S k ,… S n , гдеS k – состояние системы, когда в ней находитсяkзаявок (максимальное число заявок под обслуживанием -n). Граф состояний такой системы изображается в виде схемы на рисунке номер 6:
λ λ λ λ λ λ λ
……. …….
S 0 S 1 S 2 S m+1 S n
μ 2μ 3μ ………. kμ (k+1)μ …… nμ nμ
Рисунок 6: Многоканальная СМО с неограниченной очередью.
Интенсивность потока обслуживаний меняется в зависимости от состояния системы: kμ при переходе из состоянияS k в состояниеS k -1 так как может освободиться любой изk каналов; после того, как все каналы заняты обслуживанием, интенсивность потока обслуживаний остается равнойпμ, при поступлении в систему следующих заявок.
Для нахождения финальных вероятностей состояний получим формулы аналогично тому, как это было сделано для одноканальной системы.
(63)
Отсюда формулы для финальных вероятностей выражаются через
Для нахождения р 0 получим уравнение:
Для слагаемых в скобках, начиная с (n+ 2)-го, можно применить формулу нахождения суммы бесконечно убывающей геометрической прогрессии с первым членоми знаменателем ρ/n:
(66)
Окончательно получим формулу Эрланга для нахождения вероятности простоя системы:
(67)
Приведем формулы для расчета основных яоказателей эффективности работы системы.
Система будет справляться с потоком заявок, если
выполнено условие
, (68)
которое означает, что число заявок, поступивших в систему за единицу времени, не превосходит числа заявок, обслуженных системой за это же время. При этом вероятность отказа в обслуживании равна нулю.
Отсюда вероятность обслуживания (а также иотносительная пропускная способность системы) равны вероятности противоположного события, то есть единице:
(69)
Абсолютная пропускная способность - число заявок, обслуженныхсистемой в единицу времени:
(70)
Если система справляется с потоком заявок, то в стационарном режиме интенсивность выходящего потока равна интенсивности потока поступающих в систему заявок, так как обслуживаются все заявки:
ν=λ . (71)
Так как каждый канал обслуживает μ заявок в единицу времени, то среднее число занятых каналов можно вычислить:
(72)
Среднее время обслуживания каналом одной заявки;
. (73)
Вероятность того, что при поступлении в систему заявка окажется в очереди, равна вероятности того, что в системе находится более чем п заявок:
(74)
Число заявок, находящихся под обслуживанием, равно числу занятых каналов:
(75)
Среднее число заявок в очереди:
(76)
Тогда среднее число заявок в системе:
(77)
Среднее время пребывания заявки в системе (в очереди):
(78)
(79)
Многоканальную СМО с неограниченной очередью можно рассмотреть в системе Mathcad.
Пример 1 :
Салон-парикмахерская имеет 5 мастеров. В час пик интенсивность потока клиентов равна 6 человек. В час. Обслуживание одного клиента длится в среднем 40 минут. Определить среднюю длину очереди, считая ее неограниченной.
Фрагмент решения задачи в Mathcad.
Пример 2:
В железнодорожной кассе имеются 2 окна. Время на обслуживания одного пассажира 0,5 минут. Пассажиры подходят к кассе по 3 человека. Определить все характеристики системы.
Фрагмент решения задачи в Mathcad.
Продолжение решения задачи в Mathcad.
Многоканальная СМО с неограниченной очередью
Рассмотрим задачу. Имеется n-канальная СМО с неограниченной очередью. Поток заявок, поступающих в СМО, имеет интенсивность л., а поток обслуживаний -- интенсивность м. Необходимо найти предельные вероятности состояний СМО и показатели ее эффективности.
Система может находиться в одном из состояний S0, S1, S2, ..., Sk .., Sn, ..., нумеруемых по числу заявок, находящихся в СМО: S0 -- в системе нет заявок (все каналы свободны); S -- занят один канал, остальные свободны; S2-- заняты два канала, остальные свободны; Sk -- занято k каналов, остальные свободны; Sn -- заняты все n каналов (очереди нет); Sn+1 -- заняты все п каналов, в очереди одна заявка; Sn+r -- заняты все п каналов, r заявок стоит в очереди.
Граф состояний системы показан на рисунке 7. Обратим внимание на то, что в отличие от предыдущей СМО, интенсивность потока обслуживаний (переводящего систему из одного состояния в другое справа налево) не остается постоянной, а по мере увеличения числа заявок в СМО от 0 до n увеличивается от величины м до n??, так как соответственно увеличивается число каналов обслуживания. При числе заявок в СМО большем, чем n, интенсивность потока обслуживании сохраняется равной nм.
Рисунок 7 - Граф состояний многоканальной СМО
Можно показать, что при с/n < 1 предельные вероятности существуют. Если с/n ? 1, очередь растет до бесконечности. Используя формулы (20) и (21) для процесса гибели и размножения, можно получить следующие формулы для предельных вероятностей состояний n-канальной СМО с неограниченной очередью
Вероятность того, что заявка окажется в очереди,
Для n-канальной СМО с неограниченной очередью, используя прежние приемы, можно найти:
среднее число занятых каналов
среднее число заявок в системе
Среднее время пребывания заявки в очереди и среднее время пребывания заявки в системе, как и ранее, находятся по формулам Литтла (48) и (49).
Замечание. Для СМО с неограниченной очередью при с < 1 любая заявка, пришедшая в систему, будет обслужена, т.е. вероятность отказа Ротк = 0, Q=1, а равна интенсивности входящего потока заявок, т.е. А = л.
СМО с ограниченной очередью
СМО с ограниченной очередью отличаются лишь тем, что число заявок в очереди ограничено (не может превосходить некоторого заданного m). Если новая заявка поступает в момент, когда все места в очереди заняты, она покидает СМО необслуженной, т.е. получает отказ.
Одноканальная СМО с ограниченной длиной очереди
Предельные вероятности:
Вероятность отказа:
Абсолютная пропускная способность
Относительная пропускная способность
Среднее число заявок в очереди
Среднее число заявок под обслуживанием (среднее число занятых каналов)
Среднее число заявок в системе
Многоканальная СМО с ограниченной очередью
Предельные вероятности:
Вероятность отказа:
Абсолютная пропускная способность
Относительная пропускная способность
Среднее число заявок в очереди
Среднее число заявок под обслуживанием(среднее число занятых каналов)