Телеграм канал «NoML Digest»

Про сети очередей

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

Примером классического результата являются так называемые сети Джексона: при ряде условий стационарное распределение поведения всей сети раскладывается в произведение распределений отдельных узлов, как будто узлы независимы друг от друга. То есть задача решается аналитически и это сильно облегчает анализ системы. Но стоит отойти от этих условий (добавить ограниченную ёмкость буферов и блокировки, приоритеты, не-марковсть, ...) и аналитическое решение уже невозможно, тогда надо применять приближённые численные методы и имитационное моделирование (ИМ).

Пара книг по которым можно познакомиться с областью подробнее:
• J.F. Shortle, J.M. Thompson, D. Gross, C.M. Harris, Fundamentals of Queueing Theory, 2018. Хорошая вводная книга по ТМО, от простых очередей, до сетевых моделей (сети Джексона), фокус прежде всего на аналитические методы, но упоминается также ИМ и численные методы.
• G. Bolch, S. Greiner, H. de Meer, K. Trivedi, Queueing Networks and Markov Chains, 2006. Отличная книга в качестве второй по ТМО, уже с фокусом на сетевые модели. В ней же очень хорошая глава 2 про марковские цепи. Плюс рекомендую (может быть даже в первую очередь) почитать разделы 1.1-1.2 про таксономию задач, методов решения и так называемых концептуализаций/формализаций, то есть как описывать системы различными парадигмами.

С практической точки зрения можно посмотреть на туториалы открытых фреймворков:
• Ciw
• queueing-tool
• LINE
• JMT

Более полный список материалов по ТМО и ИМ ведется в нашей базе знаний->