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

Метод составляет расписание для десятков установок и сотен веществ и решает задачу более чем в 10 раз быстрее аналогичных вычислительных инструментов.

Сотрудник Института математики им. С.Л. Соболева СО РАН в Новосибирске создал алгоритм, который составляет расписание работы химического завода. По данным источника, он решает эту задачу более чем в 10 раз быстрее аналогичных вычислительных инструментов. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в журнале Journal of Heuristics.

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

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

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

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

Планы на дальнейшую работу рассказал Павел Борисовский, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации Омского филиала ИМ СО РАН:

РАН