Модели массового обслуживания

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

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

М – пуассоновское (марковский случайный процесс);

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

Е_k – Эрланга с параметром k;

GI – произвольное.

Для обозначения закона распределения времени обслуживания обозначения следующие:

М – отрицательный экспоненциальный;

Д – детерминированный (с фиксированной продолжительностью обслуживания);

Е_k – Эрланга с параметром k;

GS – общее распределение произвольного вида.

Для рассматриваемых далее моделей массового обслуживания дисциплина очереди принимается естественной: первый пришёл, первый обслуживается, и она обычно обозначается FCFS.

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

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

Модель 1. Одноканальная однофазная модель массового обслуживания с пуассоновским входящим потоком и экспоненциальным временем обслуживания (М/М/1).

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

1) требования обслуживаются в порядке FCFS;

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

3) требования поступают в систему независимо друг от друга, случайным образом, с известной (фиксированной в среднем) интенсивностью;

4) закон распределения числа требований, прибывающих в систему за единицу времени является пуассоновским и ёмкость источника требований не ограничена (требования поступают из неограниченной совокупности);

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

6) время обслуживания требований подчинено экспоненциальному закону распределения;

7) средняя интенсивность обслуживания больше, чем средняя интенсивность прибытия.

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

Обозначим через l среднее (ожидаемое) число требований за единицу времени, а через m – среднюю интенсивность обслуживания. Тогда, при выполнении перечисленных предпосылок имеем:

1) среднее число требований в системе (в очереди, плюс обслуживаемое):

L = l /(m – l);

2) среднее время нахождения требования в системе (время ожидания, плюс время обслуживания):

W = 1/ (m–l);

3) среднее число требований в очереди:

L_q = l² / m (m – l);

4) среднее время ожидания в очереди:

W_q = l / m (m – l);

5) коэффициент использования времени обслуживания системы, т.е. вероятность того, что система занята обслуживанием:

r = l / m;

6) вероятность простоя системы массового обслуживания, т.е. вероятность того, что в системе нет ни одного требования:

Р₀ = 1 – l / m;

7) вероятность того, что в системе находится n требований:

Р_n = (l / m)ⁿ (1 – l / m)

8) вероятность того, что в системе находится не менее k требований:

Р_{n ³k} = (l / m)^k.

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

Р_n = Р₀ (l / m)ⁿ ; Р₀ =1 – r; L_q = L – l / m = l W_q;

L = L_q + l / m = l W; W_q = W – 1/ m = L_q / l;

W = W_q + 1/ l = L / l.

Модель 2. (М/GS/1) – одноканальная однофазная модель массового обслуживания с пуассоновским входящим потоком и произвольным распределением интенсивности обслуживания.

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

Р = l / m; Р₀ = 1 – l / m; L_q = ;

L = L_q + l /m; W_q = L_q / l; W = W_q + 1/ m.

Модель 3. (М/Д/1) – одноканальная однофазная модель с пуассоновским входящим потоком и фиксированным временем обслуживания. От предыдущей модели эта модель отличается лишь тем, что для неё = 0.

Модель 4. (М/Е_k/1) – одноканальная однофазная модель массового обслуживания с пуассоновским входящим потоком и выходящим потоком Эрланга (k фаз).

Эта модель также является частным случаем модели 2 при s² = 1 / km² . Имеем р = l / m; Р₀ = 1 – r; L_q = ;

s² = 1 / km²; L = L_q + l / m; W_q = ; W = W_q + 1/m.

Не следует забывать, что, как это было указано при обсуждении закона распределения Эрланга, время обслуживания для каждой фазы считается одинаковым, а общее время обслуживания в системе кратно числу фаз. Например, если время обслуживания для каждой фазы равно 10 минут, а число фаз k = 3, то общее время обслуживания равно 30 минут, т.е. интенсивность обслуживания в среднем равна двум требованиям в час (т.е. m = 2).

Модель 5. (M/M/1): (FCFS /m/¥). От модели 1 эту модель отличает то, что здесь введены ограничения на длину очереди: m – максимальное число требований в системе, следовательно, если в системе занято все m мест, то очередное требование покинет систему не обслуженным. Такая система массового обслуживания называется системой с отказами. Операционные характеристики такой системы определятся из соотношений:

Р₀ = ; Р_n = Р₀ (l / m)ⁿ для n m;

Р_m – вероятность того, что требование покинет систему необслуженным.

L = ; L_q = L – ;

W_q = W – ; W = .

Модель 6. (М/М/1):(FCFS/¥/m). В этой модели в отличие от модели 1 предполагается, что ёмкость источника заявок ограничена величиной m. Такие системы массового обслуживания называются замкнутыми. Их операционные характеристики определятся из соотношений:

Р₀ = ; Р_n = )

L_q = m – L = L_q + (1 – P₀) или

L = m – ; W_q = ; W = W_q + 1/m.

Модель 7. (М/М/S) – в отличие от модели 1 здесь предполагается, что система массового обслуживания имеет s каналов обслуживания. Интенсивность каждого канала обслуживания одинакова и равна m, так что суммарная интенсивность системы массового обслуживания равна s m. Следовательно, для устойчивого функционирования системы необходимо, чтобы s m было больше интенсивности входящего потока l. Операционные характеристики такой системы определятся из соотношений:

Р₀ = ; Р_n = , если n £ S;

Р_n = ; r= ; L_q = ;

L = L_q + l / m; W_q = L_q / l; W = W_q + l / m.

Здесь приведён неполный перечень из стандартных моделей массового обслуживания. Возможны различные комбинации уже рассмотренных случаев. Например, (М/ М / S): (FCFS / m / ∞) или (М / М / S): (F C F S / ∞ / m) и др.

В заключение приведём пример использования стоимостных показателей при анализе систем МО.

Пусть имеется система МО типа (М / М / 1) с λ = 2 и μ = 3. Известно, что издержки ожидания в очереди равны 60 руб. за час, а издержки функционирования равны 42 руб. за час. Кроме того, имеется аналогичная система МО с большей интенсивностью обслуживания (μ = 4), но и большими издержками обслуживания (54 руб. за час). Необходимо выбрать из них более эффективную, предполагая, что общие издержки систем состоят из издержек обслуживания и ожидания исходя из 8-часового рабочего дня.

Подсчитаем издержки функционирования каждой системы. В первой системе: 42 8 = 336 (руб.), во второй – 54 8 = 432 (руб.).

Далее, используя модель 1, определим среднее время ожидания требований в системе и соответствующие ему издержки ожидания.

В первой системе – это среднее время ожидания одного требования.

В день в среднем поступает 2 8 = 16 требований, следовательно, общее время ожидания равно 2/3 16 = 10,667 часа, а издержки ожидания составят 10,667 60 = 640 (руб.).

Во второй системе , общее время ожидания равно 16 1/4 = 4 (часа), а издержки 4 60 = 240 (руб.).

Итак, общие издержки в первой системе равны 336 + 640 = 976 (руб.), а во второй – 432 + 240 = 672 (руб.), т.е. вторая система МО более эффективна.

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

Издержки функционирования такой системы определяются как 42 8 2 = 672 (руб.).

Из модели 7 определим W_q = 0,0415 часа или среднее время ожидания 0,0415 16 = 0,0664 (часа). Тогда издержки ожидания равны 60 0,664 = 39,84 (руб.), а общие издержки: 672 + 39,84 = 711, 84 (руб.).

Сравнивая с 672 руб., видим, что второй случай более выгоден.