Optimization of the solution of the problem of scheduling theory based on the evolutionary-genetic algorithm

Abstract

This article describes the genetic algorithm used to solve the problem related to the scheduling theory. A large number of different methods is described in the scientific literature. The main issue that faced the problem in question is that it is necessary to search the optimal solution in a large search space for the set of feasible solutions in a reasonable time, where the search for valid solutions is a challenging combinatorial task. Typically, for such problems, it is difficult to find any classic method of solution, which would be characterized by acceptable time spent. One of the main reasons is a large number of different constraints. Despite the great achievements and results in this area, the statement of schedule problem is quite abstract and in many cases cannot be used to solve practical problems. Specific details of tasks are considered in the context of each task. In practice, the solution of any tasks related to the planning, based on the use of algorithms to find solutions in a large space. In such cases, the use of genetic algorithms is one of the most common solutions. The purpose of our research was a genetic algorithm with small variations of basic solution finds the optimal solution. Presented genetic algorithm allows to reduce the search space and to propose a variant for the correct schedule. The article presents a mathematical model and describes the algorithm and results of computational experiments, the quality criteria of schedule are described.

Keywords: genetic algorithm; small variations; basic solution; optimal schedule