Автоматика и телемеханика, Л- 9, 2007
Системы массового обслуживания
РАС Б 02.50.Ga
© 2007 г. А.И. ЗЕЙФМАН, д-р физ.-мат. наук (Вологодский государственный педагогический университет и ВНКЦ ЦЭМИ РАН),
Я.А. САТИН
(Вологодский государственный педагогический университет)
СРЕДНИЕ ХАРАКТЕРИСТИКИ МАРКОВСКИХ СИСТЕМ ОБСЛУЖИВАНИЯ1
Рассматриваются системы массового обслуживания, описываемые нестационарными процессами рождения и гибели с иптепсивпостями, близкими к периодическим. Исследуются вопросы, связанные с существованием и построением предельных средних характеристик. Рассмотрены некоторые примеры построения средних для конкретных систем обслуживания.
1. Введение
Марковские модели теории массового обслуживания, описываемые процессами рождения и гибели (ПРГ). исследуются и применяются очень давно (см.. например. [1. 2]). При этом создание новых методов исследования ПРГ и расширение круга решаемых задач вызвали появление целого ряда новых работ [3 11].
Более реалистические модели массового обслуживания, описываемые нестационарными марковскими цепями, активно изучаются начиная с пионерских работ Б.В. Гнеденко [12. 13]. и в последующих работах [14 18]. Построение предельного режима и нахождение явных формул для вероятностей состояний таких моделей, как правило, невозможно, поэтому, естественно, основной интерес связан с вопросами аппроксимации характеристик таких систем [19 22].
Интерес к изучению нестационарных марковских моделей систем обслуживания возрастает в последние годы в связи с появлением новых методов исследования (например. [23 27]).
Две важные характеристики предельное среднее и двойное среднее введены и изучены для процессов с периодическими иптепсивпостями в [27].
В настоящей статье изучается классическая система массового обслуживания (СМО) Мп(Ь)/Мп^)/Б с близкими к периодическим иптепсивпостями поступления и обслуживания требований, получены оценки средних, указана методика их приближенного вычисления и рассмотрены несколько примеров. Работа расширенный и дополненный вариант предварительного сообщения [28].
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (грант № 06-01-00111).
2. Основные понятия
Пусть X (Ь), Ь ^ 0, - "вспомогательный" неоднородный ПРГ с пространством состояний Е = {0,1,...}, интенсивности рождения Хп (Ь), Ь ^ 0, и гибели лп (Ь), Ь ^ 0. п € Е, которого являются периодическими функциями от времени Ь с периодом, равным единице. Будем предполагать, что для вспомогательного процесса выполняются следующие условия (стандартные для ситуации с переменными интенсивностями):
(1) Хп (Ь) = Vпа (Ь), Лп (Ь)= ПпЬ (Ь), Ь > 0, п € Е,
(2) по = 0, 0 < Vn < Ь < ж, 0 < Пп+1 < М < ж, п € Е.
Пусть а (Ь) и Ь (Ь) неотрицательны, 1-периодичны и интегрируемы на [0,1]. Более того, для получения более простых оценок предполагается, что для всех Ь € [0,1]
(3) а (Ь) < а и Ь (Ь) < Ь.
Рассмотрим теперь основной ("возмущенный") ПРГ X* (Ь), Ь ^ 0, с тем же пространством состояний Е и интенсивностями рождения Хп (Ь), Ь ^ 0, и гибели лп (Ь), Ь ^ 0 п € Е, для которого выполнены аналогичные стандартные условия, а вместо 1-периодичности предполагается, что
(4) Х*п(Ь) - Хп(Ь)= Хп(Ь), л*пЬ - Лп(Ь)= Лп(Ь),
где "возмущения" интенсивностей малы: |Хп(Ь)| ^ е, \лп(Ь)\ ^ £ при всех Ь ^ 0 и п€Е
Напомним определения предельного среднего и двойного среднего из [27]. А именно, будем считать, что ПРГ X(Ь) имеет предельное среднее ф(Ь), если
Иш \Е {X(Ь) \Х(0) = к }-ф(Ь)\ =0
ь—
для любого к € Е. Здесь Е {X(Ь) X(0) = к } - среднее для процесса в момент времени Ь при условии, что X(0) = к.
Двойным средним для X(Ь) называется предел
ь
Е = Иш 1 [ Е {X(и) X(0) = к } 3,и,
ь—ж Ь ]
о
к
3. Построение и оценка предельных средних
Как и в предыдущих работах авторов, предполагается, что векторы вероятностей состояний рассматриваемых процессов описываются соответствующими прямыми системами Колмогорова (см. (П.1) и (П.2)).
Разработанный нами ранее (см., например, [17, 18]) метод исследования состоит из нескольких этапов: вместо исходной системы дифференциальных уравнений рассматривается "приведенная" (с исключенным нулевым состоянием): затем с помощью некоторой специальной перенормировки матрица новой системы приводится
к наиболее удобному виду: наконец, с помощью логарифмической нормы, введенной в [29] и изученной в [30]. оценивается скорость сходимости.
Для выполнения необходимых перенормировок ключевым шагом является построение вспомогательной "перенормирующей' последовательности, являющейся некоторым аналогом функции Ляпунова и не имеющей вероятностного смысла. Подробно вопросы, связанные с построением таких последовательностей, а также изучение их свойств в различных ситуациях рассмотрены в [31].
А именно, пусть имеется некоторая последовательность положительных чисел 1 = d-i = do ^ di ^ ... Положим
(5) ак (t) = Хк (t)+pk+i (t) - ^Ak+i (t) - dhT1 ^ (t), к > 0,
dk dk
и введем некоторые вспомогательные величины:
i
Г = sup (2 + + , a (t) = inf ak (t) , a* = f a(t) dt,
к \ dk dk J k J
0
k-1
} £ di
(6) Mo = sup a(u) du, M = eMo+a", W = inf .
\t-s\<1J k к
Теорема 1. Пусть существует последовательность такая, что а* > 0,
М ¿к- 1 > О о Г < то и а* — Гб > 0. Тогда вспомогательный ПРГ X(Ь) име-к>1 к
ет I-периодическое предельное среднее ф(Ь), причем для любого начального условия X*(0) = к и всех Ь > 0 справедлива оценка
(7) \Е {X *(Ь) \Х *(0) = к }-ф(Ь)\ <
< M (V^W ^ + f Л + ^ (l +
W \ \ a* ^ 7 a* - Ге V a
Теорема 2. Пусть выполнены условия теоремы 1. Тогда ПРГ X*(Ь) имеет предельное среднее ф*(Ь), причем выполняется неравенство
(8) ПЫ \ф(Ь) - ф*(Ь)\ , (1 +
' (а* - Гб) V а*
Замечание 1. Отметим, что в отличие от случая, когда интенсивности ПРГ 1-периодичны, предельное среднее ф* (Ь) для ПРГ X*(Ь) не обязано быть периодическим. а двойное среднее может и не существовать. Однако некоторый более слабый аналог двойного среднего может быть оценен и в этой ситуации.
Введем обозначения (верхнее и нижнее средние) для ПРГ X*(Ь): г
Е* = Пт 1 [ Е {X*(и) X*(0) = к } ¿и, Ь ]
о
г
*1
E* = lim 1 / E {X*(u) \X*(0) = к } du. t—t J
0
Заметим, что двойное среднее Е для ПРГ с 1-периодическими интенсивностя-
1
ми находится, как среднее по периоду от предельного среднего: Е = J ф(Ь) сИ. Из
о
теоремы 2 получаем тогда следствие 1.
Следствие 1. Пусть выполнены условия теоремы 1. Тогда ПРГ X*(Ь) имеет верхнее и нижнее средние, причем. выполняется неравенство
г- Ме Л ГМа^\ т=*
(9) Е " щО-Т) + ^ Е* < Е <
< Е + ,Ме ч (1 + ™^
Щ (а* - Ге) V а*
Рассмотрим теперь вопросы, связанные с построением предельного, верхнего и нижнего средних для ПРГ X*(Ь). Введем некоторые вспомогательные понятия. Пусть XN(Ь), Ь > 0 - "усеченный" ПРГ с пространством состояний ЕN = {0,1, 2,... . ..,Ы} и 1-периодическими интенсивностями рождения Хп(Ь), п € EN-1, и гибели цп(Ь), п € Е^ ^^ ^^^^^^^^ интенсивностей AN(Ь)). Нижним индексом N будем обозначать соответствующие характеристики этого процесса. Положим
(10) WN = Ы
к
dN-1+г
i=0
к^0 N + к
Рассмотрим приближенное вычисление Е {X* (Ь) \Х*(0) = к }, которое позволит вычислить и предельное среднее ф*(Ь).
Теорема 3. Пусть выполнены условия теоремы 1. Тогда при любых Ы,к и всех Ь > 0 выполняется неравенство
(И) \Е ^*(Ь) X *(0) = к } -Е {XN (Ь) X (0) =0 }\ <
М2а^0 _аЧ ?>tMav0 (Ьа + МЬ) < -е +-+
^ Ща* WN а*
+М (<™( +§ *)+^
Следующее утверждение позволяет приближенно вычислять верхнее и нижнее средние для X*(Ь).
Теорема 4. Пусть выполнены условия теоремы 1. Тогда при любом N и всех Ь > 0 выполняется неравенство
4+1
Е* - I Е {XN (и) X(0)=0 } Си < г
< Ме Л ГМа^0 N М2а^0 _аЧ 3(Ь + 1)Ма^0 (Ьа + МЬ)
"< \ Л / / -А- тч N I + -А- I + \ Л / -1- е
(12)
Щ (а* - Ге)\ а* ) Ща* WNа*
Такая же оценка справедлива и для Е*.
Замечание 2. Аналогичные результаты легко могут быть получены для систем обслуживания, описываемых
1) процессами рождения и гибели, интенсивности которых близки к периодическим с произвольным периодом T = 1;
2) процессами с конечным числом состояний (в частности, это модели типа M (t)/M (t)/K/L).
4. Примеры
Рассмотрим несколько примеров вычисления средних для конкретных CMÜ.
Пример 1. Число требований в системе обслуживания M(t)/M(t)/1.
Пусть a*(t) = 1+0,5 sin 2nt+10-9 sin t2, a b*(t) = 6 +cos 4nt+10-9 cos yfi. Полагая a(t) = 1 + 0,5 sin 2nt, b(t) = 6 + cos 4nt, имеем e = 10-9 и кроме тoro vn = rjn = 1 (n > 1). Далее L = M = 1, a = 1,5 b = 7. Полагая dk = 2k, k > 0, получаем
1 t a (t) = 2 - 0,5 sin 2nt + 0,5cos2nt, a* = f a(t) dt = 2, M0 = sup f a(u) du < 3.
0
|t-s|<1 s
W
k-i
E di • f i=0 ini ■
k
^ 2W-i+i
, 1 и WN = inf i——-— „т
k N k^o N + k N
При t = 11 N = 46 получаем рис. 1.
Па рис. 1 приведена ф(Ь), t е [11,12], с точностью 10-5. Значит, этот же рисунок дает ф*(t) при больших t с точностью 10-4.
-* л
E « 0,2023 с точностью 10-4.
Пример 2. Число требований в системе обслуживания M(t)/M(t)/2.
Пусть a*(t) = 1 +sin 2nt + 10-10 sint2, a b*(t) = 4 + 2 cos 2nt + 10-10 cos лД. Полагая a(t) = 1 + sin2nt, b(t) =4 + 2cos2nt, имеем e = 10-10, и vn = n1 = 1 (n ^ 1) и nn = 2 (n > 2). Далее L =1 M = 2, a = 2 и b = 6 Полагая dk = 2k, k > 0, получаем
1 t 1 a (t) = 3 — sin2nt + 2cos2nt, a* = / a(t) dt = 3 M0 = sup / a(u) du = 3 + —,
0 |t-s|<1 s
k-1 k £ di k 2N-1+i
2
N-1
2n'
M = eMo+°* = e6+27 < 500 W = inf ■
0
2
N1
, = 1 и = Ш ——-— — .
к к * к^о N + к N
При Ь = 9, N = 41 получаем рис. 2.
Па рис. 2 приведена ф(Ь), Ь € [9,10], с точностью 10-5. Значит, этот же рисунок
дает ф*(Ь) при больших Ь с точностью 10-4.
—* /1 Е « 0,2945 с точностью 10 .
Ф(г)
0,30'
0,28
0,26
0,24
0,22
0,20
0,18
0,16
0,14
0,12
0,10
11,0 11,2 11,4 11,6 11,: Рис. 1.
Ф(0 0,50 0,46 0,42 0,38 0,34 0,30 0,26 0,22 0,18 0,14 0,10
/ \
/ \
/ \
/ V
/
/ \
ч
9,0 9,2 9,4 9,6 9,8
Рис. 2.
5
t
t
ф(г) 0,50 0,46 0,42 0,38 0,34 0,30 0,26 0,22 0,18 0,14 0,10 25,0
25,2 25,4 25,6 25,:
Рис. 3.
Пример 3. Число требований в системе обслужив
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.