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

В подавляющем большинстве случаев на практике система массового обслуживания является многоканальными, то есть параллельно могут обслуживаться несколько заявок, и, следовательно, модели с обслуживающими каналами (где число каналов обслуживания n >1) представляют несомненный интерес.
Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется 1/μ. Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, при чем длительность процедуры обслуживания каждым из каналов является случайной величиной, починенной экспоненциальному закону распределения. Конечная цель использования параллельно включенных обслуживающих каналов заключается в повышение (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно n клиентов.
Стационарное решение системы имеет вид:
;
где, .
Формулы для вычисления вероятностей называются формулами Эрланга.
Определим вероятностные характеристики функционирования многоканальной СМО с отказами в стационарном режиме:
вероятность отказа:
.
так как заявка получает отказ, если приходит в момент, когда все каналов заняты. Величина Р отк характеризует полноту обслуживания входящего потока;
вероятность того, что заявка будет принята к обслуживанию (она же – относительная пропускная способность системы) дополняет Р отк до единицы:
.
абсолютная пропускная способность

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

Величина характеризует степень загрузки СМО.
Пример . Пусть n -канальная СМО представляет собой вычислительный центр (ВЦ) с тремя (n =3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступающих на ВЦ, имеет интенсивность λ=1 задача в час. Средняя продолжительность обслуживания t об =1,8 час.
Требуется вычислить значения:
- вероятности числа занятых каналов ВЦ;
- вероятности отказа в обслуживании заявки;
- относительной пропускной способности ВЦ;
- абсолютной пропускной способности ВЦ;
- среднего числа занятых ПЭВМ на ВЦ.
Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.
Решение.
Определим параметр μ потока обслуживаний:
.
Приведенная интенсивность потока заявок
.
Предельные вероятности состояний найдем по формулам Эрланга:

Вероятность отказа в обслуживании заявки
.
Относительная пропускная способность ВЦ
.
Абсолютная пропускная способность ВЦ:
.
Среднее число занятых каналов – ПЭВМ

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех – остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев (Р 3 = 0,180). Очевидно, что пропускную способность ВЦ при данных λ и μ можно увеличить только за счет увеличения числа ПЭВМ.
Определим, сколько нужно использовать ПЭВМ, чтобы сократить число не обслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходила 0,0180. Для этого используем формулу вероятности отказа:

Составим следующую таблицу:

n
P 0	0,357	0,226	0,186	0,172	0,167	0,166
P отк	0,673	0,367	0,18	0,075	0,026	0,0078

Анализируя данные таблицы, следует отметить, что расширение числа каналов ВЦ при данных значениях λ и μ до 6 единиц ПЭВМ позволит обеспечить удовлетворение заявок на решение задач на 99,22%, так как при n = 6 вероятность отказа в обслуживании (Р отк ) составляет 0,0078.

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

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

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

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

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

Классификационные признаки

Разновидности систем массового обслуживания

Входящий поток требований

Ограниченность требований

Замкнутые

Открытые

Закон распределения

Системы с конкретным законом распределения входящего потока: показательным, Эрланга k -го порядка, Пальма, нормальным и т.п.

Очередь

Дисциплина очереди

С упорядоченной очередью

С неупорядоченной очередью

С приоритетом обслуживания

Ограничения ожидания обслуживания

С отказами

С неограниченным ожиданием

С ограничениями (смешанные)

По длине очереди

По времени ожидания в очереди

По времени пребывания в СМО

Комбинированные

Дисциплина обслуживания

Этапность обслуживания

Однофазные

Многофазные

Количество каналов обслуживания

Одноканальные

Многоканальные

С равноценными каналами

С неравноценными каналами

Надежность каналов обслуживания

С абсолютно надежными каналами

С ненадежными каналами

Без восстановления

С восстановлением

Взаимопомощь каналов

Без взаимопомощи

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

Достоверность обслуживания

С ошибками

Без ошибок

Распределение времени обслуживания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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