Автоматика и телемеханика, № 11, 2021

А.А. ЖИЛЯЕВ (zhilyaev.alexey@gmail.com),

В.Б. ЛАРЮХИН (vladimir.larukhin@live.ru),

Д.Е. НОВИЧКОВ (dmitriy.novichkov@gmail.com),

В.А. ГАЛУЗИН (galuzin@.kg.ru)

(Самарский государственный технический университет),

Е.В. СИМОНОВА, канд. техн. наук (simonova@kg.ru)

(Самарский национальный исследовательский университет

им. академика С.П. Королева),

И.В. МАЙОРОВ, канд. техн. наук (imayorov@kg.ru),

П.О. СКОБЕЛЕВ, д-р. техн. наук (petr.skobelev@gmail.com)

(Самарский федеральный исследовательский центр РАН,

Институт проблем управления сложными системами РАН, Самара)

МЕТОДЫ И СРЕДСТВА ПОСТРОЕНИЯ

ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ДЛЯ РЕШЕНИЯ

СЛОЖНЫХ ЗАДАЧ АДАПТИВНОГО УПРАВЛЕНИЯ

РЕСУРСАМИ В РЕАЛЬНОМ ВРЕМЕНИ¹

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

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

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

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

Формулируются требования к решению рассматриваемых задач и предла-

гаются общие принципы, повышающие адаптивность управления ресур-

сами. Проводится краткий анализ существующих подходов и показыва-

ются их ограничения. Предлагается новая методология решения рассмат-

риваемых задач, дается обзор разработок и обсуждается первый опыт ее

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

сами. Показывается возможность решения экстремально сложных задач

управления ресурсами за счет модифицированной на основе онтологий

концепции сети потребностей и возможностей, в рамках которой распи-

сание строится как «конкурентное равновесие» на виртуальном рынке

унифицированной мультиагентной системы, настраиваемой на конкрет-

ное предприятие с использованием прикладных онтологий. Даются при-

мер построения прототипа интеллектуальной системы управления ресур-

сами многоспутниковой группировки ДЗЗ и результаты ее эксперимен-

тальных исследований. Предлагается подход к оценке качества и эффек-

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

расписаний при управлении ресурсами в реальном времени. Показыва-

ются перспективы дальнейшего развития подхода для решения сложных

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

¹ Работа поддержана Российским фондом фундаментальных исследований (проект

№ 20-37-90052).

Ключевые слова: задача адаптивного управления ресурсами, онтологии,

мультиагентные технологии, интеллектуальные системы, сети потребно-

стей и возможностей, виртуальный рынок, конкурентное равновесие, ре-

альное время.

DOI: 10.31857/S0005231021110039

1. Введение

Новые потребности предприятий в повышении эффективности бизнеса в

условиях современной сетевой экономики и стремительного прогресса ком-

пьютерных технологий приводят к появлению новых постановок задач управ-

ления ресурсами в сравнении с традиционными, которые было принято рас-

сматривать в исследовании операций [1-3]. Одна из таких новых задач связа-

на с переходом к управлению ресурсами в реальном времени, когда от самого

момента времени принятия решения напрямую зависят качество и эффектив-

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

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

му управлению ресурсами в реальном времени, где есть высокая сложность,

априорная неопределенность и турбулентная динамика изменений спроса и

предложения, например, когда на предприятие часто приходят новые заказы

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

ресурсы, уже запланированные заказы приостанавливаются или отменяют-

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

задачи, поставщики комплектующих и т.д.

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

ется актуальна и значима, становится все больше: это он-лайн такси для пас-

сажиров и перевозки грузов, заводы и фабрики, работающие по индивидуаль-

ным заказам, доставка товаров интернет-магазинов и т.п. Можно утверждать,

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

использованию разделяемых ресурсов и экономике реального времени, число

таких задач будет продолжать расти.

В этих условиях традиционное «пакетное» планирование на большой го-

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

тематического программирования или разнообразных эвристиках и мета-

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

граммирование и др. [4-6], не дает существенного выигрыша, так как постро-

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

ния событий может существовать лишь короткое время и далее безвозвратно

устаревает, а полное перестроение планов заново по каждому событию тре-

бует долгих вычислений, в ходе которых, в свою очередь, могут приходить

все новые события.

В этой связи становятся востребованными новые модели и методы адап-

тивного управления ресурсами в реальном времени, предназначенные для ре-

шения задач распределения, планирования, оптимизации, прогнозирования,

согласования, мониторинга и контроля использования ресурсов по событиям,

без полного перестроения планов, а только той их части, которая прямо или

косвенно задета событием.

При этом планирование ресурсов должно предполагать не столько «ин-

крементальное» изменение плана, когда новые заказы планируются на сво-

бодные ресурсы, добавляясь в открытые интервалы времени («в хвост») уже

имеющихся в расписании заказов, сколько выявление и разбор конфликтов

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

для принятия таких решений.

Во втором разделе формулируется содержательная постановка задачи

адаптивного управления ресурсами предприятий в реальном времени и рас-

сматриваются примеры такого рода практических задач в различных сфе-

рах управления ресурсами. При этом показывается, что решение любой та-

кой сложной задачи - это всегда поиск согласия или консенсуса между все-

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

относить не только людей, но и любые другие сущности: заказы и ресур-

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

производства. Выделяются типовые критерии, предпочтения и ограничения,

показывающие внутренний конфликтный характер решаемых практических

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

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

ограничения существующих методов и средств планирования и оптимизации,

затрудняющих их практическое использование.

В третьем разделе проводится краткий анализ существующих подходов

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

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

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

(конфликт ценностей) и сетевым рыночным моделям конкуренции и коопе-

рации множества участников с юберизацией ресурсов (компромиссу ценно-

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

ресурсами (ИСУР), приходящих на смену классическим Enterprise Resource

Planning (ERP) системам, для работы в условиях новой экономики.

В четвертом разделе обобщается методология решения рассматриваемых

задач и дается обзор разработок ИСУР в Самарской школе мультиагентных

систем. Прослеживается развитие предложенной в [7, 8] концепции сетей по-

требностей и возможностей, показываются поэтапное расширение состава ос-

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

ными уступками и компенсациями, в рамках которого расписание строится

как «конкурентное равновесие» (динамический останов). Приводятся требо-

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

ИСУР. Показывается опыт разработки ИСУР для различных применений,

которые создавались как новые системы «с нуля».

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

управления ресурсами с использованием модифицированной, построенной на

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

ляются основные классы понятий и отношений в предметной области управ-

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

приятия, что в свою очередь позволяет создать унифицированную мульти-

агентную систему, настраиваемую посредством прикладных онтологий и он-

тологических моделей предприятий на каждое конкретное применение. Да-

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

для решения сложных задач управления ресурсами, включая новые классы

агентов, их целевые функции и протоколы переговоров.

В шестом разделе представлена структура инструментального комплек-

са для создания ИСУР, включающего базу знаний на основе онтологий для

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

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

планов.

В седьмом разделе рассматривается пример создания прототипа ИСУР

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

рования Земли. Показаны функции системы, представлены результаты мо-

делирования для исследования качества и эффективности разработанного

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

скими методами. Обсуждаются особенности коллективного поиска агентами

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

ния и разрешения конфликтов между агентами и проведения переговоров с

взаимными уступками для достижения консенсуса.

В восьмом разделе по результатам проведенных компьютерных экспери-

ментов делаются выводы и даются рекомендации по созданию и исследова-

нию ИСУР для практических применений. Формулируется подход к оценке

качества и эффективности моделей и методов адаптивного построения рас-

писаний, который может стать основой расчета экономического эффекта по

внедрению ИСУР.

В заключение показываются перспективы дальнейшего развития подхода

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

Результаты настоящего исследования впервые дают системное изложение

и обобщают ранее полученные результаты, представленные в [7-13].

2. Задача адаптивного управления ресурсами предприятий

в реальном времени

Управление ресурсами предприятия предполагает связанное решение за-

дач организации деятельности, планирования и оптимизации ресурсов, обес-

печения производственных процессов работы всем необходимым, мониторин-

га и контроля хода исполнения задач, а также развития предприятия [2, 14].

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

ном времени, связанных с грузовыми перевозками и мобильными бригадами,

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

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

мерность пространства поиска решений.

— Управление грузоперевозками: от 500 грузовиков на дороге, 100 зака-

зов приходит в день в заранее не известные моменты времени, горизонт по-

ездок от одного до 30 дней и более, 5000 точек доставки, продолжительность

обработки заказа 3-15 с, критерии: время и стоимость перевозки, комфорт-

ность водителей, равномерность нагрузки на машины и водителей, социаль-

ная справедливость, соблюдение режимов работы водителей, необходимость

учета возможных задержек на погрузке или разгрузке и штрафов за опоз-

дание, различные типы грузов и оборудования, требования возврата тары,

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

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

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

— Управление фабриками: сборка двигателя самолета - 50 тыс. деталей,

30-40 цехов на предприятии, каждый цех - 150 рабочих и 300 единиц обору-

дования, ежедневно в цех поступает 10 новых заказов, одно сменно-суточное

задание рабочего может включать до 100 операций, для обработки каждой де-

талесборочной единицы требуется от 10 до 300 технологических операций, го-

ризонт стратегического планирования составляет 3-5 лет, оперативного пла-

нирования и диспетчеризации - от одного дня до 6 мес, план одного цеха

может включать до 500 тыс. связанных задач, желаемое время обработки

события - от 2 с до 5 мин, учет особенностей технологических процессов,

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

раций за счет привлечения дополнительных рабочих, возникновение брака,

наличие на складе комплектующих и материалов и т.д.

— Управление цепочками поставок: 5-7 фабрик в сети, 300 складов проме-

жуточного хранения, сотни каналов транспортировки, 1000 магазинов, изме-

няющих свои заказы на горизонте в 7-10 дней, 10 000 товаров, движущихся в

сети с разной скоростью, сотни и тысячи новых заказов, поступающих еже-

дневно, одно событие требуется обрабатывать от 20 с до 15 мин, горизонт

планирования от 3 дней до 3 мес с критериями минимизации себестоимости

производства заказов, включая стоимость производства, транспортировки и

хранения, а также минимальных штрафов за отклонение от заданных сроков

доставки с учетом изменяющегося прогноза продажи продукции.

— Управление мобильными бригадами: число событий в день: от 50 до

250 заявок, в среднем около 100 заявок; 43 бригады для обслуживания регио-

на в 3,3 млн человек; горизонт планирования — 8-12 ч (длительность смены);

требуемое время обработки события - до 1 мин; критерии принятия решений:

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

пробеге и простое, компетенция и оснащенность техникой бригады и др.

— Управление грузопотоком Международной космической станции: номи-

нальный план полета рассчитывается на 6 мес (2 экспедиции), грузопоток

и программа полета - на год, долгосрочная программа - на 3 года, исполь-

зуется 3500 типов грузов, в числе которых топливо, вода, продовольствие

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

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

типов грузов, норм потребления, объема складов на МКС и т.д. Критерия-

ми планирования являются своевременность доставки грузов, максимальное

заполнение кораблей и т.п.

— Управление оперативным движением поездов: полигон Москва-Санкт-

Петербург содержит 49 станций, 48 перегонов, 3500 блок-участков, в день

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

го планирования - не более 4 мин. План каждого поезда включает 40-50 круп-

ных операций при ограничениях на число путей на станциях, по соблюдению

интервалов движения, времени хода, продолжительности стоянок, разгона и

торможения, а также приоритетов поездов, опасности грузов и др. В тече-

ние дня может произойти до 50 непредвиденных событий (поломки путей,

задержки проездов и т.д.), обработка события - до 3 мин.

— Управление проектами: на подразделение в 150 инженеров в год мо-

жет приходиться 25-40 проектов, каждый проект предполагает не менее

300-500 задач. В день на исполнителя поступает 2-5 новых задач и возни-

кает от 5 до 20 событий: при задержке финансирования требуется маневр

по проектам, больше времени отнимает согласование технической докумен-

тации, уточняются задачи, подводят смежники и т.п. Горизонт планирования

составляет от 2-3 мес до 3 лет, расписание может содержать около 10 000 связ-

ных задач, требуемое время обработки события — от 2 с до 5 мин. Требуется

учитывать приоритеты, трудоемкость задач и связи между ними, индивиду-

альный календарь каждого исполнителя, его производительность и опыт.

Ключевым этапом сквозного процесса управления ресурсами в реальном

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

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

ное нахождение одного «глобально-оптимального» плана в интересах центра,

а согласованную выработку и синхронизацию «по ситуации» (событиям) мно-

жества «локально-оптимальных» планов участников в их взаимодействии, с

учетом того, что у каждого имеются свои собственные интересы, критерии

принятия решений, предпочтения и ограничения.

Методология такого распределенного подхода может быть естественным

путем распространена на интересы, предпочтения и ограничения не только

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

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

грузовики, комплектующие и материалы и т.п. Можно, конечно, задать во-

прос: “А зачем награждать «интересами» неживые сущности?” Ответ дан в

методологии «бережливого производства» — нужна «забота» об эффектив-

ном использовании каждой такой сущности в производственной системе, что-

бы постараться не допустить избытка, простоя или дефицита использования

каждого ресурса.

Более того, опыт практического решения представленных выше сложных

задач управления ресурсами показывает, что под «хорошим» планом следует

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

рое обеспечивает баланс интересов («консенсус») между участниками про-

цессов управления в каждой конкретной ситуации с учетом актуального для

всех на этот момент состава и значений критериев, предпочтений и ограни-

чений.

Такие собственные критерии, предпочтения и ограничения есть у заказчи-

ков, финансистов, производственников, логистов, инженеров и рабочих, води-

телей и других сотрудников предприятия, для которых типичны следующие

критерии:

— обеспечить качество выполнения работ;

— выполнить все заказы в срок;

— минимизировать себестоимость работ;

— минимизировать риски срыва заказов;

— обеспечить равномерность загрузки ресурсов;

— минимизировать стоимость исполнения заказов;

— гарантировать выплату зарплаты рабочим в конце месяца;

— вовремя выполнить ремонт оборудования и т.д.

Наличие участников со своими интересами делает рассмотренные задачи

не только многокритериальными по своей природе, но и, по определению,

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

предприятие («центр»), отстаивающий интересы объединенного «целого» в

поиске компромисса с интересами отдельных частей.

3. Краткий анализ существующих подходов к решению сложных задач

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

Традиционные информационно-управляющие системы класса Enterprise

Resource Planning (ERP) разработки таких известных компаний как SAP,

BAAN, Oracle, 1C, Галактика и многих других хотя и называются системами

планирования ресурсов предприятий, но в реальности остаются в основном

учетными системами с весьма ограниченными возможностями пакетного пла-

нирования.

Под «капотом» указанных систем обычно используются известные зару-

бежные программы CPLEX, ILOG, MOSEK, Gurobi, Knitro, Xpress Optimizer

и др., основанные на использовании классических моделей, методов и алго-

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

считается, что заказы и ресурсы заранее известны и не изменяются в ходе

вычислений, так что даже небольшое изменение ситуации вызывает необхо-

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

С ростом сложности решаемых задач бизнеса и в условиях динамического

изменения спроса и предложения на рынке практическое использование клас-

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

ционного характера принимаемых решений по управлению ресурсами с уче-

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

ских предметных знаний, известных лишь исполнителям «на земле», и других

требований участников процессов управления. Также не решают указанные

выше проблемы и известные эвристические подходы, предназначенные для

поиска допустимого решения, такие как жадные алгоритмы локального по-

иска, генетические алгоритмы, муравьиная оптимизация и т.п. [4-6, 16-19].

Кроме того, до сих пор принято считать, что все сведения о предприятии

и данные о его работе должны быть сосредоточены в центральном компью-

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

меняющихся заказов и ресурсов, а в результате должен быть создан один

общий глобально-оптимальный план всего предприятия в целом. При этом

предполагается, что обработка должна вестись в пакетном режиме на основе

единственной целевой функции, обычно отражающей интересы центра (соб-

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

вариантов в течение десятков часов вполне приемлем, а исполнители только

ждут указаний (отметим, что в ряде случаев требуется задать критерии ра-

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

правил или алгоритмами).

Но на практике ситуация обычно совершенно другая - окружающие нас

социально-технические системы становятся все более сложными и распреде-

ленными, причем «части» системы приобретают все большую автономность

в принятии решений, т.е. изначально признается, что исполнители обладают

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

ления становится согласованное взаимодействие между всеми участниками

процессов управления как по «вертикали», так и по «горизонтали».

Можно утверждать, что классические математические методы комбина-

торной оптимизации и различных эвристик с точки зрения процессов приня-

тия коллективных решений со многими участниками по-прежнему отвечают

модели консонанса (единства) ценностей, в которой всем участникам прису-

щи одни и те же критерии (ценности), в данном случае пусть сколько угодно

сложная, но одна целевая функция, как это было, например, во времена Гос-

плана СССР.

Этой модели противостоит модель принятия коллективных решений в

условиях конфронтации, как, например, во время войны или спортивных со-

стязаний, а также жесткой конкуренции, когда у каждого участника есть

свои собственные ценности и кто-то из сторон в результате своих планов дей-

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

что находит выражение и реализуется в теории игр.

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

ходят идеи поиска согласия (консенсуса), которое может строиться как по

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

тивных решений, когда у всех участников ценности могут быть разные, но в

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

компромиссы путем переговоров и взаимных уступок. Это отвечает требова-

ниям растущей сетевой экономики с совместным использованием ресурсов

(shared economy), что ведет к тотальной юберизации ресурсов.

В этой новой модели экономики и поиска согласия сочетаются возмож-

ности как конкуренции, так и кооперации заказов и ресурсов на рынке,

что отражается в недавно появившемся термине «coopetition» (от англ.

«Competition» — конкуренция и «Cooperation» — кооперация, здесь их соче-

тание). Например, небольшие грузовые компании могут конкурировать друг

с другом на рынке, но при поступлении большого заказа объединять свои

ресурсы. Если одна из таких компаний, имея все грузовики на юге, неожи-

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

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

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

терять такой заказ. Тенденция перехода от одного «глобального» плана к

«распределенному» множеству, причем непрерывно самосинхронизируемых

планов, актуальна и для одного предприятия, где подразделения также име-

ют собственные интересы и планы. В условиях неопределенности и высокой

динамики «оптимальные» производственные планы, построенные в центре

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

уровне цехов из-за неучтенных важных особенностей производственной си-

туации, которая могла измениться в ходе расчетов, что требует ручной «до-

водки» планов на рабочих местах с участием экономистов и диспетчеров,

мастеров и рабочих в цехах. Это совершенно не означает, что нет общего

плана на уровне завода в целом — такой план просто имеет приблизитель-

ную точность, а точный план может быть собран на момент выдачи запроса

на основе поступающих планов подразделений. Однако такой план в ту же

секунду устареет — в подразделениях будут происходить новые события, вы-

зывающие перестройку их планов и ресинхронизацию с другими.

Важным шагом в развитии моделей новой экономики является теория ак-

тивных систем (ТАС)

[20], развивающая идеи программно-целевого плани-

рования, в рамках которой кроме «центра» свои интересы и свободу выбора

могут иметь и «исполнители» на местах, например, при выполнении ком-

плексных проектов. При этом исполнители стремятся к выбору таких своих

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

при заданных управляющих воздействиях центра, а управляющие воздей-

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

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

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

смотрены.

В этой связи наиболее перспективными для решения сложных задач адап-

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

множества агентов при построении расписаний, где каждый агент сам при-

нимает решения, но готов идти на переговоры и уступки ради общей цели

или партнера. Такого рода модели должны предусматривать как вертикаль-

ные (центр-исполнители), так и горизонтальные (исполнитель-исполнитель)

взаимодействия для достижения коллективного баланса интересов («консен-

суса»).

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

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

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

ления, так и построения сетецентрических платформ и цифровых эко-систем

для решения задач управления ресурсами [20, 21]. Разработанные модели и

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

дач: от проектирования сложных технических изделий до понимания текстов,

распознавания образов или извлечения знаний.

В то же время проведенный анализ позволяет сформулировать следующие

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

ских методов комбинаторной оптимизации и различных эвристик:

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

сти предприятия: заказов, задач и технологических операций, станков, рабо-

чих и т.д.;

— требуется обеспечивать решение задач высокой размерности простран-

ства решений (сотни ресурсов и тысячи заказов на большой горизонт плани-

рования);

— каждый участник имеет множество индивидуальных предпочтений,

ограничений и критериев, которые еще и могут изменяться с течением вре-

мени;

— планирование заказов редко осуществляется в пакетном режиме, но все

чаще в «скользящем режиме», с наложением на исполнение уже построенных

планов;

— при появлении непредвиденных событий (поломка ресурсов или приход

новых заказов) все расписание не должно пересчитываться заново с «нуля»,

а требуется адаптивное перепланирование с разбором конфликтов;

— качество решений по управлению ресурсами зависит от момента времени

и любые задержки сразу приводят к затовариванию, простою или дефициту

ресурсов;

— необходимо уметь ситуативно балансировать интересы, чтобы добиться

взвешенного (гармоничного) решения, учитывающего интересы всех участ-

ников;

— необходимо уметь объяснить решение пользователю и дать ему возмож-

ность вмешаться в процесс планирования на любой стадии принятия реше-

ний;

— необходимо обеспечить пользователю возможность интерактивно испра-

вить только часть расписания без полного пересчета и т.п.

Таким образом, для решения поставленной задачи требуется создание но-

вого класса интеллектуальных систем управления ресурсами (ИСУР), кото-

рые реализуют цикл Деминга по управлению ресурсами, дополняя, а в пер-

спективе и заменяя, менеджеров в этой роли [15].

В отличие от традиционных ERP систем ИСУР должны управляться це-

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

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

ситуации. Например, для предприятия в начале года наивысший приоритет

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

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

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

вызывать адаптивное перепланирование ресурсов.

Эти системы призваны расширить и дополнить функции классических

ERP систем, которые на сегодня выполняют лишь функции информационно-

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

и оперативного управления.

4. Предлагаемая методология решения задач адаптивного

управления ресурсами в реальном времени

Рассмотренные задачи построения ИСУР вызывают растущий интерес ис-

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

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

операций. Начиная с 1980-1990 гг. можно отметить возрастание количества

исследований, направленных на использование мультиагентных технологий

для моделирования процесса поиска решений по построению расписаний во

взаимодействии его участников

[23-25]. В начале 2000-х годов были пред-

приняты попытки применения мультиагентных технологий для перехода к

распределенному решению задач управления ресурсами (от англ. Distributed

Problem Solving). Данный подход основан на разделении исходной сложной

задачи на несколько подзадач с последующим объединением полученных

частных решений. В это же время был выполнен ряд исследований, в которых

теория игр применялась к мультиагентным системам распределения ресур-

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

ния по исследованию операций сформировалась целая новая область решения

задач распределенной оптимизации в системах с ограничениями Distributed

Constraint Optimization Problem (DCOP)

[26]. Несмотря на то что при

этом продолжает доминировать централизованный подход «сверху-вниз», в

области планирования и оптимизации ресурсов разработаны распределен-

ные модели, методы и алгоритмы с использованием мультиагентных тех-

нологий. К ним можно отнести методы Asynchronous Distributed Constraint

Optimization (ADOPT), Optimal Asynchronous Partial Overlay (OptAPO),

Distributed pseudo-tree optimization (DPOP), Asynchronous Backtracking

(ABT), предназначенные для решения задач управления в системах, име-

ющих сетевую структуру, методы роевой оптимизации (Particle Swarm

Optimization), в которых несколько иначе трактуется понятие «роя» агентов,

и ряд других [27-29].

Однако предложенные подходы во многом остаются «централизованны-

ми» в то время, когда сами «исполнители» могли бы выявлять конфликты и

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

Переход к использованию моделей, методов и алгоритмов самоорганиза-

ции при построении расписаний был сделан в начале 2000-х годов в работах

Самарской школы мультиагентных систем в связи с разработкой концепции

сетей потребностей и возможностей (ПВ-сетей) [7-9]. Был предложен набор

базовых классов и функций агентов ПВ-сети (в том числе агентов потреб-

ностей и возможностей), разработан набор методов взаимодействий агентов

для формирования расписаний в виде «конкурентных равновесий» на вирту-

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

реализованы различные приложения по управлению ресурсами.

Суть разработанной мультиагентной технологии построения расписаний

на базе концепции ПВ-сети состоит в формировании решения любой слож-

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

потребностей и возможностей на виртуальном рынке системы.

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

ми роль потребностей могут играть заказы, которые ищут себе грузовики,

но, в свою очередь, каждому грузовику требуются водитель и топливо, а

водителю — ночлег и питание. Можно продолжить этот ряд и ввести новые

потребности и возможности следующей степени детализации процессов согла-

сованного принятия решений, например ввести потребности на техническое

обслуживание и ремонт грузовиков, смену водителей с учетом наличия у них

международных паспортов или подбор шин с учетом их пробега и состояния

трассы для предстоящей поездки.

В качестве базовых агентов, согласно холоническому подходу PROSA, бы-

ли выбраны агенты заказов, продуктов и ресурсов, штабной агент

[30]. На

этапе поиска потребностей и возможностей было предложено использовать

протоколы аукционно-подобных переговоров, построенные по типу Contract-

net протокола [31, 32].

В 2009-2010 гг. были опубликованы две монографии

[33, 34], которые

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

работы агентов на виртуальном рынке.

Модель виртуального рынка была сформулирована следующим образом:

имеется множество агентов A = {A_i}, множество целевых функций агентов

C = {C_i}, i = 1,...,n, где n - количество агентов, и набор задач T. Для лю-

бого набора задач T , функция C_i(T ) определяется как стоимость выполнения

агентом A_i всех задач T . Первоначально каждый агент выбирает некоторый

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

ляется минимальной, что приводит к неоптимальному распределению. Далее

агенты вступают в переговоры с целью улучшения распределения, вследствие

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

равновесие», которое считается решением задачи с минимальной стоимостью,

так как ни одно другое решение не приведет к улучшению результата. Пере-

говоры можно рассматривать как итеративный процесс взаимных уступок и

перестановок, на каждом шаге которого агенты заключают «контракт» для

обмена задачами и виртуальной валютой.

В [33] была доказана возможность получения глобального оптимума при

использовании предлагаемого метода для решения задачи о назначениях и

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

применения этих методов при решении более сложных NP полных задач

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

данных моделей и методов в случаях, когда классические методы оказыва-

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

к изменениям требований, возможность частичного адаптивного изменения

планов, органичность распараллеливания и масштабирования и т.д.

В России эта же методология применяется для решения задачи о балан-

сировке нагрузки в грид-сети вычислителей

[35, 36]. На примере расчетов

грид-сети из 1024 вычислителей показана возможность практического при-

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

сти, причем в условиях действия помех, когда другие методы оказываются в

принципе не применимы.

В ходе проведенных разработок был введен ряд новых классов агентов

и для каждого агента — собственные функции удовлетворенности и бону-

сов-штрафов, регулирующих их эластичность при уступках для достижения

баланса интересов. Например, цель заказа — максимально дешевое или быст-

рое исполнение, цель ресурса — максимальная загрузка, а цель продукта —

меньше пролеживать, но в зависимости от ситуации приходится идти на ком-

промиссы и разменивать стоимость на время и т.п.

В основе разработанной технологии, поддерживающей конкуренцию и ко-

операцию агентов, лежит возможность для агентов непрерывно, асинхрон-

но и параллельно разрешать возникающие конфликтные ситуации, когда

несколько заказов или задач претендуют на использование одного и того же

ресурса или продукта (или наоборот), посредством предложения выплаты

компенсаций за освобождение слота времени.

Получение компенсации позволяет уступающей стороне конфликта найти

себе новое место без потери удовлетворенности или с минимально возможной

потерей удовлетворенности при получаемой дополнительной сумме на счет

для поиска вариантов улучшения своего состояния в будущем.

Методология построения мультиагентных ПВ-сетей в интеллектуальных

системах управления ресурсами предполагает реализацию следующих прин-

ципов:

1. Автономность агентов, т.е. наличие у каждого экземпляра агента инди-

видуальных целей, критериев их достижения, предпочтений и ограни-

чений, а также состояний, отражающих контекст ситуации.

2. Наличие у агента собственных сценариев, методов и средств для до-

стижения целей, что может включать и более традиционные методы,

например методы ветвей и границ или машинного обучения.

3. Наличие прямых взаимодействий агентов в виде переговоров на вирту-

альном рынке системы, в которых выявляются конфликты, ищутся и

согласовываются варианты их разрешения путем взаимных уступок, в

частности, за счет аукционно-подобных протоколов.

4. Наряду с прямыми переговорами могут использоваться и косвенные,

опосредованные через общую сцену, содержащую контекст ситуации и

формируемое решение задачи построения расписания. При этом роль

сцены как семантической сети состоит в том, чтобы фиксировать от-

ношения между объектами предметной области, что позволяет исполь-

зовать «топологию» такой сети для сокращения перебора вариантов и

быстрого выяснения того, с какими ближайшими локальными соседями

следует разговаривать.

Наличие специальной среды, где каждый агент в любой момент време-

ни может стать активным и старается улучшить свое состояние, реаги-

руя на события и обладая проактивностью. В такой среде должен под-

держиваться параллельный и асинхронный характер работы каждого

экземпляра агента. В этих целях среда может предлагать диспетчер

агентов и желтые страницы или «меш»-коммуникацию (от англ. mesh),

без общего единого центра, где каждый агент может понять, с кем ему

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

ской сети.

Решение проблемы в виде искомого расписания выдается не в виде мно-

жества вариантов, полученных в ходе перебора вширь или вглубь и

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

функции, но как одно, «наилучшее» в данной ситуации, рациональное

решение, отражающее баланс целевых функций или интересов (консен-

сус) агентов участников, достигнутый в виде неулучшаемого «конку-

рентного равновесия» («динамического останова»), когда агенты про-

должают работать, но больше ни один агент не может улучшить свое

состояние так, чтобы при этом не ухудшить состояние других агентов

и системы в целом.

Важной особенностью архитектуры построения системы является высо-

кая «модульность» агентов, дающая возможность быстро дорабатывать

логику отдельных агентов или вводить новые классы агентов, чтобы по-

следовательно наращивать сложность системы для отражения сложно-

сти выявляемых разнообразных факторов, влияющих на качество услуг

или эффективность предприятий.

Важной задачей развития мультиагентных ПВ-сетей является созда-

ние унифицированной мультиагентной системы, поддерживающей ре-

шение задач планирования ресурсов в различных предметных областях,

и конструктора онтологий, позволяющего строить онтологические мо-

дели любых предприятий на основе базовой онтологии «Управление ре-

сурсами» и прикладных онтологий для управления ресурсами в маши-

ностроении, авиастроении, судостроении, приборостроении, микроэлек-

тронике и т.д.

Новизной технологии является возможность адаптивно пересматривать

решения, ранее принятые в ходе планирования, что в особенности важно для

работы по событиям в режиме реального времени, в сравнении с обычной

практикой first-in/first-out, когда, например, новые заказы размещаются ин-

крементально в свободные слоты времени на ресурсах, т.е. идет планирование

в «хвост» расписания.

Более подробно разработанные модели и методы рассмотрены в [12].

Разработанный подход был впервые использован в 1999 г. при построе-

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

оформления салонов автомобилей класса «люкс» на фабриках компании

Фольксваген (Германия) и в дальнейшем к 2008 г. позволил создать первое

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

ми (2002), консолидацией грузовых перевозок (2004), корпоративным такси

(2006), рекламными баннерами (2008) и т.д.

В 2010 г. началась разработка нового инструментария, на базе которого

были реализованы специализированные модели и методы построения ПВ-се-

тей, включая гибридную комбинацию классических и мультиагентных ме-

тодов для управления контейнерными грузовыми перевозками — Full Truck

Load (FTL) и частично заполненными грузовиками — Less Truck Load (LTL)

(2010), движением поездов (2012), фабриками (2014) и проектами (2015), гру-

зопотоком Международной космической станции (2016), мобильными брига-

дами (2017) и рядом других приложений.

В 2017-2020 гг. был сделан следующий шаг в развитии предлагаемого

МАС подхода и предложены новые классы программных агентов для ре-

шения сложных задач управления производственными системами, в частно-

сти предложены агенты технологического процесса и каждой задачи, введена

двухуровневая микроэкономика виртуального рынка, а также разработаны

онтологический подход и структура унифицированной мультиагентной систе-

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

5. Формализация задачи и метода адаптивного планирования в

интеллектуальных системах управления ресурсами предприятий

5.1. Онтологическая модель предприятия для настройки

унифицированной мультиагентной системы

на специфику предметной области предприятия

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

ласти предприятия выделены основные концепты и построена базовая онто-

логия управления ресурсами в форме семантической сети, состоящей из клас-

сов понятий и отношений, а также предложена методика построения онтоло-

гической модели цифрового двойника (ЦД) предприятия [37]. Общее опреде-

ление онтологии имеет вид: O =< C, R, Φ >, где C - множество понятий, R -

множество атрибутов и отношений (n-местных предикатов), Φ - множество

функций семантической обработки (интерпретации), заданных на понятиях

и отношениях. Онтологии все чаще используются при создании интеллек-

туальных систем

[38-40], но для управления ресурсами требуемые онтоло-

гии не были известны. Для построения онтологических моделей предприятий

предлагается использовать базовую онтологию управления ресурсами O_plan,

в которой на основе анализа различных производственных задач выделены

наиболее общие и повторно используемые понятия (табл. 1), в то время как

детали, зависящие от предметной области, предложено специфицировать в

прикладных онтологиях O_domain, расширяющих базовую:

O_domain ⊇ O_plan.

Таблица 1. Основные понятия базовой онтологии управления ресурсами

Понятие

Краткое описание

Заказ

Заявка на выпуск продукта, специфицирующая его количе-

ство и директивные сроки получения

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

выполнения задачи

Задача Групповая или атомарная работа (набор связанных работ),

выполнение которых необходимо для получения продукта

Ресурс Средства производства, необходимые для выполнения задачи

Онтология O_plan используется реализованными в МАС классами агентов,

которые через функции интерпретации Φ получают возможность взаимодей-

ствовать с базой знаний. Часть понятий и отношений из O_domain являются

производными от базовых понятий и отношений из O_plan, что позволяет объ-

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

тия и отношения с уже известными и интерпретируемыми системой, обработ-

ка которых встроена в ее программный код. При этом O_domain может также

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

которые будут использоваться МАС при сопоставлении свойств ресурсов и

продуктов с требованиями со стороны задач.

В предлагаемой формализованной онтологии управления ресурсами C_plan

заказы (Order) определяют количество и сроки создания продукта (P roduct),

задачи (T ask) задают необходимую последовательность действий для его

получения и специфицируют необходимые для своего выполнения ресурсы

(Resource):

C_plan = {Order,Product,Task,Resource}.

Каждый заказ требует появления продукта («создает» - create), который, в

свою очередь, связан с задачей, в результате выполнения которой он появля-

ется:

∀x∃y(Order(x) → Product(y) ∧ create(x,y)).

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

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

жено декомпозировать на «Производимые» (Produced Product) и «Потребляе-

мые» (Consumed Product). Между задачей и соответствующим видом продук-

та предложены отношения «производит» (produce) и «потребляет» (consume):

∀x∃y(ProducedProduct(x) → Product(x) ∧ Task(y) ∧ produce(y,x)),

∀x∃y(ConsumedProduct(x) → Product(x) ∧ Task(y) ∧ consume(y,x)).

Множество задач предложено разбивать на подмножества: «Групповые»

(Group Task) и «Атомарные» (Atomic Task). Задачи связаны между собой

посредством отношений вложенности («является частью» - part of ) и упоря-

доченности («следует за» - follow). Эти отношения позволяют агенту найти

Таблица 2. Базовые типы задач

Вид задачи

Параметры

Фиксированная Продолжительность задана фиксированной нор-

Атомарная длительность мой времени

Фиксированный Продолжительность зависит от состава и характе-

объем работы ристик используемых ресурсов и/или объема вы-

пускаемого продукта

Гамак

Выполняется строго между задачами предше-

ственниками и задачами последователями

Групповая

Продолжительность «покрывает» интервалы вы-

полнения дочерних задач

Таблица 3. Базовые типы ресурсов

Вид ресурса

Параметры

Преобразуемый Тратится при выполнении задачи (в количестве, определен-

ном ее требованиями), может быть восполнен согласно гра-

фику поставок

Обеспечивающий Становится доступным для повторного использования в

прежнем количестве сразу после завершения задач, на кото-

рые был выделен. Может иметь график зависимости распо-

лагаемого объема от времени.

предыдущую и следующую задачу для запроса о перемещении в расписании

или сообщения о возникшей задержке в выполнении:

∀x,y(partOf(x,y) → Task(x) ∧ Task(y)),

∀x,y(follow(x,y) → Task(x) ∧ Task(y)),

∀x∃y(GroupTask(x) ↔ Task(x) ∧ Task(y) ∧ partOf(x,y)),

∀x(AtomicTasks(x) ↔ ¬ GroupTasks(x)).

В зависимости от способа определения длительности предложено атомарные

задачи подразделять на задачи с фиксированной длительностью, с фиксиро-

ванным объемом работ и на задачи вида «гамак» (табл. 2). Ресурсы обеспечи-

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

предложено подразделять их на преобразуемые и обеспечивающие (табл. 3).

Отношение «требует» (require) указывает типы ресурсов, необходимые для

выполнения задачи. Для выбора вариантов выполнения задачи на различных

ресурсах вводится понятие «Требование к ресурсам» (Resource requirement):

∀x,y((reuire(x,y) → Task(x) ∧ (ResourceRequirenment(y) ∨ Resource(y))).

Продукты могут требовать размещения (stored):

∀x,y((stored(x,y) → Product(x) ∧ ReusableResource(y)).

Таким образом, на уровне базовой онтологии планирования фиксируется

множество отношений R, которые должны поддерживаться МАС:

R_plan = {create,consume,produce,partOf,follow,require,stored}.

Для работы с онтологиями управления ресурсами и построения баз знаний

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

тов следующие функции семантической обработки (интерпретации) Φ:

1. Concepts = φ₁(c) - получить множество всех понятий Concepts ⊆ C, яв-

ляющихся производными от указанного понятия c ∈ C.

2. Relations = φ₂(r) - получить множество всех отношений Relations ⊆ R,

являющихся производными от указанного отношения r ∈ R.

3. Instances = φ₃(c) - получить множество всех экземпляров Instances

заданного класса c ∈ C (включая экземпляры производных классов).

4. AreRelated = φ4(c1,c2) - проверить, является ли понятие c1 ∈ C про-

изводным от понятия c₂ ∈ C.

5. AreRelated

= φ₅(r₁,r₂) - проверить, является ли отношение r₁ ∈ R

производным от отношения r₂ ∈ R.

6. IsP art = φ₆(i, set) - определить, принадлежит ли экземпляр i заданно-

му множеству set, путем сравнения атрибутов и отношений экземпляра

с атрибутами и отношениями, определяющими это множество (учиты-

вая возможность замещения базового класса или отношения производ-

ным).

7. T asks = φ₇(p) - определить множество задач, результатом которых яв-

ляется получение указанного продукта p ∈ P roducedP roduct.

8. Resources = φ₈(t) - определить подходящие для выполнения задачи

t ∈ Task ресурсы.

9. P roducts = φ₉(t) - определить подходящие для выполнения задачи

t ∈ Task продукты.

В отличие от базовой онтологии управления ресурсами онтология пред-

метной области может дополняться новыми элементами без необходимости

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

работы унифицированной МАС добавляемые новые понятия, атрибуты и от-

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

тов и отношений при применении к ним функций семантической обработки Φ.

Например, на уровне онтологии машиностроения в качестве продуктов рас-

сматриваются детали (Component), сборочные единицы (AssemblyElement)

и изделия (F inalP roduct), в качестве задач - технологические процессы

(P rocess) и операции (Operation), ресурсы представлены оборудованием

(Equipment), оснасткой (T ool) и персоналом (Employee):

∀x(Product(x) → Component(x) ∨ AssemblyElement(x) ∨ FinalProduct(x)),

∀x(Task(x) → Process(x) ∨ Operation(x),

∀x(Resource(x) → Equipment(x) ∨ Tool(x) ∨ Employee(x)).

На основе прикладной онтологии строится онтологическая модель предприя-

тия:

M = {O_domain(O_plan,I},

Рис. 1. Пример онтологической спецификации одной операции по сборке из-

делия (цифрами указаны отношения: 1 и 6 - «предыдущая/последующая за-

дача», 2 и 5 - «вход/выход задачи», 3 - «часть/целое», 4 - «требует», 5 -

«связана», 7 - «исполнитель»).

в которую, кроме понятий и отношений базовой онтологии O_plan и приклад-

ной онтологии O_domain, рассмотренных выше, включаются дополнительные

понятия уровня предприятия, а также экземпляры I введенных ранее поня-

тий, например добавляются единицы оборудования с инвентарными номера-

ми, а также рабочие с табельными номерами, навыками и компетенциями.

На основе онтологической модели строится сцена предприятия S, кото-

рая описывает состояние предприятия и содержит значения атрибутов всех

экземпляров понятий и отношений онтологической модели предприятия для

заданного момента времени t : S = M(t). В результате применения пред-

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

семантической сети связанных между собой отношениями понятий (рис. 1),

что позволяет не только учитывать специфику каждой задачи, но и исполь-

зовать «топологию» расписания при принятии решений агентами, например,

быстрее определять состав участников переговоров, существенно сокращая

перебор вариантов и время вычислений.

Для создания ИСУР предложена методика, позволяющая формализовать

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

гические модели предприятий. Она состоит в выполнении нижеследующих

этапов:

1. Описать номенклатуру используемых и производимых продуктов или

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

и др.).

2. Описать состав и структуру производственных ресурсов.

3. Задать технологические процессы получения продуктов, представляю-

щие собой упорядоченный список задач (операций).

4. Определить критерии, предпочтения и ограничения для адаптивного

планирования заказов на ресурсы предприятия при возникновении со-

бытий рассогласования плана и факта.

5. В качестве входных данных для такой модели могут подаваться пере-

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

количестве и сроках выполнения, а также выделенные события (новый

заказ, поломка станка, задержка исполнения задачи и т.д.).

В результате предприятию ставится в соответствие его онтологическая мо-

дель, отражающая текущее состояние его заказов и ресурсов, а также пла-

ны и показатели работы на любой горизонт времени, ограниченный сроками

крайнего заказа.

5.2. Унифицированная мультиагентная система

для управления ресурсами

Рассмотрим метод работы унифицированной мультиагентной системы

управления ресурсами предприятий в составе ИСУР при переходе из теку-

щего в новое состояние при появлении очередного события.

Состояние ИСУР предприятия S_Π предлагается определить композицией

состояний s_i,i = (1, n) объектов, участвующих в производственном процессе

(заказов, продуктов, ресурсов и задач):

S_Π = {s_i},

s_i = {model_i,plan_i,kpi_i},

где: model_i - онтологическая модель объекта; plan_i - план работы объекта,

kpi_i - показатели эффективности его работы. Если обозначить как S_real со-

стояние реального предприятия, то необходимо, чтобы состояние реального

предприятия и состояние его ИСУР в каждый момент времени k максималь-

но совпадали:

(

)

D S(k)real,S(k)Π → 0 ,

где D - функция, показывающая степень различия онтологической моде-

ли, планов и показателей объектов ИСУР с реальным предприятием. Тогда

при появлении нового события Event(k) в реальном предприятии его ИСУР

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

го процесса по адаптивному перепланированию задач и ресурсов, задетых

событием:

S(k+1)Π = F(S(k)Π,Event(k)),

Таблица 4. Цели, предпочтения и ограничения основных классов агентов

Тип

Цели и предпочтения

Ограничения

Агент заказа

Быть выполненным с минимальной

Сроки, объем, пре-

задержкой (c) и стоимостью (p):

дельная стоимость

(

)

(

)

Y_i = w₁

+w₂

c_kp

p_kp

Агент задачи:

Быть выполненным на подходящем

Характеристики

- групповой

ресурсе в указанные сроки за мини-

требуемых ресур-

– атомарной

мальное время (τ_i = finish_i -start_i):

сов и продуктов,

⎧

сроки начала и

⎨1,

τ_i < τ_opt

окончания, взаи-

Y_i =

τ_i - τ_kp

⎩

иначе,

мосвязи c другими

τ_opt - τ_kp

задачами

Агент ресурса

Быть максимально загруженным,

Календарь рабо-

минимизировать простои и перена-

ты, интервалы не-

ладки:

доступности, пра-

⎧

u_i < u_kp

вила обслужива-

⎨0,

ния и переналадки,

Y_i =

u_i - u_kp

⎩

иначе,

производитель-

u_opt - u_kp

ность

где u_i - утилизация ресурса i

Агент продукта

Обеспечить свое хранение, миними-

Требования по хра-

зировать время между производ-

нению, время по-

ством и потреблением (ϵ):

ставки или произ-

ϵ_i

водства, время по-

Y_i = 1 -

ϵ_kp

требления

Агент системы

Выявление «узких мест» в расписа-

Время, отводимое

(предприятия в целом) нии, управление активностью аген-

на планирование,

тов системы, взаимодействие с внеш-

глубина цепочек

ними системами

перестановок в

расписании

где F - функция, адаптивно перестраивающая план работы предприятия в

ответ на поступившее событие, которую и должна реализовывать МАС. Для

решения поставленной задачи выделен модифицированный набор базовых

объектов ПВ-сети и каждому такому объекту s_i поставлен в соответствие про-

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

Определим цели каждого агента через функцию удовлетворенности

Y_i(Plan_i), представляющую собой взвешенную сумму M компонент, соответ-

ствующих различным критериям - показателям kpi_i и рассчитываемых на

основе текущего плана работы plan_i связанного с агентом объекта:

∑

Y_i =

w_i,jy_i,j,

j=1

где: yi,j - компонент функции удовлетворенности по критерию j = (1, M),

∑_M

w_i,j - весовой коэффициент, такой что 0 ≤ w_i,j ≤ 1 и

w_i,j = 1 ∀i.

(j=1)

Для автоматизации принятия решений будем использовать виртуальный

рынок ПВ-сети системы, на котором агенты заказов могут покупать время

ресурсов, и решать конфликтные ситуации, когда несколько заказов или за-

дач претендуют на использование одного и того же ресурса или продукта,

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

В зависимости от достигнутой удовлетворенности агенту начисляется пре-

мия (штраф), размер которой определяется через заданную для него функ-

цию бонусов и штрафов: B_i(Y_i). Ожидаемый бонус и текущий бюджет могут

быть потрачены агентом на выплату компенсаций агентам, которые согласи-

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

Функция удовлетворенности агента связывается с оценкой состояния объ-

екта, а функция бонусов и штрафов - с возможностями агента перестроить

расписание для удовлетворения своих интересов. Вид функций выбирается

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

лей kpi_i повышало удовлетворенность и размер бонуса агента.

Агенты ресурсов дополнительно характеризуются функцией стоимости

W_i(plan_i,kpi_i), определяющей стоимость размещения задач. Модификация

модели ПВ-сети связана с введением неоднородных классов агентов с соб-

ственными функциями удовлетворенности и функциями бонусов и штрафов,

а модификация метода сопряженных взаимодействий позволяет использовать

онтологическую модель предприятия в работе унифицированной МАС, в ко-

торой для каждого экземпляра объекта модели будут создаваться собствен-

ные экземпляры агентов для анализа ситуации, планирования ресурсов и

контроля их использования (рис. 2):

1. В соответствии с текущим состоянием ИСУР S_Π создаются экземпляры

агентов заказов, ресурсов и продуктов, которые получают разрешение

от агента системы начать активность.

2. Агент активного заказа a_k считывает из базы знаний технологический

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

тов задач, соответствующих технологическому процессу и его дочер-

ним операциям, связанных между собой отношениями вложенности и

очередности.

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

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

бирает их комбинацию на основе оценки своей продолжительности.

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

ресурсов, сопоставление требований задач и возможностей ресурсов, со-

гласование времен доступности всех ресурсов, выбор лучшей комбина-

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

5. По мере подбора ресурсов определяется множество заказов {a_i | i = k,

plan′k ∩ plani = 0}, мешающих размещению на выбранных ресурсах

(конфликтное множество), что определяет направленный характер про-

водимого перебора и существенно сокращает число вариантов.

O₃

O₄

O₅

O₄

O₅

O₂

R₁

R₂

O₁

O₂

O₃

O₁

Агенты

Агент заказа О₁

Агент ресурса R₁

конфликтующих

заказов О₂ и О₂

Запросить возможность

освобождения R₁

Выбрать

Найти вариант

указанное время по списку

альтернативный

размещения, рассчитать

конфликтующих заказов

вариант

стоимость

Сообщить размер

компенсации

Нет

B достаточно

для выплаты

компенсации?

Да

Инициировать

Подтвердить

перестановку

Рис. 2. Фрагмент протокола переговоров по разрешению конфликтов.

После выбора варианта размещения агент групповой задачи отправляет

запрос на планирование агентам дочерних задач.

Агенты дочерних задач рекурсивно проводят поиск вариантов разме-

щения с учетом установленных родительской задачей ограничений. Ре-

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

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

чам найти другое размещение.

Агент верхней задачи сообщает агенту заказа о выбранном размещении.

Агент заказа предлагает конфликтующим заказам найти себе другое

место в расписании, сообщив потери, которые им пришлось понести, по

сравнению с базовым (отправным для текущей версии плана) вариан-

том расписания (рис. 1). В результате определяется цепочка переста-

новок, рассчитываются потери агентов ΔB_i, которых затронули изме-

нения. Цепочка перестановок успешна, если агент заказа может ком-

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

приросту функции бонусов и штрафов ΔB_k :

∑

ΔB_k ≥ ΔB_i.

i=k

В этом случае изменение утверждается, иначе - ищутся другие вариан-

ты.

10.

Агент заказа проверяет наличие связанных с ним отношением «Произ-

водится» продуктов и оповещает их агентов о сроках поставки на склад.

11. Процесс завершается, если вышло время, отводимое на построение рас-

писания, или достигнуто условие «конкурентного равновесия» (консен-

суса), которое состоит в том, что для любого агента a_k больше не на-

ходится такого изменения плана работы plan^′k, которое привело бы к

приросту удовлетворенности ΔY_k и, как следствие, увеличению значе-

ния функции бонусов и штрафов ΔB_k, что смогло бы компенсировать

суммарные потери остальных агентов a_i, затронутых этим изменением

и нашедших другой вариант размещения plan^′i, минимизирующий их

потери и согласующийся с ранее принятыми изменениями:

∑

ΔB_k + ΔB_i < 0 ∀k.

i=k

12. По достижению консенсуса ИСУР приостанавливает свою работу, вы-

дает построенный новый план исполнителям и переходит в режим ожи-

дания новых событий.

Существенным фактором, снижающим вычислительную сложность алго-

ритма, является использование направленного поиска вариантов перестано-

вок при адаптивной перестройке расписания, при котором взаимодействие

происходит в основном между конфликтующими заказами.

6. Инструментальный комплекс для создания ИСУР

Для автоматизации процессов построения ИСУР разработаны функции

и архитектура комплекса инструментальных средств. В состав комплекса

включен конструктор онтологий (КО) и баз знаний (КБЗ) предприятия

(включает как классы, так и экземпляры понятий), конструктор сцен, уни-

фицированная МАС управления ресурсами в реальном времени, очередь со-

общений и средства взаимодействия с пользователем (рис. 3).

Основное назначение КО - построение, редактирование и хранение базо-

вой и прикладных онтологий, а также предоставление программного доступа

к этим данным. КБЗ предназначен для формирования онтологических моде-

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

Унифицированная МАС управления ресурсами обеспечивает создание и

настройку виртуального мира агентов под заданную онтологическую модель

каждого предприятия. На основе онтологической модели в виртуальном мире

ИСУР предприятия создаются экземпляры классов агентов для каждой сущ-

ности конкретного предприятия (заказа, станка, технологии, изделия, сотруд-

ника и т.д.) и обрабатываются события, поступающие через очередь событий

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

МАС являются адаптивное перепланирование расписания выполнения зака-

зов с достижением нового консенсуса агентов по каждому событию, а также

последующий мониторинг и контроль их исполнения. Исходные данные, ре-

зультаты перепланирования и показатели работы МАС размещаются в сцене

Экспертные знания об

управлении ресурсами

События

предприятий

Интерфейс пользователя

Базовая онтология

(план, показатели эффективности, лог

управления ресурсами

событий, журнал решений)

(заказ, задача, ресурс и др.)

Конструктор

Прикладные онтологии

(машиностроение,

онтологий и баз

Конструктор сцен

знаний

Сцены (планы

бурение, ДЗЗ и др.)

(PostgreSQL)

предприятия

показатели и др.)

(MongoDB)

Онтологические модели

предприятий

МАС управления ресурсами

Иркут ГПН СТТ Групп

Иркут

ГПН

СТТ Групп

Рис. 3. Структура инструментального комплекса создания ИСУР.

мира агентов, которая содержит массивы данных истории, текущего состоя-

ния и планов работы ИСУР, показатели эффективности.

Веб-интерфейс пользователя включает в себя набор визуальных компо-

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

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

мир агентов ИСУР, содержащий экземпляры основных агентов, и сцену (на-

бор массивов) данных, отражающую параметры состояния объектов пред-

приятия.

В любой момент времени ИСУР предприятия может быть скопирована

в отдельную версию для перехода к режиму моделирования «Что будет, ес-

ли. . . ?», чтобы предсказать реакцию ИСУР на события, которые ожидаются,

но пока еще не случились (приход нового крупного заказа, ввод в действие

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

Разработанный комплекс был использован для решения прикладных задач

управления ресурсами:

— агрегатно-сборочного производства самолетов МС-21 для ОАО «Ир-

кут»;

— сборочного производства грузовых электромобилей для ООО «ТРА»;

— бурения нефтедобывающих скважин для ООО «Газпромнефть-Ямал»;

— выращивания посевов растений для ОАО «Рассвет»;

— целевого применения группировки КА ДЗЗ для «СТТ-Групп».

Исследование применения разработанного комплекса показало существен-

ное снижение сложности и трудоемкости разработки ИСУР. При этом для

каждого созданного ИСУР оценивался объем изменений, вносимых в базовую

Таблица 5. Результаты применения комплекса для создания ИСУР предприятий

Число классов понятий

Время на

Кол-во

разработку

Задача

и отношений

агентов

(чел/м)

O_plan

O_domain

БЗ МАС

Сборка самолетов

152

925

>350

3.5

Сборка грузовиков

382

>520

Бурение скважин

382

>520

ЦД посевов

236

>100

Группировка КА

112

304

> 450

онтологию, а также объем доработок основных классов агентов под задачу

(табл. 5).

Представленные данные показывают, что базовая онтология управления

ресурсами O_plan оказалась построена из примерно 60 классов основных по-

нятий и отношений. Прикладные онтологии расширяют состав понятий и

отношений примерно в 2-3 раза. Онтологические модели предприятия, вклю-

чающие экземпляры, имеют от 236 до 925 экземпляров. Именно эти модели

и загружаются в ИСУР, позволяя автоматически создать требуемое число

агентов. Трудоемкость доработки унифицированной ИСУР для каждого из

указанных применений составила в среднем 2-3 мес, что по экспертным оцен-

кам позволяет в 3-4 раза сократить сроки и стоимость создания ИСУР в

сравнении с традиционным подходом.

7. Пример построения ИСУР для решения прикладной задачи

7.1. Постановка задачи для управления

спутниковой группировкой ДЗЗ

Рассмотрим применение разработанного подхода для создания ИСУР

управления многоспутниковой группировки космических аппаратов (КА) для

дистанционного зондирования Земли (ДЗЗ). В основе управления группиров-

кой КА лежит задача адаптивного планирования полетных операций по зака-

зам на съемку объектов ДЗЗ, поступающим в заранее не известные моменты

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

никающим в заранее не известные моменты времени. Пусть задана упрощен-

ная модель космической системы (КС) для решения задач ДЗЗ, представляю-

щая собой совокупность двух сегментов: космического комплекса и наземного

комплекса. Космический комплекс выполняет функции получения и переда-

чи информации, наземный комплекс - функции приема-передачи и обработки

передаваемой информации. Космический комплекс состоит из множества КА

S = s_i,i = 1,L. Каждый КА s_i характеризуется набором элементов орбиты

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

комплекс представлен множеством наземных станций приема информации

(НСПИ) G_R = {g_r}, r = 1, R. Каждая станция g_r характеризуется географи-

ческим местоположением и параметрами установленной антенны. Для НСПИ

и КА могут быть указаны ограничения в виде графика работы и интерва-

лов недоступности. КС должна обеспечить выполнение множества заявок на

съемку точечных и площадных объектов наблюдения (ОН) O = {o_p}, p =

= 1, P . Для заявки на съемку o_p может быть указан ее приоритет pr_p (заявка

с низким приоритетом не должна мешать оптимальному расположению бо-

лее высокоприоритетной заявки) и множество ограничений: момент времени,

до которого необходимо получить снимки t^epnd, коэффициент баланса между

оперативностью и качеством получаемой информации c_p (задается в диапа-

зоне от 0 до 1), минимальное и желаемое линейное разрешение полученного

снимка min Rp и max Rp. В рассматриваемой модели КС КА выполняет две

операции:

— съемка некоторой области sa_jshoot_j , характеризующаяся интервалом

выполнения t^shootj = [t^shootStartj; t^shootEndj] и углом крена КА sAngle_j ;

— проведение сеанса связи КА с НСПИ с целью передачи полученных

данных на Землю drop_j, характеризующегося интервалом выполнения t^dropj =

= [t^dropStartj; t^dropEndj].

НСПИ в свою очередь выполняет одну операцию - получение дан-

ных с КА receiv_j , характеризующуюся интервалом выполнения trecivej =

= [t^reciveStartj, t^reciveEndj].

Для реализации космической съемки ДЗЗ на основе заявок, поступаю-

щих от потребителей, требуется сформировать комплексный план выполне-

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

ствии с критерием минимизации времени доставки снимков потребителям, а

также максимизации их качества. Таким образом, целевая функция системы

имеет вид: t^receivj = [t^receivStartj; t^receivEndj].

∑

OF =

OF_k → max,

k=1

OF_k = c_kFk1 + (1 - c_k)Fk2 → max,

dropEnd

t^endk - t

Fk1 =

t_kend - t^start

⎧

⎪

min R_k - r_k

⎨

, если r_k ≥ max R_k

min R_k - max R_k

Fk2 =

⎪

r_k

⎩

иначе,

max R_k

где

OF - целевая функция системы,

OF_k - целевая функция k-й задачи,

N - количество запланированных съемок,

Fk1 - оценка критерия оперативности получения информации для k-й за-

дачи,

Fk2 - оценка критерия качества полученного снимка для k-й задачи,

t^startk,t^endk - горизонт планирования для k-й задачи,

r_k - фактическое линейное разрешение полученного снимка для k-й зада-

чи.

Примем, что на полученное решение накладывается ряд ограничений:

— выполнение условия наблюдаемости между КА и ОН при съемке;

— наличие радиовидимости между КА и НСПИ при передаче результатов

съемки;

— наличие свободного места в бортовом запоминающем устройстве (ЗУ)

КА;

— выполнение условия приоритезации заявок;

— согласованность последовательности моментов времени проведения опе-

раций;

— КА и НСПИ могут одновременно выполнять не более одной операции.

7.2. Функциональные возможности прототипа ИСУР

для решения задач ДЗЗ

Разработанный прототип системы предназначен для составления и адап-

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

съемке точечных и площадных районов средствами группировки КА при

заданных критериях эффективности и технических характеристиках КА и

НСПИ, принятой модели обстановки и внешней среды, а также для модели-

рования КС при изменении ее состава и конфигурации.

Система обеспечивает следующие основные функции:

— загрузка исходных данных о составе и параметрах элементов КС;

— загрузка заявок на съемку точечных и площадных ОН;

— составление локально-оптимального плана работы КС (группировки КА

и НСПИ) при заданном составе технических характеристик;

— адаптивное перестроение локально-оптимального плана работы КС по

событиям, изменяющим характеристики КС (состав КА и НСПИ, техниче-

ские характеристики систем КА и НСПИ, добавление ограничений работы

КА и НСПИ, изменение критериев планирования), изменяющим исходные

данные по съемке точечных и площадных районов;

— визуальное моделирование процесса выполнения заявок ДЗЗ, приема и

передачи данных на наземные станции;

— формирование графиков и диаграмм, отображающих результаты пла-

нирования;

— выгрузка полученного локально-оптимального плана работы КС.

Система создается для эксплуатации в профильных подразделениях Цен-

тра управления полетами (ЦУП) и обеспечения поддержки принятия реше-

ний по планированию использования группировки КА.

7.3. Экспериментальные исследования ИСУР для решения задач ДЗЗ

Для проведения экспериментальных исследований и оценки степени при-

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

ми КА в реальном времени использовалась модель КС, в состав космического

комплекса которой входит группировка из 30 идентичных КА, а наземный

комплекс системы представлен сетью из 10 НСПИ. Моделировался случай-

ный поток заявок на съемку объектов ДЗЗ, и результаты планирования под-

вергались автоматизированной обработке с участием экспертов. Эксперимен-

ты проводились на персональном компьютере с центральным процессором

Intel Core i7-3770 (4 ядра/8 потоков, 3.4ГГц) и оперативным запоминающим

устройством 8Гб под управлением операционной системы Windows 10.

7.3.1. Анализ хода и результатов планирования в ИСУР для ДЗЗ

В данном исследовании производился сбор статистической информации

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

строения. На ее основе построены ряд графиков и гистограмм. На рис. 4

изображены графики с историей изменения значения текущей и предельной

целевой функции системы с момента начала планирования, при помощи ко-

торых можно оценить отклонение текущего значения целевой функции (ЦФ)

системы от ее максимально возможного значения:

∑

limOF =

OF_k(iw˙o_k),

k=1

где

limOF - максимально возможная ЦФ системы, M - общее число задач,

N -число рассмотренных задач, (

wo_k) - вариант размещения, расположен-

ный в точке глобального оптимума ЦФ k-й задачи.

1,0

0,9

0,8

0,7

0,6

0,5

0,4

0,3

0,2

0,1

100

120

140

160

180

Время планирования, с

Текущая ЦФ

Предельная ЦФ

Рис. 4. Графики изменения значения текущей и предельной ЦФ в ходе пла-

нирования.

Рис. 5. Число перестановок задач на каждой итерации проактивного плани-

рования.

1400

1200

1000

800

600

400

200

Количество вариантов

Рис. 6. Распределение числа вариантов размещения задач лучше текущего,

на котором она запланированы.

На рис. 5 изображена диаграмма распределения числа вариантов разме-

щения задач лучше текущего, на котором они запланированы, т.е. вариантов

размещения, найденных в ходе планирования, для которых ЦФ задачи боль-

ше ее текущего значения, но на которых задача не смогла разместиться в

результате конфликтов с другими задачами. Из анализа данной диаграммы

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

них ресурсе, а более половины оставшейся части задач расположены в 30%

лучших вариантов, что говорит об относительно «хорошем» качестве постро-

енного плана.

Столбиковая диаграмма распределения числа перестановок задач на каж-

дой итерации проактивного планирования (рис. 6) демонстрирует его быст-

рую сходимость, так, число перестановок уже на второй итерации планиро-

вания меньше числа перестановок на первой итерации в 7 раз.

7.3.2. Исследование адаптивности получаемого

в ИСУР расписания ДЗЗ

В данном исследовании оценивалась способность метода к адаптации рас-

писания по «разрушающим» событиям, в частности по выходу из строя од-

ного из КА.

В качестве исследуемого параметра здесь рассматривалось время, затра-

ченное на перепланирование, и качество полученного расписания. Для этого

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

валось выполнение 3000 заявок на съемку ОН, сгенерированных случайным

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

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

КА и измерялись время, затраченное на перестроение расписания, измене-

ния значения ЦФ системы и количество запланированных заявок. Результа-

ты экспериментов представлены в табл. 6.

Результаты эксперимента показывают, что выход из строя одного из КА

привел к резкому падению значения ЦФ системы в среднем на 0,1 и необхо-

димости поиска новых вариантов размещения для 409 заявок. В ходе пере-

строения расписания на другие КА было перепланировано 403 заявки, что

составляет 98% от числа заявок, которые были запланированы на удален-

ный КА. В результате восстановления расписания значение ЦФ повысилось

до 0,69, что меньше исходного всего на 0,04.

Среднее время перепланирования при этом составило около 9 с.

Таким образом, применение мультиагентного подхода при планировании

позволяет оперативно, гибко и эффективно парировать возникновение внеш-

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

Таблица 6. Результаты экспериментов по исследованию способности системы к

адаптации расписания

Время

После выхода из строя

После перестроения

№ перепланирования,

КА

расписания

Кол-во

ЦФ

распланированных

ЦФ перепланированных

заявок

422

-0,11

418

0,07

379

-0,10

371

0,04

468

-0,11

465

0,08

411

-0,10

406

0,07

407

-0,11

396

0,06

425

-0,11

422

0,09

397

-0,11

395

0,06

388

-0,10

376

0,05

377

-0,07

372

0,05

419

-0,10

417

0,06

7.3.3. Анализ эффективности в сравнении с алгоритмами планирования,

основанными на традиционных методах оптимизации

В данном исследовании проводился анализ эффективности разработанно-

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

диционных методах оптимизации, таких как алгоритм имитации отжига, ал-

горитм Late Acceptance Hill Climbing и алгоритм Tabu Search, по качеству

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

ление.

В ходе исследования проведена серия экспериментов, в которых количе-

ство заявок на съемку ОН изменялось от 100 до 20 000. При этом измерялось

время, затраченное на составление плана, и значение ЦФ системы.

Рис. 7. Число перестановок задач на каждой итерации проактивного плани-

рования.

Рис. 8. График зависимости времени планирования от количества заявок.

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

мости значения ЦФ системы (рис. 7) и времени планирования (рис. 8) от

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

ма имитации отжига и алгоритма Tabu Search результаты получены лишь

до 5000 заявок на съемку, так как далее наблюдался экспоненциальный рост

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

Результаты экспериментов показывают, что в данном случае уже на за-

дачах малой размерности ДЗЗ для группировки КА предлагаемый мульти-

агентный метод не уступает традиционным эвристическим алгоритмам, а с

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

писания без потери в качестве, продолжая работать там, где классические

методы уже работают плохо или вовсе не работают.

8. Выводы по результатам

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

традиционно возникает ряд вопросов: “А чем отличается метод? При каких

условиях следует его применять? Как новый метод дополняет существую-

щие решения? Что с чем сравнивать и при каких условиях? Какой выигрыш

получается в результате и т.д.?”

Ответы на эти вопросы не всегда очевидны и в ходе проведенных иссле-

дований по оценке качества и эффективности работы ИСУР по сравнению с

классическими и эвристическими системами был выявлен ряд особенностей,

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

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

тия решений в реальном времени:

— Оценка качества и эффективности результатов работы традиционных

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

и ресурсы известны заранее и не меняются в ходе вычислений, в сравнении с

адаптивными методами ИСУР, работающими по событиям в реальном време-

ни. Напрямую сделать такое сравнение часто затруднительно, так как тра-

диционное решение оптимизирует одну целевую функцию, а предлагаемый

подход в ИСУР позволяет искать баланс интересов между многими функция-

ми. В этих целях критерии принятия решений, предпочтения и ограничения

всех участников должны быть сопоставимы, но в ИСУР много больше число

участников, принимающих решения, которые при этом еще и должны быть

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

леко получаемое решение ИСУР от глобального «оптимума», предлагаемого

имеющимися методами как «лучшее решение». Но главная проблема состо-

ит в том, что для адаптивных методов качество и эффективность решения

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

рая сложилась на этот момент в группировке КА, цехе машиностроительного

предприятия, парке грузовиков и т.д. В следующий момент ситуация может

измениться и может быть востребовано уже другое решение, а решение, вы-

работанное в этом моменте, может уже в следующую минуту быть не лучшим

и даже может не быть применимым вовсе, что требуется учитывать в оценке

и выводах.

— Учет семантики предметной области в ИСУР выражается в возможно-

сти вводить «на лету» (без перепрограммирования) новые понятия и отно-

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

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

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

стему новых критериев, предпочтений и ограничений предметной области.

Учет семантики предметной области позволяет на практике сразу отсекать

лишние варианты и повышать «разумность» получаемых решений для ко-

нечных пользователей.

— Кроме качества и эффективности решения, для такого рода систем важ-

но сравнивать возможности масштабирования решения с ростом размерности

решаемой задачи. Здесь важно не только число обрабатываемых заказов, но

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

сурсов и использования возможностей естественного распараллеливания за-

дачи на современных серверах.

— При сравнении и выборе методов важно показывать, что предлагае-

мые адаптивные методы виртуального рынка, где переговоры как аукционы

идут параллельно и асинхронно, позволяют формировать решение итераци-

онно, причем можно управлять процессом вычислений, включая качество и

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

ции» («управляемого хаоса»), в зависимости от желаемых показателей, наи-

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

на принятие решений.

— Благодаря переговорам, в ходе которых выявляются причины отказов

агентов, предлагаемые ИСУР потенциально могут быть способны к «преодо-

лению ограничений» в случае, когда решение не находится в заданных усло-

виях, а также для выработки рекомендаций получения допустимого рацио-

нального результата в условиях даже полного отсутствия решения.

— Важнейшим аспектом сравнения обсуждаемых методов является тру-

доемкость разработки и развития ИСУР, понятность и удобство работы с

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

тодов планирования и оптимизации, так и, в особенности, для новичков-

программистов, с целью оперативной доработки системы под специфические

и постоянно изменяющиеся условия решения задачи или новые применения.

— Работа методов должна анализироваться и сравниваться в условиях

растущей сложности, неопределенности и динамики изменений в среде, свя-

зываемой с постоянным желанием пользователей внести все большее число

факторов в принятие решений.

— Несомненным преимуществом методов, использующих онтологии пред-

метной области, является устойчивость к ошибкам в наборах исходных дан-

ных, так как в реальном времени у пользователей нет времени на анализ

таких ситуаций.

— Важно обеспечивать пользователям объяснение найденных решений

и возможность удобной интерактивной доработки расписаний совместно с

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

нию, добавления новых, еще не формализованных, факторов.

Указанные особенности должны обеспечивать более рациональный выбор

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

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

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

9. Заключение

До настоящего времени не предложено единого подхода к созданию ИСУР

для решения сложных NP полных задач многокритериального адаптивного

управления ресурсами в реальном времени.

Разработанная методология построения ИСУР на основе мультиагентной

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

подходов к решению такого рода задач, который не дает глобального опти-

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

оптимальные решения в приемлемые сроки для повышения эффективности

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

сроки.

Областью применения разработанной технологии в ИСУР являются слож-

ные задачи управления ресурсами, где требуется перестраивать связанные

между собой планы работы многих исполнителей по различным событиям,

возникающим в заранее не известные моменты времени, причем «здесь и

сейчас», в реальном времени. При отсутствии неопределенности и динами-

ки и наличии заранее известных и неизменяющихся потоков заказов и пулов

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

ческими и эвристическими подходами, что позволяет создавать гибридные

ИСУР.

Повышение качества решения поставленных сложных задач в ИСУР по

сравнению с традиционными методами связывается с переходом от поиска

глобального оптимума одной целевой функции системы к поиску баланса ин-

тересов всех участников бизнеса в каждой конкретной ситуации, причем как

людей (заказчиков, исполнителей и партнеров), так и любых физических или

абстрактных сущностей, также наделяемых своими интересами (предприятие

в целом, грузовик, заказ, станок или другое оборудование и т.д.).

Эффективность решения поставленной задачи обеспечивается переходом

при создании ИСУР от последовательного комбинаторного перебора вариан-

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

собственными целевыми функциями, что позволяет агентам взаимно сужать

размерность поиска вариантов решений непосредственно в ходе разрешения

конфликтов, а решению сложной задачи - фактически, самоорганизовывать-

ся в ходе последовательных улучшений.

Предложенные модели, методы и средства создания ИСУР адаптивного

управления ресурсами в реальном времени могут стать основой открытой ин-

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

сокращения трудоемкости, сроков, стоимости разработки и эксплуатации та-

кого рода систем.

Перспективы развития направления связываются с созданием ИСУР как

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

экосистем ИСУР масштаба крупного предприятия и даже отрасли для под-

держки цепочек кооперации предприятий при решении сложных производ-

ственных задач.

СПИСОК ЛИТЕРАТУРЫ

Таха Х. Введение в исследование операций. М.: Изд. дом «Вильямс», 2005.

Новиков Д.А. Классификации систем управления // Проблемы управления.

2019. № 4. С. 27-42.

Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. М.: Изд-во

МГУ, 2011.

Handbook of Scheduling: Algorithms, Models and Performance Analysis / Leung J.

(Ed.). Chapman & Hall, 2004.

Vos S. Meta-heuristics: The State of the Art // Local Search for Planning and

Scheduling / Nareyek А. (Ed.). Germany: Springer-Verlag. 2001.

Pinedo M. Scheduling Theory, Algorithms, and Systems. Springer. 2008.

Скобелев П.О. Открытые мультиагентные системы для оперативной обработки

информации в процессах принятия решений // Автометрия. 2002. № 6. С. 45-61.

Виттих В.А., Скобелев П.О. Мультиагентные модели взаимодействия для по-

строения сетей потребностей и возможностей в открытых системах // АиТ. 2003.

№ 1. С. 177-185.

Vittikh V.A., Skobelev P.O. Multiagent Interaction Models for Constructing the

Needs-and-Means Networks in Open Systems // Autom. Remote Control. 2003.

V. 64. No. 1. P. 162-169. https://doi.org/10.1023/A.1021836811441

Виттих В.А., Скобелев П.О. Метод сопряженных взаимодействий для управ-

ления распределением ресурсов в реальном масштабе времени // Автометрия.

2009. № 2. С. 78-87.

10.

Скобелев П.О. Мультиагентные технологии в промышленных применениях: к

20-летию основания Самарской научной школы мультиагентных систем // Ме-

хатроника, автоматизация, управление. 2010. № 12. С. 33-46.

11.

Skobelev Р. Bio-Inspired Multi-Agent Technology for Industrial Applications. Multi-

Agent Systems - Modeling, Control, Programming, Simulations and Applications /

Faisal Alkhateeb F., et al. (Eds.). Austria: InTech Publishers, 2011. P. 495-522.

12.

Rzevski G., Skobelev P. Managing Complexity. London-Boston: WIT Press, 2014.

13.

Skobelev P. Towards Autonomous AI Systems for Resource Management:

Applications in Industry and Lessons Learned // Y. Demazeau et al. (Eds.).

Proceedings of the 16th International Conference on Practical Applications of Agents

and Multiagent Systems (PAAMS 2018). 2018. LNAI 10978. P. 12-25.

https://doi.org/10.1007/978-3-319-94580-4_2

14.

Мескон М., Альберт М., Хедоури Ф. Основы Менеджмента / пер. с англ. М.:

Дело, 1997.

15.

Деминг Э. Менеджмент нового времени: Простые механизмы, ведущие к росту,

инновациям и доминированию на рынке / пер. с англ. М.: Альпина Паблишер.

2019.

16.

Merdan M., Moser T., Sunindyo W., Biffl S., Vrba P. Workflow scheduling using

multi-agent systems in a dynamically changing environment // J. Simulation. 2012.

Vol. 7(3). P. 144-158.

17.

Deng L., Lin Y., Chen M. Hybrid ant colony optimization for the resource-

constrained project scheduling problem // J. Syst. Engineer. Electron. 2010. Vol. 21.

Issue 1. P. 67-71.

18.

Jaberi M. Resource Constrained Project Scheduling Using Mean Field Annealing

Neural Networks // Int. J. Multidisciplin. Sci. Engineer. 2011. Vol. 2. No. 7. P. 6-12.

19.

Zhang H., Xu H., Peng W. A Genetic Algorithm for Solving RCPSP // International

Symposium on Computer Science and Computational Technology (ISCSCT ’08).

2008. Vol. 2. P. 246-249.

20.

Бурков В.Н., Новиков Д.А. Теория активных систем: состояние и перспектива.

М.: Синтег, 1999.

21.

Ivanyuk V., Abdikeyev N., Patshenko F., Grineva N. Network-Centric Methods

Management

// Management Science. M.: Financial University under the

Government of Russian Federation. 2017. Vol. 7(1). P. 26-34.

22.

Chigani A., Jamed D., Bohner S. Architecting Network-Centric Software Systems:

A Style-Based Beginning // 31st IEEE Software Engineering Workshop (SEW ’07).

P. 290-299. https://doi.org/10.1109/SEW.2007.95

23.

Wooldridge M., Jennings N. Intelligent agents: Theory and practice // The

Knowledge Engineering Review. 1995. Vol. 10(2). P. 115-152.

24.

Городецкий В.И, Грушинский М.С., Хабалов А.В. Многоагентные системы //

Новости искусственного интеллекта. 1998. № 2. С. 64-116.

25.

Пантелеев М.Г., Пузанков Д.В. Интеллектуальные агенты и многоагентные си-

стемы. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2016.

26.

Pearce J., Tambe M., Maheswaran R. Solving multiagent networks using distributed

constraint optimization // AI Magazine. 2008. 29(3).

Available from: http://teamcore.usc.edu/papers/2008/K-optimality

27.

Modi P.J., Shen W., Tambe M., Yokoo M. ADOPT: Asynchronous distributed

constraint optimization with quality guarantees // Artificial Intelligence Journal.

2005. 161 (1-2). P. 149-180.

28.

Petcu A. A class of Algorithms for Distributed Constraint Optimizations. Frontiers

in Artificial Intelligence and Applications. IOS Press. 2009. 194(1).

https://doi.org/10.5075/epfl-thesis-3942

29.

Evolutionary Multiobjective Optimization Theoretical Advances and Applications.

Abraham A., Jain L. C., Goldberg R. (Eds.). Springer. 2005.

https://doi.org/10.1007/1-84628-137-7

30.

Brussel H., Wyns J., Valckenaers P., et al. Reference Architecture for Holonic

Manufacturing Systems: PROSA // Computers in Industry. 1998. No. 37. P. 255-274.

31.

Sandholm T., Lesser V. Issues in Automated Negotiation and Electronic Commerce:

Extending the Contract Net Framework - In Proc. of the First International

Conference on Multiagent Systems (ICMAS-95). 1995. P. 328-335.

32.

Sandholm T., Lesser V. Leveled-commitment contracting: a backtracking instrument

for multiagent system // AI Magazine. 2002. Vol. 23(3). P. 89-100.

33.

Shoham Y., Leyton-Brown K. Multi-agent systems: Algorithmic, Game Theoretic

and Logical Foundations. Cambridge University Press.

2009. Available from:

http://www.masfoundations.org

34.

Easley D., Kleinberg J. Networks, Crowds, and Markets: Reasoning about a

Highly Connected World. Cambridge University Press.

2010. Available from:

http://www.cs.cornell.edu/home/kleinber/networks-book/

35.

Amelina N., Fradkov A., Jiang Y., Vergados D. Approximate Consensus in

Stochastic Networks With Application to Load Balancing // IEEE Transactions

On Information Theory. 2015. Vol. 61. No. 4. P. 1739-1752.

36.

Ivanskiy Y., Amelina N., Granichin O., et al. Optimal Step-Size of a Local

Voting Protocol for Differentiated Consensuses Achievement in a Stochastic Network

with Cost Constraints // IEEE Conference on Control Applications (CCA). 2015.

P. 1367-1372.

37.

Жиляев А.А. Онтологии как инструмент создания открытых мультиагентных

систем управления ресурсами // Онтологии проектирования. 2019. Т. 9. № 2(32).

С. 261-281.

38.

Minhas S. Ontology Based Environmental Knowledge Management - A System to

Support Decisions in Manufacturing Planning // 6th International Conference on

Knowledge Engineering and Ontology Development. 2014. P. 397-404.

39.

Järvenpää E., Siltala N., Hylli O., Lanz M. The development of an ontology

for describing the capabilities of manufacturing resources // Journal of Intelligent

Manufacturing. 2019. Vol. 30. P. 959-978.

40.

Хорошевский В.Ф. Проектирование систем программного обеспечения под

управлением онтологий: модели, методы, реализации // Онтология проектиро-

вания. 2019. Т. 9. № 4. С. 429-448.

41.

Rojko A. Industry 4.0 Concept: Background and Overview // International Journal

of Interactive Mobile Technologies. 2017. Vol. 11(5). P. 77-90.

42.

Leitao P., Karnouskos S., Ribeiro L., et al. Smart agents in industrial cyber-physical

systems // Proc. IEEE. 2016. Vol. 104(5). P. 1086-1101.

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

Поступила в редакцию 27.10.2020

После доработки 15.05.2021

Принята к публикации 30.06.2021