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

Исследователь из Института математики имени С.Л. Соболева СО РАН разработал алгоритм для планирования работы химического производства. Он выполняет вычисления на графическом процессоре и в испытаниях превзошёл известные программные инструменты по скорости и точности.

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

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

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

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

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

Источник: Российский научный фонд