Модель построения расписания на основе прецедентов
Аннотация
В статье предложен подход по построения расписания занятий вуза на основе прецедентов. Модель базируется на математическом аппарате теории графов. В основу модели положены принципы поиска и доказательства изоморфизма графов. Процесс поиска изоморфизма графов описан в терминах реляционной алгебры. Проведены экспериментальные исследования, показавшие целесообразность использования данного подхода при подготовке реального расписания, а также возможность уменьшения размерности NP-полной задачи примерно на 38,5%.
Об авторе
С. Н. Нестеренков
Белорусский государственный университет информатики и радиоэлектроники
Беларусь
Беларусь
м.т.н., начальник отдела ИТ ЦИИР БГУИР
Список литературы
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.
Рецензия
Для цитирования:
Нестеренков С.Н. Модель построения расписания на основе прецедентов. Информатизация образования. 2015;(1):61-73.
For citation:
Nesterenkov S. The Scheduling Model Based on Precedents. Informatization of Education. 2015;(1):61-73. (In Russ.)
Просмотров: 2878
Послать статью по эл. почте 