За разработкой стоит старший научный сотрудник филиала Института математики Сибирского отделения РАН в Омске Павел Борисовский. На испытаниях его алгоритм получил задачу спланировать работу предприятия, выпускающего ежемесячно больше 100 наименований продукции. Сложные задачи он решал быстрее и точнее, чем Gurobi и ряд других программ, в том числе cuOpt от NVIDIA.

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

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

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

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

Источник: ТАСС