Ранее отмечалось, что СМО можно разбить на две группы - разомкнутые и замкнутые. Типичным представителем систем разомкнутого типа являются предприятие по капитальному ремонту электрических машин, на которое поступают вышедшие из строя электротехнические изделия из многих объектов. Поток отказов электрических машин является случайным, случайным является и объект, из которого поступили заявки.
Замкнутые СМО относятся к классу циклических систем. Для замкнутых СМО характерно конечное число заявок, циркулирующих в системе «источник-СМО». Обслуженные заявки возвращаются в источник и через некоторое время (в общем случае случайное), могут вновь появиться на входе. Поведение источника в замкнутых СМО является некоторой функцией состояния СМО. В связи с этим поток на выходе системы в какой-то мере определяет входящий поток.
Простейшим примером замкнутой СМО может служить работа дежурного электромонтера на объекте, имеющем п электроустановок.
В случае возникновения неисправности электромонтер обслуживает одну электроустановку. Отремонтированное изделие остается на своем рабочем месте и снова становится потенциальным источником на новую заявку, т. е. повторно может выйти из строя и потребовать ремонта. В таких системах, как правило, общее число поступающих заявок ограничено размером объекта и в большинстве случаев является постоянной величиной.
Будем считать, что плотность поступления заявок на обслуживание от электроустановок равна X, число заявок имеет пуассоновское распределение, а время обслуживания распределено по показательному закону с параметром р. В системе могут находиться как обслуженные заявки, так и те, которые стали в очередь и ожидают, пока обслуживаемый канал освободится.
Схема возможных состояний такой системы показана на рис. 1.13.
Рис. 1.13.
Система может иметь следующие состояния:
s 0 - все электроустановки исправны и электромонтер не занят их обслуживанием;
Sj - электромонтер обслуживает одну электроустановку, остальные электроустановки работают;
s 2 - две электроустановки неисправны, одна ремонтируется, вторая находится в очереди;
s k - к электроустановок неисправны, одна ремонтируется, к - 1 стоят в очереди;
s n - п электроустановок неисправны, одна ремонтируется, п - 1 ожидают ремонта.
Стрелки на схеме показывают переходы из одного состояния в другое с интенсивностями X и р.
При переходе системы из состояния s 0 в состояние Sj интенсивность потока неисправностей равна пХ (поток неисправностей всех работающих электроустановок).
При переходе системы из состояния Sj в состояние s 2 интенсивность потока неисправностей уже определяется п - 1 работающими электроустановками (одно изделие находится в ремонте) и т. д.
При переходе же системы по стрелкам справа налево интенсивность потока событий р одинакова (принимается одинаковое время устранения неисправностей в электроустановках).
Такие СМО исследовал К. Пальм, который вывел и получил удобные и простые уравнения для определения вероятностей состояния системы:
Пример 1.15. Дежурный электромонтер на птицефабрике обслуживает 3 объекта. На каждом из объектов в сутки возникает по две неисправности. Процесс устранения неисправности занимает у электромонтера 1 ч. Необходимо рассчитать вероятности состояний, вероятность занятости электромонтера, абсолютную пропускную способность системы.
До сих пор мы рассматривали такие системы массового обслуживания, где заявки приходили откуда-то извне интенсивность потока заявок не зависела от состояния самой системы. В настоящем параграфе мы рассмотрим системы массового обслуживания другого типа - такие, в которых интенсивность потока поступающих заявок зависит от состояния самой СМО. Такие системы массового обслуживания называются замкнутыми.
В качестве примера замкнутой СМО рассмотрим следующую систему. Рабочий-наладчик обслуживает станков. Каждый станок может в любой момент выйти из строя и потребовать обслуживания со стороны наладчика. Интенсивность потока неисправностей каждого станка равна X. Вышедший из строя станок останавливается. Если в этот момент рабочий свободен, он берется за наладку станка; на это он тратит среднее время
где - интенсивность потока обслуживаний (наладок).
Если в момент выхода станка из строя рабочий занят, станок становится в очередь на обслуживание и ждет, пока рабочий не освободится.
Требуется найти вероятности состояний данной системы и ее характеристики:
Вероятность того, что рабочий не будет занят,
Вероятность наличия очереди,
Среднее число станков, ожидающих очереди на ремонт и т. д.
Перед нами - своеобразная система массового обслуживания, где источниками заявок являются станки, имеющиеся в ограниченном количестве и подающие или не подающие заявки в зависимости от своего состояния: при выходе станка из строя он перестает быть источником новых заявок. Следовательно, интенсивность общего потока заявок, с которым приходится иметь дело рабочему, зависит от того, сколько имеется неисправных станков, т. е. сколько заявок связано с процессом обслуживания (непосредственно обслуживается или стоит в очереди).
Характерным для замкнутой системы массового обслуживания является наличие ограниченного числа источников заявок.
В сущности, любая СМО имеет дело только с ограниченным числом источников заявок, но в ряде случаев число этих источников так велико, что можно пренебречь влиянием состояния самой СМО на поток заявок. Например, поток вызовов на АТС крупного города исходит, в сущности, от ограниченного числа абонентов, но это число так велико, что практически можно считать интенсивность потока заявок независимой от состояний самой АТС (сколько каналов занято в данный момент). В замкнутой же системе массового обслуживания источники заявок, наряду с каналами обслуживания, рассматриваются как элементы СМО.
Рассмотрим сформулированную выше задачу о рабочем-наладчике в рамках общей схемы марковских процессов.
Система, включающая рабочего и станков, имеет ряд состояний, которые мы будем нумеровать по числу неисправных станков (станков, связанных с обслуживанием):
Все станки исправны (рабочий свободен),
Один станок неисправен, рабочий занят его наладкой,
Два станка неисправны, один налаживается, другой ожидает очереди,
Все станков неисправны, один налаживается, стоят в очереди.
Граф состояний приведен на рис. 5.9. Интенсивности потоков событий, переводящих систему из состояния в состояние, проставлены у стрелок. Из состояния систему переводит поток неисправностей всех работающих станков; его интенсивность равна Из состояния S в систему переводит поток неисправностей уже не а станков (работают всего ) и т. д. Что касается интенсивностей потоков событий, переводящих систему по стрелкам справа налево, то они все одинаковы - работает все время один рабочий с интенсивностью обслуживания
Пользуясь, как обычно, общим решением задачи о предельных вероятностях состояний для схемы гибели и размножения (§8 гл. 4), напишем предельные вероятности состояний:
Вводя, как и раньше, обозначения перепишем эти формулы в виде
Итак, вероятности состояний СМО найдены.
В силу своеобразия замкнутой СМО, характеристики ее эффективности будут отличны от тех, которые мы применяли ранее для СМО с неограниченным количеством источников заявок.
Роль «абсолютной пропускной способности» в данном случае будет играть среднее количество неисправностей, устраняемых рабочим в единицу времени. Вычислим эту характеристику. Рабочий занят наладкой станка с вероятностью
Если он занят, он обслуживает станков (ликвидирует неисправностей) в единицу времени; значит, абсолютная пропускная способность системы
Относительную пропускную способность для замкнутой СМО мы не вычисляем, так как каждая заявка, в конце концов, будет обслужена:
Вероятность того, что рабочий не будет занят:
Вычислим среднее число неисправных станков, иначе - среднее число станков, связанных с процессом обслуживания. Обозначим это среднее число w. Вообще говоря, величину w можно вычислить непосредственно, по формуле
но проще будет найти ее через абсолютную пропускную способность А.
Действительно, каждый работающий станок порождает поток неисправностей с интенсивностью к; в нашей СМО в среднем работает станков; порождаемый ими средний поток неисправностей будет иметь среднюю интенсивность все эти неисправности устраняются рабочим, следовательно,
Определим теперь среднее число станков , ожидающих наладки в очереди. Будем рассуждать следующим образом: общее число станков W, связанных с обслуживанием, складывается из числа станков R, стоящих в очереди, плюс число станков непосредственно находящихся под обслуживанием:
Число станков , находящихся под обслуживанием, равно единице, если рабочий занят, и нулю, если он свободен, т. е. среднее значение Й равно вероятности того, что рабочий занят:
Вычитая эту величину из среднего числа w станков, связанных с обслуживанием (неисправных), получим среднее число станков, ожидающих обслуживания в очереди:
Остановимся еще на одной характеристике эффективности СМО: на производительности группы станков, обслуживаемых рабочим.
Зная среднее число неисправных станков w и производительность исправного станка за единицу времени, можно оценить среднюю потерю L производительности группы станков в единицу времени за счет неисправностей;
Пример 1. Рабочий обслуживает группу из трех станков. Каждый станок останавливается в среднем 2 раза в час Процесс наладки занимает у рабочего, в среднем, 10 минут Определить характеристики замкнутой СМО: вероятность занятости рабочего; его абсолютную пропускную способность А; среднее количество неисправных станков; среднюю относительную потерю производительности группы станков за счет неисправностей
Решение. Имеем.
По формулам (8.1)
Вероятность занятости рабочего:
Абсолютная пропускная способность рабочего (среднее число неисправностей, которое он ликвидирует в час):
Среднее число неисправных станков находим по формуле (8.5):
Средняя относительная потеря производительности группы станков за счет неисправностей , т. е. за счет неисправностей группа станков теряет около 35% производительности.
Рассмотрим теперь более общий пример замкнутой СМО: бригада из рабочих обслуживает станков Перечислим состояния системы.
До сих пор мы рассматривали такие системы массового обслуживания, где заявки приходили откуда-то извне и интенсивность потока заявок не зависела от состояния самой системы. Сейчас мы рассмотрим системы массового обслуживания другого типа – такие, в которых интенсивность потока поступающих заявок зависит от состояния самой СМО. Такие системы массового обслуживания называются замкнутыми.
Примером замкнутой СМО может служить, например, следующая система. Рабочий-наладчик обслуживает m станков. Каждый станок может в любой момент выйти из строя и потребовать обслуживания со стороны наладчика. Интенсивность потока неисправностей каждого станка равна . Вышедший из строя станок останавливается. Если в этот момент рабочий свободен, он берется за наладку станка; на это он тратит среднее время t обсл =1/ , где – интенсивность потока обслуживаний (наладок).
Если в момент выхода станка из строя рабочий занят, станок становится в очередь на обслуживание и ждет, пока рабочий не освободится.
Иными словами, мы имеем СМО с m источниками, каждый из которых может выдать заявку и после этого ожидает окончания обслуживания этой заявки. Если в приведенном примере станки обслуживаются бригадой из n наладчиков, то СМО становится многоканальной.
Другим примером может быть система с центральным процессором и удаленными терминалами. Пользователь, отправивший запрос с терминала не может выдать новый запрос, пока не получит сообщения от процессора об окончании обработки предыдущего.
Характерным для замкнутой системы массового обслуживания является наличие ограниченного числа источников заявок.
В сущности, любая СМО имеет дело только с ограниченным числом источников заявок, но в ряде случаев число этих источников так велико, что можно пренебречь влиянием состояния самой СМО на поток заявок. Например, поток вызовов на АТС крупного города исходит, в сущности, от ограниченного числа абонентов, но это число так велико, что практически можно считать интенсивность потока заявок независимой от состояний самой АТС (сколько каналов занято в данный момент). В замкнутой же системе массового обслуживания источники заявок, наряду с каналами обслуживания, рассматриваются как элементы СМО.
Построим аналитическую модель такой системы.
Сначала рассмотрим случай с одним обслуживающим прибором и количеством источников равным m. Состояния будем кодировать числом выданных заявок. Диаграмма интенсивностей переходов для данной системы изображена на рис.2.17.
Рис. 2.17. ДИП для одноканальной замкнутой СМО
Определим вероятности состояний.
Исходя из уравнения нормировки, получаем
Найдем характеристики эффективности замкнутой СМО.
Абсолютная пропускная способность – это среднее количество заявок, обслуживаемых каналом в единицу времени. Вычислим эту характеристику. Канал занят обслуживанием заявок с вероятностью
Р зан = 1-Р 0 =1-р .
Если он занят, то обслуживает в среднем μ заявок в единицу времени. Таким образом, абсолютная пропускная способность системы
А = (1-р ) μ .
Так как каждая заявка, в конце концов, будет обслужена, то относительная пропускная способность q = 1.
Вычислим среднее число заявок, ожидающих обслуживания,иначе - среднее число источников, выдавших заявку и ожидающих ответа. По сути, это количество заявок, находящихся в данный момент в системе L c . Вообще говоря, эту величину можно вычислить непосредственно, по формуле
L
c
= 1
Р
1
+ 2
Р
2
+…+ m
Р
m ,
но проще будет найти ее через абсолютную пропускную способность А.
Каждый источник, еще не выдавший заявку, порождает поток заявок с интенсивностью . Таких источников m - L c , а поток, порождаемый ими имеет интенсивность (m - L c) . Все эти заявки будут обслужены каналом, следовательно,
(m - L c) = (1-р ) μ ,
L
c
=
Определим теперь среднее число источников, выдавших заявки, обслуживание которых еще не началось. Фактически, это количество заявок в очереди L оч.
Среднее
число заявок в системе L
c
складывается из числа заявок в очереди
L
оч
и среднего числа заявок, находящихся
под обслуживанием в канале
:
L
c
= L
оч
+
.
В канале может находиться 0 заявок с вероятностью р или 1 с вероятностью 1- р , следовательно,
L
оч
=
.
Теперь перейдем к случаю с несколькими каналами обслуживания. Будем кодировать состояния общим числом выданных источниками и еще не обслуженных заявок. Так как источник не может выдать новую заявку до окончания обслуживания предыдущей, то интенсивностьобщего потока заявок зависит от того, сколько заявок связано с процессом обслуживания (непосредственно обслуживается или стоит в очереди). Количество источников –m , число каналов –n (n < m ). Диаграмма интенсивностей переходов для данной системы изображена на рис. 2.18.
Рис.
2.18. ДИП для многоканальной замкнутой
СМО
Требуется найти вероятности состояний данной системы и ее характеристики.
,
i
=1,
2,…,n
.
При i > n возникает ситуация, когда n заявок обслуживаются, а i - n ожидают обслуживания.
Подставляя в выражения для P n + i и P m полученное выше значение P n , получаем
Исходя из уравнения нормировки, определим значение p :
Через вычисленные вероятности может быть определено среднее число занятых каналов:
Абсолютная пропускная способность системы
Пример. Рабочий обслуживает группу из трех станков. Каждый станок останавливается в среднем 2 раза в час Процесс наладки занимает у рабочего, в среднем, 10 минут Определить характеристики замкнутой СМО: вероятность занятости рабочего; его абсолютную пропускную способность А ; среднее количество неисправных станков L c . Все потоки полагаем простейшими.
Решение.
Имеем п
=
3,
λ
= 2, μ
=
=
6,
.
Определяем по формулам для одноканальной замкнутой СМО
Вероятность занятости рабочего:
Р зан =1-Р 0 =1-р =0,654.
Абсолютная пропускная способность (среднее число неисправностей, которое рабочий ликвидирует в час):
Среднее число неисправных станков:
L
c
=
Инструкция . Укажите интенсивность потока заявок λ и интенсивность потока обслуживания μ . Полученное решение сохраняется в файле Word (см. на примере модели обслуживания машинного парка).
Характеристики функционирования замкнутой одноканальной СМО
| № п/п | Предельные характеристики | Обозначения, формулы |
| 1 | Показатель (коэффициент) нагрузки системы, порождаемой каждым источником заявок | ρ = λ/μ |
| 2 | Показатель (коэффициент) нагрузки системы, порождаемой всеми i источниками заявок | i ρ = i λ/μ |
| 3 | Вероятность того, что канал свободен | |
| 4 | Вероятность состояний СМО |  |
| 5 | Вероятность того, что канал занят | р зан = 1 – р 0 |
| 6 | Абсолютная пропускная способность СМО | A = p зан μ = (1 - p 0)μ |
| 7 | Интенсивность выходящего потока обслуженных заявок | v=A=p зан μ = (1-p 0)μ |
| 8 | Относительная пропускная способность | Q = 1 |
| 9 | Среднее число заявок в системе (т.е. среднее число источников, находящихся в пассивном состоянии) |
 |
| 10 | Средняя интенсивность среднего суммарного входящего потока заявок |
 |
| 11 | Среднее число заявок, находящихся под обслуживанием | |
| 12 | Среднее число заявок, находящихся в очереди |  |
| 13 | Коэффициент готовности – вероятность того, что произвольный источник находится в активном состоянии |  |
| 14 | Вероятность того, что в момент поступления заявки СМО находилась в состоянии s k |
 |
| 15 | Среднее время ожидания заявки в очереди |  |
| 16 | Среднее время обслуживания одной заявки |  |
| 17 | Среднее время пребывания заявки в системе |  |
| 18 | Средняя производительность группы источников, находящихся в активном состоянии |
 |
| 19 | Средняя потеря производительности за счёт группы источников, находящихся в пассивном состоянии |  |
Пример №1 . Один ремонтный рабочий обслуживает 6 подъемных устройств на станции технического обслуживания автомобилей. Интенсивность поломок каждого устройства равна 0.1 в сутки. Среднее время, которое тратит рабочий на обслуживание одного подъемника, равно X часов. Найти предельные вероятности состояний данной СМО и найти среднее число неисправных подъемников, т.е. находящихся в ремонте и ожидающих ремонта. Определить также следующие характеристики:
- вероятность того, что наладчик занят ремонтом подъемников;
- абсолютную пропускную способность СМО;
- относительную пропускную способность СМО;
- среднее число подъемников в ремонте;
- среднее число подъемников, ожидающих в очереди ремонта.
Пример №2 . СМО состоит из n идентичных приборов, каждый из которых выходит из строя в случайные моменты времени с интенсивностью λ. В случае выхода прибора из строя он начинает сразу восстанавливаться одним из m свободных восстанавливающих устройств (ВУ) с интенсивностью μ. Если все ВУ заняты, то прибор встает в очередь и ждет до тех пор, пока не освободится ВУ. Каждое ВУ в любой момент времени может восстанавливать не более одного прибора. Требуется оценить надежность работы системы и дать предложения по повышению эффективности ее функционирования.
Теория массового обслуживания
§1. Марковские цепи с конечным числом состояний и дискретным временем.
Пусть некоторая система S может находиться в одном из состояний конечного (или счетного) множества возможных состояний S 1, S 2,…, S n, а переход из одного состояния в другое возможен только в определенные дискретные моменты времени t 1, t 2, t 3, …, называемые шагами .
Если система переходит из одного состояния в другое случайно, то говорят, что имеет место случайный процесс с дискретным временем .
Случайный процесс называется марковским , если вероятность перехода из любого состояния S i в любое состояние S j не зависит от того, как и когда система S попала в состояние S i (т. е. в системе S отсутствует последствие). В таком случае говорят, что функционирование системы S описывается дискретной цепью Маркова .
Переходы системы S в различные состояния удобно изображать с помощью графа состояний (рис.1).
Рис. 1
Вершины графа S 1, S 2, S 3 обозначают возможные состояния системы. Стрелка, направленная из вершины S i в вершину S j обозначает переход S i → S j; число, стоящее рядом со стрелкой, обозначает величину вероятности этого перехода. Стрелка, замыкающаяся на i -той вершине графа, обозначает, что система остается в состоянии S i с вероятностью, стоящей у стрелки.
Графу системы, содержащему n вершин, можно поставить в соответствие матрицу n ´n , элементами которой являются вероятности переходов p ij между вершинами графа. Например, граф на рис.1 описывается матрицей P :
https://pandia.ru/text/78/171/images/image003_65.gif" width="95" height="33 src="> (1.1)
Условие (1.1) - обычное свойство вероятностей, а условие (1.2) (сумма элементов любой стрелки равна 1) означает, что система S обязательно либо переходит их какого-то состояния S i в другое состояние, либо остается в состоянии S i.
Элементы матрицы дают вероятности переходов в системе за один шаг. Переход S i → S j за два шага можно рассматривать как происходящий на первом шаге из S i в некоторое промежуточное состояние S k и на втором шаге из S k в S i. Таким образом, для элементов матрицы вероятностей переходов из S i в S j за два шага получим:
(1.3)
В общем случае перехода S i → S j за m шагов для элементов https://pandia.ru/text/78/171/images/image008_47.gif" width="164 height=58" height="58">, 1 ≤ l ≤ m
Полагая в (1.4) l = 1 и l = m - 1 получим два эквивалентных выражения для https://pandia.ru/text/78/171/images/image009_45.gif" width="162" height="65 src="> (1.5)
. (1.6)
Пример 1. Для графа на рис.1 найти вероятность перехода системы из состояния S 1 в состояние S 2 за 3 шага.
Решение.
Вероятность перехода S
1 → S
2 за 1 шаг равна 
. Найдем вначале , используя формулу (1.5), в которой полагаем m
= 2.
https://pandia.ru/text/78/171/images/image014_31.gif" width="142" height="54 src=">.
Как видно из этой формулы, в дополнение к необходимо вычислить также https://pandia.ru/text/78/171/images/image016_30.gif" width="38" height="30">:
https://pandia.ru/text/78/171/images/image018_27.gif" width="576" height="58 src=">
Таким образом
https://pandia.ru/text/78/171/images/image020_25.gif" width="156" height="123 src=">.
Если обозначить через P (m) матрицу, элементами которой являются - вероятности переходов из S i в S j за m шагов, то справедлива формула
P (m) = P m, (1.7)
где матрица P m получается умножением матрицы P саму на себя m раз.
Исходное состояние системы характеризуется вектором состояния системы (называемым также стохастическим вектором ).
= (q 1, q 2,…,q n),
где q j-вероятность того, что исходным состоянием системы является S j состояние. Аналогично (1.1) и (1.2) справедливы соотношения
0 ≤ q i ≤1; https://pandia.ru/text/78/171/images/image025_19.gif" width="218 height=35" height="35">
вектор состояния системы после m шагов, где - вероятность того, что после m шагов система находится в S i состоянии. Тогда справедлива формула
(1.8)
Пример 2. Найти вектор состояния системы, изображенный на рис.1 после двух шагов.
Решение. Исходное состояние системы характеризуется вектором =(0,7; 0; 0,3). После первого шага (m = 1) система перейдет в состояние
После второго шага система окажется в состоянии
Ответ: Состояние системы S после двух шагов характеризуется вектором (0,519; 0,17; 0,311).
При решении задач в примерах 1, 2 предполагалось, что вероятности переходов P ij остаются постоянными. Такие марковские цепи называются стационарными. В противном случае марковская цепь называется нестационарной.
§2. Марковские цепи с конечным числом состояний и непрерывным временем.
Если система S может переходить в другое состояние случайным образом в произвольный момент времени, то говорят о случайном процессе с непрерывным временем. В отсутствии последействия такой процесс называется непрерывной марковской цепью. При этом вероятности переходов S i → S j для любых i и j в любой момент времени равны нулю (в силу непрерывности времени). По этой причине вместо вероятности перехода P ij вводится величина λij - плотность вероятности перехода из состояния S i в состояние S j, определяемая как предел
; (i
≠ j
). (2.1)
Если величины λ ij не зависят от t , то марковский процесс называется однородным. Если за время Δt система может изменить свое состояние не более чем один раз, то говорят, что случайный процесс является ординарным. Величину λ ij называют интенсивностью перехода системы из S i в S j. На графе состояний системы численные значения λ ij ставят рядом со стрелками, показывающими переходы в вершины графа (рис. 2).
https://pandia.ru/text/78/171/images/image036_12.gif" width="101 height=62" height="62"> (2.2)
Распределение вероятностей состояний системы, которое можно характеризовать вектором https://pandia.ru/text/78/171/images/image038_11.gif" width="21 height=27" height="27"> являются константами.
Состояния S i и S j называются сообщающимися, если возможны переходы S i ↔ S j (на рис. 2 сообщающимися являются состояния S 1 и S 2, а S 1, S 3 и S 2, S 3 такими не являются).
Состояние S i называется существенным, если всякое S j, достижимое из S i, является сообщающимся с S i. Состояние S i называется несущественным, если оно не является существенным (на рис. 2 существенными являются состояния S 1 и S 2).
Если существуют предельные вероятности состояний системы
(2.3)
не зависящие от начального состояния системы, то говорят, что при t → ∞ в системе устанавливается стационарный режим.
Система, в которой существуют предельные (финальные) вероятности состояний системы, называется эргодической, а протекающий в ней случайный процесс эргодическим.
Теорема 1. Если S i – несущественное состояние, то
(2.4)
т. е. при t → ∞ система выходит из любого несущественного состояния (для системы на рис. 2 
т. к. S
3 – несущественное состояние).
Теорема 2. Чтобы система с конечным числом состояний имела единственное предельное распределение вероятностей состояний, необходимо и достаточно, чтобы все ее существенные состояния сообщались между собой (система на рис.2 удовлетворяет этому условию, т. к. существенные состояния S 1 и S 2 сообщаются между собой).
Если случайный процесс, происходящий в системе с дискретными состояниями является непрерывной марковской цепью, то для вероятностей p 1(t ), p 2(t ),…, p n(t ) можно составить систему линейных дифференциальных уравнений, называемых уравнениями Колмогорова. При составлении уравнений удобно пользоваться графом состояний системы. Рассмотрим получение уравнений Колмогорова на конкретном примере.
Пример 3. Записать уравнения Колмогорова для системы, изображенной на рис.2. Найти финальные вероятности для состояний системы.
Решение. Рассмотрим вначале вершину графа S 1. Вероятность p 1(t + Δt ) того, что система в момент времени (t + Δt ) будет находиться в состоянии S 1 достигается двумя способами:
а) система в момент времени t с вероятностью p 1(t ) находилась в состоянии S 1 и за малое время Δt не перешла в состояние S 2. Из состояния S 1 система может быть выведена потоком интенсивностью λ 12; вероятность выхода системы из состояния S 1 за время Δt при этом равна (с точностью до величин более высокого порядка малости по Δt ) λ 12 Δt , а вероятность невыхода из состояния S 1 будет равна (1 - λ 12 Δt ). При этом вероятность того, что система останется в состоянии S 1, согласно теореме об умножении вероятностей будет равна p 1(t ) (1 - λ 12 Δt ).
б) система в момент времени t находилась в состоянии S 2 и за время Δt под воздействием потока λ 21 перешла в состояние S 1 с вероятностью λ 21 Δt S 1 равна p 2(t )∙λ 21Δt .
в) система в момент времени t находилась в состоянии S 3 и за время Δt под воздействием потока λ 31 перешла в состояние S 1 с вероятностью λ 31 Δt . Вероятность того, что система будет находиться в состоянии S 1 равна p 3(t )∙λ 31Δt .
По теореме сложения вероятностей получим:
p 1(t + Δt ) = p 1(t ) (1 - λ12 Δt ) + p 2(t ) (1 - λ21 Δt ) + p 3(t ) (1 – λ31 Δt );https://pandia.ru/text/78/171/images/image043_10.gif" width="20" height="16 src=">
https://pandia.ru/text/78/171/images/image045_11.gif" width="269" height="46 src="> (2.5)
Аналогично, рассматривая вершины графа S 2 и S 3 , получим уравнения
, (2.6)
https://pandia.ru/text/78/171/images/image048_10.gif" width="217" height="84 src=">
Из последнего уравнения следует, что p 3 = 0. Решая оставшиеся уравнения, получим p 1= 2/3, p 2 = 1/3.
Ответ: вектор состояния системы в стационарном режиме равен 
С учетом рассмотренного примера сформулируем общее правило составления уравнений Колмогорова:
В левой части каждого из них стоит производная вероятности какого-то (j -го) состояния. В правой части - сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков, минус суммарная интенсивность всех потоков, выводящих систему из данного (j -го) состояния, умноженная на вероятность данного (j -го) состояния.
§3. Процессы рождения и гибели.
Так называется широкий класс случайных процессов, происходящих в системе, размеченный граф состояний которой изображен на рис. 3.
https://pandia.ru/text/78/171/images/image054_9.gif" width="32" height="12">.gif" width="61" height="12">μ0 μ1 μ2 μg-2 μg-1
Здесь величины λ 0, λ 1,…, λ g-1 - интенсивности переходов системы из состояния в состояние слева направо, можно интерпретировать как интенсивности рождения (возникновения заявок) в системе. Аналогично, величины μ 0, μ 1,…, μ g-1 - интенсивности переходов системы из состояния в состояние справа налево, можно интерпретировать как интенсивности гибели (выполнения заявок) в системе.
Поскольку все состояния являются сообщающимися и существенными, существует (в силу теоремы 2) предельное (финальное) распределение вероятностей состояний. Получим формулы для финальных вероятностей состояний системы.
В стационарных условиях для каждого состояния поток, втекающий в данное состояние должен равняться потоку, вытекающему из данного состояния. Таким образом, имеем:
для состояния S 0:
p 0∙λ 0Δt = p 1∙μ 0Δt ;λ 0 p 0 = μ 0 p 1;
для состояния S 1:
р 1·(λ 1 + μ 0)Δt = p 0∙λ 0Δt + p 2∙μ 1·Δt ;(λ 1 + μ 0) p 1 = λ 0 p 0 + μ 1p 2.
Последнее уравнение с учётом предыдущего можно привести к виду λ 1 p 1 = μ 1p 2 . Аналогично можно получить уравнения для остальных состояний системы. В результате получится система уравнений:
https://pandia.ru/text/78/171/images/image059_9.gif" width="12" height="23 src=">.gif" width="94" height="54 src=">
(3.3)
§4. Основные понятия и классификация систем массового обслуживания. Простейший поток заявок.
Заявкой (или требованием ) называется спрос на удовлетворение какой-либо потребности (далее потребности предполагаются однотипными). Выполнение заявки называется обслуживанием заявки.
Системой массового обслуживания (СМО) называется любая система для выполнения заявок, поступающих в неё в случайные моменты времени.
Поступление заявки в СМО называется событием. Последовательность событий, заключающихся в поступлении заявок в СМО, называется входящим потоком заявок. Последовательность событий, заключающихся в выполнении заявок в СМО, называется выходящим потоком заявок.
Поток заявок называется простейшим , если он удовлетворяет следующим условиям:
1)отсутствие последействия , т. е. заявки поступают независимо друг от друга;
2)стационарность, т. е. вероятность поступления данного числа заявок на любом временнóм отрезке [t 1, t 2] зависит лишь от величины этого отрезка и не зависит от значения t 1, что позволяет говорить о среднем числе заявок за единицу времени, l, называемом интенсивностью потока заявок ;
3)ординарность, т. е. в любой момент времени в СМО поступает лишь одна заявка, а поступление одновременно двух и более заявок пренебрежимо мало.
Для простейшего потока вероятность p i(t ) поступления в СМО ровно i заявок за время t вычисляется по формуле
(4.1)
т. е. вероятности распределены по закону Пуассона с параметром lt . По этой причине простейший поток называется также пуассоновским потоком .
Функция распределения F (t ) случайного интервала времени T между двумя последовательными заявками по определению равна F (t ) = P (T < t ). Но P (T <t )=1 - P (T ≥ t ), где P (T ≥ t ) – вероятность того, что следующая после последней заявки поступит в СМО по истечении времени t , т. е. за время t в СМО не поступит ни одна заявка. Но вероятность этого события находится из (4.1) при i = 0. Таким образом,
P (T https://pandia.ru/text/78/171/images/image067_9.gif" width="177" height="28 src="> (t > 0),
а математическое ожидание, дисперсия и среднее квадратическое отклонение случайной величины T равны соответственно
https://pandia.ru/text/78/171/images/image069_9.gif" width="91" height="39 src=">.gif" width="364" height="48 src=">;
б) при решении этого пункта целесообразно использовать противоположную вероятность:
https://pandia.ru/text/78/171/images/image073_8.gif" width="167" height="30 src=">.gif" width="243" height="31 src=">.gif" width="72 height=31" height="31">
https://pandia.ru/text/78/171/images/image079_7.gif" width="320" height="31 src=">
Обозначим через А, В, С события, фигурирующие в пунктах (а), (б), (в) соответственно и учитывая, что блоки работают независимо друг от друга, найдём:
Каналом обслуживания называется устройство в СМО, обслуживающее заявку. СМО, содержащее один канал обслуживания, называется одноканальной, а содержащее более одного канала обслуживания – многоканальной (например, 3 кассы на вокзале).
Если заявка, поступающая в СМО, может получить отказ в обслуживании (в силу занятости всех каналов обслуживания) и в случае отказа вынуждена покинуть СМО, то такая СМО называется СМО с отказами (примером такой СМО может служить АТС).
Если в случае отказа в обслуживании заявки могут вставать в очередь, то такие СМО называются СМО с очередью (или с ожиданием ). При этом различают СМО с ограниченной и неограниченной очередью. Примером первых СМО может служить мойка для автомашин с маленькой стоянкой для ожидающих машин, а примером вторых СМО может служить билетная касса или метрополитен.
Возможны также СМО смешанного типа, когда, например, заявка может вставать в очередь, если она не очень велика, и может находиться в очереди ограниченное время и уйти из СМО не обслуженной.
Различают СМО открытого и замкнутого типа. В СМО открытого типа поток заявок не зависит от СМО (билетные кассы, очередь в булочной). В СМО замкнутого типа обслуживается ограниченный круг клиентов, а число заявок может существенно зависеть от состояния СМО (например, бригада слесарей – наладчиков, обслуживающих станки на заводе).
СМО могут также различаться по дисциплине обслуживания : обслуживаются ли заявки в порядке поступления, случайным образом или вне очереди (с приоритетом).
СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.
n – число каналов в СМО ;
λ – интенсивность поступления в СМО заявок ;
μ – интенсивность обслуживания заявок ;
ρ = λ /μ – коэффициент загрузки СМО;
m – число мест в очереди ;
р отк - вероятность отказа в обслуживании поступившей в СМО заявки;
Q ≡ p обс - вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО); при этом
Q = p обс = 1 - р отк; (4.5)
А – среднее число заявок, обслуживаемых в СМО в единицу времени (абсолютная пропускная способность СМО)
А = λ∙Q ; (4.6)
L смо - среднее число заявок , находящихся в СМО;
https://pandia.ru/text/78/171/images/image083_7.gif" width="22" height="27 src="> определяется как математическое ожидание случайного числа занятых обслуживанием n каналов:
https://pandia.ru/text/78/171/images/image085_7.gif" width="95" height="27 src="> - коэффициент занятости каналов ;
t ож - среднее время ожидания (обслуживания) заявки в очереди,
v = 1/t ож - интенсивность потока ухода заявок из очереди.
L оч - среднее число заявок в очереди (если очередь есть); определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди
https://pandia.ru/text/78/171/images/image087_6.gif" width="87" height="31 src="> - среднее время пребывания заявки в СМО;
https://pandia.ru/text/78/171/images/image089_7.gif" width="229" height="48 src="> (4.9)
Здесь λ и μ – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S 0 обозначает, что канал свободен, а S 1 - что канал занят обслуживанием заявки.
Система дифференциальных уравнений Колмогорова для такой СМО имеет вид (см. пример 3)
https://pandia.ru/text/78/171/images/image093_7.gif" width="168" height="50 src="> , (5.1)
https://pandia.ru/text/78/171/images/image095_7.gif" width="197" height="51 src=">; 
.
Таким образом, обслуживается лишь 62,5% звонков, что нельзя считать удовлетворительным. Абсолютная пропускная способность СМО
А = λQ = λp обс = 1,2∙0,625(мин)-1 = 0,75(мин)-1,
т. е. в среднем обслуживается 0,75 звонка в минуту.
§ 6. Многоканальная СМО с отказами.
Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна λ , а интенсивность обслуживания заявки каждым каналом равна μ . Размеченный граф состояний системы изображён на рис. 5.
https://pandia.ru/text/78/171/images/image099_6.gif" width="106" height="29"> означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью λ независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина kμ характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).
Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, что многоканальная СМО с отказами является частным случаем системы рождения и гибели, если в последней принять g = n и
https://pandia.ru/text/78/171/images/image101_6.gif" width="234" height="51 src="> (6.2)
https://pandia.ru/text/78/171/images/image103_6.gif" width="84 height=29" height="29"> (6.3)
Формулы (6.2) и (6.3) называются формулами Эрланга – основателя теории массового обслуживания.
Вероятность отказа в обслуживании заявки р отк равна вероятности того, что все каналы заняты, т. е. система находится в состоянии S n. Таким образом,
https://pandia.ru/text/78/171/images/image105_6.gif" width="215" height="44"> (6.5)
Абсолютную пропускную способность найдём из (4.6) и (6.5):
https://pandia.ru/text/78/171/images/image107_6.gif" width="24" height="24 src="> можно найти по формуле:
https://pandia.ru/text/78/171/images/image108_6.gif" width="158" height="46 src="> (6.7)
Пример 7. Найти оптимальное число телефонных номеров на предприятии, если заявки на переговоры поступают с интенсивностью 1,2 заявки в минуту, а средняя продолжительность разговора по телефону составляет https://pandia.ru/text/78/171/images/image059_9.gif" width="12" height="23"> Оптимальное число каналов n неизвестно. Используя формулы (6.2) – (6.7) найдём характеристики СМО при различных значениях n и заполним таблицу 1.
Таблица 1
р отк | ||||||
р обс | ||||||
А [мин-1] |
Оптимальным числом телефонных номеров можно считать n = 6, когда выполняется 97,6% заявок. При этом за каждую минуту обслуживается в среднем 1,171 заявки. Для решения 2-го и 3-го пунктов задачи воспользуемся формулой (4.1). Имеем:
а) https://pandia.ru/text/78/171/images/image112_6.gif" width="513" height="61">
§7. Одноканальная СМО с ограниченной длиной очереди.
В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рис.6.
λ λ λ λ λ λ
μ μ μ μ μ μ
Рис.6
Состояния СМО представляются следующим образом:
S 0 - канал обслуживания свободен,
S 1 – канал обслуживания занят, но очереди нет,
S 2 – канал обслуживания занят, в очереди одна заявка,
S k+1 – канал обслуживания занят, в очереди k заявок,
S m+1 – канал обслуживания занят, все m мест в очереди заняты.
Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рис.6 является частным случаем системы рождения и гибели (рис.3), если в последней принять g = m + 1 и
λ i = λ , μ i = μ , (). (7.1)
Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (3.2) и (3.3) с учётом (7.1). В результате получим:
p k = ρk ∙p 0, (7.3)
При ρ = 1 формулы (7.2), (7.3) принимают вид
https://pandia.ru/text/78/171/images/image123_6.gif" width="88" height="25 src="> (7.4)
При m = 0 (очереди нет) формулы (7.2), (7.3) переходят в формулы (5.1) и (5.2) для одноканальной СМО с отказами.
Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии Sm +1, т. е. вероятность отказа в обслуживании заявки равна
p отк = р m +1 = ρm +1p 0. (7.5)
Относительная пропускная способность СМО равна
Q = p обс = 1 – р отк = ρm +1p 0, (7.6)
а абсолютная пропускная способность равна
https://pandia.ru/text/78/171/images/image124_6.gif" width="251" height="49 src="> (7.8)
При ρ = 1 формула (7.8) принимает вид
https://pandia.ru/text/78/171/images/image126_6.gif" width="265" height="53 src="> (7.10)
При ρ = 1, из (7.10) получим:
https://pandia.ru/text/78/171/images/image128_6.gif" width="223" height="47 src=">
р отк = ρ m+1 ∙ p 0 ≈ (1,5)6 ∙ 0,031 ≈ 0,354,
т. е. 35,4% покупателей получают отказ в обслуживании, что недопустимо много. Среднее число людей, стоящих в очереди, находим по формуле (7.8)
https://pandia.ru/text/78/171/images/image130_6.gif" width="212" height="45 src=">
т. е. не очень большое. Увеличение очереди до m = 10 даёт
p 0 ≈ 0,0039, p отк ≈ 0,0336,
т. е. не приводит к заметному уменьшению отказов в обслуживании. Вывод: необходимо посадить ещё одного кассира, либо уменьшить время обслуживания каждого покупателя.
§8. Одноканальная СМО с неограниченной очередью.
Примером такой СМО может служить директор предприятия, вынужденный рано или поздно решать вопросы, относящиеся к его компетенции, или, например, очередь в булочной с одним кассиром. Граф такой СМО изображён на рис. 7.
λ λ λ λ λ
μ μ μ μ μ
Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них m → ∞. При этом необходимо различать два существенно разных случая: а) ρ ≥ 1; б) ρ < 1. В первом случае, как это видно из формул (7.2), (7.3), p 0 = 0 и pk = 0 (при всех конечных значениях k ). Это означает, что при t → ∞ очередь неограниченно возрастает, т. е. этот случай практического интереса не представляет.
Рассмотрим случай, когда ρ < 1. Формулы (7.2) и (7.3) при этом запишутся в виде
р 0 = 1 - ρ , (8.1)
р k = ρk ∙ (1 – ρ ), k = 1, 2,… (8.2)
Поскольку в СМО отсутствует ограничение на длину очереди, то любая заявка может быть обслужена, т. е. относительная пропускная способность равна
Q = p обс =
Абсолютная пропускная способность равна
А = λ ∙ Q = λ . (8.4)
Среднее число заявок в очереди получим из формулы(7.8) при m → ∞
https://pandia.ru/text/78/171/images/image140_6.gif" width="105" height="29 src=">, (8.6)
а среднее число заявок, находящихся в СМО, равно
https://pandia.ru/text/78/171/images/image142_6.gif" width="187" height="48 src="> покупателя,
а среднее число покупателей, находящихся в СМО (т. е. у кассы), равно
https://pandia.ru/text/78/171/images/image144_6.gif" width="208" height="47 src=">
что вполне приемлемо.
§9. Многоканальная СМО с ограниченной очередью.
Пусть на вход СМО, имеющей n каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью λ . Интенсивность обслуживания заявки каждым каналом равна μ , а максимальное число мест в очереди равно m . Граф такой системы представлен на рис.8.
Очереди нет Очередь есть
λ λ λ λ λ λ
μ 2μ nμ nμ nμ nμ
S 0 - все каналы свободны, очереди нет;
S l - заняты l каналов https://pandia.ru/text/78/171/images/image147_6.gif" width="65" height="26">.
Сравнение графов на рисунках 3 и 8 показывает, что последняя система является частным случаем системы рождения и гибели, если в ней сделать следующие замены (левые обозначения относятся к системе рождения и гибели):
S 0 → S 0; Sg → Sn +m ; Sk → Sl , ; Sk → Sn +i , https://pandia.ru/text/78/171/images/image150_7.gif" width="377" height="56">. (9.1)
Выражения для финальных вероятностей легко найти из формул (3.2) и (3.3) с учётом (8.6). В результате получим:
https://pandia.ru/text/78/171/images/image152_6.gif" width="80" height="47 src=">, ; 
,. (9.3)
Образование очереди происходит, когда в момент поступления в СМО очередной заявки все n каналов заняты, т. е. когда в системе будет находиться либо n , либо n + 1,…, либо (n + m – 1)заявок. Так как эти события несовместимы, то вероятность образования очереди р оч равна сумме соответствующих вероятностей p n, p n+1,…, p n+m-1:
https://pandia.ru/text/78/171/images/image156_3.gif" width="166" height="48 src=">. (9.5)
Относительная пропускная способность равна
https://pandia.ru/text/78/171/images/image158_6.gif" width="231" height="43 src="> (9.7)
Среднее число заявок, находящихся в очереди, определяется по формуле (4.8) и может быть записано в виде
https://pandia.ru/text/78/171/images/image160_6.gif" width="192" height="51"> (9.9)
Среднее число заявок, находящихся в СМО, равно
L смо = L оч + L обс. (9.10)
Среднее время пребывания заявки в СМО и в очереди определяется формулами (4.9) и (4.10).
При ρ = n в формулах (9.2), (9.4), (9.8) возникает неопределённость типа 0/0. В этом случае, раскрывая неопределённость можно получить:
https://pandia.ru/text/78/171/images/image162_5.gif" width="149" height="44 src=">; 
, (9.12)
https://pandia.ru/text/78/171/images/image165_5.gif" width="195" height="49 src=">, (9.14)
https://pandia.ru/text/78/171/images/image167_5.gif" width="305" height="53 src=">
т. е. грузчики работают практически без отдыха.
По формуле (9.5) находим вероятность отказа в обслуживании прибывшей на склад машины:
Т. е. вероятность отказа не столь велика. Относительная пропускная способность равна
Q = p обс = 1 – р отк ≈ 1 – 0,145 = 0,855.
Среднее число машин в очереди находим по формуле (9.14).
