KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №4, Moscow, 1992
Authors: Asratyan A.S., Mirumian A.N.
Transformations of class schedules
Abstract:
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.
Keywords:
class schedule formation, load matrix, scheduling theory, schedule transformation
Publication language: russian,  pages: 18 (p. 94-111)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Asratyan Armen Surenovich
  • Mirumian A.N.