dtЦифровая трансформацияDigital Transformation2522-96132524-2822Educational Establishment “Belarusian State University of Informatics and Radioelectronics”dt-33Research ArticleНАУЧНЫЕ ПУБЛИКАЦИИSCIENTIFIC PUBLICATIONМодель построения расписания на основе прецедентовThe Scheduling Model Based on PrecedentsНестеренковС. Н.NesterenkovS.

м.т.н., начальник отдела ИТ ЦИИР БГУИР

 

Белорусский государственный университет информатики и радиоэлектроникиBelarus201530062015016173Copyright © Нестеренков С.Н., 20152015Нестеренков С.Н.Nesterenkov S.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://dt.bsuir.by/jour/article/view/33

В статье предложен подход по построения расписания занятий вуза на основе прецедентов. Модель базируется на математическом аппарате теории графов. В основу модели положены принципы поиска и доказательства изоморфизма графов. Процесс поиска изоморфизма графов описан в терминах реляционной алгебры. Проведены экспериментальные исследования, показавшие целесообразность использования данного подхода при подготовке реального расписания, а также возможность уменьшения размерности NP-полной задачи примерно на 38,5%.

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%.

ReferencesЕрунов В.П., Морковин И.И. Формирование оптимального расписания учебных занятий в вузе .// Вестн. ОГУ. – 2001. – № 3.Ерунов В.П., Морковин И.И. Формирование оптимального расписания учебных занятий в вузе .// Вестн. ОГУ. – 2001. – № 3.Костенко В.А., Винокуров А.В. Локально-оптимальные алгоритмы построения расписаний, основанные на использовании сетей Хопфилда. // Программирование. – 2003. – № 4. – С. 27 – 40.Костенко В.А., Винокуров А.В. Локально-оптимальные алгоритмы построения расписаний, основанные на использовании сетей Хопфилда. // Программирование. – 2003. – № 4. – С. 27 – 40.Ханов Г.В., Алабужев Е.В. Автоматизация составления расписаний с учетом неопределенности.// Информационные технологии в образовании, технике и медицине. Материалы международной конференции. В 3-х т. Т.1. – ВолГТУ, Волгоград, 2004.Ханов Г.В., Алабужев Е.В. Автоматизация составления расписаний с учетом неопределенности.// Информационные технологии в образовании, технике и медицине. Материалы международной конференции. В 3-х т. Т.1. – ВолГТУ, Волгоград, 2004.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.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.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.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.К.Дж. Дейт. Введение в системы баз данных. – М.: Вильямс, 2005.К.Дж. Дейт. Введение в системы баз данных. – М.: Вильямс, 2005.

The authors declare that there are no conflicts of interest present.