The optimization algorithm for solving homogeneous allocation problems of the scheduling theory is described and proved. It is a modification of Romanovsky’s algorithm known in this problem domain. Romanovsky’s algorithm is a classical version of the branch-and-bound method with one-way traversing a decision tree. A systematic study of this algorithm that allows revealing reasons for its operate time increment when traversing some decision tree branches is carried out. It allows proposing modification free of the revealed shortcoming. It is called a combinatorial-modified Romanovsky's algorithm. The essence of this modification is as follows. In the process of solving the allocation problem, those rules, stages, and steps that lead to the sorting on executors the sets of tasks deliberately duplicating the previous effects are selectively skipped. The essence of the new algorithm is illustrated by an example. The statistically presented studies are resulted. They demonstrate the algorithm capabilities on the high dimensional allocation problems. (Such problems cannot be solved by the classical algorithm due to the limited timing budgets.) The results of processing these solutions have shown that the new modification does not solve the problem of NP-complete allocation tasks, but it provides a resource-time gain associated with the significant reduction in the exponential model index of the average solution time.
Описывается и обосновывается алгоритм оптимизации решения однородных распределительных задач теории расписаний. Он представляет собой модификацию известного в этой предметной области алгоритма Романовского — классического варианта метода ветвей и границ с односторонним обходом дерева решений. Проведено системное исследование этого алгоритма, которое позволило выявить причины увеличения времени его работы при обходе некоторых ветвей дерева решений. Это даёт возможность предложить свободную от выявленного недостатка модификацию, названную комбинационно-модифицированным алгоритмом Романовского. Сущность данной модификации заключается в следующем. В процедуре решения распределительной задачи избирательно пропускаются те правила, этапы и шаги, которые приводят к перебору на исполнителях наборов заданий, заведомо повторяющих проверенный ранее результат. Сущность нового алгоритма поясняется примером. Приводятся результаты статистически представительных исследований. Они позволили продемонстрировать возможности алгоритма на распределительных задачах высокой размерности. (Решение таких задач классическим алгоритмом невозможно из-за ограниченных временных ресурсов.) Результаты обработки этих решений показали, что новая модификация не позволяет решить проблему NP-полноты распределительных задач, но обеспечивает ресурсно-временной выигрыш, связанный с существенным снижением показателя степени экспоненциальной модели роста среднего времени решения.
The authors declare that there are no conflicts of interest present.