Извините, этот техт доступен только в “Американский Английский”. For the sake of viewer convenience, the content is shown below in the alternative language. You may click the link to switch the active language.
THE METHOD OF A EURISISTIC-COMBINED SOLUTION OF LABOR-CONDUCTIVE TASKS IN PARALLEL COMPUTATIONAL SYSTEMS OF REAL TIME
Alexander G. Basyrov, Moghaysky military space academy, St. Petersburg, Russia, alexanderbas@mail.ru
Konstantin E. Legkov, Moghaysky military space academy, St. Petersburg, Russia, constl@mail.ru
Abstract
In real time often apply the heuristic algorithms yielding result, near optimal for acceptable time to a solution of NP full tasks. It is known that any heuristic algorithm provides a task solution with some figure of merit usually close or matching an optimal solution at significantly time for a task solution, smaller in comparison with optimum algorithms. In work the method of a solution of labor-consuming tasks on parallel computing systems on the basis of combination of heuristic algorithms is described. It is supposed that in the conditions of the set restrictions for time decisions of a task are passed calculations by several different heuristic algorithms with the subsequent choice of the best solution. The problem of such approach consists in the operational choice of this or that combination of the applied algorithms providing the largest probability of obtaining the best result for an allowed time of calculations. The mathematical problem of combinatory optimization consisting in maximizing probability of receiving the best (from possible for the set of heuristic algorithms) result is formulated at restrictions for operating time of a combination algorithm. The algorithm of polynomial complexity which in real time defines a rational of heuristic algorithms of a solution of a task and an order of purpose of these algorithms to elements of a parallel computing system is offered and investigated. An assessment of complexity and accuracy of the offered algorithm is given. The possibility of side-by-side execution of heuristic algorithms on several independent calculators for increase in efficiency of calculations is considered. The analysis of application of a method for a solution of different labor-consuming applied tasks showed its advantages consisting in increase in effectiveness of calculations.
Keywords: heuristic algorithm, combined solution, parallel computing.
References
1. Gary M., Johnson D. (1982). Vychislitelnie mashiny i trudno-reshaemye zadacni [Computers and hard-to-solve problems]. Moscow: Mir. 416 p. (In Russian)
2. Basyrov A.G. (2010). Combinirovannoe planirovanie parallelnych vychisleniy [Combined planning of parallel computing]. Information and space. No.4, pp. 60-62. (In Russian)
3. Dasgupta S. H., Papadimitriu, U.Vazirani. (2014). Algoritmy [Algorithms]. Moscow: MTSNMO, 320 p. (In Russian)
4. Brucker P. (2007). Scheduling Algorithms. Springer. 371 p.
5. Kustov V.N. (1992). Osnovy teorii ogranichennogo structurnogo parallelizma [Fundamentals of the theory of limited structural parallelism]. Ministry of Defense of the Russian Federation. 246 p. (In Russian)
6. Barsky A.B. (2007). Parallelnye informacionnye technologii [Parallel information technology]. Moscow: Internet University of Information Technologies; BINOMIAL. Laboratory of Knowledge. 503 p. (In Russian)
7. Basyrov A.G., Molchanov O.E. (2018). Algoritm ýevristiko-combinirovannogo reshenia trudoemkich zadach zaschity informacii v parallelnich vychyslitelnych systemah realnogo vremeni [Algorithm of a heuristic-combined solution of laborious information protection tasks in parallel real-time computing systems]. Information technologies, algorithms and programs for solving applied problems of ensuring cybersecurity, noise immunity and information support. St. Peterburg,: Mozhaysky military academy, pp.127-133. (In Russian)
8. Kolesov N.V., Tolmacheva M.V., Yukhta P.V. (2014). Sistemy realnogo vremeny. Planirovanie, analiz, diagnostirovanie. [Real time systems. Planning, analysis, diagnosis]. St. Peterburg: Concern Central Research Institute Elektropribor. 180 p. (In Russian)
9. Skorodumov Yu.M., Gruzlikov À.Ì. (2013). Efficiency research of task allocation algorithms in distributed computing systems. Proceedings of the international conference of young scientists «Automation and control», St. Peterburg, Russia, 21-22 november, p.46.
10. Liu J.W.S. (2000). Real-Time Systems. Prentice Hall, Englewood Cliffs, NJ. 600 p.
Information about authors:
Alexander G. Basyrov, PhD, Full Professor, Head of Department (BrE) of Military Space academy, St. Petersburg, Russia
Konstantin E. Legkov, PhD, Docent, Head of Department (BrE) of Military Space academy, St. Petersburg, Russia