An approach to reducing the operating time of the modified Goldberg model in solving the inhomogeneous minimax problem

Abstract

An approach to reducing the operating time of the modified Goldberg model in solving the inhomogeneous minimax problem

Kobak V.G., Zhukovskiy A.G., Kuzin A.P, Tkhazaplizheva A.N.

Incoming article date: 19.03.2019

The article deals with the problem of solving the inhomogeneous minimax problem typical for the theory of schedules. This problem is NP-complete and for it there is no exact algorithm of the solution having polynomial time for problems of big dimension. A modified Goldberg model is considered as a method of solving this problem. Godberg's model is considered with several crossovers and the most effective mutation. Under certain parameters (a large number of individuals and repeats), the modified Goldberg model receives a solution for a long time, so the article analyzes in detail one of the approaches to reduce the operating time without loss of accuracy. Since it is extremely difficult and practically impossible to make calculations analytically, a computational experiment was put into operation. As a result of the computational experiment, the tables provide a comparison of the efficiency of the modified Goldberg model after the use of HT technology. The use of HT technology leads to a significant reduction in time costs.

Keywords: single-point crossover, two-point crossover genetic algorithm, modified Goldberg model, mutation, minimax problem, scheduling theory, individual, generation, hyper-threading