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