Многоканальная СМО с очередью

Пусть на вход многоканальной СМО (n - число каналов, m - число мест в очереди) поступает экспоненциальный поток заявок. Длительность обслуживания заявки в каждом канале СМО - случайная величина, также распределенная по экспоненциальному закону. Интенсивность потока заявок одинакова для каждого канала и равна λ (1/сек), среднее время обслуживания заявки - t_обсл. Обратная величина к среднему времени обслуживания определяет интенсивность потока обслуживания μ = 1/ t_обсл, характеризующее среднее число заявок, которое может обслужить система в единицу времени.

При наличии свободного канала приходящая заявка сразу отправляется на обслуживание. Если все каналы заняты, то заявка ставится в очередь. Если очередь заполнена, то заявка получает отказ. При освобождении канала и наличии заявок в очереди в освободившийся канал сразу помещается первая заявка из очереди. Обслуженные заявки покидают систему.

Определим состояния S_i для многоканальной СМО.

S₀ - система свободна, заявок нет, очереди нет;

S₁ - система обслуживает заявку в одном канале, очереди нет;

S₂ - система обслуживает заявки в двух каналах, очереди нет;

…………………………………………

S_n - система обслуживает заявки в n каналах, очереди нет;

S_n+1 -система обслуживает заявки в n каналах, одна заявка в очереди;

…………………………………………

S_n+m - система обслуживает заявки в n каналах, в очереди находятся m заявок.

Длина очереди m может быть неограниченной.

λ λ λ λ λ

S₀ S₁ S₂ S₃ S₄

μ 2μ 3μ 4μ 4μ

Рис. 4. Граф состояний четырехканальной СМО с очередью

Граф состояний многоканальной СМО подобен графу СМО (рис. 3.3) и отличается только интенсивностями потока обслуживания (нижние стрелки на графе). При поступлении очередной заявки (если есть свободные каналы) система переходит в соседнее правое состояние. Интенсивность перехода вправо определяется интенсивностью входного потока λ. По-другому обстоит дело с потоком обслуживания. Если система находится в состоянии S₁, то работает один канал и интенсивность обслуживания равна μ. В состоянии S₂ параллельно работают 2 канала и поэтому интенсивность обслуживания равна 2μ. Рост интенсивности обслуживания прекращается после того, как все каналы оказываются занятыми. Для системы с n каналами максимальное значение интенсивности обслуживания равно nμ.

Запишем уравнения Колмогорова для стационарного режима работы 4-х канальной СМО.

В этом примере видно, что в первых 4-х уравнениях, связанных с процессом заполнения каналов обслуживания, прослеживается одна закономерность, а в остальных уравнениях - другая.

Выражая последовательно вероятности p1, p2, … , pn+m через p0, получим решение алгебраической системы уравнений Колмогорова

для k < n,

для k > n,

Вероятность p₀ находится из последнего уравнения после подстановки в него предыдущих формул

На следующем шаге находим вероятности p₁, p₂, … p _n+m.

Проведем на основе этих выражений анализ основных вариантов функционирования многоканальной СМО.

Система без очереди (с отказами) (m = 0).

Вероятность отказа. Очередная заявка, поступающая в СМО, не обслуживается, если все каналы обслуживания заняты. Это значит, что система находится в состоянии S_n. Вероятность нахождения системы в этом состоянии p_n является вероятностью "отказа" в обслуживании.

Вероятность p₀ соответствует состоянию S₀, означающему, что в СМО нет заявок. Это коэффициент простоя p₀.

Величина (1 - p₀) характеризует факт, что СМО занята обслуживанием заявок. Это коэффициент загрузки p_заг = 1 - p₀.

Пропускная способность A. Это количество обслуженных заявок, покидающих систему в единицу времени. Пропускная способность равна количеству входящих заявок в единицу времени, умноженное на вероятность того, что заявка будет обслужена

Среднее число заявок n_ср, находящихся в СМО. В текущий момент времени в системе может быть 0, 1, 2, …, n заявок, при этом все заявки обслуживаются. Вероятность того, что в системе находится k заявок, равна p_k. Среднее число заявок n_ср равно математическому ожиданию дискретной случайной величины со следующей функцией распределения вероятностей

Значение с.в.				…	n
Вероятность pk	p0	p1	p2	…	pn

Среднее число обслуживаемых заявок n_оз - математическое ожидание дискретной случайной величины "количество занятых каналов" со следующей функцией распределения вероятности

Значение с.в.				…	n
Вероятность pk	p0	p1	p2	…	pn

В рассматриваемом случае в СМО очереди нет, nср = nоз. Средняя длина очереди равна нулю.

Система работоспособна, если

Система с ограниченной очередью ( m ≠ 0.).

Вероятность отказа. Очередная заявка, поступающая в СМО, не обслуживается, если все каналы обслуживания и все места в очереди заняты. Это значит, что система находится в состоянии S_n+m. Вероятность нахождения системы в этом состоянии p_n+m является вероятностью "отказа" в обслуживании.

Вероятность p₀ соответствует состоянию S₀, означающему, что в СМО нет заявок. Это коэффициент простоя p₀.

Величина (1 - p₀) характеризует факт, что СМО занята обслуживанием заявок. Это коэффициент загрузки p_заг = 1 - p₀.

Пропускная способность A. Это количество обслуженных заявок, покидающих систему в единицу времени. Пропускная способность равна количеству входящих заявок в единицу времени, умноженное на вероятность того, что заявка будет обслужена.

Среднее число заявок, находящихся в СМО. В текущий момент времени в системе может быть 0, 1, 2, …, n + m заявок, при этом заявки 1, … n могут обслуживаться, а n + 1, … n + m могут находиться в очереди. Вероятность того, что в системе находится k заявок, равна p_k. Среднее число заявок n_ср равно математическому ожиданию дискретной случайной величины со следующей функцией распределения вероятности

Значение с.в.				…	n + m
Вероятность pk	p0	p1	p2	…	pn+m

Среднее число обслуживаемых заявок n_оз - математическое ожидание дискретной случайной величины "количество занятых каналов" со следующей функцией распределения вероятности (в состояниях S_n, … S_n+m обслуживается n заявок)

Значение с.в.			…	n	…	n
Вероятность pk	p0	p1	…	pn	…	pn+m

Средняя длина очереди r_оч. - математическое ожидание дискретной случайной величины со следующей функцией распределения (в первых состояниях S₀, … S_n очереди нет)

Значение с.в.			…	m
Вероятность pk	pn+1	pn+2	…	pn+m

Средняя длина очереди резко возрастает при стремлении коэффициента загрузки p_заг к единице.

Для p_заг больше единицы работа СМО в стационарном режиме невозможна.

Система с бесконечной очередью ( m = ∞ ).

Вероятность отказа. В бесконечной очереди могут разместиться все пришедшие заявки. Поэтому вероятность отказа равна нулю.

Вероятность p₀ соответствует состоянию S₀, означающему, что в СМО нет заявок. Это коэффициент простоя p₀.

Величина p₀ находится из последнего уравнения системы уравнений Колмогорова, в которое входит сумма бесконечного числа слагаемых

В этом уравнении конечное число первых членов суммы со степенями 1,… n соответствуют n каналам обслуживания СМО. Остальные члены со степенями n + 1, …n + m, … соответствуют очереди и образуют убывающую геометрическую прогрессию со знаменателем и первым членом

Подставим в предыдущую формулу выражение для суммы членов геометрической прогрессии и получим формулу для вычисления p₀.

Эта формула позволяет найти вероятность p₀. Затем находятся остальные вероятности p₁, p₂, … p_n+m, … по формулам, приведенным выше. В системе с бесконечной очередью бесконечное число состояний S_i и соответственно бесконечная последовательность вероятностей { p_i }. Последовательность вероятностей { p_i } для состояний, соответствующих очереди, монотонно убывает. Поэтому продолжаем вычисление этих вероятностей до тех пор, пока соответствующее значение p_N окажется меньше ε, где ε - принятая погрешность.

Величина (1 - p₀) характеризует факт, что СМО занята обслуживанием заявок. Это коэффициент загрузки p_заг = 1 - p₀.

Пропускная способность A. Это количество обслуженных заявок, покидающих систему в единицу времени. В системе с бесконечной очередью все поступившие заявки будут обслужены. Поэтому

Среднее число обслуживаемых заявок n_оз - математическое ожидание дискретной случайной величины "количество занятых каналов" со следующей функцией распределения вероятности (в состояниях Sn, … Sn+m обслуживается n заявок)

Значение с.в.			…	n	n	…	n	…
Вероятность pk	p0	p1	…	pn	pn+1	…	pn+m	…

В этой формуле в скобках записана бесконечно убывающая геометрическая прогрессия с первым членом a₁

и знаменателем

В результате получим формулу для вычисления среднего числа обслуживаемых заявок в СМО.

Средняя длина очереди r_оч. - математическое ожидание дискретной случайной величины со следующей функцией распределения (в первых состояниях S₀, … S_n очереди нет)

Значение с.в.			…	m	…
Вероятность pk	pn+1	pn+2	…	pn+m	…

Очередь в рассматриваемом случае бесконечна, однако, средняя длина очереди - конечное число.

Для вычисления r_оч преобразуем бесконечный ряд следующим образом

Разобьем этот ряд на два. Сумму положительных членов обозначим S₁, а сумму отрицательных - S₂,

Вычислим сумму первого ряда S₁. Подставим в ряд формулы для p_k, получим

где

Ряд S₁(x) сходится равномерно и поэтому его сумма является непрерывной функцией от x. Этот ряд можно почленно интегрировать и дифференцировать. Вычислим интеграл от суммы ряда

В этой функцией в скобках стоят члены геометрической прогрессией с первым членом и знаменателем

Запишем сумму этого ряда

Продифференцируем эту формулу по х и получим сумму ряда S₁(x).

Второй ряд S₂(x) - геометрическая прогрессия с первым членом и знаменателем

Сумма ряда S₂ равна

Объединяя формулы для S₁ и S₂, получим

Суммируя среднее число обслуживаемых заявок и среднее число заявок в очереди, получим среднее число заявок, находящихся в СМО n_ср.

Среднее время пребывания заявки в СМО. В стационарном режиме работы СМО ( p_заг <1 ) интенсивности входного и выходного потоков равны между собой и равны λ. Пусть в стационарном режиме среднее число заявок в системе в единицу времени равно n_ср. Тогда согласно теореме Литтла среднее время пребывания заявки в СМО - T_сист равно

Аналогично можно записать формулу для среднего времени пребывания заявки в очереди T_оч. В общем случае

Эти формулы позволяют определить среднее время обслуживания заявки СМО - t_обсл из следующего соотношения

В заключение отметим, что простые аналитические решения получены только для простейших систем массового обслуживания с входными потоками заявок экспоненциального или Пуассоновского типов. Поэтому эти результаты необходимо рассматривать как приближенные и оценочные. В аналитических моделях не удается учесть приоритеты заявок, реальные законы распределений, процессы обработки заявок в системе и многое другое. Поэтому в настоящее время основным методом анализа СМО является имитационное моделирование, позволяющее в численном виде получить характеристики системы, близкие к реальным.