The problem on the task distribution among the multiple homogeneous computing devices by the minimax criterion is considered. The problem definition with the detailed description of the subject of inquiry and its basics is given. It is proposed to use approximate algorithms for the solution to the problem. Both Krohn’s classical and modified algorithms, and the techniques of improving them through the initial task distribution among the computer system devices are considered. The critical-path algorithm and Pashkeyev’s algorithm are used for this purpose. The output values of a number of computational experiments at various input parameters are given in the paper for estimating the efficiency of the obtained Krohn’s algorithm modifications. The modified algorithms efficiency has been evaluated by the operate time and by the departure of the obtained load values from the optimum. The software to analyze the modified algorithm efficiency is developed.
Рассматривается задача распределения множества заданий между устройствами однородной вычислительной системы по минимаксному критерию. Приводится постановка задачи, в которой подробно описываются объект исследования и принципы его функционирования. Для решения поставленной задачи предлагается использовать приближённые алгоритмы. Рассмотрены классический и модифицированный алгоритмы Крона и способы их улучшения за счёт формирования начального распределения заданий между устройствами вычислительной системы. С этой целью используются алгоритм критического пути и алгоритм Пашкеева. Для оценки эффективности полученных модификаций алгоритма Крона в работе приведены выходные значения ряда вычислительных экспериментов при различных входных параметрах. Эффективность модифицированных алгоритмов оценивалась по времени работы и отклонению полученного значения загрузки от оптимального значения. Разработаны программные средства для анализа эффективности модифицированных алгоритмов.
The authors declare that there are no conflicts of interest present.