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

Содержание слайда: ПРОЕКТИРОВАНИЕ АСУ Лекция 6: Формирование выходных документов на отгружаемую продукцию с помощью сетей Петри

Содержание слайда: СОДЕРЖАНИЕ 1. Общие положения и характеристики ординарных сетей Петри 2. Использование сетей Петри для поиска оптимальных стратегий формирования документов 3. Маркировка и динамика сетей Петри

Содержание слайда: Часть 1 Общие положения и характеристики ординарных сетей Петри

Содержание слайда: Определения Ординарные сети Петри – тройка множеств C={P,T,E}, где Р – множество позиций в сети:  │Р│≠ 0. Т – множество переходов:   │Т│≠ 0. Е – отношение инцидентности позиций и переходов т.е. множество дуг сети «С».

Содержание слайда: Пример 1: ординарная сеть Петри Позиции Переходы Дуги

Содержание слайда: САМОСТОЯТЕЛЬНО 1. Граф G(X,U)– это множество вершин X и отношений их инцидентности U. 2. Сеть Петри - результат развития теории графов: C={P,T,E} - это множество позиций Р, множество переходов (планок) Т  и отношений инцидентности позиций и переходов Е. 3. Самостоятельно предложите следующий этап развития теории графов и пример, иллюстрирующий его применение.

Содержание слайда: Часть 2 Использование сетей Петри для поиска оптимальных стратегий формирования документов

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

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

Содержание слайда: Формальная постановка задачи 9z(t1)+8z(t2)+7z(t3)+6z(t4)+5z(t5)+4z(t6)+3z(t7)+2z(t8) min; z(t1)+z(t6)+z(t7)=1; z(t4)+z(t5)+z(t8)=1; z(t2)=1; z(t3)=1; z(t8)z(t7)=0; z(ti)=1,0; i=1,2,3,...,7.

Содержание слайда: Решение задачи переборными алгоритмами Объем перебора булевых переменных равен n1=128. Объем перебора перестановок вершин n2 = 24. Объем перебора перестановок вершин с учетом специфики сети Петри равен n3 = 2.

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

Содержание слайда: Алгоритм Шаг 1. i=1. Шаг 2. Определяется подмножество P’. Шаг 3. Определяется подмножество T’. Шаг 4. Выбор k-го перехода, для которого справедливо: Шаг 5. i = i+1. Шаг 6. Если i>n, то перейти к шагу 7, в противном случае – к шагу 2. Шаг 7. Конец алгоритма.

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

Содержание слайда: Самостоятельно Формализовать и определить с помощью перестановок оптимальный порядок формирования документов с помощью сети Петри вида:

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

Содержание слайда: Часть 3 Маркировка и динамика сетей Петри

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

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

Содержание слайда: Пример 1 Определить динамику сети Петри применительно к задаче поиска оптимальной стратегии формирования документов

Содержание слайда: Начальная позиция выделена красным цветом

Содержание слайда: Расстановка пометок

Содержание слайда: Самостоятельно Определить с помощью расстановки пометок оптимальный порядок формирования документов с помощью сети Петри вида:

Содержание слайда: Самостоятельно Назовите подсистемы АСУ вуз, которые эквивалентны производственным подсистемам: а) формирования портфеля заказов; б) технической подготовки производства; в) управление технологическим процессом; г) формирования документов на отгружаемую продукцию; д) логистика (управление запасами).

Содержание слайда: Самостоятельно 1. Определите порядок проектирования АСУ вуз. 2. Какие требования (ограничения) следует учесть при создании ТЗ АСУ вуз? 3. Каким образом Вы определили бы требования к техническим параметрам используемой аппаратуры? 4. Каким образом Вы определили бы требования к программному обеспечению АСУ ? 5. Как бы Вы сформулировали требования к системе кодирования АСУ вуз?