Study of the Algorithmic Complexity of Constructing a Pareto Set for Decision-Making in Allocating Resources of Computing Systems

Abstract

Modern computing systems operate in conditions of heterogeneity of nodes and variable load, which necessitates the use of multi-criteria methods in the allocation of computing resources. One of these methods is the predictive method of resource allocation based on a multi-criteria decision-making model, the key stage of which is the construction of a set of Pareto-optimal solutions. However, the computational complexity of this stage and the possibility of reducing it have not been previously investigated. The object of the research is algorithms for constructing a Pareto set in the problem of predictive resource allocation in heterogeneous computing systems. The purpose of the work is to analyze the computational complexity of the basic optimization algorithm and to study methods for reducing it in relation to multi-criteria resource allocation tasks. Methodology: the paper formalizes the problem of constructing a Pareto set, establishes a theoretical estimate of the complexity of the basic algorithm. Three methods of reducing computational complexity are considered and analyzed: preliminary filtering of alternatives by a key criterion, early stopping in pairwise comparison, and incremental construction of a Pareto set. Experimental part: to experimentally confirm the theoretical estimates, a simulation program has been developed, with the help of which three series of experiments have been conducted: a study of the dependence on the number of nodes n, on the number of criteria k, and on the threshold parameter θ of the filtration method. The results obtained make it possible to reasonably choose an algorithm for constructing a Pareto set depending on the scale of the system, the number of criteria and the requirements for completeness of the solution, which helps to increase the efficiency of the scheduler in multi-criteria real-time resource allocation systems.