Новосибирские ученые ускорили планирование химического производства в 10 раз с помощью GPU
Сотрудник Института математики имени С.Л. Соболева СО РАН разработал эволюционный алгоритм, который рассчитывает расписание работы химического завода более чем в 10 раз быстрее аналогичных программ. Результаты опубликованы в Journal of Heuristics.
Ученый из Института математики имени С.Л. Соболева СО РАН в Новосибирске создал алгоритм для планирования работы химических предприятий. Он решает задачу составления расписания более чем в 10 раз быстрее существующих инструментов. Работу поддержал Российский научный фонд, результаты вышли в журнале Journal of Heuristics.
На химическом заводе десятки установок одновременно работают с сотнями веществ. Чтобы выпустить нужный объем продукции в срок, важно точно распределить, какие реакции проводить, когда и на каком оборудовании — это избавляет от простоя установок и реактивов и увеличивает прибыль от продаж.
До сих пор для таких расчетов часто применяли метод ветвей и границ — алгоритм, перебирающий варианты расписаний в виде дерева и отбрасывающий заведомо неудачные ветви. На сложных задачах такой перебор может занимать часы и даже дни.
Новый алгоритм работает на графическом процессоре, у которого тысячи ядер считают параллельно. Программа действует по принципам эволюции: сначала создает случайный набор расписаний, затем оценивает каждое по нескольким параметрам — общему времени выполнения всех работ, равномерности загрузки оборудования — и отбирает лучшие. В них вносятся поправки: операции меняются местами, корректируется число задействованных установок. Процесс повторяется тысячи раз, расписание постепенно улучшается.
Алгоритм проверили на реальном предприятии, выпускающем более ста видов продукции в месяц. Он обошел по скорости и точности промышленный пакет Gurobi и инструмент cuOpt от NVIDIA. Авторы отмечают, что на более мощных видеокартах скорость вырастет еще больше.
«В дальнейшем мы планируем продолжить работу по ускорению алгоритма, а также его адаптации к другим задачам, например, к составлению расписаний в вычислительных системах или планированию доставки продукции потребителям», — рассказывает участник проекта Павел Борисовский, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации Омского филиала Института математики имени С.Л. Соболева СО РАН.
