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

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

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

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

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

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

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

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

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

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

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

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

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

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

На рис.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) меток. Это означает, что маркировка μ' непосредственно достижима из маркировки μ. Функционирование сети Петри - последовательная смена меток в результате срабатывания возбужденных переходов.

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

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);