5.2.3 Функционирование cpn
Рассмотрим работу раскрашенных сетей Петри. Как и в случае обыкновенных СП, функционирование сети состоит в срабатывании переходов и происходящих вследствие этого изменениях маркировок.
Мы будем говорить, что переход может сработать (может быть запущен), если выполняется условие:
. (5.20)
В первой скобке выражения (4.20) происходит поэлементное сравнение мультимножества, являющегося маркировкой позиции с мультимножеством, которым помечены дуги, ведущие от к .
Суммирование мультимножеств связано с тем, что, как отмечалось в п. 5, два узла могут быть соединены несколькими дугами, и суммирование производится по всем таким дугам.
Во второй скобке записано условие отсутствия блокировки перехода (см. п. 8 определения).
Если условие
срабатывания перехода
выполняется, то он может сработать, при
этом говорят, что выполнится шаг работы
CPN. Отсчет шагов производится в дискретном
времени
.
Поэтому маркировку отдельных позиций
и сети в целом
мы будем также привязывать ко времени
и записывать соответственно в виде
и
.
Изменение маркировки
узла
при осуществлении шага работы CPN
рассчитывается по формуле:
. (5.21)
В выражении (5.21)
все слагаемые являются мультимножествами,
и вычисления производятся в соответствии
с правилами сложения и вычитания
мультимножеств. Знаки суммирования
мультимножеств используются в формуле
по причине, которая уже пояснена выше:
каждая пара узлов может быть связана
несколькими дугами, а каждая дуга
помечена отдельным выражением
.
Если на некотором шаге
выполняются условия срабатывания
нескольких переходов, то по аналогии с
обыкновенными СП, в зависимости от
задачи исследования CPN мы можем разрешить
сработать всем переходам (при построении
дерева возможных маркировок) либо дать
такую возможность только одному из них
на основе некоторых дополнительных
условий (например, приоритетов).
Пример. Приведем описание простой CPN, схема которой и начальная маркировка приведены на рисунке 5.7 а.
а) б)
Рис. 5.7 Раскрашенная сеть Петри и эквивалентная ей обыкновенная СП
Множества цветов:
;
.
Переменные:
;
.
Множество позиций:
.
Множество переходов:
.
Множество дуг
,
,
,
,
,
;
;
;
;
Цветовая функция
Блокировочная функция отсутствует:
.функция
,
задающая выражения на дугах:
;
функция инициализации
,
задающая начальную маркировку
;
;
.
Ниже приведено полное дерево маркировок рассмотренной сети.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Поясним описание
сети. Для позиции
разрешен цвет
,
для позиций
,
разрешены цвета
,
,
.
Переход
может сработать, если в позиции
находится хотя бы одна фишка цвета
и в позиции
находится хотя бы одна фишка цветов
,
,
.
В позицию при срабатывании перехода пересылается та фишка, которая была извлечена из при срабатывании перехода. Начальная маркировка – 3 фишки цвета в позиции , по одной фишке всех цветов в позиции .
При работе сети
переменная
принимает поочередно (в произвольном
порядке) значения
,
,
,
а переменная
- значение
.
Работа сети продолжается до тех пор,
пока все фишки из
не будут пересланы в
.
При этом позиции
и
оказываются пустыми. Дерево маркировок
описывает все возможные варианты
последовательности пересылки фишек.
Эквивалентная рассмотренной CPN обыкновенная сеть Петри приведена на рисунке 5.7 б.
Построив дерево маркировок этой сети, нетрудно убедиться, что оно структурно совпадает с рассмотренным выше деревом CPN. Однако раскрашенная сеть содержит больше информации, поскольку ресурсы в позиции не обезличиваются, и можно проследить порядок их поступления.