Постановка задачи. На вход n -канальной СМО поступает простейший поток заявок с плотностью λ. Плотность простейшего потока обслуживания каждого канала равна μ. Если поступившая на обслуживание заявка застает все каналы свободными, то она принимается на обслуживание и обслуживается одновременно l каналами (l < n ). При этом поток обслуживаний одной заявки будет иметь интенсивность l .

Если поступившая на обслуживание заявка застает в системе одну заявку, то при n ≥ 2l вновь прибывшая заявка будет принята к обслуживанию и будет обслуживаться одновременно l каналами.

Если поступившая на обслуживание заявка застает в системе i заявок (i = 0,1, ...), при этом (i + 1)l ≤ n , то поступившая заявка будет обслуживаться l каналами с общей производительностью l . Если вновь поступившая заявка застает в системе j заявок и при этом выполняются совместно два неравенства: (j + 1)l > n и j < n , то заявка будет принята на обслуживание. В этом случае часть заявок может обслуживаться l каналами, другая часть меньшим, чем l , числом каналов, но в обслуживании будут заняты все n каналов, которые распределены между заявками произвольным образом. Если вновь поступившая заявка застанет в системе n заявок, то она получает отказ и не будут обслуживаться. Попавшая на обслуживание заявка обслуживается до конца (заявки «терпеливые»).

Граф состояний такой системы показан на рис. 3.8.

Рис. 3.8. Граф состояний СМО с отказами и частичной

взаимопомощью между каналами

Заметим, что граф состояний системы до состояния x h с точностью до обозначений параметров потоков совпадает с графом состояний классической системы массового обслуживания с отказами, изображенным на рис. 3.6.

Следовательно,

(i = 0, 1, ..., h ).

Граф состояний системы, начиная от состояния x h и кончая состоянием x n , совпадает с точностью до обозначений с графом состояний СМО с полной взаимопомощью, изображенным на рис. 3.7. Таким образом,

.

Введем обозначения λ / l μ = ρ l ; λ / n μ = χ, тогда

С учетом нормированного условия получаем

Для сокращения дальнейшей записи введем обозначение

Найдем характеристики системы.

Вероятность обслуживания заявки

Среднее число заявок, находящихся в системе,

Среднее число занятых каналов

.

Вероятность того, что отдельный канал будет занят

.

Вероятность занятости всех каналов системы

3.4.4. Системы массового обслуживания с отказами и неоднородными потоками

Постановка задачи. На вход n -канальной СМО поступает неоднородный простейший поток с суммарной интенсивностью λ Σ , причем

λ Σ = ,

где λ i – интенсивность заявок в i -м источнике.

Так как поток заявок рассматривается как суперпозиция требований от различных источников, то объединенный поток с достаточной для практики точностью можно считать пуассоновским для N = 5...20 и λ i ≈ λ i +1 (i 1,N ). Интенсивность обслуживания одного прибора распределена по экспоненциальному закону и равна μ = 1/t . Обслуживающие приборы для обслуживания заявки соединяются последовательно, что равносильно увеличению времени обслуживания во столько раз, сколько приборов объединяется для обслуживания:

t обс = kt , μ обс = 1 / kt = μ/k ,

где t обс – время обслуживания заявки; k – число обслуживающих приборов; μ обс – интенсивность обслуживания заявки.

В рамках принятых в главе 2 допущений состояние СМО представим в виде вектора , гдеk m – число заявок в системе, каждая из которых обслуживается m приборами; L = q max – q min +1 – число входных потоков.

Тогда количество занятых и свободных приборов (n зан (),n св ()) в состоянииопределяется следующим образом:

Из состояния система может перейти в любое другое состояние. Так как в системе действуетL входных потоков, то из каждого состояния потенциально возможно L прямых переходов. Однако из-за ограниченности ресурсов системы не все эти переходы осуществимы. Пусть СМО находится в состоянии и приходит заявка, требующаяm приборов. Если m ≤ n св (), то заявка принимается на обслуживание и система переходит в состояниес интенсивностью λ m . Если же заявка требует приборов больше, чем имеется свободных, то она получит отказ в обслуживании, а СМО останется в состоянии . Если в состояниинаходятся заявки, требующиеm приборов, то каждая из них обслуживается с интенсивностью m , а общая интенсивность обслуживания таких заявок (μ m ) определяется как μ m = k m μ / m . При завершении обслуживания одной из заявок система перейдет в состояние, в котором соответствующая координата имеет значение, на единицу меньшее, чем в состоянии ,=, т.е. произойдет обратный переход. На рис. 3.9 представлен пример векторной модели СМО дляn = 3, L = 3, q min = 1, q max = 3, P (m ) = 1/3, λ Σ = λ, интенсивность обслуживания прибора – μ.

Рис. 3.9. Пример графа векторной модели СМО с отказами в обслуживании

Итак, каждое состояниехарактеризуется числом обслуживаемых заявок определенного типа. Например, в состоянии
обслуживается одна заявка одним прибором и одна заявка двумя приборами. В этом состоянии все приборы заняты, следовательно, возможны лишь обратные переходы (приход любой заявки в этом состоянии приводит к отказу в обслуживании). Если раньше закончилось обслуживание заявки первого типа, то система перейдет в состояние(0,1,0) с интенсивностью μ, если же раньше закончилось обслуживание заявки второго типа, то система перейдет в состояние(0,1,0) с интенсивностью μ/2.

По графу состояний с нанесенными интенсивностями переходов составляется система линейных алгебраических уравнений. Из решения этих уравнений находятся вероятности Р (), по которым определяется характеристика СМО.

Рассмотрим нахождение Р отк (вероятность отказа в обслуживании).

,

где S – число состояний графа векторной модели СМО; Р () – вероятность нахождения системы в состоянии.

Число состояний согласно определяется следующим образом:

, (3.22)

;

Определим число состояний векторной модели СМО по (3.22) для примера, представленного на рис. 3.9.

.

Следовательно, S = 1 + 5 + 1 = 7.

Для реализации реальных требований к обслуживающим приборам необходимо достаточно большое число n (40, ..., 50), а запросы на число обслуживающих приборов заявки на практике лежат в пределах 8–16. При таком соотношении приборов и запросов предложенный путь нахождения вероятностей становится чрезвычайно громоздким, т.к. векторная модель СМО имеет большое число состояний S (50) = 1790, S (60) = 4676, S (70) = = 11075, а размер матрицы коэффициентов системы алгебраических уравнений пропорционален квадрату S , что требует большого объема памяти ЭВМ и значительных затрат машинного времени. Стремление снизить объем вычислений стимулировало поиск рекуррентных возможностей расчета Р () на основе мультипликативных форм представления вероятностей состояний. В работе представлен подход к расчетуР ():

(3.23)

Использование предложенного в работе критерия эквивалентности глобального и детального балансов цепей Маркова позволяет снижать размерность задачи и выполнять вычисления на ЭВМ средней мощности, используя рекуррентность вычислений. Кроме того, имеется возможность:

– произвести расчет для любых значений n ;

– ускорить расчет и снизить затраты машинного времени.

Аналогичным образом могут быть определены и другие характеристики системы.

Рассмотрим многоканальную систему массового обслуживания (всего каналов 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 через абсолютную пропускную способность СМО, т.е. А. Величина А – среднее число заявок, которые обслуживаются системой в единицу времени. Один занятый канал обслуживает за единицу времени μ заявок, тогда среднее число занятых каналов

Информатика, кибернетика и программирование

На систему обслуживания имеющую n каналов обслуживания поступает пуассоновский поток заявок с интенсивностью λ. Интенсивность обслуживания заявки каждым каналом. После окончания обслуживания все каналы освобождаются. Поведение такой системы массового обслуживания можно описать Марковским случайным процессом t представляющим собой число заявок находящихся в системе.

2. СМО с отказами и полной взаимопомощью для массовых потоков. Граф, система уравнений, расчетные соотношения.

Постановка задачи. На систему обслуживания, имеющую n каналов обслуживания, поступает пуассоновский поток заявок с интенсивностью λ. Интенсивность обслуживания заявки каждым каналом - µ. Заявка обслуживается всеми каналами одновременно. После окончания обслуживания все каналы освобождаются. Если вновь прибывшая заявка застает заявку, она тоже принимается к обслуживанию. Часть каналов продолжают обслуживать первую заявку, а остальные - новую. Если в системе уже обслуживается n заявок, то вновь прибывшая заявка получает отказ. Поведение такой системы массового обслуживания можно описать Марковским случайным процессом ξ(t), представляющим собой число заявок, находящихся в системе.

Возможные состояния этого процесса E = (0, 1, . . . , n). Найдем характеристики рассматриваемой СМО в стационарном режиме.

Граф, соответствующий рассматриваемому процессу, представлен на рисунке 1.

Рис. 1. СМО с отказами и полной взаимопомощью для пуассоновских потоков

Составим систему алгебраических уравнений:

Решение данной системы имеет вид:

Здесь χ =λ/nµ - среднее число заявок, поступающих в систему за среднее время обслуживания одной заявки всеми каналами.

Характеристики многоканальной системы массового обслуживания с отказами и полной взаимопомощью между каналами.

1. Вероятность отказа в обслуживании (вероятность того, что все каналы заняты):

2. Вероятность обслуживания заявки (относительная пропускная способность системы):

Система уравнений

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

СМО представим в виде вектора , где k m – число заявок в системе, каждая из которых обслуживается m приборами; L = q max – q min +1 – число входных потоков.

Если заявка принимается на обслуживание и система переходит в состояние с интенсивностью λ m .

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

Пример векторной модели СМО для n = 3, L = 3, q min = 1, q max = 3, P (m ) = 1/3, λ Σ = λ, интенсивность обслуживания прибора – μ.

По графу состояний с нанесенными интенсивностями переходов составляется система линейных алгебраических уравнений. Из решения этих уравнений находятся вероятности Р (), по которым определяется характеристики СМО.

СМО с бесконечной очередью для пуассоновских потоков. Граф, система уравнений, расчетные соотношения.

Граф системы

Где n – число каналов обслуживания, l – число взаимопомогающих каналов

СМО с бесконечной очередью и частичной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения.

Граф системы

Система уравнений

–λ Р 0 + n μР 1 =0,

.………………

–(λ + n μ)Р k + λР k –1 + n μР k +1 =0 (k = 1,2, ... , n –1),

……………....

-(λ+ n μ)P n + λР n –1 + n μ Р n+1 =0,

……………….

-(λ+ n μ)P n+j + λР n+j –1 + n μ Р n+j+1 =0, j=(1,2,….,∞)

СМО с бесконечной очередью и полной взаимопомощью для произвольных потоков. Граф, система уравнений, расчетные соотношения.

Граф системы