Алгоритм построения конечного дерева достижимости

Каждая i-я вершина дерева связывается с расширенной разметкой m(i). В расширенной разметке число меток в позиции может быть либо неотрицательным целым, либо бесконечно большим. Бесконечное число меток обозначим символом w. ()

Вершины классифицируются на 4 вида:

граничная, терминальная,

дублирующая, внутренняя.

Граничными являются вершины, которые еще не обработаны алгоритмом.

Алгоритм начинает свою работу с задания начальной разметки. До тех пор, пока имеются граничные вершины, они обрабатываются алгоритмом.

Пусть x - граничная вершина, которую необходимо обработать, и с которой связана разметка m(x).

1. Если для разметки m(x) на один из переходов неразрешeн, т.е. m (x) тупиковая разметка, то x терминальная вершина.

2. Если в дереве имеется другая вершина y, не являющаяся граничной, и с ней связана разметка m (y)= m (x), то вершина x дублирующая.

3. Для любого перехода tj, из множества T, разрешенных в разметке m (x), создать новую вершину z дерева достижимости. Разметка m(z), связанная с этой вершиной, определяется для каждой позиции рi следующим образом:

i. если m (x)i=w,то m(z)i =w;

ii. если на пути из корня дерева в z есть вершина y такая, что ^tj и
то m (z )i= w;

iii. в в противном случае

Дуга, помеченная tj, направлена от вершины х к вершине z. Вершина x переопределяется как внутренняя, вершина z становится граничной.

Когда все вершины дерева становятся терминальными, дублирующими или внутренними, алгоритм останавливается.

Конечное дерево достижимости

П р и м е р 2

Классификация переходов

Переход tj сети Петри С называется потенциально запустимым в маркировке μ, если в R(C,μ) существует маркировка μ', в которой tj разрешен.

Переход активен в маркировке μ, если потенциально запустим во всякой маркировке из R(C, μ).

Категории переходов по уровню активности:

o Уровень 0: Переход tj никогда не может быть запущен.

o Уровень 1: Переход tj потенциально запустим.

o Уровень 2: Для всякого целого n существует последовательность запусков, в которой переход tj присутствует по крайней мере n раз

o Уровень 3: Существует бесконечная последовательность запусков, в которой переход tj присутствует неограниченное число раз.

o Уровень 4: Для всякой μ' из R(C, μ) существует такая последовательность запусков σ, что переход tj разрешен в δ(μ`,σ).

Переход, обладающий активностью уровня 0, называется пассивным.

Переход, обладающий активностью уровня 4, называется активным.

Сеть Петри обладает активностью уровня i, если каждый ее переход обладает активностью уровня i.

П р и м е р 3

Сеть Петри с переходами различных уровней

t0 – пассивный

t1 – первый уровень

t2 – второй уровень

t3 – третий уровень

Некоторые виды сетей Петри:

Временная сеть Петри — переходы обладают весом, определяющим продолжительность срабатывания (задержку).

Стохастическая сеть Петри — задержки являются случайными величинами.

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

Цветная сеть Петри — метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях.

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

П р и м е р

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