Klimenko A.B., Trotsenko R.V..
The solution of problem of resource optimization and computation scheduling using of
parallel annealing simulation
// Software systems and computational methods. – 2014. – є 3.
– P. 282-290.
Read the article
Abstract: various metaheuristics, such as method of simulated annealing, are currently used
for solving the tasks of resource usage optimization and computation scheduling. Simulated
annealing is a serial method and it is difficult to parallelize it. However, different methods of
parallelization have been developed recently in order to improve the quality of the solutions
and the time of algorithm execution. The subjects of the study are the methods of parallelization for annealing simulation, in particular, the method of independent starts with and without
synchronization. As an example of simulated annealing implementation the authors select
the method with thermal scheme УquenchingФ as the fastest one. The article shows analytical
review of simulated annealing parallelization, with a selection of the most promising methods,
for which a series of computational experiments was carried out. Scientific novelty of the
work is in the discovery of new dependencies and trends that were not described previously
in similar studies. In discussing the parallelized annealing simulation with synchronization the
authors raise a question of the existence of the dependence of the quality of the solutions
with not only the number of computing devices, but also with the frequency of the solutions
exchanges. For asynchronous parallel simulated annealing the article shows a tendency to
solutions improvement with the increase of the number of computing devices, while for
synchronous simulated annealing a similar dependence was not found.
Keywords: simulated annealing, parallel algorithm, optimization, computational system, resource optimization, parallel computing, resource assigning, metaheuristics, parallelization techniques, computation scheduling
MsGee A. A. and Markarian M. D. Optimum Allocation of Research (Engineering Manpower within a Multi-Project Organizational Structures). IRE Trans. Engng. Manag., v. 9, No. 3, 1962.
Levy F. E., Thompson G., Wiest J. Multiship, Multishop, Workloadsmoothing Program, Naval Research, Logistics Quarterly, v. 9, No. 1, 1962.
Fey S.F. Least Cost Estimating and Scheduling with Limited Resources. Abstract. Recent Advances Math. Programm, 1963.
Barskiy A.B. Parallel'nye protsessy v vychislitel'nykh sistemakh: planirovanie i organizatsiya. Ц M.: Radio i svyaz', 1990.
F. Busetti, Simulated annealing overview. 2003. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=9F958F3AD8ACB341A84315A737883592?doi=10.1.1.66.5018)
L.Ingber, Simulated annealing: practice versus theory.1993. (http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary?doi=10.1.1.15.1046)
Crainic T.G., Toulouse M. Parallel Metaheuristics. In T. G. Crainic and G. Laporte, editors, Fleet Management and Logistics, pages