МАССОВОГО ОБСЛУЖИВАНИЯ СИСТЕМА

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

Наиболее естественными характеристиками состояния систем с очередью являются следующие: а) время w_n ожидания начала обслуживания требования с номером пи виртуальное время w(t).ожидания, к-рое определяется как время, необходимое для освобождения системы от вызовов, пришедших до момента времени t; б) длина q _п очереди в момент прихода n-го вызова и длина q(t).очереди в момент времени t.

1) В "ординарном" случае значения w_n связаны рекуррентным соотношением

Такого же типа уравнениями (для времени ожидания или для длины очереди) могут описываться системы с ожиданием и в "неординарном" случае, когда отличны от единицы. Напр., для длины q_n очереди справедливы соотношения

где b_n - число вызовов, к-рое может быть обслужено за время при бесперебойной работе системы. Если то распределение b_n можно найти из соотношений

где а - показатель распределения

Если обозначить то решение уравнения (1) имеет вид

Отсюда следует, что если

при любом фиксированном интервале и то существует предельное распределение времени ожидания:

где

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

удовлетворяют уравнению (1) и имеют распределение, совпадающее с предельным распределением w_n. Это - стационарный процесс времени ожидания.

Пусть последовательность и эргодична ( с вероятностью 1). Тогда

если или если где В остальных случаях

Если то тогда и только тогда, когда (тривиальный случай исключается).

2) Как уже отмечалось, другой возможной характеристикой состояния системы является виртуальное время w(t).ожидания. Грубо говоря, это - время, к-рое прождал бы начала своего обслуживания вызов, пришедший в момент t. Пусть S(t) есть сумма времен обслуживания вызовов, поступивших в систему до момента времени t, X(t)=S(t)-t. Аналогом равенства (3) здесь является соотношение

Пусть G_IS- класс процессов со стационарными в узком смысле приращениями и G_II - класс процессов с независимыми приращениями (G_II и G_IS здесь можно понимать и более узко; напр., можно считать, что G_II - класс обобщенных пуассоновских процессов с положительными скачками и сносом -1). Если процесс то он может быть расширен до процесса заданного на всей оси и также принадлежащего G_IS В этом случае существует

где

Если, кроме того,

то распределение процесса

сходится при

к распределению процесса

к-рый является собственным стационарным процессом виртуального времени ожидания. Сходимость здесь имеет место в сильной форме:

для любого измеримого В.

Далее, если и а<0, то существует условная функция восстановления Н ₀ (х).процесса X(t).

при этом

Приведенные формулы сохраняются и в случае

Для систем, у к-рых существуют простые связи между распределениями w^k и w^s(t).3) Эргодические теоремы для длины очереди могут быть получены с помощью соответствующих теорем для времени ожидания. Пусть, напр., последовательность эргодична (метрически транзи-тивна).' Если, кроме того, то существует предельное (стационарное) распределение q_n такое, что

Если же

и распределение

нерешетчато, то существует

где все компоненты под знаком вероятности в правой части независимы, g имеет плотность, равную

Если

то предельные распределения q_n и q(t).совпадают.

4) Если

(допускается также, что

то можно получить точные формулы и для допредельного распределения w(t).

При a<0 и имеет место формула X и н ч и н а для стационарного распределения:

где q - величина скачка процесса X(t)(если

), a - показатель распределения Пусть T_j,;=1, 2, ...,- п е р и о д ы занятости системы (т. е. длины интервалов времени в течение к-рых w(t)>0). Тогда для рассматриваемых систем

5) Для систем, у к-рых

(допускается, также

распределение w^k совпадает с распределением величины

По известному распределению x_j распределение Yможет быть найдено следующим образом. Если (это всегда при ), то справедливо следующее факторизационное тождество

где - величина первой неположительной суммы среди x₁, x₁+x₂, ... Это соотношение позволяет отождествить с отношение в любом тождестве

в к-ром функции

допускают представление

( - функции ограниченной вариации). Равенство (5).осуществляет т. н. V-факторизацию функции Оно позволяет указать следующие случаи, когда возможно отыскание в явном виде.

Предполагают, что и обозначают

так что

А) Если -рациональная функция: где Р _т к Q_n- многочлены степеней ти n соответст-

венно, то функция (1-f)Q_n в области Iml<0 имеет ровно пнулей l₁, ..., l_n и

Это означает, что если распределение t^s представимо в виде

где Р _k (х) - многочлены, то такого же вида представление (при других a_k и Р _k, определяемых нулями l₁, ..., l_n) будет иметь место и для

В) Если - рациональная функция, то функция (i-f)Q_n в области Iml>0 имеет n-1 нулей l₁, ..., l_n-1 и

Кроме этих формул, дающих явное выражение для распределения У, можно также в широком классе случаев описать асимптотич. поведение при Именно, если

и то определен единственный корень q>0 уравнения В этом случае при

Если же

то

Постоянные с ₁ и с ₂ найдены в явном виде.

Результаты, аналогичные изложенным в пп. 2) - 5), справедливы и для систем с дискретным временем, когда время tи случайные величины управляющих последовательностей принимают лишь целочисленные значения.

6) Теоремы устойчивости выясняют условия, при к-рых малое изменение конечномерных распределений управляющих последовательностей влечет за собой малое изменение стационарного распределения времени ожидания или длины очереди. Важность вопроса об устойчивости систем обслуживания объясняется тем, что обычно в реальных задачах пользуются теми или иными предположениями о природе управляющей последовательности (напр., предполагается, что x_j независимы или что t^e_j распределены по показательному закону), в то время как на самом деле эти предположения выполняются лишь приближенно. Спрашивается, будет ли решение таких "идеализированных" задач близко к решению истинной задачи.

Чтобы получить точную постановку проблемы рассматривают схему серий, когда уравнением (1) управляют стационарные последовательности (серия последовательностей)

Кроме того, рассматривают стационарную последовательность

и обозначают

Ответ на поставленный выше вопрос дает следующее утверждение.

Пусть конечномерные распределения x⁽ⁿ⁾ слабо сходятся к соответствующим распределениям последовательности x, относительно к-рой предполагается, что она эргодична и Тогда для слабой сходимости

(т. е. для сходимости распределений стационарных времен ожидания) достаточно, чтобы

Сформулированное условие сходимости близко к необходимому.

Если управляющие последовательности и таковы, что независимы, а распределения слабо сходятся к распределениям , то для выполнения (6) достаточно, чтобы

Аналогично обстоит дело со стационарным распределением виртуального времени w^s(t).ожидания. Если конечномерные распределения процессов сходятся к распределениям и последовательность эргодична, то для сходимости распределений

достаточно, чтобы

7) Асимптотич. методы исследования одноканалъных систем (они включают в себя и теоремы устойчивости) дают приближенные формулы для случая больших и малых нагрузок. Пусть Тогда говорят, что система имеет большую нагрузку, если

близко к 0, и малую нагрузку, если аблизко к -1. Точная постановка задачи связана здесь как и в п. 6) с введением схемы серий. Именно, для случая больших нагрузок рассматривают процессы X^a(t), зависящие от параметра Пусть Х ^а(t).удовлетворяют условиям слабой зависимости, обеспечивающим при выполнение условий

равномерно по а, где

Тогда для стационарного виртуального времени w^s(t).при справедливо

Аналогичный результат будет иметь место и для стационарного распределения w^k.

Если условия большой нагрузки наложить на последовательности (также в схеме серий по параметру п), потребовав, чтобы

то весьма полно можно описать также и распределение допредельного времени w_n ожидания, включая т. н. переходные явления. Именно, пусть в дополнение к (7)

при любом Тогда если при не меняя знака, так что то

где w(и) - стандартный винеровскии процесс. Значение правой части (8) вычислено в явном виде. Если то

Если

то

Если

то

8) Системы с ограниченной очередью характеризуются тем, что вызовы, пришедшие в систему и заставшие очередь объема получают отказ и выбывают из рассмотрения. В этом случае а вероятность будет также вероятностью того, что n-й вызов получил отказ.

Уравнения (2) здесь следует заменить на уравнение вида

Пусть и последовательность метрически транзитивна. Пусть, кроме того, выполнено следующее условие: или или но во втором случае h_n не представимы в виде где При выполнении этих условий существует предельное распределение q _п при

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

Существует также следующее представление для стационарного паспведеления:

где - положение частицы, вышедшей из О и блуждающей со скачками h_k, k=1, 2, ..., в момент ее первого выхода за пределы интервала (-l, т). Если (т. е. если . то вероятности (9) могут быть явным образом выражены через распределения

9) В системах с автономным обслуживанием обслуживание вызовов в отличие от обычных систем с ожиданием может начинаться лишь в моменты времени О, где - элементы управляющей последовательности. Таким образом, вызов, заставший систему свободной, должен ждать до начала очередного этапа обслуживания.

Наряду с процессом {e(t)}, описывающим входящий поток, рассматривают процесс {s(t)}, где s(t).определяется как число вызовов, к-рое приняла бы на обслуживание система к моменту tпри бесконечной очереди. Обозначив через q(t).длину очереди в момент t, не считая вызовов уже находящихся на обслуживании, и положив X(t) = e(t)-s(t), получают

Это равенство аналогично соотношению (4) и приводит к следующему результату. Если процесс и эргодичен,

то распределение процессов

сходится при к распределению стационарного процесса

Если или а остальные управляющие подпоследовательности принадлежат G₁, то можно указать явные формулы для распределения

Лит. см. при ст. Массового обслуживания теория.

А. А. Боровков.