МАТЕМАТИЧЕСКАЯ МОДЕЛЬ И АЛГОРИТМ ПОСТРОЕНИЯ РАСПИСАНИЯ УЧЕБНЫХ ЗАНЯТИЙ УНИВЕРСИТЕТА
##plugins.themes.bootstrap3.article.sidebar##
##plugins.themes.bootstrap3.article.main##
Аннотация
Представлена математическая модель составления расписания учебных занятий для университета на основе гиперграфа. В модели учтены обязательные ограничения: занятия, которые проводятся с одной и той же группой (одним и тем же преподавателем, в одной и той же аудитории), должны быть назначены на различные интервалы времени; выполнение всех аудиторных работ в течение всего планового периода; общее число всех видов занятий в выделенный промежуток времени не должно превышать имеющийся аудиторный фонд; отсутствие «форточек» для студентов; обеспечение возможности сдвоенности пар; обеспечение возможности проведения определенных пар в различные дни. Показаны критерии, по которым производится оптимизация. Представлена свертка всех критериев оптимизации в одну целевую функцию. Предложен алгоритм решения задачи методом раскраски гипервершин гиперграфа.
##plugins.themes.bootstrap3.article.details##
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Библиографические ссылки
Лазарев, А.А. Методы и алгоритмы решения задач теории расписаний для одного и нескольких приборов и их применение для задач комбинаторной оптимизации: дис. … д-ра физ.-мат. наук / А.А. Лазарев. – М.: Ин-т проблем управления им. В.А. Трапезникова РАН, 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.
Рекомендуемые статьи автора (авторов)
- М. В. ДЕКАНОВА, ЭКСПЕРТНОЕ РАНЖИРОВАНИЕ ВАЖНОСТИ ЧАСТНЫХ КРИТЕРИЕВ ОПТИМАЛЬНОСТИ РАСПИСАНИЯ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ, Вестник Полоцкого государственного университета. Серия С. Фундаментальные науки: № 12 (2015)
- М. В. ДЕКАНОВА, МЕТОДИКА ПРИМЕНЕНИЯ ДЕКОМПОЗИЦИИ ПРИ РЕШЕНИИ МНОГОКРИТЕРИАЛЬНОЙ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ, Вестник Полоцкого государственного университета. Серия С. Фундаментальные науки: № 4 (2014)
- М. В. ДЕКАНОВА, КОНКРЕТИЗАЦИЯ ПОСТАНОВОЧНЫХ ПРИНЦИПОВ ПРОБЛЕМЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ РАСПИСАНИЯ ЗАНЯТИЙ В УНИВЕРСИТЕТЕ, Вестник Полоцкого государственного университета. Серия С. Фундаментальные науки: № 4 (2014)