INVESTIGATION OF KROHN’S ALGORITHM AND ITS MODIFICATION FOR VARIOUS BASIC DATA

Abstract

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.

Keywords

• krohn’s algorithm
• krohn’s algorithm modification
• minimax criterion
• initial distribution
• load balancing
• computing system.