Министерство образования и науки Российской федерации
Государственное образовательное учреждение высшего

профессионального образования

«Нижегородский государственный университет им. Н.И.Лобачевского»

Факультет вычислительной математики и кибернетики

Кафедра информатики и автоматизации научных исследований

Н.Н.Чернышова

Имитационное моделирование бизнес - процессов
Учебно – методическое пособие

Рекомендовано методической комиссией факультета вычислительной математики и кибернетики для студентов ННГУ, обучающихся по направлению подготовки 080800 «Прикладная информатика (в информационной сфере)»

Нижний Новгород

2010

УДК 519.8

Н.Н.Чернышова Имитационное моделирование бизнес - процесов :Учебно – методическое пособие. - Нижний Новгород: Издательство Нижегородского государственного университета, 2010. – 28с.

Рецензент : кандидат физ.-мат. наук, доцент А.В.Баркалов

Материал предназначен для студентов, обучающихся по направлению подготовки 080800 «Прикладная информатика (в информационной сфере)» факультета ВМК ННГУ как пособие при изучении аппарата сетей Петри и языка имитационного моделирования GPSS.

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

УДК 519.8

Нижегородский государственный университет имени Н.И.Лобачевского

2010 г.

Часть 1. Подходы к имитационному моделированию бизнес-процессов

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

Традиционно различают аналитическое и имитационное моделирование.

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

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

В имитационном моделировании сформировались и наиболее часто применяются три основных подхода — дискретно-событийное моделирование, системная динамика и агентное моделирование [1].

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

Дискретно-событийное моделирование

Дискретно-событийное моделирование обязано своим рождением Дж. Гордону, который в начале 1960-х спроектировал и реализовал на мэйнфреймах¹ IBM систему GPSS. Основной объект в этой системе — пассивный транзакт (заявка на обслуживание), который может определенным образом представлять собой работников, детали, сырье, документы, сигналы и т. п. «Перемещаясь» по модели, транзакты становятся в очереди к одноканальным и многоканальным устройствам, захватывают и освобождают эти устройства, расщепляются, уничтожаются и т. д. Таким образом, дискретно-событийную модель можно рассматривать как глобальную схему обслуживания заявок. Аналитические результаты для большого количества частных случаев таких моделей рассматриваются в теории массового обслуживания.

Сегодня существует целый ряд инструментов, поддерживающих такой подход в моделировании: GPSS/PC, GPSS/H, GPSS World, Object GPSS, Arena, SimProcess, Enterprise Dynamics, Auto-Mod и др.

GPSS World — типичный современный представитель GPSS-семейства, реализованный для работы в среде MS Windows. Наличие встроенных инструментов статистической обработки результатов моделирования, встроенного языка программирования расчетов PLUS и др. позволяет создавать средствами GPSS World не только простые обучающие модели, но и более полезные приложения.

Несмотря на изначальную ориентацию GPSS на моделирование систем массового обслуживания, система оказалась удивительно долгоживущей и способной к развитию. Трудоемкость описания моделируемых систем в терминах бизнес-процессов может быть снижена за счет применения таких продуктов, как Object GPSS или ISS 2000 (пакет ISS 2000 представляет собой лингвистический процессор, с помощью которого пользователь в диалоговом режиме создает автоматически GPSS-программу и запускает ее на выполнение).

Системная динамика

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

Методы системной динамики поддерживаются такими инструментами, как DYNAMO, Stella, Vensim, PowerSim, iThink, ModelMaker и др.

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

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

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

Агентное моделирование

Агентное моделирование предполагает работу с децентрализованной моделью. В такой модели нет единой точки, определяющей поведение системы в целом. Агентная модель состоит из множества индивидуальных объектов (агентов) и их окружения. Поведение системы описывается на индивидуальном уровне; глобальное поведение рассматривается как результат совокупной деятельности агентов, каждый из которых действует сообразно собственному «уставу», существует в общей среде, взаимодействует со средой и другими агентами. Для описания поведения агентов используются карты состояний, являющиеся стандартным инструментом UML.

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

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

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

Другие подходы

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

Существуют и узкоспециализированные методологии, предназначенные исключительно для моделирования и анализа бизнес-процессов, например, ARIS (Architecture of Integrated Information Systems). Организация в ARIS рассматривается с четырех точек зрения: организационной структуры, функциональной структуры, структуры данных, структуры процессов. Для описания бизнес-процессов предлагается около 80 типов моделей, каждая из которых отражает тот или иной аспект моделирования. Развитая репрезентативная графика делает модели в ARIS особенно удобными для представления руководству и принятия стратегических решений.

ARIS хорошо стыкуется с известными ERP-системами², в частности, позволяет описать структуру SAP R/3 в терминах управления бизнес-процессами и провести реинжиниринг (импортировав в ARIS текущие описания бизнес-процессов из R/3). Есть возможность проверки создаваемых моделей на соответствие методологии SAP и тестирования проекта на соответствие требованиям стандарта качества ISO 9000.

Как показывает практика, внедрению ARIS должна предшествовать серьезная «безмашинная» проектно-аналитическая подготовка. Обычно ARIS используется либо для формирования бизнес-структуры с самого начала, либо для ее крупномасштабной комплексной перестройки. Методики оптимизации, предлагаемые ARIS, представляют собой только первичный этап оптимизации бизнес-процессов (т. к. стандартные алгоритмы анализа могут быть реализованы и без использования ARIS, а более сложные алгоритмы могут быть воплощены с помощью сервисной надстройки «Поиск решения» в MS Excel).

Успешность применения ARIS сильно зависит от наличия профессиональных бизнес-аналитиков и высокой управленческой культуры на предприятии.

Относительно имитационного моделирования в рамках ARIS отметим, что модуль ARIS Simulation может быть использован для проведения динамических экспериментов в целях определения узких мест в реализации процессов (несогласованность параллельно выполняемых процессов, нехватка ресурсов и т. п.). Для этого предварительно требуется формализовать временные характеристики исследуемых бизнес-процессов. Возможно, более удобным в этом плане является программный комплекс MATLAB/Simulink, специально предназначенный для моделирования динамических систем.

Выводы

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

Часть 2. Моделирование с помощью сетей Петри

Сети Петри — аппарат для моделирования динамических дискретных систем (преимущественно асинхронных параллельных процессов) [4,5]. Сеть Петри определяется как четверка , где и — конечные множества позиций и переходов, и — множества входных и выходных функций. Другими словами, сеть Петри представляет собой двудольный ориентированный граф, в котором позициям соответствуют вершины, изображаемые кружками, а переходам — вершины, изображаемые утолщенными черточками; функциям соответствуют дуги, направленные от позиций к переходам, а функциям — от переходов к позициям.

Как и в системах массового обслуживания, в сетях Петри вводятся объекты двух типов: динамические — изображаются метками (маркерами) внутри позиций и статические — им соответствуют вершины и дуги сети Петри.

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

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

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

На рис.1 показан пример распределения маркеров по позициям перед срабатыванием, эту маркировку записывают в виде (2,2,3,1). После срабатывания перехода маркировка становится иной: (1,0,1,4).

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

Рис. 1. Фрагмент сети Петри

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

Рис. 2. Конфликтная ситуация

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

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

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

Введенные понятия поясним на следующих примерах.

Пример 1

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

Здесь переходы связаны со следующими событиями: — поступление запроса на использование WS, — занятие станции, — освобождение станции, — выход обслуженной заявки; позиция используется для отображения состояния WS: если в имеется метка, то WS свободна и пришедшая заявка вызывает срабатывание перехода ; пока эта заявка не будет обслужена, метки в не будет, следовательно, пришедшие в позицию запросы вынуждены ожидать срабатывания перехода .

Рис. 3. Сеть Петри для примера 1

Пример 2

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

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

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

Рис. 4. Сеть Петри для примера 3

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

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

Возможен и другой подход к использованию сетей Петри для анализа объектов, исследуемых на системном уровне. Он не связан с имитацией процессов и основан на исследовании таких свойств сетей Петри, как ограниченность, безопасность, сохраняемость, достижимость, живость [4,5].

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

Безопасность — частный случай ограниченности, а именно это 1-ограниченность. Если для некоторой позиции установлено, что она безопасна, то ее можно представлять одним триггером.

Сохраняемость характеризуется постоянством загрузки ресурсов, т.е.

где — число маркеров в -й позиции, — весовой коэффициент.

Достижимость характеризуется возможностью достижения маркировки из состояния сети, характеризуемого маркировкой .

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

В основе исследования перечисленных свойств сетей Петри лежит анализ достижимости.

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

следующая страница>