Модели СМО с отказами

Математические модели систем массового обслуживания

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

Одноканальная СМО с отказами. Математическая постановказадачи [10]. Рассмотрим простейшую из всех задач теории массового обслуживания – задачу функционирования одноканальной СМО с отказами в которую поступает простейший поток заявок с интенсивностью l. Интервал времени t между двумя соседними заявками распределен по закону Пуассона. Поток обслуживания так же является простейшим с интенсивностью m. Заявка, нашедшая канал занятым, получает отказ и покидает систему не обслуженной.

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

• S₀ - канал свободен;
• S₁ - канал занят.

S₀

S₁

l

m

Граф-процесса функционирования СМО представлен на рис. 4. Кружками на этом графе показаны возможные состояния системы, а стрелками — возможные переходы системы из состояния в состояние за бесконечно малый промежуток времени dt. Рядом со стрелками приведены интенсивности переходов.

Рисунок 4. – Граф-процесса функционирования одноканальной СМО с отказами

Обозначим вероятности состояний системы и соответственно. Составим систему дифференциальных уравнений Колмогорова:

(34)

которая дополняется условием:

(35)

Выразив р₁(t) из уравнения (35) и подставив его в первое уравнение системы (34) получим

(36)

Решая это уравнение при начальных условиях, получим

(37)

При установившемся режиме работы системы вероятности с течением времени не меняются, т.е. выполняется условие

(38)

В этом случае предельные значения вероятностей состояний системы будут равны:

(39)

(40)

Зависимость величин вероятностей состояний системы от времени представлена на рис. 5.

Рисунок 5. − Зависимость величин вероятностей состояний системы от времени

Одними из важнейших характеристик функционирования данной системы являются:

• относительная пропускная способность (Q), которая равняется р₀(t), т.е.

; (41)

• абсолютная пропускная способность (A), которая определяется следующим уравнением

(42)

Одними из важнейших показателей качества функционирования СМО являются:

• вероятность обслуживания, которая определяется как

(43)

• вероятности отказа, которая равна

(44)

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

На практике часто встречающиеся следующие цели функционирования СМО рассматриваемого класса:

— обслуживание заявки, поступившей в систему в момент времени t, сократив до минимума время пребывания в системе;

— обслуживание максимального числа заявок на момент времени t функционирования системы;

— обслуживание максимального числа заявок, поступающих в систему за промежуток времени [0, t ].

Цель моделирования — определить зависимость эффективности функционирования системы от числа каналов и от интенсивностей потоков заявок и обслуживаний (для обоснования рационального режима функционирования или рациональной структуры СМО).

Разработка математической модели. Физическая система может находиться в одном из нескольких состояний:

• А₀ – все каналы свободны;
• А₁ - занят один канал, остальные свободны;
• .....................;
• А_n – все каналы заняты.

Обслуживающая система находиться в состоянии n, если в ней имеется n – заявок. Из аксиом пуассоновского процесса следует, что вероятность появления более одной новой заявки на протяжении малого промежутка времени стремиться к нулю при dt ® 0. Это означает, что при k > 0 состояния k может быть изменено только в двух возможных направлениях: k-1 когда с интенсивностью m обслуживается заявка, тем самым, выбывая из системы, и k+1, когда имеет место поступление заявки с интенсивностью l. Граф - процесса функционирования данной СМО представлен на рис. 6.

Рисунок 6. − Граф-процесса функционирования многоканальной СМО с отказами

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

Пусть на момент времени t распределение вероятностей равно. Тогда пользуясь общими правилами можно составить СДУ ЭРЛАНГА:

(45)

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

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

(46)

аналогично интенсивности выходящего потока

(47)

Отсюда, приравнивая эти две интенсивности получаем следующее уравнение баланса

= (48)

Решается уравнение баланса рекуррентно, последовательно выражая вероятность р_i через вероятность р₀. Для к = 0 вероятность р₁ будет определяться из уравнения:

(49)

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

Напомню, что стационарный режим имеет место, когда выполняется условие (38), тогда

(50)

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

(51)

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

Решая данную систему методом последовательной подстановки также получим уравнение (49).

(52)

Подставив значения р ₁во второе уравнение, получим

(53)

Аналогичным образом из третьего уравнения будем иметь

(54)

Тогда используя метод математической индукции в общем случае находим вероятность p_k:

при к £ n (55)

(56)

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

(57)

(58)

(59)

(60)

(61)

(62)

(63)

(64)

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

Цели функционирования СМО могут быть различными:

- обслужить заявку, которая в потоке других заявок поступит в систему в момент времени t;

- обслужить максимальное число заявок, поступающих в систему в промежутке времени [0, t ] и т. д.

Цель моделирования:

- определить зависимость эффективности СМО от числа каналов и от интенсивности потока заявок и обслуживаний (для обоснования рационального режима функционирования или рациональной структуры СМО).

Разработка математической модели. Показатель эффективности функционирования СМО определяется в соответствии с принципом Колмогорова. Для первой из рассмотренных выше целей функционирования СМО показателем эффективности является вероятность обслуживания поступивший в момент времени t заявки:

ПЭ = P _обсл(t) (65)

Во втором случае показателем эффективности является математическое ожидание числа заявок, обслуживаемых за промежуток времени [0, t ]:

ПЭ = (66)

Примем эту вероятность в качестве основного показателя эффективности. В качестве дополнительных показателей эффективности могут выступать:

- математическое ожидание числа заявок, ожидающих обслуживания (находящихся в очереди)[11];

- математическое ожидание времени пребывания заявки в очереди;

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

Обозначим:

- A_k (где) — состояния системы, при которых n каналов заняты обслуживанием, а очередь заявок отсутствует;

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

- — вероятности нахождения СМО в состояниях или соответственно на момент времени t.

Поступившая в СМО заявка получает отказ, если система находится в состоянии т. е. заняты все n каналов и все t мест для ожидания в очереди.

Граф - процесса данной СМО представлен на рис. 4.4. Кружками на этом графе показаны возможные состояния системы, а стрелками — возможные переходы системы из состояния в состояние за бесконечно малый промежуток времени dt. Рядом со стрелками приведены интенсивности переходов.

Поэтому вероятность обслуживания поступивший в момент времени t заявки будет равна:

Р _обсл(t) = (67)

Рисунок. 7 − Граф-процесса функционирования СМО с ограничением на длину очереди

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

(68)

Заметим, что заявки в очереди отделены друг от друга средними временными интервалами их поступления в систему, равными Поэтому при длине очереди математическое ожидание времени пребывания заявки в очереди находится из выражения

(69)

Отсюда можно получить выражение:

(70)

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

(71)

а числа простаивающих каналов равно

(72)

Как видно, определение показателей эффективности требует умения находить распределение вероятностей системы.

Пусть на момент времени t распределение вероятностей равно а условная вероятность перехода системы из состояния A_i в состояние A_k за время t составляет Тогда вероятность нахождения системы на момент времени t+t в состоянии A_k может быть найдена по формуле полной вероятности:

(73)

Рассмотрим случай бесконечно малого t, т. е. t = dt. За время dt (при dt ® 0) в силу ординарности процесса система может или перейти в одно из смежных состояний, или остаться в прежнем состоянии. Поэтому оказаться на момент времени t+dt в состоянии A_k система может только при одном из следующих условий:

— или на момент времени t система находилась в состоянии и за время dt в систему поступила заявка;

— или на момент времени t система находилась в состоянии и за время dt освободился канал;

— или на момент времени t система находилась в состоянии A_k, и за время dt в систему не поступила заявка, и канал не освободился.

Вероятность поступления в систему заявки за время dt равняется l dt, вероятность освобождения одного из каналов равна m dt. Вероятность того, что в систему не поступит заявка и не освободится канал равна

(74)

или, с точностью до бесконечно малых высших порядков,

(75)

Отсюда вероятность нахождения системы в момент времени t+dt в состоянии A_k может быть определена по формуле полной вероятности:

(76)

Преобразуем полученное выражение:

(77)

При dt, стремящемся к нулю, будем иметь

(78)

Итак, для определения вероятности P_k (t) получили дифференциальное уравнение. Аналогичные уравнения могут быть получены и для определения вероятностей всех остальных состояний системы. В результате будем иметь следующую систему дифференциальных уравнений:

......................

...................... (79)

......................

......................

Система (72) имеет n + m + 1 неизвестных и n + m независимых уравнений, так как любое из уравнений системы может быть получено из остальных благодаря условию

Поэтому система уравнений (4.44) должна быть дополнена этим условием. Проинтегрировав систему в заданном интервале времени [0, t ], получим распределение вероятностей состояний системы на заданный момент времени t, а затем по формулам (58 ÷ 65) — рассчитаем значения основного и дополнительных показателей эффективности. Интегрирование осуществляется на ЭВМ одним из численных методов. Начальные условия для интегрирования, т. е. значения вероятностей P_k (0); (k = 0, 1, 2,..., n; s = 1, 2,..., m) состояний системы на момент времени t = 0 начала процесса обслуживания, выявляются при оценке среды.

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

(80)

Но при этом и вместо системы дифференциальных уравнений (72) будем иметь систему алгебраических линейных уравнений:

.................

.............. (81)

................

................

которая дополняется условием

В общем случае для всех

При k > n

(82)

(83)

..................

(84)

Вероятность р ₀найдём из условия

(85)

откуда

(86)

так как

(87)

С учётом (85) для определения вероятностей будем иметь следующие выражения

(88)

(89)

Знание вероятностей позволяет определить показатели эффективности СМО. Вероятность обслуживания заявки

(90)

а вероятность получения отказа

(91)

Математическое ожидание числа заявок в очереди составит

(92)

а математическое ожидание времени пребывания заявки в очереди —

(93)

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

(94)

а математическое ожидание числа простаивающих каналов — по формуле

(95)

Разработаем теперь общую схему действий при моделировании процессов массового обслуживания в стационарном режиме. Предварительно выведем правило составления формул для определения вероятностей Запишем формулу (79) в следующем виде:

(96)

Рассмотрение структуры этой формулы и структуры графа СМО (см. рис. 6.2) позволяет сформулировать следующее правило. Формула для определения вероятности p_k состоит из двух сомножителей. Одним из них является вероятность р ₀, а другим — дробь. В числителе этой дроби помещается произведение всех интенсивностей переходов, стоящих у стрелок, направленных слева направо от стрелки, ведущей из состояния А ₀, и до стрелки, ведущей в состояние A_k; в знаменателе — произведение всех интенсивностей переходов стоящих у стрелок, направленных справа налево от стрелки, ведущей в состояние А ₀, до стрелки ведущей из состояния A_k.

По аналогичному правилу составляется и выражение для определения вероятностей (s = 1, 2,..., m).

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

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

(97)

(98)

Вероятность р ₀определим из выражения

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

(99)

Поэтому будем иметь

(100)

(101)

(102)

Найдём теперь выражения для определения показателей эффективности СМО:

— математическое ожидание числа заявок в очереди (длины очереди)

(103)

— математическое ожидание времени пребывания заявки в очереди

(104)

— математическое ожидание времени пребывания заявки в системе

(105)

— математическое ожидание числа каналов, занятых обслуживанием заявок,

(106)

после подстановки значений p_k и p_n+s и некоторых преобразований получим

(107)

— математическое ожидание числа простаивающих каналов

(108)

ЛИТЕРАТУРА

а) Основная:

1. Бабурин В.А., Полянская Т.И., Шилкина И.Д., Экономико-математические методы и модели в управлении водным транспортом: Системы массового обслуживания: Учебное пособие. СПб.: СПГУВК, 2009.

2. Вентцель Е.С., Исследование операций: Учебник. М.: Советское радио, 1972.

3. Хэмди А. Таха, Введение в исследование операций: Руководство. М.: Вильямс, 2001.

б) Дополнительная:

4. Вентцель Е.С., Теория вероятностей: Учебник. М.: Наука, 1964.

5. Красс М.С., Чупрынов Б.П., Математические методы и модели: Учебное пособие для магистров экономики. – Санкт-Петербург: ПИТЕР, 2006.

[1] Целесообразно цель действий определять в содержании приказа, распоряжения или иного подобного управленческого документа.

[2] Основной показатель эффективности формулируется руководителем и лицом принимающим решение, используя принцип А.Н. КОЛМОГОРОВА.

[3] По сути, функциональные зависимости основного показателя эффективности или параметра, ему эквивалентного.

[4] Это уравнение для вероятности состояния называется уравнением КОЛМОГОРОВА.

[5] Дисциплина ожидания может предусматривать отсутствие очереди

[6] Характеристикой каналов обслуживания является закон распределения времени обслуживания каналами заявок.

[7] Характеристикой потока заявок является закон распределения числа заявок..

[8] Т.е. СМО с различными законами распределения времени работы каналов обслуживания и их восстановления.

[9] Таким образом, искомая вероятность есть вероятность суммы несовместных событий. Это обстоятельство означает: за время dt может освободиться один либо не освободиться ни одного из k каналов. Вероятность освобождения хотя бы одного канала равна вероятности освобождения ровно одного канала (с точностью до бесконечно малых высшего порядка).

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

[11] Этот показатель часто называют также математическим ожиданием длины очереди.

Дата добавления: 2014-01-20