Новый алгоритм составит расписание для работы оборудования без производственных задержек

Ученые разработали алгоритмы для составления расписаний работы машин на производствах. Предложенные инструменты позволят избежать задержек в процессах даже при ограниченных времени и ресурсах, а также при наличии перерывов в работе оборудования. Результаты исследования, поддержанного грантом Российского научного фонда (РНФ), опубликованы в журнале «Известия Иркутского государственного университета. Серия "Математика"».

Чтобы предприятия точно в срок производили запланированное количество продукции, им важно составлять расписания хорошего качества, особенно если в процессах задействовано несколько разных типов оборудования. Так, например, для какого-то одного процесса может потребоваться несколько машин одновременно. Если какая-то из них используется в другой задаче, возникнет простой и, как следствие, задержка в изготовлении продукции.

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

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

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

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

Во втором случае (когда прерывания процесса запрещены) ученые разработали и протестировали два сложных инструмента — жадные эвристики и эволюционный алгоритм. Жадные эвристики работают как диспетчер, который каждый раз выбирает самое выгодное действие прямо сейчас, условно не думая о будущем. Благодаря этому он очень быстрый, но не всегда идеальный. Эволюционный алгоритм действует как селекционер: он создает много разных вариантов расписаний, сравнивает их, «скрещивает» лучшие между собой и постепенно совершенствует решения.

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

«Наше исследование показывает, что даже в задачах, которые традиционно считаются очень сложными для вычислений, существуют эффективные пути поиска приближенного решения. Мы не просто нашли способ ускорить расчеты, а предложили математический инструмент, который позволяет находить расписания, значительно сокращающие задержки, без огромных затрат на вычисления, что критически важно для современных производств», — рассказывает руководитель проекта, поддержанного грантом РНФ, Юлия Захарова, кандидат физико-математических наук, старший научный сотрудник лаборатории дискретной оптимизации Омского филиала Института математики имени С.Л. Соболева СО РАН.