Piecewise continuous paths in the task of building and optimizing schedules

A. M. Magomedov

Informacionnye tehnologii i vyčislitelnye sistemy, no. 1 (2018), pp. 78-84.

Résumé

Data for the schedule is given in a form of a bipartite graph where the vertices of the two parts of the graph are associated with specialized processors and tasks, and the edges are associated with prescribed operations of single-unit duration for processing by the processors. The schedule is viewed as a mapping from a set of graph edges to the set of positive integers – "colors" of edges (the set of discrete time intervals of single-unit duration assigned to perform a particular operation). Problem of edge interval coloring of a bipartite graph is considered as a theoretical-graph model for schedule of a multiprocessor system without downtime of the processors and job interruptions. Graph structures necessary for subsequent sections are defined in the Introduction. Using those in section 1 a number of properties of interval coloring are defined. Based on the concept of piecewise continuous path in section 2, we developed a heuristic algorithm for interval coloring, effective for both theoretical and practical problems of schedule optimizations. In the Conclusion we discuss the results of the application of software developed on the basis of that heuristic algorithm and future prospects.

Détail

Mots-clés : schedule, graph, algorithm, colors, complexity.