- •ПРЕДИСЛОВИЕ
- •1. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
- •1.1. Основные элементы систем массового обслуживания
- •1.2. Пуассоновский поток требований
- •1.3. Типы систем обслуживания. Краткая символика
- •1.4. Показатели эффективности систем массового обслуживания
- •2. ОСНОВНЫЕ ТИПЫ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
- •2.1. Системы масового обслуживания с отказами
- •2.2. Системы с бесконечным числом приборов
- •2.3. Системы массового обслуживания с ожиданием
- •2.4. Замкнутые системы массового обслуживания
- •2.5. Смешанные системы с ожиданием
- •3. СПЕЦИАЛЬНЫЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
- •3.1. Упорядоченные системы
- •3.2. Системы с поступлением групповых заявок
- •3.3. Системы с приборами разной производительности
- •3.4. Многофазные системы
- •3.5. Системы с накопителем требований
- •3.6. Системы со смешанным потоком требований
- •3.7. Системы с ненадежными обслуживающими приборами
- •3.8. Системы с групповым обслуживанием
- •4. МАРКОВИЗИРОВАНИЕ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ
- •4.1. Потоки Эрланга и их свойства
- •4.2. Замена реальных потоков потоками Эрланга
- •4.3. Марковские модели процессов с ограниченным последействием
Заметим, что если каждая баржа будет разгружаться только одной брига- дой, то получим pотк = 0,145 , т. е. на 2,5% больше отказов.
4. МАРКОВИЗИРОВАНИЕ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ
Вбольшинстве практически интересных задач потоки событий, перево- дящие систему из одного состояния в другое, могут быть с достаточной точно- стью аппроксимированы потоками Пуассона. В этом случае процесс, проте- кающий в системе, благодаря замене реальных потоков пуассоновскими сво- дится к марковскому, т.е. становится процессом без последействия, для которо- го оказывается удобным аналитическое исследование.
Представление процесса функционирования системы в виде марковского случайного процесса с непрерывным временем позволяет применить для опи- сания процесса ее функционирования аппарат обыкновенных дифференциаль- ных уравнений (примеры марковских моделей массового обслуживания приве- дены в предыдущих разделах).
Замена эмпирического процесса марковским путем замены реальных по- токов пуассоновскими потоками приводит, естественно, к некоторым погреш- ностям, величина которых зависит от степени последействия реальных потоков.
Вбольшинстве практических случаев эти погрешности невелики и не превы- шают погрешностей в исходных данных, возникающих при статистической об- работке реальных потоков. Однако иногда имеют место случаи, когда потоки событий, переводящие систему из одного состояния в другое, являются пото- ками с ограниченным последействием, замена которых пуассоновскими пото- ками возможна лишь в качестве первого приближения.
На основании этого возникает необходимость рассмотреть вопрос о том, каким образом учесть последействие потоков так, чтобы процесс функциони- рования систем можно было описать по-прежнему в виде марковского процесса с непрерывным временем и дискретным числом состояний.
Вданном разделе рассматривается простой метод, который в некоторых случаях может быть полезен в ситуациях такого рода. В этом методе использу- ются два свойства потока Эрланга, состоящих в том, что, во-первых, поток Эр- ланга является потоком с ограниченным последействием и, во-вторых, закон распределения промежутка времени между событиями в потоке Эрланга явля- ется композицией показательных законов распределения.
4.1. Потоки Эрланга и их свойства
Потоком Эрланга k-го порядка называется ординарный стационарный по- ток с ограниченным последействием, у которого промежутки времени Т между событиями в потоке являются суммами случайных величин, распределенных по показательному закону с параметром λ.
Поясним это с помощью рис. 7. Обозначим через Е события, соответст- вующие пуассоновскому потоку, и предположим, что они пронумерованы в
60
порядке их появления, начиная с некоторого ис- ходного момента. Пусть Е* - события, определяе- мые следующим образом: Е* наступает в момент появления событий Е с номером, кратным k. То- гда поток, состоящий из последовательности со- бытий Е*, и будет потоком Эрланга k-го порядка.
В частности, на рисунке приведен поток Эрланга при k = 3. Очевидно, при k = 1 имеем исходный пуассоновский поток, для которого промежутки времени Т
между событиями в потоке распределены по закону с плотностью
f (t)= λe−λt , |
(4.1) |
где λ - параметр потока.
Промежуток времени между n-м и n+k-м событиями в потоке Эрланга ра- вен сумме k промежутков времени между событиями в пуассоновском потоке. Следовательно, искомый закон является k-кратной композицией закона (4.1),
плотность распределения его имеет вид
fk (t) = |
λ(λt)k −1 |
e−λt , |
(4.2) |
|
|||
|
(k − 1)! |
|
|
|
где k - порядок потока Эрланга, λ - |
||
|
плотность |
исходного пуассоновского |
|
|
потока. |
|
|
|
|
Закон распределения с плотно- |
|
|
стью (4.2) называется законом Эрланга |
||
|
k-го порядка. |
||
|
|
В качестве примера на рис. 8 |
|
|
приведены законы распределения fk(t) |
||
|
для k = 1, 2, 3, 6, 11, 26 при λ = 1. |
||
|
|
Известно, что поток называется |
|
|
потоком с |
ограниченным последейст- |
вием, если промежутки времени между последовательными событиями пред- ставляют собой независимые случайные величины. Следовательно, потоки Эр- ланга являются потоками с ограниченным последействием, так как промежутки времени Т между событиями, являясь суммами независимых случайных вели- чин, независимы между собой.
Математическое ожидание и дисперсия промежутка времени между со-
бытиями в потоке Эрланга k-го порядка определяются формулами: |
|
|
mk |
= k / λ , |
(4.3) |
Dk |
= k / λ2 . |
(4.4) |
Из этих формул получаем, что для закона Эрланга любого порядка спра- |
||
ведливо соотношение |
= λDk . |
|
mk |
(4.5) |
Плотность потока Эрланга Λk обратна величине математического ожида- ния mk:
61
Λk |
= λ / k , |
|
(4.6) |
||
где λ - параметр показательного закона. |
|
|
|||
Из (4.6), (4.3), (4.4) имеем: |
|
|
|
|
|
mk |
= 1/ Λk , |
|
(4.7) |
||
Dk |
= 1/ kΛ2k . |
(4.8) |
|||
С учетом (4.6) выражение fk(t) через плотность Λk имеет вид: |
|
||||
fk (t) = |
[kΛk ]k t k −1 |
|
e−kΛk t . |
(4.9) |
|
|
|||||
|
|
(k −1)! |
|
|
Законы fk(t) при Λk = 1 для k = 1, 2, 3, 6, 11, 26 показаны на рис. 9.
Из (4.7), (4.8) и рис. 9 видно,
что при постоянной плотности потока Λk математическое ожидание не зави- сит от порядка потока k, а дисперсия с возрастанием k неограниченно убы-
вает, при k → ∞ и Dk → 0.
Таким образом, поток Эрланга обладает ценным свойством, которое состоит в следующем: при неограни- ченном увеличении порядка потока k и при постоянной плотности Λk поток
Эрланга приближается к регулярному потоку с постоянными интервалами вре- мени между событиями, равными 1/Λk, а плотность распределения fk(t) при k → ∞ обращается в δ-функцию в точке t = 1/Λk.
Это свойство потоков Эрланга позволяет при различных k получать прак- тически любую степень последействия потока - от полного отсутствия после- действия (k = 1) до жесткой функциональной связи между моментами появле- ния событий (при k → ∞). Таким образом, порядок потока k может служить как бы мерой последействия, имеющегося в потоке. Заметим, что даже при k → ∞ поток Эрланга остается потоком с ограниченным последействием.
Определим асимметрию Sk закона Эрланга:
|
|
|
Sk |
= μk3 |
|
/ ( |
|
)3 , |
|
|
(4.10) |
||
|
|
|
|
Dk |
|
|
|||||||
где μk3 |
- третий центральный момент распределения fk(t). |
|
|||||||||||
В свою очередь, |
|
|
|
|
|
(D |
|
− m2 )+ 2m3 , |
|
||||
|
μ |
k3 |
= α |
k3 |
− 3m |
k |
k |
(4.11) |
|||||
где αk3 |
|
|
|
|
|
k |
|
k |
|
||||
- третий начальный момент распределения fk(t): |
|
|
|||||||||||
|
|
|
∞ |
|
|
|
|
∞ |
|
|
k −1 |
|
|
|
αk3 |
= òt3 fk (t)dt = òt 3 λ(λt) |
|
e−λt . |
(4.12) |
||||||||
|
|
|
0 |
|
|
|
|
0 |
|
(k −1)! |
|
|
|
Берем интеграл по частям, после чего получаем |
|
|
|||||||||||
|
|
|
αk3 |
= k(k + 1)(k + 2)/ λ3 . |
|
(4.13) |
62
Подставляя полученные выражения в (4.10) и производя несложные пре-
образования, получаем |
|
|
|
|
|
|
|
|
|
Sk = 2 / |
|
|
. |
|
|
|
|
(4.14) |
|
|
k |
|
|
|
|
||||
Для показательного закона (k = 1) Sk = 2. При k → ∞ |
|
||||||||
lim Sk = lim |
|
2 |
|
= 0 . |
(4.15) |
||||
|
|
|
|
||||||
k →∞ |
k →∞ |
|
k |
|
|
|
Таким образом, при увеличении порядка потока k скошенность распреде- ления постепенно исчезает, распределение становится более симметричным. Закон Эрланга любого порядка имеет положительную асимметрию.
Определим эксцесс распределения fk(t):
εxk = [μk4 / ( |
|
)]− 3, |
(4.16) |
Dk |
|||
где μk4 - четвертый центральный момент распределения fk(t): |
|
||
μk4 = αk4 − 4mk αk3 + 6mk2 αk2 − 3mk4 . |
(4.17) |
||
Начальные моменты определим аналогично (4.12): |
|
||
αk4 = k(k + 1)(k + 2)(k + 3)/ λ4 , |
|
||
αk3 = k(k + 1)(k + 2)/ λ3 , |
(4.18) |
αk2 |
= k(k + 1)/ λ2 . |
|
Подставляя полученные выражения в (4.17) и (4.16) и производя неслож- |
||
ные преобразования, получим |
|
|
εxk |
= 6 / k . |
(4.19) |
Для показательного закона (k = 1) εxk = 6. С увеличением k εxk |
уменьша- |
ется и в пределе при k → ∞ εxk → 0 (так как закон Эрланга при k → ∞ асимпто- тически стремится к нормальному закону). Пределы изменения εxk = 6÷0. Сле-
довательно, закон Эрланга любого порядка всегда имеет положительный экс- цесс.
Используя зависимость числовых характеристик и степени последействия потока Эрланга от порядка потока k, рассмотрим способ замены реальных по- токов с ограниченным последействием потоками Эрланга различного порядка.
4.2. Замена реальных потоков потоками Эрланга
Произвольные потоки с ограниченным последействием, встречающиеся на практике, можно заменить потоками Эрланга с теми же математическим ожиданием и дисперсией промежутка времени между событиями в потоке.
Пусть, например, в результате статистической обработки промежутков времени между событиями в произвольном потоке с ограниченным последей-
ствием получены оценки для математического ожидания и дисперсии величины
Т: mc = 2, Dc = 1.
Заменим этот поток потоком Эрланга с теми же характеристиками. Из
(4.3) и (4.4) получаем
63
k = mc2 / Dc ,
откуда k = 4.
Таким образом, произвольный поток с ограниченным последействием с математическим ожиданием промежутка времени между событиями mc = 2 и дисперсией Dc = 1 можно заменить потоком Эрланга 4-го порядка с плотностью l = 2.
Следует заметить, что такая замена возможна при соблюдении условия
Dc ≤ mc2 . |
(4.20) |
Ввиду функциональной зависимости между математическим ожиданием и дисперсией в потоке Эрланга рассмотренная замена возможна не для любых значений математического ожидания mc и дисперсии Dc произвольного потока. Например, при mc = 2, Dc = 1,6 получаем k = 2,5, т.е. дробное значение k. Таким образом, используя лишь рассмотренные потоки Эрланга, не всегда удается ре- альный поток с ограниченным последействием заменить рассмотренными по- токами Эрланга. Однако существует класс потоков, так называемые обобщен- ные потоки Эрланга, с помощью которых можно заменить любой реальный по- ток с ограниченным последействием, с любым математическим ожиданием и дисперсией, если соблюдено условие (4.20).
Обобщенным потоком Эрланга называется поток, у которого промежутки времени Т между событиями являются суммами случайных величин Ti, подчи- няющихся показательному закону распределения с различными параметрами li.
Для обобщенных законов Эрланга введем обозначение f*k(t). Тогда закон
распределения с плотностью
f * |
æ |
k |
ö k |
k |
) |
(4.21) |
k (t) = ç |
Õli ÷åe-lit |
Õ(l j - li |
||||
|
è |
i=1 |
ø i=1 |
j=1 |
|
|
будем называть обобщенным законом Эрланга k-го порядка.
Определим числовые характеристики закона f*k(t) - математическое ожи- дание m*k, дисперсию D*k, асимметрию S*k и эксцесс ε*xk .
В общем случае для обобщенного закона Эрланга k-го порядка f*k(t) с па- раметрами li (i =1, 2, …, k) математическое ожидание
k |
k |
k |
|
m* k = åÕli |
Õli , |
(4.22) |
|
j=1 |
i=1 |
i=1 |
|
|
i¹ j |
|
|
дисперсия |
k |
k |
|
k |
|
||
D* k = åÕl2i |
Õl2i , |
(4.23) |
|
j=1 |
i=1 |
i=1 |
|
|
i¹ j |
|
|
асимметрия
k |
k |
S* k = 2 åÕl3i |
|
j=1 |
i=1 |
|
i¹ j |
эксцесс
æ |
|
|
ö3 |
|
|
ç |
k |
k |
÷ |
, |
(4.24) |
ç |
åÕl2i |
÷ |
|||
ç |
j=1 |
i=1 |
÷ |
|
|
è |
|
i¹ j |
ø |
|
|
64
|
|
|
|
|
|
æ |
|
|
|
ö2 |
|
e* xk |
|
k |
k |
|
ç |
k |
|
k |
÷ |
(4.25) |
|
= 6 åÕl4i |
|
ç |
åÕl2i |
÷ . |
|||||||
|
|
j=1 i=1 |
|
ç |
j=1 i=1 |
÷ |
|
||||
|
|
|
i¹ j |
|
è |
|
i¹ j |
ø |
|
||
Рассмотрим некоторые свойства обобщенных законов Эрланга. Для про- |
|||||||||||
стоты возьмем обобщенный закон Эрланга 2-го порядка |
|
||||||||||
f * 2 (t) = |
|
λ1λ2 |
|
(e-l1t |
- e-l2t ). |
|
(4.26) |
||||
l2 - l1 |
|
||||||||||
|
|
|
|
|
|
|
|
|
|||
Очевидно, при l2 = l1 = l f*2(t) = |
f2(t), где |
f2(t) - закон Эрланга второго |
|||||||||
порядка. |
|
|
|
|
|
|
|
|
|
|
|
При l2 ® ¥ |
|
|
|
|
|
λ2λ1 |
|
(e-l1t |
|
)= l1e-l1t = f1 (t), (4.27) |
|
lim |
f * 2 (t) = lim |
|
|
- e-l2t |
|||||||
|
l2 - l1 |
|
|||||||||
l2 ®¥ |
|
|
l2 ®¥ |
|
|
|
|
||||
|
|
|
|
|
|
|
|
||||
где f1(t) - показательный закон с параметром l1. |
|
f*2(t) ® 0. |
|||||||||
Естественно, при l1 или l2, стремящихся к нулю, |
|||||||||||
При рассмотрении обобщенных законов Эрланга более высокого порядка |
выявляются некоторые дополнительные свойства. Рассмотрим изменение
обобщенного закона Эрланга третьего порядка |
f*3(t) при изменении парамет- |
||||||||||||||
ров l1, l2 и l3: |
|
|
|
|
|
|
|
|
|
|
|
||||
f * 3 |
(t)= l |
l |
|
l |
é |
e-l1t |
|
+ |
|
e-l2t |
|
|
+ |
e-l3t |
ù . |
|
3 ëê |
(l2 - l1 )(l3 - l1 ) |
(l1 - l2 )(l3 - l2 ) |
|
|||||||||||
|
1 |
|
2 |
|
|
|
(l1 - l3 )(l2 - l3 )ûú |
||||||||
|
Очевидно, при l1 = l2 = l3 |
f*3(t) = f3(t). Если l1 ¹ l2, а l3 ® ¥, то |
(4.28) |
||||||||||||
|
|
||||||||||||||
|
|
|
|
|
|
|
|
lim |
f * 3 (t) = f * 2 (t). |
|
|
(4.29) |
|||
|
|
|
|
|
|
|
l3 ®¥ |
|
|
|
|
|
|
||
|
Если же l3 = l2, но l2 ¹ l1, то |
|
f * 3 (t) = f * 3(1) (t), |
|
|
||||||||||
|
|
|
|
|
|
|
|
lim |
|
(4.30) |
|||||
|
|
|
|
|
|
|
l3 ®l2 |
|
|
|
|
|
|
где f*3(1)(t) - обобщенный закон Эрланга 3-го порядка, у которого два параметра из трех равны между собой.
Если для f*3(1)(t) положить l1 = l2, то |
|
|
lim |
f * 3(1) (t) = f3 (t). |
(4.31) |
l1 ®l2 |
|
|
Если же для f*3(1)(t) положить l1 ® ¥, то |
|
|
lim |
f * 3(1) (t) = f2 (t). |
(4.32) |
l1®¥ |
|
|
Примем для обобщенных законов Эрланга с несколькими равными пара- метрами l0 следующие обозначения: f*k(t) - все k параметров li разные; f*k(k-2)(t) - два параметра равны l0, остальные k-2 параметров li разные; f*k(k-3)(t) - три па- раметра равны l0, остальные k-3 параметров li разные; f*k(1)(t) - k-1 параметров равны l0, один параметр l1 отличен от остальных; fk(t) - все параметры равны между собой, т.е. li (i = 1, 2, …, k) равны l0.
65
Используя эти обозначения, все превращения обобщенных законов Эр- ланга при изменении параметров λi можно представить в виде рис. 10.
Переходы слева направо, обозначенные на схеме горизонтальными стрелками, происходят при одном из λi → λ0.
Переходы слева направо, обозначенные на схеме вертикальными стрел- ками, происходят, когда один из параметров λi → ∞, т.е. при понижении поряд- ка законов Эрланга, при этом количество равных параметров λ0 остается преж- ним. Переходы справа налево, обозначенные вертикальными стрелками, проис- ходят, когда один из параметров λ0 → ∞,при этом также получается понижение порядка закона Эрланга.
Из рассмотрения свойств обобщенных законов Эрланга можно сделать важный для практики вывод, что при постоянной плотности потока Эрланга Λ*k, а следовательно, при постоянном математическом ожидании m*k, изменяя параметры λi от λ0 до ∞, можно получить различные значения дисперсии D*k.
При этом наиболее удобным в практическом отношении является обобщенный закон Эрланга f*k(1)(t), у которого все параметры равны λ0, кроме одного λ1. Варьируя эти параметры при постоянном математическом ожидании m*k, мож- но получить различные значения дисперсии D*k.
Используя это свойство, можно реальные потоки с ограниченным после-
действием заменять потоками Эрланга с теми же математическим ожиданием и дисперсией промежутка времени между событиями в потоке. При этом, однако,
необходимо соблюдать условие
m2 |
k ≤ D ≤ m2 . |
(4.33) |
k |
k k |
|
66
Из выражений (4.22) и (4.23) нетрудно получить общее выражение для математического ожидания и дисперсии закона f*k(1)(t):
m* k (1) = |
(k −1)λ1 + λ0 |
, |
(4.34) |
|
|
||||
|
λ1λ0 |
|
||
D* k (1) = |
(k −1)λ21 + λ20 |
. |
(4.35) |
|
|
||||
|
λ21λ20 |
|
Тогда порядок замены реального потока с ограниченным последействием с математическим ожиданием mc и дисперсией Dc обобщенным потоком Эрлан- га f*k(1)(t) с теми же характеристиками сводится к следующему.
Определяется порядок потока Эрланга k = mc2 Dc . Дробное значение k
округляется в большую сторону. |
|
|
|
|
|
|
|
|
||||
Из выражения (4.34) имеем |
|
|
|
|
|
|
|
|
||||
|
|
|
λ1 = λ0 |
/ (1− k +λ0 mc ). |
|
|
|
|
|
(4.36) |
||
Подставляя (4.36) в (4.35) и производя несложные преобразования, полу- |
||||||||||||
чим |
|
(mc2 − Dc )λ20 − 2(1− k)mc λ0 + k(k −1) = 0, |
|
|
|
|
||||||
откуда |
|
|
|
|
|
|||||||
|
|
m0 (k −1)± |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
λ01,2 = |
(k −1)2 mc2 − k(k −1)(mc2 |
− Dc |
) |
. |
(4.37) |
|||||||
|
|
(mc2 − Dc |
) |
|
и λ1 |
|||||||
Подставляя λ0 |
и λ0 |
2 |
в (4.36), получим два значения λ1 |
. Таким об- |
||||||||
1 |
|
|
|
|
|
1 |
2 |
|
||||
разом, для одних и тех же значений mc и Dc получаем закон |
f*k(1)(t) с двумя раз- |
|||||||||||
личными сочетаниями параметров λ1 |
и λ0: ( λ1 , |
λ0 ), ( λ1 |
, λ0 |
2 |
|
), |
при этом |
|||||
|
|
|
|
|
1 |
1 |
2 |
|
|
|
|
m*k = mc , D*k = Dc.
Метод, с помощью которого получено распределение Эрланга, подсказы- вает способ моделирования процессов с ограниченным последействием, при котором потоки, переводящие систему из одного состояния в другое, являются потоками Эрланга (рис. 7).
Предположим для конкретности, что события Е обозначают процесс пе- реходов системы из состояния в состояние, число состояний системы равно k и процесс протекает следующим образом: 1) в каждый момент времени система может находиться только в одном из k состояний; 2) система последовательно проходит состояния 1, 2, …, k. Время пребывания системы в каждом состоянии распределено по показательному закону с параметром λ = kΛk.
Длительность пребывания системы во всех k состояниях соответствует промежутку времени между событиями Е*, эти события и образуют поток Эр- ланга.
Такое разбиение каждого состояния системы на k состояний позволяет продемонстрировать важный факт. Пусть n*(t) и n(t) - соответственно числа по- явления событий Е* и Е за время от 0 до t. Пуассоновский процесс n(t) является марковским, процесс n*(t), напротив, не марковский: вероятноять того, что n*(t)dt = j при условии n*(t) = i, зависит от момента появления последнего со-
67