Алгоритм оптимизации производственных процессов с помощью графов

Юлия Захарова и аспирант Мария Сахно изучают оборудование для решения задач по ускорению запуска работы приложений. Источник: Юлия Захарова

Юлия Захарова и аспирант Мария Сахно изучают оборудование для решения задач по ускорению запуска работы приложений. Источник: Юлия Захарова

Группа исследователей создала новый алгоритм, который помогает оптимизировать производственные, логистические и вычислительные процессы. Эта разработка находит применение в таких областях, как логистика и многостадийное производство, где каждая операция происходит на строго определенных этапах производственной цепочки. Например, некоторые задачи можно выполнять только в начале или в конце смены, или с использованием специфического оборудования. Исследование, которое получило поддержку гранта Российского научного фонда (РНФ), опубликовано в журнале Journal of Scheduling.

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

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

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

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

«Алгоритм создан с учетом реальных производственных ограничений, что часто не учитывается в теоретических моделях. Он предлагает качественные решения и легко адаптируется к различным практическим задачам», — отмечает Юлия Захарова, руководитель проекта, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации.

Информация и фото предоставлены пресс-службой Российского научного фонда

Что читать дальше

Подборка материалов по этой теме.

Сейчас читают

Материалы, которые чаще открывают сегодня.

Загрузка…

Ещё по теме

Продолжить чтение

Материалы, которые помогут не выпадать из темы.