INFORMATION TECHNOLOGY FOR THE SCHEDULE GENERATION BASED ON THE ALGEBRA OF ADDITIVE-DISJUNCTIVE FORMS AND THE MODIFIED METHOD OF PERMANENT DECOMPOSITION

Abstract

To improve the information technology of drawing up class schedules, there is a need to develop methods that allow significantly reduce the number of combinatorial objects in the process of algorithms for generating schedules matrices. For example, the result of applying the method of permanent decomposition is a collection of combinatorial objects - permutations, combinations, and placements. For the task of drawing up lesson schedules in the part of forming timetable matrices, the method provides a memory-recorded set of all possible systems of various representatives of sets, which are the columns of the timetable matrices (SRPS). Since the algorithm of permanent decomposition gives all possible SRPS, it creates the problem of forming the final schedule based on SRPS or all possible variants of schedules and requires the development of special algorithms. Certain known approaches to solving such a problem are associated with significant computational complexity in the general case. This also applies to the approach based on the order relation of the set of decomposition matrices.

The basis of the information technology proposed in the work is the further modification of the incidence matrices and, accordingly, such a modification of the permanent decomposition method, which allows generating ready versions of the schedule matrices at the output. This is achieved due to the introduction of a special algebra of additive-disjunctive forms and, accordingly, the possibility of generating such forms in the process of permanent decomposition. In fact, in this context, ADF is a formal representation of a ready-made version of an admissible schedule that satisfies some additional requirements.