11.1. Особенность системы массового обслуживания

Поток заявок на обслуживание поступает случайно, и завершение обслуживания происходит также в случайный момент времени (рис. 11.1).

Рис. 11.1. Схема системы массового обслуживания: H_i –накопитель с заданной емкостью; W_i – поток заявок на канал K_i; U_i – поток обслужи-

вания

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

11.2. Виды потоков

Виды потоков подразделяются на однородный и неоднородный.

1. Однородный поток характеризуется только моментом поступления событий и задается последовательностью {t_n},

 = t_n – t_n-1.

2.Неоднородный поток характеризуется последовательностью {t_n, f_n}, где f_n – набор признаков событий.

Пример: заявка принадлежит конкретному источнику (возможны приоритеты).

Если есть интервалы ₁ и ₂, независимые между собой, тогда поток называется потоком с неограниченным последействием.

Пример: входной поток в метро – однородный, выходной поток зависит от прихода поезда на станцию.

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

P > 1 (t, t), P₁(t, t)>>P_>1(t, t),

здесь t выбирают произвольно, исходя из условий задачи.

Стационарным называется поток, для которого вероятность появления того или иного числа событий на интервале  зависит только от величины  и не зависит от t.

Отдельные приборы объединяются в композиции многих приборов П_i, образующих Q-схему. Если каналы К_i соединены параллельно, то имеет место многоканальное обслуживание. Если каналы соединены последовательно, то имеет место многофазное обслуживание. Для Q-схем необходимо использовать операторы сопряжения R, т.е. правила поведения в различных ситуациях:

• правило ожидания заявок в накопителе;

• правило обслуживания заявок каналом К_i каждого прибора П_i.

Приоритеты бывают следующих видов:

1. Статические.

2. Динамические.

3. Относительные.

4. Абсолютные.

Статические приоритеты назначают заранее и не они зависят от состояния системы.

Динамические приоритеты зависят от состояния системы.

Относительный приоритет означает, что заявка с более высоким приоритетом ожидает окончания обслуживания предшествующей заявки К_i каналом и только после этого занимает канал.

Абсолютным приоритетом называется приоритет, когда заявка с более высоким приоритетом прерывает обслуживание заявок с более низким приоритетом каналом К_i и сама занимает этот канал. При этом вытесненная заявка ставится в очередь согласно дисциплине (либо покидает систему, либо снова попадает в накопитель).

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

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

Для К_i-го канала необходимо разрабатывать правила выбора маршрутов и направлений ухода. Для заявок надо знать правила, по которым они остаются в канале К_i или не допускаются в канал, т.е. правила блокировки.

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

Рис. 11.2. Пример Q-схемы

Моделирование работы пивного бара

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

L_1,1=

Н_1,1

H_2,1

N2

n=16

L=16

N

l >1 N4

H_1,2

H_2,2

N1

n=4

N3

L=4

Рис.11.3. Структурная схема бара

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

N – общий поток клиентов;

N1 – поток клиентов, не допущенных в пивной бар;

N2 – поток клиентов у стойки бара;

N3 – поток клиентов за столиками бара;

K_1,1 – канал обслуживания (место за столиком);

K_1,2 – канал обслуживания (место за стойкой);

K_3,1, K_3,2 – канал обслуживания (2 официанта);

K_4,1 – канал обслуживания (бармен);

L_1,1 – длина очереди в бар.

L = L (T, L_1,1) – количество клиентов бара за время Т, это случайная функция, имеющая математическое ожидание, определяемое следующим уравнением:

m = 0,01 Q(T) f₁(L) f₂(T) (11.1)

и среднеквадратичным отклонением  = 0,4 m, где 0,01 – коэффициент, определяющий долю прохожих, являющихся потенциальными клиентами бара;

Q(T) – количество прохожих за время цикла Т=15 мин. (задается графиком рис. 11.4, 11.5);

f₁(L_1,1)=e^-1/3 – зависимость интенсивности посещений от длины очереди.

Допустим, что поставлены задачи:

1. Смоделировать процесс обслуживания клиентов при различных значениях каналов обслуживания.

2. Рассчитать затраты, связанные с изменением количества рабочих мест, считая, что один официант обслуживает 4 стола (16 клиентов) и за это получает 100 рублей за смену (8 часов).

3. Условно постоянные затраты считать равными 50 руб. в сутки.

4. Доход от каждого клиента принять равным 3,5 руб.

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

Транзакт потока N = {L, K, prior},

где K – канал обслуживания (в зале или за стойкой)

prior – приоритет посетителя:

с вероятностью 0,1% рэкетиры /приоритет 0;

с вероятностью 0,9% ветераны /приоритет 1;

с вероятностью 4,0% пьяные / приоритет 99;

с вероятностью 75% обычные клиенты в зале / при-

оритет 5;

с вероятностью 20% обычные клиенты за стойкой /

приоритет 6.

Q

0 6 11 17 19 21 24 Т, ч

Рис. 11.4. График изменения количества прохожих за Т в течение суток

f₂

0 6 17 19 21 24 Т, ч

Рис. 11.5. График изменения интенсивности посещений в течение суток

Примечание:

- пьяные не пропускаются;

- ветераны имеют относительный приоритет;

- рэкетиры имеют абсолютный приоритет.

Эту задачу можно решить в следующем порядке:

- процесс будем моделировать в дискретном времени с шагом T;

- количество клиентов каждого типа, посетивших бар за время T, моделируем как непрерывную случайную величину с математическим ожиданием m (11.1), умноженным на вероятность прихода клиентов соответствующего типа (полученное вещественное число округляем до целого);

- все клиенты командой push заносятся в две очереди: 1  в зал; 2  к стойке; № очереди моделируем как дискретную величину, реализуемую с вероятностями 0,95 и 0,05 соответственно;

- все клиенты поступают на обслуживание в очередь, реализуемую списками;

- списки имеют следующую структуру:

- № очереди;

- приоритет;

- состояние (0 заказ ещё не принят;

1  заказ принят;

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

- очередь на обслуживание формируется командой dispatch в соответствии с относительными приоритетами клиентов;

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

- признак принятия заказа (состояние = 1) заносится в первые элементы списков, имеющие признак состояния, равный 0;

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

- элементы списка, время окончания обслуживания которых больше текущего, переводятся функцией dispatch в состояние 2 и затем командой pool удаляются;

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

- условно постоянные расходы;

- расходы на содержание одного посадочного места в зале (плата за аренду единицы площади);

- расходы на заработную плату обслуживающего персонала (будем считать, что один человек может обслужить 16 человек).

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

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