The Scheduling Model Based on Precedents
Abstract
The paper presents an approach for university scheduling based on precedents. The model is based on the mathematical apparatus of the theory of graphs. The model uses the principles of finding and proof of the graph isomorphism. The process of finding of the graph isomorphism described in terms of relational algebra. Experimental studies showed expediency of this approach using in the preparation of the real schedule, as well as the possibility of reducing the dimension of the NP-complete problem approximately 38.5%.
About the Author
S. Nesterenkov
Белорусский государственный университет информатики и радиоэлектроники
Belarus
Belarus
References
1. Ерунов В.П., Морковин И.И. Формирование оптимального расписания учебных занятий в вузе .// Вестн. ОГУ. – 2001. – № 3.
2. Костенко В.А., Винокуров А.В. Локально-оптимальные алгоритмы построения расписаний, основанные на использовании сетей Хопфилда. // Программирование. – 2003. – № 4. – С. 27 – 40.
3. Ханов Г.В., Алабужев Е.В. Автоматизация составления расписаний с учетом неопределенности.// Информационные технологии в образовании, технике и медицине. Материалы международной конференции. В 3-х т. Т.1. – ВолГТУ, Волгоград, 2004.
4. L.P. Cordella, P. Foggia, C. Sansone, M. Vento. A (Sub) Graph Isomorphism Algorithm for Matching Large Graphs IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 26, no. 10, pp. 1367-1372, 2004.
5. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990.
6. К.Дж. Дейт. Введение в системы баз данных. – М.: Вильямс, 2005.
Review
For citations:
Nesterenkov S. The Scheduling Model Based on Precedents. Informatization of Education. 2015;(1):61-73. (In Russ.)
Views: 2882
Email this article 