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

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

Обслуживающая система Блок

обслуживания

Очередь

 

Поток

поступающих Выбывающие

заявок на из системы

обслуживание обслуженные

клиенты

 

 

Рисунок 1

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

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

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

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

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

с - число параллельно функционирующих узлов обслуживания (с=1, 2… ¥ );

d- дисциплина очереди;

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

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

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

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

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

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

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

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

Для иллюстрации рассмотрим структуру (M/D/10):(GD/N/¥). В соответствии с принятыми обозначениями здесь речь идет о СМО с пуассоновским входным потоком, фиксированным временем обслуживания и десятью параллельно функционирующими узлами обслуживания. Дисциплина очереди не регламентирована, что подчеркивается парой символов GD. Кроме того, независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь+обслуживаемые клиенты) не может вместить более N требований (клиентов), т.е. клиенты, не попавшие в блок ожидания, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.

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

При выполнении условий стационарности нас будут интересовать следующие операционные характеристики СМО:

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

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

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

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

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

По определению

Между L_s и W_s (как и между L_q и W_q) существует строгая взаимосвязь, так что, зная числовые значения одной из этих величин, можно легко найти значение другой величины. В частности, если частота поступлений в систему заявок на обслуживание равняется l (интенсивность поступления требований), то мы имеем

Приведенные выше соотношения справедливы и при гораздо менее жестких предположениях, не налагающих никаких специальных ограничений ни на распределение моментов последовательных поступлений требований, ни на распределение продолжительностей обслуживания. Однако в тех случаях, когда частота поступлений заявок на обслуживание равняется l, но не все заявки имеют возможность попасть в обслуживающую систему (например, из-за недостаточно большой вместимости блока ожидания), соотношения (1) необходимо видоизменить путем такого нового определения параметра l, которое позволило бы учесть только действительно "допускаемые" в систему требования. Тогда, вводя в рассмотрение

Эффективная частота поступлений,

l_ЭФФ = т.е. количество требований, действи-

тельно допущенных в блок ожидания

обслуживающей системы, в единицу

времени

будем иметь

В общем случае

Это означает, что только часть поступающих заявок на обслуживание действительно "проникает" в систему. Но в любом случае можно установить зависимость l_ЭФФ от L_S L_q следующим образом. По определению

Средняя продол- Средняя продолжи- Среднее время

жительность пре- = тельность пребы- + обслуживания.

бываний в системе вания требований

в очереди

Если средняя скорость обслуживания равняется m и, следовательно, средняя продолжительность обслуживания равняется 1/m, то справедливо следующее соотношение:

Умножая левую и правую части этого соотношения на l, получаем

Последнее соотношение остается справедливым и в том случае, если l заменить на l_ЭФФ. При этом для l_ЭФФ можно записать

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

Отметим, что в большинстве случаев при вычислении значений р_n в рамках соответствующей математической модели особые трудности не встречаются. Что же касается распределений продолжительностей ожидания, то их численная оценка может оказаться далеко не простой. Таким образом, в большинстве случаев удобнее вычислять W_S и W_q через L_S и L_q.

Пример. Рассмотрим СМО с одним обслуживающим прибором. Пусть среднее количество требований, поступающих в систему в течение часа, равняется трем(l), а скорость обслуживания составдяет 8 (m)требований в час. Вероятность р_n того, что в системе окажется n требований, определяется на основе данных, полученных в результате наблюдений за функционированием системы. Допустим, что мы имеем следующие статистические оценки:

n									³8
рn	0.625	0.234	0.088	0.033	0.012	0.005	0.002	0.001

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

На основе приведенных выше исходных данных можно вычислить L_S, W_S, W_q и L_q. Начнем с определения среднего числа требований, находящихся в обслуживающей системе:

требования. Поскольку l=3, для средней продолжительности пребывания требования в системе имеем

Учитывая, что m=8, получаем оценку средней продолжительности пребывания в очереди

откуда следует, что среднее количество находящихся в очереди "клиентов" равняется

Используя в качестве исходных данных, приведенные в предыдущем примере, вычислим:

(а) Среднее количество находящихся в очереди требований, используя при этом непосредственно известные значения р_n.

По определению

Подставляем соответствующие значения

(б) Среднее количество клиентов, которые обслуживаются системой.

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

При увеличении параметра l будет увеличиваться L_S и L_q, а при увеличении параметра m будет уменьшаться W_S и W_q.

2.1.1 Система массового обслуживания типа (M/M/1):(GD/¥/¥)

В модели (M/M/1):(GD/¥/¥) имеется единственный узел обслуживания (обслуживающий прибор), а на вместимость блока ожидания и емкость источника требований никаких ограничений не накладывается. Входной и выходной потоки являются пуассоновскими с параметрами l и m соответственно.

Прежде всего получим уравнение в конечных разностях для р_n(t), т.е. для вероятности того, что в интервале времени t в системе находится n требований (клиентов). После этого при надлежащих условиях перейдем к пределам пи t®¥ и получим формулу для р_n, соответстветствующих сиационарному режиму исследуемого процесса.

Уравнения в конечных разностях для р_n(t) выводятся на основе тех же соображений, которые приводились в связи с рассмотрением моделей чистого рождения и чистой гибели. Для достаточно малого, но не равного нулю h(>0) запишем

Вероятность поступления в систему n(n>0) требований в интервале t+h [обозначим эту вероятность через р_n(t+h)] складывается из следующих вероятностей:

а) в конце временного интервала t в системе находится n требований, а

Р в интервале h не происходит ни поступлений, ни выбытий

б) в конце временного интервала t в системе находится (n-1) требований, а

Р в интервале h происходит одно поступление, но не происходитвыбытий

в) в конце временного интервала t в системе находится (n+1) требований, а

Р в интервале h не происходит не одного поступления, но происходит

одно выбытие.

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

Для n=0 вероятность того, что в интервале h не произойдет ни одного выбытия, естественно, равняется единице. Следовательно,

Перенесем теперь (в предыдущем соотношении) р_n в левую часть и разделим левую и правую части полученного в результе уравнения на величину h. Переходя к пределу h®0, получим следующее дифференциальные уравнения:

Заметим, что при выводе этой системы дифференциально-разностных уравнений не было сделано никаких аппроксимаций. В этой связи подчеркнем, что аппроксимацию, которая заключается в замене е^-lh величиной (1-lh), не следует принимать в расчет, поскольку при предельном переходе h®0 все слагаемые высоко порядка (h² и выше) все равно обратились бы в нуль.

Решение приведенных выше дифференциально-разностных уравнений позволяет в принципе найти значения всех вероятностей р_n(t), которые описывают стохастический процесс, не обязательно являющийся (в общем случае) стационарным. Заметим, что как метод получения такого решения, так и само решение выглядят весьма сложными и громоздкими.

Можно доказать, что стационарное решение существует при t®¥, когда l<m. В предложение, что условие l<m действительно выполняется, нетрудно получить уравнения для стационарного процесса; в этом случае при t®¥ необходимо иметь в виду, что р'_n(t)®0, а р_n(t)® р_n для любого n=0, 1, 2 …. В результате будем иметь

Решение приведенной выше системы уравнений имеет следующий следующий вид:

где r=l¤m<1. В рассматриваемом случае распределение является геометрическим.

Выражение для L_S получается путем элементарных преобразований:

Заметим, что сходимость årⁿ обеспечивается за счет выполнения неравенства r<1. Используем теперь выведенные ранее формулы, получаем

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

Для анализа процесса обслуживания студентов в дисплейном классе с указанными выше операционными характеристиками можно использовать результаты, полученные для модели типа (M/M/1):(GD/¥/¥); при этом следует считать емкость источника, генерирующего заявки на обслуживание, неограниченной, а помещение, отведенное для ожидающих обслуживания студентов, способно разместить всех прибывших в класс студентов.

В рассматриваемом случае l=5 студентов в час, а m=60/10=6 студентов в час. Поскольку r=l¤m=5/6, т.е. меньше единицы, система может функционировать в стационарном режиме. Чтобы иметь представление о том, какое количество ЭВМ необходимо организовать в дисплейном классе, требуется вычислить L_q по формуле

Однако известно, что L_q интерпретируется как математическое ожидание, так что количество ожидающих обслуживания студентов в произвольно выбранный момент времени может оказаться либо меньше, либо больше четырех. Поэтому следует подойти к решению задачи определения количества ЭВМ для обслуживания прибывших студентов с позиции "разумного" обеспечения местами для работы, например, задавшись целью обеспечить одновременно работой 80% прибывающих студентов. Это эквивалентно выполнению условия

где s- подлежащее определению количество ЭВМ.

Используя формулу для р_n, можно записать

Учитывая, что

получаем r^S+1£0,2. Прологарифмировав обе части данного неравенства (при r=5/6), будем иметь

Поскольку значение log(5/6) отрицательное, деление на log(5/6) правой и левой частей приведенного выше неравенства изменяет знак неравенства, т.е. s получаем

Таким образом, для одновременного размещения по крайней мере 80% студентов минимальное число ЭВМ должно быть приблизительно в два раза больше найденного выше значения L_q.

Можно получить и другую важную информацию о функционировании дисплейного класса. Нетрудно вычислить долю времени, в течение которого дисплейный класс вынуждено бездействует. Для этого достаточно определить вероятность такого события равняется р₀=1-r»0,17; т.е. можно утверждать, что доля времени, в течение которого дисплейный класс будет простаивать, составляет 17%. С другой стороны, для оценки времени размещения студента в дисплейном классе необходимо знать сколько времени студент ожидает освобождение компьютера. В данном случае значение этого показателя, обозначенного через W_S, равняется

Как видно, значение W_S оказалось большим, так что возникает необходимость изыскать ресурсы для увеличения скорости обслуживания.

Найдем вероятность того, что пришедший студент будет вынужден ждать, пока его не обслужат. Так как вероятность того, что дисплейный класс будет пустовать равно 0,17, то необходимая вероятность равна 1-р₀=0,83.

Если параметр m будет ³12 мин, то система перейдет из стационарной в неустановившуюся, так как очередь со временем будет увеличиваться. Такое же явление будет получено, если интенсивность потока будет больше 5, а скорость обслуживания останется равной 10 мин. По этому нужно стремиться к уменьшению времени обслуживания.

2.1.2 Система массового обслуживания типа (M/M/1):(GD/N/¥)

 

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

Дифференциально-разностные уравнения как для n=0, так и 0<n<N имеют такой же вид, как в модели (M/M/1):(GD/¥/¥). Для n>N имеем p_n(t)-0, а для n=N

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

Решение приведенной выше системы уравнений для модели (M/M/1):(GD/N/¥) имеет вид

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

С учетом приведенной выше формулы для р_n выражение для среднего числа находящихся в системе требований принимает следующий вид:

Выражения для L_q,W_s и W_q можно получить из формулы для L_s, если предварительно вывести формулу для l_ЭФФ. Поскольку вероятность того, что требование не имеет возможности присоединится к очереди, равняется р_N, доля требований , которым разрешено войти в блок ожидания, равняется Р{n<N}=1- р_N. Отсюда следует, что

 

 

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

Пример. Ситуация предыдущего примера. Пусть дисплейный класс располагает пятью ЭВМ для обслуживания студентов. Если все ЭВМ заняты, дополнительно прибывающие в класс студенты вынуждены искать другой класс.

Не исключено, что инженеров класса прежде всего интересует количество студентов, которые покидают класс из-за ограниченности мест. Практически это эквивалентно нахождению разности между l и l_ЭФФФ:

В рассматриваемом примере N=5+1=6, r=5/6, а

Отсюда следует, что частота возникновения ситуации, когда прибывающий в класс студент не имеет возможности присоединиться к очереди, равняется 5*0,0774=0,387 студента в час; при 8-часовом рабочем дне это эквивалентно тому, что дисплейный класс в среднем за день будет терять три студента.

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

С учетом того, что l_ЭФФФ=l(1-r₆)=5(1-0,0774)=4,613, получаем

Таким образом, при введение ограничения на количество мест для работы (N=6) среднее время ожидания по сравнению со случаем, когда в дисплейный класс могли попасть все нуждающиеся студенты, сократилось примерно на полчаса. Это было достигнуто за счет "потери" в среднем трех студентов в день из-за недостаточности мест для работы прибывших студентов.

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

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

При увеличении количества ЭВМ на одно количество студентов, которое теряет дисплейный класс, при l=5 равно l-l_ЭФФ=lр_N=1,16 (N=6+1=7). Таким образом в течение 8-ми часового дня класс теряет только одного студента. При увеличении количества ЭВМ уже до 9 класс будет терять 0,00225 студента в час или 0,01125 студента в день (т.е. практически 0). При увеличении параметра l, для того чтобы не терять студентов необходимо прямо пропорционально увеличивать количество ЭВМ.

 

2.1.3 Система массового обслуживания типа (M/M/c):(GD/¥/¥)

 

Процесс массового обслуживания, описываемый моделью (M/M/c):(GD/¥/¥), характеризуется интенсивностью входного потока l и тем обстоятельством, что параллельно обслуживаются может не более с клиентов. Средняя продолжительность обслуживания одного клиента равняется 1/m. Входной и выходной потоки являются пуассоновскими. Конечная цель использования с параллельно включенных обслуживающих приборов заключается в повышении (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно с клиентов. Таким образом, если n=c, то интенсивность входного (выходного) потока равняетсясm. С другой стороны, если n<c, то интенсивность входного (выходного) потока равняется nm<cm (поскольку при этом занятыми обслуживанием окажутся не все обслуживающие приборы, а лишь n(<c) приборов). По существу, использование нескольких обслуживающих приборов эквивалентно использованию одного обслуживающего прибора, быстродействие которого варьируется, увеличиваясь при наличии в системе n требований ровно в n раз.

Таким образом, для анализа модели (M/M/c) требуется построить обобщенную одноканальную модель, в которой как интенсивность входного потока, так и скорость обслуживания зависели бы от n, так что вместо безиндексных параметров l и m нужно было бы использовать величины l_n и m _n. Нужно вывести формулу для вычисления стационарных значений значений р _n. Полагая l_n =l, а m _n =nm при n<c или m _n =сm при n³c, можно получить числовые оценки для функциональных характеристик системы, описываемой (М/М/с)- моделью. При заданных значениях l_n и m _n после нахождения значения р _n окажется также возможным получить результаты для СМО других типов.

Для модели (М/М/1):(GD/¥/¥) справедливы следующие утверждения:

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

Для стационарного режима, получим следующие уравнения:

Эти уравнения можно привести к следующему (более удобному) виду:

Рассматривая последовательно уравнения для р₁, р₂, р₃, … и рассуждая по обычной схеме, реализующей метод индукции, приходим к формулам:

 

Выражения для р₀ получено из условия åр_n=1.

Таким образом, если СМО относится к типу (M/M/c):(GD/¥/¥), то для оценки ее операционных характеристик мы исходим из того, что

Из выражения для р_n,выведенного для модели (M_n/M_n/1):(GD/¥/¥) при n£c

В случае, когда n³с, формула принимает следующий вид:

Полагая r=l¤m, находим

 

где r¤с<1 (или l¤mс<1).

Теперь нетрудно показать, что

При приближенный методе нахождения р₀ и L_q получаем: при r<<1 можно записать

Тогда как для значений r/с, близких к единице,

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

Администрация университета разрешила посещение всеми студентами всех библиотек обоих корпусов. При раздельном использовании библиотек между корпусами, которыми они принадлежали, коэффициент загруженности равнялся 95,8%:действительно,

(Заметим, что в рассматриваемом случае библиотека с точки зрения ТМО является "обслуживающим прибором".) Мы видим, что коэффициент загруженности работников библиотек корпусов был большим. Возникает вопрос о целесообразности централизации управления библиотеками.

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

(а) варианта с независимыми обслуживающими системами типа (М/М/2): (GD/¥/¥) при l=10 студентов в час и m=5,217 обслуживаний студентов в час

(б) варианта с одной очередью типа (М/М/4): (GD/¥/¥) при l=2*10=20 студентов в час и m=5,217 обслуживаний студентов в час.

Заметим, что в обоих случаях m интерпретируется как среднее число обслуживания одного студента в час.

Коэффициент загруженности во втором случае будет таким же, как и в первом случае, а именно

Объединение всех четырех библиотек в рамках одной системы не приводит на первый взгляд к эффекту. Если, однако, рассмотреть другие показатели, это первое впечатление не подтвердится. Вычислим W_q (среднее время ожидания студентом обслуживания от момента прихода в библиотеку до момента выдачи книг) в первом и втором случаях. Тогда для с=2 будем иметь

Таким образом,

С другой стороны, для с=4 будем иметь l/m=20/5,217=3,83 и

Следовательно,

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