Графы помогут оптимально планировать производственные процессы

Ученая из Омского филиала Института математики имени С.Л. Соболева СО РАН (Омск) предложила свести задачу планирования к поиску оптимальных комбинаций (совершенных паросочетаний) в двудольных графах — системе из точек (вершин) и линий (ребер), где вершины соответствуют определенным операциям и их позициям в расписании, а ребра отражают допустимые варианты их распределения между машинами.

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

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