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

Сети Петри - математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году.

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

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

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

В другом подходе весь процесс проектирования и определения характеристик проводится в терминах сетей Петри. В этом случае задача заключается в преобразовании представления сети Петри в реальную информационную систему.

Несомненным достоинством сетей Петри является математически строгое описание модели. Это позволяет проводить их анализ с помощью современной вычислительной техники (в том числе с массово-параллельной архитектурой).

В работе приведены результаты исследований, направленных на разработку программно-аппаратного комплекса моделирования сетей Петри, который:

позволяет моделировать простые и цветные (CPN) сети Петри;

позволяет моделировать сети Петри со сложной структурой (включением подсетей-блоков в основную сеть) и большим количеством мест и переходов;

позволяет исследовать сети Петри на ограниченность (безопасность), наличие тупиков и достижимость разметок;

предоставляет удобный интерфейс пользователю.

Ни один из существующих программных комплексов моделирования сетей Петри не удовлетворяет этим требованиям.

Разработана система имитационного моделирования сетей Петри в трехуровневой архитектуре клиент-сервер. В основу системы было положено объектно-ориентированное описание сетей Петри в UML-нотации (Unified Modeling Language). Система реализована с помощью CASE-технологии DoomXL, разработанной в ЦОС и ВТ МФТИ. Применение современной промышленной СУБД Informix US в качестве серверной части системы позволяет:

хранить большие массивы данных по структуре сетей Петри;

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

Кроме того, примененный объектно-ориентированный подход позволяет реализовать модели сетей Петри со сложной структурой.

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

Сети Петри - инструмент исследования систем. В настоящее время сети Петри применяются в основном в моделировании. Во многих областях исследований явление изучается не непосредственно, а косвенно, через модель. Модель - это представление, как правило, в математических терминах того, что считается наиболее характерным в изучаемом объекте или системе. Манипулируя моделью системы, можно получить новые знания о ней, избегая опасности, дороговизну или неудобства анализа самой реальной системы. Обычно модели имеют математическую основу.

Развитие теории сетей Петри проводилось по двум направлениям. Формальная теория сетей Петри занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Прикладная теория сетей Петри связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы.

Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояние предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнения событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако, такой анализ не дает числовых характеристик, определяющих состояние системы. Развитие теории сетей Петри привело к появлению, так называемых, “цветных” сетей Петри. Понятие цветности в них тесно связано с понятиями переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Несмотря на некоторые сходства между цветными сетями Петри и программами, они еще не применялись в качестве языка программирования.

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

Сетевое планирование

Сетевое планирование - метод управления, основанный на использовании математического аппарата теории графов и системного подхода для отображения и алгоритмизации комплексов взаимосвязанных работ, действий или мероприятий для достижения четко поставленной цели. Разработаны в начале 50-х г. ХХ в.

Наиболее известны практически одновременно и независимо разработанные метод критического пути - МКП и метод оценки и пересмотра планов - PERT.

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

Основная цель сетевого планирования - сокращение до минимума продолжительности проекта.

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

Наиболее распространенными направлениями применения сетевого планирования являются:

целевые научно-исследовательские и проектно-конструкторские разработки сложных объектов, машин и установок, в создании которых принимают участие многие предприятия и организации;

планирование и управление основной деятельностью разрабатывающих организаций;

планирование комплекса работ по подготовке и освоению производства новых видов промышленной продукции;

строительство и монтаж объектов промышленного, культурно-бытового и жилищного назначения;

реконструкция и ремонт действующих промышленных и других объектов;

планирование подготовки и переподготовки кадров, проверка исполнения принятых решений, организация комплексной проверки деятельности предприятий, объединений, строительно-монтажных организаций и учреждений.

Использование методов сетевого планирования способствует сокращению сроков создания новых объектов на 15-20%, обеспечению рационального использования трудовых ресурсов и техники.

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

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

Математические модели с использованием сетей Петри

Сети Петри являются эффективным инструментом дискретных процессов, в частности, функционирования станочных систем. Их особенность заключается в возможности отображения параллелизма, асинхронности и иерархичности.

На рис.1 приводится пример сети Петри, где Р - конечное непустое множество позиций (состояний); Т - конечное непустое множество переходов (событий), причем p P и t_i T; F: Р x Т - {0, 1, 2,... }; Н: Т x Р {0, 1, 2,... } - функции входных и выходных инциденций; μ₀ : Р {0, 1, 2,... } - начальная маркировка. Вершины сети p P изображены кружками, а вершины t_i T - черточками (баркерами). Дуги соответствуют функциям инцидентности позиций и переходов. Точки в кружочках означают заданную начальную маркировку. Число маркеров в позиции равно значению функции μ: Р {0, 1, 2,... }. Переход от одной маркировки к другой осуществляется срабатыванием переходов. Переход t может сработать при маркировке μ, если он является возбужденным:

Рис.1. Сеть Петри

Данное условие показывает, что в каждой входной позиции перехода t число маркеров не меньше веса дуги, соединяющей эту позицию с переходом. В результате срабатывания перехода t, удовлетворяющего условию (1), маркировку μ заменяют маркировкой μ' по следующему правилу:

По этому правилу в результате срабатывания из всех входных позиций перехода t изымается F (p,t) маркеров и в каждую выходную позицию добавляется H (t,p) маркеров. Это означает, что маркировка μ' непосредственно достижима из маркировки μ. Функционирование сети Петри - последовательная смена маркировок в результате срабатывания возбужденных переходов.

Состояние сети в данный момент времени определяется ее текущей маркировкой. Важная характеристика сети Петри - граф достижимости, с помощью которого описываются возможные варианты функционирования сети. Такой граф имеет вершины, которые являются возможными маркировками. Маркировки μ и μ' соединяются в направлении t дугой, помеченной символами перехода t T или μ^t μ'. Маркировка μ' такая последовательность переходов: τ = t₁ , t₂ ,..., t_k является достижимой из маркировки μ, если существует, что μ^t1 μ'^t2 ... μ ^tk μ.

N = (Р, Т, F, Н, μ₀), где Р = {Р₁, Р₂, Р₃, Р₄, Р₅},

T = {t₁, t₂, t₃, t₄, t₅}, μ₀ = (1, 1, 0, 0, 0).

Функции F и Н заданы матрицами

Фрагмент графа достижимости для сети Петри приведен на рис. 2

рис. 2

Список используемой литературы

1. <http://revolution. /mathematics/00003923_0.html> (ноябрь, 2008);
2. <http://orion.netlab. cctpu.edu.ru/TPU/soft/10. htm> (декабрь, 2008);
3. <http://www.miracle.ru/pub/512/512. htm> (декабрь, 2008);
4. <http://orion.netlab. cctpu.edu.ru/TPU/soft/10. htm> (октябрь, 2008);
5. <http://www.netspetri. h17.ru/theor.html> (октябрь, 2008);
6. <http://mathmod. narod.ru/> (октябрь, 2008);
7. <http://matlab. exponenta.ru/ml/book1/matlab/index_book. php> (октябрь, 2008);
8. <http://www.rgc. Su/material/998/0/index. shtml > (декабрь, 2008);