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

• Баштова, Елена Евгеньевна
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Баштова, Елена Евгеньевна

Введение

Глава 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. Г. Афанасьевой за постановку задач, ценные советы, обсуждения и постоянное внимание к работе.

Заключение диссертации по теме «Теория вероятностей и математическая статистика», Баштова, Елена Евгеньевна

Заключение.

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Баштова, Елена Евгеньевна, 2006 год

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