Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

INTEGRATION OF MULTI AGENT SIMULATION AND CRITICAL PATH METHOD TO SOLVE PROJECT SCHEDULING PROBLEM AND BOTTLENECK ANALYSIS OF BUSINESS PROCESSES

Aksenov K.A. 1 Van K.V. 1 Aksenova O.P. 1
1 Ural Federal University named after First President of Russia B.N. Yeltsin
In this work is considered the projects portfolio scheduling and bottlenecks analysis of business process tasks. Current methods of analysis and dynamic simulation of business processes frequently face the objects that contain hundreds and even thousands of elements. Industrial and business processes, projects can be defined as multi-agent resources conversion processes. Simulation of such objects constantly requires more and more computational resources and processing time. Due to this an important problem emerges – a problem of detection and application of new approaches to analysis and improvement of multi-agent models of resources conversion process. Method of multi agent scheduling of projects portfolio and bottlenecks analysis of business process base on multi agent resources conversion process model, operation analysis of probability networks, Critical Path Method (CPM).
critical path
portfolio
project
scheduling
multi-agent simulation

Введение

Современные методы анализа и динамического моделирования бизнес-процессов (БП) часто сталкиваются с объектами, в которых количество элементов составляет сотни, а то и тысячи. Производственные и бизнес-процессы, организационно-технические системы (ОТС) относятся к процессам преобразования ресурсов. Для моделирования таких объектов требуется все больше вычислительных ресурсов и машинного времени. Спецификой БП и ОТС являются процессы принятия решений. Для формализации моделей лиц, принимающих решения (ЛПР), и сценариев принятия решений в данной работе предлагается использовать аппарат экспертных и мультиагентных систем. В связи с этим является актуальным выявление и использование новых принципов построения, анализа и изменения мультиагентных моделей процессов преобразования ресурсов (МППР) с помощью реинжиниринга бизнес-процесса (РБП) на основе анализа узких мест и процедур сверток/разверток [1]. Свертка – процедура уменьшения размерности модели динамического процесса, позволяющая сократить время эксперимента и снизить затраты вычислительных ресурсов за счет выявления и сжатия неиспользуемых или неэффективно используемых элементов (цепочек) процесса. Развертка – процедура, увеличивающая размерность модели за счет добавления новых параллельных элементов (цепочек) процесса, решающих задачу повышения пропускной способности системы и эффективности ее функционирования.

Ключевая концепция, через которую рассматривается современное предприятие – это бизнес-процесс. В литературных источниках присутствует масса определений термина «бизнес-процесс», кроме этого, понятие БП часто смешивается с понятием процесса.

Под управлением проектом будем понимать деятельность, направленную на реализацию проектов с максимально возможной эффективностью при заданных ограничениях по времени, денежным средствам, трудовым и материальным ресурсам, а также качеству конечных результатов проекта [2]. Как в случае задачи планирования портфеля проектов (или проекта), так и в случае задачи анализа узких мест и РБП исследованию подлежит граф, состоящий из последовательно-параллельных операций (работ).

Для решения задачи планирования портфеля проектов (объектов строительства, в контексте бизнес-процесса данная задача трансформируется в задачу планирования выполнения заказов) в данной работе используется модель МППР и программы семейства BPsim [4]. Основные понятия процессов преобразования ресурсов приведены в [4].

Подход мультиагентных процессов преобразования ресурсов [4] используется для исследования БП и ОТС и предлагает интеграцию следующих методов: имитационного, экспертного, ситуационного и мультиагентного моделирования.

Множество элементов модели МППР представляет собой набор: MPPR={ Goal, Res, Mech, Order, Op, Agent }, где Goal – множество целей модели; Res – множество ресурсов; Mech – множество средств; Order – множество заявок; Op – множество операций модели; Agent – множество агентов модели, содержащих AgentGoal (множество целей агентов) и AgentSolution (база знаний).

Мультиагентный подход также нашел свое развитие в имитационном моделировании (ИМ). Так, система ИМ AnyLogic поддерживает моделирование реактивных агентов. Для формализации поведения агентов в AnyLogic используются диаграммы состояний (State Chart) расширения UML-RT.

В контексте ИМ происходит трансформация понятия агента в направлении уменьшения значимости свойств коммуникации (на уровне сетевых протоколов) и возможности перемещения по сети в сторону интеллектуальности (учет большего объема данных и знаний, сложности реализации машины логического вывода – как это развивается в системах G2 и BPsim) и социальности (моделирования социального поведения, внутренних убеждений, намерений и целей агентов) [3]. В G2 используется продукционная модель представления знаний. В BPsim для формализации агентов используются продукции и фреймы.

Метод планирования портфеля проектов и анализа узких мест бизнес-процесса

Основными этапами метода планирования портфеля проектов / принятия решений задачи реинжиниринга (применения процедур свертки/развертки) модели мультиагентного процесса преобразования ресурсов (БП / ОТС) являются:

1. Анализ структуры и параметров модели (по результатам имитационного эксперимента).

2. Поиск «узких мест» в модели процесса (с точки зрения задачи планирования к узким местам относятся операции процесса (работы) не имеющие резерва времени и относящиеся к критическому пути).

3. Осуществление синтеза модели, т.е. применение процедур свертки/развертки.

4. Применение алгоритмов балансировки средств.

5. Построение плана, сетевого графика.

6. Анализ характеристик новой модели процесса по результатам экспериментов.

В качестве теоретической основы метода анализа узких мест взят операционный анализ вероятностных сетей [5; 7-8]. При поиске узких мест анализируются следующие параметры мультиагентной модели:

1) коэффициент использования операции UOp_ср, средства UMech_ср, агента UAgent_ср;

2) среднее время заявки в очереди к операции, агенту;

3) простой операции из-за отсутствия средств PMechOp, простой операции из-за отсутствия входных ресурсов PResOp.

Для оценки динамики работы операции Op и агента Agent также анализируется средняя очередь заявок к операции QOp_ср, и к агенту QAg_ср. Аналогично оценке очереди проводится оценка среднего состояния ресурсов.

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

Принципы построения имитационной модели портфеля проектов

Определены следующие принципы построения имитационных моделей для предметных областей управления проектами, строительства и бизнес-процессов:

  • при построении ИМ проекта или портфеля проектов необходимо классифицировать все операции по трём типам приоритетов: 1) наивысший - для операций критического пути; 2) средний - для операций, предшествующих операциям критического пути; 3) низший - для остальных операций;
  • применение моделей субподряда позволяет снять узкие места на средствах;
  • если предметная область допускает использование прерываний операций, то при построении модели у операций могут быть использованы относительный и абсолютный приоритет, иначе - у операций устанавливается запрет прерываний;
  • применение «выталкивающей» стратегии при моделировании проектных работ (FIFO) и алгоритмов балансировки средств.

Данные принципы построения ИМ и требования предметной области также хорошо согласуются с выводами Дэйвиса [6, с. 293]: «… правило упорядочения, в соответствии с которым первой выполняется работа с наименьшим резервом (или эквивалентное правило минимизации самого позднего времени начала), в среднем дает наилучший результат».

Сравнение предлагаемого метода и классического сетевого метода

Для анализа узких мест в управлении проектами и строительстве наиболее часто применяется сетевая модель (сетевой график), которая вместе с методом критического пути (англ. CPM [6]) позволяет определить резервы времени выполнения отдельных работ. Применение ИМ субподряда приводит к эффекту наискорейшего «проталкивания» работ. Результаты применения метода CPM и МППР на примере цепочек параллельно-последовательных работ показаны на рис. 1.

Рис. 1. Применение методов CPM и ИМ субподряда

Рассмотрим ситуацию параллельного выполнения во времени двух проектов, когда имеется 3 ресурса для выполнения проектов (каждая работа захватывает 1 ресурс), объект 2 начинается в 24-й день (рис. 2). Для случая, когда параллельно во времени могут выполняться 2 работы и наивысший приоритет назначается работам, относящимся к критическому пути (причем эти приоритеты для разных проектов (объектов) одинаковы).

Рис. 2. Сетевой график проектов с выровненной потребностью в ресурсах (суммарная длительность портфеля 52)

Если для случая, представленного на рис. 2, допустимо начать объект 2 раньше (на 12-й день) и не вводятся штрафные санкции за задержки в выполнении проекта, а также допустимо использовать прерывания операций, то можно минимизировать длительность портфеля проектов с 52 до 43 дней (рис. 3).

Рис. 3. Сетевой график проектов для трех ресурсов с началом объекта 2 на 12-й день и возможностью прерывания операции О2.Op1 (суммарная длительность портфеля 43)

Для случая трех ресурсов, с возможностью смещения сроков работ объекта 2 на 12-й день, сетевые графики для одного из возможных вариантов и функции потребления ресурсов представлены на рис. 5: при условии запрета прерывания работ (вариант «окно» запуск операции O2.Op1, длительность портфеля проектов 40 дней).

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

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

Рис. 4. Сетевой график проектов для трех ресурсов, с возможностью смещения объекта 2 на 12-й день и запретом прерывания работ (вариант «окно» запуск операции O2.Op1, суммарная длительность 40 дней)

Таблица 1.

Критерий сравнения

CPM

МППР

1.

Учет использования средств

+

+

2.

Учет поставок и потребления ресурсов

НЕТ

+

3.

Учет времени жизни потребляемого ресурса

НЕТ

+

4.

Учет субподряда

+

+

5.

Балансировка средств

+

+

6.

Формирование сетевого графика

+

+

7.

Формирование графика использования средств

+

+

8.

Нахождение критического пути

+

+

9.

Оценка резерва времени для каждой работы

+

+

10.

Формирование графика поставок/потребления ресурсов

НЕТ

+

Дополнительным преимуществом новой информационной технологии мультиагентного планирования, реализованной на основе комплекса BPsim, является автоматическая генерация и параметризация объектов портфеля. С применением системы BPsim и нового метода планирования была разработана модель строительного холдинга CHINA WANBAO (задача строительства 11 многоэтажных зданий) [1; 5; 9]. Применение метода привело к уменьшению сроков выполнения строительства на 5.94% (81 день) и повышению загрузки средств в холдинге.

Выводы

Задача планирования строительных работ и ее программная реализация решена с использованием гибридного подхода в результате применения мультиагентного моделирования и метода критического пути. Проведено сравнение разработанного метода мультиагентного планирования и РБП с методом критического пути. Результаты сравнения показали эффективность нового метода мультиагентного планирования.

Работа выполнена в рамках договора № 02.G25.31.0055 (проект 2012-218-03-167).

Рецензенты:

Шабунин С.Н., д.т.н., профессор кафедры высокочастотных средств радиосвязи и телевидения, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.

Доросинский Л.Г., д.т.н., профессор, заведующий кафедрой информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.