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

Напомним, что под дисциплиной очереди понимаются три возможные принципа, заложенные в порядок обслуживания очереди: 
— «первым пришел — первым обслужен (собственно очёредь);

— «последним пришел — первым обслужен (стек);

— случайный выбор заявок из очереди;

— выбор заявок из очереди в соответствии с некоторым приорите-том.

Целью анализа систем и процессов массового обслуживания является разработка критериев эффективности функционирования систем массового обслуживания. Поскольку процесс массового обслуживания .Протекает во времени, постольку он может быть неустановившимся (переходным) или стационарным. Неустановившийся процесс — это процесс, при котором пове-дение системы продолжает оставаться функцией времени. Процессы чистого рождения и чистой гибели всегда относятся к категории неустановившихся стохастических процессов. В системах массового обслуживания, в которых происходит, с одной стороны, поступление заявок на обслуживание, а с дру¬гой — обслуженные клиенты выбывают из системы, в начальный период функционирования всегда наблюдается неустановившийся режим, а по исте-чении достаточно большого периода времени устанавливается стационарный режим. Однако, если интенсивность (l) поступления требований на обслу-живание превышает интенсивность выходного потока (m), то стационарный режим оказывается недостигаемым, то есть очередь со временем будет по-стоянно увеличиваться.

 

 

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

 

 

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

pn — вероятность того, что в системе находятся n клиентов (заявок на об-служивание);

Ls — среднее число находящихся в системе клиентов (заявок на обслужи-вание);

Lq — среднее число клиентов в очереди на обслуживание;

Ws — средняя продолжительность пребывания клиента (заявки на обслу-живание) в системе;

Wq — средняя продолжительность пребывания клиента (заявки на обслу-живание) в очереди.

По определению 
Ls=Sn*pn, Lq=S(n-c)*pn.

Между Ls и Ws (между Lq и Wq) существует строгая зависимость. В част-ности, если частота поступлений заявок в систему равняется l, то мы имеем 
Ls= l*Ws,Lq=l*Wq 
В случае, когда не все заявки имеют возможность попасть в обслужи-вающую систему (из-за небольшой вместимости блока ожидания), приведен¬ные соотношения надо видоизменить путем введения нового значения пара¬метра lэфф, которое позволило бы учесть только действительно попавшие в систему требования. Определим это значение следующим образом

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

Ls=lэфф*Ws, Lq=lэфф*Wq. 
В общем случае 
lэфф=b*l,0<b<1.

Это означает, что только часть поступающих требований на обслужива¬ние действительно попадают в систему. 
Если средняя скорость обслуживания равняется m в час, следовательно, средняя продолжительность обслуживания равняется 1/m и тогда справедли¬во соотношение. 
Ws=Wq+ 1/m.

Умножая левую и правую части этого неравенства на l, получаем 
Ls = Lq +l / m. 
Последнее равенство остается справедливым и в случае замены l на lэфф. При этом будет 
Ls=Lq+ lэфф/m,или lэфф=m(Ls-Lq).

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

pn®Ls=Sn*pn®Ws=Ls/l®Wq=Ws-1/m®Lq=l*Wq

 

 

3.3. Модель (M/ M/ 1): (GD/¥/¥).

 

 

В этой модели имеется единственный узел обслуживания, а на вмести¬мость блока ожидания и емкость источника требований никаких ограничений не накладывается. Входной и выходной потоки являются пуассоновскими с параметрами l и m соответственно. 
Сначала выведем уравнения для Pn(t) — вероятностей того, что в интервале времени t в системе находится n требований (клиентов). Выберем достаточно малое значение h>0. Тогда вероятность Pn(t+h) (вероятность поступления в 
систему n>О требований в интервале (t+ h) складывается из следующих веро-ятностей:

1. В конце временного  интервала t в системе находится n тре-бований, а в интервале h не происходит ни поступлений, ни выбы-вании.

2. В конце временного  интервала t в системе находится (n-1) требований, а в интервале h происходит одно поступление, но не происходит ни одного выбывания.

3. В конце временного  интервала t в системе находится (n+1) требований, а в интервале h не происходит ни одного поступления, но происходит одно выбывание.

Кроме того, будем предполагать, что события происходят случайным об-разом и в интервале h происходит не более одного события (поступление требования или выбытие обслуженного клиента). Тогда имеют место при-ближенные равенства

Рn(t+h) =Рn(t)*(1-(l*h))(1-(m*h)) + Рn-1(t)(l*h)( 1-(m*h)) +Pn-1(t)*(1-(l*h))(m*h),n>0.

В последнем равенстве мы воспользовались тем, что при малых h>0 име¬ют место следующие представления вероятностей: 
(1-l*h ) — вероятность того, что в интервале h нет ни одного поступле¬ния; 
(1-m*h) ¾ вероятность того, что в интервале h нет ни одного выбыва¬ния;

(l*h) — вероятность того, что в интервале h только одно поступление; 
(m*h) — вероятность того, что в интервале h только одно выбывание. для n=0 вероятность того, что в интервале h не произойдет ни одного вы¬бывания, очевидно, равна единице. 
Следовательно, Р0(t+h)=Р0(t)*(1-(l*h) ) + Р1(t)*( m*h)( 1-(l*h)) группировав соответствующим образом члены написанных приближен¬ных равенств, разделив их на h и перейдя к пределу при h®0, получим сле¬дующие дифференциально-разностные уравнения

P¢n = l*Pn-1(t) +m*Рn+1(t) - (l+m)*Рn(t), n>0,

Po¢(t) = -l*Р0(t) +m*Р1(t), n=0.

В принципе написанная система разностно-дифференциальных уравнений разрешима, и поэтому она задает некоторый стохастический процесс (Pn(t)), который не обязательно стационарен. Однако, решения этой системы, выпи-санные в явном виде, весьма громоздки. 
Можно доказать, что при l<m существует стационарный процесс, то есть при t®¥ существует решение полученной системы разностно¬-дифференциальных уравнений, не зависящее от t. В этом случае, очевидно, будут иметь место предельные переходы

Pn'(t)®0, Pn(t) ® pn ,t®¥). 
Осуществив предельный переход при t ®¥ в системе разностно¬-дифференциальных уравнений, приходим к равенствам 
-l*p0+m*p1=0,n=0, 
l*pn-1+m*pn+1-(l+m)*pn=0,n>0.

В математике полученные уравнения называются разностными. для раз-ностных уравнений с постоянными коэффициентами полностью разработана теория и известны способы представления их решений. Для нашего разност-ного уравнения решения таковы Pn=(1-r)*rn,n=0,1,2,.., где через r обозначена величина r=l/m<1. Чтобы убедиться в справедливо¬сти представления решения, достаточно подставит его в разностное уравне¬ние. 
Полученное распределение вероятностей pn=(1-r)*rn в теории вероят¬ностей называется геометрическим распределением. 
Выражение для Ls получается путем элементарных преобразований: 
Ls=Sn*pn=Sn*(1-r)*rn=(1-r)*r*d/d*r(1/(1-r))=r/(1-r). 
Заметим, что ряд Srn сходится как сумма бесконечной убывающей геометрической прогрессии со знаменателем r<1 . 
Используя выведенные ранее формулы, получаем Ls=М= r*(1-r), Lq =Ls-l/m=r2/(1-r),

Ws=Ls/l=1/[m(1-l)], Wq=r/[m(1-r)].

 

 

3.4. Модель (М/ М/ 1): (GD/N/¥)

 

 

Разница между моделью (М/М/1):(GD/N/¥) и уже рассмотренной мо¬делью (М/М/1):(GD/¥/¥) заключается в том, что максимальное число требований, допускаемых в блок ожидания, равняется N (то есть максимальна длина очереди есть N-1). В результате эффективная частота lэфф поступ¬лений требований становится меньше частоты l с которой заявки на обслу¬живание генерируются соответствующим источником. 
Разностно-дифференциальные уравнения для n=0 и для 0N имеем Рn(t) =0, а для n = N можно написать

PN(t + h)=PN(t)*1*(1-m*h) +PN-1(t)*(l*h)*(1-(m*h)).

Таким образом, для установившегося процесса в модели (М/М/1):(GD/¥/¥) разностные уравнения имеют вид

-r*p0+p1=0,-pn+r*pN-1=0, 
-(1+r)*pn+pn+1+r*pn-1=0,0<n<n. 
Решение этого разностного уравнения имёет вид:

Следует отметить, что значение параметра r=l/m не обязательно меньше единицы, как это требовалось в модели (М/ М/ 1): (GD/¥/¥). Это следует из того, что число допускаемых в систему требований контролируется путем введения ограничения на длину очереди (которая не может превышать N-1),

а не соотношением между интенсивностями входного и выходного потоков есть не отношением l/m. 
С учетом формул для pn находим

Выражения для Lq, Ws, Wq можно получить из формулы для Ls если предварительно вывести формулу lэфф. Поскольку вероятность того, что требование не имеет возможности присоединиться к очереди, равна рn(то есть вероятность того, что в системе уже находится N требований) доля тре¬бований, которым разрешено войти в блок ожидания, равняется

P{n<n}= 1-Рn.<br="">Отсюда следует, что

lэфф=l*(1-pN), 
Wq=Lq/lэфф =Lq/[l*(1 —pN)], 
Ls= Lq + lэфф /m = Lq +l*(1-pN)/m, 
Ws=Wq+ 1/m =Ls/[l*(1-pN)].

Таким образом, еще раз убедились, что

lэфф = m*(Ls-Lq) = l*(1-pN).

 

 

Литература:

1. В.А.Онегов «Исследование операций». 
2. Х.Хата «Введение в исследование операций» (том 2). 
3. Е.С.Вентцель «Теория вероятностей».