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

Простейший поток обладает такими важными свойствами:

1. Свойством стационарности, которое выражает неизменность вероятностного режима потока по времени. Это значит, что число требований, поступающих в систему в равные промежутки времени, в среднем должно быть постоянным. Например, число вагонов, поступающих под погрузку в среднем в сутки должно быть одинаковым для различных периодов времени, к примеру, в начале и в конце декады.
2. Отсутствия последействия, которое обуславливает взаимную независимость поступления того или иного числа требований на обслуживание в непересекающиеся промежутки времени. Это значит, что число требований, поступающих в данный отрезок времени, не зависит от числа требований, обслуженных в предыдущем промежутке времени. Например, число автомобилей, прибывших за материалами в десятый день месяца, не зависит от числа автомобилей, обслуженных в четвертый или любой другой предыдущий день данного месяца.
3. Свойством ординарности, которое выражает практическую невозможность одновременного поступления двух или более требований (вероятность такого события неизмеримо мала по отношению к рассматриваемому промежутку времени, когда последний устремляют к нулю).[4]

При простейшем потоке требований распределение требований, поступающих  в систему, подчиняются закону распределения Пуассона: вероятность того, что в обслуживающую систему за время t поступит именно k требований:

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

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

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

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

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

Во-первых, важно учитывать  принцип, в соответствии с которым поступающие па вход обслуживающей системы требования  подключаются  из очереди  к  процедуре обслуживания.  Этот принцип   называют дисциплиной очереди. Наиболее широко распространенной и, по-видимому, наиболее справедливой дисциплиной очереди является дисциплина, определяемая правилом «первым пришел — первым обслуживаешься» (FIFO). Но на практике приходится сталкиваться и с другими вариантами дисциплины очереди, среди которых следует указать дисциплину очереди, осуществляемую по правилу «последним пришел — первым обслуживаешься» (LIFI), и дисциплину очереди, определяемую правилом случайного отбора заявок (СОЗ).

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

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

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

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

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

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

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

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

1. распределением моментов поступлений заявок на обслуживание (единичных или групповых);
2. распределением продолжительностей обслуживания (при индивидуальном или при групповом обслуживании);
3. конфигурацией обслуживающей системы (последовательное, параллельное или параллельно-последовательное обслуживание);
4. дисциплиной очереди (FIFO, LIFO, СОЗ) и приоритетными характеристиками обслуживающей системы;
5. вместимостью блока ожидания (ограниченная или неограниченная);
6. емкостью (или мощностью) источника требований (конечная или бесконечно большая);
7. бихевиоральными характеристиками системы (возможности клиентов переходить из одной очереди в другую, ненулевая вероятность отказов от ожидания либо сразу при поступлении в обслуживающую систему, либо после непродолжительной задержки в очереди).

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

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

• среднее время обслуживания;
• среднее время ожидания в очереди;
• среднее время пребывания в СМО;
• средняя длина очереди;
• среднее число заявок в СМО;
• количество каналов обслуживания;
• интенсивность входного потока заявок;
• интенсивность обслуживания;
• интенсивность нагрузки;
• коэффициент нагрузки;
• относительная пропускная способность;
• абсолютная пропускная способность;
• доля времени простоя СМО;
• доля обслуженных заявок;
• доля потерянных заявок;
• среднее число занятых каналов;
• среднее число свободных каналов;
• коэффициент загрузки каналов;
• среднее время простоя каналов.

Формулы для расчета  данных характеристик будут представленных ниже для конкретных типов СМО.

 

3. СХЕМЫ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ⁵

3.1. ОДНОКАНАЛЬНАЯ СМО С ОТКАЗАМИ

Рассмотрим простейший случай СМО. Пусть СМО состоит только из одного канала (n=1) и на нее поступает пуассоновский поток заявок с интенсивностью l, зависящей в общем случае от времени l=l(t) (9.1). Заявка, заставшая канал занятым, получает отказ и покидает систему.

Обслуживание заявки продолжается в течение случайного времени Т_об, распределенного по показательному закону с параметром  m:

f(t)= me^-mt (t>0).

Из этого следует, что «поток обслуживаний» – простейший, с интенсивностью m.

Рассмотрим единственный канал обслуживания как физическую систему S, которая может находиться в одном из двух состояний: S₀ – свободен, S₁ – занят. Обозначим вероятности состояний p₀(t) и p₁(t). Очевидно:

"t p₀(t)+p₁(t)=1

Граф состояний данной системы:

 

 

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

Для случая l=const:

1. Вероятности состояний:

 

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

q= p₀,  

(при t®¥)

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

,  (при t®¥)

4. Вероятность отказа:

P_отк =1-q; 

(при t®¥)

 

3.2. МНОГОКАНАЛЬНАЯ СМО С ОТКАЗАМИ

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

S₀ – все каналы свободны;

S₁ – занят ровно один канал, остальные свободны;

……

S_k – заняты ровно k каналов, остальные свободны;

…….

S_n – заняты все n каналов.

Граф состояний имеет следующий  вид.

Слева направо систему  переводит один и тот же поток – поток заявок с интенсивностью l. Очевидно,  если обслуживанием занято 2 канала, а не один, поток обслуживаний, переводящий систему по стрелке S₂®S₁,  будет вдвое интенсивнее (2m), если занято k- каналов – в k раз интенсивнее (km).

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

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

1. Вероятности состояний:

 (k=1,2,..n)

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

q = 1-p_n.

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

А= lq=l(1- p_n).

4. Вероятность отказа:

5. Среднее число занятых каналов

.

 

3.3. ОДНОКАНАЛЬНАЯ СМО С ОЖИДАНИЕМ

На СМО поступает  поток заявок с интенсивностью l, интенсивность обслуживания m (т.е. в среднем непрерывно занятый канал будет выдавать m обслуженных заявок в единицу времени), n=1. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что количество мест в очереди ограничено числом m (в дальнейшем, при m®¥ можно получить характеристики одноканальной СМО без ограничений по длине очереди). Будем нумеровать состояния СМО по числу заявок, находящихся в системе (как обслуживаемых, так и ожидающих обслуживания):