Что общего у селекции новых сортов растений и идеального плана производства? Оказывается, общий принцип — эволюция — позволяет находить решения, которые не под силу традиционным методам.
Почему планирование — это NP-полная задача
Построение оптимального плана производства относится к классу NP-полных задач. Это значит, что количество возможных комбинаций растёт экспоненциально с ростом числа заказов, деталей и операций. Например, для цеха с несколькими тысячами операций полный перебор невозможен — он занял бы годы даже на мощных серверах. Поэтому в промышленности применяются эвристические и приближённые методы.
Классические алгоритмы (MRP-II, жёсткие правила приоритизации) дают быстрый, но далекий от оптимального результат. Чтобы приблизиться к действительно «хорошему» плану, в APS применяются методы эволюционной оптимизации, в частности генетические алгоритмы (GA).
Эволюционные алгоритмы — ИИ или нет?
В профессиональной среде ведутся споры: можно ли считать генетические алгоритмы искусственным интеллектом.
Скептики утверждают, что GA — это лишь стохастический перебор с отбором лучших решений. Они не учатся в привычном смысле и не демонстрируют «понимания» задачи. Кроме того, вычислительная стоимость их применения высока.
Однако есть и противоположная позиция. Генетические алгоритмы относятся к семейству методов искусственного интеллекта, зародившихся ещё в 1950-е годы. Их сила — в способности находить решения в задачах, где прямой перебор невозможен. А если вспомнить, что человеческий интеллект сам является продуктом биологической эволюции, то GA вполне можно назвать одной из форм ИИ.
Для производственного планирования эти философские различия вторичны. Главное — эффективность метода при реальных ограничениях.
Почему не нейросети?
Нейросети сегодня на слуху, но в задачах планирования они уступают GA. Причина проста: для обучения нейросети нужны миллионы примеров «идеальных» планов. Таких данных не существует. Более того, производственная среда слишком динамична: оборудование ломается, поставки срываются, заказы меняются ежедневно.
GA же не требуют обучающей выборки. Они работают непосредственно с моделью производства и целевой функцией. Нейросети лучше подходят на другом уровне — например, для роботизации исполнения плана или прогнозирования сбоев. Но сам план эффективнее рассчитывать эволюционными методами.
Как устроен генетический алгоритм
Представьте, что вы не ищете одно верное решение, а выращиваете его, как селекционер.
В основе — принцип естественного отбора. Мы создаём не одно, а целую популяцию случайных решений — как первое поколение особей.
Каждое решение оценивается по функции пригодности — целевой функции. Она показывает, насколько особь хороша для выживания.
Далее начинается эволюция:
1. Инициализация. Формируется популяция возможных планов (особей).
2. Оценка пригодности. Каждое решение оценивается по целевой функции: себестоимость, сроки, количество переналадок, уровень незавершённого производства.
3. Отбор. Лучшие планы получают «право» на продолжение.
4. Скрещивание. Параметры двух успешных решений комбинируются, рождая новые варианты.
5. Мутация. Вносятся случайные изменения, чтобы избежать застоя и исследовать большее пространство решений.
Цикл повторяется десятки или сотни поколений. В результате план становится всё более «приспособленным». Важно понимать: алгоритм не ищет идеал, а быстро находит достаточно хорошее решение, часто лучшее из доступных человеку или традиционным методам.
Эволюционные алгоритмы в ТАП APS
Давайте посмотрим, как принципы эволюции применяются в нашей системе планирования.
Что выступает в роли «генов»?
Это ключевые изменяемые параметры плана. Например:
· Выбор варианта маршрута производства,
· Настройка буферов рабочих мест,
· Время начала работ по заказу,
· Размер оптимальной партии,
· Приоритет того или иного заказа.
А что же является «естественным отбором»?
Эту роль выполняет наша целевая функция — сложная формула, которая оценивает качество каждого плана. По сути, это взвешенная сумма ключевых KPI, таких как:
· Общая себестоимость,
· Количество и время переналадок,
· Своевременность выполнения заказов,
· Общая длительность цикла и время простоев.
Как происходит сам процесс?
После операций скрещивания и мутации мы формируем новую популяцию «особей» — то есть, множество вариантов планов. Для каждого из этих вариантов система выполняет полный расчёт, чтобы оценить его по нашей целевой функции и определить, кто выживет в следующем цикле.
И главное преимущество — скорость.
Так почему же скорость расчетов является ключевым преимуществом? Дело в том, что для нахождения максимально приближенного к идеалу варианта плана необходимо «вырастить» десятки, а то и сотни поколений. То есть, в нашем случае, рассчитать тысячи, а то и сотни тысяч вариантов плана. На малом количестве поколений генетический алгоритм вряд ли будет эффективным, ведь вероятность появления лучшей версии плана среди сотен вариантов выше, чем среди трех-пяти. А чтобы просчитать все эти варианты в разумные сроки, каждый их них должен считаться максимально быстро.
Если один вариант плана рассчитывается 20-25 минут, то одна тысяча вариантов будет считаться около 15 суток. Это не имеет никакого смысла.
Именно поэтому нашей приоритетной задачей было обеспечение максимальной производительности расчетного движка. И мы успешно с ней справились. Сейчас расчет одного варианта плана в ТАП APS выполняется менее 1 минуты, даже на достаточно большой номенклатуре в десятки тысяч наименований, что позволяет применять генетические оптимизации, не рискуя утратой актуальности результатов. Но и это еще не все. При увеличении количества ядер на сервере или организации кластера из нескольких серверов система автоматически распределяет вычисления по всем доступным ядрам. ТАП APS позволяет провести полноценное моделирование плана с расчётом многих сотен тысяч вариантов за пару часов.
На сегодняшний день аналогов такой реализации APS на рынке нет.
Математическое обоснование
Работа ядра APS строится на двух уровнях:
1. Разузлование (MRP-II) — формирование списка необходимых компонент на основе матрицы входимости. Сложность решения сводится к почти линейной.
2. Составление расписания — назначение операций на рабочие центры с учётом частичного порядка. Эффективные эвристики позволяют достичь сложности порядка O(M^1.1), где M — число операций.
Что получает предприятие
По данным аналитиков CIMData, внедрение APS с эволюционными алгоритмами даёт:
· сокращение времени планирования на 60–90%;
· рост производительности на 5–20%;
· снижение длительности производственного цикла на 15–40%;
· сокращение уровня незавершённого производства на 20–50%;
· повышение точности выполнения планов на 10–30%.
Это значит, что система перестаёт быть «бутылочным горлышком» и превращается в инструмент стратегического управления.
Заключение
Эволюционные алгоритмы доказали свою применимость в промышленности. Это не академическая экзотика, а реальный инструмент, который ежедневно помогает заводам и холдингам снижать затраты, повышать гибкость и выполнять обязательства перед клиентами.
ТАП APS сочетает математическую строгость, инженерную надёжность и современные подходы к оптимизации. И если нейросети стали символом ИИ в потребительских сервисах, то именно эволюционные методы сегодня формируют «интеллект» производственного планирования.
Смотрите вебинар в записи, где автор поста и он же - автор алгоритма ТАП APS - математик Олег Морозов, рассказывает об алгоритме и его применении для создания быстрых и точных планов производства.