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

Для классификации систем используется следующее обозначение

(a/b/c):(d/e/f),

где символы a,b,c,d,e,f, связаны с существенными элементами модельного представления процессов массового обслуживания.

a- распределение моментов поступления заявок на обслуживание,

b- распределение времени обслуживания (или выбытий обслуженных клиентов),

c- число параллельных узлов обслуживания,

d- дисциплина очереди (ПЕРППО, ПОСППО, СОЗ),

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

f- емкость источника, генерирующего заявки на обслуживание.

Для а и b приняты следующие обозначения:

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

D- фиксированный (детерминированный) интервал времени  между моментами последовательных поступлений в систему заявок на обслуживание или детерминированная (фиксированная) продолжительность обслуживания.

E_k- распределение Эрланга или гамма - распределение интервалов времени между моментами последовательных поступлений требований в ОС или продолжительностей обслуживания  ( при этом k- параметр распределения),

G- распределение произвольного вида моментов поступления в систему заявок на обслуживание  (или интервалов времени между последовательными поступлениями требований),

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

Пример обозначения (M/D/10):(GD/N/¥) -система массового обслуживания с пуассоновским входным потоком, фиксированным временем обслуживания и 10 параллельными узлами, дисциплина очереди не регламентирована, независимо от числа поступающих требований  данная система (очередь + обслуживаемые клиенты) не может вместить более N требований, т.е. остальные не принимаются, источник ¥ емкости. Это обозначение по Кендаллу - Ли.

Цель нашего анализа - разработка критериев эффективности СМО. Среди режимов работы СМО явно выделяют переходные и стационарные режимы. К переходным относятся процессы чистого рождения и чистой гибели, которые с течением времени переходят в стационарные. Если l - интенсивность поступлений > m (интенсивности выходного потока) , то стационарный режим не достижим. Анализ нестационарных режимов сложен, поэтому далее будут рассматриваться только стационарные процессы.  

Стационарный ординарный поток без последействия называется простейшим. Математическое описание простейшего потока задается системой функций p₀(t),p₁(t),...p_n(t).

Определим их вид.

 Основное свойство стационарного потока:

 Теорема 1:

Для любого стационарного потока существует предел

lim w(t)/t=l>0 при tà0,

где w(t)=1-p₀(t).Величина l может быть неограниченно большой. Эту величину называют параметром потока. Функция w(t) является вероятностью того, что за промежуток времени t поступит в систему обслуживания хотя бы одно требование. Действительно, так как

å_k=0^¥ p_k(t)=1,

то 1-p₀(t)=å_k=1^¥ p_k(t), значит w(t)=1-p₀(t)=å_k=1^¥p_k(t)

есть вероятность поступления хотя бы одного требования за промежуток времени t. Для доказательства используется лемма 1: Если f(x)>=0 есть функция, не убывающая на отрезке 0<x<=a и f(x+y)<=f(x)+f(y) при x,y Î(0,a], то отношение f(x)/x при xà0 стремится к пределу, который либо является конечным числом, либо неограниченно возрастает, и равен нулю только в том случае, когда f(x)=0. Функция w(t) удовлетворяет условиям леммы. Определим вид функции p_k(t) при k=0,1,... Для этого рассмотрим промежуток (0,t+Dt). Какова вероятность того, что за время (0,t+Dt) поступит ровно k требований. Разобъем его на два промежутка (0,t) и (t,t+Dt), тогда точно k требований могут поступить одним из не совместимых способов

Из таблицы видно, что поступление точно k требований за промежуток времени (0,t+Dt) исчерпывается (k+1) случаями. Так как  поток простейший, то отсутствие последействия позволяет вычислить вероятность каждого из этих случаев появления ровно k требований, используя теорему умножения вероятностей. Действительно, вероятность того, что за промежуток времени (0,t) появится k требований, а за (t,t+Dt) появится 0 требований равно p_k(t)*p₀(Dt). Для  случая (k-1) в промежутке (0,t) и 1 за промежуток (t,t+Dt) вероятность равна p_k-1(t)*p₁(Dt) и т.д. Заметим, что все эти случаи попарно несовместимы, а поэтому вероятность появления ровно k требований за промежуток (0,t+Dt) равна сумме вероятностей появления  k требований за указанный промежуток в каждом отдельном случае. Используя теорему сложения вероятностей, получим

p_k(t+Dt)=å_i=0^k p_i(t)*p_k-i(Dt),

где p_k(t+Dt)- вероятность появления k требований за время (0,t+Dt). Распишем правую часть уравнения

å_i=0^k p_i(t)*p_k-i(Dt)=p₀(t)*p_k(Dt)+p₁(t)*p_k(Dt)+...+p_k-2(t)*p_k(Dt)+p_k-1(t)*p₁(Dt)+p_k(t)*p₀(Dt)

Очевидно, что все слагаемые справа, кроме двух последних, являются величинами более высокого порядка чем Dt. Далее, поскольку 0<=p_k(t)<=1  справедливо

å_i=0^k-2p_k(t)*p_k-i(Dt)<=å_i=0^k-2p_k-i(Dt)=å_i=2^kp_i(Dt)

Если продолжить суммирование в сумме å_i=2^kp_i(Dt) неограниченно, то получим

å_i=0^k-2p_k(t)*p_k-i(Dt)<=å_i=2^kp_i(Dt)<=å_i=2p_i(Dt).

Так как за время Dt может не поступить ни одного требования или поступить одно или более требований, то эти события являются взаимоисключающими. Поэтому å_i=0^¥p_i(Dt)=1 . Перенесем два первых слагаемых вправо å_i=2^¥p_i(Dt)=1-[p₀(Dt)+p₁(Dt). Сумма p₀(Dt)+p₁(Dt) есть вероятность того, что за промежуток времени Dt  поступит не более одного требования (т.е. ничего или одно), а вся правая часть есть вероятность поступления двух и более требований, т.о. сумма справа есть вероятность поступления не менее двух требований за Dt . Для свойства ординарности эту вероятность мы обозначим Y(Dt)=O(Dt). Следовательно, å_i=2^¥p_i(Dt)=Y(Dt)=O(Dt) при tà0. Подставив значения в (7) получим

å_i=2^¥p_i(t)*p_k-i(Dt)<=Y(t), следовательно å_i=0^k-2p_i(t)*p_k-i(Dt)=O(Dt) при Dtà0.Т.Е. сумма справа в (3) без двух первых членов есть бесконечно малая величина. Преобразуем правую часть (5) следующим образом

p_k(t+Dt)=p_k(t)*p₀(Dt)+p_k-1(t)*p₁(Dt)+O(Dt) (11). Используем (11) для нахождения p0(Dt) и p1(Dt). Из теоремы 1 имеем w(Dt)=lDt+O(Dt).Но значение w(Dt) мы определили как вероятность того, что за время Dt поступит хотя бы одно требование , т.е. w(Dt)=1-p₀(Dt) (13). Подставляя (13) в (12) получаем

lDt+O(Dt)=1-p₀(Dt), откуда p₀(Dt)=1-lDt+O(Dt). Для вычисления p₁(Dt)  воспользуемся тем, что вероятность поступления хотя бы одного требования за Dt равна сумме вероятностей поступления одного, двух, трех и т.д. требований ,т.е.

w(Dt)=p₁(Dt)+p₂(Dt)+... = p₁(Dt)+O(Dt), откуда p₁(Dt)=w(Dt) из (12) имеем

p₁(Dt)=lDt+O(Dt). Теперь выражение p₀(t) из (14) и p₁(Dt)  из (16) подставляем в (11)

p_k(t+Dt)=p_k(t)-lDtp_k(t)*D+lp_k-1(t)*Dt+p_k(t)O(Dt)+p_k-1(t)O(Dt).

Так как p_k(t)<=1 и p_k-1(t)<=1, то p_k(t+Dt)=p_k(t)-lp_k(t)Dt+lp_k-1(t)Dt+O(Dt) (17)

Преобразуем (17), перенеся pk(t) влево и поделив на Dt

(p_k(t+Dt)-p_k(t))/Dt=-lp_k(t)+lp_k-1(t)+O(Dt)/Dt, переходя к пределу , получим слева dp_k(t)/dt  и

dp_k(t)/dt=-lp_k(t)+lp_k-1(t) при k=1,2,3,...(19). Это рекурсивная система линейных однородных дифференциальных уравнений для определения p_k(t). Для ее решения нужно знать p₀(t). Из (11) следует p₀(t+Dt)=p₀(t)*p₀(Dt) (20). Подставим в (20) вместо p₀(Dt) его выражение из (14)

p₀(t+Dt)=p₀(t)*[1-lD+O(Dt)], откуда  p₀(t+Dt)-p₀(t)=-lp₀(t)D+p₀(t)*O(Dt). Поделив на Dt и переходя к пределу , получим dp₀(t)/dt=-lp₀(t). Запишем его как dp₀(t)/p₀(t)=-ldt, откуда интегрируя, получим

òdp₀(t)/p₀(t)=-lòdt или lnp₀(t)=-lt+lnC. Потенцируя, получаем p₀(t)=Ce^-lt (22). Определим постоянную С.

Имеем p₀(0)=1,т.е. вероятность того, что за промежуток времени равный нулю не поступит ни одной заявки равна 1. Подставив p₀(0) в (22) получим p₀(0)=C^e-l0=C=1, следовательно, p₀(t)=e^-lt (23). Для вычисления  p_k(t) из (19) воспользуемся подстановкой p_k(t)=e^-ltu_k(t) для k=0,1,2...(24)

При p₀(t)=e^-lt  получаем из (24) u₀(t)=1. Задача теперь состоит в отыскании функции u_k(t).Подставив в (19) значения p_k(t) и p_k-1(t) из (24) и приведя подобные, получаем du_k(t)/dt=lu_k-1(t) k=1,2,...(25)

Из (16) вытекает p₁(0)=0 (26).Следовательно, p₀(0)=1,p₁(0)=0 и å_k=0^¥p_k(t)=1. Откуда å_k=2^¥p_k(0)=0 (27)

Но величина p_k(t)>=0. Их сумма равна 0, если они все равны нулю, т.е. p_k(0)=u_k(0)=0 (28). Подставив u_k(0) и u₀(t)=1  в (25) , получаем du₁(t)/dt=l или после интегрирования u₁(t)=lt+C₁. Но так как u₁(0)=C₁=0, то u₁(t)=lt. Теперь подставив u₁(t)=lt в (25), получим du₂(t)/dt=l²t, откуда u₂(t)=l²t²/2+C₂, но так как u₂(0)=0=C₂, то u₂(t)=l²t²/2. Аналогично получаем u₃(t)=(lt)³/3! и т.д. u_k(t)=(lt)^k/k! (29)

Следовательно, p_k(t)=(lt)^k/k!*e^-lt (30). Выражение (30) означает, что число требований в промежутке времени t при простейшем потоке распределено по закону Пуассона с параметром Dt, т.о. p_k(t)-вероятность поступления ровно k требований за время (0,t) зависит только от параметра l. Легко показать, что l равно математическому ожиданию числа требований, поступивших в систему за единицу времени . Действительно, M_t(k)=å_k=1^¥kp_k(t)=å_k=1^¥k(lt)^k/k!e^-lt=e^-ltltå_k=1^¥(lt)^k-1/(k-1)!

Последняя сумма является разложением в ряд функции e^lt  по степеням lt, поэтому

M_t[k]=lte^-lte^lt=lt (31). При t=1 получаем M₁[k]=l (32)

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

Важной характеристикой функционирования отдельного аппарата обслуживающей системы является время обслуживания. Оно характеризует пропускную способность одного аппарата, показывая скольок времени необходимо ему для обслуживания одного требования. При нашем анализе мы считаем, что если обслуживание требования закончилось, то заявка на обслуживание удовлетворена, не зависимо от качества обслуживания. Время обслуживания является случайной величиной, так как зависит от поступающих требований, которые не одинаковы, и от возможностей аппарата. Если g - время обслуживания, а F(t) вероятность того, что g будет меньше заданного значения t, то полной характеристикой времени обслуживания будет закон распределения F(t)=P{g<е} (t>=0), так как время обслуживания величина неотрицательная, то F(t)=0 при t<=0.Т.е. F(t) должна быть положительной монотонно-возрастающей функцией, не превосходящей 1.  Указать конкретный вид функции F(t) заранее без изучения функционирования аппарата нельзя. Но в теории и на практике чаще всего пользуются показательным законом распределения времени обслуживания, где F(t) имеет вид

F(t)=1-e^-bt.

Здесь b есть обратная величина от среднего времени обслуживания (математическое ожидание обслуживания), т.е. 1/b есть математическое ожидание времени обслуживания. Действительно, дифференцируя F(t) , получаем плотность распределения F’(t)=be^-bt . А, следовательно, среднее время обслуживания (математическое ожидание) будет

M[g]=ò₀^¥tbe^-btdt=1/bò₀^¥ue^-udu=1/b.(33)

При вычислении интеграла использована подстановка bt=u. Из (33) видно, что чем больше b , тем меньше среднее время обслуживания. Т.е. при показательном законе распределения времени обслуживания вероятность обслуживания достаточно велика вскоре после его начала. Закон распределения оставшейся части времени обслуживания не зависит от того, сколько времени обслуживание  уже длится. Это свойство является признаком так называемого марковского процесса. Случайные процессы, для которых при фиксированном настоящем будущее не зависит от прошлого (в ТМО это понимается в смысле вероятностей появления новых требований или отказа в обслуживании последнего) называются марковскими процессами.