Имитационная модель СМО с гиперэкспоненциальным распределением в среде GPSS World

Универсальная среда дискретно-событийного моделирования GPSS WORLD не нуждается в рекламировании, т.к. широко используется при моделировании систем массового обслуживания, и производственных систем [1-4]. Она включает множество библиотечных программ, в том числе генераторы псевдослучайных последовательностей для различных законов распределений. В теории массового обслуживания востребованы законы распределений с широким диапазоном коэффициента вариации случайной величины, такие как гиперэкспоненциальный или гиперэр-ланговский. Таких генераторов в системе моделирования GPSS WORLD нет и их надо разрабатывать на основе имеющихся. Этот недостаток препятствует моделированию систем массового обслуживания типа G/G/1 и G/G/m с наиболее общими распределениями.

Разработку имитационной модели проиллюстрируем на примере системы H 2 /M/1, сформированной функциями плотности

a ( t ) = pX 1 e "^X1 t + ( 1 - p ) X 2 e ^-x 2 t , (1) как вероятностной смеси экспоненциальных распределений и экспоненциального распределения

b ⁽ t ) =ц e "^ц t .                    (2)

Таким образом, настоящая статья посвящена моделированию СМО H 2 /M/1 с гиперэкспоненциальным (H 2 ) и экспоненциальным (M) входными распределениями в среде GPSS WORLD.

Постановка задачи

В статье ставится задача построения имитационной модели для СМО H 2 /M/1 и подтверждения адекватности построенной математической модели путем численного моделирования в пакете Mathcad. Тогда построение таких же моделей для других систем с использованием распределения H 2 не должно вызывать осложнений.

Решение задачи

При построении любой имитационной модели необходимо задавать исходные данные. В нашем случае это будут значения моментных характеристик распределений HE 2 и M, а через них определим неизвестные параметры распределений (1) и (2). Моментные характеристики определим через преобразование функции Лапласа (1):

A ⁽ ^ ) = p ⁽ t-^¹— ) + ( 1 ^- p ) ⁽T^²—) .

X 1 + s          X ₂ + s

Тогда два первых начальных момента будут равны:

– для интервалов поступлений

, _ Р_ . ^{( 1} — Р ) _T2₌2 p . ^{2 (1 -} p ) ^Ч"Х 1⁺ х2 ^{, Ч} = х ²      X ²

– для времени обслуживания тц = 1/ ^ , тц = 2 / ^ •

,

Из уравнений моментов (3) найдем неизвестные параметры распределения (1) х1, х2, Р. Для этого к уравнениям моментов (3) добавим выражение для квадрата коэффициента вариации:

2    ^т К ^{- ( т} К ) 2

cх =----- 5 —,

( Ч ) 2

как связующее условие между уравнениями (2). Исходя из вида первого уравнения (3) положим х1 = 2Р/тх , X2 = 2(1 -p)/тх        (4)

и потребуем выполнения условия (3) [2; 3]. Подставив выражения (4) с учетом (2) в (3), получим

10 HYPERI FVARIABLE (Exponential(l,0,1.252))

20 HYPER2 FVARIABLE (Exponential 1,0,9.86))

30 TEST L (RN1),0.887,METl

40 GENERATE VSHYPERl

50 TRANSFER ,MET_2

60 MET_1 GENERATE V$HYPER2

70 MET2 QUEUE QCHAN

80 SEIZE CHAN

90 DEPART QCHAN

100 ADVANCE (Exponential (1,0,1.0))

110 RELEASE CHAN

120 TERMINATE 1

130 START 1000000

; Переменная для первой фазы гиперэкспон ; Переменная для второй фазы гиперэкспон ; Если значение случайной величины меньше ; pi, то генерировать первую фазу и встать в ; очередь к устройству "CHAN", если нет, то ; переход по метке 1 для генерирования ; второй фазы

; Встать в очередь к устройству "CHAN"

; Занять устройство "CHAN"

; Покинуть очередь к устройству "CHAN"

; Задержать транзакт на единичное время

; Освободить устройство "CHAN"

; Удалять по одному транзакту

; Прогон 1 млн. транзактов

GPSS World simulation Report - Untitled Model 1.1.1

	Sunday, November	27, 2022 17:47:08
LABEL MET_1 MET_2 FACILITY	START TIME    END TIME BLOCKS FACILITIES STORAGES 0.000     1112574.792   10        1           0 NAME                         VALUE CHAN                         10003.000 HYPERI                       10000.000 HYPER2                       10001.000 MET_1                            4.000 MET_2                            5.000 QCHAN                        10002.000 LOC BLOCK TYPE ENTRY COUNT CURRENT COUNT RETRY 1      TEST        0              0             0 2    GENERATE    887557       0            0 3    TRANSFER    887557       0            0 4    GENERATE    112447       0            0 5    QUEUE       1000004      3            0 6    SEIZE       1000001      1            0 7    DEPART      1000000      0            0 8    ADVANCE     1000000      0            0 9    RELEASE     1000000      0            0 10   TERMINATE   1000000      0           0 ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY					DELAY
CHAN	1000001 0.899   1.000	1   1000002	0	0	0	3
QUEUE	MAX CONT. ENTRY ENTRY(0)	AVE.CONT. AVE.	TIME	AVE.	(-0)	RETRY
QCHAN	92   4 1000004 101172	8.103     9.015		10.	030	0

Рисунок 1. Результаты прогона имитационной модели

уравнение четвертой степени относительно неизвестного параметра p. Отбросив тривиальные ре- шения p = 0 и p = 1, получим квадратное уравнение, решив которое, выберем для однозначности больший корень для параметра p:

p =2^{(1 +}

c ² —¹

'l с 2 + 1) .

Отсюда следует, что коэффициент вариации c х ^ 1 . Подставив (5) в (4), определяем все три неизвестных параметра распределения (1) [5-7].

Для построения и отладки имитационной модели для системы H₂/M/1 возьмем коэффициент загрузки р = т_ц / Т х = 0,9 , коэффициент вариации интервалов поступлений с х = 2 и единичное время обслуживания т_ц = 1 . Тогда исходные данные для имитационной модели будут иметь вид:

Р = 1(1 + c l"¹ ) = 0,887 , 1 — Р = 0,113 , 2 1 = 1,597 , ²     С с² + 1

2 ₂ = 0,203 .

Отсюда средние значения для первой и второй фаз гиперэкспоненциального распределения

2/ 2 1 = 1,252, 2 / 2 2 = 9,86 единиц времени.

Сравнение имитационной модели с аналитической

Вначале при построении имитационной модели используем логический оператор TEST для перенаправления транзактов в модели с вероятностью p на первую фазу гиперэкспоненциального закона, а с вероятностью 1- p – на вторую фазу, как это показано ниже в тексте имитационной модели. Здесь отмечается полная аналогия с аналитической моделью (1) гиперэкспоненциального закона распределения, т.к. в аналитической модели предполагается мгновенная передача заявок с заданной вероятностью p на первую фазу, а с вероятностью 1 - p – на вторую фазу.

Анализ результатов прогона модели (рисунок 1) показывает, что в этом случае на первую фазу направляется примерно 887 тыс. транзактов, а на вторую фазу - 113 тыс. траз-актов, что полностью соответствует заданным вероятностям 0,887 и 0,113. Коэффициент загрузки равен 0,9 а среднее время обслуживания – единице, т.е. исходные данные и результаты моделирования совпадают. Коэффициент загрузки ρ в аналитике, также как в имитационном моделировании, определяется отношением средних интервалов р = тц / тх Результат по среднему времени ожидания в очереди 9,015 не соответствует аналитической модели [5; 6], которая дает 22,41 единиц времени.

Второй этап построения имитационной модели

Таким образом, в имитационном моделировании прямое копирование аналитического моделирования не подходит. Здесь нужно учитывать механизм дискретно-событийного продвижения транзактов в модели. Далее нужно промоделировать двухфазное формирование гиперэкспоненциального распределения для имитационной модели (рисунок 2). Для этого в предыдущую модель надо добавить логические переключатели в составе трех операторов: Switch TRANSFER, LOGIC, GATE, каждый со своим форматом.

Рисунок 2. Формирование двухфазного гиперэкспоненциального распределения

На рисунке 2 показано, что с вероятностью p сформированный транзакт отправляется на первую фазу гиперэкспоненциального закона со средним интервалом 1/λ 1 , а с вероятностью 1- p – на вторую фазу со средним интервалом 1/ λ 2 . В схему включены логические переключатели – объекты, которые могут находиться только в двух состояниях: включен, выключен. Эти два состояния управляются с помощью логического оператора LOGIC X A. Здесь A – имя логического ключа, X – логический оператор, задающий тип операции: S – включить, R –выключить.

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

Это достигается следующим логическим оператором GATE (впустить). Его формат: GATE X A,[B], где A – имя проверяемого объекта;

B – номер блока, к которому переходит тран-закт, если положение объекта не отвечает условию проверки;

X – логический оператор с множеством значений, проверяющий условие, которое должно быть выполнено для объекта в текущий момент для успешного завершения проверки. В нашем случае объектом A является переключатель Kluch1 или Kluch2, а положение объекта LS – логический ключ включен.

10 P_1 EQU 0.113

20 P_2 EQU (1-P_1)

30 T_1 EQU 4.926

40 T_2 EQU 0.626

50 GENERATE ,,,1

60 Switch TRANSFER P_1,Met_2,Met_1

70 Met_1 TRANSFER ,Kl_1

80 Met_2 TRANSFER ,Kl_2

90 Kl_1 LOGIC S Kluch1

100 ADVANCE (T_1#1.93)

110 LOGIC R Kluch1

120 TRANSFER ,Switch

130 Kl_2 LOGIC S Kluch2

140 ADVANCE (T_2#1.93)

150 LOGIC R Kluch2

160 TRANSFER ,Switch

170 GENERATE (Exponential(11,0,T_1))

180 GATE LS Kluch1,Met_10

190 TRANSFER ,Met_20

200 GENERATE (Exponential(21,0,T_2))

210 GATE LS Kluch2,Met_10

220 Met_20 QUEUE QCHAN

230 SEIZE CHAN

240 DEPART QCHAN

250 ADVANCE (Exponential(31,0,1.0))

260 RELEASE CHAN

270 TERMINATE 1

280 Met_10 TERMINATE

290 START 1000000

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

T_1#3.1, а для второго – T_2#3.1. Здесь T_1 и T_2 – средние интервалы для фаз, # - операция арифметического умножения. Константа 1,93

; Значение вероятности р1 1-й фазы

; гиперэкспоненциального распределения

; Значение вероятности р2 2-й фазы

; гиперэкспоненциального распределения

; Значение среднего интервала 1-й фазы

; Значение среднего интервала 2-й фазы

; Генерация одного транзакта управления

; ключами выбора фазы

; Включение 1-го ключа с вероятностью р1,

; а 2-го - с вероятностью р2

; Отправить транзакт на 1-й ключ «Kl_1»

; Отправить транзакт на 2-й ключ «Kl_2»

; Включить ключ 1-й фазы

; Время работы ключа

; Выключить ключ 1-й фазы

; Отправить транзакт на выбор рабочего ключа

; «Switch»

; Включить ключ 2-й фазы

; Время работы ключа

; Выключить ключ 2-й фазы

; Отправить транзакт на выбор рабочего ключа

; «Switch»

; Генерация 1-й эрланговской фазы

; Определения состояния 1-го ключа (если

; «включен»– переход к следующей строке

; программы, если «выключен» – переход на

; Met10)

; Переход по метке

; Генерация 2-й фазы

; Определение состояния 2-го ключа

; аналогично 1-му

; Встать в очередь к устройству «CHAN»

; Занять устройство «CHAN»

; Освободить одно место в очереди

; Задержать на обслуживании на единичное

; время

; Освободить устройство «CHAN»

; Удалять по одному транзакту

; Удалить транзакты из модели

; Прогон 1 млн. транзактов

GPSS World Simulation Report - Untitled Model 1.3.1 Sunday, November 27, 2022 19:14:41

START TIME 0.000	END TIME 1113182.614	BLOCKS FACILITIES 1 STORAGES
		24	1	0
NAME			VALUE
CHAN			10006.000
KLUCH1			10007.000
KLUCH2			10004.000
KL_	1		5.000
KL_,	2		9.000
MET	1		3.000
MET	ID		24.000
met"	J		4.000
MET	20		18.000
P 1"			0.113
P 2			0.887
QCHAN			10005.000
SWITCH			2.000
T_1			4.926
T_2			0.626
LABEL     LOC I	3LOCK TYPE	ENTRY COUNT CURRENT COUNT RETRY
1	GENERATE	1	0	0
SWITCH     2	TRANSFER	517670	0	0
MET_1      3	TRANSFER	58772	0	0
MET 2       4	TRANSFER	458898	0	0
KL_1       5	LOGIC	58772	0	0
6	ADVANCE	58772	1	0
7	LOGIC	58771	0	0
8	TRANSFER	58771	0	0
KL 2       9	LOGIC	458898	0	0
10	ADVANCE	458898	0	0
11	LOGIC	458898	0	0
12	TRANSFER	458898	0	0
13	GENERATE	226691	0	0
14	GATE	226691	0	0
15	TRANSFER	113740	0	0
16	GENERATE	1778237	0	0
17	GATE	1778237	0	0
MET 20    18	QUEUE	1000028	27	0
19	SEIZE	1000001	1	0
20	DEPART	1000000	0	0
21	ADVANCE	1000000	0	0
22	RELEASE	1000000	0	0
23	TERMINATE	1000000	0	0
MET_10    24	TERMINATE	1004900	0	0

FACILITY ENTRIES UTIL. AVE. TIME AVAIL. OWNER PEND INTER RETRY DELAY

CHAN 1000001 0.899   1.000    1    2004894 0    0     0     27

QCHAN 222 28 1000028 51979    20.159    22.440 23.670    0

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

Из результатов имитации на рисунке 3 следует, что коэффициент загрузки равен 0,899 вместо 0,9, а среднее время обслуживания – единице, т.е. исходные данные для примера и результаты моделирования совпадают. Среднее время ожидания заявок в очереди в 22,44 единицы времени практически совпадает с результатом численного моделирования 22,41. Средняя длина очереди в модели

20,159 также практически совпадает с результатом численного моделирования 20,3169.

В статье использованы приемы аппроксимации законов распределений с использованием моментных характеристик. Эти методы более подробно описаны в [8-13].

Заключение

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