Рассмотрим многоканальную систему массового обслуживания (всего каналов n), в которую поступают заявки с интенсивностью λ и обслуживаются с интенсивностью μ. Заявка, прибывшая в систему, обслуживается, если хотя бы один канал свободен. Если все каналы заняты, то очередная заявка, поступившая в систему, получает отказ и покидает СМО. Пронумеруем состояния системы по числу занятых каналов:
- S 0 – все каналы свободны;
- S 1 – занят один канал;
- S 2 – занято два канала;
- S k – занято k каналов;
- S n – все каналы заняты.
Рис. 7.24
На рисунке 6.24 изображен граф состояний, в котором S
i
– номер канала; λ – интенсивность поступления заявок; μ
– соответственно интенсивность обслуживания заявок. Заявки поступают в систему массового обслуживания с постоянной интенсивностью и постепенно занимают один за другим каналы; когда все каналы будут заняты, то очередная заявка, прибывшая в СМО, получит отказ и покинет систему.
Определим интенсивности потоков событий, которые переводят систему из состояния в состояние при движении как слева направо, так и справа налево по графу состояний.
Например, пусть система находится в состоянии S
1 , т. е. один канал занят, поскольку на его входе стоит заявка. Как только обслуживание заявки закончится, система перейдет в состояние S
0 .
Например, если заняты два канала, то поток обслуживания, переводящий систему из состояния S
2 в состояние S
1 будет вдвое интенсивнее: 2-μ; соответственно, если занято k
каналов, интенсивность равна k-μ.
Процесс обслуживания является процессом гибели и размножения. Уравнения Колмогорова для этого частного случая будут иметь следующий вид:
(7.25)
Уравнения (7.25) называются уравнениями Эрланга
.
Для того, чтобы найти значения вероятностей состояний Р
0 , Р
1 , …, Р
n
, необходимо определить начальные условия:
– Р
0 (0) = 1, т. е. на входе системы стоит заявка;
– Р
1 (0) = Р
2 (0) = … = Р
n
(0) = 0, т. е. в начальный момент времени система свободна.
Проинтегрировав систему дифференциальных уравнений (7.25), получим значения вероятностей состояний Р
0 (t
), Р
1 (t
), … Р
n
(t
).
Но гораздо больше нас интересуют предельные вероятности состояний. При t → ∞ и по формуле, полученной при рассмотрении процесса гибели и размножения, получим решение системы уравнений (7.25):
(7.26)
В этих формулах отношение интенсивности λ / μ
к потоку заявок удобно обозначить ρ
.Эту величину называют приведенной интенсивностью потока заявок,
то есть среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.
С учетом сделанных обозначений система уравнений (7.26) примет следующий вид:
(7.27)
Эти формулы для вычисления предельных вероятностей называются формулами Эрланга
.
Зная все вероятности состояний СМО, найдем характеристики эффективности СМО, т. е. абсолютную пропускную способность А
, относительную пропускную способность Q
и вероятность отказа Р
отк.
Заявка, поступившая в систему, получит отказ, если она застанет все каналы занятыми:
.
Вероятность того, что заявка будет принята к обслуживанию:
Q
= 1 – Р
отк,
где Q
– средняя доля поступивших заявок, обслуживаемых системой, или среднее число заявок обслуженных СМО в единицу времени, отнесенное к среднему числу поступивших за это время заявок:
A=λ·Q=λ·(1-P отк)
Кроме того, одной из важнейших характеристик СМО с отказами является среднее число занятых каналов
. В n
-канальной СМО с отказами это число совпадает со средним числом заявок, находящихся в СМО.
Среднее число заявок k
можно вычислить непосредственно через вероятности состояний Р 0 , Р 1 , … , Р n:
,
т. е. находим математическое ожидание дискретной случайной величины, которая принимает значение от 0 до n
с вероятностями Р
0 , Р
1 , …, Р
n
.
Еще проще выразить величину k
через абсолютную пропускную способность СМО, т.е. А. Величина А – среднее число заявок, которые обслуживаются системой в единицу времени. Один занятый канал обслуживает за единицу времени μ заявок, тогда среднее число занятых каналов
Для СМО с отказами :
Для СМО с неограниченным ожиданием как абсолютная, так и относительная пропускная способности теряют смысл, так как каждая поступившая заявка рано или поздно будет обслужена. Для такой СМО важными показателями являются:
Для СМО смешанного типа используются обе группы показателей: как относительная и абсолютная пропускная способности , так и характеристики ожидания.
В зависимости от цели операции массового обслуживания любой из приведенных показателей (или совокупность показателей) может быть выбран в качестве критерия эффективности.
Аналитической моделью СМО является совокупность уравнений или формул, позволяющих определять вероятности состояний системы в процессе ее функционирования и рассчитывать показатели эффективности по известным характеристикам входящего потока и каналов обслуживания.
Всеобщей аналитической модели для произвольной СМО не существует . Аналитические модели разработаны для ограниченного числа частных случаев СМО. Аналитические модели, более или менее точно отображающие реальные системы, как правило, сложны и труднообозримы.
Аналитическое моделирование СМО существенно облегчается, если процессы, протекающие в СМО, марковские (потоки заявок простейшие, времена обслуживания распределены экспоненциально). В этом случае все процессы в СМО можно описать обыкновенными дифференциальными уравнениями, а в предельном случае, для стационарных состояний - линейными алгебраическими уравнениями и, решив их, определить выбранные показатели эффективности.
Рассмотрим примеры некоторых СМО.
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 прогонов практически совпадают: .
СМО с отказами (задача Эрланга)
Рассматривается N-канальная СМО с отказами:
λобслуживания
Любая заявка может быть обслужена любым свободным каналом. Если все каналы заняты, заявка немедленно получает отказ в обслуживании и покидает систему (теряется). Интенсивности входных и выходных потоков:
Считаем, что в этой системе имеются следующие потоки событий:
1) поступление заявок на вход СМО из источника заявок G;
2) обслуживание заявок в каналах.
1) интенсивность потока поступающих заявок характеризуется λ
2) интенсивность обслуживания одним каналом:
![](https://i0.wp.com/mirznanii.com/images/96/02/9400296.gif)
Т.о. входной поток с интенсивностью λ и поток обслуживания с интенсивностью µ распределены по экспоненциальному закону и следовательно данные потоки являются простейшими, а сами процессы в системе Марковскими. Представим граф схему переходов для этого случая:
Состояния СМО в данном случае нумеруются по числу заявок, находящихся в СМО (в силу отсутствия очереди состояния, в котором находится система, совпадает с числом занятых каналов)
S0 - все каналы свободны, система свободна
S1 - занят один канал
Sk - заняты k каналов, остальные (n-k) свободны
Sn - заняты все n каналов
![](https://i2.wp.com/mirznanii.com/images/98/02/9400298.gif)
Из состояния Si-1 всегда с интенсивностью входного потока λ система переходит в следующее состояние Si, т.е. в данном случае будет заняе еще один канал и интенсивность перехода в следующее состояние равно интенсивности входного потока λ. Интенсивность обратного перехода возрастает с ростом числа параллельно работающих каналов. Чем больше их работает, тем интенсивнее процесс их освобождения. Для простейших потоков имеем:
Данная схема называется схемой гибели и размножения. Такое название происходит от того, что связаны соседние состояния. Математический аппарат - это Марковский процесс, с дискретными состояниями и непрерывным временем. Для заданной СМО матрица интенсивностей Λ имеет вид:
![](https://i2.wp.com/mirznanii.com/images/00/03/9400300.gif)
Пользуясь матрицей Λ запишем уравнения, которые позволяют рассчитать вероятности пребывания системы в каждом из указанных состояний. Распределение вероятностей P0,P1,…,Pn по состояниям S0,…,Sn определяется как решение системы дифференциальных уравнений.
Рассмотрим -канальную СМО с отказами. Будем нумеровать состояния системы по числу занятых каналов (или, что в данном случае то же, по числу заявок, связанных с системой). Состояния будут:
Все каналы свободны,
Занят ровно один канал, остальные свободны,
Заняты ровно k каналов, остальные свободны,
Заняты все каналов.
Граф состояний СМО представлен на рис. 5.3. Разметим граф, т. е. проставим у стрелок интенсивности соответствующих потоков событий.
По стрелкам слева направо систему переводит один и тот же поток - ноток заявок с интенсивностью к. Если система находится в состоянии (занято k каналов) и пришла новая заявка, система переходит (перескакивает) в состояние
Определим интенсивности потоков событий, переводящих систему по стрелкам справа налево.
Пусть система находится в состоянии 5, (занят один канал). Тогда, как только закончится обслуживание заявки, занимающей этот канал, система перейдет в значит, поток событий, переводящий систему по стрелке имеет интенсивность Очевидно, если обслуживанием занято два канала, а не один, поток обслуживание переводящий систему но стрелке будет вдвое интенсивнее если занято k каналов в k раз интенсивнее Проставим соответствующие интенсивности у стрелок, ведущих справа налево.
Из рис. 5.3 видно, что процесс, протекающий в СМО, представляет собой частный случай процесса гибели и размножения, рассмотренного нами в § 8 гл. 4.
Пользуясь общими правилами, можно составить уравнения Колмогорова для вероятностей состояний:
Уравнения (4.1) называются уравнениями Эрланга. Естественными начальными условиями для их решения являются:
(в начальный момент система свободна).
Интегрирование системы уравнений (4.1) в аналитическом виде довольно сложно; на практике такие системы дифференциальных уравнений обычно решаются численно, на АВМ или ЭЦВМ. Такое решение дает нам все вероятности состояний
как функции времени.
Естественно, нас больше всего будут интересовать предел -ные вероятности состояний характеризующие установившийся режим работы СМО (при ). Для нахождения предельных вероятностей воспользуемся уже готовым решением задачи, полученным для схемы гибели и размножения в § 8 гл. 4. Согласно этому решению,
В этих формулах интенсивность потока заявок и интенсивность потока обслуживаний (для одного канала) не фигурируют по отдельности, а входят только своим отношением Обозначим это отношение
и будем называть величину р «приведенной интенсивностью» потока заявок. Физический смысл ее таков: величина представляет собой среднее число заявок, приходящих в СМО за среднее время обслуживания одной заявки.
С учетом этого обозначения, формулы (4.2) примут вид:
Формулы (4.3) называются формулами Эрланга. Они выражают предельные вероятности всех состояний системы в зависимости от параметров ( - интенсивность потока чаявок, - интенсивность обслуживания, п - число каналов СМО).
Зная все вероятности состояний
можно найти характеристики эффективности СМО: относительную пропускную способность q, абсолютную пропускную способность А и вероятность отказа .
Действительно, заявка получает отказ, если приходит в момент, когда все каналов заняты. Вероятность этого равна
Вероятность того, что заявка будет принята к обслуживанию (она же относительная пропускная способность q) дополняет Яотк до единицы:
Абсолютная пропускная способность:
Одной из важных характеристик СМО с отказами является среднее число занятых каналов (в данном случае оно совпадает со средним числом заявок, находящихся в системе). Обозначим это среднее число
Величину k можно вычислить непосредственно через вероятности по формуле:
как математическое ожидание дискретной случайной величины, принимающей значения с вероятностями Однако значительно проще выразить среднее число занятых каналов через абсолютную пропускную способность А, которую мы уже знаем. Действительно, А есть не что иное, как среднее число заявок, обслуживаемых в единицу времени-, один занятый канал обслуживает в среднем за единицу времени заявок; среднее число занятых каналов получится делением А на