ПОСТРОЕНИЕ РАСПИСАНИЙ УЧЕБНЫХ ЗАНЯТИЙ НА ОСНОВЕ РАСКРАСКИ ВЕРШИН ГРАФА
Аннотация
Приводится описание алгоритмов и программ для построения расписаний учебных занятий. Процесс составления расписания представляется как раскраска вершин графа с дополнительными ограничениями на множества цветов. Для оптимизации раскраски графа разрабатываются эвристические алгоритмы, которые позволяют строить практически приемлемые расписания учебных занятий в школах, колледжах или высших учебных заведениях. Система апробирована на реальной информации.
Об авторах
С. В. Балтак
СП ЗАО «Научсофт»
Беларусь
Беларусь
Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Беларусь
Список литературы
1. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 c.
2. Leighton, F.T. A graph coloring algorithm for large scheduling problems / F.T. Leighton // Journal of Research of the National Bureau of Standards. – Vol. 84. – 1979. – P. 489–506.
3. Werra, D. de. An introduction to timetabling / D. de Werra // European Journal of Operations Research. – Vol. 19. – 1985. – P. 151–162.
4. Tuza, Z. Graph colorings with local constraints: a survey / Z. Tuza // Discussions Mathematical Graph Theory. – Vol. 17. – 1997. – P. 101–228.
5. Расписание Про 2.3. – Mode of access: http://www.softsearch.ru/programs/28-705-raspisanie-pro-download.shtml.
6. Magic Timetable Master. – Mode of access: http://www.imagictimetablesoftware.com/
7. TimeTabler. – Mode of access: http://www.timetabler.com/
8. Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев, Ю.Н. Сотсков, В.А. Струсевич. – М.: Наука, 1989. – 328 c.
9. Харари, Ф. Теория графов / Ф. Харари – М.: Мир, 1973. – 300 c.
10. Haupt, R.L. Practical Genetic Algorithms / R.L. Haupt, S.E. Haupt. – NJ: John Wiley & Sons, 2004. – 261 p.
Рецензия
Для цитирования:
Балтак С.В., Сотсков Ю.Н. ПОСТРОЕНИЕ РАСПИСАНИЙ УЧЕБНЫХ ЗАНЯТИЙ НА ОСНОВЕ РАСКРАСКИ ВЕРШИН ГРАФА. Информатика. 2006;(3(11)):58-69.
Просмотров: 1064
Послать статью по эл. почте 