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