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.