Простейшие модели систем обслуживания с ожиданием

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

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

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

если в момент освобождения узла имеется хотя бы одно требование в накопителе, то первое из них по очереди поступает на обслуживание;

каждый узел в любой момент времени обслуживает не более одного требования;

каждое требование обслуживается одним узлом;

обслуживание не прерывается;

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

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

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

Рис.5.5.1. Схема открытой СМО с ожиданием.

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

Рис.5.5.2. Схема замкнутой СМО.

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

Открытые СМО с ожиданием.

Простейшей СМО с ожиданием является модель, в которой к условиям (1)-(7) добавляются следующие:

(8) по окончании обслуживания требование покидает систему;

(9) входящий поток является простейшим.

Для вероятности того, что время обслуживания будет больше некоторого , из (7) вытекает следующее соотношение:

, (5.5.1)

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

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

Для этого требуется ввести понятие состояния, показать, что процесс перехода из состояния в состояние является марковским, и доказать, что вероятности переходов удовлетворяют соотношениям (5.2.10), (5.2.11), (5.2.12).

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

Докажем, что процесс перехода из состояния в состояние является марковским. При этом примем во внимание, что изменение состояния имеет две причины: 1) поступление новых требований из входящего потока и 2) уход обслуженных требований их системы.

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

Найдем вероятности переходов. Переход за время связан с поступлением одного требования в систему (вероятность этого есть ) и тем, что ни один из занятых узлов за время обслуживания не окончил (вероятность этого согласно (5.5.1) есть , где – число занятых узлов). Число занятых узлов равно при и равно при . Соответственно, для имеем

.

Учитывая известное разложение функции , имеем

Тогда

. (5.5.2)

Аналогично, при

. (5.5.3)

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

. (5.5.4)

Аналогично, при

. (5.5.5)

Переход при имеет вероятность

. (5.5.6)

при

. (5.5.7)

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

(5.5.8)

Используя (5.5.8), получим выражения для финальных вероятностей состояний. При

. (5.5.9)

При

. (5.5.10)

Введем обозначение

. (5.5.11)

Тогда

(5.5.12)

Наконец,

.

Здесь

,

где

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

. (5.5.13)

При ряд расходится и, соответственно, и т.д., число требований в системе стремится к бесконечности.

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

Вероятность наличия очереди

. (5.5.14)

Вероятность того, что все узлы заняты

. (5.5.15)

Среднее число требований в системе

(5.5.16)

Средняя длина очереди

. (5.5.17)

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

(5.5.18)

При .

Среднее число свободных узлов

. (5.5.20)

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

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

Среднее время ожидания начала обслуживания определяется соотношением

. (5.5.21)

Общее время, которое проводят в очереди требования, поступившие в единицу времени, определится соотношением

. (5.5.22)

Легко видеть, что правая часть соотношения (5.5.22) совпадает с правой частью соотношения (5.5.17), т.е. , откуда среднее время ожидания начала обслуживания можно находить в виде

Среднее время, которое требование находится в системе обслуживания, складывается из времени ожидания и времени обслуживания.

. (5.5.23)

Суммарное время, которое в среднем находятся в системе требования, поступившие в единицу времени,

. (5.5.24)

Замкнутые СМО.

Простейшей замкнутой СМО, схема которой приведена ранее на рис. 5.5.2, является модель, в которой к условиям (1)-(7) добавляются следующие:

(10) обслуженные требования после некоторой задержки снова поступают на обслуживание;

(11) время задержки является случайной величиной, распределенной по экспоненциальному закону.

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

.

(Считаем, что , противоположный случай анализируется аналогично но не представляет интереса).

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

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

.

При

.

Переход соответствует окончанию обслуживания одного требования. Для

.

При

.

Остальные переходы являются бесконечно малыми.

Таким образом, имеем процесс «гибели и рождения» с

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

, (5.5.25)

при

. (5.5.26)

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

. (5.5.27)

В силу соотношений (5.5.25), (5.5.26) и того, что суммы в соотношении (5.5.27) являются конечными, существуют и не равны нулю финальные вероятности состояний системы. Вероятности состояний позволяют определить характеристики функционирования СМО (аналогично (5.5.14)-(5.5.24)).