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

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

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

1 Формализация задачи планирования работ

В работе рассматривается ПП, выполняющее множество проектов (контрактов) C = { C 1 , C ₂ , ..., C p } в определённом плановом периоде, делящемся на месяцы и представляющем собой множество T = { T 1 , T 2 , ..., T _c }. Каждый контракт C i - это выпуск одного или нескольких конечных продуктов или оказания услуг. В данной задаче принято, что результаты деятельности ПП представляются множеством продуктов P = { P 1 , P ₂ , ..., P d }. Для каждого продукта P j существует множество операций O ij = { O ij 1 , O ij ₂ , ., O ijo }. Каждая операция O ijk характеризуется трудоёмкостью L ijk - объёмом трудовых затрат (нормо-часов), необходимых для её выполнения. Набор операций может иметь технологические или логические отношения предшествования, при которых O a <  O b означает необходимость завершить операцию O a до начала O b . Для выполнения операций O ijk имеется множество ресурсов R = { R 1 , R ₂ , ., R y }. Ресурсом в данном случае является рабочее время отдельных работников определённой квалификации, участвующих в выполнении данной операции O ijk . Каждый ресурс R n обладает календарём доступности: в каждый дискретный период планирования T ресурс R n может быть использован в размере y 'nt не более заранее задаваемого объёма норма-часов y_nt. При этом каждый y nt обладает заранее задаваемой стоимостью S nt .

Решение задачи планирования заключается в определении:

• ■    распределения ресурсов R по всем требуемым операциям O ;

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

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

Y ⁽ⁿ, ^ - I

Xijk =

• 1,    если операция O ijk начинается в период t на ресурсе R n ,

• 0, иначе.

Решение должно удовлетворять следующим ограничениям:

• ■    суммарные выделенные ресурсы на каждую операцию O ijk должны быть равны трудоёмкости L ijk ;

• ■    для любого ресурса R n в каждом периоде T _t суммарная нагрузка от всех назначенных операций не превосходит доступного R i ;

• ■    соблюдение отношения предшествования;

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

• ■    суммарная стоимость всех используемых ресурсов R должна находиться в рамках задаваемых границ бюджета: В_тinijk <  Ine^terVn_ty'_n) < B_maxijk.

В рассматриваемых условиях ПР можно сформулировать следующие критерии оптимальности f:

• ■    для каждой C i :

  ^тт^^тах^ 2

  
  

fi - минимизация отклонения от целевого бюджета контракта Вaargеt f'i - максимизация выполнения контракта внутри целевого периода выполнения TARGET; f"i - максимизация равномерности распределения нагрузки между R;

• ■    для каждого P ij :

^nzin, • • + ^тпах • *

fj - минимизация отклонения от целевого бюджета продукта В_targеt.. = ---¹—^-----;

f"y - максимизация выполнения продукта внутри целевого периода выполнения T _TARGETij ; f'"ij - максимизация равномерности распределения нагрузки между R ;

• ■    для каждого O ijk :

f jk - минимизация отклонения от целевого бюджета операции В_{aar gеt}  = ---^---—;

fjk - максимизация выполнения операций внутри целевого периода выполнения T _TARGETijk ; f"jk - максимизация равномерности распределения нагрузки между R .

В зависимости от выбранного метода многокритериальная задача может иметь разную целевую функцию. Например, используя метод линейной свёртки критериев, можно получить функцию: = = тax^l=1Wff.+ ^i=1Wff ''.+ Sf=iWf f'''.), где Wb - вес критерия соответствия целевому бюджету, Wt - вес критерия соответствия целевому периоду, Wc - вес критерия равномерности распределения нагрузки.

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

| Определение пользовательских ролей j

Обновляется ежемесячно

Регистрация пользователей

[ Ввод данных по Периодам |

[Ввод данных по Группам работников| [ Ввод данных по всем Контрактам ]

При каждом расчете

Обновлять по мере необходимости

Ввод данных по [ всем Работникам |

Ввод данных по доступному времени в месяце у каждого Работника

Ввод данных по всему перечню Продукции/этапов

Ввод данных по всем Операциям

Необходимо делать лишь на старте проекта

Автоматический процесс зматизированный процесс

Рисунок 1 - Алгоритм работы лица, принимающего решение, в мультиагентной СППР

I Ввод данных по стоимости часа каждого Работника

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

IDEF0 -диаграмма (см. рисунок 2) переносит эту цепочку в терминологию « Input – Control – Output – Mechanism », демонстрируя действия ЛПР, точки передачи данных и механизмы управления на каждом этапе работы.

распределений по изделиям

Данные (Название, 13 -тип, заказчик .1 даты нач. и конца)

j । _Тскутие договора

(сок Продуктов-

Формирование

Определение

Раб.

pic01НИКОЕ

Работников по периодам

Групп Работников

А4

Распределение сотрудников по функциональным ----,

18 — Перечень

Работников Данные (ФИО.

19—ДОЛЖНОСТЬ.—► таб. номер, прим.)

контрактов

Формирование перечня Продуктов для каждого Контракта

। Данные по Операциям для каждого Продукта (Название, длительность)

Формирование перечня Операций для каждого Продукта с указанием трудоемкости и Групп работников

Создание планов распределения по Продуктам

Формирование

Определение планируемого времени и

Итоговый отчет с общим планом по периоду

Плановое время стоимость час? Работников

Формирование итогового отчёта с результатами планир станин по со ответ ствующеьу

Производственный

Рисунок 2 – Схема процесса планирования работ с помощью мультиагентной СППР

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

• ■    перцептивная нагрузка - объём и гетерогенность информации, актуальной для ЛПР, формально оцениваемые по подграфу ОМ, релевантному текущему контексту выбора: к_регс = 1^1 + 1^1, где V_s , E_s - множества вершин и рёбер подграфа;

• ■    нагрузка памяти - число одновременно активных ограничений и правил, влияющих на решение: k_wm = Е геь w_r, где L - множество ограничений, w_r - «когнитивный вес» ограничения;

• ■    комбинаторная сложность выбора - мощность множества альтернатив А и их неопределённость: к _{с 0 т ь} = ¹ А¹.

С целью повышения прозрачности процесса принятия решения и повышения уровня когнитивной поддержки ЛПР, предлагаемое решение должно предоставлять ЛПР:

• ■    ОМ всех сущностей и взаимоотношений ПрО;

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

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

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

• ■    объяснение получаемых решений.

2 Онтологическая модель процесса планирования

Онтология в контексте информационных систем определяется как формальное описание ПрО в понятной для всех участников процесса форме [5]. Внесённые уточнения [6, 7] опре- деляют онтологию как:

• ■    формальную модель ПрО (множество классов и отношений);

• ■    аксиомы и правила, обеспечивающие возможность контроля целостности знаний;

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

Онтология обеспечивает повторное использование знаний, позволяя разработать обобщённую структуру и специализировать её под разные ПрО. Так, в работах [8, 9] рассматривается использование онтологий для формализации знаний о производственных процессах в МАС. Такая онтология является примером обобщённой структуры, что позволяет на её основе сформировать конкретную модель с учётом особенности задачи. Наличие формальной структуры знаний облегчает идентификацию ключевых параметров и взаимосвязей между ними, помогая ЛПР принимать решения быстрее и с меньшими усилиями [10].

В данной работе используется редактор онтологий Pro égé 1 . Среди основных сущностей онтологии ПР можно выделить следующие классы (см. рисунок 3): Контракт, Продукт, Операция, Ресурс, Группа работников, Работник, Тариф работника, Период, План.

Приведённые классы образуют иерархическую структуру: Контракт включает один или несколько Продуктов, каждый Продукт выполняется множеством Операций, а каждая Операция потребляет определённые Ресурсы, которые представляют собой Работников, объединённых в Группы по

Рисунок 3 – Диаграмма классов для задачи планирования работ

принципу возможности их взаимозаменяемости в рамках определённых Операций.

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

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

1 Pro égé – свободный, открытый редактор онтологий и фреймворк для построения баз знаний.

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

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

■ длительность, периоды

■ 'длительность, периоды' Domain Операция

▼ ■дедлайн

■дедлайн Domain Контракт

■ имеет операцию

■ 'имеет операцию' Range Операция

▼ ■может выполняться группой

■ 'может выполняться группой' Domain Операция

заказчик

■ заказчик Domain Контракт

■ назначена на период

■ 'назначена на период' Domain Операция

▼ ф Контракт

■ Контракт rdfs label "ContracT@en

•Class Контракт

г 1 Операция

#CL Операция

■ Операция rdfs:lat)el 'Operation'@en

■ Операция rdfe:label "Операция’@ги

Контракт rdfslabel "Контракт' @hj

' ■ требует ресурс

■ Требует ресурс Domain Операция

▼ ■приоритет

■ приоритет Domain Контракт

■ трудоемкость, н-ч

■ Трудоёмкость, н-ч* Domain Операция

реализуется планом

■ реализуется планом' Domain Контракт

▼ ■часть плана

■ часть плана* Domain Операция

а)

в содержит продукцию

■ содержит продукцию' Domain Контракт

б)

Рисунок 4 - Примеры отношений между классами и атрибуты для класса: (а) «Операция» и (б) «Контракт»

3    Интеграция онтологии с мультиагентной системой

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

Среди подходов к интеграции онтологии в МАС можно выделить следующие.

• ■    Онтология в виде централизованной базы знаний, доступной всем агентам [8] (в таком случае выделяется специализированный агент, отвечающий за взаимодействие с онтологией: хранение экземпляров классов, выполнение запросов и внесение изменений).

• ■    Трёхуровневая система, включающая следящие слои (такая концепция устраняет информационную разрозненность путём приведения данных к единому онтологическому виду):

• ■    онтологический слой (общая информационная модель, обеспечивающая согласованное хранилище данных о продукте и процессах);

• ■    слой взаимодействия агентов (коммуникационный центр, через который модули обмениваются данными на основе онтологии);

• ■    слой имитационных агентов (набор программных агентов, моделирующих поведение рассматриваемых логистических субъектов) [11].

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

• ■    Подход с использованием онтологии для оценки «аргументов» и согласования действий агентов, подкрепляющий результаты работы агентов формальными доказательствами, заложенными в онтологию [14].

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

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

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

• ■    распределённые вычисления - агенты могут создавать краткосрочные группы (коалиции) с целью решения

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

  
  

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

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

Рисунок 5 - Схема интеграции онтологии с мультиагентной системой

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

4    Апробация модели

Апробация ОМ в МАС выполнялась путём сопоставления двух вариантов процесса ПР:

• ■    базового , в котором ЛПР разрабатывает план, используя справочники и последовательный просмотр ограничений без семантического отсечения несогласованных решений;

• ■    интеграционного , в котором МАС с ОМ создают единое семантическое пространство ПрО, осуществляется фильтрация альтернатив и предоставляется возможность управления ограничениями с помощью весовых коэффициентов W b , W t и W c .

Для обоих вариантов применялись одинаковые наборы тестовых исходных данных и сценарии изменений. Исходные данные разделены на две типовые категории по их мощности: малые и средние (см. таблицу 1).

Таблица 1 – Основные параметры тестовых данных

Набор данных	Количество Операций	Число Работников	Количество Периодов	Отношение длительности Операций к доступному времени Работников, %
Средний А	25	22	6	21
Средний Б	25	22	9	9
Малый А	12	12	3	37
Малый Б	12	12	3	49

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

• ■    время подготовки плана T plan (минут) - затрачиваемое время на формирование плана при заранее подготовленных исходных данных;

• ■    критерии оптимальности плана: f , f' и f” ;

• ■    количество перегрузок Работников N over - среднее арифметическое от количества перегрузок Работников в данном режиме у всех участников.

Таблица 2 – Полученные показатели эффективности двух вариантов процесса планирования работ

Набор данных	Метод	T plan , минут	. f , %	. Г , %	f” , %	over
Средний А	Базовый	91	2,1	100	94,3	0,4
	МАС с ОМ	3	0,9	100	97,6	0
Средний Б	Базовый	82	3,5	100	93,1	0
	МАС с ОМ	3	1	100	96,9	0
Малый А	Базовый	30	1,2	100	94,3	0
	МАС с ОМ	2	0,3	100	98,1	0
Малый Б	Базовый	55	1,9	100	82,8	1,2
	МАС с ОМ	2	1,4	100	93,6	0

По представленным в таблице 2 результатам можно сделать следующие выводы:

• ■    наибольший эффект от использования МАС с ОМ виден на времени подготовки плана;

• ■    несмотря на близкие к минимальным значениям базовые показатели f , все сценарии МАС с ОМ продемонстрировали заметную положительную динамику;

• ■    критерий соответствия срокам во всех сценариях достиг максимального значения в связи с тем, что все ЛПР ориентировались в первую очередь на него;

• ■    показатель равномерности распределения стабилен в условиях разброса времени доступности работников;

• ■    небольшое количество перегрузок, встречавшееся в базовых сценариях, в варианте МАС с ОМ сведены до нуля за счёт встроенных в ОМ ограничений на наличие перегрузок.

Помимо технической эффективности, в задаче снижения когнитивной нагрузки необходимо учитывать и оценку влияния МАС непосредственно на ЛПР. Для этого использовался метод субъективной оценки рабочей нагрузки NASA TLX, включающий набор шкал, по которым пользователь оценивает умственную и физическую нагрузки, нехватку времени, каче- ство выполнения задачи, сложность и уровень стресса [17]. Данный метод показал достаточную достоверность в исследованиях когнитивной нагрузки в сравнении с более глубокими тестами [18-20]. В данном тестировании использовалась его сокращённая версия RAW-TLX без физической нагрузки, где каждому из пяти факторов соответствовала десятибалльная шкала от «очень низкий» (1) до «очень высокий» (10) (кроме качества выполнения задачи, которое оценивается инвертированной шкалой), а итоговый индекс рассчитывался как среднее арифметическое всех параметров [21]. Опросник заполнялся участниками сразу после выполнения задания в каждом из режимов (см. рисунки 6 и 7).

а)

б)

Рисунок 6 – Результаты субъективной оценки методом RAW-TLX : (а) Базовый вариант и (б) МАС с ОМ

Можно отметить, что на сценариях с высокой дефицитностью ресурсов и более жёсткими ограничениями по Периодам преимущество МАС возрастало, что объясняется онтологическим отсечением несогласованных альтернатив, снижающим объём рассматриваемых альтернатив и число итераций. Данный эффект позволяет снизить и . Этот эффект проявляется и при увеличении объёма входных данных, помогая преодолеть комбинаторный рост числа вариантов, характерный для централизованных алгоритмов управления [16]. При этом снижается за счёт установленных по умолчанию правил разработанной ОМ, так как ЛПР освобождается от необходимости удерживания в своей

Базовый вариант            МАСсОМ

Показатель по шкале RAW-TLX

■ Средний А ■ Средний Б ■ Малый А ■ Малый Б

Рисунок 7 – Интегральный показатель субъективной оценки рабочей нагрузки методом RAW-TLX

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

Таким образом, можно отметить, что ОМ процесса ПР в сочетании с МАС позволила уменьшить комбинаторную сложность выбора, перцептивную нагрузку и нагрузку памяти ЛПР, при этом повысив основные метрики эффективности решения в сравнении с базовым вариантом процесса ПР.

Заключение

Разработана оригинальная ОМ процесса ПР на ПП, интегрированная в мультиагентную СППР и учитывающая когнитивную нагрузку на ЛПР.

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

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

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

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