Dispatching of circular-type applications

V. V. Kureichik ; A. E. Saak

News of the Kabardin-Balkar scientific center of RAS, no. 6 (2021), pp. 50-57

Résumé

The article deals with the polynomial-time-consuming initial-ring and sequential approximation algorithm to discuss the question of the practical feasibility of their application in Grid systems. The first coordinate quadrant serves as a model of a Grid system with a centralized architecture, and the application model is represented by a resource rectangle. The quality of the algorithms is assessed by a nonEuclidean heuristic measure. The proposed algorithms are based on the operations of dynamic integration along the horizontal and vertical lines with a local optimum. The proposed algorithms are analysed on test arrays obtained from the facing of a square with strips of smaller squares. The heuristic measures of the resource shells of the initial-ring and the algorithm of successive approximations are calculated, which do not exceed the value of 0.61, and the magnitude of the error relative to the optimal value is determined, which does not exceed 22%. A recommendation is given to use these algorithms for dispatching circulartype claims in Grid-systems of a centralized architecture by arrays.

Détail

Keywords: dispatching, non-Euclidean heuristic measure, polynomial complexity of the algorithm, initial-ring algorithm, sequential approximation algorithm, array of applications of circular type, Grid-system.