Введение к работе
Одной из важных задач современной теории массового обслуживания является изучение асимптотического (с ростом времени) поведения случайных процессов, характеризующих состояние систем обслуживания; в частности, выяснение условий сходимости этих процессов к предельным, соответствующим так называемому стационарному режиму работы. В последнее время особенно интенсивно исследуются модели систем и сетей обслуживания, возникающих в реальных приложениях и имеющих, как правило, достаточно сложную структуру.
Данная работа посвящена изучению предельного поведения двух классов систем обслуживания:
I) систем поллинга,
II) неполнодоступных систем.
Системами поллинга называют системы, состоящие из нескольких станций (или очередей), входного потока вызовов и одного прибора, обслуживающего очереди последовательно и переходящего из одной очереди в другую в соответствии с некоторым случайным маршрутом. Задаются также алгоритмы, определяющие число вызовов, обслуживаемых за один визит прибора в каждую очередь (в дальнейшем вместо термина «алгоритм» мы будем использовать термин «дисциплина обслуживания») .
Понятие «неполнодоступности» систем не имеет четкого определения, трактуется различными авторами по-разному и связано с некоторыми ограничениями на маршруты поступающих в систему вызовов, определяемыми их внутренними характеристиками. В данной работе под непол-нодоступной понимается система обслуживания, входной поток в которую состоит из вызовов различных типов, причем тип вызова определяет множество доступных этому вызову параллельно работающих станций обслуживания. Среди этих станций вызов выбирает одну по некоторому правилу (в зависимости от состояния системы в момент поступления вызова), обслуживается на ней в порядке очереди и покидает систему по окончании обслуживания.
Достаточно давно известно, каковы должны быть естественные условия «стабильности» для систем поллинга, однако вопрос о существовании стационарного режима и сходимости к нему допредельных процессов при выполнении этих условий долго оставался открытым. В последнее время появился ряд статей, в которых доказана сходимость процесса длины очереди к стационарному режиму (который является единственным)
для широкого класса моделей поллинга в марковских предположениях. В этих работах рассматриваются системы с пуассоновскими независимыми входными потоками и взаимно независимыми последовательностями времен обслуживания на каждой станции.
Так, например, А. А. Боровков и Р. Шассбергер1 рассмотрели марковскую модель поллинга, в которой после посещения очереди г прибор переходит в очередь j с вероятностью pi j за время Wij со средним Witj, а число вызовов, обслуженных за один визит прибора в г'-ю очередь, имеет вид f(x,L,) = т'т[х, L{), где х — длина этой очереди в момент прихода прибора и Li — случайная величина. Доказано, что необходимым и достаточным для эргодичности такой системы является следующее условие:
р = У^Л,чг,+ max —'—w < 1. (1)
іҐї !<^К TfFj
Здесь А,- — интенсивность входного потока на станцию г, <т,- — среднее время обслуживания на этой станции, w = 5Z» j=i KiPijWij — среднее время перехода между последовательно посещаемыми очередями для стационарного распределения {эт,-}/^ матрицы (pij), и F,- = EL,-.
К. Фрикер и М. Р. Джайби2 рассмотрели систему поллинга с периодическим (не обязательно циклическим) маршрутом прибора и случайными дисциплинами обслуживания произвольного вида, удовлетворяющими некоторым условиям стохастической монотонности. Доказано, что условие вида (1) необходимо и достаточно для эргодичности такой системы. Ранее JI. Георгиадис и В. Шпаньковски3 получили аналогичный результат для циклических систем поллинга с ограниченными дисциплинами обслуживания.
Вопросы существования стационарного режима для систем поллинга в общих предположениях относительно входного потока рассматривались лишь в нескольких работах. Е. Альтман и С. Г. Фосс4 получили условия эргодичности системы поллинга с т.н. «неограниченными дисциплинами обслуживания» и входным потохом, образованным последовательностью
'Borovkov А.А., Schassberger R. Ergodicity of a polling network // Stochast. Process, and Appl. 1994. V. 50. P. 253-262.
'Flicker C, Jaibi M.R. Monotonicity and stability of periodic polling models// Queueing Systems. 1994. V. 15. P. 211-238.
3Georgiadis L., Szpankowski W. Stability of token passing rings// Queueing Systems. 1992. V. 11. P. 7-34.
4Altman E., Foss S. Polling on a graph with general arrival and service time. INRIA rep.N« 1992.
независимых, одинаково распределенных случайных величин.
Л. Массули5 исследовал систему поллинга со стационарным и метрически транзитивным входным потоком, марковским маршрутом прибора и монотонными в некотором смысле дисциплинами обслуживания, зависящими от случайного аргумента. Существование стационарного режима
для системы с нулевыми начальными условиями доказано при выполне-
к к .
нии следующего условия (ср. с (1)): У^А,-<т,- -+- \^ —'—w < 1. Показа-
но также, что построенный стационарный режим является в некотором стохастическом смысле минимальным для систем с ненулевыми начальными условиями.
В последнее время широко исследуются системы с несколькими типами вызовов. Системы, в которых вызову одного типа доступно только одно обслуживающее устройство, изучались, например, в работах X. Че-на и А. Мандельбаума6, Д. Г. Дай7.
. Для доказательства сходимости к стационарному режиму в марковских предположениях авторы используют метод жидкостной аппроксимации.
Отметим, что в этих моделях каждый вызов из входного потока, в зависимости от своего типа, направляется на определенную станцию. В нашем случае номер станции, на которую поступит вызов из входного потока, не определяется полностью его типом: выбор станции из числа доступных зависит от состояния системы. Такого вида модели, но с отказами, рассматривались, например, Г. И. Фалиным8.
Цель работы — получить необходимые и достаточные условия эргодичности систем поллинга и неполнодоступных систем обслуживания в возможно более широких предположениях о распределениях характеристик рассматриваемых моделей.
Методы исследования. Исследования, проведенные в работе, основаны на применении и развитии современных методов теории массового обслуживания, таких как метод разделения, предложенный Ф. Баччелли
5Massoulie L. Stability of поп markovian polling systems // Queueing Systems. 1995. V. 21, № 1,2. P. 67-96.
6Chen, H. and Mandelbaum, A. Discrete flow networks: Bottlenecks analysis and fluid approximations // Math. Oper. Pes. 1991. V. 16. P. 408-446.
7Dai, J.G. On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid models // Ann. Appl. Probab. 1995. V. 5. P. 49-77.
8Фалин Г.И. О сходимости процессов обслуживания в структурно-сложных системах с потерями к стационарным // Теория вероятностей и ее применения. 1987. Т.32, К' 3. С. 577-580.
и С. Г. Фоссом9, и метод жидкостной аппроксимации, развитый в недавних работах А. Н. Рыбко и А. Л. Столяра10, Д. Г. Дай, Ш. П. Майна11. Основное различие между системами поллинга и неполнодоступными системами и, как следствие, между подходами к их изучению, состоит в том, что системы поллинга обладают определенными свойствами монотонности, что позволяет развить некоторый подход к исследованию предельного поведения сложных систем при весьма общих (немарковских) стохастических предположениях, основываясь на идеях метода разделения. Для исследования эргодичности неполнодоступных систем, не обладающих такими свойствами монотонности, в работе используется метод жидкостной аппроксимации.
Основные результаты диссертации
1. Для класса систем поллинга со стационарным, метрически транзитивным входным потоком и регенерирующим маршрутом прибора, дисциплины обслуживания в которых удовлетворяют некоторым свойствам монотонности и могут быть случайными, доказано существование стационарного режима в системе с нулевыми начальными условиями при выполнении условия вида (1). Доказано, что этот стационарный режим является в некотором смысле минимальным среди всех возможных. Кроме того, построен некоторый максимальный (в том же смысле) стационарный режим. Для систем с ненулевыми начальными условиями доказано, что выполнение условия вида (1) влечет ограниченность суммарной длины очереди. Доказана необходимость условия р < 1 для ограниченности очереди.
-
В тех же предположениях относительно входного потока и маршрута прибора, для класса систем поллинга с произвольными дисциплинами обслуживания установлена достаточность условия вида (1) для ограниченности (по вероятности) суммарной длины очереди.
-
Получено обобщение этих результатов для систем поллинга с бесконечным (счетным) числом очередей.
9ВассеШ F., Foss S. On the saturation rule for the stability of queues // J.AppI.Probab. 1995, V. 32, N» 2. P. 494-507.
10Рыбко A.H., Столяр А.Л. Об эргодичности-случайных процессов, описывающих функционирование открытых сетей массового обслуживания // Проблемы передачи информации. 1992. Т. 28. С. 2-26.
"Dai, J.G. and Meyn, S.P. Stability and convergence of moments for multiclass queue-ing networks via fluid limit models // IEEE Transaction on Automatic Control, 1994 (to appear).
4. Аналогичные результаты получены для сетей поллинга с возмож
ными переходами вызовов с одной станции на другую, а также для систем
с групповым поступлением вызовов.
5. Для класса неполнодоступных систем обслуживания выделены
два широких подкласса систем, в которых времена обслуживания вызо
вов ассоциированы либо со станциями, либо с типами вызовов и правило
выбора одной из доступных станций удовлетворяет свойству, названно
му «асимптотической отделимостью». Для каждого из этих подклассов в
предположениях, что входной поток и процессы обслуживания — взаим
но независимые процессы вида GI[GI, доказано существование (при вы
полнении условий нагрузки) стационарного режима для системы с произ
вольными начальными условиями и сходимость к нему в метрике полной
вариации.
Такое же утверждение получено для системы с двумя станциями, в которой время обслуживания вызова зависит как от типа вызова, так и от станции, на которой этот вызов обслуживается, и выбор станции определяется правилом наименьшего времени ожидания.
Результаты, включенные в диссертацию, являются новыми.
Апробация работы
Результаты диссертации докладывались на VI Белорусской зимней школе-семинаре по теории массового обслуживания (Витебск, январь-февраль 1990 г.), научно-исследовательском семинаре под руководством Р. Л. Добрушина (ИППИ РАН), международном семинаре «Предельные теоремы теории вероятностей и смежные вопросы» (Омск, август-сентябрь 1995 г.), на объединенном семинаре кафедры теории вероятностей и математической статистики НГУ и лаборатории теории вероятностей и математической статистики ИМ СО РАН под руководством А. А. Боровкова.
Публикации
По теме диссертации опубликованы 5 работ, три из которых — в соавторстве с научным руководителем. Кроме того, две совместные работы сданы в печать.
Структура и объем диссертации
Диссертация состоит из введения и двух глав, которые делятся на 13 параграфов (1.1 - 1.7, 2.1 - 2.6). Формулы нумеруются отдельно во введении и внутри каждой главы. Нумерация утверждений двойная: например, теорема 2.3 является третьей теоремой главы 2. Общий объем диссертации 105 страниц, список литературы содержит 47 наименований.
