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

На правах рукописи

ЗРЛЕНКО Алексей Сергеевич

СИСТЕМА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И ФОРМИРОВАНИЯ КОАЛИЦИЙ И ЕЕ ПРИМЕНЕНИЕ НА ПРОМЫШЛЕННЫХ ПРЕДПРИЯТИЯХ ДИВИЗИОНАЛЬНОЙ СТРУКТУРЫ УПРАВЛЕНИЯ ПРИ ВЫПОЛНЕНИИ КРУПНЫХ ЗАКАЗОВ

Специальность 05.13.01 - Системный анализ, управление и обработка информации (промышленность)

Автореферат диссертации на соискание ученой степени кандидата технических наук

23 ОКТ 2014

Самара-2014

005553605

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

Научный руководитель: Аксенов Константин Александрович

кандидат технических наук, доцент

Официальные оппоненты: Соколов Борис Владимирович

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

Скобелев Петр Олегович

доктор технических наук, профессор, ведущий научный сотрудник ФГБУН «Институт проблем управления сложными системами РАН» (г. Самара)

Ведущая организация: ФГБОУ ВПО «Уральский государственный

университет путей сообщения» (г. Екатеринбург)

Защита состоится «20» ноября 2014 г. В 10 час. 00 мин. на заседании диссертационного совета Д 212.217.03 при ФГБОУ ВПО «Самарский государственный технический университет» по адресу: г. Самара, ул. Галактионовская, 141, корп. № 6, ауд. № 33.

С диссертацией можно ознакомиться в научной библиотеке Самарского государственного технического университета (г. Самара, ул. Первомайская, 18, корпус № 1) и на сайте www.samgtu.ru.

Отзывы на автореферат просим высылать в двух экземплярах, заверенных печатью, по адресу: 443100, г. Самара, ул. Молодогвардейская, 244, главный корпус СамГТУ, ученому секретарю диссертационного совета Д 212.217.03; тел. (846) 337-04-43, e-mail: radch@samgtu.ru.

Автореферат разослан октября 2014 г.

Ученый секретарь

диссертационного совета Д212.217.03 доктор технических наук, доцент

В.Е. Зотеев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Для управления такими предприятиями, как в стратегическом, так и в тактическом плане все шире применяется мультиагентное моделирование всех процессов, протекающих как на предприятии, так и во внешней среде. В системном анализе разработка мультиагентных моделей является эффективным методом нахождения оптимального (либо приемлемого) решения задач, возникающих в сложных системах. Существенный вклад в развитие мультиагентных систем внесли: Борщев A.B., Виттих В.А., Городецкий В.И., Карпов Ю.Г., Кобелев Н.Б., Попов Э.В., Поспелов Д.А., Скобелев П.О., Смирнов C.B., Советов Б.Я., Стефанюк B.J1., Соколов Б.В., Хорошевский В.Ф., Швецов A.B., Яковлев С.А., Conway J.H., Epstein J. M., Jennings N.R., McCarthy J., Nilsson N., Norvig P., Russell S. J. и др.

Под крупным заказом в рамках настоящей работы будем понимать заказ, полученный агентом-руководителем подразделения предприятия, требующий использование ресурсов и средств, превосходящих по объему имеющиеся ресурсы и средства данного подразделения. Коллективное использование ресурсов и средств, принадлежащих различным агентам, возможно при организации сообщества - коалиции. Существенный вклад в развитие теории коалиций внесли M.J. Wooldridge, М.В. Губко, J. Vidal, Y. Shoham, К. Leyton-Brown и др.

Для моделирования поступления заказов и распределения ресурсов с целью дальнейшего планирования выполнения работ могут быть использованы различные системы. В существующих системах, близких по функциональности: AnyLogic 6, 3Psim2, MagentA, RepastJ, Simplex3, Tecnomatix Plant Simulation, не представлены встроенные механизмы формирования коалиций агентов и формирования оптимальных планов выполнения работ (или заказов).

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

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

Для реализации данной цели в работе поставлены следующие задачи:

1) провести системный анализ методов и средств планирования использования ресурсов на предприятиях с дивизиональной структурой управления;

2) выполнить сравнение существующих мультиагентных моделей и определить требования для Коалиционной модели;

3) разработать Коалиционную модель, позволяющую осуществлять планирование ресурсов для выполнения заказов на промышленных предприятиях с ограничением их выполнения по времени;

4) определить типы и характеристики производственных процессов, для которых существуют методы получения оптимальных планов, и при

необходимости осуществить их доработку.

5) разработать алгоритмическое обеспечение и систему распределения ресурсов и формирования коалиций на базе Коалиционной модели;

6) провести испытания эффективности разработанной модели и системы в предметной области производства тепловых пунктов (ТП):

a) разработать онтологию предметной области производства ТП;

b) апробировать разработанную систему при совместном выполнении крупных заказов отдельными подразделениями предприятия по производству ТП.

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

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

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

Научная новизна работы.

1. Разработана Коалиционная модель, отличающаяся от существующих: механизмами формирования коалиций, расширенными за счет

встроенных алгоритмов совместного выполнения работ агентами;

- возможностью составления оптимальных планов выполнения работ с учетом ограничений по времени;

- расширенными механизмами взаимодействия агентов на основе стандарта ИРА,

что в сумме позволяет повысить количество выполняемых заказов в единицу времени в условиях ограниченности ресурсов.

2. Разработаны алгоритмы взаимодействий агентов, отличающиеся от существующих:

- ориентацией на проблемную область коалиций и задачу разрешения конфликтов между агентами при ограниченности ресурсов и средств;

- ориентацией на использование совместно с алгоритмом составления оптимальных планов выполнения работ с ограничениями по времени;

что в сумме позволяет повысить эффективность взаимодействия агентов и мультиагентной системы в целом.

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

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

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

Практическое значение работы. Разработанная модель и система позволяют:

- получать эффективные решения при совместном выполнении крупных заказов отдельными подразделениями промышленного предприятия;

- решать для подразделений промышленных предприятий задачи составления оптимального плана выполнения работ с учетом ограничений по времени;

- использовать встроенные и разрабатывать новые алгоритмы взаимодействий агентов в моделях;

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

Основные научные результаты и положения, выносимые на защиту:

1. Коалиционная модель, включающая:

- встроенные механизмы формирования коалиций;

- язык взаимодействия агентов на основе стандарта FIPA, разработанный для предметной области коалиций.

2. Метод взаимодействия агентов в модели, позволяющий:

- использование агентом стратегий взаимодействия при формировании коалиций;

- разрешение конфликтов на общих ресурсах и средствах агентов на

основе алгоритмов проведения аукционов.

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

Реализация результатов работы. Разработанная Коалиционная модель и система jSIM внедрены на ФГУП «Уральский региональный информационно-аналитический центр «Уралгеоинформ» для моделирования поступления заказов на разработку геоинформационных систем (акт внедрения от 12 марта 2008 г.), в ООО АН «КИМ» для определения направления развития компании (акт внедрения от 4 тоня 2008 г.), в ООО «Альтернативные энергосистемы» для моделирования производства ТП (акт внедрения от 19 марта 2013 г.).

Апробация работы. Основные положения и результаты диссертационной работы докладывались автором на Международной научно-практической конференции СВЯЗЬ-ПРОМ (г. Екатеринбург, 2006, 2007, 2008, 2010), X Национальной конференции по искусственному интеллекту с международным участием (г. Обнинск, 2006), II Международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (г. Санкт-Петербург, 2006), VI Международной научно-технической конференции «Научное программное обеспечение в образовании и научных исследованиях» (г. Санкт-Петербург, 2008), IX Международной научно-технической конференции «Компьютерное моделирование 2008» (г. Санкт-Петербург, 2008), Всероссийской научно-технической конференции «Наука - Производство - Технологии - Экология» (г. Киров, 2007), X Всероссийской студенческой научно-технической конференции «Информационные технологии и электроника» (г. Екатеринбург, 2005), IV Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (г. Санкт-Петербург, 2009).

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

- модель процессов формирования коалиций при совместном выполнении сложных заказов агентами-руководителями подразделений [1,3,4,6,7,15];

- алгоритм составления оптимальных планов выполнения работ по теореме Джонсона с ограничениями по времени выполнения работ [2];

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

коалиций на основе стандарта взаимодействия агентов FIPA [5,10-12];

- система распределения ресурсов и формирования коалиций jSIM [8,9,13,14].

Публикации. По теме диссертации опубликовано 15 научных работ, в том числе 4 работы в печатных изданиях, рекомендованных ВАК.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и семи приложений. Объем основной части работы составляет 168 страниц машинописного текста. Работа содержит 49 рисунков и 23 таблицы. Список литературы включает 204 наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

Коалиционной модели М соответствует структура:

M=<NameM, DescM, {Obj,,...,Objm}, tM> (1)

где: Nameh, - имя модели; DcscK, - описание модели; {Obji, ...,Obj„} - объекты (элементы модели): агенты, коалиции, ресурсы, средства, сообщения, цели, стратегии, работы (заказы), планы выполнения работ (заказов), tM - время в модели.

В модели функционируют процессы, представленные на рисунке 1.

-«...........-......— > Процессы формирования коалиции К1

< >■ Процессы формирования коалиции К2

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

"Vs Процессы взаимодействия коалиций между собой и с отдельными агентами

^_________Процессы взаимодействия агентов разных коалиций между собой и с отдельными

агентами (направленные на достижение их второстепенных целей)

Рисунок 1 - Схемы процессов в Коалиционной модели

Агенты в модели представлены в виде следующей структуры:

А = <NameÄ, {GA!,...,GA„}, КВА, {StrA,,...,StrAv} >, (2)

где: Name а - имя агента; {GAh...,GA„} - цели агента; КВА - база знаний агента; {StrAi, ...,StrAv} - множество допустимых стратегий взаимодействия агентов.

Каждый агент А, имеет собственную базу знаний КВА„ множество целей {G'Ai,...,G"Ai}, включающих одну доминирующую цель GDAi и множество второстепенных целей {G с\}- Каждый агент А; управляет собственными ресурсами {Res'Al_____Res'",,,} и средствами {Mech'A„ ...,MechkAi}. Управление

агентом Л, организуется с помощью плана действий PDM на основе использования информации из собственной базы знаний КВА, и обшей базы знаний СКВ.

В процессе работы MAC агенты могут взаимодействовать, формировать коалиции {Ki,...,Ka} с целями: выполнения крупного заказа, получения необходимых ресурсов и средств. Коалиция агентов в MAC представлена в виде следующей структуры:

K = <NameK, {Ah...,Am}, GK, {Str,, ...,Strv}, КВк, (3)

где: NameK - имя коалиции; {A,..... Ат} - множество агентов, входящих в

коалицию; GK - цель коалиции; {Strh...,Strv} - множество допустимых стратегий поведения коалиции; КВк - база знаний коалиции; tWAi - время выполнения работы агента-инициатора коалиции.

Под работой WK коалиции К будем понимать следующую структуру:

WK= < tWK, {if ,, {Resa, ...,ResKm}, {MechKb...,MechKk} >, (4)

где: tWK - время выполнения работы; {DK,.....£>%} - действия по выполнению

работы; {ResKh...,ResKm} - ресурсы, используемые в работе; {MechKh...,hiechK%\ - средства, используемые в работе.

План выполнения работ PWK формируется коалицией К для достижения цели Ск и состоит из определенной последовательности работ {WKh..., WKt}. Плану выполнения работ PWK коалиции ^соответствует следующая структура: PWK = <{WK1,...,WKl), G'K, КВк, GKB, {ADh...,ADh}, iPK>, (5)

где: (WK}.....lVf;,} - работы плана; - цель плана; {AD,, ...,ADh] - множество

агентов, участвующих в плане; tPWK- срок выполнения плана работ коалиции.

В главе проведен анализ методов составления планов выполнения работ. Для Коалиционной модели рассмотрены методы Джонсона (для производств, число переделов в которых допустимо объединить до 2-х) и случайного поиска (не дающий оптимального решения, но применимый для производств из большего количества переделов). В связи с необходимостью учета ограничений по времени, проведено расширение алгоритма Джонсона путем введения максимальной длительности выполнения каждой из работ. Из теории составления расписаний известен алгоритм, по которому упорядочение работ S* является оптимальным по теореме Джонсона. Пусть: А,- — длительность работы первого множества ресурсов и средств для г-й работы; В, — длительность работы второго множества ресурсов и средств для /-й работы; F,- - длительность прохождения «-й работы, X{i] - время простоя 2-й машины (производственного

передела) для / й работы, I - количество работ. План выполнения работ для системы из 2-х переделов представлен на рисунке 2.

Передел 1 Ащ | АШ АГЗ] Л[4] Лр)

Передел 2 - ХМ ! В1Ч л/1 В[2] В[31 хю В[<] В{5]

Рисунок 2 - Плап выполнения работ для системы из 2-х переделов

J

По Джонсону: " тах

/=1

.М М Ы 1 1 ¡=-1

и J-1 ]

Определим У, как: = Хли; " Е %Ь тогда = тах^К,,...,}^)

¡=1 ¡=1

Если максимальную длительность прохождения для конкретного расписания 5 обозначить Ртах (5), то

^па =Е%] +шах(7„У2,...,Уя)

/=1 ¿=1 1=1 Введем дополнение к алгоритму Джонсона. Обозначим для каждой работы : критическую дату Т„ определяющую максимальный срок ее выполнения, при переходе через нее возникает штраф О;. Введем обозначения: X* - время простоя при оптимальном размещении работ, X* = =

Сформулируем задачу: найти расписание 5**, обеспечивающее выполнение ограничений по времени, и не допустить времени простоя, превышающего X*. То есть разработанный алгоритм должен минимизировать количество работ, превышающих критическую дату 7). По алгоритму рассматриваются работы оптимального по Джонсону расписания, проверяется выполнение неравенств, и производятся перестановки. Максимальная длительность для расписания 5:

¡=1 1-1 ы

Таким образом, разработан алгоритм для «оснащения» агента механизмом составления оптимальных планов выполнения работ с минимизацией штрафов за превышение временных ограничений. Проведено сравнение с аналогом -алгоритмом Ю.А. Зака. Новый алгоритм отличается: гарантией составления оптимального плана; невозможностью изменения ограничений по времени; гарантией составления расписания при любых ограничениях по времени; применимостью только для производств из 2-х переделов.

Далее в главе рассмотрены существующие методы разрешения конфликтов между агентами. По результатам анализа, для задачи разрешения конфликтов в

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

В третьей главе описана структура и функции разработанной системы jSIM. Рассмотрены основные принципы построения системы. Проведен обзор и сравнительный анализ стандартов взаимодействия агентов. Приведено описание технологии работы в системе. Для использования системы в распределенном режиме выбран стандарт FIPA благодаря следующим преимуществам: наибольшая надежность, возможность описания онтологии; соответствие проблемной области коалиций; простота программной реализации. Графический интерфейс системы jSIM представлен на рисунке 3.

j^sä .-J •

5" Заявки проект fzl) ® в A, ton® Заказа -ji| i 1 iv щ V 2 Директор n \ в? S run лт l § - | 1...............................°вп Щ

В О test - § Заказчтж [а1] # Имя В • Директор (а8| - У Имя Имя В § ГИП 1 |аЗ] /' Имя Й # ГИП2[а10| У Имя § 08П tale] @ Нпет iw20|

"СоЗмшя"-----------— —........ V — — A

■ TIME [00.00) -. Stat ZM ; TIME 100.00) Agent (Заказ-.« |al9|) -> »ека na проект в : TIME 100.021: Aqent (Директор [aSIl -> nowet«e заказа TIME (01 .Ü0): Agent {Директор [aßü —> решение jpj

Май Mode) j Eifa " • - '

1 Е Директор SU ; f IF J ■ state*"noreK" ; ! txif out(a1.AskHJ ; a THEN FIPA(al.Ask."il") 4 3 1.2 ! & IF ! state="noHCK" buf_ou<(a1.A5kH buf_ir){a1. InfotmK'no' : В THEN del_mea<a1) ¿j м >r ß----------.........ArtpT) | Щ 1 1«............-г...........«ГШ I К-.......... «□-^J-;J.'.-M'l------j [ •| "<=>f»"i.........1.............J ¡"5*1 .....I 1— ! - ■ --------oo«W] | 1 t^.............r-..........DopTll-S-) , 1 1 k.............1...........«пл.- I...................1..........-................1.....................Г "Г" • s--------В, -5 I ........Ц I I S| | т^укТ).........^............. 1 i I v........<■. ¿a

jProv*fei=SQLOLED0.1 integrated Sectf С oonect jtest -jjtea jj j

Рисунок 3 - Графический интерфейс системы jSIM

Система]81М позволяет вырабатывать управленческие решения, создавать модели мультиагентных процессов, проводить имитационные эксперименты с использованием механизма составления планов выполнения работ.

В четвертой главе рассмотрены примеры моделей в системе ¡БГМ. Система апробирована на примере задачи по производству тепловых пунктов на промышленном предприятии «Альтернативные энергосистемы». Проведен расчет планов выполнения работ агентами по трем различным алгоритмам. Проведен сравнительный анализ эффективности стратегий взаимодействия агентов. Исследована динамика использования ресурсов в зависимости от стратегии взаимодействия агентов. Проведена оценка эффективности внедрения системы

Схема коалиции в модели по производству ТП на предприятии «Альтернативные энергосистемы» приведена на рисунке 4.

1Л

Руководитель подразделения А-,

К

м

Руководитель подразделения Aj

Проектирование

Сборка

Контроль качества

_^, N,

— г^ь » *

Проектировщики1 рафические® Сборщики Станок Д \ (К человек) станции у (М человек) по металлу / \

{Р штукК | V (1штук^ у

Т--

äb

Um

Контролеры качества (К человек)

Проектирование

Сборка

/

Контроль качества

Рисунок 4. Схема коалиции в модели по производству ТП

В модели по производству ТП цели агентов - руководителей подразделений (А„ А/):

- минимизация времени выполнения работ по заказу: t1" (W„)~»min;

- минимизация финансовых затрат по выполнению работ (т.е. максимизация прибыли агента): S4"—>тах;

- минимизация количества используемых «общих» ресурсов и средств в связи с вероятностью возникновения «параллельного» заказа: //"'—►min.

Для описания предметной области формирования коалиций и составления планов выполнения работ на предприятии «Альтернативные энергосистемы» разработана онтология, представленная на рисунке 5.

!трзфные санкции4

за сдаиг сроков ,

Включает'

Включает

<3грасичения гю\ времени , исполнения рабр^

■Цель коалици!

Включает

Формирует

Регламентирует

Заказ на .выполнение работ,

Конфигурация ИТП

Действия

. Проводят к созданию включает ; \

Включает

Формирует

Формирует

Произволе 1во ИТП

Переговоры Завершаются

коалиции

Руководит I

Стратегия руководителя 1цодразделени£

Проводит

Включает

работ коалиции

5 ля ют количество

Является

Включает

Обновляют количество

Использует

Принадлежат

Принадлежат

Оптимальный план

База знаний~^\8ключа« руководителя У тодоаздеяени^-/

Методы взаимодействий

Включают

Включают

Включает Включает

)бщая база знании4 Предприятия >

Включает

Включают4

1лан действий г выполнению .____работы___

Рисунок 5 - Онтология предприятия по производству ТП

Далее проведен расчет оптимального плана выполнения работ для описанной модели. Будем считать, что на определенный момент времени имеется очередь из 15 работ (заказов) по производству ТП в системе конвейерного типа, состоящей из 2-х переделов: проектирование (1-й передел); сборка и контроль качества (2-й передел). Каждая работа управляется своим агентом-руководителем подразделения по производству ТП. В диссертации

проведены расчеты гшанов выполнения работ по алгоритму Джонсона (S*) к по разработанному алгоритму с учетом ограничений по времени (S**). Согласно расчетам, суммарное время выполнения работ по плану S** - 130 единиц, равное времени выполнения работ по плану S*. Т. е. разработанный алгоритм обеспечил оптимальное время выполнения работ. При этом штраф за превышение времени равен 5 единиц (по 2-м просроченным работам). В плане S* - штраф составляет 28 единиц из 67 возможных (по 5-и просроченным работам). По алгоритму Ю. А. Зака получен план с большим временем выполнения работ (136 единиц), но с меньшим размером штрафа (3 единицы) по 3-й просроченной работе. Таким образом, разработанный алгоритм обеспечил оптимальное время выполнения работ, а также их выполнение с меньшим штрафом (чем алгоритм Джонсона).

Произведена оценка эффективности внедрения системы jSIM на предприятии «Альтернативные энергосистемы» относительно производящегося ранее планирования в MS Excel. Оценка производилась по критерию изменения чистой прибыли предприятия от деятельности по производству ТП. График сравнения приведен на рисунке 6. Красной линией обозначен график получения прибыли по заказам при планировании выполнения работ в MS Excel, синим - в системе jSIM. «Ломаность» графика связана с нелинейностью поступления денежных средств по результатам выполнения заказов.

S, у .е.

Рисунок 6 - График сравнения чистой прибыли

Д7

Такгш образом, з результате внедрения системы ]Б1М чистая прибыль предприятия кАльтернативные энергосистемы» от деятельности по производству ТП выросла € среднем на 11,4%. Рост обеспечен за счет оптимизации загрузки ресурсов и средств.

В приложении 1 определены критерии сравнения систем распределения ресурсов и формирования коалиций. В приложении 2 приведен сравнительный анализ программных систем, близких по функциональности к системам распределения ресурсов и формирования коалиций, и разработанной системы ]51М. В приложении 3 приведен сравнительный анализ существующих математических моделей, позволяющих описывать мультиагентные процессы, и Коалиционной модели. Приложение 4 содержит копии документов, подтверждающих внедрение программной сисгемы jSIM. Приложение 5 содержит решение задачи составления плана выполнения работ по алгоритму Джонсона. Приложение б содержит решение задачи составления плана выполнения работ с учетом ограничения по времени. Приложение 7 содержит решение задачи составления плана выполнеши работ по алгоритму Ю.А. Зака.

ЗАКЛЮЧЕНИЕ

В заключении приводятся следующие основные результаты работы:

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

2. Проведен сравнительный анализ средств разработки мультиагентиых моделей с точки зрения возможности их использования для создания моделей с коалициями. Рассмотрены системы АпуЬо^с 6, Ма§еп1А, ВР51т2, КеравИ, БтркхЗ, ТеспотаЦх Р1ап13ти1аиоп. Сделан вывод о необходимости разработки нового программного средства-на базе системы ВРз1ш2.

3. Разработана Коалиционная модель, включающая механизмы:

- обмена сообщениями между агентами, разработанного для предметной области коалиций на основе стандарта БГРА;

- разрешения конфликтов на основе стратегий взаимодействий и организации аукционов;

- формирования коалиций;

- составления оптимальных планов выполнения работ агентами с учетом

ограничений по времени для производств, число переделов в которых допустимо объединить до 2-х;

- составления планов выполнения работ для производств, включающих

более 2-х переделов.

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

5. Разработано расширение языка FIPA Semantic Language, обеспечившее его адаптацию к предметной области коалиций и возможность описания взаимодействий агентов в конфликтных ситуациях.

6. Разработана система распределения ресурсов и формирования коалиций jSIM. Система внедрена на ФГУП «Уралгеоинформ», в ООО АН «КИМ» и в ООО «Альтернативные энергосистемы». В результате внедрения на предприятии «Альтернативные энергосистемы» чистая прибыль предприятия от деятельности по производству ТП выросла в среднем на 11,4%.

Основные положения диссертации опубликованы в следующих работах:

Статьи, опубликованные в ведущих рецензируемых научных журналах, входящих в перечень ВАК:

1. Зраенко A.C. Коалиционная модель мультиагентного процесса преобразования ресурсов / A.C. Зраенко, К.А. Аксёнов, Ван Кай // Научно-технические ведомости СПбГУ, 2009. -№5. - С. 156-161.

2. Зраенко A.C. Решение задач планирования в коалиционной модели / A.C. Зраенко, К.А. Аксёнов, В.П. Федотов // Программные продукты и системы, 2012.-№1.-С. 23-28.

3. Зраенко A.C. Разработка коалиционной системы поддержки принятия решений / A.C. Зраенко, К.А. Аксёнов, В.П. Федотов // Вестник Самарского государственного технического университета. Серия физ-мат науки, 2013. -№2(31).-С. 72-79.

4. Зраенко A.C. Сравнительный анализ мультиагентных моделей процессов преобразования ресурсов [Электронный ресурс] / Зраенко A.C., Аксенов К.А.,

Федотов В .П. // Современные проблемы науки и образования, 2013. - № 4. Режим доступа: http://wwvV.sciencc-education.rU/l 10-9640.

Статьи, опубликованные в научных сборниках и материалах международных конференций:

5. Аксёнов К.А. Разработка языка коммуникации агентов для мультиагентной системы моделирования процессов преобразования ресурсов / К.А. Аксёнов, A.C. Зраенко // Журнал научных публикаций аспирантов и докторантов. - Курск: ООО «Редакция журнала научных публикаций аспирантов и докторантов», 2008. - №5. - С. 134-136.

6. Зраенко A.C. Конфликтные ситуации в интеллектуальных мультиагентных процессах преобразования ресурсов / A.C. Зраенко, К.А. Аксенов // Сборник трудов второй международной научно-практической конференции «Исследование, разработка и применение высоких технологий в промышленности». - СПб.: Издательство Политехнического университета, 2006. -Том№5.-С. 24-26.

7. Аксенов К.А. Конфликтные ситуации в мультиагентных процессах преобразования ресурсов / К.А. Аксенов, A.C. Зраенко, Н.В. Гончарова, С.Ю. Долматов // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2006» в рамках III Евро-Азиатского форума «СВЯЗЬ-ПРОМЭКСПО 2006». - Екатеринбург: ЗАО «Компания Реал-Медиа», 2006. - С. 49-51.

8. Зраенко A.C. Защита информации в распределенных системах поддержки принятия решений / A.C. Зраенко, К.А. Аксенов // «Безопасность информационного пространства»: материалы международной научно-практической конференции. - Екатеринбург: Издательство ГОУ ВПО УрГУПС, 2006. - С. 58-64.

9. Зраенко A.C. Применение мультиагентного подхода в системах поддержки принятия решений / A.C. Зраенко, С.А. Коновалова, К.А. Аксенов // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2007» в рамках 4-го Евро-Азиатского форума «СВЯЗЬ-ПРОМЭКСПО 2007». - Екатеринбург: ЗАО «Компания Реал-Медиа», 2007. - С. 214-217.

10. Зраенко A.C. Разработка модели и языка общения для мультиагентной системы BPsim.MAS / A.C. Зраенко, К.А. Аксёнов, Е.М. Лазарев // VI международная научно-техническая конференция «Научное программное обеспечение в образовании и научных исследованиях»: Сборник материалов. -СПб.: Изд-во Политехнического университета, 2008. - С. 43-46.

SV

11. Зраенко A.C. Реализация механизма общения агентов в мультиагентной системе моделирования процессов преобразования ресурсов jSIM / A.C. Зраенко, К.А. Аксёнов, Е.М. Лазарев // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2008» в рамках V Евро-Азиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2008». - Екатеринбург: ЗАО «Компания Реал-Медиа», 2008. - С. 235-237.

12. Зраенко A.C. Применение механизмов коммуникации агентов в системе мультиагентного моделирования / A.C. Зраенко, К.А. Аксенов, Е.М. Лазарев // IX международная научно-техническая конференция «Компьютерное моделирование 2008»: Сборник материалов. - СПб: Издательство Политехнического университета, 2008. — С. 7-11.

13. Зраенко A.C. Разработка библиотеки сценариев взаимодействий агентов для СИМ BPsim2 / A.C. Зраенко, Е.М. Лазарев // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2009» в рамках VI ЕвроАзиатского международного форума «СВЯЗЬ-ПРОМЭКСПО 2009». -Екатеринбург: ЗАО «Компания Реал-Медиа», 2009. - С. 157-159.

14. Зраенко A.C. Разработка системы поддержки принятия решений с использованием средств мультиагентного моделирования / A.C. Зраенко, К.А. Аксёнов, Е.М. Лазарев // XVI международная конференция молодых ученых: сборник статей. - Екатеринбург, УГТУ-УПИ, 2009. - С. 31-34.

15. Зраенко A.C. Коалиции агентов в имитационном моделировании // Научные труды международной научно-практической конференции «СВЯЗЬ-ПРОМ 2010» в рамках VII Евро-Азиатского форума «СВЯЗЬ-ПРОМЭКСПО 2010». - Екатеринбург: ЗАО «Компания Реал-Медиа», 2010. - С. 105-108.

Автореферат отпечатан с разрешения диссертационного совета Д 212.217.03 ФГБОУ ВПО «Самарский государственный технический университет» (протокол №3 от «15» сентября 2014 г.)

Отпечатано на ризографе. Усл. печ. л. 1,0 Тираж 100 экз. Заказ №821

ФГБОУ ВПО «СамГТУ» Отдел типографии и оперативной печати 443100, г. Самара ул. Молодогвардейская, 244