Fedorenko N. Development of methods and algorithms for solving anomalous and generalized parallel scheduling tasks

The object is optimization tasks on graphs and methods of their solving. The aim is the development of methods and algorithms for solving anomalous and generalized parallel scheduling tasks. Methods are the methods of discrete optimization, combinatorial analysis, statistical analysis. In the paper, we define and prove the necessary conditions for the four main types of anomalies for solving the task of creating a scheduler of the given width and minimum length for directed graphs with vertices having non-unit weights if the priority list is defined, and for its dual problem. The class of digraphs, for which the existence of transitive arcs does not affect the optimality of the algorithm based on the defining of lexicographical marks, and classes of digraphs, for which the existence of transitive arcs always affects optimality, are described. The necessary conditions under which the optimal scheduler will break the level principle are defined. The lower bounds of the width of the scheduler for the task of building scheduler of the given length and minimum width are proposed. The algorithms for solving classic and generalized scheduler problems, such as building the minimal width scheduler with the given length, building all schedulers of the given length, building schedulers of the given width, as well as schedulers with width defined with the bounding sequence, and scheduling for digraphs with vertices of two types, are developed. Scope - machine building, metallurgy, the learning process. Scope - parallelization of computing, resource management, the learning process.