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