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

Информационные системы в экономике

Н.И. Головко,

кандидат технических наук, доцент кафедры математики и моделирования ДВГАЭУ;

В.В. Катрахов,

доктор физико-математических наук, профессор кафедры математики и моделирования ДВГАЭУ;

Н.А. Филинова,

аспирант кафедры математики и моделирования ДВГАЭУ

МАРКОВСКИЕ СИСТЕМЫ ОБСЛУЖИВАНИЯ

С БЕСКОНЕЧНЫМ НАКОПИТЕЛЕМ ПРИ СКАЧКООБРАЗНОЙ ИНТЕНСИВНОСТИ ВХОДНОГО ПОТОКА

Рассматриваются марковские системы массового обслуживания (СМО) типа М/М/1 с бесконечным накопителем, экспоненциальным обслуживанием, с дважды стохастическим входным пуассоновским потоком заявок со скачкообразной интенсивностью. Приводятся стационарное распределение и моменты числа заявок в СМО. Стационарные характеристики числа заявок используются при проектировании и эксплуатации локальных вычислительных сетей. Показана методика решения бесконечной системы разностно-интегральных уравнений с вырожденным ядром относительно вероятностных характеристик СМО. Демонстрируются результаты численного анализа.

В литературе достаточно хорошо изучены системы обслуживания (СМО) с дважды стохастическим (ДС) пуассоновским потоком (1111) заявок, интенсивность которого представляет собой марковскую или полумарковскую цепь с конечным множеством состояний [4,5]. Меньше исследован случай, когда интенсивность ДС 1111 СМО представляет марковскую цепь с бесконечным числом состояний или марковский процесс с непрерывным пространством состояний. Для СМО с входным ДС 1111, интенсивность которого представляет собой чисто разрывный (рус. терминология) или скачкообразный (англ. терминология) случайный процесс, рассматриваются приближенные методы анализа [1,2] и матричный анализ систем массового обслуживания с конечным накопителем [3,6]. В данной работе для СМО с бесконечным накопителем и скачкообразной интенсивностью входного потока предлагается анализ распределения числа заявок с применением метода производящих функций.

В настоящей работе рассматриваются СМО типа Ы / Ы /1 с одним прибором, бесконечным накопителем, экспоненциальным обслуживанием с параметром / . На вход СМО поступает ДС 1111, интенсивность ко-

торого X(t) представляет собой скачкообразный процесс, изменяющийся на отрезке [а, b]. Процесс X(t) в течение случайного интервала Т сохраняет постоянное значение, затем мгновенно изменяет свое значение на новое и т. д. Случайная величина Т распределена по экспоненциальному закону с параметром а . Интенсивность X(t) имеет в точках разрыва t0 справа условную плотность распределения

p(x/y) = P{x < X(t0 + 0)< x + dx / X(t0 - 0) = y}/ dx.

В настоящей работе приводится анализ характеристик рассматриваемой СМО в случае, когда условная плотность p(x/y) совпадает с плотностью p(x) = P{x < X(t0 + 0) < x + dx}/ dx.

Введем стационарную плотность f (x) = P{x < X < x + dx}/dx, где через X обозначен процесс X(t) в стационарном режиме. Можно показать, что f (x ) = p(x) [2].

Обозначим через v(t) число заявок в СМО в момент t, а через Pk (t, x) нестационарные характеристики числа заявок

Pk (t, x) = P{y(t) = k, x < X(t) < x + dx}/ dx , где k > 0 . Обозначим через v число заявок в СМО в стационарном режиме, а через pk (x) = P{v = k, x < X < x + dx}/ dx соответствующие стационарные характеристики числа заявок. В частности, в качестве pk (x) можно рассматривать пределы pk (x) = lim Pk (t, x) при t ^ <x>, которые могут существовать при некоторых ограничениях на входные параметры (например, при выполнении условия отсутствия перегрузок в СМО: b < ¡и). Заметим, что интегралы

£Pk (x)dx = qk , k > 0,

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

Метод производящих функций

Стационарные характеристики числа заявок удовлетворяют бесконечной системе разностно-интегральных уравнений [2]

- (х + а) р0 (х) + црх (х) + а<р(х) Гр0 (у ^у = 0,

xPk-1(х) -(х + М + а)Pk(х) + аР(х)]Рк (уУу = 0к > 1.

Введем вспомогательные производящие функции R

R(x, 2) = £ рк (хУ , г(И) = £ чИ, И < 1, 2 е С , к>0 к >0 где множество О = \и : |и| < 1} является областью сходимости данных функциональных рядов. Заметим, что

Г

Получим уравнение для производящих функций. Умножим первое уравнение системы (1) на Z, остальные на zk+l, соответственно, затем сложим их и выделим производящие функции

R

Обозначим L

R

L

Корни уравнения L(x, z) = 0 находятся по формулам zj = x + u + a - -\J(x + f + a)2 - 4xf |/2 x, z2 = x + f + a + yj(x + f + a)2 - 4xf |/ 2x.

Функции zj (x) и z2 (x) — вещественные, так как выражение под корнем положительное. Действительно,

(x + f + a)2 - 4xf = (x - f)2 + a2 + 2ax + 2af > 0 .

Легко увидеть, что 0 < zj (x) < 1, z2 (x) > 1 при x > 0, причем zj (x ) и z2 (x) монотонно убывают, так как zj(x)< 0 и z2 (x)< 0. Кроме того, имеют место следующие пределы

lim zj (x) = f(f + a)-1, lim zj (x)= 0, lim z2 (x) = w , lim z2 (x) = 1.

Уравнение (4) можно рассматривать как неоднородное интегральное уравнение Фредгольма 2-го рода с вырожденным ядром относительно функции R(x, z), где z — параметр. Знаменатель L(x, z) этого уравнения обращается в нуль при |z| < 1. Обозначим Q = |z| < 1, z i \a, ß]|, a = zj (b), ß = zj (а). Выразим из уравнения (4) функцию r (z) через функцию p0 (x). Для этого проинтегрируем левую и правую части (4) по x е [а, b] при z ей и, воспользовавшись равенством (2), получим

r

1 + az f p(x \ dx = f(1 - z) f

Ja L(x, z) Ja

L

P0

dx .

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

, ч

р(и,г)* [г - г (и)]-14и г2г где g(u, г)= /ир0 (и )и - г2 (и )]-1, h(u, г)=(/-иг)<р(и)и ч[г - г2 (и)]-1.

Следует отметить, что при г = г1 (х)е(о, /(/ + а) 1) знаменатель в уравнении (4) обращается в нуль, а так как ^(х, г) является целой функцией, то при г = г1(х) и числитель в (4) равен нулю, т.е.

МР0

Получили еще одно уравнение, связывающее г (и ) и р0 (х) . К сожалению, прямая подстановка функции г (и ) из формулы (5) в уравнение (6), или наоборот, невозможна, так как функция г (и ) в (5) не определена при 2 = и1 (х) . Однако это неудобство можно преодолеть, если в интегралах в числителе и знаменателе дроби (5) выделить неопределенности одинакового вида.

Устранение неопределенности

Сделаем подстановку 2 = 21(у) в интегралах в формуле (5), предварительно преобразовав данные интегралы. Числитель и знаменатель дроби (5) имеют одинаковый вид, поэтому рассмотрим, например, числитель. Аналогичные результаты будут справедливы и для знаменателя. Выполним в числителе замену переменных

у = 21

Обозначим обратную функцию через и = и (у ) = ¡¡(у). Можно показать, что

п(у )=М - а.

у 1 - у

Функция ¡¡(у) непрерывна и непрерывно дифференцируема по у е (а, р ). Сделав замену переменных, получим

Г

а и - у

где у/(у, и ) = g (¡(у), и ¡(у). Преобразуем выражение (8) к виду

Г1

а у - 2 •'а у - 2

где И(2,2)= МР0 (П(2)М2)/[П(и)(и - 22 (П(и)))], а под функциями Р0 (П(и)),

22 (¡(и)) понимается аналитическое продолжение функций р0 (х), и2 (х) вещественного аргумента, определенное в комплексной области О. В дальнейшем в результате предельного перехода при 2 ^ q е (а, р) предполагается возврат к функциям вещественного аргумента р0 (д), и2 (д).

Вычисление интегралов методом перевала

Вычислим интегралы в выражении (9).

Первый интеграл в (9) найдем методом перевала. При стремлении 2 ^ q е (а, р) будем рассматривать перевал снизу: 2 = q - ¡е , е ^ +0 ; перевал сверху: 2 = q + ¡е , е ^ +0 ; перевал слева: 2 = а - е, е ^ +0, перевал справа: 2 = р + е, е ^ +0. Заметим, что при любом способе устремления 2 ^ q е (а,р) относительно р0(х) получается одно и то же уравнение. При 2 ^ а и 2 ^ р относительно р0 (х) получаются тождества.

Рассмотрим метод перевала снизу. Пусть z = q - is , s > 0 , q е (a,ß), тогда

rß dy rß y - q rß s

fß У - q dy - i Г

y - z a (y - q) + s2 a (y - q) + s2

1 2

= 1ln

2

(ß -q)2 + s2]- jln[(a- q)2 + s2]-i

ß - q a - q arctg--arctg-

Откуда следует

lim f—— = lim [_—— = ln(ß -q)-ln(q-a)-in .

z^q a d - z z=q-isJa y - z

Рассмотрим второй интеграл в формуле (9), найдем предел при z ^ q и возвращаясь к переменной u , с использованием замены (7), получим

гМмЬИм) л, - £ g(u q)- g (n(q), q )n'(q )z1(u L,

у - ч •>а ч - г

Итак, при ч = г1

Г1 (г (х)) = ^^ [1п(Д - г (х)) - 1п(г (х) - а)- 1х]+

+ Г6 g

Заметим, что при и = х в последнем интеграле знаменатель г1 (и)- г1(х) обращается в нуль, но нуль знаменателя компенсируется нулем числителя, так что значение подынтегральной функции в точке и = х вычисляется по правилу Лопиталя, причем после применения правила Лопиталя знаменатель (и) Ф 0, У и е [а, Ь].

Выражение для г2 (г1 (х)) получается путем формальной замены функции g на h в выражении (10). При этом (по аналогии с предыдущим случаем) в области D вводится аналитическое продолжение р(р(г)) функции вещественного аргумента р(х).

Вывод уравнения относительно р0

Из уравнений

Ро (х )к (х) = ар(х) Г61 Р0 (и )г(х) - Р0 (х )г(и) 1 . 4и , 0 ь [ и[г1(х)-г2 (и)] х[г1 (х)-г2 (х)]] г1(х)[г1 (и)-г1 (х)]'

где

R

zj

s

5(х) { 21 (х)21'(х) ^ 21 (х)) хИ'(х)[21(хс)- 22 (х)]}

[1п

Множитель при мнимой единице в выражении (11) можно преобразовать к виду

—/ ч ,/ чТр

х21 (х )2Дх )[21(х)- 22 (х)] Учитывая, что и1 (х) корень уравнения L(x, 2), выражение в фигурных скобках в строке (14) тождественно равно нулю, следовательно, комплексная составляющая в равенстве (11) становится равной нулю. Кроме того, составляющая 5 (х) в (11) тождественно равна нулю при х е (а, Ь). Действительно, преобразуя выражение в фигурных скобках в формуле (13), имеем

1 -21 и(х 2 )- аР(х) = {х212 -(х + М +а)и1 + Мр(х) = 0 , п\х,21> ,[ - ]- ,[ - ] -0,

2121 х^[21 22\ х2121[21 2 2 \ где 21 = 21 (х) , 22 = 22 (х) .

Таким образом, относительно функции р0 (х) получено уравнение

Ро ( ) <().[{и[21(х)-22(и)] х[р(х)-22(х)]^[ 2;(х)[и 1 (и)-21(х)] (15) Заметим, что относительно р0 (х) получается такое же уравнение, если в формуле (9) вычислять интегралы методом перевала сверху.

Уравнение (15) представляет собой однородное интегральное уравнение Фредгольма 2-го рода. Однако задача нахождения р0 (х) — неоднородная задача, так как известен интеграл от р0 (х) по х е [а, Ь]

[р0

^ ¿а М

Условие (16) получено из уравнения (3), если проинтегрировать (3) по х е [а, Ь], сократить на (1 - 2) и в полученное равенство

Г

^а За

подставить и = 1. Из равенства (17) следует условие (16) с учетом того, что

R(x,l) = X рк (х) = ^х), ]/(х)(х = 1, f (х ) = р(х).

к>0 а

Следует отметить, что интегральное однородное уравнение (15) имеет непрерывный подынтегральный оператор при х > 0 . Действительно, при и = х нуль знаменателя компенсируется нулем числителя, и значение подынтегральной функции вычисляется по правилу Лопиталя. Кроме того, подынтегральный оператор в (15) не имеет особенностей при и ^ 0, х ^ 0 , так как

Нт и[и1 (х) - и2 (и)] = Нт ии1 (х) - Нт ии2 (и) = -2(м + а);

lim x[zj (x) - z2 (x)] = lim xzj (x) - lim xz2 (x) = -2(и + а).

Аналогичный анализ, как и для подынтегрального оператора в уравнении (15), показывает, что функция ^(x) в (12) является конечной и непрерывной по x е [a, b], в том числе и для значения a = 0 .

Таким образом, получено, что p0 (x) удовлетворяет неоднородной задаче (15), (16), условия существования и единственности которой определяют условия существования и единственности стационарного режима. Через p0 (x) выражается r (z), как показано в (6). С помощью r (z) можно находить различные моменты числа заявок. Например, математическое ожидание числа заявок в стационарном режиме равно Mv = r '(1), дисперсия Dv = r"(1)+r'(1)—[r'(1)]2. Вычисляя математическое ожидание числа заявок, получим

Mv =-

аиЧ0

ац (1 - q0) + Г (и - x)2 p(x)dx + ¡и \ xp0 (x)dx - и Ja Ja

Выражение для дисперсии не приводится ввиду своей громоздко-

сти.

Численный анализ

Методом полиномиального приближения была решена неоднородная задача (15), (16) и найдена неизвестная функция р0 (х), через которую выражается математическое ожидание Mv числа заявок в стационарном режиме. Численный анализ значений функции р0 (х) и величины Mv проводился с целью наблюдения за установлением стационарного режима в СМО в зависимости от значений входных параметров: а,Ь,а,м. В качестве плотности р(х) рассматривалась плотность равномерного распределения р(х) = 1/(Ь - а).

Расчет стационарной характеристики р0 (х) и математического ожидания Mv проводился по различным сечениям следующих входных данных: а = 1, Ь = 2, а = 1, м = 2,2 . Все численные результаты получены в предположении, что выполняется условие отсутствия перегрузок: Ь < м . Зависимость функции р0 (х) от изменения интенсивности обслуживания м показана на рис.1.

p0

1

0,5 0

1,2 1,4 1,6 1,8

U = 9 ¡=3

U = 2,2

Рис. 1. Графики функции p0

1

2

x

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

Рассмотрим зависимость математического ожидания Му от / (рис.2) и от а (рис.3).

Рис. 2. График зависимости среднего числа заявок Му от интенсивности обслуживания /и

Рис. 3. График зависимости среднего числа заявок Му от параметра а

С увеличением / среднее число заявок стремится к нулю (рис.2), так как с увеличением интенсивности обслуживания заявки быстрее обслуживаются и покидают СМО. Увеличение параметра а (рис.3) незначительно влияет на уменьшение значений Му .

Рассмотрим зависимость Му от а (рис.4) и от Ь (рис.5).

10 0

0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 а

10 0

0,4 0,6 0,8 1 1,2 1,4 1,6 1,8 а

Рис. 4. График зависимости среднего Рис. 5. График зависимости среднего числа заявок Му от параметра а числа заявок Му от параметра Ь

При увеличении а или Ь среднее число заявок увеличивается. Это объясняется тем, что с увеличением а или Ь возрастает среднее значение интенсивности входного потока Л =(а + Ь)/2, и, в соответствии с приближенной формулой Литтла Му « Л / / , среднее число заявок в СМО увеличивается.

Таким образом, приведенные численные результаты получили теоретическое обоснование.

Литература

1. Головко Н.И., Коротаев И.А. Время задержки сообщения в узле сети при переменной интенсивности входящего потока // Автоматика и вычислительная техника. 1989. №2. С.36-39.

2. Головко Н.И., Коротаев И.А. Системы массового обслуживания со случайно изменяющейся интенсивностью входящего потока // Автоматика и телемеханика. 1990. №7. С.80-86.

3. Головко Н.И., Катрахов В.В, Филинова Н.А. Матричный анализ систем массового обслуживания со скачкообразной интенсивностью входного потока // Вестник ДВГАЭУ. №10. 1999.

4. Горцев А.М., Назаров А.А., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. Томск: Изд-во Томского ун-та, 1978.

5. Дудин А.Н. Об обслуживающей системе с переменным режимом работы // Автоматика и вычислительная техника. 1985. №2. С.27-29.

6. Филинова Н.А. Стационарное распределение числа заявок в системах обслуживания с конечным накопителем при скачкообразной интенсивности входного потока // 2-я Дальневосточная конференция студентов и аспирантов по математическому моделированию. Тез. докл. Владивосток. Изд-во "Дальнаука" ДВО РАН. 1998. С.31.