Полумарковские системы обслуживания

К нолумарковским СМО относятся системы, поведение которых в момент времени t может быть описано ПМП. В частности, сюда относятся СМО MGN _у GM N для 0 < N< со, 1</?<�оо.

В качестве примера рассмотрим СМО M|G|l|oo. Пусть на вход одноканальной системы обслуживания поступает простейший поток заявок с параметром X. В системе имеется неограниченное число мест для ожидания, поэтому заявка, заставшая систему свободной, сразу поступает на обслуживание, а заявка, заставшая систему занятой, поступает в очередь и ожидает начала обслуживания. Длительности обслуживания заявок являются независимыми, одинаково распределенными случайными величинами, функцию распределения которых обозначим через B (t) = P (r < t). Предполагаем также, что в начальный момент функционирования заявок в системе нет.

Поскольку время обслуживания произвольно распределено, то ?(t) — число заявок в момент времени t — немарковский процесс. Поэтому при исследовании стационарного распределения длины очереди СМО M|G|l |со применяют метод вложенных цепей Маркова. Идея метода предельно проста и состоит в следующем.

1. Выбирают моменты времени x_t, т₂, т", …, в которые процесс %(?),.

описывающий эволюцию системы массового обслуживания во времени, образует однородную цепь Маркова.

2. Изучают предельное эргодическое распределение этой однородной цепи = ^(т"), т. е. р, = lim Р{Цх,) = j}.

оо.

3. Доказывают факт совпадения пределов p_t = lim Р{^(х_п) = j) =

^J И—КС.

= lim P№)=Jl

t-> оо Пусть ij < т₂ < т₃ <… — моменты уходов заявок из СМО M|G|l|co или моменты поступления в пустую СМО, а Ъ,_п = Ь>(т_п + 0) — число заявок, оставшихся в системе после ухода из нее п-й по счету заявки. Легко видеть, что {%", п > 1} — цепь Маркова, вложенная в !;(?). Найдем матрицу переходных вероятностей этой цепи (р^). Вероятность того, что за время обслуживания заявки поступит j заявок, равна.

Очевидно, что.

и получаем следующую матрицу переходов:

Пусть выполнено условие р = ХЬ < , где  — среднее время обслуживания заявки. Очевидно, что рассматриваемая цепь однородна, неприводима и непериодична. По эргодической теореме Фостера [12] существует единственное совпадающее с эргодическим стационарное распределение, которое удовлетворяет уравнениям.

Учитывая формулу (6.22), равенство (6.23) можно записать в виде.

так как р^ = 0 для у < i — 1.

Введем производящие функции:

Учитывая соотношение (6.21), находим.

где  — преобразование Лапласа — Стильтьсса функции распределения B (t).

Пользуясь равенством (6.24), получим откуда

Из условия нормировки Ф (1) = 1 получим.

откуда следует р₀ = 1 — р.

Окончательно получаем.

Формула (6.25) называется формулой Поллячека — Хинчина.

Хинчину удалось показать, что стационарное распределение вложенной цепи для СМО МG 1 |со совпадает со стационарным распределением процесса ^(/), т. е.

Этот факт Хинчин назвал основным законом стационарной очереди.

Таким образом, формула (6.25) дает производящую функцию стационарного распределения заявок в системе. Среднее число заявок в стационарной системе M|G|1 легко находится из формулы (6.25) с помощью правила Лопиталя:

где о² = (3″ (0) — (Р'(0))² — дисперсия времени обслуживания заявки.

Формулу (6.26) также называют формулой Поллячека — Хинчина.