Some methods of solving the NP-difficult problem of optimal schedule for the university

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. © 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license ( Peer-review under responsibility of the scientific committee of the 13th International Symposium “Intelligent Systems” (INTELS'18).

Сборник материалов конференции
Elsevier B.V.
  • 1 RUDN University, Miklukho-Maklaya str. 6, Moscow, 117198, Russian Federation
  • 2 Federal Research Center, Computer Science and Control, Russian Academy of Sciences, 44/2, Vavilova str., Moscow, 119333, Russian Federation
Ключевые слова
Genetic algorithm; Intelligent method; Method of substitution; Method to color the vertices of the graph; Small variations of the optimal schedule
Дата создания
Дата изменения
Постоянная ссылка

Другие записи