Метод жидкостной аппроксимации и его применение к исследованию систем поллинга с несколькими приборами тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

УДК 519.21

Ковалевский Артём Павлович

Метод жидкостной аппроксимации и его применение к исследованию систем поллинга с несколькими приборами

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

Диссертация на соискание ученой степени кандидата физико-математических наук

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

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

СОДЕРЖАНИЕ

Введение 3

Глава 1. Метод жидкостной аппроксимации 12

1.1 Построение стохастической жидкостной модели......................12

1.2 Возвратность и положительная возвратность............19

1.2.1 Возвратность.................. .........20

1.2.2 Положительная возвратность.................24

1.3 Свойство подобия жидкостных пределов ...............26

1.4 Теорема о возвратности.........................29

1.5 Теорема о положительной возвратности...............32

1.6 Примеры применения жидкостной аппроксимации к анализу систем обслуживания...........................41

1.6.1 Одноканальная система обслуживания........... . 42

1.6.2 Сеть обслуживания..................................42

1.6.3 Система обслуживания с переключениями..........46

1.6.4 Примеры к условиям возвратности............................53

Глава 2. Системы поллинга с несколькими приборами 55

2.1 Общая модель..............................55

2.2 Существование жидкостной модели ................59

2.3 Исчерпывающая дисциплина обслуживания.............63

2.3.1 Свойства жидкостных пределов.................63

2.3.2 Случай двух станций......................69

2.3.3 Циклический поллинг.......................88

2.4 Ограниченные дисциплины обслуживания..............90

2.4.1 Свойства жидкостных пределов................90

2.4.2 Случай двух станций......................95

Литература 100

ВВЕДЕНИЕ

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

Ключевая идея метода состоит в следующем. Рассматривается марковский процесс Ь > 0}, характеризующий динамическое состояние системы в

момент времени t. Вводится линейное масштабирование (сжатие) по пространственной координате и времени в ¡Х(0)| раз, и изучаются масштабированные

А Л

версии процесса X, подчиненные тому условию, что ¡Х(0)( = 1. Рассматривается семейство процессов, предельных для последовательностей масштабированных процессов в смысле слабой сходимости. Такое семейство называется жидкостной моделью, а процессы {<£>(£); Ь > 0} из этого семейства называются жидкостными пределами. Вводятся различные условия стабильности жидкостной модели, достаточные для положительной возвратности исходного процесса.

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

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

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

Метод жидкостной аппроксимации развит в работах [1-14] и применен к исследованию систем поллинга (с одним прибором и с несколькими одинаковыми приборами) в работах [8], [9].

В статье [1] изучается стохастическая система массового обслуживания с 2 станциями и 4 типами вызовов. Показано, что при дисциплине обслуживания спениальното вида естественные условия положительной возвратности не являются достаточными, тогда как при обслуживании вызовов на каждой станции в порядке поступления — являются достаточными (пример системы, для которой естественные условия положительной возвратности не являются достаточными при обслуживании вызовов на каждой станции в порядке поступления, приведен в работе [15]). Получено следующее условие эргодичности:

Пусть существует конечная константа Т такая, что для любого жидкостного предела о?

= 0 п.и. для всех I > Т. (1)

Тогда рассмативаемая система, обслуживания эргодична.

В [2] жидкостная модель применяется для изучения детерминированного варианта сетей Джексона. Получены условия перегруженности и недогруженное!'и станций в такой системе.

В [3] метод жидкостной аппроксимации последовательно применен к ряду систем обслуживания с несколькими типами вызовов в весьма общих стохастических предположениях. Здесь жидкостные пределы понимаются как траектории слабых пределов последовательностей масштабированных процессов (что позволило исключить из рассмотрения вероятностное задание предельных процессов). Показано, что условие ( I ) достаточно для положительной возвратности и (при некоторых дополнительных предположениях) эргодичности таких систем. В частности, получено новое доказательство эргодичности обобщенной сети Джексона.

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

В статье [5] для сетей обслуживания показано, что жидкостная модель стабильна тогда и только тогда, когда стабильна так называемая «незадержанная» (щкЗе!ауес1) жидкости ал модель, что позволяет работать напрямую с

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

М, [П, М-

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

В [7] исследован класс сетей обслуживания с фиксированным маршрутом вызовов и зависимыми временами обслуживания вызова на различных этапах его маршрута.

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

N \

V А,+ А шах < 1,

4=1 *

где N — число станций; А,; — интенсивность прихода вызовов на станцию ц О,; — среднее время обслуживания вызовов на станции ¡¡; Д — среднее суммарное время переключений за цикл; к\ — максимальное число вызовов на станции г, обслуживаемых за 1 визит прибора на станцию.

В [9] аналогичные результаты полу йены для систем поллинга с несколькими одинаковыми приборами в предположении, что маршруты приборов задаются неразложимой цепью Маркова. Условия положительной возвратности и невозвратности получены для неограниченных и ограниченных дисциплин обслуживания: система положительно возвратна при р < 1 и невозвратна при р > 1, где

д V,

л — — ( N г>• А• 4- А '■"ах ——■ ^

Мч " ' \<\<п У *'

•"4-1 --

Здесь с,; — среднее число посещений станции г за цикл (циклом называется интервал времени меж л у двумя последовательными возвращениями прибора

на некоторую фиксированную станцию).

В работе [10] метод жидкостной аппроксимации применен к анализу открытых сетей обслуживания с пуассоновскими входными потоками, показательными временами обслуживания и широким классом «консервативных» дисциплин обслуживания. Жидкостная модель определяется как замыкание (относительно равномерной сходимости на компактных множествах) семейства траекторий предельных процессов. Доказано свойство подобия жидкостных пределов. Для детерминированных жидкостных пределов показано, что условие стабильности жидкостной модели i эквивалентно одному из следующих:

Для любого жидкостного предела ф существуют константы Т' и е (0, 1] такие, что:

ИТ')|<1-£ П.Н. (2)

Или:

Для любого жидкостного предела (р выполнено:

mí \u?{tM < 1 п.н. t>о'7 к "

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

Условия невозвратности случайных процессов, описывающих состояние открытых сетей обслуживания, в терминах жидкостной модели исследовались в ткут [iii

В [12] показано, что достаточно выполнения условия: существуют mо > 1, да > 0, be, > 0 такие, что для всех <р имеет место:

¡^(О! ^ ~'°о + ío "v^ п.н. для всех t > 0. (3)

В [13] предложено другое условие невозвратности: существует константа 7' > 0 такая, что для любого решения жидкостных уравнений 'у?, удовлетворяющего условию у?(0) = 0, выполнено \<р{Т)\ > 0.

В [14] рассмотрены случайные жидкостные пределы и предложено более общее понятие стабильности жидкостной модели: жидкостная модель называется Lp - стабильной, р > 0, если вир Щ(р{1)\*> 0 при í -* оо. Показана эквивалентность -став ильности жидкостной модели и различных определений стабильности исходного марковского процесса.

Для исследования асимптотического поведения марковских систем массово-ю обслуживания часто оказывается полезным изложенный в книге [16] подход, основанный на построении и изучении так называемых индуцированных цепей Маркова. Этот подход применен в статьях [17], [i8].

В работе [17] исследуется асимптотическое поведение однородного случайного блуждания в Z+, соответствующего процессу, описывающему сеть Джексона с взаимодействием станций. Показано, что изучение положительной возвратности, нулевой возвратности и невозвратности этого случайного блуждания сводится к изучению асимптотического поведения соответствующей динамической системы. Дана характеризация однородных случайных блужданий

В работе [18] изучается жидкостная динамика консервативных систем обслуживания с пуассоновскими входными потоками и показательным обслуживанием. Доказана единственность траектории жидкостного предела в таких системах и описано ее поведение.

Исследованию вопросов эргодичности систем поллинга с одним прибором (М = 1) при весьма общих стохастических предположениях посвящено большое число работ (см., например, [19], [20] и списки литературы в них).

В [19] рассмотрена система поллинга, в которой перемещение обслуживающего прибора между станциями управляется неразложимой апериодической цепью Маркова, а дисциплина обслуживания к-й станции задается функцией /(х, Ь'1) = шш{х, Ь7к}, оде х — длина очереди в момент ^-того прихода прибора на эту станцию, а случайные величины {¿{}у>1 независимы, одинаково распределены для каждого к, и имеют конечное математическое ожидание = Ь'к- Входные потоки являются независимыми пуассоновскими, а времена обслуживания образуют взаимно независимые последовательности независимых одинаково распределенных случайных величин. Получено необходимое и достаточное условие эргодичности:

где N — число станций; А1 — интенсивность прихода вызовов на станцию г; Ьь

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

— среднее число посещений станции г за цикл.

В [20] исследована, система поллинга со стационарным метрически транзитивным входным потоком, дисциплинами обслуживания, удовлетворяющими некоторым свойствам монотонности, и маршрутом прибора, обладающим свойством регенерации. Для системы с нулевыми начальными условиями при выполнении условия (4) доказала так называемая каплинг-сходимость к ста-

N

ЕЛ ¿6,- -4- А • тах

|<-.:<г Л;

< 1,

(4)

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

Системы поллинга с несколькими одинаковыми приборами, кроме упомянутой работы [9], рассмотрены в [21], [22]. В [21], [22] приведены результаты численного моделирования систем поллинга с несколькими одинаковыми приборами, посещающими станции в циклическом порядке, и получены приближенные формулы для среднего времени ожидания.

Диссертация состоит из 2 глав, которые делятся на 10 параграфов. Нумерация утверждений двойная: например, теорема 2.1 является первой теоремой главы 2. Нумерация формул сквозная. Список литературы содержит 33 наименования и составлен в порядке цитирования. Работы автора помещены в конце списка.

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

В §1.1 проводится построение жидкостной модели для марковского процесса (Х(Ь), Z(t)), состояхцего из двух компонент: пространственной компоненты Х(Ь), принимающей значения в метрическом пространстве с компактными шарами, и индексной компоненты Z(t), принимающей значения в конечном множестве индексов. Для этого строится процесс У({), подсчитывающий время, в течение которого процесс находился в каждом из возможных состояний, и доказывается относительная компактность на бесконечности семейства масштабированных версий процесса (А (г:), У(0) ПРИ выполнении условий асимптотической липшицевости. Предельные процессы (жидкостные пределы) обозначаются через <р — (х, у).

В §1.2 получены условия возвратности и положительной возвратности в терминах поведения жидкостных пределов в неслучайный момент времени Т. Эти условия могут быть записаны (при ряде дополнительных ограничений) следующим образом.

Условие возвратности: существуют '1\ е > 0. 6 > 0 такие, что для любого <р ~ (х, у) имеет место:

Е 1о§+тах{о; ¡х(Т)|} < —е. (5)

Условие положительной возвратности: существуют Т, е > 0, такие, что для

любого <р — (х, у) имеет место:

Е|х(Т)| < 1 - с-

(б)

Это условие является естественным аналогом в терминах стохастических жидкостных пределов известных теорем о положительной возвратности (см. [23], §4), а также результата А. Л. Столяра [10].

пределов со случайными начальными условиями. С. Г. Фоссом в [33] доказано следующее свойство жидкостных пределов: если для жидкостного предела <р — (х, у) Е Ф неслучайный момент t > 0 таков, что Р(|х(£)| > 0) > 0, то

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

В § 1.4 условия возвратности (5) перенесены на случай марковских моментов остановки.

В §1.5 приводится результат С. Г. Фосса (теорема 2.2 в [33]) о положительной возвратности и следствие из него. Условия положительной возвратности получены в терминах случайных моментов остановки. Эти условия можно рассматривать как аналог исходного критерия для случайных Т (которые могут быть различны для различных жидкостных пределов <р). В частности , показано. что такое определение стабильности эквивалентно /^-стабильности [14] для некоторого р > 1 (Теорема 1.5 (пункт (¡у)) и замечание 1.5).

Заметим, что в отличие от общего критерия положительной возвратности для цепей Маркова (теорема 1. Ш в [23]) здесь не требуется даже существования конечного математического ожидания у моментов остановки. Это обусловлено спецификой рассматриваемых процессов — выполнением для них свойства асимптотической липшицевости.

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

Рассмотрен пример системы обслуживания с одним прибором, для которой жидкостная модель не