Аннотация.

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

Ключевые слова:

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

Стр. 10-18.

 Полная версия статьи в формате pdf.

Tian Bo, M.A. Posypkin, I.H. Sigal

"Load balancing in solving problems based on estimates of the computational complexity of subproblems"

We proposed a new static load distribution strategy for parallel Branch-and-Bound method based on complexity estimates of sub-problems appearing in a Branch-and-Bound tree. This strategy can be used on parallel systems with low connectivity where dynamic load balancing is problematic. The experimental results demonstrated the superiority of the proposed strategy over other three strategies under test. Based on these results we draw some conclusions about the duration of the first (serial) part of the algorithm and choice of a load distribution strategy.

Keywords: Branch-and-Bound, Parallel Computing, Load Balance, Evaluation of the Computational Complexity of Subtasks.