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