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

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

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

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

1. СМО  с  типом  дисциплины "первый  пришел  -  первый  обслуживается" - дисциплина "живой очереди";
2. СМО с типом дисциплины "последний пришел - первый обслуживается" - примером   такой   системы   является   склад,   заполненный   изделиями,   из которого на доработку удобно брать изделия, поступившие последними;
3. СМО с типом дисциплины выбора требований случайным способом;
4. СМО    с    типом    дисциплины    выбора    требований    в    соответствии   с присвоенными приоритетами.

Другими вариантами классификаций могут быть следующие.

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

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

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

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

 

1.1.2.1.Классификация входных потоков

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

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

_{Рис. 2. Классификация входного потока}

 

 

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

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

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

Входной поток  называется рекуррентным, если он характеризуется следующими свойствами:

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

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

1. продолжительность интервалов между поступлениями требований статистически независимы;
2.   продолжительность интервалов описывается одной и той же плотностью 
   распределения;
3. вероятность поступления требований на достаточно малом интервале Δt 
   зависит только лишь от величины Δt (это свойство называется стационарностью или однородностью прихода);
4. вероятность   поступления   требований   на   интервале Δt  не   зависит   от 
   предыстории процесса;
5. характер потока требований таков, что в любой момент времени может 
   поступить только одно требование.

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

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

(1.1)

где λ– интенсивность  поступления заявок в систему.

Если   интервалы   распределены   по   экспоненциальному   закону,   то процесс пуассоновский. Такие процессы называются М-процессами (Марковскими).

Кроме закона Пуассона часто применяется закон  распределения Эрланга.

(1.2)

 

1.1.2.2. Классификация процессов обслуживания.

 Обозначения Кендалла систем массового обслуживания.

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

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

 

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

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

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

Используются  следующие обозначения:

M - пуассоновское  или экспоненциальное распределение;

D - постоянная  величина;

E_k - распределение Эрланга;

G – общий вид распределения;

GI – рекуррентный входной поток.

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

где Н₁ – характеристика входного потока, H₂ – характеристика времени обслуживания прибора, i – число приборов.

Например, система M /D /s - система с s приборами, обслуживающая поступающие требования за строго определенный интервал времени, поступающие требования образуют пуассоновский поток [16].

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

по характеру обслуживания.

1.1.2.3.1. СМО с отказами.

Одноканальная СМО содержит один канал (n = 1), и на ее вход поступает пуассоновский поток заявок П_вх интенсивность (среднее число событий в единицу времени) которого inП_вх=λ. Так как интенсивность входящего потока может изменяться во времени, то вместо λ записывают λ(t). Тогда время обслуживания каналом одной заявки Т_об распределено по показательному закону и записывается в виде: , где λ — интенсивность отказов.

Состояние СМО характеризуется  простаиванием или занятостью ее канала, т. е. двумя состояниями: S₀ — канал свободен и простаивает, S₁ — канал занят. Переход системы из состояния S₀ в состояние S₁ осуществляется под воздействием входящего потока заявок П_вх, а из состояния S₁ в состояние S₀ систему переводит поток обслуживании П_об: если в данный момент времени система находится в некотором состоянии, то с наступлением первого после данного момента времени СМО переходит в другое состояние. Плотности вероятностей перехода из состояния S₀ в S₁ и обратно равны соответственно λ и µ. Граф состояний подобной СМО с двумя возможными состояниями приведен на рис. 3.

_{Рис. 3. Граф состояний одноканальной СМО с отказами.}

Для многоканальной СМО с отказами (n > 1) при тех же условиях состояния системы обозначим по числу занятых каналов (по числу заявок, находящихся в системе под обслуживанием, так как каждый канал в СМО либо свободен, либо обслуживает только одну заявку). Таким образом, подобная СМО может находиться в одном из следующих (n+1) состояний: s₀ — все n каналов свободны; s₁— занят только один из каналов, остальные (n—1) каналов свободны; s_i — заняты i - каналов, (n-i) каналов свободны; s_n —заняты все n каналов. Граф состояний такой СМО приведен на рис. 4.

_{Рис. 4. Граф состояний многоканальной СМО с отказами.}

При этом имеет  место  а

Пользуясь  общим  правилом  составления  дифференциальных уравнений Колмогорова, можно для приведенных на рис. 2 и рис. 3 графов состояний составить системы дифференциальных уравнений:

1. например, для одноканальной СМО (рис. 2) имеем:

2. для многоканальной СМО (рис. 3) соответственно имеем:

 

……………………………

……………………………

Решив первую систему  уравнений, можно найти значения p₀(t) и p₁(t) для одноканальной СМО и построить графики при трех случаях: 1) λ >µ; 2) λ=µ; 3) λ<µ (рис. 5 а, б, в). Можно также определить предельную пропускную способность СМО. Решение второй системы уравнений для многоканальной СМО в аналитическом виде получить вручную сложно, и его обычно получают с помощью ЭВМ в численном виде.

_{Рис. 5 а, б, в, г.}

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

Характеристика в момент времени t	Обозначения, формулы
Вероятность того, что  канал свободен
Вероятность того, что  поступившая заявка будет принята  к  обслуживанию
Вероятность  занятости  канала
Вероятность отказа заявки
Относительная  пропускная  способность СМО (средняя доля обслуженных  заявок среди поступивших)
Абсолютная пропускная способность СМО (среднее число  обслуженных заявок за единицу времени)
Интенсивность выходящего потока обслуженных заявок
Среднее время обслуживания заявок
Среднее время пребывания заявки в системе

^{Таблица 1. Характеристики одноканальной  СМО с отказами.}

Характеристика в момент времени t	Обозначения, формулы
Вероятность того, что  канал свободен
Вероятность того, что  поступившая заявка будет принята  к обслуживания
Вероятность занятности канала
Вероятность отказа заявке
Относительная пропускная способность СМО
Абсолютная пропускная способность СМО
Интенсивность выходящего потока Пвых обслуженных заявок
Среднее время обслуживания заявок
Среднее время пребывания заявки в системе

 

 

1.1.2.3.2. СМО с ожиданием.

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

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

^{Рис. 6. Граф состояний одноканальной СМО с ожиданием}

Состояния СМО имеют  следующую интерпретацию:

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

S₁ – канал занят (очереди нет);

S₂ – канал занят (одна заявка стоит в очереди);

……………………………………………………