Преподаватель который помогает студентам и школьникам в учёбе.

Моделирование бизнес-процессов при помощи сетей Петри.

Содержание:

Введение

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

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

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

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

О сетях Петри.

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

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

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

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

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

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

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

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

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

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

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

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

Рис. 1. Моделирование простой вычислительной схемы

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

Рис. 2. Номенклатура длительного процесса

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

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

Рис. 1 может быть перерисован в следующем виде:

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

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

Моделирование конечных автоматов

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

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

$Описание: ~M = (Q, \Sigma, \delta, q_0, F)$ ,

где:

Q — конечное множество состояний автомата;
q0 — начальное состояние автомата ( $Описание: q_0 \in Q$ );
F — множество заключительных (или допускающих) состояний, таких что $Описание: F \subseteq Q$ ;
Σ — допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
δ — заданное отображение множества $Описание: Q \times \Sigma$ во множество $Описание: \mathcal {P} (Q)$ подмножеств Q: $Описание: \delta : Q \times \Sigma \rightarrow \mathcal {P} (Q)$ (иногда δ называют функцией переходов автомата).

Так как целью данной работы не является построение конечных автоматов, то подробно мы их описывать не будем. Но скажем, что автоматы часто представляются в виде графов-переходов. А моделирование в рамках сети Петри осуществляется посредством представления алфавитов автомата (входного или выходного) позициями или переходами. Обычно входы представляются позициями. Приведём небольшой пример:

Рис. 4. Граф конечного автомата, вычисляющего дополнение до двух

Рис. 5. Эквивалентная сеть Петри

Но основным применением сетей Петри в данной конкретной работе будет возможность преобразования блок-схемы в сеть Петри. Таким образом, в виде сети Петри можно представить любой готовый алгоритм, который построен на вычислениях и ветвлениях. Рис. 6 иллюстрирует правила перевода:

Рис. 6. Правила перевода блок-схемы в сеть Петри

Параллельные вычисления и синхронизация

Сетями Петри легко моделируется создание и выполнение параллельных ветвей различных вычислительных процессов. К примеру, на рис. 1 изображена одна из довольно популярных на сегодняшний день конструкций fork/join. Переход fork моделирует «разветвление» – создание из одной ветви выполнения двух параллельных ветвей. Это, как правило, реализуется путем создания одной дополнительной ветви вдобавок к существующей. Переход join, в свою очередь, осуществляет «слияние» двух ветвей по завершению их работы – уничтожение созданной параллельной ветви за ненадобностью.

Рис. 7. Пример конструкции fork/join

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

Рис. 8. Барьерная синхронизация процессов

В начале работы сети разрешенными являются три длительных перехода, характеризующих выполнение некоторых подзадач. Три независимых процесса выполняют эти подзадачи, и лишь после их полного завершения становится разрешенным переход-барьер wait(all). После его срабатывания все три процесса снова продолжают свою работу.

Рис. 9. Задача об обедающих философах

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

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

Рис. 10. Другое представление задачи

Одним из довольно простых решений этой проблемы, хотя, конечно, далеко не самым лучшим, является следующее. К сети, изображенной на рис. 10, добавим барьерную синхронизацию после того, как каждый философ осуществит прием пищи по одному разу. Для этого добавим к каждому философу по две позиции – позицию todo, количество фишек в которой отражает количество предстоящих подходов философа к еде до следующего барьера, и позицию done, отражающую количество выполненных подходов. Полученная сеть изображена на рис. 11.

Рис. 11. Решение задачи вместе с барьерном синхронизацией

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

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

Заключение

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

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

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