Глава IX. Модели массового обслуживания Системы массового обслуживания и их классификация. Марковский случайный процесс. Уравнения Колмогорова

Среди оргсистем часто встречаются системы массового обслуживания (СМО). Примерами таких систем в человеческой деятельности служат предприятия бытового обслуживания, общественного питания, поликлиники, телефонные станции и др. В явлениях природы примером СМО являются биологические популяции.

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

Заявки на обслуживание поступают в СМО не регулярно, а случайно, образуя так называемый случайный поток заявок (требований).

Обслуживание заявок также продолжается какое-то случайное время. Случайный характер потока заявок и времени их обслуживания приводит к неравномерной загруженности СМО. В какие-то периоды времени накапливаются заявки, которые либо становятся в очередь, либо покидают СМО необслуженными. В другие же периоды времени СМО работает с недогрузкой или простаивает.

Схематически СМО изображена на рис. 22.1.

Рис. 22.1

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

К показателям эффективности относятся: среднее число заявок, обслуживаемых в единицу времени; среднее число заявок в очереди; среднее время ожидания обслуживания; вероятность отказа в обслуживании и др.

СМО делят на два класса: СМО с отказами и СМО с ожиданием (очередью).

В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ и покидает СМО необслуженной.

В СМО с ожиданием заявка, поступившая в момент, когда все каналы заняты, не покидает СМО, а становится в очередь на обслуживание.

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

Различают следующие виды дисциплины обслуживания:

• первой пришла – первой обслужена;

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

• ограничено время пребывания в очереди;

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

Процесс работы СМО представляет собой случайный (стохастический) процесс с дискретными состояниями и непрерывным временем. Это означает, что состояние СМО меняется скачком в случайные моменты появления каких-то событий. Например, прихода новой заявки, окончания обслуживания и т. п.

Построение математических моделей СМО значительно облегчается, если процесс работы СМО – марковский.

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

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

Для математического описания марковского процесса введем следующие понятия.

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

Интенсивностью потока событий  называется среднее число событий, поступающих в СМО в единицу времени.

Стационарным потоком событий является поток, вероятностные характеристики которого не зависят от времени. В частности, интенсивность стационарного потока – величина постоянная.

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

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

Простейшим потоком событий называется поток, являющийся стационарным, ординарным и не имеющий последствия.

Известно, что для простейшего потока число m событий, попадающих на произвольный интервал времени , распределено по закону Пуассона

, (22.1)

где – вероятность того, что на интервал времени  попадает ровно m событий;  – интенсивность потока.

В частности, вероятность того, что за время  не произойдет ни одного события , равна

. (22.2)

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

.

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

Вероятность попадания на элементарный временной интервал хотя бы одного события потока находят из соотношения

, (22.3)

где функцию заменили двумя первыми членами ее разложения в ряд Маклорена по степеням .

Уравнения Колмогорова

Займемся нахождением вероятности состояний СМО. Для простоты и наглядности изложения ограничимся случаем марковского процесса из следующего примера.

Пример 22.1. Устройство S состоит из двух узлов, каждый из которых в случайный момент времени может выйти из строя, после чего мгновенно начинается ремонт узла, продолжающийся заранее неизвестное случайное время. Определить вероятности всех возможных состояний системы.

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

На рис. 22.2 изображен граф состояний устройства S.

Рис. 22.2

Здесь отмечены следующие возможные состояния системы: – оба узла исправны; – первый узел ремонтируется, второй исправен; – второй узел ремонтируется, первый исправен; – оба узла ремонтируются.

Стрелка, направленная из в , означает переход системы в момент отказа первого узла. Стрелка из в – переход в момент окончания ремонта первого узла. Аналогичный смысл остальных стрелок графа состояний.

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

Полагают, что все переходы системы из состояния в происходят под воздействием простейших потоков событий с интенсивностями , .

Граф состояний системы с проставленными у стрелок интенсивностями называют размеченными (см. рис. 22.2).

Вероятностью i-го состояния называется вероятность того, что в момент t система будет находиться в состоянии . Для любого момента t выполняется соотношение

. (22.4)

Рассмотрим систему в момент t.

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

Возможны два случая, когда система будет находиться в состоянии :

• либо система в момент t с вероятностью находилась в состоянии и за время не вышла из него;

• либо система в момент t с вероятностью находилась в состоянии или с вероятностью – в состоянии и за время перешла в состояние .

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

.

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

.

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

.

Откуда

.

Переходя к пределу при , получим (опустив переменную t):

. (22.5)

Соотношение (22.5) представляет собой дифференциальное уравнение первого порядка относительно функции .

Повторив рассуждения для других состояний системы, получим систему дифференциальных уравнений Колмогорова для вероятностей состояний:

(22.6)

Нетрудно видеть, система уравнений (22.6) составляется по следующему алгоритму:

1. В левую часть каждого уравнения ставится производная вероятности i-го состояния по времени.

2. В правую часть каждого уравнения ставится:

а) сумма произведений вероятностей всех состояний, из которых идут стрелки в i-е состояние, на интенсивность соответствующих потоков событий;

б) минус суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-го события.

В системе (22.6) независимых уравнений на единицу меньше их общего числа. Поэтому для решения системы добавляют уравнение (22.4).

Задав начальные условия (в данном примере вероятности состояний системы в начальный момент ) и решив систему дифференциальных уравнений Колмогорова, находят систему функций времени . Тем самым получают дискретное распределение вероятностей СМО для любого момента времени.

Предельные (финальные) вероятности состояний

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

Предельная вероятность состояния показывает среднее относительное время пребывания системы в этом состоянии.

Так как предельные вероятности постоянные, то их производные обращаются в нуль и уравнения Колмогорова (22.6) можно записать в виде:

(22.7)

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

Система уравнений (22.7) для предельных вероятностей по размеченному графу составляется по следующему алгоритму:

1. В левую часть каждого уравнения ставится суммарная интенсивность всех потоков, выводящих систему из данного состояния, умноженная на вероятность i-го состояния.

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

Пример 22.2. Найти предельные вероятности для системы из примера 22.1 при , , , , , , , .

Решение. Подставим заданные значения интенсивностей в систему уравнений (22.7):

Последнее уравнение системы представляет собой сумму предыдущих уравнений. Поэтому, заменив его уравнением (22.4), получим систему уравнений, описывающих стационарный режим для системы S:

Решив ее, найдем ; ; ; .

Таким образом, в стационарном режиме устройство S в среднем 34 % времени будет находиться в состоянии (оба узла исправны), 23 % – в состоянии (первый узел ремонтируется, второй работает), 26 % – в состоянии (второй узел ремонтируется, первый работает) и 17 % – в состоянии (оба узла ремонтируются).