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

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

Авторы рассмотрели два типа производственных процессов: с возможностью временно прерывать выполнение задач и без такой возможности. Для каждого случая исследователи предложили собственные алгоритмы и протестировали их на стандартных наборах производственных задач.

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

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

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

Результаты опубликованы в журнале «Известия Иркутского государственного университета. Серия "Математика"»

Подробнее — в материале ТАСС

РНФ | Телеграм | ВКонтакте | MAX #новостинауки_РНФ #математика