UNIV. NEWS. NORTH-CAUCAS. REG. TECHNICAL SCIENCES SERIES. 2022; 4: 5-10
http://dx.doi.org/10.17213/1560-3644-2022-4-5-10
IMPLEMENTATION OF MODIFICATIONS OF THE CROHN'S ALGORITHM FOR SOLVING MINIMAX PROBLEMS WITH INFINITIES
Kobak Valeriy G. – Doctor of Technical Sciences, Professor, Department «The Software of Computer Facilities and Automated Systems», Don State Technical University, Rostov-on-Don, Russia, valera33305@mail.ru
Valadov Anton S. – Student, Department «The Software of Computer Facilities and Automated Systems», Don State Technical University, Rostov-on-Don, Russia.
Shevchenko Vadim V. – Student, Department «The Software of Computer Facilities and Automated Systems», Don State Technical University, Rostov-on-Don, Russia.
Abstract
In this paper, we consider the solution of the distribution problem for homogeneous systems containing infinities using various modifications of the Krohn algorithm. Distributive is a class of economic and mathematical problems related to the allocation of resources for the work to be performed. A description of each of the evaluated modifications of the Crohn's algorithm is given. To evaluate their effectiveness, the results of experiments with different input data and comparison of the obtained data by algorithms are demonstrated. The data contains information about the average value obtained as a result of the modification, as well as the average execution time of one task. Interactions with infinities for each algorithm proposed by the authors are described. Software tools have been developed to analyze the effectiveness of these algorithms.
Keywords: Crohn's algorithm, approximate algorithms, minimax problem, minimax problems with infinities, distribution algorithm
Full text: [in elibrary.ru]
References
- Koffman E.G. Scheduling Theory and Computers. Moscow: Nauka Publ.; 1984. 337 р.
- Golovkin B.A. Calculation of Characteristics and Planning of Parallel Computing Processes. Moscow: Radio and Communications; 1983. 272 p.
- Alekseev O.T. Complex Application of Discrete Optimization Methods. Moscow: Nauka; 1987.
- Kobak V.G., Zhukovsky A.G., Zolotykh O.A., Rostov A.N. Solution of a Homogeneous Minimax Problem by Various Modifications of the Crohn's Algorithm. Izv. vuzov. Sev.-Kavk. region. Technical sciences=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2016; (3): 3-8. (In Russ.)
- Kobak V.G., Zhukovsky A.G., Zolotykh O.A., Rostov A.N. Various Approaches to Solving a Homogeneous Minimax Problem in Scheduling Theory by Heuristic Algorithms. Izv. vuzov. Sev.-Kavk. region. Technical sciences=Bulletin of Higher Educational Institutions. North Caucasus Region. Technical Sciences. 2016; (1): 41-45. (In Russ.)
- Kobak V.G., Ivanov M.S. Comparative analysis of algorithms for solving the planning problem in homogeneous computing systems. Mathematical methods in engineering and technology - MMGT-20: sat. tr. XX, 2007.
- Kobak V.G., Titov D.V., Zolotykh O.A. Investigation of the Crohn's Algorithm and its Modifications with Different Source Data. Vestn. DSTU. 2012; 8(69).
- Kobak V.G., Titov D.V., Zolotykh O.A., Chizhov D.V. Various Approaches to Increase the Efficiency of the Crohn's Algorithm in Homogeneous Information Processing Systems. Izvestiya Vysshihkh Uchebnykh Zavedenii. Elektromekhanika = Bulletin of Higher Educational Institutions. Electromechanics. 2012; (5): 74-77. (In Russ.)
- Kobak V.G., Zolotykh O.A., Titov D.V. Improving the Efficiency of the Crohn's Algorithm by Modifying the Initial Distribution of Task. Modern problems of informatization in modeling and social technologies: collection of tr. XVI International. Open Scientific conference Voronezh: Scientific Book; 2011. Pp. 246-251.
- Kobak V.G., Titov D.V., Zolotykh O.A. Investigation of the Crohn's Algorithm Under Different Initial Conditions. Mathematical methods in engineering and technologies - MMTT-24: sat. tr. International Scientific Conference. SSTU, 2011; (8).