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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет

-ч

На правах рукописи - ; УДК 519 21

Баштова Елена Евгеньевна

. СИСТЕМЫ ОБСЛУЖИВАНИЯ С ДВАЖДЫ СТОХАСТИЧЕСКИМИ ПУАССОНОВСКИМИ ПОТОКАМИ

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

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

Москва 2006

Работа выполнена на кафедре теории вероятностей Механико-математического факультета Московского государственного университета имени М В Ломоносова

Научный руководитель: доктор физико-математических наук,

профессор J1 Г. Афанасьева

Официальные оппоненты: доктор физико-математических наук,

Защита диссертации состоится 2 марта 2007 года в 16 часов 15 минут на заседании диссертационного совета Д 501 001 85 в Московском государственном университете имени M В Ломоносова по адресу 119992, ГСП-2, г Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета (Главное здание, 14 этаж)

Автореферат разослан 2 февраля 2007 года Ученый секретарь диссертационного

профессор В Ю Королев

доктор физико-математических наук вед н с В И Афанасьев

Ведущая организация:

Институт проблем информатики РАН

совета Д 501 00185 в МГУ, доктор физико-математических наук, профессор'

Т П Лукашенко

Общая характеристика работы

Актуальность темы.

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

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

Системы обслуживания с зависящими от времени и случайными параметрами рассматривались в работах многих авторов Начало изучения систем с непостоянной интенсивностью было положено в статьях А Кларка 2 в 1953 году, а двумя годами позже Д.Кокс 3 предложил рассматривать потоки, интенсивность которых зависит от состояний некоторой марковской цепи Такой поток позже был назван марковски-модулированным или процессом Кокса, а его обобщение — дважды стохастическим пуассоновским процессом Среди дальнейших можно выделить работы Д Харрисона и А Лемуана4'5, JI Г Афанасьевой6,7,

'Clarke А В (1953) The time-dependent waiting line problem Um« Michigan Rept M720-1R39, 1953

2Clarke А В On time-dependent waiting line processes Ann Math Stattet v 24(1953), p 491-492

3Cox D R The analysis of non-Markovian stochastic processes Free Cambr Phii Soc 1955 v 61, n 3 p 433-441

4Harrison 3 M , Lemoin A J (1977) Limit theorems for periodic queues JApplProb v 14(1977), p 566-576

5Lemom A J (1981) On queues with periodic Poisson input J Appl Prob v 18(1981), p 889-900

6Афанасьева Л Г Кибкало А А (1985) Равномерные оценки для периодического решения в системе M(i)|G|l|oo Пробл уст стох моделей Труди семинара ВНИИСИ

TL G Afanas'eva (1984) On waiting-time process m periodic queues Lect Notes Math Stab probt stoch models 1984

ТРольски8'9

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

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

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

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

8Rolski Т (1986) Upper bounds for single server queues with doubly stochastic Poisson arrivals Math Opa-Res, Vol 11 442-450

9Rolski T (1989) Queues with nonstationary input Queuetng systems, Vol 5 113-130

входящего потока или при замедлении обслуживания10,11 Если возникает необходимость изучать работу нагруженной системы до вхождения в предельный режим, или предельного режима вообще не существует, то рассматривают схему серий, то есть модель, в которой время и параметр нагрузки увеличиваются синхронно Сюда относятся задачи о диффузионной аппроксимации и анализ переходных явлений12'13'14

Другим предельным случаем, позволяющим получать оценки и приблизительный вид распределений, является ситуация малой нагрузки Результаты, касающиеся условий малой нагрузки можно найти, например, в работах А А Бо-ровкова15, ТРольски16

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

Цель работы.

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

10L G Afanas'eva (1984) Oil waiting-time process in periodic queues Led, Notes Math Stab probl stock models 1984

11Боровков A A (1972) Вероятностные процессы в теории массового обслуживания Наука, Москва

12Ю В Прохоров (1963) Переходные явления в теории массового обслуживания Лит Мат сб т 3 № 1, стр 199-206

13D Y Burman (1979) An analytic approach to diffusion approximations m queuemg Ph D New York Untv

14G I Falin (1989) Periodic queues m heavy traffic Adv Appl Prob v 21, p 485-487

15Боровков A A (1972) Вероятностные процессы в теории массового обслуживания Наука, Москва

"RolskiT В Blaszczyszyn (1993), Queues in series in light traffic Ann Appl Prob v 3 No 3,881-896

Научная новизна.

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

Основные результаты работы состоят в следующем

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

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

3 В тех же условиях высокой загрузки доказана С-сходимость нормированного времени ожидания к процессу броуновского движения на каждом конечном интервале

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

5 В ситуации малой загрузки найдено асимптотическое разложение по параметру загрузки для периодического распределения времени ожидания

Методы исследования.

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

Теоретическая и практическая ценность.

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

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

Результаты диссертации докладывались и обсуждались на семинаре "Современные проблемы теории массового обслуживания" (руководитель - д.ф-мн, профессор Л Г Афанасьева), на Большом семинаре кафедры теории вероятностей механико-математического факультета МГУ (2004-2006 гг), а также на XXIV международном семинаре по проблемам устойчивости стохастических моделей (Юрмала, 10 - 15 сентября 2004г), на конференции "Современные проблемы и новые направления в теории вероятностей"(Черновцы, Украина, 26 -30 июня 2005г.) и на Воронежской зимней математической школе С Г Крейна (Воронеж, 24-28 января 2004 г, 27-30 января 2006 г) Тематика работы была поддержана грантом РФФИ 05-01-00256

Публикации

Результаты диссертации опубликованы в 6 работах, список которых приведен в конце автореферата

Структура диссертации.

Диссертация состоит из введения, трех глав (разбитых на разделы), заключения и списка литературы, насчитывающего 50 наименований Общий объем диссертации — 97 страниц

Краткое содержание диссертации

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

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

Определение 1 Пусть на вероятностном пространстве (О, Т, Р) задан случайный процесс Л(£), имеющий с вероятностью 1 неубывающие непрерывные справа траектории, и на том же вероятностном пространстве задан стандартный пуассоновский процесс, в > 0}, не зависящий от (Л(£), < € К} Тогда дважды стохастический пуассоновский процесс £ > 0} определяется при помощи формулы

л(«) = л*(лю) (1)

4

В диссертации предполагается, что Л(£) = / \{и)(1и , где

о

> 0} - неотрицательный и ограниченный с вероятностью 1 случайный процесс При этом процесс Л(£) называется ведущим процессом, а Х{€) интенсивностью дважды стохастического пуассоновского процесса {А(1), £ > 0}

В диссертации приведено несколько примеров дважды стохастического пуас-соновского процесса, возникающих в классических системах обслуживания Укажем один из них Рассмотрим r-канальную систему, в которую поступает пуас-соновский поток требований интенсивности Л Время обслуживания каждого требования экспоненциально с параметром ¡л Вновь прибывшее требование поступает на обслуживание, если в системе находится к < г требований Если в системе находится к > г требований, то новое требование с вероятностью Д присоединяется к очереди, а с вероятностью 1 — fк теряется

Пусть Q(t) - число требований в системе в момент t, a X(t) - число потерянных требований за (0, t) Тогда X(t) является дважды стохастическим пуассо-новским процессом с интенсивностью А(1 — fQ(t)) Кроме того, поскольку в данном случае Q(t) - стационарный марковский процесс, то X(t) — пример часто изучаемого в литературе марковски-модулированного потока (процесса Кокса) Основное внимание в диссертации уделяется одноканальной системе обслуживания 5 с дважды стохастическим пуассоновским входящим потоком Alt) интенсивности A(i, ы)

Времена обслуживания {£t}JSi суть независимые одинаково распределенные случайные величины с функцией распределения В(х) и средним Ь

Изучается процесс виртуального времени ожидания W(t), который, как известно17, задается формулой

W(t) = W(0) + Y(t) - inf{Y(s) О < s < t) где (2)

Y{t) = X(t) - t, a X(t) = & + &+.. + £л(г)-Для одноканальной системы с входящим ДСПП имеет место следующая теорема

Теорема 1 Пусть существуют числа 0<с<С<оо и последовательность марковских моментов Т\ < < относительно потока

17см напр Боровков А А (1972) Вероятностные процессы в теории массового обслуживания Наука, Москва

Ft = <r(A(u), и < t), такая что с < Е(Г„ — Tn_i) < С и для всех достаточно больших п выполняется•

ЕЛ(ГП^,Г„) Е(Тп - Т„_!) Тогда процесс W(t) стохастически ограничен.

Доказательство проводится методом Кифера и Вольфовица 18 Формулировка теоремы 1, будучи ограниченной на случай детерминированной интенсивности, эквивалентна теореме о стохастической ограниченности в работе Т Рольски19 Таким образом теорема 1, обобщает соответствующую теорему Т Рольски

Если же сделать дополнительные предположения о природе ведущего процесса, то, используя теорему Смита20, можно доказать не только стохастическую ограниченность, но и существование предельного режима

Предположим, что A(í, ш) - регенерирующий, ограниченный с вероятностью 1 случайный процесс и {ín}5£Li - последовательные моменты регенерации A (i, ш), а {т„ = tn — ín-i}£Lr длительности периодов регенерации (Етп < оо) Тогда для системы S коэффициент загрузки определяется следующим образом

п

Ь f

Р = / (3)

о

Определение 2 Случайный процесс {V(t),t > 0} - периодический с периодом Т, если все его конечномерные распределения периодичны с периодом Т

Определение 3 Случайный процесс {Vit), t > 0} - периодический регенерирующий процесс, если регенерирующим является процесс {V(nT),neN}

"Kiefer J, Wolfowitz J (1955) On the theory of queues with many servers // Tïans Amer Math Soc v 78,1, p 1-18

19Rolski T (1989) Queues with nonstationary input Queuemg systems. Vol 5 113-130

20 Smith W L (1955) Regenerative stochastic processes // Proc Roy Soc London Ser A 1955 v 232

Теорема 2 Если интервалы между регенерациями Л(i, си) имеют нерешетчатое распределение, то существует предел

hm P(W(t) < х) = Н(х)

Если же А(t, си) - периодический регенерирующий процесс с периодом Т (в смысле определения 3), то для каждого t > 0 существует предел

lim P(W(nT + t) < х) = H(t, х)

п—юо

где H(t, х) - периодическая по t функция

При этом функции Н{х), H(t,x) являются функциями распределения тогда и только тогда, когда р < 1

В противном случае они тождественно равны О

В конце главы приводятся примеры систем, в которых можно выписать явные формулы для предельного распределения времени ожидания

Вторая глава посвящена ситуации высокой загрузки для систем с входящим ДСПП Рассмотрено два варианта постановки задачи Сначала изучается поведение предельного периодического режима в условиях большой загрузки, а затем - диффузионная аппроксимация нормированного процесса времени ожидания в случае, когда нагрузка увеличивается вместе с течением времени Предполагается, что изучаемая система является элементом последовательности систем {¿У с общей функцией распределения В(х) времен обслуживания Интенсивность входящего потока Ae(f) системы SE зависит от е таким образом, что

Ae(t) = i-^A(i) и £ 0 (4)

Здесь, как и раньше, A(i) - периодический регенерирующий случайный процесс, представляющий собой интенсивность входящего потока

При таком определении Аe(t) коэффициент загрузки системы Se (определенный для исходной системы соотношением (3)), стремится к 1 при е 0, оста-

ваясь меньше 1.

ЕА£(т) ,

ре = —— О = 1 — £ -»• 1 при е О Ьуг

Те параметры и характеристики системы которые зависят от е всюду далее будут отмечены значком е

Для предельного периодического или стационарного распределения имеет место

Теорема 3 Пусть р < 1 и < оо и < оо для некоторого 5 > О

Тогда существует

2 = Ь. + рЛЫЕг„ 2соу(тп,Л(гп))

а Ь + (ЕЛ(тп))2 + Ет„ ЕЛ(т„) [Ь>

В диссертации приведены два способа доказательства этой теоремы один из них опирается на факторизационную технику для случайных блужданий, а второй основан на применении результата А А Боровкова21 вместе с методом мажорирования

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

Рассматривается схема серий, т е последовательность систем {5е}, функционирующих в условиях высокой нагрузки (4) на удлиняющихся интервалах времени II = и/е2, где и > 0 фиксировано Изучается нормированный процесс виртуального времени ожидания

Основной результат второго параграфа главы 2 составляет следующая теорема

Теорема 4 Пусть Е£2+г < оо, Е< оо для некоторого 6 > 0 и И^(0) = О Тогда процесс 2е({) С-сходится

21 Боровков А А (1972) Вероятностные процессы в теории массового обслуживания Наука, Москва

на каждом конечном отрезке [0, и] к диффузионному процессу с с отражением от нулевой границы и коэффициентами (—1,с2), где а2 определяется формулой (6)

Доказательство этой теоремы существенным образом опирается на фундаментальную теорему Боровкова о диффузионной аппроксимации22, которая применима к широкому классу процессов Однако проверка условий этой теоремы для систем с входящим ДСПП представляет собой значительную трудность и требует применения разнообразных приемов и методов современной теории вероятностей (различные свойства стохастических неравенств, неравномерные оценки в классической ЦПТ, а также ЦПТ для зависимых случайных величин, предельные теоремы для процессов накопления)

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

Рассмотрим марковски-модулированный поток, управляемый стационарной цепью Маркова с п состояниями и инфинитезимальной матрицей Цау]| Поскольку для функции Н(1, х) в случае марковски-модулированного потока можно выписать уравнение, подобное уравнению Такача23 , то в данном случае для вычисления коэффициента а2 удобно воспользоваться этим уравнением, переписанным в терминах преобразования Лапласа-Стилтьеса

оо оо

Обозначим 6*(в) = / е~ахВ((1х), Н*{е) = / е~ахН(<1х)

о о

Введем матрицу М(в)=||ту(в)||, ту(з) — а]г для г Ф з,

ти(в) = в — АД1 - Ь*) — ^ ач зФ*

Согласно теореме 3

Ит Я*(5£) = —Цг- (7)

£4-0 1 + сг2в

22Боровков А А (1980) Асимптотические методы в теории массового обслуживания стр 55, 77 теорема 2

23Tak£cs L (1955) Investigation of waitmg-time problems by reduction to Markov process / / Acta Math Acad Sa Hungary, 6(1955) p 101-129

Для марковски-модулированного потока удается в явном виде найти этот предел

Теорема 5 Обозначим Д(«) = ¿е1ЪЛ($) Тогда

¿-Ът'-^Ш (8)

<40 Ае (0) ^ !

Примером подсчета коэффициента а1 по формуле (8) может служить следствие для процесса размножения и гибели

Следствие 1 Пусть аи+= а, ~ (3, г — 1, п — 1 Тогда

6 и ¿¿Л 'Л Р) ¿«.-1^

г=1

В главе 3 рассмотрена ситуация малой загрузки

Предположим снова, что наша система является элементом последовательности систем {5е} с общей функцией распределения В(х) времен обслуживания. Интенсивность входящего потока Ае(£) системы Э£ зависит от е таким образом, что Хе{г) - еЛ(<) и е -»■ 0

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

Теорема 6 Пусть

< оо для некоторого 5 > 0 и натурального п

Тогда существуют функции у), г — 1 . п, такие что

п

Яе(*, у) = 1 - £ У) + е (10)

1=1

Доказательство теоремы б разделено на две части Сначала доказано несколько лемм оценочного характера

Для фиксированного £ > 0 и с < О обозначим интервалы А = (£ — ес, <) и Д°° = (—оо, Ь — ес] Первые две леммы описывают асимптотическое поведение

вероятности того, что хотя бы одно требование, пришедшее на промежутке Л00, находится в системе в момент I Третья лемма оценивает вероятность появления в системе более чем п требований на интервале Д Последняя лемма касается вероятности застать систему занятой в момент I — ес

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

В последнем параграфе третьей главы приведен пример подсчета коэффициентов разложения для одного вида случайной интенсивности

Пусть - периодическая интегрируемая неотрицательная функция с периодом Т и - последовательность независимых одинаково распределенных случайных величин (т]п > 0 п н ) Случайную интенсивность дважды стохастического пуассоновского потока определим так

При таком определении величины г/п можно интерпретировать как случайные амплитуды, которые постоянны на п-ом периоде

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

На этом примере видно, что в случае периодического режима коэффициенты разложения, начиная со второго, существенно отличаются от коэффициентов

А {пТ + ^о}) = т)п

(11)

= -Ще^У ц

= -(Щ)2уе-"У -

(¡лЩ* + 2- 2Щ + М \

для классического пуассоновского потока

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

Автор выражает глубокую благодарность своему научному руководителю профессору Л Г Афанасьевой за постановку задач, ценные советы и постоянное внимание к работе

Работы автора по теме диссертации

1 Баштова Е Е (2004) Виртуальное время ожидания в одной системе с марковски-модулированным входным потоком Мат заметки m 76 вып 6 стр 945-948

2 Баштова Е Е (2006) Режим малой загрузки для системы обслуживания со случайной нестационарной интенсивностью Мат заметки m 80 вып 3 стр 339-349

3 Afanasieva L G , Bashtova Е Е (2004)The queue with periodic double stochastic Poisson input Trans XXIV Int Sem Stab Probl Stock Mod Jurmala 2004 P 8087

Л Г Афанасьевой принадлежит постановка задачи и идеи доказательств теорем о предельном режиме и о высокой загрузке в общем случае Е Е Баш-товой принадлежит реализация этих идей, теорема о малой загрузке и теорема о высокой загрузке для марковски-модулированных потоков

4 Баштова Е Е (2004) Периодическое распределение в одноканальной системе с очередью Условия малой загрузки Воронежская зимняя математическая школа - 2004 Тезисы докладов стр 19

5 Bashtova E E (2005)The queue with a periodic doubly stochastic Poisson input m the light traffic situation Trans XXV Int Sern Stab Probl Stoch Mod Maion/Salerno, Italy 2005 p 32-37

6 Афанасьева JI Г, Баштова Е Е (2005) Предельные теоремы для некоторой системы с входящим потоком переменной интенсивности Int Conf Modern Probl New Trends m Probab Th Abstracts Chernivtsi, Ukraine 2005 p 16-17

Л Г Афанасьевой принадлежит постановка задачи и идея доказательства теоремы о предельном режиме Е Е Баштовой принадлежит реализация этой идеи и теорема о малой загрузке

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова Подписано в печать /7,6{, V Ч-

Формат 60 х 90 1/16 Уел печ л /,<?

Тираж 100 экз Заказ 06

Введение

Глава 1. О существовании продельных режимов для систем с входящим ДСПП.

1.1. Определения и примеры дважды стохастического пуассоновского процесса.

1.2. Описание основной модели.

1.3. Теоремы о стохастической ограниченности и предельном режиме.

1.4. Явный вид предельной функции распределения для некоторых систем.

Глава 2. Предельные теоремы для ситуации высокой загрузки.

2.1. Ситуация высокой нагрузки для предельного периодического режима.

2.2. Диффузионная аппроксимация.4G

2.3. Методы вычисления коэффициента и1.СО

Глава 3. Асимптотическое разложение для периодического распределения в системе MR(t)|GI|l|oo в условиях малой загрузки

3.1. Постановка задачи и формулировка основного результата.

3.2. Оценки малых вероятностей.

3.3. Доказательство теоремы 10.7G

3.4. Явная формула для первых коэффициентов.

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

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

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

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

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

Одна из первых работ, посвященных системам с входящим потоком непостоянной интенсивности, принадлежит А.Кларку [20-21] и написана в 1953 году. Затем Л.Такач в 1955 году получил иитегро-дифференциальное уравнение для времени ожидания ([49]). Это уравнение и метод его получения до сих пор остаются одними из главных инструментов для изучения свойств виртуального времени ожидания в различных системах. Исследованию свойств решения уравнения Такача посвящены статьи Е.Рейча [36], [37] и А.Хасофера [29].

Из результатов 70-х годов наибольший интерес представляют работы Б.В.Гнеденко и И.П.Макарова [11], где для анализа систем с отказами используются методы теории дифференциальных уравнений, Д.Харрисона и А.Лемуана [28], где представлены предельные теоремы для периодических систем, и А.Лемуана [35], который установил связь между предельным распределением времени ожидания в периодической системе и вероятностью выхода некоторого сложного пуассоновского процесса за криволинейную границу. При помощи этого представления Л.Г.Афанасьевой и А.А.Лустиной [4], [5] доказаны теоремы устойчивости по отношению к входящему потоку для распределения времени ожидания. Результаты, касающиеся условий большой и малой загрузки, быстро и медленно меняющейся интенсивности для периодических систем можно найти у Л.Г.Афанасьсвой [17].

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

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

Теоретические исследования отражены в работах Д.Кингмана [34], О.Калленберга [30], Д.Дали и Д.Вере-Джоиса [24[ и других [45 - 46]. Наиболее полно свойства ДСПП представлены в монографии Д.Гранделла [20]. Там доказаны теоремы об эргодических свойствах дважды стохастических пуассоновских процессов, аналог центральной предельной теоремы, рассмотрены свойства пальмовских мер.

Одним из вопросов, появившихся при изучении систем с дважды стохастическим пуассоновским потоком, стала так называемая гипотеза Ш.Росса [44], который предположил, что в системе с входящим ДСПП среднее время ожидаиия больше, чем в системе с пуассоновским входящим потоком усредненной интенсивности. Доказательство этой гипотезы в наиболее общем случае принадлежит Т.Рольски [38].

В другой статье Т.Рольски с соавторами получены теоремы о монотонности для быстро меняющихся интснсивностей ([43]). Интересны также результаты С.Асмуссепа [18] (теоремы переноса ), С.Чанга и К.Хао [23] (неравенства для дисперсии времени ожидания).

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

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

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

В дополнительных предположениях доказана теорема о предельном периодическом или стационарном режиме.

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

В главе 2 изучается ситуация высокой загрузки.

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

В параграфе 2.1 доказана сходимость предельной функции распределения нормированного времени ожидания нагруженной системы к экспоненциальному распределению. Доказательство дано двумя способами: при помощи теории случайных блужданий и применением результата А.А.Бо-ровкова из [8] вместе с методом мажорирования.

При изучении работы нагруженной системы до вхождения в предельный режим, или если предельного режима вообще не существует, рассматривают модель, в которой время и параметр нагрузки увеличиваются синхронно. Теоремы общего характера, относящиеся к вопросу о диффузионной аппроксимации, можно найти в книге А.А.Боровкова [9j. Однако проверка условий этих теорем для систем с входящим ДСПП представляет собой значительную трудность и требует применения разнообразных приемов и методов современной теории вероятностей (различные свойства стохастических неравенств, неравномерные оценки в классической ЦПТ, а также ЦПТ для зависимых случайных величин, предельные теоремы для процессов накопления).

В параграфе 2.2 доказана С-сходнмость нормированного времени ожидания к процессу броуновского движения на каждом конечном отрезке. Выписана формула для параметра <т2 экспоненциального распределения, являющегося также коэффициентом диффузии броуновского движения.

В параграфе 2.3 представлено несколько методов для вычисления этого параметра. Для марковски-модулировапного потока доказана формула для а2 в терминах переходных вероятностей управляющего процесса.

В главе 3 рассмотрена ситуация малой загрузки. Дано асимптотическое разложение по малому параметру загрузки для периодического распределения времени ожидания. Приведен пример подсчета коэффициентов разложения для одного вида случайной интенсивности.

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

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

Заключение.

В заключение сделаем краткий обзор полученных результатов.

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

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

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

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

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

1. Афанасьева Л.Г. (1966) О потоке потерянных требований в некоторых системах массового обслуживания с ограничением.Изв.АН СССР Тсхи.Кибсри. п п. 3 стр.57 - 65

2. Афанасьева Л.Г. (1989) Стохастическая ограниченность циклических систем обслуживания. Пробл. уст. стох. моделей. Труды семинара ВНИИСИ.

3. Афанасьева Л.Г. Булинская Е.В. (1980) Случайные процессы в теории массового обслуживания и управления запасами. Издательство МГУ.

4. Афанасьева Л.Г. Лустина А.А. (1984) О периодическом решении уравнения Такача. Пробл. уст. стох. моделей. Труды семинара ВНИИСИ.

5. Афанасьева Л.Г. Кибкало А.А. (1985) Равномерные оценки для периодического решения в системе M(t)\G\l\oo. Пробл. уст. стох. моделей. Труды семинара ВНИИСИ.

6. Бикялис А. (1966) Оценки остатотчного члена в центральной предельной теореме. JIum.Mam.c6. т.6 № 1, стр.323-346

7. Биллингсли П. (1977) Сходимость вероятностных мер. Наука, Москва.

8. Боровков А.А. (1972) Вероятностные процессы в теории массового обслуживания. Наука, Москва.

9. Боровков А.А. (1980) Асимптоттические методы в теории массового обслуживания. Наука, Москва.

10. Гнеденко Б.В. Коваленко И.Н.(1975) Введение в теорию массового обслуживания. Наука, Москва.

11. Гнеденко Б.В. Макаров И.П.(1971) Свойства решений для систем спо-терями в случае периодической интенсивности. Дифференциальные уравнения т.7, стр. 1696-1698

12. Золотарев В.М. (1986) Современная теория суммирования независимых случайных величин. Наука, Москва.

13. Кокс Д.Р., Смит B.JI.(1965) Процессы восстановления. Сов.радио.

14. Феллер В.(1965) Введение в теорию вероятностей и ее приложения. Мир, Москва

15. Прохоров Ю.В. (1963) Переходные явления в теории массового обслуживания. Лит.Матп.сб. тп.З № 1, стр.199-206

16. Хинчин А.Я. (1963) Работы по математической теории массового обслуживания. М.: Физматгиз.

17. L.G.Afanas'eva (1984) On waiting-time process in periodic queues.Lect.Notes Math. Stab, probl.stoch.models 198418. Asmussen S. (1991) Ladder heights and the Markov-modulated M|G|1queue. Stoch.Proc. Appl. v.37 313-3269.1

18. Burman D.Y. (1979) Аи analitic appoach to diffusion approcsimations in queucing Ph.D. New York Univ.

19. Clarke A.B. (1953) The time-dependent waiting line problem. Univ. Michigan Rept. M720-1R39, 1953.

20. Clarke A.B. (1953) On time-dependent waiting line processes. Ann.Math.Statist. v.24(1953), p.491-492. (резюме)

21. Cox D.R. (1955) The analysis of non-Markovian stochastic processes Proc.Cambr.Phil.Soc. 1955 v.51, n.3 p.433-441.

22. Chang C., Chao X., Pinedo M. (1991) Monotonicity result for queues with doubly stochastic Poisson arrivals: Ross's conjecture. Adv. Appl. Prob., Vol. 23. 210-228.

23. Daley D.J. Vere-Jones D. (1972) A summary of the theory of point processes Stoch.Point processes: Stat, analysis, theory and appl. New York

24. Falin G.I. (1989) Periodic queues in heavy traffic Adv.Appl.Prob. v.21, p.485-481

25. Grandell J. (1976) Double stochastic poisson processes. Led. Notes Math., vol 529. Berlin Heidelberg. New York: Springer

26. Gut A. Spataru A. (2000) Precise asymptotics in the Baum-Katz and Davis Laws of large numbers J.Math. Anal.Appl. v.248 p.233-246

27. Harrison J.M., Leinoin A.J. (1977) Limit theorems for periodic queues. J. Appl Prob. v. Ц (1977), p. 566-576.

28. Hasofcr A.M., (1964) On the single-server queue with non-homogeneous Poisson input and general service times. J.ApplProb. v.1(1964), p.369-384.

29. Kallenberg O. (1975) Limits of compound and thinned point processes J.ApplProb. 12, 269-278

30. Kendall D.G. (1957) J.Roy.Statist.Soc. Ser В 19, 209

31. Kiefer J., Wolfowitz J. (1955) On the theory of queues with many servers. Trans. Amer.Math. Soc. v.78, 1, p. 1-18

32. Kingman J.F.C. (19G1) The single server queue in heavy traffic. Proc. Camb. Phil. Soc. 57, 902-904.

33. Kingman J.F.C. (1964) On doubly stochastic Poisson processes. Proc. Camb. Phil. Soc. 60, 923-930.

34. Lernoin A.J. (1981) On queues with periodic Poisson input .J.ApplProb. v. 18(1981), p. 889-900.

35. Reich E. (1958) On the integro-differential equation of Takach.I. Ann.Math.Statist. v.29(1958), p.567-570.

36. Reich E. (1950) On the integro-differential equation of Takaeh.II. Ann.Math.Statist. v.30(1959), р.ЦЗ-Ц8.

37. Rolski T. (1981) Ross conjecture Adv.Appl.Prob. vl3 n.3 603-618

38. Rolski T. (1986) Upper bounds for single server queues with doubly stochastic Poisson arrivals. Math. Oper. Res., Vol. 11. 442-450.

39. Rolski Т. (1989) Queues with nonstationary input. Queueing systems, Vol. 5. 113-130.

40. Rolski T. (1991), Szekli R. Stochastic ordering and thinning of point processes Stoch.Proc. Appl. v.37 299-312

41. Rolski T. Blaszczyszyn B. (1993), Queues in series in light traffic. Ann.Appl.Prob. v.3 No. 3, 881-896

42. Bauerle N., Rolski T. (1998) A monotonicity result for the workload in Markov-modulated queues. J. Appl Prob. Vol. 35. 741-747.,

43. Ross Sh.M. (1978) Average delay in queues with non-stationary Poisson arrivals. J. Appl Prob. v. 15. 602-609

44. Serfozo R. (1972) Conditional Poisson processes J. Appl Prob. v.9. 288-302

45. Serfozo R. (1972) Processes with conditional independent increments. J. Appl Prob. v.9. 303-315

46. Szekli R. , Disney R. L., Hur S. (1994) MR/GI/1 queues with positive correlated arrival stream. J. Appl Prob., Vol. 31. 497-514.

47. Smith W.L.(1955) Regenerative stochastic processes. Proc.Roy.Soc.London. Ser A 1955 v.232

48. Takacs L. (1955) Investigation of waiting-time problems by reduction to Markov process. Acta Math.Acad. Sci. Hungary, 6(1955) p.101-129.

49. Yokoyama R. (1980) Moment bounds for stationary mixing sequenses Z.Wahrscheinlichkeitsthcor. verw. Geb. B.52 s.45-57

50. Список публикаций автора по теме диссертации.

51. Баштова Е.Е.(2004) Виртуальное время ожидания в одной системе с марковски-модулированным входным потоком. Матем.заметки т.76 вып.6 стр.945-948

52. Afanasieva L.G., Bashtova Е.Е. (2004)The queue with periodic double stochastic Poisson input. Trans. XXIV Int.Sem. Stab.Probl.Stock.Mod. Jurmala 2004 P-80-87

53. Баштова Е.Е. (2004) Периодическое распределение в одноканаль-ной системе с очередью. Условия малой загрузки. Вороисэ1сская зимняя математическая школа 2004- Тезисы докладов, стр.19

54. Bashtova Е.Е. (2005)The queue with a periodic doubly stochastic Poisson input in the light traffic situation. Trans. XXV Int. Sem. Stab.Probl.Stock.Mod. Maiori/Salerno, Italy 2005 p. 32-37

55. Афанасьева JI.Г., Баштова Е.Е. (2005) Предельные теоремы для некоторой системы с входящим потоком переменной интенсивности. Int. Conf.Modern Probl.New Trends in Probab.Th. Abstracts. Chernivtsi, Ukraine 2005 p. 16-17

56. Баштова E.E.(2006) Режим малой загрузки для системы обслуживания со случайной нестационарной интенсивностьыо. Матем.заметки т.80 вып.З стр.339-349