Использование сетей Петри для планирования

Месторасположение/переход сети Петри

Двудольный граф

Месторасположение/переход сети Петри (Р/Т PN) [DIA 93] (R = (Р, W), т₀) является двудольным графом, где:

• — Р = {/?j, ..., /?_м} иТ = {/|, ..., t_N} — два набора узлов, называемые местами и переходами соответственно, с |Р| = М и |Т| = N;
• — W:P-TuT-P^N выступает в качестве уравнителей дуг, соединяющих узлы;
• — т₀: Р -> N связано с каждым местом р е Р, в целом т₀(/?) называется маркировкой р.

Термины «вышестоящий» и «нижестоящий» используются для описания предыдущих и последующих узлов в сети соответственно.

Графическое представление

В графическом представлении сети Петри места располагаются в кружках, а переходы — в прямоугольниках. Метки (токены) располагаются в кружках с точками внутри. На рисунке 5.3 показан пример месторасположения/перехода сети Петри, где т₀ = (1,0, 0, 0, 1,0, 1, 1)^т.

Рисунок 5.3. Пример месторасположения/перехода сети Петри

Матричное представление

Матрицы инцидентности С~, С⁺ е N^MxN иСе Z^MxN определяются следующим образом:

Матрицы инцидентности, которые относятся к сети, изображенной на рисунке 5.3, представлены на рисунке 5.4.

Для краткости изложения информации мы использовали систему обозначений, применяемую в линейной алгебре:

• — Вектор e_tk обозначает собственный вектор, связанный с переходом t_k, чей к-й компонент равен 1, а остальные компоненты равны нулю.
• — Вектор то обозначает маркировочный вектор, определенный по следующей формуле: гщ = (т{р), т(р2), ..., т(рМ))^Т е N^M.

Рисунок 5.4. Матрица инцидентности сети на рисунке 5.3