Презентация на тему Формирование выходных документов на отгружаемую продукцию с помощью сетей Петри

Использование сетей Петри для поиска оптимальных стратегий формирования документов
3.

Маркировка и динамика сетей Петри

Р – множество позиций в сети:
 │Р│≠ 0. Т –

множество переходов:
  │Т│≠ 0.
Е – отношение инцидентности позиций и переходов т.е. множество дуг сети «С».

кружками, переходы – барьерами(планками), отношения – стрелками (дугами)

отношений их инцидентности U.
2. Сеть Петри - результат развития

теории графов: C={P,T,E} - это множество позиций Р, множество переходов (планок) Т  и отношений инцидентности позиций и переходов Е.
3. Самостоятельно предложите следующий этап развития теории графов и пример, иллюстрирующий его применение.

формирования документов

Содержательная постановка задачи:
 
Задано множество документов, которые нужно формировать на

основе базы данных и множества программных единиц, которые могут это делать. Каждая единица характеризуется временем и объемом памяти. Каждый документ характеризуется объемом используемой памяти. Требуется построить такую стратегию формирования документов, которая бы:
Минимизировала время формирования выходных документов.
Удовлетворяло ограничениям на объем используемой памяти.

i-ой
программной
единицы задается

формулой:
τ(ti)=10-i, i=1,2,.. 7.
База данных.
Переход t5 может
сработать, только
если документы 1
и 2 уже сформированы.

z(ti)=1,0; i=1,2,3,...,7.

n1=128.
Объем перебора перестановок вершин n2 = 24.
Объем перебора перестановок

вершин с учетом специфики сети Петри равен n3 = 2.

(│ P’ │= i).
Выбирается k-й переход такой, что:

исходящая из него дуга заходит в позицию, стоящую на (i+1)-м месте в перестановке π;
В планку k-го перехода заходят дуги подмножества переходов Т’, в которые заходят только дуги, исходящие из позиций подмножества Р’.

Определяется подмножество T’.
Шаг 4. Выбор k-го перехода, для которого

справедливо:
Шаг 5. i = i+1.
Шаг 6. Если i>n, то перейти к шагу 7, в противном случае – к шагу 2.
Шаг 7. Конец алгоритма.

4. Тогда для формирования документа, отвечающего
позиции 1,

выбирается t2, для формирования документа, отвечающего
позиции 2, выбирается t3,
позиции 3 отвечает t6, а
позиции 4 отвечает t8. Т.о.
суммарное время форми-
рования всех документов
равно 21. Перебрав все
перестановки, получим
оптимальную стратегию
формирования документов.

формирования документов с помощью сети Петри вида:

4


2


3


1


0

t1

t2

t3
t4

t5 t6

t7
τ(ti)= 8 – i, i=1,2,…,7.

когда документы формируются с использованием распределенной базы данных?
Как учесть

в формальной постановке задачи случай, когда в сети Петри существуют контуры?

или значений. Представляется в виде вектора Mj
Динамика сети Петри

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

Динамика ординарных сетей Петри.

входных позициях которого – 1.
Срабатывание перехода может наступить через

любой конечный промежуток времени, после его возбуждения.
Если в каком то состоянии сети Петри возбужденными оказываются несколько переходов, то выполняется только один (любой) из них.
В результате срабатывания перехода, метка меняется в каждой входной его позиции - она уменьшается на 1, а метки во всех его выходных позициях увеличивается на 1.
Выделение перехода – неделимый процесс изменения разметки выполняется мгновенно.
 

Приняты следующие правила:

поиска оптимальной стратегии формирования документов

В) С)








D) E)

Порядок расстановки пометок определяет оптимальную стратегию формирования документов

порядок формирования документов с помощью сети Петри вида:

4


2


3


1


0

t1

t2

t3
t4

t5 t6

t7
τ(ti)= 8 – i, i=1,2,…,7.

формирования портфеля заказов;
б) технической подготовки производства;
в) управление технологическим процессом;
г)

формирования документов на отгружаемую продукцию;
д) логистика (управление запасами).