МУ ЭММ часть 1
.pdf
101
Системы массового обслуживания с отказами
Пусть имеется одноканалъная система массового обслуживания с отказами, в которую поступает поток заявок с интенсивностью . Заявки обслуживаются каналом СМО с некоторой интенсивностью . Процесс обслуживания образует поток обслуженных заявок.
Здесь и далее будем предполагать, что все потоки в СМО простейшие. Если заявка поступает в момент, когда единственный канал занят, то она получает отказ и в дальнейшей работе СМО не участвует. Требуется определить предельные вероятности состояний такой СМО и показатели ее эффективности.
СМО имеет два состояния: S0 – канал свободен и S1 – канал занят
(рис. 32).
S0 S1
Рис. 32. Размеченный граф состояний одноканальной СМО с отказами
Система алгебраических уравнений для предельных вероятностей состояний такой СМО имеет вид
p0 p1 ,p1 p0
т.е., по существу, имеем одно уравнение.
Добавляя к нему условие нормировки p0 + p1 = 1. найдем предельные вероятности состояний
p |
|
|
|
|
; |
p |
|
, |
|
|
|
|
|||||
|
0 |
|
|
1 |
|
|||
которые показывают среднее относительное время пребывания СМО в соответствующих состояниях.
Вычислим показатели эффективности функционирования одноканального СМО с отказами:
очевидно, что вероятность отказа Ротк равна относительному времени, в течение которого канал занят, т.е.
Pотк p1 ;
относительная пропускная способность Q представляет собой вероятность, что заявка будет обслужена, т.е.
Q p0 ;
абсолютную пропускную способность СМО найдем, умножив Q на интенсивность потока заявок ,
102
A Q
.
Рассмотрим теперь многоканальную СМО с отказами. Пусть в СМО имеется n каналов, на которые поступает поток заявок с интенсивностью
.
Поток обслуживается одним каналом с интенсивностью , двумя каналами – 2 , тремя – 3 и т.д.
Обозначим состояния СМО S0, S1, S2, …, Sk, …, Sn, где Sk – состояние, когда в ней находится k заявок, т.е. k каналов заняты.
Граф состояний СМО в этом случае (он соответствует процессу гибели и размножения) будет иметь вид, изображенный на рис. 33.
|
|
|
|
|
|
|
|
|
… |
… |
|||||||
S0 |
S1 |
S2 |
Sk |
|
Sn |
|||
|
2 |
3 |
|
k |
(k+1) |
|
n |
|
|
|
Рис. 33. Размеченный граф состояний многоканальной СМО с отказами
Из рис. 4 очевидно, что поток заявок последовательно переводит систему из левого состояния в соседнее правое с одной и той же интенсивностью . Интенсивность потока обслуживания зависит от состояния. Если СМО находится в состоянии S2 (заняты два канала), то она может перейти в состояние S1, когда закончат обслуживание либо первый, либо второй занятый канал. Следовательно, суммарная интенсивность потока обслуживания будет 2 и т.д.
Всоответствии с графом, изображенным на рис. 4, пропускную
способность одного канала обозначим |
, |
2 – двух каналов, |
||
|
|
|
|
|
3 – трех и т.д. |
|
|
||
|
|
|
||
Тогда по аналогии с формулами (3) нетрудно получить предельные
вероятности состояний для рассматриваемой СМО: |
|
|
|||||||||||||||||||
|
|
|
|
|
2 |
|
|
|
|
|
k |
|
|
|
|
n |
1 |
||||
p0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
; |
|||||||
1 |
2! |
|
|
|
|
n! |
|
|
|||||||||||||
|
|
|
|
|
|
|
|
k! |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
k |
|
|
|
||||
p p |
|
; p |
|
|
|
p |
|
; p |
k |
|
|
|
|
|
p |
|
; |
||||
|
|
2! |
|
|
k! |
|
|||||||||||||||
1 |
|
0 |
|
2 |
|
|
|
0 |
|
|
|
|
|
|
0 |
(4) |
|||||
Полученные формулы предельных вероятностей многоканальной СМО с отказами называются формулами Эрланга.
Запишем основные показатели эффективности функционирования многоканальной СМО с отказами:
103
вероятность отказа СМО – предельная вероятность того, что все n каналов заняты, т.е.
n
Pотк n! p0 ;
относительная пропускная способность – вероятность того, что заявка будет обслужена,
|
|
n |
|
|
|
Q 1 P |
1 |
|
p |
|
(5) |
|
|
||||
отк |
|
n! |
0 |
|
|
абсолютная пропускная способность
|
|
n |
|
|
|
|
A Q 1 |
|
p |
0 |
|
; |
|
|
|
|||||
|
n! |
|
|
|
||
|
|
|
|
|
||
среднее число занятых каналов k – математическое ожидание числа занятых каналов, которое определяется по известной формуле математического ожидания
n
kki pi ,
i1
где рi – вероятность того, что i каналов будут заняты; ki – количество занятых каналов.
Величину k можно найти проще. Так как каждый занятый канал обслуживает в среднем заявок в единицу времени, то
|
|
A |
|
|
|
n |
|
|
|
|
k |
|
1 |
|
p |
|
|
|
|||
|
|
|
|
|
||||||
|
|
|
|
0 |
|
|
||||
|
|
|
|
|
n! |
|
|
|||
|
|
|
|
|
|
|
. |
|||
|
|
|
|
|
|
|
|
|
|
|
Пример 5. Торговая фирма выполняет заказы на приобретение товаров по телефону. В настоящее время в офисе фирмы установлен один телефон. Интенсивность входящего потока заявок составляет 30 заявок/ч. Длительность оформления заказа в среднем составляет 5 мин.
Определить показатели эффективности функционирования такой СМО.
Сколько телефонов нужно поставить в офисе, чтобы относительная пропускная способность СМО была не менее 0,75?
Решение. При интенсивности потока заявок равна 30 заявок/ч время обслуживания (оформление заказа) составляет Т = 5 мин/заявка, количество каналов (телефонов) n = 1.
104
Приведем к одинаковой размерности интенсивность входящего потока и интенсивность обслуживания. Так как интенсивность потока
1
обслуживания T , то
60 мин/ч 5 мин/заявка = 12 заявок/ч.
Тогда показатели эффективности:вероятность отказа
|
P |
|
|
|
|
|
|
|
30 |
|
|
|
30 |
|
0,714 ; |
||||||
|
|
|
|
|
|
|
30 12 |
|
|
||||||||||||
|
отк |
|
|
|
42 |
|
|
||||||||||||||
|
относительная пропускная способность |
|
|||||||||||||||||||
|
Q |
|
|
|
|
|
|
12 |
|
|
|
12 |
0,286 ; |
||||||||
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
12 30 |
42 |
|
|
|||||||||||||
|
абсолютная пропускная способность |
|
|
|
|||||||||||||||||
|
A Q |
|
|
|
|
|
30 12 |
|
|
360 |
8,57 |
||||||||||
|
|
|
|
30 12 |
42 |
||||||||||||||||
|
|
|
|
|
|
|
|
|
|
заявок/ч. |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Чтобы найти, при каком минимальном количестве телефонов относительная пропускная способность будет не менее 0,75, будем постепенно увеличивать число телефонов в офисе и по формулам (4) определим относительную пропускную способность.
Предварительно вычислим
30 2,5
12
1.Пусть в фирме установлено два телефона. Тогда количество каналов n = 2. Вероятность, что все телефоны свободны,
|
|
|
|
2 |
|
1 |
1 |
|
|
|
|
1 |
|
p |
0 |
1 |
|
|
|
|
|
|
|
0,151 |
|||
|
|
|
|
2 |
|
|
|||||||
|
|
2! |
|
|
|
2,5 |
|
|
6,625 |
|
|||
|
|
|
|
|
1 2,5 |
|
|
|
|
||||
|
|
|
|
|
|
|
2! |
|
|
. |
|||
|
|
|
|
|
|
|
|
|
|
||||
Тогда относительная пропускная способность
|
|
2 |
|
|
2,52 |
|
|
Q 1 P |
1 |
|
p |
|
1 |
|
0,151 1 0,491 0,509. |
2! |
|
2! |
|||||
отк |
|
|
0 |
|
|
||
Видно, что величина Q значительно меньше требуемого значения 0,75 по условию задачи. Добавим еще один телефон. Тогда производим все вычисления аналогично.
2. Пусть в фирме установлено три телефона. Тогда количество каналов n = 3.
105
|
|
|
|
2 |
|
|
3 |
|
1 |
|
|
|
1 |
|
|
|
|
|
|
1 |
|
|
p |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
0,108 |
||||||
|
|
|
|
|
|
|
|
2 |
|
|
3 |
|
|
|||||||||
|
|
2! |
|
3! |
|
|
|
|
|
2,5 |
|
2,5 |
|
|
9,229 |
|
||||||
|
|
|
|
|
|
1 2,5 |
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
2! |
3! |
|
|
; |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
Q 1 P |
|
1 |
3 |
p |
1 |
2,53 |
|
0,108 1 0,281 0,719. |
|||||||||||||
|
|
|
|
|
||||||||||||||||||
|
|
отк |
|
|
|
3! |
0 |
3! |
|
|
|
|
|
|
|
|
|
|
||||
Видно, что величина Q меньше требуемого значения 0,75 по условию задачи. Добавим еще один телефон.
3. Пусть в фирме установлено четыре телефона. Тогда количество каналов n = 4.
|
|
|
|
2 |
|
|
3 |
|
|
4 |
|
1 |
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
1 |
|
|||
p |
0 |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0,092 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
3 |
|
|
4 |
|
|
||||||||||
|
|
2! |
|
3! |
4! |
|
|
|
|
|
2,5 |
|
|
2,5 |
|
2,5 |
|
|
10,857 |
|
|||||||||||
|
|
|
|
|
|
|
1 2,5 |
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2! |
|
3! |
|
4! |
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
; |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q 1 P |
|
1 |
|
4 |
p |
1 |
2,54 |
0,092 1 0,150 0,850. |
|||||||||||||||||||||
|
|
|
|
|
4! |
4! |
|
||||||||||||||||||||||||
|
|
|
|
|
отк |
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
Из последнего решения следует: чтобы относительная пропускная способность СМО была не менее 0,75, в офисе должно быть не менее четырех телефонов.
Системы массового обслуживания с ожиданием
Пусть имеется одноканальная СМО с неограниченной очередью (например, телефон-автомат с одной будкой). То есть на СМО не наложены никакие ограничения ни по длине очереди, ни по времени ожидания.
Поток заявок, поступающих в СМО, имеет интенсивность . Поскольку обслуживание ведет один канал, то обслуживание заявок производится с одинаковой интенсивностью для всех состояний.
Необходимо найти предельные вероятности состояний и показатели эффективности СМО.
Система может находиться в одном из состояний S0, S1, S2, …, Sk, … по числу заявок, находящихся в СМО:
S0 – канал свободен;
S1 – канал занят, обслуживает заявку, очереди нет; S2 – канал занят, в очереди одна заявка;
…
Sk – канал занят, в очереди (k – 1) заявка;
…
Размеченный граф состояний СМО имеет вид, изображенный на рис. 34.
|
|
106 |
|
|
|
|
|
|
|
|
|
|
|
… |
… |
|||||
S0 |
S1 |
S2 |
|
|
Sk |
|
|
|
|
… |
|
|
… |
Рис. 34. Одноканальная СМО с ожиданием
Это процесс гибели и размножения, но с бесконечным числом состояний. Для такого процесса доказано, что если среднее число приходящих заявок в единицу времени меньше среднего числа обслуживаемых заявок
< 1
то предельные вероятности существуют.
Если ≥ 1, то очередь растет до бесконечности.
Для определения предельных вероятностей состояний можно воспользоваться формулами (3) для процесса гибели и размножения (хотя они были получены для случая конечного числа состояний системы, ими можно воспользоваться и в данном случае).
Тогда для случая одного канала n = 1 в соответствии с формулами (4) можно записать
p0 = (1 + + 2 + … + k + …)-1.
Предельные вероятности могут существовать лишь при < 1. Ряд,
1
стоящий в скобках, сходится к сумме 1 , так как это геометрический ряд со знаменателем меньшим единицы. Поэтому можно записать для первого члена прогрессии
p0 = 1 – ,
а предельные вероятности других состояний определяются по формулам p1 = p0 = (1 – ); p2 = 2p0 = 2(1 – ); …, pk = kp0 = k(1 – ) …
Анализируя полученные зависимости, можно сделать вывод, что предельные вероятности состояний образуют убывающую геометрическую прогрессию со знаменателем < 1. Тогда в этой прогрессии первый член p0 – наибольший.
Это значит, что если СМО справляется с потоком заявок, то наиболее вероятным ее состоянием из всех возможных состояний будет отсутствие заявок в системе.
Рассмотрим основные показатели эффективности СМО с ожиданием:
среднее число заявок в системе Lсист определяется по формуле математического ожидания
107
Lсист kpk 1 k k
k 1 k 1 .
Можно показать, что эта формула преобразуется при < 1 к виду
1 ;
среднее число заявок, находящихся иод обслуживанием Lоб также легко определить по формуле для математического ожидания
Lоб = 0p0 + 1(1 – p0) = 1 – p0 = 1 – (1 – ) = ;
среднее число заявок в очереди Lоч, очевидно, определяется как разность Lсист и Lоб
|
|
2 |
|
2 |
||
|
|
|
|
|
|
|
|
|
|
|
|||
Lоч = Lсист – Lоб =1 |
1 |
1 ; |
||||
среднее время пребывания заявки в системе Тсист или в очереди Точ равно среднему числу заявок в системе или в очереди, деленному на интенсивность потока заявок,
|
|
L |
|
|
|
L |
|
2 |
|
||
T |
|
сист |
|
|
|
; T |
оч |
|
|
|
|
|
1 |
|
1 |
|
|||||||
сист |
|
|
оч |
|
. |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
Эти зависимости называются формулами Литтла.
Пример 6. Минимаркет с одним контролером-кассиром обслуживает покупателей, интенсивность входящего потока которых равна 20 покупателей/ч. Интенсивность потока обслуживания равна 25 покупателей/ч.
Найти показатели эффективности СМО, а также вероятность, что в очереди стоят не более двух покупателей.
Решение. Выпишем исходные данные:
|
|
|
20 |
|
|
|
|
|
|
= 20; = 25; = |
|
25 |
= 0,8. |
|
Проведем вычисления.
Вероятность того, что контролер-кассир свободен,
р0 = 1 – = 1 – 0,8 = 0,2.
Вероятность того, что кассир занят,
Рзан =1 – p0 = 1 – 0,2 = 0,8.
Среднее число покупателей в очереди
L |
|
2 |
0,82 |
|
|
|
|
|
|
|
|
|
|
||||
оч |
1 |
1 0,8 = 3,2 покупателя. |
|||
Среднее число покупателей в минимаркете
|
|
|
|
|
|
|
|
|
|
108 |
|
|
|
|
||
L |
|
|
|
|
|
|
|
|
|
0,8 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||||||
сист |
|
1 |
|
1 0,8 = 4 покупателя. |
||||||||||||
Среднее время простоя в очереди |
|
|
||||||||||||||
T |
|
2 |
|
|
|
|
|
0,82 |
|
|
|
|
||||
1 |
|
201 0,8 |
|
|
||||||||||||
оч |
|
|
|
= 0,16 ч = 9,6 мин. |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Среднее время нахождения в минимаркете |
||||||||||||||||
Tсист |
|
|
|
|
|
|
0,8 |
|
|
|
|
|||||
1 |
|
|
20(1 0,8) |
= 0,2 ч = 12 мин. |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вероятность того, что в очереди не более двух покупателей, определяется по формуле
Р(n 2) = p0 + p1 + p2 + p3 = (l – )(1 + + 2 + 3) =
=(1 – 0,8)(1 + 0,8 + 0,82 + 0,83) = 0,2 2,95 = 0,59.
ЗАДАНИЯ
Вариант 1
Задача 1. В бюро обслуживания в среднем поступает 15 заявок в час. Считая поток заказов простейшим, определить вероятность того, что:
а) за 2 мин не поступит ни одного заказа; б) за 20 мин поступит не более двух заказов.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 – обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе
кассы заняты, если 01 = 4; 12 = 1; 10 = 3; 21 = 2 (покупателей/мин). Задача 3. Минимаркет с одним кассиром обслуживает покупателей,
интенсивность входящего потока которых равна 10 покупателей/ч. Интенсивность потока обслуживания равна 14 покупателей/ч. Найти показатели эффективности СМО, а также вероятность, что в очереди стоят не более трех покупателей.
Вариант 2
Задача 1. В ресторан прибывает в среднем 15 посетителей в час.
Считая поток посетителей простейшим и зная, что ресторан открывается в 1000, определить:
а) вероятность того, что в 1015 в ресторане будет 20 посетителей при условии, что в 1005 их было 11;
б) вероятность того, что между 1130 и 1135 в ресторане окажется
новый посетитель, если известно, что предшествующий посетитель прибыл в 1125.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 –
109
обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе
кассы заняты, если 01 = 4; 12 = 1; 10 = 3; 21 = 2 (покупателей/мин). Для решения использовать теорию процесса гибели и размножения.
Задача 3. Найти основные показатели эффективности функционирования одноканальной СМО с отказами, если интенсивность входящего потока заявок равна 80 заявок/ч, а средняя продолжительность обслуживания одной заявки – 3 мин.
Вариант 3
Задача 1. В бюро обслуживания в среднем поступает 9 заявок в час. Считая поток заказов простейшим, определить вероятность того, что:
а) за 5 мин не поступит ни одного заказа; б) за 15 мин поступит не более трех заказов.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 – обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе
кассы заняты, если 01 = 1; 12 = 3; 10 = 2; 21 = 6 (покупателей/мин). Задача 3. Минимаркет с одним кассиром обслуживает покупателей,
интенсивность входящего потока которых равна 18 покупателей/ч. Интенсивность потока обслуживания равна 24 покупателей/ч. Найти показатели эффективности СМО, а также вероятность, что в очереди стоят не более двух покупателей.
Вариант 4
Задача 1. В ресторан прибывает в среднем 25 посетителей в час.
Считая поток посетителей простейшим и зная, что ресторан открывается в 1200, определить:
а) вероятность того, что в 1220 в ресторане будет 40 посетителей при условии, что в 1120 их было 21;
б) вероятность того, что между 1330 и 1345 в ресторане окажется
новый посетитель, если известно, что предшествующий посетитель прибыл в 1328.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 – обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе
кассы заняты, если 01 = 1; 12 = 3; 10 = 2; 21 = 6 (покупателей/мин). Для решения использовать теорию процесса гибели и размножения.
Задача 3. Найти основные показатели эффективности функционирования одноканальной СМО с отказами, если интенсивность входящего потока заявок равна 40 заявок/ч, а средняя продолжительность обслуживания одной заявки – 1 мин.
110
Вариант 5
Задача 1. В бюро обслуживания в среднем поступает 11 заявок в час. Считая поток заказов простейшим, определить вероятность того, что:
а) за 2 мин не поступит ни одного заказа; б) за 17 мин поступит не более двух заказов.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 – обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе
кассы заняты, если 01 = 4; 12 = 5; 10 = 7; 21 = 8 (покупателей/мин). Задача 3. Минимаркет с одним кассиром обслуживает покупателей,
интенсивность входящего потока которых равна 28 покупателей/ч. Интенсивность потока обслуживания равна 31 покупатель/ч. Найти показатели эффективности СМО, а также вероятность, что в очереди стоят не более трех покупателей.
Вариант 6
Задача 1. В ресторан прибывает в среднем 22 посетителя в час.
Считая поток посетителей простейшим и зная, что ресторан открывается в 1000, определить:
а) вероятность того, что в 1015 в ресторане будет 30 посетителей при условии, что в 1005 их было 11;
б) вероятность того, что между 1130 и 1135 в ресторане окажется
новый посетитель, если известно, что предшествующий посетитель прибыл в 1122.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 – обе кассы свободны; S1 – одна касса свободна, а другая занята; S2 – обе
кассы заняты, если 01 = 4; 12 = 5; 10 = 7; 21 = 8 (покупателей/мин). Для решения использовать теорию процесса гибели и размножения.
Задача 3. Найти основные показатели эффективности функционирования одноканальной СМО с отказами, если интенсивность входящего потока заявок равна 25 заявок/ч, а средняя продолжительность обслуживания одной заявки – 11 мин.
Вариант 7
Задача 1. В бюро обслуживания в среднем поступает 25 заявок в час. Считая поток заказов простейшим, определить вероятность того, что:
а) за 1 мин не поступит ни одного заказа; б) за 12 мин поступит не более трех заказов.
Задача 2. В минимаркете две кассы. Найти относительное время пребывания этой системы массового обслуживания в состояниях: S0 –