Математические методы и алгоритмы расчета некоторых немарковских моделей массового обслуживания тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Чаплыгин, Василий Васильевич

• Чаплыгин, Василий Васильевич
• кандидат физико-математических наук
• 2005

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

Введение

1 Стационарные характеристики системы массового обслуживания SM/MSP/n/r

1.1. Описание системы.

1.2. Система SM/MSP/n/r с конечным накопителем.

1.3. Система SM/MSP/п/оо с бесконечным накопителем

1.4. Система G/MSP/n/r

1.4.1. Система G/MSP/n/r с конечным накопителем

1.4.2. Система G/MSP/п/оо с бесконечным накопителем

1.5. Система массового обслуживания SM/MSP/1/r.

1.5.1. Система SM/MSP/1/r с конечным накопителем

1.5.2. Система SM/MSP/1/r с бесконечным накопителем

2 Стационарные характеристики системы массового обслуживания G/BMSP/1/r

2.1. Описание системы.

2.2. Конечный накопитель.

2.3. Бесконечный накопитель

3 Стационарные характеристики СМО G/MSP/n/r с потоком отрицательных заявок

3.1. Описание системы.

3.2. Конечный накопитель.

3.3. Бесконечный накопитель

4 Алгоритмы расчета СМО

4.1. Алгоритмы расчета системы SM/MSP/n/r.

4.2. Алгоритмы расчета системы G/MSP/n/r.

4.3. Алгоритмы расчета системы SM/MSP/1/r.

4.4. Алгоритмы расчета системы G/BMSP/1/r.

4.5. Алгоритмы расчета системы G/MSP/n/r с потоком отрицательных заявок.

5 Описание программного комплекса. Примеры расчета моделей систем массового обслуживания

Введение диссертации (часть автореферата) на тему «Математические методы и алгоритмы расчета некоторых немарковских моделей массового обслуживания»

С момента появления первых телефонных сетей возникла необходимость решения задач расчета вероятностно-временных характеристик, среди которых основными являются стационарное распределение числа заявок в системе (для телефонных сетей важнейшей характеристикой является вероятность потери заявки), стационарные распределения времени ожидания начала обслуживания и времени пребывания заявки в системе. Эти задачи впервые поставлены известным датским ученым А.К. Эрлангом [42], который и является родоначальником теории массового обслуживания (ТМО). Внимание многих математиков привлекли возможности применения этой теории к важнейшим практическим задачам в самых различных сферах: при эксплуатации различных транспортных систем, в медицинском обслуживании, в страховом деле, при профилактическом обслуживании технических устройств. Значительный вклад в разработку и анализ классических моделей ТМО внесли А.Я. Хинчин, Б.В. Гнеденко, А.А. Боровков, Г.П. Башарин, Д. Кендалл, Д. Литтл, Д. Кокс, В. Смит, JI. Такач, Ф. Поллачек. Бурное развитие информационно-телекоммуникационных технологий и сетей различного назначения направило методы ТМО, в первую очередь, на решение задач именно в этой области.

Модели, рассмотренные Эрлангом, имели пуассоновский входящий поток и экспоненциальное обслуживание. Но еще при анализе телефонных сетей было замечено, что во многих случаях требование экспоненциальное™ времени обслуживания не выполнено. Первой попыткой более адекватного описания обслуживания в реальных системах стало использование моделей с рекуррентным обслуживанием. Большое число работ посвящено модели однолинейной системы массового обслуживания (СМО) M/G/1/оо1 с накопителем бесконечной емкости. Для исследования указанной модели СМО разработаны различные методы исследования: построение вложенной цепи Маркова по момендальнейшем будем придерживаться классификации СМО, которую ввел Д. Кендалл [47]. Заметим, что существует другая классификация СМО, с которой подобно можно ознакомится в работе А.А. Боровкова [4]. там обслуживания заявок, исследование с помощью виртуального времени ожидания, введение дополнительной переменной, исследование с использованием процессов восстановления. Метод построения вложенной цепи, впервые предложенный А.Я. Хинчиным [25], позволил вычислить для СМО M/G/1/оо лишь некоторые характеристики, связанные с числом заявок в системе только в специальные моменты времени. Применение метода исследования с помощью виртуального времени ожидания приводит к интегро-дифференциальному уравнению Такача [54], которое разрешается с помощью преобразований Лапласа-Стилтьеса (ПЛС). Недостаток этого метода заключается в невозможности использования его для вычисления характеристик очереди. При использовании метода введении дополнительной переменной, как правило, в качестве дополнительной переменной рассматривается прошедшее или остаточное время обслуживания. С полным обоснованием этого метода можно ознакомится в работе Ю.К. Беляева [31]. Метод исследования с помощью процессов восстановления позволяет найти совместное нестационарное распределение практически любых характеристик обслуживания. Методы, разработанные для расчета модели однолинейной СМО M/G/1/r, позволили получить стационарные характеристики для однолинейных моделей СМО, обобщающих входящий поток и процесс обслуживания. В частности, в последнее время для описания СМО было предложено использовать марковский входящий поток. Тем не менее, несмотря на то, что созданы определенные методы расчета с марковским входящим потоком [6, 11, 15, 17, 18, 40, 41, 48, 50], в этом направлении остается немало нерешенных проблем, связанных с вычислительными сложностями.

К настоящему времени не создано методов исследования многолинейной СМО M/G/n/oo, которые позволяли бы находить для нее стационарные показатели в сколько-нибудь пригодном для анализа виде (Тем более это касается СМО G/G/n/oo. Даже для однолинейной СМО G/G/1/оо полученные на сегодняшний день результаты ориентированы на решение лишь качественных задач ТМО. При этом подавляющее число работ посвящено рассмотрению характеристик, связанных с временем пребывания заявок в системе, и так или иначе опирается на уравнение Линдли [49]. Еще более глубокие качественные результаты относительно СМО GI/GI/1/оо с зависимыми временами между поступлениями заявок и временами обслуживания можно найти в монографиях А.А. Боровкова [4, 5]). Исключением такого положения вещей являются системы с немногими частными случаями рекуррентного потока (например, СМО M/D/n/oo, для которой получены соотношения для расчета стационарного распределения числа заявок в системе). Еще хуже обстоит дело с многолинейными СМО M/G/n/r с конечным накопителем. Они остаются практически неизученными (исключением является телефонная система M/G/n/О с потерями, для которой Б.А. Севастьяновым [32] получены стационарные вероятности состояний, которые фактически совпадают с формулами Эрланга).

Шагом вперед стало появление в начале 80-х годов прошлого века алгоритмических методов (см. работы [10, 38]), предложенных впервые М.Ф. Ньютсом [51] и позволивших на основе современных высокопроизводительных вычислительных устройств производить расчеты стационарного распределения очереди для модели СМО с марковским входящим потоком и фазовым распределением времени обслуживания, гораздо более адекватно описывающих функционирование ин-фотелекоммуникационных систем. Однако, предложенные там математические методы расчета, основанные на матричной модификации метода прогонки для решения систем уравнений равновесия, оказались неустойчивыми к погрешностям вычислений, что не позволило вычислить пользовательские показатели СМО с большим числом фаз входящего потока и обслуживания и большими емкостями накопителей. В настоящее время на основе этого подхода разработаны методы для расчета многолинейных СМО вида РН/РН/n/r и МАР/РН/п/г с накопителем конечной и бесконечной емкости (см., например, работу [37]).

Пуассоновский входящий поток заявок, в отличие от экспоненциального времени обслуживания, долгое время вполне удовлетворял исследователей. Однако, по мере развития инфотелекоммуникационных технологий появились системы, для которых использование моделей с пуассоновским, и даже с обобщающим его марковским входящим потоком является неприемлемым. Это привело к изучению модели СМО G/M/n/r с рекуррентным входящим потоком вида и экспоненциальным обслуживанием. Для модели СМО G/M/n/r удалось получить как стационарные вероятности состояний, которые представимы в геометрическом виде, так и стационарное распределение времени ожидания начала обслуживания и времени пребывания заявки в системе. Наконец, совсем недавно появились работы, позволяющие рассчитывать стационарные характеристики однолинейной СМО вида G/MSP/1/r с марковским процессом обслуживания и накопителем конечной и бесконечной очереди [7, 9]. В [7] для системы G/MSP/1/r в случае конечного числа мест ожидания, т. е. г < оо, было получено стационарное распределение длины очереди. Однако предложенная там вычислительная процедура хорошо работала только для относительно небольших значений г. В [9] предложен другой способ исследования системы G/MSP/1/r, основанный на методе последовательного исключения состояний вложенной цепи Маркова. Метод исследования СМО с помощью построения вложенной цепи Маркова дал возможность получить стационарные распределения времени ожидания начала обслуживания и времени пребывания произвольной, принятой к обслуживанию заявки. В работах Албореса с соавтором [31, 32] была рассмотрена многолинейная система с рекуррентным потоком, марковским обслуживанием и накопителем конечной емкости. Но полученные там алгоритмы расчета стационарных вероятностей применимы лишь к системам с малым числом приборов, фаз обслуживания и мест ожидания.

Среди новейших инфотелекоммуникационных систем встречаются системы, требующие применение моделей СМО с полумарковским потоком, обобщающим рекуррентный и марковский потоки (полумарковский поток в большинстве случаев, когда использование рекуррентного или марковского процесса является неадекватным, весьма точно позволяет отразить свойства описываемой реальной системы). Однолинейная система с полумарковским входящим потоком, двумя типами заявок, марковским обслуживанием была рассмотрена в работе А.В. Печинкина и С.И. Тришечкина [19]. До настоящего времени не было работ, посвященных моделям многолинейных СМО с полумарковским входящим потоком и марковским обслуживанием.

В диссертации также рассмотрена модель СМО с отрицательными заявками. Модели СМО с отрицательными заявками тесно связаны с G-сетями [8, 1] и являются предметом интенсивных исследований. Первая работа, в которой была исследована однолинейная СМО с неограниченным накопителем с отрицательными заявками, принадлежит Е. Геленбе с соавторами [43]. В дальнейшем системы с отрицательными заявками рассматривались в работах П. Харрисона [44], П.Харрисона с соавторами [45, 46, 39], Н.Байера и О.Боксмы [36], И.Атенсиа с соавторами [33, 34, 35], Д.Албореса, П.П.Бочарова и Д. Ю.Любина [29, 30]. Хотя понятие отрицательной заявки было введено Е. Геленбе сравнительно недавно, однако в ТМО уже давно известны СМО с ограниченным временем пребывания или, что то же самое, СМО с нетерпеливыми заявками (см., например, Б.В. Гнеденко [13]), которые по своей сущности практически ничем не отличаются от отрицательных заявок.

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

Кратко остановимся на содержании диссертации.

Заключение диссертации по теме «Теоретические основы информатики», Чаплыгин, Василий Васильевич

Выход

Время между поступлениями заявок | Ш\

Рис. 12. Задание условной ФР для элемента (1,1) ядра полу Маркове кого процесса генерации заявок из примера 36.

1пгмгнт 1) w пппумпркоагного npoucrca Экспоненциальный пра^асс 'J | Сохранить | быход

Параметр I э~М|

Рис. 13. Задание условной ФР для элемента (2.1) ядра пол у Маркове кого процесса генерации заявок из примера 36.

Заключение

В диссертационной работе решены следующие задачи:

1. Разработаны математические методы расчета стационарных характеристик моделей СМО: многолинейной СМО с полумарковским входящим потоком, марковским обслуживанием и накопителем конечной и бесконечной емкости; однолинейной СМО с рекуррентным входящим потоком и групповым марковским обслуживанием; многолинейной СМО с рекуррентным входящим потоком, обслуживанием фазового типа на каждом приборе и потоком отрицательных заявок.

2. Разработаны алгоритмы для вычисления основных стационарных характеристик рассмотренных систем по полученным математическим соотношениям.

3. Для моделей многолинейных СМО с полумарковским входящим потоком на основе предложенных численных алгоритмов создан прикладной программный комплекс для расчета следующих стационарных характеристик: стационарного распределения числа заявок в системе по времени и по моментам поступления заявок в систему; стационарной вероятности потери заявки; средней длина очереди; среднего числа занятых приборов; среднего числа заявок в системе; стационарного распределения времени ожидания начала обслуживания и времени пребывания заявки в системе и их средних значений.

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

1. Башарин Г. П., Бочаров П. П., Коган А. Я. Анализ очередей в вычислительных сетях. Теория и методы расчета. Москва, Наука, 1989. 336 с.

2. Беллман Р. Введение в теорию матриц. Москва, Физматгиз, 1969. 367 с.

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

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

5. Бочаров П.П. Анализ системы массового обслуживания MAP/G/1/r конечной емкости. // Вестник РУДН. Сер. «Прикладная математика и информатика». 1995. № 1. С. 52-67.

6. Бочаров П. П. Стационарное распределение конечной очереди с рекуррентным потоком и марковским обслуживанием // Автоматика и телемеханика. 1996. № 9. С. 66-78.

7. Бочаров П.П., Вишневский В. М. G-сети: развитие теории мультипликативных сетей. // Автоматика и телемеханика. 2003. № 5. С. 4674.

8. Бочаров П. П., ДАпиче Ч., А. В. Печинкин, Салерно С. Система массового обслуживания G/MSP/1/r // Автоматика и телемеханика. 2003. JVs 2. С. 127-143.

9. Бочаров П.П., Печинкин А.В. Теория массового обслуживания. Москва, Изд-во РУДН, 1995. 529 с.

10. Бочаров П.П., Печинкин А.В., Д'Апиче Ч., Фонг Н.Х. Однолинейная система обслуживания конечной емкости с групповым марковским потоком и полумарковским обслуживанием // Вестник РУДН. Сер. «Прикладная математика и информатика». 2001. № 1. С. 64-79.

11. Воеводин В. В., Кузнецов Ю. А. Матрицы и вычисления. Москва, Наука, 1984. 320 с.

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

13. Королюк В. СТурбин А. Ф. Полумарковские процессы и их приложения. Киев, Наукова думка, 1976. 184 с.

14. Наумов В.А. Марковские модели потоков требований // Системы массового обслуживания и информатика. 1987. № 1. С. 67-73.

15. Печинкин А.В. Об одной инвариантной системе массового обслуживания // Math. Operationsforsch. und Statist. Ser. Optimization. 1983. Vol. 14, № 3. S. 433-444.

16. Печинкин А.В. Однолинейная система обслуживания с марковским входящим потоком требований // Автоматика и телемеханика. 1996. № 4. С. 100-110.

17. Печинкин А.В. Ветвящийся процесс, управляемый цепью Маркова. // Вестник РУДН. Сер. «Прикладная математика и информатика». 1999. № 1. С. 115-127.

18. Печинкин А.В., Тришечкин С.И. Система SM2/MSP/l/r с дисциплиной случайного выбора заявки на обслуживание и общим накопителем // Системы и средства информатики: спец. выпуск. Москва, Изд-во института проблем инфоматики РАН, 2002. С. 160-180.

19. Печинкин А.В., Чаплыгин В.В. Исследование системы массового обслуживания SM/MSP/n/r // Труды международного семинара «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения (DCCN-2003)». Москва, 2003. С. 58-65.

20. Печинкин А.В., Чаплыгин В. В. Стационарные характеристики системы массового обслуживания G/MSP/n/r // Вестник РУДН. Сер. «Прикладная математика и информатика». 2003. № 1. С. 119-143.

21. Печинкин А.В., Чаплыгин В.В. Стационарные характеристики системы массового обслуживания SM/MSP/n/r // Автоматика и телемеханика. 2004. № 9. С. 85-100.

22. Печинкин А.В., Чаплыгин В.В. Математическая модель для расчета многолинейных СМО // Тезисы докладов II научной сессии Института проблем информатики Российской академии наук. Москва, 2005. Р. 94-96.

23. Севастьянов Б. А. Эргодическая теоремадля марковских процессов и ее приложение к телефонным линиям с отказами // Теория вероятностей и ее прим. 1957. Т. 2, Вып. 1. С. 106-116.

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

25. Чаплыгин В.В. Система массового обслуживания G/BMSP/1/r // Информационные процессы. 2003. Т. 3, № 2. С. 97-108.

26. Чаплыгин В.В. Система массового обслуживания SM/MSP/1/r // Вестник МГТУ им. Н.Э. Баумана. Сер. «Естественные науки».2004. № 2. С. 60-74.

27. Чаплыгин В.В. Система массового обслуживания G/MSP/n/r с потоком отрицательных заявок // Информационные процессы. 2005. Т. 5, № 1. С. 1-19.

28. Albores J.F., Bocharov P.P., Luybin D.Yu. Two-stage exponential queueing system with internal losses, feedback and negative arrivals // Вестник РУДН. Сер. «Прикладная математика и информатика». 2003. № 1. С. 70-84.

29. Albores J.F., Bocharov P.P., Luybin D.Yu. On two-stage exponential system with losses, feedback and negative customers // Proc. of Internal Conference «Distributed Computer and Communication Networks.

30. Stochastic Modelling and Optimization (DCCN-2003)». Moscow, 2003. P. 100-105.

31. Albores J.F., Tajonar S.F. The multi-server GI/MSP/c/r queue // Transactions of XXIV International Seminar on Stability Problems for Stochastic Models. Jurmala, Latvia, 2004. P. 110.

32. Albores J.F., Tajonar S.F. Analysis of the GI/MSP/c/r Queueing System // Информационные процессы. 2004. Т. 4, № 1. С. 46-57.

33. Atencia I., Aguillera G., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. Oper. Res. 42 Annual Conf. University of Swamsea. 2000. P. 30-34.

34. Atencia I., Bocharov P. P. On the M/G/1/0 queueing system under LCFS PR discipline with repeated and negative customers with batch arrivals // Proc. 3-rd Europ. Cong. Math. Barcelona, 2000. P. 133.

35. Atencia I., DApiche C., Manzo R., Salerno S. Retrial queueing system with several input flows and negative customers and LCFS PR discipline // Proc. Fourth Int. Workshop on Queueing Networks with Finite Capacity. Ilkley, U. K., 2000. P. 1-9.

36. Bayer N., Boxma O. J. Wiener-Hopf analysys of an M/G/l queue with negative customers and of related class of random walk // Queueing Systems. 1996. V. 23. P. 301-316.

37. Bocharov P.P., DApice C., Pechinkin A.V., Salerno S. Queueing Theory. Utrecht, Boston: VSP, 2004. 446 p.

38. Bocharov P.P., Naumov V.A. Matrix-geometric stationary distribution for the PH/PH/l/r queue // Electron. Informmationsverarb. Kyb. 1986. Vol. 22, № 4. P. 179-186.

39. Chakka R., Harrison P. G. A Markov modulated multi-server queue with negative customers — The MM CPP/GE/c/L G-queue // Acta Informatika. 2001. V. 37. P. 881-919.

40. Dudin A.N., Klimenok V.I. BMAP/SM/1 queue with Markov modulated retrials // TOP. 1999. V. 7. P. 267-278.

41. Dudin A.N., Klimenok V.I. Alternative algorithm for characteristics calculation of BMAP/SM/1 system with the multi-threshold control // Queues: Flows, Systems, Networks. Minsk, BSU, 2001. V. 16. P. 81-86.

42. Erlang A.K. Solution of some problemsin the theory of probabilities of significance in automatic telephone exchanges // The Post Office Electrical Engineers Journal. 1917. Vol. 10. P. 189-197.

43. Gelenbe E., Glynn P., Sigman K. Queues with negative arrivals. // J. Appl. Prob. 1991. V. 28. P. 245-250.

44. Harrison P. G. The MM CPP/GE/c G-queue: sojourn time distribution // Queueing Sytems. 2002. V. 41. P. 271-298.

45. Harrison P. G., Pitel E. Sojourn times in single server queues with negative customers // Queueing systems. 2002. V 41. P. 943-963.

46. Harrison P. G., Pitel E. The M/G/l queue with negative customers // Adv. Appl. Prob. 1996. V. 28. P. 540-566.

47. Kendall D.J. Stochastic processes ocurring in the theory of queues and their analysys by the method of the embedded Markov chains // Ann. Math. Stat. 1953. № 24. P. 338-354.

48. Klimenok V.I. The Controlled BMAP/SM/1 Retrial Queue with Markov Modulated Retrials. // Proc. of Internat. Conference «Distributed Computer and Communication Networks. Stochastic Modelling and Optimization (DCCN-2003)». Moscow, 2003. C. 81-88.

49. Lindley D. V The theory of queueswith a single server // Proc. Camb. Phil. Soc. 1962. Vol. 58, № 3. P. 497-520.

50. Lucantoni D.M., Neuts M.F. Simpler proofs of some properties of the fundamental period of the MAP/G/1 queue // J. Appl. Prob. 1994. V. 31. P. 235-243.

51. Neuts M.F. Matrix-geometric solutions in stochastic models. An algorithmic approach. Baltimore and London, The Johns Hopkins Univ. Press, 1981. 332 p.

52. Pechinkin A., Chaplygin V. The Stationary Characteristics of an SM/MSP/n/r Queueing System // XXIII Seminar on Stability Problems for Stochastic Models. Pamplona, Spain, 2003. P. 32.

53. Pechinkin A., Chaplygin V. The mathematical methods and the algorithms for a multichannel queues calculation // Transactions of XXIV International Seminar on Stability Problems for Stochastic Models. Ju-rmala, Latvia, 2004. P. 110.

54. Takacs L. Introduction to the theory of queues. New York, Oxford University Press, 1962. 268 p.