Автоматика и телемеханика, № 6, 2015
Стохастические системы, системы массового обслуживания
© 2015 г. М.А. МАТАЛЫЦКИЙ, д-р физ.-мат. наук (m.matalytski@gmail.com) (Гродненский государственный университет, Беларусь)
АНАЛИЗ И ПРОГНОЗИРОВАНИЕ ОЖИДАЕМЫХ ДОХОДОВ В МАРКОВСКИХ СЕТЯХ С ОГРАНИЧЕННЫМ ВРЕМЕНЕМ ОЖИДАНИЯ ЗАЯВОК
Рассматриваются методы нахождения ожидаемых доходов в системах марковских сетей массового обслуживания с доходами и ограниченным временем ожидания заявок в очередях. Исследования проводятся в случаях, когда доходы от переходов между состояниями сети являются детерминированными функциями, зависящими от состояний и времени, либо являются случайными величинами с заданными моментами первых двух порядков.
1. Введение
Понятие сетей массового обслуживания (МО) с доходами было введено в [1—3]. Заявка при переходе из одной системы обслуживания (СМО) в другую приносит последней некоторый доход, а доход первой СМО уменьшается на эту величину. В обзорной статье [4] и монографии [5] приведены результаты по анализу, оптимизации, управлению марковских сетей с доходами, описаны различные практические применения их в качестве стохастических моделей прогнозирования доходов в информационно-телекоммуникационных системах и сетях (ИТСС), когда, например, обслуживание запросов на сервере приносит доход обслуживателю, а также в производстве, страховых компаниях, логистических транспортных системах и других объектах. Функционирование любой марковской сети МО описывается с помощью цепей Маркова с непрерывным временем и, как правило, с большим или счетным числом состояний; в простейшем случае марковские цепи с небольшим числом состояний и доходами, являющимися константами, были рассмотрены в [6]. В данной статье рассматриваются марковские сети с доходами, у которых длительности пребывания заявок в очередях СМО сети являются случайными величинами, распределенными по экспоненциальным законам.
Рассмотрим открытую экспоненциальную сеть МО с однотипными заявками, состоящую из п СМО Б\,..., Бп. Под состоянием сети понимается вектор к(1) = (к\,..., кп, I), где кг - число заявок в системе Si в момент времени I, I € [0, +оо), г = 1,п. Для унификации обозначений введем систему ¿>о (внешнюю среду), из которой в сеть поступает простейший поток заявок с интенсивностью Л. Пусть роу - вероятность поступления заявки из системы £о в
систему Sj, n=i Poj = 1; 'Pij - вероятность перехода заявки в СМО Sj после
j=
лп
ее обслуживания в СМО Si, Ylj=oPij = 1) = 1>п- Заявки на обслуживание выбираются в соответствии с дисциплиной FIFO.
Предположим, что длительность ожидания заявок в очереди i-й СМО является случайной величиной (СВ), распределенной по экспоненциальному закону с параметром 9i, и не зависит от других факторов, например, от числа заявок в очереди, времени ожидания в очереди других заявок и т.д. В ИТСС это соответствует ситуации, когда, скажем, пользователь ждет определенное время доступа к некоторому вычислительному ресурсу, а затем, если в течение этого времени он не будет обслужен, переходит в очередь другого доступного ему вычислительного ресурса. В [7] описано применение сетей с ограниченным временем ожидания заявок при моделировании информационных систем межбанковских расчетов и систем документооборота. Заявки, которые покидают СМО, не получив в ней обслуживания, называются "нетерпеливыми" [8]. В этой же работе найдены стационарные вероятности состояний такой сети в форме произведения. В [9] для нахождения вероятностно-временных характеристик в переходном (нестационарном) режиме применен аппарат многомерных производящих функций. Заявки, время ожидания которых в очереди i-й СМО истекло, переходят в j-ю СМО с вероятностью qj либо с вероятностью qi0 покидают сеть, ^П=о Qij = 1. Таким образом, динамика движения в сети "нетерпеливых" заявок задается матрицей Q = \\qijУгах(га+1), причем в общем случае матрица Q не тождественна матрице р = \\pij \\(п+1)х(п+1).
В данной статье для марковской сети с доходами и ограниченным временем ожидания заявок в очередях СМО находятся ожидаемые (средние) доходы СМО сети за время t при условии, что известно состояние сети в начальный момент времени.
2. Система разностно-дифференциальных уравнений для ожидаемых доходов и ее решение
Рассмотрим вначале случай, когда доходы от переходов между состояниями сети являются детерминированными функциями, зависящими от состояний сети и времени, а СМО сети являются однолинейными. Пусть: v¿(fc,í) - ожидаемый доход, который получает система Si за время Ь, если в начальный момент времени сеть находится в состоянии к; ri(k) - доход системы Si в единицу времени в течение времени пребывания сети в состоянии к;
— п - вектор с нулевыми компонентами, за исключением компоненты с номером г, которая равна 1; — ^0(к — Ь,Ь), —И,ю(к — и, Ь) - доходы системы Si, когда сеть меняет свое состояние из (к,Ь) на (к — + ДЬ) соответственно из-за ухода заявки после обслуживания в этой системе во внешнюю среду и из-за ухода заявки из очереди этой системы во внешнюю среду, которая не дождалась обслуживания в ней; г^(к + - доход системы Si, когда сеть меняет свое состояние с (к, Ь) на (к + + ДЬ) из-за прихода заявки из внешней среды в эту систему; г^ (к+I\ — Ij• ,Ь), Н^ (к + и — Ij• ,Ь) - доходы системы Si, когда сеть меняет свое состояние с (к, Ь) на (к + ^ — I^ + ДЬ) соответственно из-за перехода заявки после обслуживания в системе Sj в эту систему и из-
за перехода заявки, не дождавшейся обслуживания в системе Sj, из очереди этой системы в систему S¿.
Теорема 1. Система разностно-дифференциальных уравнений для ожидаемых доходов системы Si сети имеет вид
г)
Ж ~
vi (к, г) +
х + ^ ш1п , mj) и ) + ej- mj) и - mj)) j=l
п
(1) + {xРоjVi (к + ^,г) + шт (^, mj) и (^) Pjo +
j=l
+9j (^ - mj) и (^ - mj) qjo] Vi (к - и,г)} +
п
+ {[^ шт (к, mi) и (к) р^ + вi (к - mi) и (к - mi) qij] Vi (к - и + ^,г) + j=l
+ [ц,j шт (kj, mj) и (kj) pji + вj (kj - mj) и (kj - mj) qji] vi (к + Т, - ^,г)} +
п
+ У] [^з шт (ks, ms) и (ks) Рзс + вз (кз - ms) и (к8 - ms) qsc] Vi (к + 1с - 1з, г) +
0,8=1, с,в=
п
+ [^ шт (^, mj) и (^) Рjirij (к + и - ^ ,г) -j=l
-/л, шт (к, mi) и (к) р^^ (к - и + ^ ,г) +
+вj (kj - mj) и (^ - mj) qjihij (к + и - ^ ,г) +
+вг (к - mi) и (к - mi) qijhji (к - и + ^, г)] +
+Аро^ (к + и, г) - /л, шт (к, mi) и (к) рмЩо (к - и, г) -
-О, (к - mi) и (к - mi) qiоHiо (к - и, г) + г, (к).
Доказательство теоремы аналогично доказательству соответствующей теоремы без ограничений на время ожидания заявок [4].
Для замкнутой сети, т.е. в случае, когда Л = 0, р^ = £>¿0 = Яог = Яю = О, г = 1 ,п, данная система упрощается. В этом случае систему уравнений (1) можно свести к системе конечного числа линейных неоднородных обыкновенных дифференциальных уравнений (ОДУ) с постоянными коэффициентами, которая в матричной форме может быть записана в виде
(2)
аг
где (г) = ^ (1, г) (2, г),... (Ь, г)) - искомый вектор ожидаемых доходов системы Si, Т - знак транспонирования, Ь - число состояний сети.
Систему (2) можно решить прямым методом, используя матричную экспоненту [10]:
г
Ui(t) = eAtUi(0) + У eA(t-T )Qi(r )dt
о
или методом преобразований Лапласа, тогда
Ut(t) = W(t) * Qi{t) + W(t)Ut( 0), i = lji,
W(t) - обратное преобразование Лапласа матрицы (si — A)-1, I - единичная матрица,
W (t) * Ql (t) = j W (u) Qi (t - u) du.
Однако необходимо помнить, что число состояний замкнутой сети МО равно L = СП—к-i, гДе K - число заявок в сети и оно является довольно большим даже при относительно небольших n и K, т.е. число уравнений в системе (2) будет также достаточно большим. Опыт показал, что такими методами можно производить расчеты для сетей с относительно небольшим пространством состояний (L < 200); прямым методом это можно сделать для сетей большей размерности, чем методом преобразований Лапласа.
3. Анализ доходов в случае, когда доходы от переходов между состояниями сети являются случайными величинами с заданными моментами первых двух порядков
Будем рассматривать случай, когда интенсивность обслуживания заявок в системе Джексона S¿ и интенсивность ухода заявок из очереди (кг)
зависят от числа заявок в ней, i = 1 ,п. Рассмотрим динамику изменения доходов этой системы. Пусть в начальный момент доход этой системы равен v-o, а Vi (t) - ее доход в момент времени t. Разобьем отрезок [0, t] на m равных частей длиной At = считая т большим. Для нахождения дохода системы выпишем вероятности тех событий, которые могут произойти на l-м отрезке времени, I = 1 ,т. При этом возможны следующие ситуации: а) с вероятностью X'poiAt + o (At) в систему Si поступит заявка из внешней среды, которая принесет ей доход в размере ro¿, где ro¿ - СВ с функцией распределения (ф.р.) Fqí (х), i = 1, щ б) с вероятностью (l)) pioAt + о (At) заявка после обслуживания в системе Si перейдет во внешнюю среду, при этом ее доход уменьшится на величину Río, где Río - СВ с ф.р. Fío(x), г = 1,щ в) с вероятностью уj (kj (l)) pjiAt + o (At) заявка перейдет после обслуживания из системы Sj в систему Si, при этом доход системы Si возрастет на величину r'ji, а доход системы Sj уменьшится на эту величину, í,j = 1 ,п, j ф i, где Tj-i - СВ с ф.р. Fiji (x); г) с вероятностью (kj, (l)) pijAt + o (At) заявка после обслуживания в системе Si поступит в систему Sj, при этом доход системы Si уменьшится на величину Rj, а доход Sj возрастет на эту величину, где Rij -
СВ с ф.р. F-2ji (ж), i,j = 1 ,п, j ф i; очевидно, что Vji = Rji с вероятностью 1,
(3)
F\ij (ж) = F2ij (ж), г, j = 1, щ
д) с вероятностью вi (кi (I)) qi0Аt + о (Аг) заявка, не дождавшись обслуживания в системе Si, перейдет из очереди этой СМО во внешнюю среду, при этом ее доход уменьшится на величину Що, где Що - СВ с ф.р. Qiо (ж), г = 1,щ
е) с вероятностью вj (^ (I)) qjiАt + о (Аг) заявка, не дождавшаяся обслуживания в системе Sj, перейдет из очереди этой СМО в систему Si, доход ее при этом возрастет на величину hji, а доход СМО Sj уменьшится на эту величину, г,;) = 1 ,п, г ф ;), где - СВ с ф.р. С<)^г(х); ж) с вероятностью в% (к (I)) qijАг + о (Аг) заявка, не дождавшись обсл
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.