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

Аннотация

Современные методы решения задач планирования выполнения пакетов заданий в многостадийных системах характеризуются наличием ограничений на их размерность, невозможностью гарантированного получения лучших результатов в сравнении с фиксированными пакетами при различных значениях входных параметров задачи. В статье автором решена задача оптимизации составов пакетов заданий, выполняющихся в многостадийных системах, с использованием метода ветвей и границ. Проведены исследования различных способов формирования порядков выполнения пакетов заданий в многостадийных системах (эвристических правил упорядочивания пакетов заданий в последовательностях их выполнения на приборах МС). Определен способ упорядочивания пакетов в последовательностях их выполнения (эвристическое правило), обеспечивающий минимизацию общего времени реализации действий с ними на приборах. На основе полученного правила сформулирован способ упорядочивания типов заданий, в соответствии с которым их пакеты рассматриваются в процедуре метода ветвей и границ. Построена математическая модель процесса реализации действий с пакетами на приборах системы, которая обеспечивает вычисление его параметров. Выполнено построение метода формирования всех возможных решений по составам пакетов заданий для заданного их количества. Решения по составам пакетов заданий разных типов интерпретируются в процедуре метода ветвей и границ с целью построения оптимальной их комбинации. Для реализации метода ветвей и границ сформулирована процедура ветвления (разбиения), предполагающая формирование подмножеств решений, включающих пакеты разных составов заданий одного типа. Построены выражения для вычисления нижних и верхних оценок значений критерия оптимизации составов пакетов для сформированных в процедуре ветвления подмножеств. Процедура отсева предполагает исключение подмножеств, нижняя оценка которых не меньше рекорда. Для поиска оптимальных решений применена стратегия поиска в ширину, предусматривающая исследование всех подмножеств решений, включающих различные пакеты заданий одного типа, полученных в результате процедуры разбиения подмножеств заданий, не исключенных из рассмотрения после реализации процедуры отсева. Разработанные алгоритмы реализованы программно, что позволило получить результаты планирования выполнения пакетов заданий в многостадийной системе, являющиеся в среднем на 30 % лучшими, чем для фиксированных пакетов.