Параметры и характеристики систем массового обслуживания

Приведенные трех или четырех буквенные  обозначения называют обозначениями Кендалла. В этих обозначениях А и В могут принимать значения из следующего набора символов {M, D, E_k, H_k, G, U}. При этом:

а) А или В=M, если распределение интервалов поступления или длительностей обслуживания заявок является экспоненциальным (М – от слова Markovian – Марковский);

б) А или В=D, если интервалы поступления или длительности обслуживания являются детерминированными (D – Determinate);

в) А или В=E_k, если соответствующие распределения являются Эрланговскими порядка k (E – Erlang);

г) А или В=H_k, в случае гиперэкспоненциальных распределений порядка k (H – Hyperexponential);

д) А или В= G, в случае распределений общего (произвольного) вида (G – General – общий, общего вида);

е) А или В= U – при равномерных распределениях соответствующих случайных величин (U – Uniform distribution – равномерное распределение).

Так, например, обозначение вида:

М/М/1 означает СМО с простейшим потоком на входе и экспоненциально распределенной длительностью обслуживания заявок в приборе (один)

D/Е₂/3/5 – СМО с регулярным потоком на входе, длительностью обслуживания, распределенной по закону Эрланга 2-го порядка, тремя обслуживающими приборами и пятью местами ожидания;

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

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

2. Характеристики функционирования  СМО

 

          2.1. Характеристики одноканальной СМО с однородной нагрузкой.

Предположим, что задана ОК СМО общего вида (типа G/G/1), для которой определены параметры нагрузки, а, именно, интенсивность l и КВ n_а интервалов поступления, интенсивность обслуживания m и КВ n длительности обслуживания:

Основными характеристиками, определяющими  качество функционирования такой СМО, являются:

1. вероятности состояний системы;
2. загрузка или коэффициент использования системы;
3. время ожидания заявок в системе;
4. время пребывания в системе;
5. число заявок в очереди системы или длина очереди;
6. число заявок в системе.

Следует отметить, что все перечисленные характеристики имеют смысл только в том случае, когда система функционирует в установившемся режиме (без перегрузок), что и предполагается далее. Кроме того, последние четыре характеристики являются случайными величинами ("3" и "4" – непрерывные, "5" и "6" – дискретные) и полный анализ этих характеристик предполагает определение соответствующих функций распределения. Однако в большинстве практических приложений достаточно анализировать данные характеристики на уровне их средних значений, что и делается далее.

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

1) Вероятности состояний системы — это наиболее полная характеристика системы в том смысле, что, зная вероятности состояний, можно определить все остальные характеристики. При этом под состоянием СМО понимается число заявок, находящихся в системе. Вероятность состояния системы, когда в ней находится k заявок, обозначим далее через Р_k, k=0, 1, 2, ...

2) Загрузка системы — это отношение интенсивности поступления l к интенсивности обслуживания m и обозначается через r:

r=l/m=lb=b/а,

где а=1/l и b=1/m – средние значения интервалов поступления и длительности обслуживания соответственно.

Значение загрузки определяет условие  существования в системе стационарного режима. Необходимым и достаточным условием существования в стохастической СМО стационарного режима является условие, когда r<1 или l<m. Выполнение этого условия означает, что система в среднем справляется с поступающей нагрузкой. Если r³1, то система работает в режиме перегрузок.

 

Загрузка r СМО характеризует:

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

б) долю времени, в течение которого прибор занят обслуживанием;

в) вероятность того, что прибор занят обслуживанием заявок;

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

Перечисленные утверждения составляют физический смысл загрузки.

Справедливость утверждения "а" следует из определения загрузки r=lb: если l – среднее число заявок, поступающих в единицу времени, то за время b в систему поступят в среднем lb заявок.

Справедливость утверждения "б" можно показать следующими простыми рассуждениями. Рассмотрим достаточно длинный интервал t времени функционирования системы. Для простоты предположим, что в начале и в конце этого интервала система была свободна. Очевидно, что за время t в систему в среднем поступят lt заявок. Каждая из этих заявок в среднем обслуживается за время b. Тогда суммарное время обслуживания всех заявок равно ltb. Отсюда доля времени, в течение которого прибор занят обслуживанием заявок, равна ltb/t=lb=r, что и следовало показать.

Утверждение "в" напрямую следует  из утверждения "б", ибо рассмотренная ранее доля времени и есть вероятность занятости прибора. Тогда вероятность простоя системы равна 1–r.

Справедливость утверждения "г", в свою очередь, следует из утверждения "в": в приборе может находиться 1 заявка с вероятностью r и 0 заявок с вероятностью 1–r. Тогда среднее число заявок в приборе равно

1·r + 0·(1–r)=r.

3) Время ожидания — это, как правило, случайное время, которое заявка проводит в очереди в состоянии ожидания. Среднее значение этого времени, которое представляет наибольший интерес, обозначается через w.

4) Время пребывания — это случайный промежуток времени от момента поступления заявки в систему до момента окончания ее обслуживания. Для среднего значения u времени пребывания справедливо равенство:

u=w+b.

5) Среднее число заявок в очереди или средняя длина очереди

l=lw.

6) Среднее число заявок m, находящихся в системе, складывается из средних значений числа заявок, находящихся в очереди (l) и в приборе (r):

m=l+r=lw +lb=l(w+b)=lu

Формулы r =lb, l=lw и m=lu называются формулами Литтла соответственно для прибора, очереди и системы в целом. Справедливость этих формул показывается далее в разделе 2.4.

Ранее отмечалось, что если известны вероятности состояний, то можно  определить и все остальные характеристики системы. Предположим, что вероятности состояний  Р_к=Pr{в системе находится k заявок}, k = 0, 1, 2, ..., известны или заданы. Тогда загрузка системы, которая характеризует вероятность того, что, прибор занят обслуживанием, определяется равенством:

r

,

где P₀ – вероятность простоя системы.

В системе могут находиться 1, 2, 3, ... заявок соответственно с вероятностями P₁, P₂, P₃, .... Тогда, исходя из определения математического ожидания дискретной случайной величины, среднее число заявок в системе

.

Если в системе находится k заявок, то в очереди ожидают k–1 заявка (k= 1, 2, 3, ...). Тогда средняя длина очереди

m–r.

Зная среднее число заявок в  системе (m) и в очереди (l), соответствующие временные характеристики можно определить по формуле Литтла:

u=m/l       и       w=l/l=u–b.

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

 

2.2. Характеристики одноканальной  СМО

с неоднородной нагрузкой.

Рассмотрим характеристики функционирования ОК СМО с неоднородной нагрузкой. Пусть в СМО поступают заявки Н классов с параметрами:

– l₁, l₂, ... , l_н — интенсивность поступления;

– n_а1, n_а2, ... , n_ан — КВ интервалов поступления;

– b₁, b₂, ... , b_н — среднее время обслуживания;

– n₁, n₂, ... , n_н — КВ длительности обслуживания.

Приведенные параметры полностью  описывают систему, которая является СМО типа :

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

 

Характеристики заявок отдельных  классов.

1) Pr{n₁, n₂, ..., n_H} — вероятности состояний СМО, где под состоянием системы здесь понимается вектор , показывающий, сколько заявок каждого класса находятся в системе.

2) r_к=l_кb_к — загрузка СМО заявками класса k (k–заявок). При этом, загрузка r_к имеет тот же физический смысл, что и в случае однородной нагрузки, но только применительно к классу k .

3) w_k — среднее время ожидания k–заявок.

4) u_k=w_k+b_k — среднее время пребывания в системе k–заявок.

5) l_k=l_kw_k — средняя длина очереди заявок класса k.

6) m_k=l_ku_k =l_k+r_k — среднее число k–заявок в системе .

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

Характеристики заявок объединенного  потока.

1) — суммарная загрузка системы и СМО функционирует в стационарном режиме, если R<1. При этом h=1–R — коэффициент простоя.

2) — среднее время ожидания заявок объединенного потока, где — интенсивность результирующего потока.

3) — среднее время пребывания, где — усредненное время обслуживания.

4) — средняя (суммарная) длина очереди.

5) — среднее число заявок в системе.

 

2.3. Характеристики многоканальной  СМО 

(однородная нагрузка).

Рассмотрим МК СМО из N обслуживающих приборов, в которую поступает поток заявок интенсивности l и КВ n_а интервалов поступления. Все приборы совершенно идентичны и среднее время обслуживания в одном приборе равно b, а КВ длительности обслуживания – n. Определим для описанной МК СМО (типа G/G/N) характеристики функционирования.

1) Вероятности состояний. Под состоянием МК СМО как и в случае ОК СМО понимается число заявок k, находящихся в системе, и вероятность такого состояния также обозначается через P_k, k = 0, 1, 2, ...

2) Загрузка. По аналогии с ОК СМО произведение lb можно было бы трактовать как загрузку МК СМО. Однако это не так и в качестве загрузки МК СМО принимается загрузка ее одного прибора, определяемая как r=lb/N. Это делается с тем, чтобы использовать одинаковые обозначения для загрузки, придать одинаковый смысл загрузке, "приравнять" отдельные приборы МК СМО и прибор в ОК СМО. После такого определения загрузки МК СМО для нее справедливы все утверждения, приведенные ранее относительно загрузки ОК СМО. Отношение l/N=l¢ в выражении для загрузки характеризует интенсивность заявок, приходящих на один прибор МК СМО. Условием существования стационарного режима: r=l¢b<1.

3) Среднее число заявок m в МК СМО определяется так же, как и в ОК:

m=

.

4) Средняя длина очереди

l=

,

где k–N — число заявок в очереди, когда в системе находится k заявок.

5) Среднее время ожидания w определяется по формуле Литтла:

w=l/l.

6) Среднее время пребывания

u=m/l=w+b.

7) Вероятность ожидания или вероятность того, что все N приборов заняты обслуживанием заявок

.

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

.

С другой стороны, — это среднее число заявок, находящиеся в обслуживающих приборах, т.к., очевидно, что число занятых приборов всегда равно числу заявок в приборах. Вспомним, что загрузка r=lb/N — это среднее число заявок в приборе (одном). Тогда среднее число заявок в N приборах равно Nr. Таким образом

=lb.

Очевидно, что m=l+ (сравните с m=l+r для ОК СМО). Действительно

 

 

 

 

 

2.4. Вывод формулы Литтла.

Универсальная формула Литтла (справедлива  для любой системы без отказов) устанавливает связь между средними значениями числа заявок, времени пребывания и интенсивности поступления. Так для СМО в целом эта связь имеет вид: m=lu, вывод которой приводится ниже.

Рассмотрим производную СМО  и достаточно длинный интервал (0, t) ее функционирования. Пусть a(t) — число заявок, поступивших в систему, а d(t) — число заявок, покинувших ее за время t.

 Очевидно, что n(t)=a(t)–d(t) — число заявок в системе в момент времени t. С другой стороны, площадь между кривыми a(t) и d(t) (заштрихованная площадь) на интервале (0, t) есть общее (суммарное) время, проведенное всеми заявками в системе на момент времени t. Обозначим это общее время через g(t).