Software & Systems

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

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

В общем виде задача оперативного планирования формулируется следующим образом.

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

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

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

1)  в соответствии с требованиями основного графика производства (ОГП) необходимо составить перечень производственных заданий (ПЗ) или работ, покрывающих потребность в выпуске продукции (будем считать, что одно задание содержит только одну номенклатуру изделия);

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

3)  для каждой производственной линии надо определить последовательность запуска назначенных ПЗ, то есть подобрать даты завершения заданий; при этом согласно требованиям ОГП необходимо минимизировать отклонения от директивных сроков выпуска, учесть технологические и организационные ограничения.

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

где F1 – функция штрафа, отражающая суммарное по всей номенклатуре состояние складских запасов планируемой номенклатуры (исходя из среднедневного спроса si и плановых выпусков, значение этой составляющей нужно минимизировать); F2 – составляющая, отражающая суммарное по всем ресурсам количество переналадок по предложенному варианту оперативного плана (значение нужно минимизировать); F3 – функция штрафа, отражающая суммарное по всей номенклатуре отклонение сроков завершения заданий от директивных требований ОГП (необходимо обеспечить минимальное значение этой составляющей); α1, α2, α3 – весовые коэффициенты, определяющие влияние F1, F2, F3 соответственно на значение суммарного критерия F; CF1, CF2, CF3 – коэффициенты поправки размерностей составляющих критерия.

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

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

Использование многоагентного подхода

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

где M – количество итераций поискового алгоритма.

Каждое последующее решение получается из предыдущего с помощью алгоритма поиска А, который указывает, какие операции необходимо сделать при Z[m], чтобы получить более предпочтительное решение Z[m+1]: Z[m+1]=A(Z[m]).

Для простоты будем считать, что один агент работает с одной заявкой. Состояние k-го агента характеризуется n-мерным вектором атрибутов vk(xk1, xk2,…, xkn). Решение Z на m-й итерации определяется состоянием всех агентов, то есть набором векторов Z[m]=Z(v1[m], v2[m],…, vk[m]), а именно матрицей размерности k строк на n столбцов.

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

Значение критерия рассчитывается как функция от матрицы Z, то есть векторов атрибутов всех агентов: FP=F(Z)=F(v1,v2,…,vm). К сожалению, для большинства реальных практических задач оперативного планирования достаточно трудно, а иногда и невозможно вывести формулу целевой функции в явном виде. В этих случаях значение критерия может быть получено только вычислительным путем, то есть методом моделирования или прогона решения.

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

В нашем случае необходимы операторы преобразования значений элементов матрицы Z. Здесь под операторами преобразования решения подразумеваются эвристические правила или действия предметных специалистов. Условия применимости того или иного правила определяют так называемую ситуацию или предпосылки, инициирующие наиболее актуальное действие. С этой целью предварительно определяется и формализуется набор характерных для отрасли действий и ситуаций, которыми руководствуются плановики в процессе составления планов.

Пусть заданы конечные множества возможных ситуаций s и действий a. Предполагается, что ситуация siÎs должна отражать текущее состояние агента, а именно, насколько агент достиг локальной цели. В ином рассматривается, как текущее состояние агента повлияло на достижимость глобальной цели – оптимизацию целевого критерия.

Для организации процедуры направленного перехода от одного решения к другому каждый агент наделяется возможностью выполнять действия, изменяющие его состояние, то есть корректирующие значения вектора его атрибутов (x1, x2, …, xn). Выбор действия производится согласно так называемой матрице обучения Q(si,aj ) в зависимости от ситуации, в которой находится агент на текущий момент работы алгоритма. Значение элемента qij матрицы обучения Q отражает степень уверенности агента в применении действия aj в ситуации si. В зависимости от ситуации агент отдает предпочтение действию, имеющему наибольшее значение элемента qij с вероятностью (1-ε). Напротив, с вероятностью ε агент предпринимает произвольное действие. Эта стратегия выбора называется ε-жадной политикой.

Таким образом, агент эмулирует действия предметного специалиста, опыт которого закладывается в матрицу обучения Q. Предполагается, что начальные значения элементов qij назначаются экспертом. Обучение агента базируется на методе SARSA (ситуация®действие®переоценка®ситуа­ция®действие) и сводится к переоценке значений элементов матрицы Q. Это производится по ходу процесса поиска решения посредством получения так называемого сигнала отклика среды (поощрение или наказание), несущего оценку целесообразности выбранного действия. Формирование сигнала проводится на основе данных об изменении ситуации для текущего агента: если предпринятое действие привело к устранению нарушения конкретного ограничения или же благоприятно сказалось на значении критерия, то вырабатывается сигнал поощрения. В процессе поиска не исключены случаи, когда для агента одновременно имеет место несколько ситуаций. В соответствии с приоритетным правилом алгоритмом осуществляется выбор единственной, наиболее важной ситуации, относительно которой проводится выбор актуального действия.

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

·     в соответствии с вектором состояния v определить актуальные ситуации и сосредоточиться на одной, наиболее важной;

·     согласно матрице обучения Q произвести выбор наиболее адекватного действия;

·     реализовать выбранное им действие;

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

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

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

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

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

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

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

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

Изложенный выше подход реализован в виде оптимизационных алгоритмов для задачи оперативного планирования производства. Они применены в рамках внедрения ERP-системы ORACLE e-Business Suite и информационной системы 1С 7.7 на отечественных предприятиях пищевой и химической отрасли соответственно. Тестовые прогоны бизнес-процессов, использующих описанный подход, подтвердили адекватность получаемых производственных планов. В настоящее время осуществляется переход к стадии опытно-промышлен­ной эксплуатации.