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.
References
principles and prospects of development], Informatsionnye tekhnologii i vychislitel'nye sistemy
[Information technologies and computing systems], 2008, No. 4, pp. 38-50.
2. Vasenin V.A., Shundeev A.S. Evolyutsiya tekhnologii Grid [Evolution of Grid technology],
Informatsionnye tekhnologii [Information Technologies], 2012, No. 1, pp. 2-9.
3. Barskiy A.B. Algoritmicheskie, arkhitekturnye i strukturnye metody organizatsii
upravlyayushchikh protsessov v virtual'nom prostranstve sredstv Grid-sistemy [Algorithmic, architectural
and structural methods of organizing control processes in the virtual space of Gridsystem
tools], Informatsionnye tekhnologii [Information Technologies], 2012, No. 5, pp. 2-6.
4. Kovalenko V.N., Semyachkin D.A. Metody i algoritmy upravleniya parallel'nymi zadaniyami v
gride s resursami v forme klasterov [Methods and algorithms for managing parallel tasks in a
grid with resources in the form of clusters], Vestnik Yuzhnogo nauchnogo tsentra RAN [Bulletin
of the Southern Scientific Center of the Russian Academy of Sciences], 2008, Vol. 4,
No. 3, pp. 23-34.
5. Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoylov V.I. Rekonfiguriruemye mul'tikonveyernye
vychislitel'nye struktury [Reconfigurable multiconveyor computing structures], under the general
ed. of I.A. Kalyaeva. Rostov-on-Donu: Izd-vo YuNTS RAN, 2009.
6. Liu C., Baskiyar S. A general distributed scalable grid scheduler for independent tasks, J. Parallel
Distrib. Comput., 2009, Vol. 69, pp. 307-314.
7. Saak A.E. Lokal'no-optimal'nye resursnye raspredeleniya [Locally optimal resource distributions],
Informatsionnye tekhnologii [Information technologies], 2011, No. 2, pp. 28-34.
8. Saak A.E. Dispetcherizatsiya v Grid-sistemakh na osnove odnorodnoy kvadratichnoy tipizatsii
massivov zayavok pol'zovateley [Dispatching in Grid-systems based on homogeneous quadratic
typing of arrays of user requests], Informatsionnye tekhnologii [Information Technologies],
2012, No. 4, pp. 32-36.
9. Saak A.E. Polinomial'nye algoritmy raspredeleniya resursov v Grid-sistemakh na osnove
kvadratichnoy tipizatsii massivov zayavok [Polynomial algorithms for resource allocation in
Grid systems based on quadratic typing of request arrays], Informatsionnye tekhnologii [Information
Technologies], 2013, No. 7. Appendix, 32 p.
10. Korf R. Huang E. New Improvements in Optimal Rectangle Packing. In Proceedings of the
21st International Joint Conference on Artificial Intelligence (IJCAI 2009). Pasadena,
California, USA, July 11-17, 2009, pp. 511-516.
11. Saak A.E. Dispetchepizatsiya massivov zayavok summapnoy pesupsnoy mepy, pavnoy
kvadpatu tselogo chisla [Dispatching of request arrays with a total resource measure equal to
the square of an integer], Informatsionnye tekhnologii [Information Technologies], 2015, Vol.
21, No. 9, pp. 675-679.
12. Emel'yanov V.V., Kureychik V.V., Kureychik V.M. Teoriya i praktika evolyutsionnogo
modelirovaniya: monografiya [Theory and practice of evolutionary modeling: monograph].
Moscow: Fizmatlit, 2003.
13. Kureychik V.V., Kureychik V.M., Rodzin S.I. Kontseptsiya evolyutsionnykh vychisleniy,
inspirirovannykh prirodnymi sistemami [The concept of evolutionary calculations inspired by
natural systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2009, No. 4 (93), pp. 16-24.
14. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy:
monografiya [Theory of evolutionary calculations: monograph]. Moscow: Fizmalit, 2012.
15. Kureychik V.V., Rodzin S.I. O pravilakh predstavleniya resheniy v evolyutsionnykh
algoritmakh [On the rules for the representation of solutions in evolutionary algorithms],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2010, No. 7
(108), pp. 13-21.
16. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy: ucheb. posobie [Modern search engine optimization algorithms. Algorithms inspired
by nature: a textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p.
17. Kureychik V.M., Kureychik V.V. Ob upravlenii na osnove geneticheskogo poiska [About management
on the basis of genetic search], Avtomatika i telemekhanika RAN [Avtomatika i
telemekhanika RAS], 2001, No. 10, pp. 174-187.
18. Kureychik V.V. Kureychik V.M., Sorokoletov P.V. Analiz i obzor modeley evolyutsii [Analysis
and review of models of evolution], Izvestiya Rossiyskoy akademii nauk. Teoriya i sistemy
upravleniya [Izvestiya Rossiyskoy akademii nauk. Theory and control systems], 2007, No. 5,
pp. 114-126.
19. Korf R. Huang E. Optimal Rectangle Packing on Non- Square Benchmarks. In Proceedings of
the twenty-fours AAAI Conference on Artificial Intelligence (AAAI-10). Atlanta, Georgia, USA,
July 11–15, 2010, pp. 83-88.
20. Saak A.E. Sravnitel'nyy analiz polinomial'nykh algoritmov dispetcherizatsii v Grid-sistemakh
[Comparative analysis of polynomial dispatching algorithms in Grid systems],
Informatsionnye tekhnologii [Information Technologies], 2012, No. 9, pp. 28-32.
21. Saak A.E. Urovnevye algoritmy dispetcherizatsii massivami zayavok krugovogo tipa v Gridsistemakh
[Level algorithms for dispatching circular-type request arrays in Grid-systems],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 6
(167), pp. 223-231.
