Содержание к диссертации
Введение
Глава 1. Сети Петри как инструмент динамического моделирования сложных дискретных систем и протекающих в них процессов 15
1.1 Содержательное описание сетей Петри 15
1.2 Формальное описание сетей Петри 18
1.3 Расширения и модификации сетей Петри 20
1.4. Индикаторные сети Петри 29
1.5 Выводы по главе 32
Глава 2. Режимное динамическое моделирование ПС 34
2.1 Многорежимная модель агента 34
2.2 Режимное моделирование многоагентных ПС 38
2.3 Выводы по главе 48
Глава 3. Потоковое динамическое моделирование многоагентных ПС 50
3.1 Общие принципы 50
3.2 Моделирование операций 56
3.2.1 Алгебра потокособытий 56
3.2.2 Пример моделирования на основе обобщенных триадных схем 60
3.2.3 Коррекция управления потоками при нештатных ситуациях ...63
3.2.4 Моделирование детализированной (атрибутированной) триадной схемы 65
3.2.5 Пример матричного дерева 67
3.2.6 Взаимодействие матричного дерева и индикаторной сети 68
3.3 Моделирование процессов 70
3.3.1 Базовая потоковая модель производственной системы 70
3.3.2. Реализация процессов на основе триадных схем 75
3.3.3 Моделирование обобщенных триадных схем 78
3.3.4 Моделирование системы взаимодействующих атрибутированных структурных схем 85
3.3.5 Описание жизненного цикла элементов потока в диаграмме системы взаимодействующих атрибутированных структурных схем 90
3.3.6. Описание внутриоперационных и межоперационных преобразований в диаграмме системы взаимодействующих атрибутированных триадных схем 94
3.4 Конвейерно-временная диаграмма процесса 98
3.5 Выводы по главе 101
Заключение 103
Приложение 104
Акты о внедрении 104
Программные средства поддержки режимного и потокового моделирования
ПС 107
Литература
- Формальное описание сетей Петри
- Индикаторные сети Петри
- Режимное моделирование многоагентных ПС
- Коррекция управления потоками при нештатных ситуациях
Введение к работе
Актуальность проблемы. Важнейшую роль при управлении проектированием и функционированием производственных систем (ПС) играет моделирование, как статическое (моделирование структуры), так и динамическое (моделирование поведения). С помощью инструментальных средств моделирования решаются задачи прогнозирования развития ПС, в том числе: формирования стратегии развития системы в условиях изменения внешней среды; выбора целей ПС с учетом ограничений на потребляемые ресурсы; определения возможных сценариев достижения целей при выбранной стратегии; определения оптимального сценария и т.д.
Решение этих и других задач моделирования позволяет сформировать предварительные ориентиры проекта ПС, выявить и устранить нестыковки и ошибки на возможно более ранних этапах его выполнения. Расширение круга задач моделирования ПС, несомненно, актуально.
В моделировании ПС существует ряд научно-прикладных направлений, в становление и развитие которых внесли вклад многие ученые: российские авторы В.Н. Бурков, А.В.Гордеев, Г.Н. Калянов, Е.К. Корноушенко, В.В. Кульба, О.И. Ларичев, В.И. Максимов, Д.А. Новиков, Э.А. Трахтенгерц, А.Д. Цвиркун, С.А. Юдицкий и др.; зарубежные авторы Г. Буч, А. Джекобсон, К. Мак-Гоуэн, Д. Марка, Г. Минцберг, С. Мэллор, Дж. Питерсон, Д. Рамбо, Ф.С. Роберте, Т. Саати, Г. Саймон, А.В. Шеер, С. Шлеер и др.
В большинстве известных работ акцент сделан на статическое моделирование. Динамическому моделированию уделено значительно меньше внимания. Настоящая диссертация в некоторой степени устраняет этот пробел. В ней исследуется динамическое моделирование ПС на основе математического аппарата сетей Петри: моделирование динамики смены режимов1 работы системы (режимное моделирование) и динамики движения потоков - финансовых, информационных, материальных и т.д., внутри системы и между системой и внешней средой (потоковое моделирование). Оба этих вида моделирования тесно связаны - потоковое моделирование дополняет и развивает знания, полученные при режимном моделировании.
Предметом исследований в работе являются методы динамического моделирования при управлении ПС на основе математического аппарата сетей Петри.
Под режимом понимается образ поведения системы, характеризующий в качественных терминах вид и результаты её деятельности, в том числе динамику факторов, соотнесенных режиму.
ЄОС НАЦИОНАЛЬНАЯ БИБЛИОТЕКА > СПетеИург Л/- ,
ОЭ njfmcjjb ;
— - — ч»
Цель работы заключается в расширении функциональных возможностей динамического моделирования ПС путем исследования дополнительных аспектов поведения системы - динамики режимов и динамики потоков, и создании прозрачных и эффективных структурных методов моделирования, ориентированных на эти аспекты.
В соответствии с поставленной целью в работе решаются следующие задачи:
-
Обзор основных направлений динамического моделирования ПС.
-
Анализ сетей Петри и их расширений и выбор базового инструмента для динамического моделирования ПС.
-
Разработка методов режимного динамического моделирования ПС на уровне автономных структурных компонентов системы - агентов и на уровне межагентных взаимодействий.
-
Разработка обобщенного и детализированного методов потокового динамического моделирования процессов, реализуемых в ПС, на основе интеграции операционных структурных схем и описаний в терминах сетей Петри.
-
Разработка экспериментальной версии программного обеспечения поддержки режимного и потокового моделирования ПС.
Математический аппарат. В работе применялись методы теории сетей Петри и теории графов, теории логических функций, алгебры событий, теории алгоритмов и др.
Научная новизна положений, выносимых на защиту.
-
В качестве изобразительного средства при динамическом моделировании ПС предложена многоцветная (атрибутированная) сеть Петри, нагруженная модификацией булевых функций - индикаторными функциями (индикаторная сеть Петри). Показано, что по своим выразительным возможностям предложенная модель не уступает известным расширениям и модификациям сетей Петри, но является визуально более наглядной.
-
Разработана многорежимная имитационная модель агентов ПС в виде индикаторной сети Петри и процедура определения на ее основе графиков изменения во времени параметров режимов и интегральных показателей агентов.
3. Введены отношения порядка между агентами в многоагентной системе и механизмы, реализующие эти отношения. Предложен метод синтеза многоагентной режимной модели ПС на базе режимных моделей агентов, разработана процедура построения и анализа режимного протокола многоагентной ПС. 4. Предложена базовая потоковая модель процессов, реализуемых в
ПС, развивающая графическую конструкцию в стандарте SADT. Процессы
состоят из целенаправленных действий-операций, взаимодействующих с внешней средой и между собой посредством потоков. Проведена классификация операций по типу вход-выходных потоков (позиционированные и атрибутированные) и по способу преобразования потоков (пассивный и активный).
-
Введена структурная потоковая модель операции процесса, названная триадной схемой. По результатам проведенной классификации операций триадные схемы подразделены на обобщенные ("грубые") и детализированные ("тонкие" или атрибутированные).
-
Разработаны методы структурного описания динамики обобщенных схем (с применением наряду с индикаторными сетями Петри введенной в работе алгебры потокособытий) и динамики детализированных схем (применяются индикаторные сети Петри и графический аппарат "матричных деревьев").
-
Созданы методы синтеза многоагентной потоковой модели, отображающей уровень ПС, на базе обобщенных и детализированных структурных схем с представлением результата анализа синтезированной модели в виде графической конструкции - конвейерно-временной диаграммы.
Достоверность результатов, полученных в работе, подтверждается корректными математическими построениями и проверкой на практических примерах.
Практическая ценность работы определяется созданием эффективной человеко-машинной процедуры режимного и потокового динамического моделирования ПС. Предложенные методы могут применяться на практике, как при создании новых ПС, так и при совершенствовании уже существующих.
Методы режимного динамического моделирования позволяют синхронизировать работу агентов, задавать различную последовательность выполняемых ими режимов работы, оптимизировать загрузку агентов, проводить анализ с помощью режимных протоколов и т.д.
Потоковое динамическое моделирование дает картину движения на заданном временном интервале элементов финансовых, информационных, материальных, энергетических и иных потоков и отражает связи между движением потоков и изменением значений показателей ПС.
Предложенный в работе подход к потоковому моделированию повышает "прозрачность" движения потоков, а также удобен для последующего применения (в ходе реализации проекта создания/реформирования ПС) объектно-ориентированных методов анализа, проектирования и программирования.
На базе предложенной в работе процедуры разработана демо-версия пропзаммного продукта, поддерживающего режимное и потоковое динамическое моделирование. Демо-версия разработана на языке программирования C++.
Реализация и внедрение результатов. Разработанные модели и методы применяются в учебном процессе по специальности 35.14.10 "Прикладная информатика (по областям)" в технических университетах (МФТИ, Новомосковский институт РХТУ им. Менделеева, ТТТУ (г.Тверь), в ЧТУ (г. Чебоксары), в Пензенском военном институте и в других ВУЗах). Методология используется рядом консалтинговых фирм: ХИМИТ (г.Череповец), "Логика бизнеса" (г. Москва) и др.
Апробация работы. Основные научные и практические результаты докладывались на следующих международных и отечественных конференциях и семинарах: Международная конференция по проблемам управления (г. Москва, 2003), Общемосковский семинар «Логическое моделирование» (2004), Семинары лаборатории 32 ИПУ.
Публикации. По результатам выполненных исследований опубликовано 7 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, приложения и списка литературы. Содержание работы составляет 140 страниц, в том числе 40 иллюстраций. Список литературы включает 80 наименований.
Формальное описание сетей Петри
Формально сеть Петри может быть задана пятеркой вида: N = (Р, Т, I, О, Мо). (1.1) где: Р - {pi, р2,..., рп} - конечное множество позиций, п 0, Т - {ti, t2,..., tm} - конечное множество переходов, m 0, Р n Т = 0, I : Р х Т - {0, 1} - прямая функция инцидентности, определяющая входные позиции переходов, I (pi, tj) = 1, если дуга (pi, tj) - существует, I (pi, tj) = 0, если дуга (pi, tj) - не существует, 0:Тх Р- {0, 1}- обратная функция инцидентности, определяющая выходные позиции переходов, О (tj, pi) = 1, если дуга (tj, pi) - существует, 0 (tj, pi) = 0, если дуга (tj, pi) - не существует, Мо : Р - {0, 1, 2,...} - функция начальной маркировки. Для каждого перехода tj можно определить множества его входных и выходных позиций: 1 (tj) = (Pi є Р 11 (Pi tj) = 1} — входные позиции, (1.2) О (tj) = { РІ є Р I О (tj, рО = 1} - выходные позиции, (1.3) где = і,..., n, j = 1,..., m, n = I P I, m = I T . Аналогично можно определить множества входных и выходных переходов для каждой позиции.
В результате срабатывания переходов сети Петри меняется ее маркировка. Для срабатывания перехода tj необходимым и достаточным условием является: VPiei(tj):{M(pi) 0}, (1.4) где М (рі)-разметка позиции р;. Срабатывание перехода tj приводит к изменению маркировки сети М = (М (р]), .... М (рп)) на маркировку М = (М (pi), .... М (рп)) по правилу: М (РІ)=" М(Рі)-\, если (Pi є/(/,))л(д eOitj)) M(Pi)+l, если (Pi eOitj))A(Pi /(/,)) (1.5) M(Pi), если ((д l{tj))A{Pi Щ))М(р, є/(/у))л(я еЩ)))
Таким образом, при срабатывании перехода из его входных позиций убирается, а в выходные позиции добавляется по одной фишке.
Если в сети одновременно возбуждено несколько переходов, то порядок их срабатывания не определен и, следовательно, может существовать несколько последовательностей срабатывания переходов. Это является следствием того, что активизация возбужденного перехода в сетях Петри может произойти через любой конечный промежуток времени после его возбуждения. Срабатывание перехода считается неделимым актом, т.е. предполагается, что изъятие маркеров из всех входных позиций перехода и их перемещение в выходные позиции осуществляется мгновенно, с нулевой задержкой.
Таким образом, обычные (канонические) сети Петри не отражают временных параметров моделируемой системы, что является существенным ограничением при их использовании в качестве инструмента моделирования. Для снятия ограничения были предложены разнообразные расширения сетей Петри.
Стремление расширить применимость аппарата сетей Петри для моделирования различных дискретных систем привело к появлению большого числа их различных расширений и модификаций, ориентированных на моделирование сложных систем с учетом таких факторов как приоритетность процессов (приоритетные сети, сети с инверсными дугами), временные параметры событий (временные сети, сети Мерлина), стохастичность системы (стохастические сети), необходимость совместного отображения структуры управления и потоков данных (раскрашенные сети, Е-сети, F-сети, комби-сети) и многие другие. Модификации сетей Петри предлагались в первую очередь для того, чтобы более адекватно и удобно выражать в терминах сетей особенности функционирования реальных дискретных систем, поскольку моделирующие возможности сетей Петри ограничены, в отличие, например, от машины Тьюринга, с их помощью могут быть представлены далеко не все системы [Котов, 1984]. В основном эти расширения связаны с изменением правил срабатывания переходов. Можно выделить следующие принципы расширения [Гордеев, 1993]:
Индикаторные сети Петри
В работе вводится новое, эффективное по своим выразительным и аналитическим возможностям расширение сетей Петри: индикаторные сети. Модель представляет собой каноническую (или эквивалентную ей атрибутированную) сеть Петри, переходам которых дополнительно приписаны так называемые индикаторные булевы формулы. Индикатором сравнения названо выражение х=(р#а), где хє{0,1}, р 0 -целочисленная переменная, а - числовая переменная или константа, # - один из знаков бинарного отношения =, Ф, , , , , J 1, если выполняется #, х= 0, если иначе.
Индикаторной булевой формулой (ИБФ) названо выражение, полученное путем применения конечное число раз к индикаторам сравнения логических операций конъюнкции (Л), дизъюнкции (v), отрицания (-і).
Выразительность индикаторных сетей достигается благодаря выделению взаимосвязанных сетевой и алгебраической части описания единого процесса, возможности раздельного упрощения той и другой части, применению однообразных стандартных правил функционирования канонических сетей Петри (по сравнению с другими расширениями сетей Петри).
Примеры представления индикаторными сетями расширений сетей Петри, динамика которых определяется локальными действиями (срабатываниями переходов), даны в табл. 1.3.
При аналитическом исследовании индикаторной сети вначале проверяется корректность положенной в её основу канонической (атрибутированной) сети Петри, а затем согласование с ИБФ, приписанными её переходам. При этом, в частности, ИБФ не должны быть нулевыми константами.
Дано содержательное описание сетей Петри как формального аппарата, позволяющего моделировать асинхронность и параллелизм независимых событий, параллелизм конвейерного типа, сложные формы синхронизации и конфликтные взаимодействия между процессами.
Дано формальное описание сетей Петри в виде совокупности множеств позиций и переходов, функций инцидентности и вектора начальных маркировок. Изложены правила срабатывания переходов.
Рассмотрены расширения и модификации сетей Петри, позволяющие увеличить их моделирующую мощность по сравнению с каноническими сетями Петри. Большинство этих модификаций по моделирующей мощности эквивалентно машине Тьюринга, а отличия между ними состоят в удобстве моделирования той или иной предметной области.
Введено новое расширение сетей Петри: индикаторные сети. Данная модель представляет собой каноническую сеть Петри, переходам которой дополнительно приписаны так называемые индикаторные булевы формулы. Индикаторная сеть путем представления сетями Петри, в общем случае ингибиторными, функций, приписанных переходам, всегда может быть преобразована в ингибиторную сеть Петри. Последняя как известно, по своей моделирующей мощности равносильна машине Тьюринга. Следовательно, проблема распознавания аномалий (живость, безопасность и т.д.) в индикаторной сети Петри в общем случае алгоритмически неразрешима. Необходимое условие алгоритмической разрешимости заключается в отсутствии в функциях, приписанных переходам, индикаторов (переменная равна нулю).
Индикаторная сеть обладает рядом преимуществ по сравнению с остальными расширениями: возможность раздельного анализа базовой канонической сети Петри и индикаторных функций, что упрощает процедуру проверки корректности модели. обладает хорошей наглядностью и удобством в применении для моделирования динамики сложных систем.
Режимное моделирование многоагентных ПС
При функционировании многоагентной ПС режимы разных агентов выполняются либо независимо друг от друга, либо с учетом межрежимных связей, выражаемых бинарными отношениями. Эти отношения можно разбить на две основные группы - синхронизация переходов и отношение порядка при запуске различных режимов. Отношения первой группы базируются на понятии «синхросвязка». Синхросвязкой будем называть набор переходов, принадлежащих разным агентам, на который наложено дополнительное ограничение: все переходы набора срабатывают одновременно, и только одновременно, при этом каждый переход входит только в одну синхросвязку. Так как переходы режимных индикаторных сетей агентов нагружены логическими условиями, то для их объединения в синхросвязку необходимо, чтобы конъюнкция этих условий была истинной при некоторых значениях предметных переменных агентов. В противном случае синхросвязка никогда не сможет быть запущена.
Синхросвязку Sj , j=l,...,m, переходов tu,..., tj.n обозначим через Sj={ /V --- (і п } Пример синхросвязки Sj={/,+f , І2л } Для фрагментов режимных индикаторных сетей агентов дан на рис. 2.3. В данном случае синхронизируется начало выполнения режима г и с завершением выполнения режима Г2.1 Г2.І )
Пример синхросвязки переходов. Рассмотрим некоторые примеры применения синхросвязок: синхросвязка sa={/,+;Ve, t+2s{) - синхронизация начала работы в определенных режимах разными агентами; синхросвязка sb= { ," [ , Q) - синхронизация завершения работы в определенных режимах разными агентами; синхросвязка sc={/,+,v% Q} - синхронизация завершения работы в определенном режиме одного агента и начала работы в определенном режиме другого агента (контрсинхронизация); набор синхросвязок Sd={/,+iv, t }, sc={/,";, , Q) - синхронизация начала и завершения работы в определенных режимах разными агентами; набор синхросвязок sf={/u/, /2Т ) Sg l uS 12л) " синхронизация начала (завершения) работы в одном и завершения (начала) работы в другом агенте в определенных режимах (полная контрсинхронизация); набор синхросвязок sh={tf, Q}, Si={/,7, / }, sm={/27, /3" } синхронизация завершения выполнения работы в первом и начала выполнения работы во втором агенте в определенных режимах, завершения выполнения работы во втором и начала выполнения работы в третьем агенте в определенных режимах и т.д., а также синхронизация начала выполнения работы в первом агенте и завершения выполнения работы в последнем агенте в определенных режимах (циклическая смена). Циклическая смена является обобщением полной контрсинхронизации для трех и более агентов. По второй группе выделим следующие отношения между режимами, в которых могут работать два разных агента: несовместимость режимов - один режим исключает другую; последовательно-циклическое выполнение запусков двух режимов; доминирование числа повторений одного режима над числом повторений другого; временная задержка запуска режима относительно запуска другого режима. последовательно-циклическая работа в одном режиме с периодичностью к относительно работы в другом режиме. Отношения второй группы реализуются путем введения «буферных» позиций между индикаторными сетями различных агентов.
Проиллюстрируем вышесказанное на примерах.
На рис. 2.4 представлена индикаторная сеть Петри, реализующая отношение несовместимости режимов г 1.1 и r2.i, содержащая «буферную» позицию Ь. В начальной маркировке маркеры находятся в позициях ri.0, Гг.о, Ь, и активизированы переходы /,+,, /2+і запускающие соответственно режимы Г.ь
Г2.1- Тот из активизированных переходов, который срабатывает первым, изымает маркеры из позиции для «пустого» режима и позиции b и вносит маркер в соответствующую режимную позицию, тем самым, блокируя срабатывание второго перехода. Далее срабатывает переход, завершающий выполнение работы в выбранном режиме, маркер изымается из режимной позиции и вводится в позицию b и в начальную позицию. После этого может сработать другой активизированный переход, запускающий второй режим. Гі.О Ь2 Г2.0
Последовательно-циклическое выполнение запусков двух режимов.
На рис. 2.5 дана индикаторная сеть Петри, реализующая последовательно-циклический запуск режимов г , гг.ь содержащая «буферные» позиции Ь], Ьг. В начальной маркировке маркеры находятся в позициях Г).о, r2.o, Ь2, и активизирован только переход tj.i.i. При срабатывании этого перехода маркеры удаляются из позиций п.о, b2 и вносятся в позиции Гц, Ъ\. При этом активизируется переход t2.i.i переводящий маркеры из позиций r2.o, bi в позиции Г2.і, Ь2. Таким образом, запуск режима Г2.1 осуществляется после режима Ги. В маркировке, характеризуемой наличием маркеров в позициях rlti, Г2.1, Ьг активизированы переходы ti.1.2» 2.1.2- Оба эти перехода срабатывают в любой последовательности и возвращают сеть в начальную маркировку. Аналогично (введением двух дополнительных «буферных» позиций Ьз, Ьд) срабатывание переходов tu.2, t2.i.2, завершающих выполнение соответственно режимов Гц, г2.ь может быть упорядочено.
Коррекция управления потоками при нештатных ситуациях
Блок коррекции управления фиксирует нештатные ситуации в потоковой сети и для исправления ситуации вносит изменения в индикаторную сеть - корректирует индикаторные функции, приписанные его переходам, или/и конфигурацию сети.
В качестве примера проиллюстрируем коррекцию управления поточной конвейерной линией [Юдицкий и Радченко, 2003], упрощенная индикаторная сеть которой дана на рис. 3.6. Линия представляет собой шаговый конвейер, вдоль которого размещены обрабатывающие станки. При штатной работе линии все станки параллельно выполняют цикл обработки изделия, находящегося в зоне данного станка, после чего конвейер перемещает изделия на шаг (в зону следующего станка), и цикл повторяется.
Операция г/, соответствует исходному состоянию линии и запускает таймер г, отсчитывающий продолжительность ее функционирования при фиксированном критическом времени рабочего цикла станков тк. По условию г 0 инициируется операция и2, которая запускает этот цикл. Если время рабочего цикла трц не превышает критического значения (трц тк),то вслед за и2 следует операция иу - шаг конвейера; если превышает (трч тк), то операция и4 - прерывание работы линии и вычисление индекса интенсивности прерываний G, зависящего от величины тк. Зависимость G = f(rk) имеет качественный характер и выражается следующим образом: чем больше величина тк, тем более вероятно выполнение условия гст гА (инициирующего переход г3 на графе управления), чем условия гm тк (инициирующего переход г,). Другими словами, при увеличении тк возрастает вероятность непрерывной работы поточной линии, а при уменьшении тк возрастает вероятность прерываний.
Величина G вычисляется (операцией ил) по формуле G = N/TM, где N -суммарное число прерываний за время моделирования тм. Если G G„, где G„ - нормативное значение индекса, то по завершении операции срабатывает переход г5, и возобновляется штатная работа линии с операции щ. Если G G„, то срабатывает переход г6, и после м4 запускается операция и5, осуществляющая коррекцию величины тк критического времени рабочего цикла линии, а также сброс таймера г. По показанию таймера г = 0 индикаторная сеть переходом Yj переводится в исходное состояние (операция щ).
Таким образом, нештатная ситуация при работе линии, проявляющаяся в превышении интенсивностью прерываний установленных норм, устраняется подбором значения переменной хк в составе индикаторных функций, приписанных переходам г2,г3 графа управления. Операция и5 определяет минимальное значение критического времени х\ , при котором выполняется условие G GU, на основе следующего алгоритма: 1. Задатьначальное значение т кшч. 2. При первом прерывании проверить условие G G„. 3. Если условие выполняется, то проверить не завышено ли значение г , т.е. можно ли его уменьшить. Для этого полагаем тк =т кшч-\ и продолжаем моделирование работы линии. Если за установленное время не произойдет прерывания, то принимаем гк"" = т кшч-\, в противном случае повторяем шаг 3. 4. Если на шаге 2 G G„, то выполняем присваивание тк = х"кач +1 и возобновляем моделирование. При выполнении условия G G„ и отсутствии прерываний (за установленное время) принимаем т к "" - Т Г +! » ПРИ возникновении прерывания повторяем шаг 4 до тех пор, пока не будет найдено искомое гк"".
При моделировании детализированной триадной схемы производится структурирование (атрибутирование) ее внешних и внутренних потоков: каждому потоку приписывается фиксированный набор переменных-атрибутов, среди которых выделяется ключевой атрибут - идентификатор (имя) элемента потока. Каждый ЭП, поступающий в триадную схему, характеризуется своим уникальным именем и определенными начальными значениями атрибутов. В процессе обработки в схеме ЭП проходит через несколько последовательных стадий (состояний), которые определяются как приобретение элементами некоторых новых свойств.
