Законы больших чисел и глобальная асимптотическая устойчивость в сетях массового обслуживания

• Автор: Хмелёв, Дмитрий Викторович
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 137 с. : ил

Оглавление
Введение
Глава

Закон больших чисел для конечномерных сетей систем массового обслуживания ‘

1. Устойчивость одного класса систем нелинейных дифференциальных уравнений

2. Простейшая транспортная сеть

3. Сеть приборов с выбором наименьшей из двух очередей

4. Существование инвариантного компакта

5. Транспортная сеть с очередью

6. Кластерная транспортная сеть

7. Транспортная сеть с непоказательным распределением времени перемещения приборов

Глава
Глобальная асимптотическая устойчивость некоторых счётных систем дифференциальных уравнений г
1. Устойчивость одного класса счётномерных систем нелинейных дифференциальных уравнений
2. Система обслуживания с выбором наименьшей из двух очередей
3. Транспортная сеть с неограниченным числом мест ожидания для приборов
4. Другие примеры с.чётномерных систем
5. Достаточное условие эргодичности счётной цепи Маркова с непрерывным временем
6. Транспортная сеть из двух узлов
Глава
Бесконечная транспортная сеть 7
1. Бесконечная транспортная сеть: описание и простейшие результаты
2. Предел среднего поля для процесса с нулевой областью зависимости
Список литературы

Введение
Теория массового обслуживания — богатая и интенсивно развивающаяся область математического знания. Начиная с работ А.К. Эрланга [1], ей была присуща очевидная практическая направленность, что приводило к появлению множества естественных и интересных вероятностных задач.
В настоящей диссертации исследуются модели теории массового обслуживания, связанные с сетями из перемещающихся приборов. Такого рода системы получили название поллинг-систем и они являются популярной областью среди исследователей (см., например, книгу A.A. Боровкова [2]). Отметим, что очень многие классические модели теории массового обслуживания по сути своей являются поллинговыми. Вспомним, например, модель Б.В. Гнеденко [3] системы из п ткацких станков, время от времени выходящих из строя (из-за обрыва нити) и требующих ремонта, оказываемого то работниками, перемещающимися между станками. Вероятностная модель, избранная Б.В. Гнеденко приводила к исследованию марковской цепи с непрерывным временем и состоянием, описываемым одной переменной, а именно, числом неисправных станков (такая система, в частности, описана в книге В. Феллера [4, I том, раздел XVII.7]). Очевидно, в этой задаче достаточно естественно возникает поллинговая модель обслуживания заявок, возникающих на станках, перемещающимися работниками. Однако, учёт того, что работники перемещаются, очень усложняет анализ функционирования описанной системы.
Как и в других математических дисциплинах, в теории массового обслуживания можно наблюдать постепенное усложнение исследуемых моделей и задач, вызванное необходимостью лучше понять изучаемые явления. Развитие происходит от простейших моделей с одним обслуживающим прибором к сетям обслуживания со случайным выбором обслуживающего прибора и далее к сетям обслуживания, на которых загрузка при сложном взаимодействии с заявками перераспределяется между приборами (именно к последнему классу относятся поллинговые системы). При этом наблюдается стремление исследовать как можно более широкий класс возможных распределений времён обслуживания и времён между появлениями заявок. Далее будут упомянуты некоторые работы, в которых отражается отмеченная тенденция.
А.К. Эрланг [1] (см. также книгу А.Я. Хинчина [5, §20]) получил свои известные формулы с использованием теории цепей Маркова с конечным пространством состояний. Кроме того, он изучал цепи Маркова со счётным пространством состояний, которые описывались счётной системой линейных дифференциальных уравнений, где вопросы о сходимости к стационарному решению уже требуют привлечения тонких вероятностных соображений (этот вопрос решили А.Н. Колмогоров [6] и В. Феллер [4,

I том, гл. XVII. 5]). Формулы Эрланга получены в предположениях па экспоненциальное распределение времени обслуживания и пуассоновость входного потока заявок. Эти предположения казались слишком ограничительными и многие исследователи обратились к изучению общего времени обслуживания. В случае конечной системы обобщение формул Эрланга получил Б.А. Севастьянов [7].
Формулы, описывающие стационарное поведение систем с общим временем обслуживания получили Ф. Поллачек [8] и А.Я. Хинчин [9] (см. также работы Д.Г. Кендалла [10, 11]). В работе Д.В. Линдли [12] изучалось асимптотическое поведение времени ожидания начала обслуживания при поступлении в очередь к одному обслуживающему прибору. В [12] интервалы между поступлением заявок и времена обслуживания считались последовательностями независимых одинаково распределённых величин. При аналогичных условиях Дж. Кифер и Дж. Волфовиц [13] исследовали уже случай нескольких обслуживающих приборов. Затем P.M. Лойнес [14, 15] обобщил результаты Д.В. Линдли, а также Дж. Кифера и Дж. Волфовица на случай стационарных метрически транзитивных последовательностей времён обслуживания, обнаружив, в частности, что стационарный режим для систем с несколькими обслуживающими приборами может не быть единственным. Дальнейшие результаты и обобщения в области систем с общими временами обслуживания и интервалами между поступлениями заявок получили П. Франкен [16] и A.A. Боровков [17], что нашло отражение в книге А. Брандта, П. Франкена и Б. Лизека [18]. Также упомянем работу Дж.Ф. Кингмана [19] об алгебраической природе формул для стационарного распределения времени ожидания и числа заявок в очереди к одному прибору.
Другое направление в усложнении исследуемых моделей состоит в изучении сетей систем массового обслуживания, в которых заявки перемещаются от одной системы к другой. В рамках этой задачи замечательное наблюдение сделал Дж.Р. Джексон [20, 21], обнаруживший явные формулы для стационарного распределения числа заявок, проходящих последовательность обслуживающих приборов сообразно некоторой обрывающейся цепи Маркова. Многочисленные примеры явных решений для многочисленных сетей обслуживания приведены в книге Ф.П. Келли [22]. Тем не менее, сложность изучаемых сетей обслуживания очень велика и явные формулы для стационарного состояния системы удаётся найти лишь с учётом предположений экспоненциальности времён обслуживания и пуассоновости входного потока.
Дальнейшее развитие теории связано с изучением всё более сложных дисциплин взаимодействия заявок и обслуживающих систем и оно может привести к определённым результатам в изучении поллинговых моделей, которые иногда можно исследовать именно как некоторые специальные сети массового обслуживания.

1.3. Равномерное сжатие для неавтономных систем. Обобщим результаты предыдущего пункта на неоднородную во времени систему дифференциальных уравнений
х = /(ж,£), х £ К", (1.6)
удовлетворяющую следующим условиям
1) Векторное поле /(хД) и матрица Якоби
ЛхД) - дЦдх = (дф/дх^)
непрерывны по своим аргументам, и, кроме того, векторное поле /(х, <) дифференцируемо по х. Эти условия обеспечивают локальное существование и единственность решения х{1, £о> з) системы (1.6) с сг(]Со, 4о> з) =
2) Имеется множество X, которое является выпуклым подмножеством аффинного многообразия Т+с, с £ К", и, кроме того, 21 инвариантно относительно динамической системы (1.6). Допустим, что для всех д £ X решение х(тДй,д) существует при всех г > £о, удовлетворяющих неравенству г ^
Предположим также, что существует неотрицательная матрица В > 0 и интегрируемая при т £ [1оД] функция С(тД(ьз) ^ 0 удовлетворяющие следующим условиям
(а) ф(х(тДо,д)Д) + С{тДо> д)1 ^ ^ ПРИ всех 3 € 21 и при всех т 6 [£оД]-
(б) матрица В — марковская и при некотором п0 6 N выполнено неравенство к{(1 + В)п°) > 0.
Далее условия 1)-2) и (а)-(б) считаются выполненными.
Заметим только, что из условия (а) следует неотрицательность недиагональных элементов матрицы Якоби.
Пусть Ф(т, 4о) з) = дх(т, Ьо, д)/дд — матрица Якоби отображения х(т, й0, -): X X при т € [10Д].
Теорема 1.10. В указанных условиях на функцию С и матрицу В верна следующая оценка
||Ф(Мо>з)||ь < д(Мо,з) < 1,

д(Мо,з) = 1 -ехр(-^ С(тДо,з)^ ^ к((1 + В)п°) <1.
Доказательство. Матрица Ф(т, £0,з) удовлетворяет уравнению в вариациях
Ф(. = /(ж(гДо,з)Д)ф) Ф(^оДо,з) = ^- (1-7)
Введём
Ф(Т)*о,з) = Ф(тДо,з)ехр^ ((вД0,д)дв