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

Пусть рассматриваемая система  имеет  - возможных состояний . Вероятность -го состояния  - это вероятность того, что в момент времени , система будет находиться в состоянии . Очевидно, что для любого момента времени сумма всех вероятностей состояний равна единице:

.

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

Что будет происходить  с вероятностями состояний при ? Будут ли  стремиться к каким-либо пределам? Если эти пределы существуют и не зависят от начального состояния системы, то они называются финальными вероятностями состояний.

,

где  – конечное число состояний системы.

Финальные вероятности состояний – это уже не переменные величины (функции времени), а постоянные числа. Очевидно, что:

.

Финальная вероятность состояния  – это по–существу среднее относительное время пребывания системы в этом состоянии.

Например, система  имеет три состояния ,  и . Их финальные вероятности равны соответственно 0,2; 0,3 и 0,5. Это значит, что система в предельном стационарном состоянии в среднем 2/10 времени проводит в состоянии , 3/10 – в состоянии  и 5/10 – в состоянии .

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

Пользуясь этим правилом, напишем  систему уравнений для нашего примера:

.

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

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

Четвертое уравнение отбрасываем, добавляя вместо него нормировочное  условие:

.

; ; ; .

Т.е. в предельном, стационарном режиме система  в среднем 40% времени будет проводить в состоянии  (оба станка исправны), 20% - в состоянии  (первый станок ремонтируется, второй работает), 27% - в состоянии  (второй станок ремонтируется, первый работает), 13% - в состоянии  (оба станка ремонтируются). Знание этих финальных вероятностей может помочь оценить среднюю эффективность работы системы и загрузку ремонтных органов.

Пусть система  в состоянии  (полностью исправна) приносит в единицу времени доход 8 условных единиц, в состоянии  – доход 3 условные единицы, в состоянии  – доход 5 условных единиц, в состоянии  – не приносит дохода. Тогда в предельном, стационарном режиме средний доход в единицу времени будет равен:  условных единиц.

Станок 1 ремонтируется долю времени, равную: . Станок 2 ремонтируется долю времени, равную: . Возникает задача оптимизации. Пусть мы можем уменьшить среднее время ремонта первого или второго станка (или обоих), но это нам обойдется в определенную сумму. Спрашивается, окупит ли увеличение дохода, связанное с ускорением ремонта, повышенные расходы на ремонт? Нужно будет решить систему четырех уравнений с четырьмя неизвестными.

 

1.1.5 Задачи теории массового обслуживания

 

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

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

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

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

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

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

 

1.1.6 Классификация систем массового обслуживания

 

Первое деление (по наличию  очередей):

1. СМО с отказами;
2. СМО с очередью.

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

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

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

Итак, например, рассматриваются  следующие СМО:

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

Кроме этого СМО делятся  на открытые СМО и замкнутые СМО.

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

Классификация СМО далеко не ограничивается приведенными разновидностями, но этого достаточно.

 

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

 

1.2.1 Одноканальная СМО с ожиданием 

 

Рассмотрим простейшую СМО  с ожиданием — одноканальную  систему , в которую поступает поток заявок с интенсивностью ; интенсивность обслуживания  (т.е. в среднем непрерывно занятый канал будет выдавать  обслуженных заявок в единицу (времени). Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания [1].

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

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

• — канал свободен; 
• — канал занят, очереди нет; 
• — канал занят, одна заявка стоит в очереди; 
• — канал занят, k-1 заявок стоят в очереди; 
• — канал занят, т-заявок стоят в очереди.

ГСП показан на рис. 4. Все интенсивности потоков событий, переводящих в систему по стрелкам слева направо, равны , а справа налево — . Действительно, по стрелкам слева направо систему переводит поток заявок (как только придет заявка, система переходит в следующее состояние), справа же налево — поток «освобождений» занятого канала, имеющий интенсивность  (как только будет обслужена очередная заявка, канал либо освободится, либо уменьшится число заявок в очереди).

Рис. 4. Одноканальная СМО с ожиданием

Изображенная на рис. 4 схема  представляет собой схему размножения  и гибели. Напишем выражения для  предельных вероятностей состояний:

, (5)

или с использованием : 

(6)

Последняя строка в (6) содержит геометрическую прогрессию с первым членом 1 и знаменателем , откуда получаем:  

(7)

в связи с чем предельные вероятности принимают вид:

. (8)

Выражение (7) справедливо  только при  (при  она дает неопределенность вида ). Сумма геометрической прогрессии со знаменателем  равна , и в этом случае:

[6].

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

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

. (9)

Относительная пропускная способность:  

. (10)

Абсолютная пропускная способность:

.

Средняя длина очереди. Найдем среднее число  - заявок, находящихся в очереди, как математическое ожидание дискретной случайной величины – числа заявок, находящихся в очереди:

.

С вероятностью в очереди стоит одна заявка, с вероятностью – две заявки, вообще с вероятностью в очереди стоят заявок, и т.д., откуда: 

[2]. (11)

Поскольку , сумму в (11) можно трактовать как производную по  от суммы геометрической прогрессии:

.

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

 (12).

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

.

и среднее число заявок, связанных с СМО, равно:

(13).

Среднее время ожидания заявки в очереди. Обозначим его ; если заявка приходит в систему в какой-то момент времени, то с вероятностью  канал обслуживания не будет занят, и ей не придется стоять в очереди (время ожидания равно нулю). С вероятностью  она придет в систему во время обслуживания какой-то заявки, но перед ней не будет очереди, и заявка будет ждать начала своего обслуживания в течение времени  (среднее время обслуживания одной заявки). С вероятностью  в очереди перед рассматриваемой заявкой будет стоять еще одна, и время ожидания в среднем будет равно , и т.д [3].

Если же , т.е. когда вновь приходящая заявка застает канал обслуживания занятым и m-заявок в очереди (вероятность этого ), то в этом случае заявка не становится в очередь (и не обслуживается), поэтому время ожидания равно нулю. Среднее время ожидания будет равно:

_,

если подставить сюда выражения  для вероятностей (8), получим:

 (14).

Здесь использованы соотношения (11), (12) (производная геометрической прогрессии), а также  из (8). Сравнивая это выражение с (12), замечаем, что иначе говоря, среднее время ожидания равно среднему числу заявок в очереди, деленному на интенсивность потока заявок.