Some Methods of Solving the NP-difficult Problem of Optimal Schedule for the University

Abstract The task of an optimal scheduling of training sessions is a combinatorial type problem, and its characteristic feature is a large dimension. In addition, the task is complicated by the presence of a large number of complex shape constraints. At present, there are no universal methods for solving such problems. Classical scheduling theory includes only a narrow circle of well-formalized problems that are usually reduced to the task of a salesman, transportation, etc. Direct application of the methods to the problem of scheduling training sessions is not possible. However, there are a number of heuristic and brute force methods that are quite amenable to programming. This article presents an analysis of some existing approaches to solve the problem of scheduling such as: replacement method, graph coloring method, intelligent method, genetic algorithm. The advantages and disadvantages of each of them are highlighted. It is concluded that the problem of scheduling refers to the class of discrete optimization with a finite set of alternatives. The task of scheduling is complicated by multi-criteria. It is concluded that it is necessary to apply an integrated approach that takes into account the advantages of the considered methods of this work to solve the problem.