Понятие Сетей Петри.Построение графа

Содержание

1. Сети Петри

1.1. Структура сети Петри.

1.2. Маркировка сетей Петри.

1.3. Правила выполнения  сетей Петри.

1.4. События и условия.

1.5. Одновременность и  конфликт

2. Разработка автоматизированной системы управления торговым предприятием.

2.1. Стоимость проекта АСУП

2.2. Основные функции ERP систем

3. Задание 2

4. Оценка функциональности

Сети Петри

Сети Петри были разработаны  и используются для моделирования  систем, которые содержат взаимодействующие  параллельные компоненты, например аппаратное и программное обеспечение ЭВМ, гибкие производственные системы, а также социальные и биологические системы. Впервые сети Петри предложил Карл Адам Петри в своей докторской диссертации "Связь автоматов" в 1962 году. Работа Петри привлекла внимание группы исследователей, работавших под руководством Дж. Денниса над проектом МАС в Массачусетском Технологическом институте. Эта группа стала источником значительных исследований и публикаций по сетям Петри. Полная оценка и понимание современной теории сетей Петри требуют хорошей подготовки в области математики, формальных языков и автоматов. Современный инженер - системотехник должен иметь квалификацию, необходимую для проведения исследований с помощью сетей Петри.

Структура сети Петри.

Сеть Петри состоит из 4 компонентов, которые и определяют ее структуру:

- множество позиций  Р,

- множество переходов  Т,

- входная функция I,

- выходная функция  О.

Входная и выходная функции  связаны с переходами и позициями. Входная функция I отображает переход t_j в множество позиций I(t_j), называемых входными позициями перехода. Выходная функция О отображает переход t_j в множество позиций О(t_j), называемых выходными позициями перехода.

Маркировка  сетей Петри.

Маркировка m есть присвоение фишек позициям сети Петри. Фишка - это одна из компонент сети Петри (подобно позициям и переходам). Фишки присваиваются позициям. Их количество при выполнении сети может изменяться. Фишки используются для отображения динамики системы.

Маркированная сеть Петри  есть совокупность структуры сети Петри C = (P,T,I,O) и маркировки m и может быть записана в виде M = (P,T,I,O, m). На графе сети Петри фишки изображаются крупными точками в кружке, который представляет позицию сети Петри. Количество фишек (точек) для каждой позиции не ограничено и, следовательно, в целом для сети существует бесконечно много маркировок. Множество всех маркировок сети, имеющей n позиций, является множеством всех n векторов, т.е. Nⁿ. Очевидно, что хотя это множество и бесконечно, но оно счетно. Когда маркировка превышает 4 или 5 фишек, то в кружках удобнее не рисовать фишки, а указывать их количество

Правила выполнения сетей Петри.

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

Переход запускается, если он разрешен. Переход называется разрешенным, если каждая из его входных позиций  имеет число фишек по крайней  мере равное числу дуг из позиции в переход. Фишки во входной позиции, которые разрешают переход, называются его разрешающими фишками. Например, если позиции р1 и р2 служат входами для перехода t1, тогда t1 разрешен, если р1 и р2 имеют хотя бы по одной фишке. Для перехода t3 с входным комплектом {p3,p3,p3} позиция р3 должна иметь не менее 3 фишек для разрешения перехода t3.

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

Переход t3 I(t3) = {p2} и O(t3) = {p3,p4} разрешен каждый раз, когда в р2 будет хотя бы одна фишка. Переход t3 запускается удалением одной фишки из позиции р2 и помещением одной фишки в позицию р3 и р4 (его выходы). Переход t4, в котором I(t4) = {p4,p5} и O(t4) = {p5,p6,p6} запускается удалением по одной фишке из позиций р4 и р5, при этом одна фишка помещается в р5 и две в р6.

События и условия.

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

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

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

Построение моделей  систем в виде сетей Петри связано  со следующими обстоятельствами: 

1. Моделируемые процессы (явления) совершаются в системе, описываемой множеством событий и условий, которые эти события определяют, а также причинно - следственными отношениями, устанавливаемыми на множестве "события - условия". 

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

3. Условия (предикаты) могут быть выполнены или не выполнены. Только выполнение условий обеспечивает возможность наступления событий (предусловия).

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

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

1. заготовка поступила;

2. автомат начинает  обработку;

3. автомат заканчивает  обработку;

4. деталь посылается в накопитель.

Условиями для системы  являются:

1. автомат ждет;

2. заготовка загружена;

3. автомат выполняет  обработку;

4. деталь обработана. 

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

Одновременность и конфликт. 

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

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

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

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

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

Если в какой либо момент времени разрешено более одного перехода, то любой из них может стать “следующим”. Выбор запускаемого перехода осуществляется недетерминированным образом, то есть случайно и зависит от воли моделирующего систему. Недетерминорованность и неодновременность запусков переходов в моделировании паралельной системы показывается двумя способами. В этой ситуации два разрешённых перехода t_j и t_k не влияют друг на друга. В число возможных последовательностей событий входит последовательность, в которой первым срабатывает один переход и последовательность в которой первым срабатывает другой переход. Эти два перехода могут быть запущены в любом порядке, это называется недетерминированностью и неодновременностью, переход t_k может быть запущен в любом порядке, но обязательно при помощи маркеров в обеих позициях. Это называется одновременностью. Другая ситуация, в которой одновременное выполнение затруднено и которая характеризуется невозможностью одновременного запуска. Здесь переходы t_j и t_k находятся в конфликте, так как запуск одного из них удаляет маркёр из p_i и тем самым завершает другой переход. Эта ситуация называется конфликтом и в моделируемых системах отображает борьбу за общие ресурсы.

Разработка  автоматизированной систему управления торговым предприятием.

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

Производственные системы  часто ориентированы на одну или  несколько отраслей и/или типов  производства:  
1)         серийное сборочное (электроника, машиностроение);  
2)         малосерийное и опытное (авиация, тяжелое машиностроение);  
3)         дискретное (металлургия, химия, упаковка);  
4)         непрерывное (нефте- и газодобыча).

Имеют значение также различные  типы организации самого производственного  процесса. Например, для дискретного  производства возможно:

1)         циклическое повторное производство (repetitive manufacturing) — планирование выполняется на определенный срок (квартал, месяц, неделя);  
2)         производство на заказ (make-to-order) — планирование только при поступлении заказа;  
3)         разработка на заказ (engineering-to-order) — самостоятельная разработка каждого нового заказа с последующим производством;  
4)         производство на склад (manufacture-to-stock);  
5)         смешанное производство (mixed mode manufacturing) — для производства конечного продукта используется несколько типов организации производственного процесса.

1)         циклическое повторное производство (repetitive manufacturing) — планирование выполняется на определенный срок (квартал, месяц, неделя);  
2)         производство на заказ (make-to-order) — планирование только при поступлении заказа;  
3)         разработка на заказ (engineering-to-order) — самостоятельная разработка каждого нового заказа с последующим производством;  
4)         производство на склад (manufacture-to-stock);  
5)         смешанное производство (mixed mode manufacturing) — для производства конечного продукта используется несколько типов организации производственного процесса.  
Такая специализация отражается как в наборе функций системы, так и в существовании бизнес моделей данного типа производства. Наличие встроенных моделей для определенных типов производства отличает производственные системы друг от друга.  
Если поставщик придерживается открытой маркетинговой политики, то при демонстрации систем вам будет сказано, на какое производство в первую очередь ориентирована система в мире и какие модули были переведены и локализованы для России.  
Производственные системы по многим параметрам значительно более жесткие, чем финансово-управленческие. Производственное предприятие должно, в первую очередь, работать как хорошо отлаженные часы, где основными механизмами управления являются планирование и оптимальное управление производственным процессом, а не учет количества счетов-фактур за период. Эффект от внедрения производственных систем чувствуется на верхних эшелонах управления предприятием, когда видна вся взаимосвязанная картина работы, включающая планирование, закупки, производство, запасы, продажи, финансовые потоки и многие другие аспекты.  
При увеличении сложности и широты охвата функций предприятия системой, возрастают требования к технической инфраструктуре и компьютерной платформе. Все без исключения производственные системы разработаны с помощью промышленных баз данных. В большинстве случаев используется технология клиент-сервер, которая предполагает разделение обработки данных между выделенным сервером и рабочей станцией. Технология клиент-сервер оправдывает себя при обработке больших объемов данных и запросов, так как позволяет оптимизировать интенсивность передачи данных по компьютерной сети.  
Таблица 1.2  
Внедрение, соотношение затрат и стоимостные оценки.

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

Исходным стандартом, появившимся в 70-х годах, был стандарт MRP (Material Requirements Planning), включавший только планирование материалов для производства /1/.  
Когда ряд американских специалистов в области управления разработали концепцию MRP, было замечено, что существует два типа материалов — с зависимым спросом (для выпуска десяти автомобилей нужно пятьдесят колес — не больше и не меньше — к определенному сроку) и с независимым спросом (типичная ситуация с запасами для торговых предприятий).  
Основная концепция MRP в том, чтобы минимизировать издержки, связанные со складскими запасами (в том числе и на различных участках в производстве). В основе этой концепции лежит следующее понятие — Bill Of Material (BOM — спецификация изделия, за которую отвечает конструкторский отдел), который показывает зависимость спроса на сырье, полуфабрикаты и прочее в зависимости от плана выпуска (бюджета реализации) готовой продукции. При этом очень важную роль играет время. Для того чтобы учитывать время, системе необходимо знать технологию выпуска продукции (или технологическую цепочку, т. е. последовательность операций и их продолжительность). На основании плана выпуска продукции, BOM и технологической цепочки осуществляется расчет потребностей в материалах, привязанный к конкретным срокам.

Однако у MRP есть серьезный  недостаток. Его суть в том, что, рассчитывая  потребность в материалах, мы не учитываем (как минимум) производственные мощности, их загрузку, стоимость рабочей силы и т. д. Поэтому возникла концепция MRP II (Manufacturing Resource Planing — планирование производственных ресурсов). MRP II позволял планировать все производственные ресурсы предприятия (сырье, материалы, оборудование, персонал и т.д.) /1/.  
Впоследствии концепция MRP II развивалась, и к ней постепенно добавлялись возможности по учету остальных затрат предприятия — появилась концепция ERP (Enterprise Resource Planning — Планирование ресурсов предприятия).  
Стандарт ERP позволил объединить все ресурсы предприятия, таким образом, добавляя управление заказами, финансами и т. д.

В соответствии с мировой  практикой, при необходимости более  тонкого анализа нескольких систем одного или близких классов, этапу  выбора придается большое значение. Каждый проект в области автоматизации должен рассматриваться предприятием как стратегическая инвестиция средств, которая должна окупиться за счет улучшения управленческих процессов, повышения эффективности производства, сокращения издержек. В выборе правильного решения должно быть, в первую очередь, заинтересовано руководство предприятия. Данный проект должен ставиться на один уровень с приобретением, например, новой производственной линии или строительством цеха.  
Прежде всего, предприятие должно определить, а что же собственно ожидается от новой системы: какие функциональные области и какие типы производства она должна охватывать, какую техническую платформу использовать, какие отчеты готовить? Проведение такой работы заканчивается составлением документа «Требования к компьютерной системе». Этот документ предназначен, прежде всего, для самого предприятия, так как в нем формализованы и расписаны в соответствии с приоритетами все характеристики новой системы. Он дает объективные критерии для сравнения систем по заранее определенным параметрам.  
Любая из систем — лишь механизм для повышения эффективности управления, принятия правильных стратегических и тактических решений на основе своевременной и достоверной информации, выдаваемой компьютером.

Стоимость проекта АСУП

Автоматизированная  система управления предприятием (АСУП) — комплекс программных, технических, информационных, лингвистических, организационно-технологических средств и действий квалифицированного персонала, предназначенный для решения задач планирования и управления различными видами деятельности предприятия, частный случай автоматизированной системы управления (АСУ).

По различным оценкам, лишь 20-50% проектов по внедрению ERP-систем в РБ можно считать успешными. Дорогостоящие системы известных производителей далеко не всегда гарантируют успех их внедрения. Кроме того, при оценки эффективности внедрения зачастую используются различные экономические модели.

ERP-система-система планирования ресурсов предприятия.

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

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

Основные функции ERP систем:

• ведение конструкторских и технологических спецификаций, определяющих состав производимых изделий, а также материальные ресурсы и операции, необходимые для их изготовления;
• формирование планов продаж и производства;
• планирование потребностей в материалах и комплектующих, сроков и объёмов поставок для выполнения плана производства продукции;
• управление запасами и закупками: ведение договоров, реализация централизованных закупок, обеспечение учёта и оптимизации складских и цеховых запасов;
• планирование производственных мощностей от укрупнённого планирования до использования отдельных станков и оборудования;
• оперативное управление финансами, включая составление финансового плана и осуществление контроля его исполнения, финансовый и управленческий учёт;
• управления проектами, включая планирование этапов и ресурсов

Отличие между ERP-системами  и системами электронного документооборота (СЭД) в том, что, как правило, в ERP документы являются машино-читаемыми, и они не «ведутся», а «проводятся» — уже после того, как они осуществят свой жизненный цикл, то есть были созданы, обсуждены, проверены, согласованы, утверждены и т. д. А СЭД осуществляет поддержку такого жизненного цикла человеко-читаемых документов на предприятии.

Специфичность оценки эффективности  систем класса ERP обусловлена и основными  свойствами, отличающими ERP от систем других классов, в частности:  
1)         универсальность с точки зрения типов производств;  
2)         возможность многозвенного производственного планирования;  
3)         интегрированное планирование ресурсов.  
ERP объединяет все отделы и функции компании в единую информационную среду, в которую интегрировано множество подсистем (модулей) для обслуживания специфических потребностей отдельных подразделений и реализации определенных функций управления, как например, корпоративные финансы, логистика, маркетинг. При оценке эффективности следует учитывать не только сумму эффектов от внедрения ERP в отдельных подразделениях, в конечном итоге за счет синергии общий эффект будет выше.

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

Среди основных рисков проекта  внедрения ИС можно выделить следующие:  
1)         неадекватность функций системы целям и задачам предприятия;  
2)         снижение эффективности предприятия в результате неудачного внедрения ИС, потеря менеджментом инструментов контроля;  
3)         отклонение фактической эффективности внедрения системы от заданной, краткосрочность эффектов;  
4)         риски, связанные с «человеческим фактором»;  
5)         риск перерасхода бюджета проекта, риски упущенной выгоды в результате выбора неверной конфигурации ERP-решения.

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

Номер варианта задания 2 выбирается по предпоследней цифре  студенческого билета.

Вариант 8.

В соответствии с выбранной темой «Разработка модели сети управления торговым предприятием», построим граф возможных состояний и переходов систем (смотрим рисунок 1).

Полученная система  имеет вид соединения «обратная  связь», например, элементы 1 и 15.

Рис. 1 Граф состояний и переходов системы

Составим список работ (обозначенных как элементы системы) в соответствии с выбранной темой.

Ниже приведен список возможных состояний и переходов  между ними:

1. Исследование спроса на продукцию и формирование заказов на выпуск продукции;
2. Закупка расходных материалов;
3. Аренда складов и торговых помещений;
4. Заключение договоров с фирмами поставщиками;
5. Закупка и доставка необходимой продукции;
6. Заключение договоров с потребителями;
7. Расчет основных затрат, снабжение МТО (материально техническое обслуживание (спецодежда, расходные материалы, инструменты и т.д.));
8. Подготовка отчетной документации по объемам выпускаемой продукции;
9. Инвентаризация товара на складах;
10. Составление плана продаж;
11. Подготовка отчетной документации по объемам продаж;
12. Формирование заказа для производственного отдела;
13. Контроль качества производимой продукции;
14. Сбор сведений отделом маркетинга;
15. Создание отчета для финансовой службы.

Оценка функциональности

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

Список литературы