§ 4. МЕТОД ВЛОЖЕННЫХ ЦЕПЕЙ МАРКОВА ПРИМЕНИТЕЛЬНО К МОДЕЛИ ОБСЛУЖИВАНИЯ (M/G/1)

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

Пусть число требований в очереди в момент Предположим, что процесс наблюдается в моменты окончаний операций обслуживания. При этом получается последовательность целых чисел

где последовательные моменты окончаний операций обслуживания. Последовательность образует процесс с дискретным временем

Ниже будет показано, что в силу «пуассоновости» входящего потока последовательность (4.2) является цепью Маркова.

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

Легко видеть, что этот процесс является марковским, поскольку если состояние системы в момент то

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

зависит только от V и не зависит ни от длины очереди, ни от момента начала обслуживания. Отсюда следует, что цепь Маркова.

Вероятностное распределение величины можно найти, налагая условие на значение V и применяя формулу полной вероятности

Далее, число требований, поступающих за время является случайной величиной с пуассоновским распределением, имеющим параметр Следовательно,

поэтому

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

Если обозначить

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

Детальный анализ цепи Маркова (4.4) уже был проведен в § 5 гл. 3. Там было доказано, что цепь является возвратной положительной, возвратной нулевой или невозвратной в зависимости от того, или соответственно, где

Величина

называется нагрузкой системы. Найдем теперь предельное распределение для данной цепи Маркова в случае

А. Стационарное распределение вложенной цепи Маркова

Найдем вектор

такой, что

где матрица определена равенством (4.4). Если выразить эти уравнения через величины то они примут вид

Найдем производящую функцию

через функцию

Умножая записанное выше равенство на получим

Суммируя и учитывая, что является сверткой, получим

Отсюда

Эта формула определяет производящую функцию стационарного распределения с точностью до постоянного множителя Поскольку

то дробь

стоящая в знаменателе выражения для стремится при к величине

Найдем среднее число требований, поступающих за время обслуживания одного требования:

очевидно, является нагрузкой системы), где средняя длительность интервала между моментами поступления. Поскольку стационарное распределение существует и, следовательно, Но из полученной формулы следует

поэтому

Таким образом производящая функция стационарного распределения равна

Величина является стационарной вероятностью того, что система свободна.

Б. Средняя длина очереди для системы (M/G/1) в стационарном режиме

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

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

Если число требований в очереди после ухода некоторого требования, число требований в очереди после следующего ухода, то

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

В стационарном режиме величина имеет такое же распределение, что и Таким образом, и

Из этого же выражения, поскольку имеем

Так как (см. определение ), то

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

Усредняя полученное равенство и учитывая (4.5), получаем

Поскольку в силу предположения о стационарности, то

Далее,

и

Следовательно,

поскольку

Таким образом

В. Среднее время ожидания

В условиях стационарности можно найти среднее время ожидания требования. Предположим, что требование ожидает время начала своего обслуживания, которое продолжается время Предположим, что, когда требование покидает систему, в очереди остается требований. Это означает, что за время поступило требований пуассоиовского потока. В силу стационарности сумма

должна равняться среднему числу требований, поступивших за этот период, умноженному на среднюю длительность интервала между требованиями, т. е. величине Но поскольку рассматривается стационарный режим, то в силу (4.6)

Деля на и вспоминая, что из последнего соотношения получим

или

Из формул (4.6) и (4.7) следует один несколько неожиданный факт. Именно: при заданных средних интервалах между поступлениями и длительностях обслуживания можно уменьшить

средние длину очереди и время ожидания, уменьшая дисперсию времени обслуживания. Очевидно, что наилучшим в этом отношении случаем является постоянное время обслуживания.

Г. Распределение времени ожидания

В тех же предположениях, что и выше, найдем преобразование Лапласа распределения времени ожидания. Пусть равновесные вероятности, производящая функция которых была найдена выше. Если требование ожидает время начала обслуживания и обслуживается время V, то вероятность того, что после его ухода останется требований, равная совпадает с вероятностью поступления требований за время Поскольку входящий поток — пуассоновский с параметром то

где функция распределения величины Отсюда

где преобразование Лапласа функции . Но функция распределения суммы независимых случайных величин функции распределения которых равны соответственно. Преобразование Лапласа для суммы равно произведению соответствующих преобразований. Следовательно,

или