Improving the efficiency of the hybrid algorithm for solving inhomogeneous minimax problem

¹ Don State Technical University, 1 Gagarina sq., Rostov-on-Don 344003, Russia
² North Caucasus branch of the Moscow Technical University of Communications and Informatics, Rostov-on-Don 344010, Russia

^* Corresponding author: angel_b@mail.ru

Abstract

The article deals with the problem of inhomogeneous minimax problem solution, what is typical of scheduling theory. This problem is NPcomplete, and there is no exact algorithm for it, which has a polynomial time for large-scale problems. Therefore a quick algorithm that gets approximate tables is used. A possible method for solving this problem is considered a hybrid model, representing the synthesis of two genetic algorithms models, namely models Goldberg and CGS. Goldberg’s model is viewed from multiple crossovers and most promising mutation. As it is difficult to make calculations analytically and often impossible to make it in practice, the computational experiment was carried out in this article. The results of the experiment are described in the tables, which graphically show a comparison of the hybrid model effectiveness. The comparison is based on the accuracy results obtained for two types of crossovers with the basic parameters of genetic algorithm. It is proved that the use of hybrid algorithm leads to the results which are more précised to the optimal ones, despite the deterioration in the temporary search characteristics solutions.