Эргодические теоремы для сложных стохастических моделей обслуживания тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ им. С. Л. СОБОЛЕВА

На правах рукописи УДК 519.21

Чернова Наталья Исааковна

ЭРГОДИЧЕСКИЕ ТЕОРЕМЫ ДЛЯ СЛОЖНЫХ СТОХАСТИЧЕСКИХ МОДЕЛЕЙ ОБСЛУЖИВАНИЯ

(01.01.05 — теория вероятностей и математическая статистика)

/

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Новосибирск 1996

Работа выполнена на кафедре теории вероятностей и математической статистики Новосибирского государственного университета.

научный руководитель — доктор физико-математических наук, профессор С.Г.Фосс.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор физико-математических наук,

профессор В.В.Калашников, доктор физико-математических наук, профессор А.А.Могульский.

ведущая организация — Институт Проблем Передачи Информации РАН.

£>р

Защита состоится " " 1996 г. в "__" часов

на заседании Специализированного совета Д.002.23.03 при Институте математики СО РАН по адресу: 630090, Новосибирск, Университетский проспект, 4, к.417, Институт математики СО РАН.

С диссертацией можно ознакомиться в библиотеке Института математики СО РАН.

Автореферат разослан " ^^ "_~{<Я— 1996 г.

Ученый секретарь Специализированного совета Д.002.23.03 при Институте математики СО РАН д.ф.-м.н. (Лч^Сд— А.В.Косточка

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Одной из важных задач современной теории массового обслуживания является изучение асимптотического (с ростом времени) поведения случайных процессов, характеризующих состояние систем обслуживания; в частности, выяснение условий сходимости этих процессов к предельным, соответствующим так называемому стационарному режиму работы. В последнее время особенно интенсивно исследуются модели систем и сетей обслуживания, возникающих в реальных приложениях и имеющих, как правило, достаточно сложную структуру.

Данная работа посвящена изучению предельного поведения двух классов систем обслуживания:

I) систем поллинга,

II) неполнодоступных систем.

Системами поллинга называют системы, состоящие из нескольких станций (или очередей), входного потока вызовов и одного прибора, обслуживающего очереди последовательно и переходящего из одной очереди в другую в соответствии с некоторым случайным маршрутом. Задаются также алгоритмы, определяющие число вызовов, обслуживаемых за один визит прибора в каждую очередь (в дальнейшем вместо термина «алгоритм» мы будем использовать термин «дисциплина обслуживания») .

Понятие «неполнодоступности» систем не имеет четкого определения, трактуется различными авторами по-разному и связано с некоторыми ограничениями на маршруты поступающих в систему вызовов, определяемыми их внутренними характеристиками. В данной работе под непол-нодоступной понимается система обслуживания, входной поток в которую состоит из вызовов различных типов, причем тип вызова определяет множество доступных этому вызову параллельно работающих станций обслуживания. Среди этих станций вызов выбирает одну по некоторому правилу (в зависимости от состояния системы в момент поступления вызова), обслуживается на ней в порядке очереди и покидает систему по окончании обслуживания.

Достаточно давно известно, каковы должны быть естественные условия «стабильности» для систем поллинга, однако вопрос о существовании стационарного режима и сходимости к нему допредельных процессов при выполнении этих условий долго оставался открытым. В последнее время появился ряд статей, в которых доказана сходимость процесса длины очереди к стационарному режиму (который является единственным)

для широкого класса моделей поллинга в марковских предположениях. В этих работах рассматриваются системы с пуассоновскими независимыми входными потоками и взаимно независимыми последовательностями времен обслуживания на каждой станции.

Так, например, А. А. Боровков и Р. Шассбергер1 рассмотрели марковскую модель поллинга, в которой после посещения очереди г прибор переходит в очередь ] с вероятностью за время WiJ со средним , а число вызовов, обслуженных за один визит прибора в г-ю очередь, имеет вид /(х,Х,) = гшп(2, где х — длина этой очереди в момент прихода прибора и X,- — случайная величина. Доказано, что необходимым и достаточным для эргодичности такой системы является следующее условие:

Здесь Л,- — интенсивность входного потока на станцию г, <т,- — среднее время обслуживания на этой станции, w = niPi,jwi,j — среднее время перехода между последовательно посещаемыми очередями для стационарного распределения {7г,-}|11 матрицы (pij), и F,- = EL,-.

К. Фрикер и М. Р. Джайби2 рассмотрели систему поллинга с периодическим (не обязательно циклическим) маршрутом прибора и случайными дисциплинами обслуживания произвольного вида, удовлетворяющими некоторым условиям стохастической монотонности. Доказано, что условие вида (1) необходимо и достаточно для эргодичности такой системы. Ранее JI. Георгиадис и В. Шпаньковски3 получили аналогичный результат для циклических систем поллинга с ограниченными дисциплинами обслуживания.

Вопросы существования стационарного режима для систем поллинга в общих предположениях относительно входного потока рассматривались лишь в нескольких работах. Е. Альтман и С. Г. Фосс4 получили условия эргодичности системы поллинга с т.н. «неограниченными дисциплинами обслуживания» и входным потохом, образованным последовательностью

1 Borovkov А.А., Schassberger R. Ergodicity of a polling network // Stochast. Process, and Appl. 1994. V. 50. P. 253-262.

2FrickerC., 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.№ 1992.

(1)

независимых, одинаково распределенных случайных величин.

JI. Массули5 исследовал систему поллинга со стационарным и метрически транзитивным входным потоком, марковским маршрутом прибора и монотонными в некотором смысле дисциплинами обслуживания, зависящими от случайного аргумента. Существование стационарного режима

для системы с нулевыми начальными условиями доказано при выполне-

к к д

нии следующего условия (ср. с (1)): V^ А,с,- + V^ —'—w < 1. Показа-

t! Ы KiFi

но также, что построенный стационарный режим является в некотором стохастическом смысле минимальным для систем с ненулевыми начальными условиями.

В последнее время широко исследуются системы с несколькими типами вызовов. Системы, в которых вызову одного типа доступно только одно обслуживающее устройство, изучались, например, в работах 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, и метод жидкостной аппроксимации, развитый в недавних работах А. Н. Рыбко и A. JI. Столяра10, Д. Г. Дай, Ш. П. Майна11.

Основное различие между системами поллинга и неполнодоступными системами и, как следствие, между подходами к их изучению, состоит в том, что системы поллинга обладают определенными свойствами монотонности, что позволяет развить некоторый подход к исследованию предельного поведения сложных систем при весьма общих (немарковских) стохастических предположениях, основываясь на идеях метода разделения. Для исследования эргодичности неполнодоступных систем, не обладающих такими свойствами монотонности, в работе используется метод жидкостной аппроксимации.

Основные результаты диссертации

1. Для класса систем поллинга со стационарным, метрически транзитивным входным потоком и регенерирующим маршрутом прибора, дисциплины обслуживания в которых удовлетворяют некоторым свойствам монотонности и могут быть случайными, доказано существование стационарного режима в системе с нулевыми начальными условиями при выполнении условия вида (1). Доказано, что этот стационарный режим является в некотором смысле минимальным среди всех возможных. Кроме того, построен некоторый максимальный (в том же смысле) стационарный режим. Для систем с ненулевыми начальными условиями доказано, что выполнение условия вида (1) влечет ограниченность суммарной длины очереди. Доказана необходимость условия р < 1 для ограниченности очереди.

2. В тех же предположениях относительно входного потока и маршрута прибора, для класса систем поллинга с произвольными дисциплинами обслуживания установлена достаточность условия вида (1) для ограниченности (по вероятности) суммарной длины очереди.

3. Получено обобщение этих результатов для систем поллинга с бесконечным (счетным) числом очередей.

9ВассеШ F., Foss S. On the saturation rule for the stability of queues // J.Appl.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. Для класса неполнодоступных систем обслуживания выделены два широких подкласса систем, в которых времена обслуживания вызовов ассоциированы либо со станциями, либо с типами вызовов и правило выбора одной из доступных станций удовлетворяет свойству, названному «асимптотической отделимостью». Для каждого из этих подклассов в предположениях, что входной поток и процессы обслуживания — взаимно независимые процессы вида а [а, доказано существование (при выполнении условий нагрузки) стационарного режима для системы с произвольными начальными условиями и сходимость к нему в метрике полной вариации.

Такое же утверждение получено для системы с двумя станциями, в которой время обслуживания вызова зависит как от типа вызова, так и от станции, на которой этот вызов обслуживается, и выбор станции определяется правилом наименьшего времени ожидания.

Результаты, включенные в диссертацию, являются новыми.

Апробация работы

Результаты диссертации докладывались на VI Белорусской зимней школе-семинаре по теории массового обслуживания (Витебск, январь-февраль 1990 г.), научно-исследовательском семинаре под руководством Р. Л. Добрушина (ИППИ РАН), международном семинаре «Предельные теоремы теории вероятностей и смежные вопросы» (Омск, август-сентябрь 1995 г.), на объединенном семинаре кафедры теории вероятностей и математической статистики НГУ и лаборатории теории вероятностей и математической статистики ИМ СО РАН под руководством А. А. Боровкова.

Публикации

По теме диссертации опубликованы 5 работ, три из которых — в соавторстве с научным руководителем. Кроме того, две совместные работы сданы в печать.

Структура и объем диссертации

Диссертация состоит из введения и двух глав, которые делятся на 13 параграфов (§1.1 - 1.7, §2.1 - 2.6). Формулы нумеруются отдельно во введении и внутри каждой главы. Нумерация утверждений двойная: например, теорема 2.3 является третьей теоремой главы 2. Общий объем диссертации 105 страниц, список литературы содержит 47 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении приводятся краткий обзор литературы, постановка задач и основные результаты диссертации.

Глава 1 посвящена изучению систем поллинга. В §1.1 рассматривается основная модель поллинга следующего вида. Имеется К < оо станций (очередей) и стационарный, метрически транзитивный входной поток {тп, /»п. °"п}£°=_оо ■ Здесь тп — интервалы между моментами прихода вызовов, Ет1 = Л-1 > 0, — номер станции, на которую направляется п-й вызов, = к) = рк, <тп — его время обслуживания, Естх = а < оо.

Маршрут обслуживающего прибора не зависит от входного потока и задается последовательностью в которой {г^} — номера

последовательно посещаемых станций, и^- — время перехода прибора из очереди с номером ц в очередь с номером Предполагается, что последовательность { ^, ги^} можно разбить на независимые, одинаково распределенные участки случайной длины (циклы). Пусть \У < оо — среднее суммарное время переходов прибора за «типичный» цикл, С к < оо — среднее количество посещений очереди к за цикл.

Если прибор, прибывая на станцию к в;'-й раз, застает х вызовов в очереди, он обслуживает первые Д (х, 1Ук) < х вызовов из них и затем переключается на следующую станцию своего маршрута. Обслуженные вызовы покидают систему. Здесь (для любого к) случайные величины Щ., ] = 0, ±1, ±2,... независимы и одинаково распределены и не зависят от входного потока и маршрута прибора. Предполагается также, что

р(Л(1,^) = 1)>о.

Рассматриваются следующие три класса, которым могут принадлежать дисциплины обслуживания:

1) класс произвольных измеримых функций с целыми неотрицательными значениями В = {/ : х И —> для /6 В обозначим ^(у) = Шпш^-юо /(х, у) < оо;

2) класс В = {/ : существует Итг_юо/(¡с, у) = Р(у) < оо, /(х, у) < Р(у) для всех х, у);

3) класс М = {/ : /(х, у) < /(х + 1, у) < /(х,у) ■+ 1 для всех х,у}.

Если Д принадлежит одному из этих классов, обозначим Гк =

< оо).

Во всех известных автору работах, посвященных системам поллинга, рассматривались системы с дисциплинами из класса М.

Положим р = А[сг + max J*k W].

\<к<к r^Cfc

В §1.1 сформулированы следующие утверждения. Для систем с дисциплинами обслуживания из класса В справедлива

Теорема 1.1. Если р < 1, то (при любых начальных условиях) суммарная длина очереди в системе ограничена по вероятности.

Хорошо известно, что в случае р = 1, вообще говоря, может иметь место как ограниченность, так и рост до бесконечности длины очереди в зависимости от стохастических предположений.

Для систем с дисциплинами из класса В справедлива

Теорема 1.2. Если р > 1, то (при любых начальных условиях) суммарная длина очереди по вероятности неограниченно возрастает.

Утверждение теоремы 1.2, вообще говоря, неверно для систем с дисциплинами из класса В\В, т. е. ограниченность по вероятности длины очереди может иметь место и при р > 1. Соответствующий пример приведен в §1.3.

Утверждение о существовании стационарного режима сформулировано в терминах каплинг-сходимости к некоторому стационарному (в смысле Пальма) процессу.

Определение 1. Пусть X, Y — случайные элементы на вероятностном пространстве (fi,^7, Р). Назовем X копией Y, если существует взаимно-однозначное, ^-измеримое, сохраняющее меру преобразование сдвига 9 на Q такое, что Х(ы) = Y(0u>) для всех ш.

Определение 2. Будем говорить, что процесс X(t) стационарен в смысле Пальма (относительно последовательности вложенных моментов времени {Тп}, где То = О, Т„ = Tn-i + т„), если для любого п процесс {Xn(t) = X(t + T„),t > 0} является копией процесса {X(t),t > 0}.

Определение 3. Пусть X и Y — два процесса, соответствующие различным стационарным режимам в рассматриваемой системе поллин-га. Будем говорить, что X меньше (больше) У, если время освобождения системы, работающей в стационарном режиме X, от вызовов, пришедших не позже момента Тт (если после этого момента вызовы не поступают), по распределению меньше (больше) соответствующего времени для системы со стационарным режимом Y.

Предположим далее, что маркированный точечный процесс, точками

которого являются моменты начала циклов маршрута в пустой системе, и марками — сами циклы, стационарен в непрерывном времени.

Для системы с таким маршрутом и дисциплинами из класса М справедлива

Теорема 1.3. 1). Если р < 1, то процесс {У[_п т характеризующий состояние системы с нулевыми начальными условиями, в которую поступают вызовы с номерами —п,..., т, сходится при п,т —»■ оо к некоторому стационарному (в смысле Пальма) процессу оо <t < оо}. Сходимость понимается в следующем смысле: для любого т = 1,2,... существует последовательность {У"'"1}^! копий процесса {Х(<),0 < £ < Тт}, для которой

Р(У[-„,т] ¿УП1т)-+0 при П-> сю.

Процесс Х{1) определяет минимальный стационарный режим работы системы (в смысле определения Ъ). Существует максимальный стационарный режим.

2). Если р > 1, то суммарная длина очереди неограниченно возрастает п.н.

Из теоремы 1.3 вытекает, в частности,

Следствие 1.1. При р < 1 процесс {У[_„100)(<),< > 0} сходится к стационарному (в смысле Пальма) процессу > 0} : существует

последовательность {У > 0} копий процесса > 0} такая,

что Р(У[-п,оо)(*) ф УП(<М > 0) 0 при п ->• оо.

В теореме 1.3 получена так называемая каплинг-сходимость процессов У[_п т] к предельному, которая, как известно, эквивалентна сходимости в метрике полной вариации. Процесс X(¿) определяет стационарный (в смысле Пальма) режим на всей оси.

Замечание. Вообще говоря, стационарный режим в системе может быть не единственным. В зависимости от начальных условий возможна сходимость к различным стационарным процессам. Более того, при отличных от нуля начальных условиях сходимости к стационарному процессу может и не быть. В §1.5 приводятся соответствующие примеры.

В §1.2 доказываются теоремы сравнения для детерминированных моделей поллинга, являющихся реализациями на одном элементарном исходе рассматриваемых в §1.1, 1.3 - 1.7 стохастических систем поллинга. Показывается, что для двух систем Ей Ее дисциплинами из класса М момент окончания обслуживания конечного числа вызовов в системе Е больше, чем в Е, если

а) вызовы в систему Е приходят позже, чем в Е;

б) количество обслуживаемых на любой станции за один визит прибора вызовов (при одинаковой длине очереди) в системе Е больше, чем в системе Е.

В §1.2 также показано, что класс М в некотором смысле «плотен» в В: любая функция из класса В может быть ограничена поточечно сверху и снизу функциями из М, имеющими одинаковый предел при х —> оо. Последнее свойство используется при доказательстве теорем 1.1, 1.2 в §1.3.

Доказательство теорем 1.1 - 1.3 в §1.3 - 1.5 опирается на идеи метода разделения и основывается на свойствах монотонности систем поллинга. Однако прямое применение метода разделения оказывается невозможным в силу того, что некоторые существенные свойства («внутренняя монотонность», «отделимость», «субаддитивность» п.н.), на выполнении которых основан этот метод, для систем поллинга, вообще говоря, места не имеют. Связано это с наличием не зависящего от входа управляющего параметра (маршрута прибора).

Предложено рассмотреть на том же вероятностном пространстве систему, маршрут прибора в которой стационарен в непрерывном времени. Характеристики этой системы оказываются связаны с характеристиками исходной системы некоторыми свойствами солидарности, обеспечивающими одинаковое предельное поведение.

Вводя сдвиг моментов начала циклов маршрута на некоторые величины, зависящие от входного потока, можно получить заданный на одном вероятностном пространстве набор «одинаково распределенных» систем поллинга, который удовлетворяет требованиям внутренней монотонности и так называемой случайной субадцитивности. Эта конструкция проводится в §1.3 - 1.4 и позволяет построить (при выполнении естественных условий нагрузки) на том же вероятностном пространстве процесс, определяющий стационарный режим в системе. Построению этого процесса посвящен §1.5.

В §1.6 получены обобщения теорем 1.1 - 1.3 для систем поллинга с бесконечным (счетным) числом станций в предположениях §1.1.

Пусть (рк — случайная величина, имеющая распределение числа посещений очереди к за «типичный» цикл, 5к = Р(Д(1, Dj.) > 0) > 0. Обозначим через /Зк = Е[1 — (1 — Sk)'pk] вероятность того, что если в начале цикла на станции к находится один вызов и новые вызовы не поступают, то он будет обслужен за этот цикл.

Показано, что условие X^Pfe/A < 00 является достаточным и, в известном смысле, необходимым для выполнения утверждений, аналогичных теоремам 1.1 - 1.3.

А именно, при выполнении условия нагрузки

p=A[<r+sup-=^W]<l к ïk^k

справедливо первое утверждение теоремы 1.3.

Если, напротив, р > 1, то найдется натуральное К такое, что с ростом времени суммарная длина очереди на первых К станциях стремится к бесконечности.

В §1.7 утверждения теорем 1.1 - 1.3 обобщаются на случай систем поллинга с переходами вызовов. Предполагается, что с каждой станцией ассоциируется последовательность случайных величин, определяющих номер станции, на которую направляется очередной вызов после обслуживания на данной станции.

Такая система может быть описана как композиция «простых» систем поллинга (систем с одним поступающим вызовом) аналогично тому, как это делается в работе Ф. Баччелли, С. Г. Фосса12 для систем джек-соновского типа.

При этом остаются справедливы утверждения теорем 1.1 - 1.3, условие эргодичности в которых будет выглядеть следующим образом:

p = A[cr+ max-A-W]<l,

где а — среднее суммарное время обслуживания вызова в «простой» системе, фк — среднее число посещений вызовом в «простой» системе станции к.

В том же параграфе полученные результаты обобщаются на системы с более сложным стационарным входным потоком. В частности, показывается, что утверждения теорем 1.1 - 1.3 сохраняются без изменений, если ввести следующие стохастические предположения. Пусть

12Baccelli F., Foss S. Ergodicity of Jackson-type queueingnetworks // Queueing Systems. 1994. V. 17. P. 5-72.

{т~п, ¡¿п, <?п) — стационарная, метрически транзитивная последовательность, в которой г„ — время между моментами прихода п — 1-й и п-й группы вызовов; р„ = (¡лп д, ...,цп,к) — количество вызовов п-й группы, направляемых в очереди 1,..., К соответственно; ап — (<?пд,..., &п,к), где от,^ — вектор времен обслуживания вызовов п-й группы на станции к. Через а обозначается среднее суммарное время обслуживания «ти-

Фк

пичной» группы вызовов; 0 < Е//1 к = фк <с оо, р = А[сг + шах РУ].

В главе 2 рассматриваются неполнодоступные системы обслуживания. Исследование эргодичности неполнодоступных систем проводится в предположениях независимости и одинаковой распределенности величин, образующих входной поток и процессы обслуживания. Для получения условий возвратности по Харрису соответствующих марковских процессов используется метод жидкостной аппроксимации. Применение марковских методов исследования для таких систем, в отличие от систем поллинга, связано с тем, что для рассматриваемых систем не удается обнаружить требуемые в главе 1 (или аналогичные) свойства монотонности. В §2.5 приведены примеры отсутствия каких-либо свойств монотонности характеристик неполнодоступных систем в зависимости от моментов прихода вызовов во входном потоке или от времен обслуживания.

В §2.1 рассматривается следующая модель. Имеется К станций (очередей) с неограниченным числом мест ожидания. Каждая станция обслуживается одним прибором. Входной поток в систему определяется независимыми последовательностями независимых, одинаково распределенных величин {г„}, {Фп), где тп — интервал между моментами прихода вызовов и ф„ — тип вызова, Р(фп = А) = р а- Вызов, получивший тип А ф 0, А С Б = {1,..., Л'}, может обслуживаться только на станциях с номерами из множества А. Среди этих станций вызов, в зависимости от состояния системы, выбирает одну в соответствии со следующим правилом, которое названо в работе правилом «асимптотической отделимости».

Для произвольного множества А = {¿1,...,гт} и к £ А обозначим через -Рд(2/11, • • •, 2/<т) вероятность вызову типа А выбрать для обслуживания станцию к, если у^,..., у%т — длины очередей на станциях множества А. Предполагается, что для всех А и к £ А функция Рд : Ъ™ —¥ [0,1] удовлетворяет свойству

(АО): Для любого С/ С А и любой последовательности (у,-, (п), ...,1Лт (п))

такой, что |у(п)| = Vij(n) —оо и

Г liminfn yJy(n)/|y(n)| > 0 для ij£U, \ limsupn У;Дп)/|г/(п)| = 0 для ij g U,

существует предел

lim £ рЦ{уи (п),..., yim (п)) ЕЕ Ga(U) G [0,1]. " кеи

Введенное правило означает следующее: как только очереди на одном множестве станций становятся «очень большими» по сравнению с очередями на другом множестве, вызов оказывается на одной из станций первого множества с вероятностью, не зависящей от конкретных длин очередей. Это правило включает, например, так называемые правило кратчайшей очереди и правило наименьшего времени ожидания.

По окончании обслуживания вызов покидает систему.

В §2.1 рассмотрены две модели обслуживания.

В модели 1 времена обслуживания ассоциируются со станциями: независимо от типа j-й по счету вызов на станции к обслуживается время <rk(j), и для любого к случайные величины аk(j) независимы и одинаково распределены со средним Ьк. Последовательности времен обслуживания на разных станциях независимы.

В модели 2 времена обслуживания ассоциируются с типом вызова: независимо от станции, j-й по счету вызов типа А обслуживается время &а(]} со средним 6д (при аналогичных предположениях независимости).

Для первой модели величина нагрузки определяется следующим образом: г / \

= maxj А Рс/+ JT puuvGuuv(U)J /

- 14 UCA ^ VCS\A,K?i0 ' fcgA

Аналогично выглядит нагрузка для второй модели. Пусть {Х(п)} — цепь Маркова, характеризующая состояние системы в моменты поступления вызовов. В предположении, что распределение величины Tj не ограничено, в §2.1 для моделей 1 и 2 сформулировано утверждение:

Теорема 2.1. При выполнении условия р < 1 можно задать на одном вероятностном пространстве с {.Х(п)} стационарную эргодиче-скую последовательность {X'")} такую, что

Р(Х(ГО) = Х^т\т = п, n+ 1,...)-» 1 при п —У сх> при любом начальном условии Х(0).

■

Условие р < 1 для описанных выше систем, вообще говоря, не является необходимым условием для ограниченности очереди. Соответствующий пример приведен в §2.3. Однако в предположении Ол{и) = 0 для любых А С {1,..., К}, и С А, справедлива

Теорема 2.2. Если р > 1, то найдется А С {1,..., К}, такое что суммарная длина очереди на станциях из множества А неограниченно возрастает п.н.

§2.2 носит вспомогательный характер. В нем излагаются известные идеи метода жидкостной аппроксимации и доказывается существование жидкостной модели для рассматриваемой системы обслуживания.

В §2.3 проводится доказательство стабильности полученной жидкостной модели, непосредственным следствием чего является (в силу утверждений §2.2) теорема 2.1. Здесь же доказана теорема 2.2.

§2.4 посвящен изучению общей модели обслуживания: с каждой станцией и каждым типом вызова, которому доступна данная станция, ассоциируется последовательность независимых, одинаково распределенных времен обслуживания {о"дО')} _/-го вызова типа А на станции к, и все эти последовательности взаимно независимы. Рассматривается лишь правило выбора очереди с наименьшим временем ожидания начала обслуживания.

Для системы из двух станций и трех типов вызовов выписаны необходимые и достаточные условия нагрузки (теорема 2.5), при которых справедливы утверждения теорем 2.1 и 2.2.

Для системы из трех (и более) станций показано, что пропускная способность такой системы не может, вообще говоря, быть определена в терминах жидкостной модели или в терминах интенсивностей входного потока и процессов обслуживания. Приведен пример (см. пример 2.3), показывающий, что длина очереди в рассматриваемой системе может как быть ограниченной, так и расти до бесконечности в зависимости от начальных условий.

В §2.6 предположения независимости и одинаковой распределенности для входного потока заменяются условиями регулярности, сформулированными С. Г. Фоссом13. Показывается, что при некоторых дополнительных условиях на распределения времен обслуживания (аналогичных

13Фосс С .Г. Некоторые свойства открытых сетей обслуживания / / Проблемы передачи информации. 1989. Т. 25. С. 90-97.

условиям А. А. Боровкова14), без каких-либо предположений, делающих систему марковской, можно для моделей 1 и 2, введенных в §2.1, получать утверждения о положительной возвратности процесса характеризующего состояние системы в момент времени I, в дискретном или непрерывном времени, а также экспоненциальные оценки времени возвращения в некоторое замкнутое множество. Соответствующее утверждение сформулировано в лемме 2.7.

В том же параграфе приводится обобщение результатов §2.1 для систем с регенерирующим входным потоком.

Автор выражает глубокую благодарность своему научному руководителю Сергею Георгиевичу Фоссу за постановку задач и постоянную помощь в работе.

1. (Совместно с С. Г. Фоссом) Об эргодичности многоканальных не-полнодоступных систем связи // Проблемы передачи информации. 1991. Т. 27, № 2. С. 9-14.

2. (Совместно с С. Г. Фоссом) Об эргодичности многоканальных не-полнодоступных систем обслуживания // Математические методы исследования сетей связи и сетей ЭВМ: Тез. докл. (VI Белорусская зимняя школа-семинар по теории массового обслуживания, Витебск, январь-февраль 1990). Минск. 1990. С. 147-148.

3. Условия эргодичности для одного класса систем обслуживания // Математический анализ и дифференциальные уравнения: Межвуз. сб. науч. тр.: Новосиб. гос. ун-т, Новосибирск. 1991. С. 94-98.

4. (Совместно с С. Г. Фоссом) Эргодические свойства систем поллин-га. Новосибирск, 1995. 47 с. (Препринт / РАН. Сиб. отд-ние. Ин-т математики; № 6).

5. Эргодические свойства систем поллинга // Предельные теоремы и смежные вопросы. Тез. докл. Междун. семинара. Омск: Омский гос. ун-т, 1995. С. 57-58.

6. (Совместно с С. Г. Фоссом) Теоремы сравнения и эргодические свойства систем поллинга // Проблемы передачи информации (в печати).

7. (Совместно с С. Г. Фоссом) О системах поллинга с бесконечным числом станций. // Сиб. мат. журн. (в печати).

14А.А.Боровков. Предельные теоремы для сетей обслуживания. I // Теория вероятностей и ее применения. 1986. Т. 31, К® 3. С. 474-490.

Публикации по теме диссертации