INFORMATION TECHNOLOGY OF THE TIMETABLE MATRIX GENERATION ACCORDING TO PERMANENT DECOMPOSITION

Abstract

The paper analyzes known approaches, methods, and information technologies for solving the problems of drawing up class schedules. The relevance of such problems is determined not only by the significant computational complexity of known methods but also by the presence of a number of additional requirements in each specific case, which significantly affect the solution method. The requirements that arise when drawing up schedules are often antagonistic and require certain compromise solutions. Therefore, the development of new approaches and methods for solving calendar planning problems is an urgent task.

The result of the work is the creation of information technology for drawing up a schedule of classes based on the method of permanent decomposition. This method allows you to generate combinatorial objects, in particular, systems of different representatives of the columns of the distribution matrices and is distinguished by the presence of a procedure for decomposing the modified permanent by row with memorization of the identifiers of the elements of the incidence matrix. At the same time, we are not talking about a classic permanent, but about a certain modification of it, which is proposed in the work. The concept of a modified incidence matrix is also proposed, which allows to correctly take into account the information about flows, and is distinguished by the introduction of additional columns for each teacher who has current pairs with the correct display of information about the structure of the flow.

The modified permanent decomposition algorithm includes a constructive procedure of forming systems of various representatives of the columns of the schedule matrix and recording column indices in memory cells and provides the possibility of the simultaneous presence of the teacher in several groups if flows are allowed. The appropriate decomposition algorithm with "memorization" can be used to solve a wide class of problems of generating combinatorial objects, particularly permutations, combinations, and subsets of various elements of some system of sets.

Conducted experiments and calculations of computational complexity confirm the effectiveness of the permanent decomposition method.