Научная Сеть >> Маркированные гиперграфы в задачах компьютерного моделирования

Наука >> Математика >> Геометрия и топология | Научные статьи

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

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

Для исследования реальной производственной системы строится ориентированный гиперграф G, структура которого полностью соответствует структуре исследуемой системы. При этом маркированный гиперграф $G = {\left\langle {P,\,E,\,M_{0} } \right\rangle }$ представляется множеством вершин $P = {\left\{ {} \right.}p_{1} ,p_{2} ,\ldots,p_{n} {\left. {} \right\} }$ и множеством дуг и гипердуг $E = {\left\{ {} \right.}e_{1} ,e_{2} ,\ldots,e_{m} {\left. {} \right\} }.$ Для отражения динамики системы вводится маркировка дуг графа. Состояние системы в любой момент времени $k = 0,\;1, \,2,\ldots$ определяется текущим значением вектора маркировки $M_{k} = (\mu _{1}^{k} ,\mu _{2}^{k} ,\ldots,\mu _{m}^{k} )$ графа. Начальное состояние гиперграфа задается с помощью его начальной маркировки $M_{0} = (\mu _{1}^{0} ,\mu _{2}^{0} ,\ldots,\mu _{m}^{0} ).$ Выполнение маркированного гиперграфа осуществляется посредством запусков разрешенных вершин.

При описании матричным способом маркированный граф задается матрицами инцидентности $D^{ - } = {\left[ {d_{ij}^{ - } } \right]}, D^{ + } = {\left[ {d_{ij}^{ + } } \right]}$ размерностью $n\times m.$ Матрица $D^{ - }$ определяет входную функцию графа, а $D^{ + }$ - выходную функцию. Вершина маркированного графа считается разрешенной, если на каждой входной дуге размещается число маркеров, равное или превышающее ее кратность: $M_{j}^{k} \ge d_{ij}^{ - } .$ Если разрешенных вершин несколько, то осуществляется выбор одной из разрешенных вершин для запуска. При выборе необходимо определить тип входящих в разрешенные вершины дуг: являются ли они простыми дугами (И-дуги) или альтернативными гипердугами (ИЛИ-дуги). По матрице входов $D^{ - }$ определяется тип соответствующей дуги. Если дуга $e_{q}$ является входной более чем для одной вершины, т.е. ${\sum\limits_{i = 0}^{n} {d_{iq}^{ - } } }\gt 1,$ то она является гипердугой. Простая дуга $e_{q}$ является входной только для одной вершины, т.е. ${\sum\limits_{i = 0}^{n} {d_{iq}^{ - } } }=1.$ Из всех разрешенных вершин, в которые входит одна и та же гипердуга, выбирается только одна вершина для запуска. Выбор вершины осуществляется по заранее определенным критериям в зависимости от типа вершин. Разрешенные вершины с простыми входящими дугами запускаются поочередно согласно времени прибытия разрешающего маркера.

После очередного выбора вершины формируется вектор запуска $V_{k}$ размерности $n.$ Очередная маркировка $M_{k + 1} ,$ возникающая в результате запуска разрешенной вершины в маркировке $M_{k} ,$ определяется выражением: ${\rm M}_{k + 1} = {\rm M}_{k} + V_{k} \times D,$ где $D$ - результирующая матрица изменений состояния: $D = D^{ + } - D^{ - }.$ Таким образом, на каждом шаге $k$ выполнения расчетов определяется вектор запуска вершины $V_{k}$ и вычисляется очередная разметка графа ${\rm M}_{k} .$

Для реализации компьютерного моделирования создается библиотека модулей (компонент). Выбор модуля осуществляется заданием соответствующей вершине графа признаков, определяющих тип модуля (источник заявок, прибор обслуживания и т.п.). После выбора модуля редактируются его параметры. Например, для вершины типа "источник заявок" указываются параметры генерации однородного потока заявок. При такой организации моделирования модель производственной системы строится из стандартных модулей библиотеки с их параметрической настройкой. Библиотека модулей может расширяться пользователем в зависимости от решаемых задач. Описание взаимодействия компонент осуществляется при помощи оператора связи. При этом оператор связи задается в виде матрицы смежности. На рис. 1 представлена модель производственной системы в виде помеченного маркированного гиперграфа $P = {\left\{ {p_{1} ,p_{2} ,p_{3} ,p_{4} ,p_{5} } \right\}},\; E = {\left\{ {a,b,c,d,e,f} \right\}},\; M_{0} = {\left[ {{\begin{array}{*{20}c} {1} \hfill & {0} \hfill & {0} \hfill & {0} \hfill & {N} \hfill & {0} \hfill \\ \end{array} }} \right]}.$ Модель содержит два источника однородных потоков заявок (вершины графа 1, 2), узел формирования единого потока заявок (вершина 3), узел обработки заявок (вершина 4). Вершина 5 графа соответствует узлу статистической обработки и определяет режим управления процессом имитации. Интенсивность потоков заявок от источников определяется параметрами $\lambda _{1} = \lambda _{2} = 0.67.$ Интенсивность обслуживания заявок $\nu = 0.5.$ Общее число заявок в системе определяется количеством маркеров $N$ на дуге e в начальной маркировке $M_{0} .$ В системе по окончанию обслуживания очередной заявки ответ с узла поступает на источник, который ее сформировал. Для имитации данного закона генерации заявок источниками вершины графа 1, 2, 4 соединены гипердугой $a,$ а маркеры раскрашены. Цвет маркера определяется номером источника генерации текущей заявки и присваивается узлом, формирующим единый поток заявок.

Рис. 1.

Матрицы инцидентности для гиперграфа, представленного на рис.1, имеют следующий вид:

$D^{ - } = {\left[ {{\begin{array}{*{20}c} {1} & {0} & {0} & {0} & {0} & {0} \\ {1} & {0} & {0} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {1} \\ {0} & {0} & {1} & {0} & {1} & {0} \\ \end{array} }} \right]}, \quad D^{ + } = {\left[ {{\begin{array}{*{20}c} {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} & {0} & {1} \\ {1} & {0} & {0} & {0} & {0} & {0} \\ {0} & {0} & {0} & {1} & {0} & {0} \\ \end{array} }} \right]}.$

В заданной начальной маркировке разрешенными вершинами графа являются вершины 1 и 2. Выбор одной из вершин определяется раскраской маркера, которым отмечена гипердуга $a.$ Если раскраска $r = 1,$ то вектор запуска имеет следующее значение:

$V_{0} = {\left[ {{\begin{array}{*{20}c} {1} \hfill & {0} \hfill & {0} \hfill & {0} \hfill & {0} \hfill \\ \end{array} }} \right]}.$

На рис. 3 приведены результаты моделирования. Столбцы таблицы соответствуют номерам заявок. Первая строка соответствует времени поступления заявки, вторая - времени ожидания обслуживания в очереди, третья - времени начала обслуживания, четвертая - времени обслуживания, пятая - времени окончания обслуживания. В шестой строке указан номер источника (вершины графа), сформировавшего заявку.

Рис. 3.

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

П.П.Макарычев

Написать комментарий

Маркированные гиперграфы в задачах компьютерного моделирования.