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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СМО представим в виде вектора , где 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,….,∞)

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

Граф системы

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

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

Граф системы

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

Расчетные соотношения:

,

Постановка задачи. На вход 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 ;

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

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

До сих пор мы рассматривали только такие СМО, в которых каждая заявка может обслуживаться только одним каналом; незанятый каналы не могут «помогать» занятому в обслуживании.

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

При рассмотрении СМО со взаимопомощью между каналами необходимо учитывать два фактора:

1. Насколько убыстряется обслуживание заявки, когда над ним работает не один, а сразу несколько каналов?

2. Какова «дисциплина взаимопомощи», т. е. когда и как несколько каналов берут на себя обслуживание одной и той же заявки?

Рассмотрим сначала первый вопрос. Естественно предположить, что если над обслуживанием заявки работает не один канал, а несколько каналов, интенсивность потока обслуживаний не будет убывать с увеличением k, т. е. будет представлять собой некоторую неубывающую функцию числа k работающих каналов. Обозначим эту функцию Возможный вид функции показан на рис. 5.11.

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

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

Самым простым для исследования будет случай, когда функция возрастает пропорционально k при а при остается постоянной и равной (см. рис. 5.12). Если при этом общее число каналов , которые могут помогать друг другу, не превосходит

Остановимся теперь на втором вопросе: дисциплине взаимопомощи. Самый простой случай этой дисциплины мы обозначим условно «все как один». Это означает, что при появлении одной заявки ее начинают обслуживать все каналов сразу и остаются занятыми, пока не закончится обслуживание этой заявки; затем все каналы переключаются на обслуживание другой заявки (если она есть) или ждут ее появления, если ее нет, и т. д. Очевидно, в этом случае все каналов работают как один, СМО становится одноканальной, но с более высокой интенсивностью обслуживания.

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

Пример 1. Имеется трехканальная СМО с отказами: интенсивность потока заявок (заявки в минуту), среднее время обслуживания одноц заявки одним каналом (мин), функция Спрашивается, выгодно ли с точки зрения пропускной способности СМО вводить взаимопомощь между каналами по типу «все как один»? Выгодно ли это с точки зрения уменьшения среднего времени пребывания заявки в системе?

Решение, а. Без взаимопомощи,

По формулам Эрланга (см. § 4) имеем:

Относительная пропускная способность СМО;

Абсолютная пропускная способность:

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

Гсист (мин).

Не нужно забывать, что это среднее время относится ко всем заявкам - как обслуженным, так и необслуженным Нас же может интересовать среднее время, которое пробудет в системе обслуженная заявка. Это время равно:

6. Со взаимопомощью.

Среднее время пребывания заявки в СМО:

Среднее время пребывания обслуженной заявки в СМО:

Таким образом, при наличии взаимопомощи «все как один» пропускная способность СМО заметно уменьшилась. Это объясняется увеличением вероятности отказа: за то время, пока все каналы заняты обслуживанием одной заявки, могут прийти другие заявки, и, естественно, получить отказ. Что касается среднего времени пребывания заявки в СМО, то оно, как и следовало ожидать, уменьшилось. Если, по каким-то соображениям, мы стремимся ко всемерному уменьшению времени, которое заявка проводит в СМО (например, если пребывание в СМО опасно для заявки), может оказаться, что, несмотря на уменьшение пропускной способности, все же будет выгодно объединить три канала в один.

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

В силу формул (6.13), (6.14) § 6 для обслуживания без взаимопомощи среднее число заявок в очереди будет

среднее время ожидания:

а среднее время пребывания в системе:

Если же применяется взаимопомощь типа «все как один», то система будет работать как одноканальная с параметрами

и ее характеристики определятся формулами (5.14), (5.15) § 5:

Пример 2. Имеется трехканальная СМО с неограниченной очередью; интенсивность потока заявок (заявки в мин.), среднее время обслуживания Функция Выгодно имея в виду:

Среднюю длину очереди,

Среднее время ожидания обслуживания,

Среднее время пребывания заявки в СМО

вводить взаимопомощь между каналами типа «все как один»?

Решение, а. Без взаимопомощи.

По формулам (9.1) - (9.4) имеем

(3-2)

б. Со взаимопомощью

По формулам (9.5) - (9.7) находим;

Таким образом, средняя длина очереди и среднее время ожидания в очереди в случае взаимопомощи, больше, но среднее время пребывания заявки в системе - меньше.

Из рассмотренных примеров видно, что взаимопомощь между к? налами типа «все как один», как правило, не способствует повышению эффективности обслуживания: время пребывания заявки в СМО уменьшается, но зато ухудшаются другие характеристики обслуживания.

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

Назйвем условно «равномерной взаимопомощью» следующий тип взаимопомощи. Если заявка приходит в момент, когда все каналы свободны, то все каналов принимаются за ее обслуживание; если, в момент обслуживания заявки, приходит еще одна, часть каналов переключается на ее обслуживание; если, пока обслуживаются эти две заявки, приходит еще одна, часть каналов переключается на ее обслуживание и т. д., до тех пор, пока не окажутся занятыми все каналов; если это так, вновь пришедшая заявка получает отказ (в СМО с отказами) или становится в очередь (в СМО с ожиданием).

При такой дисциплине взаимопомощи заявка получает отказ или становится в очередь только тогда, когда нет возможности ее обслужить. Что касается «простоя» каналов, то он в этих условиях минимален: если в системе имеется хотя бы одна заявка, все каналы работают.

Выше мы упомянули, что при появлении новой заявки часть занятых каналов освобождается и переключается на обслуживание вновь прибывшей заявки. Какая часть? Это зависит от вида функции Если она имеет вид линейной зависимости, как показано на рис. 5.12, и то все равно, какую часть каналов выделить на обслуживание вновь поступившей заявки, лишь бы все каналы были заняты (тогда суммарная интенсивность обслуживаний при любом распределении каналов по заявкам будет равна ). Можно доказать, что если кривая выпукла кверху, как показано на рис. 5.11, то нужно распределять каналы по заявкам как можно более равномерно.

Рассмотрим работу -канальной СМО при «равномерной» взаимопомощи между каналами.