Моделирование потоков работ сетями Петри

При моделировании потоков работ часто используются сети Петри и методы их функционального анализа [14-18]. Сети Петри — достаточно выразительное средство для моделирования потоков, в том числе синхронных и асинхронных.

Переход к сети Петри заключается в замене операторов алгоритма соответствующими операторами сети Петри и в «склеивании» этих операторов между собой. Склеивание происходит по обрамляющим позициям. Таким образом, можно задать отображение алгоритма в сеть Петри и далее использовать её в качестве модели алгоритма.

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

Сеть Петри формально задаётся пятёркой:

N = (Р, Т, F, Н, М0),

где

Р — непустое конечное множество позиций (мест),

Т — непустое конечное множество переходов,

F и Н — матрицы инцидентности, причём

F : Р х Т — отображение множества Р на Т,

Н : Т х Р — отображение множества Т на Р,

Mq — начальная разметка (маркировка) — вектор, который содержит информацию о количестве меток (фишек, маркеров) в соответствующих позициях (местах) сети.

Сеть называется ^-ограниченной, если количество меток в позиции не превышает величины к. Сеть является безопасной, если она fc-ограниченна и к = 1. Если метка при попадании в позицию не может её покинуть при данной разметке, то такая позиция является ловушкой. Сеть находится в состоянии тупика, если дальнейшее срабатывание переходов невозможно.

1.3.1.