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

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

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

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

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

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

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

Отношение называют коэффициентом загрузки системы . Часто рассматриваются только такие системы, в которых .

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

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

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

Эффективность систем обслуживания в зависимости от условий задач и целей исследования можно характеризовать большим числом разных количественных показателей.

Наиболее часто применяются следующие показатели :

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

Частным случаем является – вероятность того, что все каналы свободны.

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

3. Среднее число занятых каналов характеризует степень загрузки системы.

4. Среднее число каналов, свободных от обслуживания:

5. Коэффициент (вероятность) простоя каналов .

6. Коэффициент загрузки оборудования (вероятность занятости каналов)

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

8. Абсолютная пропускная способность , т.е. число заявок (требований), которое может обслужить система за единицу времени:

9. Среднее время простоя канала

Для систем с ожиданием используют дополнительно характеристики:

10. Среднее время ожидания требований в очереди .

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

12. Средняя длина очереди .

13. Среднее число заявок в сфере обслуживания (в СМО)

14. Вероятность того, что время пребывания заявки в очереди не продлится больше определенного времени.

15. Вероятность того, что число требований в очереди, ожидающих начала обслуживания, больше некоторого числа.

Кроме перечисленных критериев при оценке эффективности систем могут быть использованы стоимостные показатели :

– стоимость обслуживания каждого требования в системе;

– стоимость потерь, связанных с ожиданием в единицу времени;

– стоимость убытков, связанных с уходом требований из системы;

– стоимость эксплуатации канала системы в единицу времени;

– стоимость единицы простоя канала.

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

а) для систем с неограниченным ожиданием

Где – интервал времени;

б) для систем с отказами ;

в) для смешанных систем .

Варианты, в которых предусматривается строительство (ввод) новых элементов системы (например, каналов обслуживания), обычно сравниваются по приведенным затратам .

Приведенные затраты по каждому варианту есть сумма текущих затрат (себестоимости) и капитальных вложений, приведенных к одинаковой размерности в соответствии с нормативом эффективности, например:

(приведенные затраты за год);

(приведенные затраты за срок окупаемости),

где – текущие затраты (себестоимость) по каждому варианту, р.;

– отраслевой нормативный коэффициент экономической эффективности капитальных вложений (обычно = 0,15 - 0,25);

– капитальные вложения по каждому варианту, р.;

– нормативный срок окупаемости капитальных вложений, лет.

Выражение есть сумма текущих и капитальных затрат за определенный период. Их называют приведенными , так как они относятся к фиксированному отрезку времени (в данном случае к нормативному сроку окупаемости).

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

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

Очевидно, что .

Если процесс, протекаемый в системе с дискретными состояниями и непрерывным временем, является марковским , то для вероятностей состояний можно составить систему линейных дифференциальных уравнений Колмогорова.

Eсли имеется размеченный граф состояний (рис.4.3) (здесь над каждой стрелкой, ведущей из состояния в состояние, проставлена интенсивность потока событий, переводящего систему из состояния в состояние по данной стрелке), то систему дифференциальных уравнений для вероятностей можно сразу написать, пользуясь следующим простым правилом .

В левой части каждого уравнения стоит производная , а в правой части – столько членов, сколько стрелок связано непосредственно с данным состоянием; если стрелка ведет в

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