Асимптотический анализ неоднородной системы массового обслуживания M|M| в марковской случайной среде
Рассматривается неоднородная система массового обслуживания с неограниченным числом обслуживающих приборов, функционирующая в условиях изменяющейся внешней среды. На вход СМО поступает пуассоновский поток, интенсивность потока и дисциплина обслуживания поступающей заявки определяются состоянием внешней среды и имеют экспоненциальное распределение с соответствующими параметрами, не меняющими свои значения до окончания обслуживания. Решается задача исследования многомерного случайного процесса - числа заявок, обслуживаемых с разной интенсивностью в системе, методом асимптотического анализа. Доказано, что распределение вероятностей рассматриваемого процесса при условии эквивалентно растущего времени обслуживания является многомерным гауссовским.
Asimptotic analysis of heterogeneous queuing system M|M| in a Markov random environment.pdf Большинство современных технических систем, в том числе систем передачи информации и телекоммуникационных систем, функционирует в рамках изменяющейся внешней среды, причем ее изменения носят как регулярный, так и случайный характер. Влияние этих факторов на систему представляет значительный интерес в условиях быстро развивающихся технических возможностей современного мира. Поэтому исследование систем, работающих в случайной среде, является частью глобальной задачи исследования устойчивости систем к внешним воздействиям и представляется актуальным и интересным как в теоретическом, так и в прикладном плане. Классические модели СМО, активно исследовавшиеся в середине прошлого столетия, не учитывали возможностей изменения параметров систем во времени, что существенно ограничивало область их применения. Со временем появлялись качественно новые системы управления и связи, возникала необходимость в более адекватном описании случайных процессов, имеющих место в этих системах. Возникновение в последние несколько десятилетий новых практических задач, связанных с появлением систем гибкого автоматического производства, в которых возможны отключение, переподключение и переналадка оборудования, систем управления запасами и экономических систем, информационно-вычислительных сетей и сетей связи, дало существенный толчок к развитию исследований систем с изменяемыми параметрами [1, 2]. Такие системы в теории массового обслуживания называются системами массового обслуживания, функционирующими в случайной среде [3]. Эти СМО более адекватно по сравнению с классическими системами отображают реальные процессы, связанные с изменяющейся во времени внешней случайной средой и реакцией самой системы на такие изменения. Одной из первых работ, посвященных исследованию систем массового обслуживания, функционирующих в случайной среде, была работа [4], в которой рассмотрена однолинейная система в предположении, что среда может находиться только в двух состояниях. Эта система была исследована также в работе [5], а затем обобщена на случай произвольного конечного числа состояний внешней среды [6]. Также имеется много работ, посвященных исследованию бесконечнолинейных систем как в марковских [7-9], так и полумарковских [10-12] случайных средах. В разных работах рассмотрены различные варианты реакции заявок на переход среды в новое состояние. Например, в работе [13] представлен случай, при котором в момент смены состояния среды все заявки немедленно покидают систему. В работе [14] исследован вариант, при котором в момент перехода среды в новое состояние заявки, имеющиеся в системе, переходят на соответствующий новый режим обслуживания. В этой же работе рассматривается случай, предполагающий, что режим обслуживания заявок не меняется до тех пор, пока они не покинут систему. Исследование систем с непуассоновскими входящими потоками [15] требует применения специальных методов. Например, в работе [16] получены числовые характеристики изучаемого процесса с помощью метода моментов. Для более детального исследования применяются асимптотические методы [17] при различных условиях. В настоящей работе рассматривается неоднородная система массового обслуживания M|M| in a random environment Обозначим ii(t) - число заявок, обслуживаемых с интенсивностью цг. Ставится задача исследования многомерного случайного процесса i(t) = [/'1(0, i2(t), ..., is(t)]. Так как {i 1 (t), 12(f), ..., is(t)} - немарковский случайный процесс, то будем рассматривать многомерную цепь Маркова [i(t), ii(t), ..., is(0, s(t)}. 2. Система дифференциальных уравнений Колмогорова Обозначим P(i1, h, ..., is, n, t) = P{i(t) = i, ii(t) = h, ..., is(t) = is, s(t) = n}, e: = [1, 0, ..., 0], e2 = [0, 1, ..., 0], ..., en = [0, 0, ..., 1], тогда для стационарного распределения вероятностей P(i, n) запишем систему дифференциальных уравнений Колмогорова: ( S Л s _ + XiVz P(i,n) + KP(i -e„,n) + (i + 1)P(i +e7,n) + £qvP(i,v) = 0, Vn = 1,S . /=1 /=1 j£-i)-^^ = KH(u,n)(eun -l) + Z4vnH(u,v), Vn = 1,S . k=1 duk v Систему уравнений для H(u, n) в матричном виде запишем следующим образом: JVL(u) ^ = h(u) (Л(u) + Q), h(u)=[H(u,1),H(u,2),--.,H(u,S)], v(u) = -1),-1),---,Vs(e j ~ 1)] (1) где Тогда для частичных характеристических функций вида H(u,u2us,n) = H(u,n) = Z j Z j'2 ■ ■ Ze'UsisР({,n), Уп = ^ = S имеем следующую систему уравнений: 'dH (u,1) dH (u, S) dh(u) du ■■■ 0 ■■■ 0 ■■■ ^S(eJuS -1) (eJu -1) 0 0 X2 (eju2 -1) 0 Л(u) = 0 Полученная система уравнений является основной для дальнейших исследований. Предлагается провести анализ характеристик рассматриваемой СМО с помощью метода асимптотического анализа. 3. Метод асимптотического анализа Предлагаемый метод асимптотического анализа реализуется в построении последовательности асимптотик возрастающего порядка, в котором асимптотика первого порядка, аналогично закону больших чисел, определяет асимптотическое среднее значение числа занятых приборов. Асимптотика второго порядка, аналогично центральной предельной теореме, позволяет построить гауссовскую аппроксимацию распределения вероятностей числа занятых приборов в системе. 3.1. Асимптотика первого порядка Решение системы (1) будем находить в асимптотическом условии эквивалентно растущего времени обслуживания, т.е. при ^ 0, i = 1, ... S. Обозначим = qs (s - бесконечно малая величина) и в (1) выполним замены u = sx (т.е. Ui = sxi), h(u) = F1(x, s), получим уравнение для F1(x, s): dF (x s ) JV(x, S) = F1(x, s) (Л(x, s) + Q) , dx где V(x,s) = [(ej -1)q^.,(e~]SXs -1)qs] , Л(ъ,s) = diag[e]s:' -1)" В (2) выполним предельный переход при s ^ 0, получим, что F1(x) является решением однородной системы линейных алгебраических уравнений: F1 (x)Q = 0, поэтому F1(x) будем искать в виде F,(x) = гФ, (x). (3) Здесь Ф1(х) = Ф1(х;, Х2, ..., x„) - неизвестная скалярная функция n переменных, n = 1, ..., S, r - вектор-строка стационарного распределения вероятностей значений цепи Маркова s(t), определяемая системой уравнений rQ = 0 (2) и условием нормировки re = 1, где e - единичный вектор. i = 1, S . Разложив экспоненты в (2) в ряд Тейлора до первого порядка, получим 0 ... 0 X x -j [ ад,..., xsqs ] В) = F1 (х,в) дх 0 X2 x2 0 0(в2). (4) 00 XSxS Домножив (4) на единичный вектор справа, имеем: -л dF (i, х, в) ' dx I dF2 (i, x, в) ' dxn X x X2 -j [ x1q1'...' xsqs ] + 0(в2). = F1(x, в) (5) I dF2 (i, x, в) ' dxn В (5), положив s ^ 0 и подставив разложение (3), получим -, дф (х)" X sxs -j [ xlql'•••' xsqs ] dxj dq (x) dx, X xj = Ф,(х)г Z r d^ ,■ 1 dr„ Получили дифференциальное уравнение первого порядка в частных производных для Ф^): ±x,q, дф^ = jtrXxq^). (6) 1=1 dxi 1=1 Нетрудно показать, что решение уравнения (6) имеет вид: M ФДх) = C2exp j q1 qs Учитывая начальное условие Ф1(0) = 1, функция Ф^) примет вид: f rS X SxS r X x w f rS XSxS qs r X xl q1 ФДх)=exp j тогда r X xl q1 rs Xsxs qs Fl(x) = г exp
Ключевые слова
бесконечнолинейная система массового обслуживания,
случайная среда,
метод асимптотического анализа,
infinite-server queue,
asymptotic analysis method,
random environmentАвторы
Полин Евгений Павлович | Томский государственный университет | аспирант кафедры теории вероятностей и математической статистики Института прикладной математики и кибернетических наук | polin_evgeny@mail.ru |
Моисеева Светлана Петровна | Томский государственный университет | профессор, доктор физико-математических наук, профессор кафедры теории вероятностей и математической статистики Института прикладной математики и компьютерных наук | smoiseeva@mail.ru |
Рожкова Светлана Владимировна | Томский политехнический университет | доктор физико-математических наук, профессор кафедры высшей математики и математической физики физико-технического факультета | rozhkova@tpu.ru |
Всего: 3
Ссылки
Моисеева С.П., Полин Е.П. Исследование математической модели бесконечнолинейной СМО с входящим MAP-потоком переменной интенсивности // Доклады 12-й Междунар. азиатской школы-семинара «Проблемы оптимизации сложных систем». 12-16 декабря 2016 г. Новосибирск, 2016. С. 380-384.
Таташев А.Г. Система массового обслуживания с переменной интенсивностью входного потока // Автоматика и телеме ханика. 1995. № 12. С. 78-84.
Дудин С.А., Дудина О.С. Многоканальная система обслуживания с марковским входным потоком нетерпеливых запро сов, функционирующая в случайной среде // Информатика. 2015. № 1. С. 45-55.
Eisen M., Tainiter M. Stochastic variations in queueing processes // Opens. Res. 1963. V. 11. P. 922-927.
Naor P., Yechiali U. Queueing problems with heterogeneous arrivals and service // Opens. Res. 1971. V. 19, No. 3. P. 722-734.
Yechiali U. A queueing tipe birth and death process defined as a continuous time markov chain // Opens. Res. 1973. V. 21, No. 2. P. 604-629.
Baykal-Gursoy M., Xiao W. Stochastic Decomposition in M/M/» Queues with Markov Modulated Service Rates // Queueing Syst. 2004. V. 48. P. 75-88.
O'Cinneide C.A., Purdue P. The M/M/» Queue in a random environment // J. Appl. Prob. 1986. V. 23. P. 175-184.
Blom J., Kella O., Mandjes M., Thorsdottir H. Markov-Modulated Infinite-Server Queues with General Service Times // Queueing Syst. 2014. V. 76. P. 403-424.
D'Auria B. M/M/» queues in semi-Markovian random environment // Queueing Syst. 2008. V. 58. P. 221-237.
Falin G. The M/M/» Queue in Random Environment // Queueing Syst. 2008. V. 58. P. 65-76.
Fralix B.H., Adan I.J.B.F. An infinite-server queue influenced by a semi-markovian environment // Queueing Syst. 2009. V. 61. P. 65-84.
Linton D., Purdue P. An M/G/» Queue with m customer types subject to periodic clearing // Opsearch, 1979. V. 16. P. 80-88.
Назаров А.А., Баймеева Г.В. Исследование системы М/М/» в полумарковской случайной среде // Известия вузов. Физика. 2015. Т. 58, № 11/2. С. 198-203.
Моисеев А.Н., Моисеева С.П. Исследование входящего потока для GRID-системы с адаптируемым выделением вычислительных ресурсов // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2012. № 3 (20). С. 81-87.
Полин Е.П. Исследование системы MMPP(n)|M(n)|» методом моментов // Труды Томского государственного университета. Т. 302. Сер. физико-математическая. Томск : Издательский Дом ТГУ, 2018. С. 306-311.
Назаров A.A., Моисеева С.П. Метод асимптотического анализа в теории массового обслуживания. Томск : Изд-во HTJI, 2006. 112 с.
Убонова Е.Г., Панкратова Е.В. Гауссовская аппроксимация для системы массового обслуживания MMPP/M/» с разнотипным обслуживанием // Известия вузов. Физика. 2015. Т. 58, № 11/2. С. 225-230.