НАУКА и ОБРАЗОВАНИЕ

Файл статьи: Nesterov_P.pdf (855.92Кб)

УДК 519.872	Россия, МГТУ им. Н.Э. Баумана

Предметом исследования в данной статье является получение аналитических выражений для  функций распределения вероятностей (ФРВ) состояний  замкнутой системы массового обслуживания  (СМО) типа «модели ремонтника»  Mr|GIr|1||Nr в стационарном режиме. СМО имеет источник заявок конечной емкости с экспоненциальным распределением времени пребывания заявок разных классов в источнике, одну очередь с дисциплиной обслуживания заявок - относительные приоритеты, один обслуживающий аппарат (ОА) и произвольные ФРВ  времени обслуживания заявок каждого класса.

Метод  включает выполнение следующих шагов.

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

На втором шаге устанавливается  связь между ФРВ состояний СМО в стационарном режиме и полученными ранее ФРВ состояний вложенной цепи Маркова. В основе определения такой связи лежит построение системы уравнений глобального баланса для состояний СМО в стационарном режиме и состояний вложенной марковской цепи. Физический смысл такого баланса состоит в том, что каждое состояние СМО в стационарном режиме является равновесным, т.е. интенсивности  переходов из состояния и  в состояние равны между собой. Определено пространство состояний исходной СМО в стационарном режиме. Показано, что на отрезках времени обслуживания заявок в ОА процесс ведет себя как процесс чистого размножения, когда интенсивность гибели – перехода СМО в более «низкие» состояния – равна нулю. Получены аналитические выражения для вычисления стационарных  ФРВ данной СМО в зависимости от ФРВ вложенной цепи Маркова, дисциплины обслуживания  и ФРВ времен обслуживания заявок разных классов в ОА.

На третьем шаге выводятся выражения для вычисления средних значений времен пребывания и ожидания заявок каждого класса в СМО, а также выражения для определения загрузки ОА заявками каждого класса и общей загрузки ОА.  Вывод формул основан на свойстве консервативности (сохранения работы),справедливом для  дисциплины обслуживания с относительными  приоритетами, а также на использовании результата Литтла и  выражений для среднего числа заявок каждого класса в СМО, которые, в свою очередь, определяются с помощью  ФРВ   состояний СМО в стационарном режиме.

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

Список литературы

1. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Изд-во ЛКИ, 2007. 400 с.
2. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. 512 с.
3. Клейнрок Л. Теория массового обслуживания: пер. с англ. М.: Машиностроение, 1979. 432 с.
4. Клейнрок Л. Вычислительные системы с очередями: пер. с англ. М.: Мир, 1979. 600 с.
5. Нестеров Ю.Г. Декомпозиционный метод анализа замкнутых сетей массового обслуживания // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2014. № 2. Режим доступа: http://technomag.bmstu.ru/doc/700018.html (дата обращения 28.02.2014). DOI:10.7463/0214.0700018
6. Кёниг Д., Штойян Д. Методы теории массового обслуживания: пер. с нем. М.: Радио и связь, 1981. 128 с.
7. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения. М.: Высшая школа, 2000. 383 с.
8. Джейсуол Н. Очереди с приоритетами: пер. с англ. М.: Мир, 1973. 280 с.
9. Konig D., Rolsky T., Smidt V., Stoyan D. Stochastic processes with imbedded marked point processes (PMP) and their application in queuing theory // Math. Operationsforschung und Statistik. Ser. Optimization. 1978. Vol. 9. P. 125-142.
10. Little J.D.C. A proof for the queueing formula L = W // Operations Research. 1961. Vol. 9, no. 3. P. 383-387. DOI: 10.1287/opre.9.3.383
11. Szep A. Iterative Method for Solving M/G/l//N-type Loops with Priority Queues. Режим доступа: http://www.inf.u-szeged.hu/actacybernetica/edb/vol07n3/pdf/Szep_1986_ActaCybernetica.pdf (дата обращения 28.02.2014).
12. Fatnes J.N. Flow-times in an M/G/1 Queue under a Combined Preemptive/ Non-preemptive Priority Discipline: Master of Science in Physics and Mathematics. Norwegian University of Science and Technology, Department of Mathematical Sciences, 2010. Режим доступа: http://www.diva-portal.org/smash/get/diva2:348953/FULLTEXT01.pdf (дата обращения 28.02.2014).
13. Madan K.C. A Non-Preemptive Priority Queueing System with a Single Server Serving Two Queues M/G/1 and M/D/1 with Optional Server Vacations Based on Exhaustive Service of the Priority Units // Applied Mathematics. 2011. Vol. 2, no. 6. P. 791-799. DOI: 10.4236/am.2011.26106
14. Atar R., Biswas A., Kaspi H. Fluid limits of G/G/1+G queues under the non-preemptive earliest-deadline-rst discipline. Preprint. Technion - Israel Institute of Technology, Haifa, Israel, 2014. 28 p. Режим доступа: http://webee.technion.ac.il/people/atar/ata-bis-kas.pdf (дата обращения 28.02.2014).