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





