Алгоритм метода ветвей и границ оптимизации расписаний выполнения пакетов заданий в конвейерных системах

Аннотация

Введение: оптимизация расписаний выполнения пакетов заданий обеспечивает эффективную реализацию производственных и вычислительных процессов. Современные методы оптимизации расписаний характеризуются ограничениями на размерность задач либо невозможностью получить решения, приближающиеся к глобально оптимальному. Цель: разработать алгоритм метода ветвей и границ оптимизации расписаний выполнения пакетов заданий в конвейерных системах. Результаты: получена математическая модель многостадийных процессов, позволяющая идентифицировать моменты времени начала выполнения пакетов заданий в соответствующих позициях в последовательностях реализации действий с ними на приборах конвейерных систем. Представлен критерий оптимизации решений, соответствующий моменту времени окончания выполнения заданий, включенных в пакеты. Сформулирован способ разбиения множеств решений на их подмножества (ветвления вершин дерева), который предусматривает добавление по одному пакету разных типов в последовательности реализации действий с ними из множеств не включенных в них пакетов. Разработан способ построения решений по порядкам выполнения на приборах пакетов, входящих в сформированные подмножества, для которых вычисляются значения критерия, используемые при обновлении верхних оценок. Синтезирован способ определения значений нижних оценок критерия для множеств решений, соответствующих вершинам дерева, полученным в результате ветвления, а также алгоритм метода ветвей и границ. Практическая значимость: исследования, проведенные с использованием программной реализации алгоритма, показали, что он позволяет до 35 % сократить время на выполнение пакетов по сравнению с решениями без оптимизации. При малом количестве типов заданий алгоритм позволяет получить решение, соответствующее глобально оптимальному. При увеличении количества типов заданий точность приближения решений к глобально оптимальному составляет 0,9–0,95.