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

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

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

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

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

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

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

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

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

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

Е_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: (М/D/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: (М/М/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.

Модель 6: (M/M/1): (FCFS /m/¥)

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

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

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

L = ; L_q = L – ;

W_q = W – ; W = .

Модель 7: (М/М/1):(FCFS/¥/m)

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

Р₀ = ; Р_n = )

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

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

 

В программе QM в модуле Waiting Lines – линии ожидания или в другой терминологии – система массового обслуживания приводится 9 моделей таких систем в следующих обозначениях:

Вышеописанные модели соответствуют этому списку, кроме модели 7, которая в этом списке обозначена как модель 8. Модели 7 и 8 из этого списка здесь не описаны.

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

- ошибка в данных: интенсивность обслуживания должна быть строго меньше, чем интенсивность прибытия. В таком случае, щёлкнув по кнопке ОК, исправьте данные.

 

Пример использования этих моделей

Пусть имеем первую модель и l = 5, а m = 7.

Выбрав модель 1, заполним исходные данные и решим задачу(рисунок 5.1).

 

Рисунок 5.1 – Исходные данные и решение задачи

Итак, r = l/m = 0,71 – первая строка отчёта – средняя интенсивность использования системы, т.е. вероятность того, что система занята обслуживанием, а остальные операционные характеристики этой СМО соответствуют ранее введённым обозначениям. Кроме того, можно вывести вероятности нахождения системы в том или ином состоянии (рисунок 5.2).

Рисунок 5.2 – Вероятностные характеристики системы

Так, например, P₀ = 0,29; P₁ = 0,2 и т.д., что отражено в первом столбике таблицы вероятностей и на графике. Второй столбик вероятностей – это вероятности, что в системе будет находиться не менее k требований, а третий – более k требований.

Если предположить, что в СМО может находиться только два требования, то при тех же данных операционные характеристики системы изменятся (например, одна бензоколонка и на ней могут находиться только два автомобиля) (рисунок 5.3):

Рисунок 5.3 – Решение задачи по модели (М/М/1)

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

Пусть имеется система МО типа (М/М/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 (руб.). Из модели 5 определим W_q = 0,041 5 часа или среднее время ожидания 0,0415*16 = 0,066 4 (часа).

Тогда издержки ожидания равны 60*0,664 = 39,84 (руб.), а общие издержки: 672 + 39,84 = 711, 84 (руб.).

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

 

Задания для выполнения лабораторной работы №5

Считать, что интенсивность входящего потока равна 10+n,

где n – номер варианта;

интенсивность потока обслуживания равна 15+n;

число каналов обслуживания равно 2 (в этом случае интенсивность входящего потока удваивается);

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

число мест в очереди равно 2;

ёмкость источника заявок равна 3.

Решите задачу выбора оптимальной СМО со своими данными при этом подключите позицию «Use costs».

 

Лабораторная работа № 6

Сетевое моделирование