В практике моделирования объектов часто приходится решать задачи, связанные с формализованным описанием и анализом причинно-следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов. Самым распространенным в способом описания структуры и взаимодействия параллельных систем и процессов, являются сети Петри (англ. Petri Nets).
Впервые сети Петри предложил немецкий математик Карл Адам Петри в своей докторской диссертации "Связь автоматов" в 1962 году. Работа Петри привлекла внимание группы исследователей, работавших под руководством Дж. Денниса над проектом МАС в Массачусетском Технологическом институте. Эта группа стала источником значительных исследований и публикаций по сетям Петри. Полная оценка и понимание современной теории сетей Петри требуют хорошей подготовки в области математики, формальных языков и автоматов.
Теория сетей Петри развивается в нескольких направлениях:
- разработка математических основ,
- структурная теория сетей,
- различные приложения (параллельное программирование, дискретные динамические системы и т. д.).
Формально сеть Петри (N-схема) задается четверкой вида
N=áB,D,I,Oñ
где В - конечное множество символов, называемых позициями, В¹Æ;
D - конечное множество символов, называемых переходами, D¹Æ; BÇD¹Æ;
I - входная функция (прямая функция инцидентности), I: B´D®{0, 1};
О - выходная функция (обратная функция инцидентности), О: D´B®{0,1}. Таким образом, для каждого перехода djÎD можно определить множество входных позиций перехода I(dj)и выходных позиций перехода О(dj).
Аналогично, для каждого перехода biÎBвводятся определения множества входных переходов позиции I(b)и множества выходных переходов позиции O(bi):
Рисунок 1 – Циклические траектории элементов производственной системы.
Рисунок 2 – Сеть Петри, моделирующая работу станка.
Графически N-схема изображается в виде двудольного ориентированного мультиграфа, представляющего собой совокупность позиций и переходов (рис. 2). Как видно из этого рисунка, граф N-схемы имеет два типа узлов: позиции и переходы, изображаемые 0 и 1 соответственно. Ориентировочные дуги соединяют позиции и переходы, причем каждая дуга направлена от элемента одного множества (позиции или перехода) к элементу другого множества (переходу или позиции). Граф N-схемы является мультиграфом, так как он допускает существование кратных дуг от одной вершины к другой.
Возможные приложения.
Приведенное представление N-схемы может использоваться только для отражения статики моделируемой системы (взаимосвязи событий и условий), но не позволяет отразить в модели динамику функционирования моделируемой системы. Для представления динамических свойств объекта вводится функция маркировки (разметки) М:B®{0, 1, 2, ...}. Маркировка М есть присвоение неких абстрактных объектов, называемых метками (фишками), позициям N-схемы, причем количество меток, соответствующее каждой позиции, может меняться. При графическом задании N-схемы разметка отображается помещением внутри вершин-позиций соответствующего числа точек (когда количество точек велико, ставят цифры).
Маркированная (размеченная) N-схема может быть описана в виде пятерки NM =áB, D, I, О, Mñи является совокупностью сети Петри и маркировки М.
Функционирование N-схемы отражается путем перехода от разметки к разметке. Начальная разметка обозначается как M0:В®{0, 1, 2, ...}. Смена разметок происходит в результате срабатывания одного из переходов djÎD сети. Необходимым условием срабатывания перехода dj является M(bi)³1, где М{bi} — разметка позиции bi. Переход dj, для которого выполняется указанное условие, определяется как находящийся в состоянии готовности к срабатыванию или как возбужденный переход.
Рисунок 3 – Пример функционирования размеченной N -схемы.
Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход.
Все это происходит до тех пор до тех пор, пока хотя бы один из переходов будет разрешен. Поиск тупиковых ситуаций (когда ни один из переходов не является разрешенным) – тема отдельной статьи.
Переход запускается удалением всех разрешающих фишек из его входных позиций и последующим помещением в каждую из его выходных позиций, по одной фишке для каждой дуги.
Срабатывание перехода dj изменяет разметку сети М(Ь)= =(М(Ь1), Мф2), ..., М(Ья))г на разметку М'(Ь) по следующему правилу:
M'(b) = M(b) ¾ I(dj) + 0(dj),
Для изображения смены разметки М на М' применяют обозначение .
Функционирование N-схемы продолжается до тех пор, пока существует хотя бы один возможный переход.
Таким образом, N-схема выполняется путем запусков переходов под управлением количества меток и их распределения в сети. Переход запускается удалением меток из его входных позиций и образованием новых меток, помещаемых в выходные позиции. Переход может запускаться только тогда, когда он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число меток, по крайней мере равное числу дуг из позиции в переход.
Пример.
Для некоторой заданной размеченной N-схемы (рис. 4) с начальной маркировкой M0={1, 2, 0, 0, 1} разрешенным является только переход dl, а остальные переходы d2, d3 и d4— запрещенные. В результате выполнения этого перехода получим новую размеченную N-схему. Теперь разрешены переходы d2 и d3; в результате их запуска получим новую размеченную N-схему. Переходы d2 и d3находятся в конфликте, так как запущен может быть только один из них. Например, при запуске d3получим сеть, показанную на рис. 4,в. Теперь разрешен только переход d4 и получим новую размеченную сеть (рис. 4,г). Теперь разрешено два перехода: d2 и d3 (в конфликте). Запустим переход d4 (рис. 4, д). Теперь ни один переход не может быть запущен и выполнение сети прекращается.
Важной особенностью моделей процесса функционирования систем с использованием типовых N-схем является простота построения иерархических конструкций модели. С одной стороны, каждая N-схема может рассматриваться как макропереход или макропозиция модели более высокого уровня. С другой стороны, переход, или позиция N-схемы, может детализироваться в форме отдельной подсети для более углубленного исследования процессов в моделируемой системе S. Отсюда вытекает возможность эффективного использования N-схем для моделирования параллельных и конкурирующих процессов в различных системах.
Типовые N-схемы на основе обычных размеченных сетей Петри пригодны для описания в моделируемой системе S событий произвольной длительности. В этом случае модель, построенная с использованием таких N-схем, отражает только порядок наступления событий в исследуемой системе S. Для отражения временных параметров процесса функционирования моделируемой системы S на базе N-схем используется расширение аппарата сетей Петри: временные сети, Е-сети, сети Мерлина и т. д.
.
Важной особенностью моделей процесса функционирования систем с использованием типовых N-схем является простота построения иерархических конструкций модели. С одной стороны, каждая N-схема может рассматриваться как макропереход или макропозиция модели более высокого уровня. С другой стороны, переход, или позиция N-схемы, может детализироваться в форме отдельной подсети для более углубленного исследования процессов в моделируемой системе S. Отсюда вытекает возможность эффективного использования N-схем для моделирования параллельных и конкурирующих процессов в различных системах.