При построении сокращенного графа достижимости сети Петри позиция pmacro используется следующим образом. Если начальная маркировка Мо такова, что М[O]i = 1 для всех i = n+1,
n+2,...,n+k, то позиции pmarco присваивается фишка в начальной маркировке. Если в процессе построения сокращенного графа достижимости вес вершины графа w(vj) включает в себя вершину
pmarco, вместо этой вершины вписывается множество {pn+1,
pn+2,...,pn+k}.
Наличие какого-либо собственного подмножества моделей из указанного множества на решение задач проектирования не оказывает никакого влияния, кроме использования ресурсов памяти.
2. Образование макровершин: "макропереходов". Если в рассматриваемой сети Петри (рис. 3.1. б) существует пара переходов ti и tj такие, что входные и выходные функции этой пары удовлетворяют условиям:
O(ti) = I(tj), то эту пару можно объединить, "склеив" два перехода в один tmacro. Вновь найденный переход будет соответствовать последовательному запуску переходов ti, a затем
tj. Входные и выходные функции tmacro удовлетворяют условиям:
I(tmacro) = I(ti); O(tmacro) = O(tj).
При построении сокращенного графа достижимости сети Петри переход tmacro работает следующим образом. Если в графе появляется дуга с весом w(uj), содержащим переход tmacro, то эта дуга удаляется и вводится вместо нее цепочка и дуга Up, вершина
Vp и дуга Up+1 со следующими весами
w(up) = tiUw(uj) \ tmacro w(up+1) = tjUw(uj) \tmacro
вес вершины vp получается добавлением к весу инцедентной дуге up
вершины vp-1 позиции pn: w(vp) = w(vp-1)U{pn}.
Если в начальной маркировке Мо M[O]n = 0, то в сокращенном графе достижимости к весу вершин, смежных vo дописывается вес
I(tj) = I(tmacro):
w'(vj) = w(vj)UI(tmacro), a дугам, исходящим из vo вес tj:
w'(uj) = w(uj)U tj
3. Удаление транзитивных замыканий из сети (рис. 3.1. в).
Переход t3 не сработает до тех пор, пока не получена модель р2.
В этом случае модели р1 и р2 преобразуются соответственно к виду р1'= p1Up3={p1,p3} и p2'=p2Up3={p2,p3}
I'(t1)=I(t1); I'(t2)={p1'}={p1,p3}; I'(t3)={p2,p3};
O'(t1)={p1'}={p1,p3};O'(t2)={p2'}={p2,p3}; O'(t3)=O(t3).
При построении сокращенного графа достижимости в этом случае все веса вершин w(vi) такие, что p1' w(vi) или p2' w(vi)
будут переписаны следующим образом:
w'(vi)={p1,p3}Uw(vi) \ p1', либо
w'(vi)={p2,p3}Uw(vi) \ p2' соответственно.
После выполнения первого шага упрощения (получения
"макропозиций"), следующие два шага упрощения повторяются циклически до тех пор, пока они выполнимы. По упрощенной сети
Петри строится сокращенный граф достижимости в соответствии с приведенным алгоритмом, по заданному множеству начальных маркировок Мn={Mn1,Mn2,...,Mnk}. При этом, в соответствии с изложенными правилами преобразования макровершин к исходным обозначениям, следует преобразовывать вершины, имеющие ненулевую начальную маркировку. Преобразования всех остальных макровершин
(макропозиций и макропереходов) имеет смысл выполнять только после проведения операции объединения сокращенных графов достижимости и получения сокращенного графа достижимости системы.
3.2. Алгоритм метода "обратной волны".
Для удаления "паразитных" модулей и моделей, которые не требуется использовать для достижения целей проектирования, разработан алгоритм метода "обратной волны".
В результате работы алгоритма планирования на сокращенном графе достижимости получается в общем случае l решений задачи планирования. Решение имеет вид:
.................
Вообще говоря не обязательно ; для .
Важным является выполнение условия включения множества выходных позиций Mt в вес вершин , i = 1,2,...,k. Mt также является элементом множества достижимости R(C,Mo), где С - сеть
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.