В этом параграфе мы обсудим несколько примеров систем и сетей очередей.

Начнем с рассмотрения так называемой одноканальной системы обслуживания. В системе находится один прибор (сервер). Вызовы поступают в систему группами случайного объема через единичные интервалы времени (пусть X_n і 0 означает количество вызовов, поступающих в момент времени n = 1,2, ј; все возможные значения X_n являются целыми числами). Все вызовы нумеруются и обслуживаются в порядке поступления (внутри каждой группы вызовы нумеруются в произвольном порядке). Как только сервер заканчивает обслуживание некоторого вызова, он немедленно начинает обслуживать следующий (если вызовы в системе есть), а обслуженный вызов покидает систему. Сервер может простаивать только тогда, когда в системе нет вызовов.

Предположим, простоты ради, что все вызовы имеют одно и то же неслучайное время обслуживания b > 0. Будем считать, что случайные величины X_n независимы и одинаково распределены. Следовательно, они имеют одно и то же математическое ожидание (среднее), которое обозначим через a = M(X_n) > 0. В начальный момент времени n = 0 вызовы в системе отсутствуют.

Обозначим через W_n количество "работы", скопившейся в системе к моменту времени n (то есть суммарное время, нужное для обслуживания имеющихся в наличии вызовов). Ясно, что W₁ = b X₁ и при всех n = 2,3, ј справедливы рекуррентные соотношения

Естественно считать, что система работает "стабильно", если с ростом времени n распределения случайных величин W_n остаются ограниченными - в некотором смысле, но в каком? Можно, к примеру, назвать систему стабильной, если найдется некоторое число K, при котором неравенство W_n Ј K выполняется всегда (т.е. при каждом n с вероятностью единица). Но для выполнения этого условия необходимо, чтобы с вероятностью единица имело место неравенство

Отметим, что предположение (3.2) является сильно ограничительным и малореалистичным, так как на практике возможны резкие (хотя и редкие) колебания входного потока во времени (так называемые "пиковые нагрузки"), т.е. величины X_n могут принимать большие значения - но с маленькими вероятностями. Поэтому представляется разумным следующее (более "широкое") определение стабильности.

Система обслуживания является стабильной, если для любого (как угодно малого) числа e найдется такое число K, что при всех n

Оказывается, что для того, чтобы определить, является одноканальная система стабильной или нет, не требуется знания распределения случайных величин X_n - достаточно лишь знать значение их среднего a. Более точно, имеет место следующая теорема

Теорема 3.1. Одноканальная система обслуживания является стабильной при ab < 1 и нестабильной при ab > 1. В случае ab = 1 система является стабильной тогда и только тогда, когда величины X_n являются вырожденными, т.е. P (X_n = a) = 1.

Поясним, как доказывается эта теорема. Начнем со случая ab = 1. Если все X_n вырождены (и совпадают с a), то W_n є 1 при всех n. Поэтому система стабильна. В случае невырожденных случайных величин заметим, что при каждом n

Рассмотрим случай ab > 1. Если случайные величины X_n вырождены, то величины W_n = ab + (n-1) (ab-1) неограниченно растут с ростом n. Если же X_n невырождены, то, повторяя ранее изложенные рассуждения, мы получаем неравенство:

В случае ab < 1 утверждение Теоремы 3.1 доказывается значительно сложнее, и мы его приводить не будем. Опишем лишь один полезный прием, используемый при доказательстве и называемый часто "правилом насыщения" (saturation rule). Предположим, что к некоторому моменту времени n в системе скопилось очень много вызовов (система "насыщена" вызовами). Тогда, начиная с момента n, в течение длительного времени сервер обслуживает только имеющиеся вызовы - независимо от того, что еще в систему поступает. Допустим, что так сервер работает в течение времени T. За это время обслуживается приблизительно ^T/_b вызовов (то есть сервер обслуживает приблизительно ¹/_b вызовов за единицу времени, эту дробь естественно назвать интенсивностью, или скоростью обслуживания), а поступает X_n+1 + X_n+2 + ј + X_n+T вызовов. По закону больших чисел,

И действительно, как показывает более точный и строгий анализ, для одноканальной системы использование правила насыщения оказывается корректным.

Приведем еще два примера систем, где условия стабильности находятся аналогичным образом.

Пример 3.1. Одноканальная система с двумя типами вызовов. В систему с одним сервером поступают вызовы двух типов: в каждый момент времени n приходят X_n⁽¹⁾ вызовов первого типа и X_n⁽²⁾ - второго типа. Для каждого i = 1,2, случайные величины X₁⁽ⁱ⁾, X₂⁽ⁱ⁾, ј независимы и одинаково распределены со средним

Наиболее известные варианты дисциплин:

• Дисциплина первый пришел - первый обслуживается (first come first served, FCFS). При этой дисциплине сначала (в произвольном порядке) обслуживаются вызовы, пришедшие в момент времени n = 1, затем вызовы, пришедшие в момент n = 2, и т.д.
• Приоритетная дисциплина. Вызовы первого типа имеют приоритет перед вызовами второго типа. Это означает, что вызовы разных типов образуют две разные очереди, и в каждый момент, когда сервер заканчивает обслуживание какого-то вызова, на обслуживание направляется вызов первого типа (первый вызов из первой очереди), и только если первая очередь пуста, то разрешается обслуживание вызову второго типа.

Справедлива следующая

Теорема 3.2. Обозначим r = a₁b₁+a₂b₂. Каков бы ни был порядок (дисциплина) обслуживания вызовов, одноканальная система с двумя типами вызовов является стабильной при r < 1 и нестабильной при r > 1. В случае r = 1 система является стабильной тогда и только тогда, когда величины X_n⁽¹⁾ и X_n⁽²⁾ являются вырожденными, т.е.

Доказательства теорем 3.1 и 3.2 используют одни и те же рассуждения.

Пример 3.3. Открытая сеть Джексона с двумя серверами и одним типов вызовов. Пусть в сети находятся два сервера, время обслуживания любого вызова на первом неслучайно и равно b₁, а на втором - b₂. В каждый момент времени n = 1,2, ј в сеть извне поступает X_n вызовов, причем случайные величины X₁, X₂, ј независимы и одинаково распределены со средним a. Каждый вызов (независимо от других) с вероятностью s₁ встает в очередь к первому серверу и с вероятностью s₂ = 1-s₁ - ко второму. Любой вызов, обслуженный на первом сервере, либо покидает сеть (с вероятностью r_1,0), либо встает в очередь ко второму (с вероятностью r_1,2). Здесь r_1,0+r_1,2 = 1. Аналогично, после обслуживания на втором сервере вызов с вероятностью r_2,0 покидает сеть и с вероятностью r_2,1 переходит в очередь к первому серверу (где r_2,0+r_2,1 = 1). Для того, чтобы вызовы имели возможность покинуть сеть, требуется, чтобы сумма r_1,0+r_2,0 была положительной. Посчитаем, какое число раз в среднем любой вызов посетит первый сервер (нам нужно найти M(n₁), где n₁ - случайное число посещений).

В случае, когда вызов сразу поступил в очередь к первому серверу, вероятность q того, что он снова вернется на этот сервер хотя бы раз (другими словами, посетит этот сервер хотя бы два раза), равна вероятности того, что он переходит с первого сервера на второй и затем - со второго на первый. Так как эти события независимы, то

Если предположить, что сначала вызов поступает на второй сервер, то вероятность того, что он посетит первый сервер хотя бы раз, равна r_2,1, хотя бы два раза - r_2,1q, хотя бы три - r_2,1q² и т.д. Следовательно, в этом случае среднее число посещений первого сервера равно

Симметрично, среднее число M(n₂) посещений одним вызовом второго сервера равно [1/(1-q)] (s₂+s₁r_1,2).

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

Каждый вызов посетит в среднем первый сервер M(n₁) раз. Значит, он в среднем "приносит" на этот сервер количество работы, равное b₁M(n₁). За единицу времени в систему поступает в среднем a вызовов. Значит, все они вместе приносят на первый сервер количество работы ab₁M(n₁). Обозначим это число через r₁. Если первый сервер "насыщен", то он постоянно занят (работает с интенсивностью единица). Поэтому для стабильности нужно, чтобы выполнялось условие r₁ Ј 1. Аналогично, требуется и второе условие: r₂ є ab₂M(n₂) Ј 1.

Поэтому неудивительно, что имеет место следующая теорема.

Теорема 3.3. Открытая сеть Джексона с двумя серверами может быть стабильной только в следующих случаях:

• max (r₁, r₂ ) < 1;
• случайная величина X₁ вырождена, max ( r₁, r₂ ) = 1 и выполнено одно из условий:

  либо r_1,0 = r_2,0 = 1,

  либо r_1,0 = 1, r_2,0 = 0,

  либо r_1,0 = 0, r_2,0 = 1.

Теорема 3.2 обобщается естественным образом на случай любого числа вызовов, а теорема 3.3 - любого числа серверов.

До конца 80-х годов у многих ученых, работающих в области теории систем обслуживания, была надежда на то, что "правило насыщения" является универсальным, т.е. с его помощью всегда можно найти верные условия стабильности систем обслуживания. Однако в 1990 году Р.П.Кумар привел относительно простой пример детерминированной (неслучайной) системы, в которой условия стабильности существенно отличаются от получаемых с помощью этого правила. Затем А.Л.Столяр и А.Н.Рыбко (1992) построили пример системы со случайными характеристиками, имеющей те же свойства. Эти и другие примеры привели к развитию так называемой "теории жидкостной аппроксимации", позволяющей анализировать условия стабильности случайных систем обслуживания с помощью вспомогательных динамических "жидкостных" моделей, удовлетворяющих ряду интегро-дифференциальных уравнений.