Ученые разработали алгоритм, позволяющий оптимизировать производственные, логистические и вычислительные процессы, сокращая их длительность и минимизируя простои используемого оборудования. Разработка будет полезна в логистике, многостадийном производстве и компьютерных системах, где каждая операция может выполняться только на строго определенных этапах производственной цепочки. Например, некоторые задачи могут решаться только в начале или конце смены, на конкретном оборудовании или между определенными операциями. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в журнале Journal of Scheduling.
Чтобы современные логистические, производственные и вычислительные системы работали эффективно, нужно оптимально распределять все выполняемые задачи между машинами или процессорами. Классические алгоритмы планирования не всегда учитывают ограничения в последовательности работ в производственном цикле. Например, определенные операции могут выполняться только на конкретных этапах технологического процесса, некоторые работы нельзя ставить в начало или конец смены из-за особенностей оборудования, отдельные задачи должны обязательно следовать друг за другом или, наоборот, не могут быть соседними. Если это не учитывать, ресурсы — например оборудование, сырье, финансы — используются неэффективно, а длительность процесса обработки и затраты увеличиваются. Поэтому необходимы математические модели, учитывающие подобные ограничения.
Ученая из Омского филиала Института математики имени С.Л. Соболева СО РАН (Омск) предложила свести задачу планирования к поиску оптимальных комбинаций (совершенных паросочетаний) в двудольных графах — системе из точек (вершин) и линий (ребер), где вершины соответствуют определенным операциям и их позициям в расписании, а ребра отражают допустимые варианты их распределения между машинами.
Алгоритм включает несколько этапов: сначала система анализирует все возможные варианты размещения работ с учетом ограничений, затем с помощью математических методов отбирает наиболее эффективные комбинации и наконец строит итоговое расписание, минимизирующее общее время выполнения или другие заданные показатели. Для сложных случаев, когда полный перебор вариантов невозможен, исследовательница предложила математические инструменты, позволяющие находить решения, близкие к оптимальным, за приемлемое время.
Для проверки эффективности метода автор провела серию вычислительных экспериментов на синтетических данных, моделирующих различные производственные сценарии, которые включают до ста различных операций. Среди таких сценариев рассматривались маршрутизация транспортных средств, энергетически эффективные расписания, обработка многокомпонентных заказов клиентов, учет директивных сроков и важность операций. Алгоритм смог за установленное время найти приемлемые по качеству решения даже для задач с большим количеством ограничений на последовательность выполнения работ, где классические подходы, например генетические алгоритмы и методы динамического программирования, часто давали неудовлетворительные для практиков результаты. Предлагаемый подход показал статистически значимое преимущество по сравнению с известными на текущий момент в литературе методами.
«Алгоритм специально разрабатывался так, чтобы он мог работать с реальными производственными ограничениями, которые часто игнорируются в теоретических моделях. Метод не только дает качественные решения в условиях ограничений, но и достаточно гибок для адаптации к различным практическим применениям», — рассказывает руководитель проекта, поддержанного грантом РНФ, Юлия Захарова, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации Омского филиала Института математики имени С.Л. Соболева СО РАН.
***
Больше результатов исследований грантополучателей Российского научного фонда и актуальных новостей из мира науки доступны в социальных сетях РНФ Вконтакте и Телеграм