Investigation of the queueing system MMPP|M|? with repeated service.pdf Одним из перспективных направлений современной экономической науки является привлечение для описания и количественного выражения экономических реалий методов их математического описания и моделирования. В связи с этим возникает задача формализации той высокой неопределенности, которая свойственна реальным экономическим процессам. В качестве математических моделей социально-экономических и демографических процессов часто используют системы массового обслуживания (СМО) с неограниченным числом обслуживающих приборов [1-3]. Как правило, в таких системах число потенциальных клиентов (страховых и торговых компаний, пенсионных фондов) считается неограниченным. В реальных технических системах число обслуживающих приборов конечно, но в случае, когда вероятностью потери заявки можно пренебречь, такие системы можно аппроксимировать бесконечнолинейными СМО. Исследование таких систем с пуассоновским входящим и произвольным временем обслуживания можно встретить в работах В.В. Рыкова, П.П. Бочарова, А.В. Печинкина и других авторов [4-7]. Однако применение пуассоновского потока для расчета характеристик качества обслуживания в реальных системах дает большую погрешность. Обоснованность адекватности применения марковского модулированного пуассоновского потока для описания информационных потоков в мультисер-висных сетях связи и телекоммуникационных системах следует из работ W.E. Leland, M.S. Taqqu, W. Willinger, V. Paxson, C. Lindemann, M. Lohmann и др. [8-9]. Системам с непуассоновскими входящими потоками (марковскими модулированными, полумарковскими) посвящены статьи D. Baum и L. Breuer [10, 11], M. Parulekar и A.M. Makowski [6], A.K. Jayawardene и O. Kella [12] и многих других. Основными методами исследования СМО с неограниченным числом приборов, как правило, являются метод вложенных цепей Маркова и метод дополнительной переменной, в последние двадцать лет стали развиваться матрично-аналитические методы [13]. В тех случаях, когда не удается найти характеристики системы в явном виде, применяют асимптотические методы [14-16]. Одной из модификаций СМО с неограниченным числом приборов являются системы массового обслуживания с повторными обращениями, которые применяются для описания математических моделей, например, страховых или торговых компаний. Исследования таких систем с пуассоновским входящим потоком приведены в работах [2, 17], где методом производящих функций определены такие процессы, как число занятых приборов в системе и характеристики потоков, обращающихся в систему. Такие модели используют для описания процесса зависимости величины капитала коммерческой организации от стимулирующих программ, например предоставление скидки при приобретении товара; кроме того, подобные системы предлагаются в качестве математических моделей распределительных вычислительных сетей [1, 18]. Для аналогичных систем с произвольным временем обслуживания в работе [19] предложен метод предельной декомпозиции, позволяющий свести исследование бесконечнолинейной системы массового обслуживания к исследованию совокупности однолинейных систем. К сожалению, данный метод не удается применить для исследования систем не пуассоновским входящим потоком (ММРР, МАР, рекуррентный поток), для таких потоков необходимо освоение новых методов исследования. В данной статье приводится исследование СМО с повторными обращениями, на вход которой поступает поток MMPPjMjw. С помощью метода начальных моментов найдены основные характеристики системы, такие как среднее число занятых приборов в системе и второй момент числа занятых приборов. Кроме того, для более детального исследования процессов, указанных выше, предложен метод асимптотического анализа. 1. Постановка задачи Рассмотрим систему массового обслуживания с неограниченным числом приборов (рис. 1), на вход которой поступает марковский модулированный поток (MMPP), управляемый цепью Маркова k(t), заданной матрицей инфинитезимальных характеристик Q = |^Ц и матрицей условных интен-сивностей Л [16]. Продолжительность обслуживания заявки имеет экспоненциальное распределение с параметром ц [20]. Поступившая заявка занимает любой из свободных приборов, завершив обслуживание на котором, с вероятностью 1-г покидает систему или с вероятностью г возвращается в неё для повторного обслуживания [2,17]. Рис.1. Система массового обслуживания MMPP|M|i» с повторным обращением к блоку Обозначим i(t) число занятых приборов в момент времени t, n(t) - число повторных заявок, обратившихся за время t, k(t) - состояние управляющей цепи Маркова. Полученный двумерный случайный процесс {k(t), i(t)} является марковским. Для его распределения вероятностей P (k, i, n, t) = P{k (t) = k, i(t) = i, n(t) = n} получаем систему дифференциальных уравнений Колмогорова ^^ = P(k,i,t)(k(1-r)) + P(k,i +1,t)(i + 1)(1-r) + P(k,i -1,t)k + Z P(v,i,t)^vk (1) Введем частичные характеристические функции [21] вида H (k, u, w, t) = ZZ eJuieJwnP(k, i, n, t). i n Учитывая, что = j Z ie]U'P (k, i, t), дИ ( k, u, t) дu i=0 из (1) имеем следующую систему уравнений: дИ(^ + » (1-Г)(J - = X k ( - ) (k, U, t)+ Z Яли (v, u, t). dt ^ ! ды k Запишем данную систему в виде матричного уравнения дН (ы, t) (2) v^k j-ц(1-Г)(e-Ju - 1))M = H(u,t)[Л( -1 dt где Н(u,t) = [И(1,u,t),И(2,u,t),...,И(K,u,t)] : X1 0 ... 0 0 X 2 ... 0 q11 q12 ... q1K q21 q22 ... q2K qK1 qK 2 ... qKK Л = , Q = 0 0 ... X K. 2. Метод начальных моментов Используя уравнение (2), определим начальные моменты для числа занятых приборов в системе, для этого рассмотрим нулевой момент времени, в который имеем число повторных обращений w = 0 (так как число обслуженных заявок равно нулю), тогда (2) перепишем в следующем виде: (1- г)(e-ju - в = Н(u)[л(u -1) du Чтобы определить момент первого порядка, продифференцируем уравнение (3) по u: ч ,u дН (u) ./ u чд2Н (u) дН (u) г , ,u ч ц(1 - г)e-+ j-ц(1 - Г( - = _Li[Л(u - ^ обозначив (3) je'u Н (u ), (4) дН (u) = jmi, du u=0 получаем следующую систему линейных уравнений: m^ (1 - г ) = mxQ + ИЛ . Здесь R = Н(0) - вектор стационарного распределения вероятностей управляющей цепи Маркова [16], которое определяется системой уравнений RQ = 0 и удовлетворяет условию нормировки RE = 1. Решая данную систему, получаем выражение, определяющее вектор m1: mt = ИЛ[ц(1 - г)I - Q]-1. (5) Тогда значение среднего числа занятых приборов в системе определяется следующим выражением: M{i(t)}= . 1 . ЯЛE . ц (1 - г) Для определения момента второго порядка продифференцируем по u выражение (4), получим , ч ,u 8H(u) . ч u 82H (u) , ч/ ,u \83H (u) - ;ц (1 - г )e-]u-8^~ + 2ц (1 - Г )e- j + (1 - г )( - 1^-8ГН = Л(eiu -1) + Q] + 2 jeju 8HdMЛ - ejuH (u) . 8 2H ( u ) 8u2 8u Тогда, обозначив 8 2H (u ) = j m2 , 8u2 u=0 получим m2 [Q - 2ц(1 - г)I] + m1 [2Л + ц(1 - г)I] + ЯЛ = 0, где I - единичная диагональная матрица. Подставляя в (5) выражение (6) и решая данное уравнение относительно величины m 2, имеем ЯЛ{[Q-ц(1 - г)I]"1 [2Л + ц(1 - г)I] - l}{Q - 2ц(1 - г)l} . Тогда второй момент числа занятых приборов в системе имеет вид M {i2 (t)} = m2E = RЛ{[Q-ц(1 - г)I]-1 [2Л + ц(1 - г)I] - i}{Q - 2ц(1 - г)i} E . m. 3. Метод асимптотического анализа Для более полного исследования применим метод асимптотического анализа, заключающийся в нахождении аппроксимации характеристической функции числа занятых приборов в системе MMPPjMjw при определенных условиях. Для нашей системы будем рассматривать условие растущего времени обслуживания [16], т.е. высокой загрузки системы. 3.1. Асимптотика первого порядка Обозначим (6) ц = е, u = ey, H (u) = Fi (y, e) . Перепишем (3) с учетом введенных обозначений: (7) (8) решение которого имеет вид ,-(1 - г)(e-jEy -1))= Fi (y, е)[Л(ejEy -1) + q" Тогда при е ^ 0 имеем уравнение 0 = Fi (y) Q, Fi (y ) = ЯФ1 ( y) . Домножая уравнение (8) на единичный вектор E и выполняя все необходимые преобразования, имеем j (1 - г)(e-jy -1))E = F (y,8)(ejsy - 1)ЛЕ . Раскладывая в этом уравнении экспоненты в ряд, а также разделив обе части уравнения на 8 и полагая 8 ^ 0, получаем ч дК (y) . . (1 - г)y-^E = jyFj (y)ЛЕ . (10) дy Подставляя (9) в систему (10) и учитывая условие RE = 1, получаем дифференциальное уравнение первого порядка для нахождения функции Ф^у): ^ E=j Ф1(у)ЛЕ . д^ (1 - г) 1W Откуда, учитывая начальное условие Ф1 (0) = 1, имеем jy Ф! (y ) = exp j^- K1 j, K1 = R • Л • E. Следовательно, учитывая (9), F1(y) = R exp j j K1 j . В силу замены (7) и предыдущего равенства можно записать следующее асимптотическое равенство: Н (u ) = Ft (y, 8)* Ft (y) = R • exp j j к j . Поэтому для характеристической функции стационарного процесса i(t) запишем Ju_ К! j "г Ц M \eju,(t)} = Н (u )E * exp • j к1 I = exp j ^ Данное равенство будем называть асимптотикой первого порядка для СМО ММPP|M|да с повторными обращениями. 3.2. Асимптотика второго порядка Выполним следующую замену: г ju к (11) Н (u ) = Н2 (u )exp jy Тогда уравнение (3) для H2 (u) будет иметь вид j^(1 - г)(e-ju - 1))= Н2 (u)[q + Л(eju -1) + K1 (e- - 1)l Обозначим Ц = 82 , u = 8y , Н2 (u) = F2 (y, 8) (12) je(1 - г)(e-jEy -1))М = F2 (y,е)[q + Л(ejEy -1) + к (e"jEy -1)1 тогда при е ^ 0 имеем уравнение 0 = F2 (y) Q. Следовательно, решение F2 (y, е) в уравнении (13) можно записать в виде разложения F2 (y, е) = Ф2 (y) [ R + jeyf2 ] + O (е2). (14) Подставляя данное выражение в (13) и раскладывая в ней экспоненты в ряд, получаем уравнение для нахождения функции f2 R (Л - к11) + f2Q = 0. Чтобы найти функцию Ф2 (y), домножим обе части уравнения (13) на единичный вектор E, далее, раскладывая в данном выражении экспоненты в ряд и подставляя (14), получаем дифференциальное уравнение первого порядка (1 - г= j2уФ2 (У)[R • Л • E+f2 (Л - кх!)E]. 8У Решение данного уравнения, удовлетворяющее начальному условию Ф2 (0) = 1, имеет вид (jy) 2 Ф2 (У ) = exp< 2 (1 - г)2 где к2 = к + f2 (Л - KjI) E . Тогда в силу замен (12) запишем асимптотическое равенство для H2 (u) : H2 (u) = F2 (y, e )« F2 (y) = R • exp j j) к 2 } = R • exp j }. (15) Это равенство будем называть асимптотикой второго порядка. Учитывая (11) и (15), имеем следующее выражение для H(u): H(u) = H2 (u)• exp{-^1} = R • expj-" + j к2 I ^j-' I /4 1 - г ц J 11 - г ц 2(1 - г) ц поэтому для характеристической функции числа занятых приборов i(t) в системе получим (13) и из(11) получим ju к! , (ju )2 к1 - г ц 2 (1 - г) ц I M {)} = H (u )E = exp {1 Из последнего выражения следует, что стационарное распределение вероятностей числа занятых приборов в системе MMPPjMjw можно аппроксимировать гауссовским распределением со следующими параметрами: к2 =M {(t)}=, о2=M! Q = 0,2 -0,6 0,4 , Л = 0 8 0 , л = 0 8 0 , E = 0 1 0 , I = 1 0,5 0,3 -0,8 0 0 10 ч 0 0 10V ч 0 0 1V Л Сравнение асимптотических и аналитических результатов "-0,5 0,3 0,2 " "1 0 0 Q = 0,2 -0,6 0,4 , Л = 0 0,6 0 0,5 0,3 -0,8 0 0 0, Для заданных значений, изменяя параметр ц, получаем следующие результаты (табл. 1). Т а б л и ц а 1 Сравнение асимптотических и аналитических результатов 1 0,5 0,25 0,1 0,05 M D M D M D M D M D Асимптотические результаты 4,067 4,244 8,133 8,488 16,267 16,976 40,667 42,440 81,333 84,881 Аналитические результаты 4,067 4,210 8,133 8,450 16,267 16,936 40,667 42,399 81,333 84,839 Вычислим относительную погрешность между величиной дисперсии, полученной методом моментов, и асимптотическим методом (табл. 2). Т а б л и ц а 2 Относительная погрешность 1 0,5 0,25 0,1 0,05 А 0,82% 0,45% 0,24% 0,10% 0,05% Следует отметить, что при данных входных параметрах максимальная относительная погрешность составляет менее 1%. Отметим, что при уменьшении параметров времени обслуживания результаты, полученные асимптотическим методом, приближаются к аналитическим результатам, что позволяет применять асимптотический алгоритм для широкого круга задач. Пример 2. Рассмотрим еще один пример с большой интенсивностью входящего потока (табл. 3). Используем следующие значения параметров: Т а б л и ц а 3 1 0,5 0,25 0,1 0,05 M D M D M D M D M D Асимптотические результаты 36,667 59,383 73,333 118,765 146,667 237,531 336,667 593,827 733,330 1187,654 Аналитические результаты 36,667 55,354 73,333 114,343 146,667 232,882 336,667 589,031 733,330 1182,807 Вычислим относительную погрешность между величиной дисперсии, полученной методом моментов, и асимптотическим методом. Т а б л и ц а 4 Относительная погрешность 1 0,5 0,25 0,1 0,05 А 7,28% 3,87% 2,00% 0,81% 0,41% Заметим, что в данном примере относительная погрешность, приведенная в табл. 4, оказалась в разы больше погрешности в примере 1; это говорит о том, что на асимптотические результаты влияет не только продолжительность времени обслуживания, но и входящие параметры, а именно интенсивность входящего потока. Заключение В настоящей работе была построена математическая модель обслуживания заявок в системе MMPPjMj®, а также определены аналитические выражения для нахождения первого и второго моментов, характеризующих число занятых приборов в системе и их асимптотического приближения. Проведен численный анализ полученных результатов.

Скачать электронную версию публикации