Маркировка. Правила выполнения

Маркировка µ, есть присвоение фишек позициям сети Петри. Фишка - это примитивное понятие сетей Петри (подобно позициям и переходам). Фишки присваиваются (можно считать, что они принадлежат) позициям. Количество и положение фишек при выполнении сети Петри могут изменяться. Фишки используются для определения выполнения сети Петри.

Определение 5. Маркировка µ сети Петри С = (Р,Т, I, О) есть функция, отображающая множество позиций Р в множество неотрицательных целых чисел N.

Маркировка µможет быть также определена как n-вектор µ = (µ₁,µ₂, …, µ_n), где п есть мощность множества Р и каждое µ_i есть целое неотрицательное число, i = 1,.... п. Вектор µопределяет для каждой позиции р_i сети Петри количество фишек в этой позиции. Связь между определениями маркировки как функции и как вектора очевидным образом устанавливается соотношением. Обозначение ее в виде функции является несколько более общим и поэтому употребляется гораздо чаще.

Рис. 2.11. Маркированная сеть Петри. Структура сети Петри совпадает со структурами на рис. 2.1 и 2.4. Маркировка — (1, 2, 0, 0, 1).

Рис. 2.12. Маркированная сеть Петри. Структура аналогична структуре, изображенной на рис. 2.11, но маркировка отличается.

Маркированная сеть Петри М = (С, µ) есть совокупность структуры сети Петри С = (Р, Т, I, О) и маркировки µ, и может быть записана в виде М = (Р, Т, I, О, µ).

На графе сети Петри фишки изображаются маленькой точкой в кружке, который представляет позицию сети Петри. На рис. 2.11 и 2.12 приведены примеры графического представления маркированной сети Петри.

Рис. 2.13. Граф сети Петри с очень большой маркировкой (47, 13, 7, 42).

Так как количество фишек, которое может быть определено для каждой позиции, неограниченно, то в целом для сети Петри существует бесконечно много маркировок. Множество всех маркировок сети Петри, обладающей п позициями, есть множество всех n-векторов. Это множество, хотя и бесконечно, является счетным.

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

Переход может запускаться только в том случае, когда он разрешен. Переход называется разрешенным, если каждая из его входных позиций имеет число фишек по крайней мере равное числу дуг из позиции в переход. Кратные фишки необходимы для кратных входных дуг. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции p_i и р_j служат входами для перехода t_k, тогда t_k разрешен, если p_i и р_j имеют хотя бы по одной фишке. Для перехода t_j с входным комплектом #(p_i,I(t_j)) = 3 позиция p_i должна обладать по крайней мере тремя фишками, для того чтобы t_j был разрешен.

Определение 6. Переход t_j є Т в маркированной сети Петри С = (Р, Т, I, О) с маркировкой µ разрешен, если для всех p_i є Р

#(p_i,I (t_j))<= µ_i

Переход запускается удалением всех разрешающих фишек из его входных позиций и последующим помещением в каждую из его выходных позиций по одной фишке для каждой дуги. Кратные фишки создаются для кратных выходных дуг.

Запуск перехода в целом заменяет маркировку µ сети Петри на новую маркировку µ'. Заметим также, что так как можно запустить только разрешенный переход, то при запуске перехода количество фишек в каждой позиции всегда остается неотрицательным. Запуск перехода никогда не удалит фишку, отсутствующую во входной позиции. Если какая-либо входная позиция перехода не обладает достаточным количеством фишек, то переход не разрешен и не может быть запущен.

Определение 7. Переход t_j в маркированной сети Петри с маркировкой µ может быть запущен всякий раз, когда он разрешен. В результате запуска разрешенного перехода t_j образуется новая маркировка у/, определяемая следующим соотношением:

µ'(p_i) = µ(p_i) - #(p_i,I (t_j)) + #(p_i,O(t_j))

В качестве примера рассмотрим маркированную сеть Петри, изображенную на рис. 2.15. При такой маркировке разрешены только три перехода: г_ь t_z и £₄. Переход t₂ не разрешен, так как ни позиция р₂, ни позиция р₃, являющиеся входами перехода t%, не содержат ни одной фишки. Так как переходы t_u t₃ и t₄ разрешены, любой из них может быть запущен. Если запущен переход t_it то происходит удаление фишки из каждого входа и помещение фишки в каждый выход. При этом одна фишка удаляется из р₅, одна фишка помещается в р₃, а количество фишек в р₄ увеличивается с двух до трех. Новая маркировка, полученная в результате запуска перехода t_iy показана на рис. 2.16.

В маркированной сети Петри, изображенной на рис. 2.16, раз­решены только переходы t_t и t₃. При запуске перехода t_t осуществ­ляется удаление фишки из p_t и помещение фишек в р₂» Рз и р₄ (в р₄ — две фишки, так как эта позиция является кратным выходом перехода t_t). Эта операция образует маркировку, приведенную на Рис. 2.14. Иллюстрация того, как меняется маркировка позиций, когда запу­щен переход tj. Каждая позиция может или не может быть входом либо вы­ходом перехода. Здесь показан случай для кратности 0 или 1.

Рис. 2.15. Маркированная сеть Петри для иллюстрации правил запуска. Переходы h, h и U разрешены.

Рис. 2.16. Маркировка, полученная в результате запуска перехода U в сети на рис. 2.15.

Рис. 2.17. Маркировка, полученная при запуске перехода t\ в сети на рис. 2.16.

Рис. 2.18. Маркировка, полученная при запуске перехода Рис. 2.17. в сети на

Рис. 2.19. Маркированная сеть Петри.рис. 2.17.

В такой маркированной сети Петри переходы t₂ и t₃ раз­решены. Запуск перехода t₃ образует новую маркировку (рис, 2.18), где две фишки удалены из р₄, а одна добавлена в р₅.

Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.