AN EVOLUTIONARY ALGORITHM FOR SOLVING THE DISPATCHING PROBLEM

Abstract

The paper considers one of the most important optimization tasks – the dispathing task that belongs to the class of NP-complex optimization problems. The paper presents the formulation of this problem. In Grid systems the array of users' requests for computer services is modelled by an extended linear polyhedral of coordinate resource rectangles. In this case, dispatching is represented by the localization of a linear polyhedron in the envelope of the area of computational and time resources of the system according to the multipurpose criterion of the quality of the applied assignment. Due to the complexity of this problem, the authors propose methods of evolutionary modelling for its effective solution and describe a modified evolutionary search architecture. Three additional blocks are introduced as a modification. This is a block of "external environment", a block of evolutionary adaptation and a block of "unpromising solutions." The authors have developed a modified evolutionary algorithm that uses the Darwin’s and Lamarck’s evolution models. This makes it possible to significantly reduce the time for obtaining the result, partially solve the problem of premature convergence of the algorithm, and obtain sets of quasi-optimal solutions in polynomial time. A software module has been developed in the C # language. A computational experiment has carried out on test examples and shown that the quality of solutions obtained on the basis of the developed evolutionary algorithm is, on average, 5 percent higher than the results of solutions obtained using the known algorithms of sequential, initial-ring and level at comparable time, which indicates the effectiveness of the proposed approach.