MATHEMATICAL MODEL AND ALGORITHM OF TIMETABLING AT UNIVERSITY
Article Sidebar
Main Article Content
Abstract
The mathematical model of drawing up the schedule of university studies on the basis of the hyper graph is presented. In the mathematical model obligatory restrictions are considered: classes, which are conducted with the same group (by the same teacher, in the same audience) must be appointed at various time intervals, all classroom assignments must be done during the planned period, the total number of all types of classes in the allocated period mustn’t exceed the available classroom fundre. The mustn’t be “free periods” for students, the must be possibility to have dual classes and to conduct certain classes in various days. Optimization carried out according to the following criteria: the uniformity of the distribution of classes during the day, the possibility of carrying out classes in a certain change, the minimization of the number of the days with an academic load, the minimization of “free periods” for teachers, lack of classes in certain days for teachers. The convolution of all optimization criteria is presented one criterion function. The algorithm of the task solution by method of a coloring of hyper tops of the hyper graph is offered.
Article Details
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
Лазарев, А.А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации: дис. … д-ра физ.-мат. наук / А.А. Лазарев. – М.: Ин-т проблем управления им. В.А. Трапезникова РАН, 1997. – 413 с.
Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев, Ю.Н. Сотсков, В.А. Струсевич. – М.: Наука, 1989. – 328 c.
Гафаров, Е.Р. Задачи теории расписаний. Алгоритмы и применение / Е.Р. Гафаров // Современные проблемы фундаментальных и прикладных наук: тр. 49-й науч. конф. МФТИ: Управление и прикладная математика. – Москва-Долгопрудный, 2006. – С. 82 – 83.
Баронов, В.В. Автоматизация управления предприятием / В.В. Баронов. – М.: Инфра-М, 2000.
Логоша, Б.А. Комплекс моделей и методов оптимизации расписания занятий в вузе / Б.А. Логоша, А.В. Петропавловская // Экономика и математические методы. – 1993. – Т. 29, № 4.
Строкина, Ю.Г. Алгоритмические процедуры формирования гетерогенных расписаний для производственных систем: дис. … канд. техн. наук / Ю.Г. Строкина. – Уфа: УГАТУ, 1997. – 150 с.
Волков, И.К. Исследование операций: учебник для вузов / И.К. Волков, Е.А. Загоруйко; под ред. В.С. Зарубина, А.П. Крищенко. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. – 436 с.
Ху, Т. Целочисленное программирование и потоки в сетях / Т. Ху; пер. с англ. – М.: Мир, 1974. – 520 с.
Таха, Хэмди А. Введение в исследование операций / Хэмди А. Таха. – 6-е изд.; пер. с англ. – М.: Издат. дом «Вильямс», 2001.
Сигал, И.Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: учеб. пособие / И.Х. Сигал, А.П. Иванова. – 2-е изд., испр. – М.: ФИЗМАТЛИТ, 2003. – 240 с.
Расписание Про 2.3 [Electronic resource].
Magic Timetable Master [Electronic resource].
TimeTabler [Electronic resource].
Burke, E.K. A University Тimetabling System Based on Graph Coloring and Constraint Manipulation / E.K. Burke, D.G. Elliman, R.F. Weare // Journal Of Research on Computing in Education. – 1993.
Бабкин, Э.А. Проектирование и реализация алгоритмов составления учебного расписания на основе многоагентных технологий / Э.А. Бабкин, И.М. Ретинский // Технические, программные и математи-ческие аспекты управления сложными распределенными системами: материалы науч.-техн. конф. – Нижний Новгород, 2003. – С. 10 –12.
Безгинов, А.Н. Обзор существующих методов составления расписания / А.Н. Безгинов, С.Ю. Трегубов // Информационные технологии и программирование: межвуз. сб. ст. – Вып. 2(14). – М.: МГИУ, 2005.
Ерунов, В.П. Формирование оптимального расписания учебных занятий в вузе / В.П. Ерунов, И.И. Морковин // Вестн. ОГУ. – 2001. – № 3.
Каширина, И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида / И.Л. Каширина // Вестн. ВГУ. – 2003. – № 1.
Костенко, В.А. Локально-оптимальные алгоритмы построения расписаний, основанные на использовании сетей Хопфилда / В.А. Костенко, А.В. Винокуров // Программирование. – 2003. – № 4. – С. 27 – 40.
Костин, С.А. Модели и алгоритмы глобальной оптимизации первоначального расписания вуза / С.А. Костин, Н.Н. Клеванский // Информационные технологии в образовании: XIV междунар. конф.-выст.: материалы конф. – М.: МИФИ, 2004.
Маслов, М.Г. Эвристический алгоритм решения задачи составления расписания учебных занятий в вузе / М.Г. Маслов // Математические методы в технике и технологиях: сб. тр. XV междунар. науч. конф., Тамбов, 2 – 4 июня 2002 г.: в 10-ти т. – Тамбов, 2002. – Т. 9. – С. 86 – 88.
Система моделей и методов рационального планирования и организации учебного процесса в вузе / под ред. В.В. Гусева, Н.Я. Краснера. – Воронеж: ВГУ, 1984. – 152 с.
Ханов, Г.В. Автоматизация составления расписаний с учетом неопределенности / Г.В. Ханов, Е.В. Алабужев // Информационные технологии в образовании, технике и медицине: материалы междунар. конф.: в 3-х т. Т. 1 / ВолгГТУ. – Волгоград, 2004.
Сотсков, Ю.Н. Построение расписаний учебных занятий на основе раскраски вершин графа / Ю.Н. Сотсков, С.В. Балтак // Информатика. – 2006. – С. 58 – 69.
Люггер, Джордж, Ф. Искусственный интеллект: стратегии и методы решения сложных проблем / Джордж, Ф. Люггер. – 4-е изд.; пер. с англ. – М.: Издат. дом «Вильяме», 2003. – 864 с.
Кузин, Л.Т. Основы кибернетики / Л.Т. Кузин: в 2 т. Т. 1. Математические основы кибернетики: учеб. пособие для вузов. – 2-е изд., перераб. и доп. – М.: Энергоатомиздат, 1994. – 576 с.
Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.
Харари, Ф. Теория графов / Ф. Харари. – М.: Мир, 1973. – 300 c.
Клеванский, Н.Н. Формирование расписания с использованием динамических критериев загруженности / Н.Н. Клеванский, Е.А. Макарцова // Информационные технологии в образовании: XI междунар. конф.-выст. Ч. IV. – М.: МИФИ, 2001. – С. 139 – 140.
Клеванский, Н.Н. Моделирование стратегии формирования расписания занятий вуза средствами реляционной алгебры / Н.Н. Клеванский, Е.А. Макарцова, С.А. Костин // Прикладные проблемы образовательной деятельности: межвуз. сб. науч. тр. – Воронеж: ВГПУ, 2003. – С. 71 – 74.
Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978. – 432 с.
Leighton, F.T. A graph coloring algorithm for large scheduling problems / F.T. Leighton // Journal of Research of the National Bureau of Standards. – 1979. – Vol. 84. – P. 489 – 506.
Werra D. de. An introduction to timetabling / D. de Werra // European Journal of Operations Research. – 1985. – Vol. 19. – P. 151 – 162.
Tuza Z. Graph colorings with local constraints: a survey / Z. Tuza // Discussions Mathematical Graph Theory. – 1997. – Vol. 17. – P. 101 – 228.
Most read articles by the same author(s)
- M. DEKANOVA, EXPERT RANKINGS OF IMPORTANCE OF INDIVIDUAL CRITERIA OF OPTIMALITY OF THE SCHEDULE UNDER CONDITIONS OF UNCERTAINTY, Vestnik of Polotsk State University. Part C. Fundamental Sciences: No. 12 (2015)
- M. DEKANOVA, TECHNIQUE OF APPLICATION OF THE PRINCIPLES OF DECOMPOSITION AT THE SOLUTION OF THE MULTICRITERIA PROBLEM OF TIMETABLING, Vestnik of Polotsk State University. Part C. Fundamental Sciences: No. 4 (2014)
- M. DEKANOVA, METHODS OF SOLVING MULTICRITERIA PROBLEM SCHEDULE OF TRAINING SESSIONS UNIVERSITY, Vestnik of Polotsk State University. Part C. Fundamental Sciences: No. 4 (2014)