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

Аннотация

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