Poisson flows in systems with retrial queues.pdf Системы массового обслуживания с повторным обслуживанием заявок вызывают большой интерес у специалистов по массовому обслуживанию [1, 2]. Особый интерес в последние годы вызывают системы с повторным обслуживанием и бесконечным числом каналов [3, 4]. В этих работах инициируется построение достаточно общих моделей обслуживания в сетях с бесконечным числом каналов в каждом узле. Особенностью таких сетей является их представление в виде ориентированного дерева. При анализе этих сетей с пуассоновским входным потоком появляется необходимость использовать теорему Бурке и применять теоретико-графовые построения для определения независимости отдельных потоков сети. В настоящей работе предпринимается попытка решения подобных вопросов в наиболее общем виде. 1. Потоки, выходящие из одного узла Рассмотрим бесконечно канальную систему массового обслуживания с пуассоновским входным потоком и показательным распределением времени обслуживания заявок. Полагаем, что каждая заявка после окончания обслуживания может быть повторно обслужена (рис. 1). Возможны самые различные протоколы работы такой системы, например, время повторного обслуживания может иметь распределение, отличающееся от времени первоначального обслуживания, число повторных обслуживаний может быть отличным от единицы и т. д. Рис. 1. Преобразование системы с однократным повторным обслуживанием в сеть Самой общей может быть модель прохождения заявки через сеть, в каждом узле которой имеется бесконечное число каналов с показательным распределением времени обслуживания. Такая сеть описывается ориентированным деревом D, в котором каждое ребро направлено от корня дерева r (вершины, в которую не входит направленное ребро) к его листьям (вершинам, из которых не выходят направленные ребра). После окончания обслуживания в узле заявка может быть направлена в один из узлов дерева, куда указывают его направленные ребра. Естественным обобщением этой модели является предположение, что время обслуживания заявки на приборе является гиперэкспоненциальным (вероятностной смесью экспоненциальных распределений). Данное обобщение никак не меняет вид сети, у которой вновь переходы заявок между узлами описываются ориентированным деревом. Из известной теоремы Бурке [6] следует, что если сеть функционирует в стационарном режиме, то выходной поток из каждого узла, равно как и входной поток в каждый узел, является пуассоновским. Однако возникает вопрос о зависимости или независимости этих потоков. Рассмотрим теперь пуассоновский поток точек Л = {0 < t1 < t2 0, и обозначим n, n1, n2 количество точек потоков Л, Л1, Л2 на этом отрезке. Вычислим вероятность P(n = ^ П2= *2)= P(n = k + ^2)^^ p!1 pk22 = k2 {\+kkf p!1 p22 = = e-XTpl ^^ • e-^Tp2 ^t- = P(nl=k) P(n2 = k2). k1! k2! Пусть теперь отрезки [t(1),t(1) + T(1)], [t(2),t(2) + T(2)] не пересекаются. Обозначим n(i), n1(i), n2i) количество точек потоков Л, Л1, Л2 на отрезке [t(i),t(i) + T(i)], i = 1,2. Докажем независимость случайных величин n1(1), n^. Для этого, полагая k21} = k(1) - к/1), k(2) = k(2) - k22), вычислим вероятность P (n1(1) = k(1), n22) = k22) )= Z P (n(1) = k(1), n(2)= k(2) )) pk(1) pf C% pk(2) pf = \ ' (1) (1) (2) (2) V ' ky ' k ' k(1) >k1(1), k(2) >k22) / (1) (1) (2) (2)\ k(1) k(1) k(1) k(2) k(2) k(2) Z P(n(1)= k(1))P(n(2) = k(2))p1k1 p^2 C%pk p\2 = k(1)>k(1), k(2)>k(2) v ' k k 1 ' 2 Z -xt(1) (XT(1))k(1) Xt(2) (XT(2))k(2) k(1)! ^ pk21) k(2)! = kO>k(Z(2)>k(2)e k(1)! e k(2)! kj(1)! k21)!p p2 k(2)! k22)!p p2 = = e-XT(1) д e k(1)! ~ k22)! (1) k (1) (2) k (2) (1) k (1) (2) k (2) = e-XT(1)p (XT(1)A)1 e-XT(2)P2 (XT(2)p2) 2 Z e-XT(1)P2 (XT(1)p2) 2 Z e-XT(2)P, (XT(2)p1) 1 k1(1)! k22)! k2D>0 kf! k(2)>0 k®! (1) k(1) (2) k(2) iil^e--(2) lXIk|^ = P (nf')=k1(') )P ()= kf). независимых компонент. Следовательно, пуассоновские потоки Aj, Л2 независимы. Замечание 1. Утверждение теоремы 1 распространяется на случай, когда пуассоновский поток A делится на l >1 пуассоновских потоков с помощью вероятностного просеивания, при котором каждая точка потока A с вероятностью Pj >0 попадает в поток A, j = 1,..., l, ^ Pj = 1. j=1 2. Независимость конечного числа потоков сети На множестве вершин ориентированного дерева D (в каждую вершину которого входит только одно направленное ребро) определим отношение частичного порядка u1 У u2, если в дереве D существует путь из вершины u1 в вершину U2 (здесь u У u >. Сопоставим каждой вершине u дерева D множества вершин P(u> = (v: u у v}, Q(u> = {v: v У u} u P(u>. Теорема 2. Предположим, что вершины u^,..., uk дерева D таковы, что множества Р(щ>,...,P(uk> не пересекаются. Тогда для любых вершин v1 еP(u1>,...,vk е P(uk> потоки A(vj>,.,A(vk>, входящие в вершины v1,.,vk, соответственно, независимы. Доказательство. Из определения дерева D следует, что в нем существует вершина u такая, что непересекающиеся множества P(uj>,...,P(uu> содержатся в множестве P(u>. В качестве u можно взять, например, корень дерева. Следовательно, в силу теоремы 1 и замечания 1 потоки, выходящие из вершины u, независимы. Отсюда автоматически следует независимость потоков A(vj>,.,A(vk>. Всюду далее без ограничения общности будем предполагать, что любая вершина дерева D за исключением листьев имеет отвлетвление (из нее выходит несколько направленных ребер, рис. 3>. Построим алгоритм выделения кластеров на множестве вершин дерева D . Пусть в дереве D зафиксирована вершина u, не совпадающая с корневой вершиной, и определены соответствующие ей множества P(uj>, Q(uj>, Sj= Q(uj>. Если на шаге i > 1 заданы ui, Si, то возьмем вершину ui+j £ Si и положим Si+i = Si u Q(ui >. В силу конечности числа вершин в дереве D эта процедура закончится на некотором шаге l > 1 построением вершин uj,...,ui и соответствующих им множеств Sj,...,Si. Рис. 3. Дерево с ответвлениями Теорема 3. Множества вершин P(u1>,., P(ui > в дереве D не пересекаются. Доказательство. Пусть на шаге i ,...,P(ui>. Тогда на шаге i +1 выполняется соотношение ui+1 £Si и, значит, множество P(ui+1> не пересекается с множествами P(u1>,...,P(ui>. В противном случае существуют такие k, 1 < k < i, v e P(uk), что v e P(ui+1). Следовательно, ui+1 > v, Uk ^ v, Mi+1 ык и, значит, D не является ориентированным деревом. Таким образом, пары случайных величин ((1>,n2*> ),(n состоят из Обозначим m число ребер, выходящих из корневой вершины дерева D и попадающих в вершины v^...,vm, и положим M число листьев этого дерева. Теорема 4 Справедливо неравенство m < l

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