Теория массового обслуживания: сети Джексона и анализ многоузловых систем очередей

Математическая модель сети Джексона состоит из набора K узлов (систем обслуживания). В каждый узел могут поступать заявки из внешней среды (согласно пуассоновскому процессу с определенной интенсивностью). Внутри узла заявки обрабатываются одним или несколькими серверами (экспоненциальное распределение времени). Самым важным элементом модели является маршрутная матрица вероятностей. После завершения обслуживания в узле i заявка не исчезает, а с вероятностью P_ij переходит в очередь узла j, либо с вероятностью (1 - сумма P_ij) навсегда покидает сеть. Эта структура формирует сложный марковский процесс, в котором задержка в одном узле немедленно сказывается на длине очередей во всех последующих этапах технологической цепи.

Великая теорема Джексона для открытых сетей гласит: несмотря на то, что потоки внутри сети пересекаются, ветвятся и не являются строго пуассоновскими, стационарное распределение вероятностей состояний всей сети имеет форму мультипликативного произведения (Product Form). Это означает, что вероятность того, что в первом узле находится n1 заявок, во втором n2 заявок и так далее, вычисляется как простое произведение вероятностей для каждого отдельного узла, как если бы они работали абсолютно изолированно друг от друга (в режиме M/M/1 или M/M/c). Это алгебраическое чудо избавляет инженеров от необходимости решать дифференциальные уравнения для миллионов комбинированных состояний сети, сводя расчет к последовательному анализу одиночных систем.

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

Концепция сетей массового обслуживания получила мощное развитие в теореме Гордона-Ньюэлла для закрытых сетей. В закрытой сети (например, парке курсирующих заводских вагонеток или системе циркулирующих паллет) нет внешних поступлений и выходов; строго фиксированное количество заявок вечно вращается между узлами сети. Здесь вероятности состояний также имеют мультипликативную форму, но они нормируются специальной константой (Normalization Constant), вычисление которой требует сложных рекурсивных алгоритмов (алгоритм Бузена). Аппарат сетей Джексона и Гордона-Ньюэлла стал абсолютным базисом для проектирования архитектуры современных многоядерных процессоров, оценки производительности облачных серверов (Cloud Computing) и оптимизации пропускной способности узловых аэропортов (Hub-and-Spoke).