A.M. Donetskov – Ph. D. (Eng.), Associate Professor, Department «Compute systems and networks», Kaluga branch of the Bauman MSTU. E-mail: firstname.lastname@example.org
The obtaining qualitative timetable of classes is a difficult process of integrating the various conflicting requirements imposed on the organization of the educational process. Main of all, taking into account methodological, organizational and personal requirements of professors.
When conducting lessons going on moving student groups and professors from one classroom to another. Therefore the problem of minimizing the transition of students and professors from the audience in the auditorium and from one building to another arises. There is a problem based on the priorities in the event of a conflict of interest. The manual way make timetables virtually impossible.
This problem relates in type of NP complete problems. That is, there are no accurate methods for solving problems of this type in a time O (nk), where k – constant. But since the dimension of problems ranging from a few thousand to hundreds of thousands of vertices (n), it is desirable in the proposed approach to solve this problem by using the algorithm is not worse than O (n4), otherwise the result in a reasonable time is not possible. Therefore, the most common way of solving the problem is to use a variety of «heuristics» that allow you to get results in a reasonable time, but the quality of the timetable is not predictable.
The author proposed an approach to solving this problem with the complexity of O(n4), which was implemented in the software package «Timetable». The program «Timetable» is successfully operating for 5 years in Kaluga Branch of the Bauman MSTU. Automated system «Timetable» takes into account the methodological and organizational requirements for scheduled training sessions, as well as take into account the wishes of of professors on the learning process.