- вероятность отказа канала, вероятность свободного канала, абсолютная пропускная способность;
- относительная пропускная способность, среднее время обслуживания, среднее время простоя канала.
Инструкция . Для решения подобных задач в онлайн режиме выберите модель СМО. Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Для одноканальной СМО с ограниченной длиной очереди можно указать длину очереди m , а для одноканальной СМО с неограниченной очередью - число заявок в очереди (для расчета вероятности нахождения этих заявок в очереди). см. пример решения . . Полученное решение сохраняется в файле Word .
Классификация одноканальных систем массового обслуживания
Пример №1 . Авто заправочная станция имеет одну бензоколонку. Предполагается что простейший поток автомашин поступает на станцию с интенсивностью λ=11 автомашин/ч. Время обслуживания заявки случайная величина которая подчиняется экспоненциальному закону с параметром μ=14 автомашин/ч. Определить среднее число автомашин на станции.
Пример №2
. Имеется пункт проведения профилактического осмотра машин с одной группой проведения осмотра. На осмотр и выявление дефектов каждой машины затрачивается в среднем 0,4 часа. На осмотр поступает в среднем 328 машин в сутки. Потоки заявок и обслуживаний - простейшие. Если машина, прибывшая в пункт осмотра не застает ни одного канала свободным, она покидает пункт осмотра необслуженной. Определить предельные вероятности состояний и характеристики обслуживания пункта профилактического осмотра.
Решение. Здесь α = 328/24 ≈ = 13.67, t = 0.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).
В систему поступает пуассоновский поток требований интенсивностью λ, поток обслуживания имеет интенсивность μ, максимальное число мест в очереди – т. Если заявка поступает в систему, когда все места в очереди заняты, она покидает систему необслуженной.
Финальные вероятности состояний такой системы всегда существуют, так как число состояний конечно:
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.
Для СМО с отказами :
Для СМО с неограниченным ожиданием как абсолютная, так и относительная пропускная способности теряют смысл, так как каждая поступившая заявка рано или поздно будет обслужена. Для такой СМО важными показателями являются:
Для СМО смешанного типа используются обе группы показателей: как относительная и абсолютная пропускная способности , так и характеристики ожидания.
В зависимости от цели операции массового обслуживания любой из приведенных показателей (или совокупность показателей) может быть выбран в качестве критерия эффективности.
Аналитической моделью СМО является совокупность уравнений или формул, позволяющих определять вероятности состояний системы в процессе ее функционирования и рассчитывать показатели эффективности по известным характеристикам входящего потока и каналов обслуживания.
Всеобщей аналитической модели для произвольной СМО не существует . Аналитические модели разработаны для ограниченного числа частных случаев СМО. Аналитические модели, более или менее точно отображающие реальные системы, как правило, сложны и труднообозримы.
Аналитическое моделирование СМО существенно облегчается, если процессы, протекающие в СМО, марковские (потоки заявок простейшие, времена обслуживания распределены экспоненциально). В этом случае все процессы в СМО можно описать обыкновенными дифференциальными уравнениями, а в предельном случае, для стационарных состояний - линейными алгебраическими уравнениями и, решив их, определить выбранные показатели эффективности.
Рассмотрим примеры некоторых СМО.
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.4 и совпадает с графом рис. 2.1 описывающим процесс «рождения--гибели», с тем отличием, что при наличии только одного канала.
Размеченный граф процесса «рождения - гибели» обслуживания все интенсивности потоков обслуживания равны
Состояния СМО можно представить следующим образом:
S0 - канал обслуживания свободен,
S, - канал обслуживания занят, но очереди нет,
S2- канал обслуживания занят, в очереди стоит одна заявка,
S3- канал обслуживания занят, в очереди стоят две заявки,
Sm+1 - канал обслуживания занят, в очереди все т мест заняты, любая следующая заявка получает отказ.
Для описания случайного процесса СМО можно воспользоваться изложенными ранее правилами и формулами. Напишем выражения, определяющие предельные вероятности состояний:
Выражение для р0 можно в данном случае записать проще, пользуясь тем, что в знаменателе стоит геометрическая прогрессия относительно р, тогда после соответствующих преобразований получаем:
с= (1- с)
Эта формула справедлива для всех р, отличных от 1, если же р = 1, то р0 = 1/(т + 2), а все остальные вероятности также равны 1/(т + 2).
Если предположить т = 0, то мы переходим от рассмотрения одноканальной СМО с ожиданием к уже рассмотренной одноканальной СМО с отказами в обслуживании.
Действительно, выражение для предельной вероятности р0в случае т = 0 имеет вид:
pо = м / (л+м)
И в случае л =м имеет величину р0= 1 / 2.
Определим основные характеристики одноканальной СМО с ожиданием: относительную и абсолютную пропускную способность, вероятность отказа, а также среднюю длину очереди и среднее время ожидания заявки в очереди.
Заявка получает отказ, если она поступает в момент времени, когда СМО уже находится в состоянии Sm+1 и, следовательно, все места в очереди да заняты и один канал обслуживает
Поэтому вероятность отказа определяется вероятностью появлением
Состояния Sm+1:
Pотк = pm+1 = сm+1 * p0
Относительная пропускная способность, или доля обслуживаемых заявок, поступающих в единицу времени, определяется выражением
Q = 1- pотк = 1- сm+1 * p0
абсолютная пропускная способность равна:
Среднее число заявок Lочстоящих в очереди на обслуживание, определяется математическим ожиданием случайной величины к - числа заявок, стоящих в очереди
случайная величина к принимает следующие только целочисленные значения:
- 1 - в очереди стоит одна заявка,
- 2 - в очереди две заявки,
т-в очереди все места заняты
Вероятности этих значений определяются соответствующими вероятностями состояний, начиная с состояния S2. Закон распределения дискретной случайной величины к изображается следующим образом:
Таблица 1. Закон распределения дискретной случайной величины
Математическое ожидание этой случайной величины равно:
Lоч = 1* p2 +2* p3 +...+ m* pm+1
В общем случае при p ?1 эту сумму можно преобразовать, пользуясь моделями геометрической прогрессии, к более удобному виду:
Lоч = p2 * 1- pm * (m-m*p+1) * p0
В частном случае при р = 1, когда все вероятности pkоказываются равными, можно воспользоваться выражением для суммы членов числового ряда
1+2+3+ m = m(m+1)
Тогда получим формулу
L"оч= m(m+1) * p0 = m(m+1) (p=1).
Применяя аналогичные рассуждения и преобразования, можно показать, что среднее время ожидания обслуживания заявки а очереди определяется формулами Литтла
Точ = Lоч/А (при р? 1) и Т1оч= L"оч /А(при р = 1).
Такой результат, когда оказывается, что Точ ~ 1/ л, может показаться странным: с увеличением интенсивности потока заявок как будто бы должна возрастать длина очереди и уменьшается среднее время ожидания. Однако следует иметь в виду, что, во-первых, величина Lоч является функцией от л и м и, во-вторых, рассматриваемая СМО имеет ограниченную длину очереди не более mзаявок.
Заявка, поступившая в СМО в момент времени, когда все каналы заняты, получает отказ, и, следовательно, время ее «ожидания» в СМО равно нулю. Это приводит в общем случае (при р? 1) к уменьшению Точростом л, поскольку доля таких заявок с ростом л увеличивается.
Если отказаться от ограничения на длину очереди, т.е. устремить m--> >?, то случаи р < 1 и р?1 начинают существенно различаться. Записанные выше формулы для вероятностей состояний преобразуются в случае р < 1 к виду
При достаточно большом к вероятностьpk стремится к нулю. Поэтому относительная пропускная способность будет Q= 1, а абсолютная пропускная способность станет равной А --л Q -- л следовательно, обслуживаются все поступившие заявки, причем средняя длина очереди окажется равной:
Lоч =p2 1-p
а среднее время ожидания по формуле Литтла
Точ = Lоч/А
В пределе р << 1 получаем Точ = с / м т.е. среднее время ожидания быстро уменьшается с увеличением интенсивности потока обслуживания. В противном случае при р? 1 оказывается, что в СМО отсутствует установившийся режим. Обслуживание не успевает за потоком заявок, и очередь неограниченно растет со временем (при t > ?). Предельные вероятности состояний поэтому не могут быть определены: при Q= 1 они равны нулю. Фактически СМО не выполняет своих функций, поскольку она не в состоянии обслужить все поступающие заявки.
Нетрудно определить, что доля обслуживаемых заявок и абсолютная пропускная способность соответственно составляют в среднем с и м, однако неограниченное увеличение очереди, а следовательно, и времени ожидания в ней приводит к тому, что через некоторое время заявки начинают накапливаться в очереди на неограниченно долгое время.
В качестве одной из характеристик СМО используют среднее время Тсмо пребывания заявки в СМО, включающее среднее время пребывания в очереди и среднее время обслуживания. Эта величина вычисляется по формулам Литтла: если длина очереди ограничена -- среднее число заявок, находящихся в очереди, равно:
Lсмо= m+1 ;2
Тсмо= Lсмо; при p ?1
A тогда среднее время пребывания заявки в системе массового обслуживания (как в очереди, так и под обслуживанием) равно:
Тсмо= m+1 при p ?1 2м