The problems of forming a class schedule reflect a major pattern in scheduling theory: once a mathematical model provides a sufficiently complete description of the studying process the problem of forming a schedule becomes NP-complete in terms of R. Karp's definition. This implies the use of heuristic algorithms for constructing schedules or simplified models of the studying process. Yet another approach is possible: we first construct an h-schedule, corresponding to a matrix T and then transform it into an h-schedule meeting the necessary requirements. Within the present article we find three types of transformations that allow to pass from any given h-schedule A corresponding to a load matrix T to any h-schedule C that also corresponds to the load matrix T. We suggest a polynomial-time algorithm for such a transformation. Some combinatorial applications of the obtained results are outlined. In particular, we give a new proof of the criterion for a double stochastic matrix to be uniquely represented as a convex combination of permutation matrices. The graph analogues of our results allow to solve A. Kotzig's problem of localizing edge coloring transformations for bipartite multigraphs.

class schedule formation, load matrix, scheduling theory, schedule transformation

Mathematical problems and theory of numerical methods