ПОСТРОЕНИЕ РАСПИСАНИЙ УЧЕБНЫХ ЗАНЯТИЙ НА ОСНОВЕ РАСКРАСКИ ВЕРШИН ГРАФА
Abstract
Приводится описание алгоритмов и программ для построения расписаний учебных занятий. Процесс составления расписания представляется как раскраска вершин графа с дополнительными ограничениями на множества цветов. Для оптимизации раскраски графа разрабатываются эвристические алгоритмы, которые позволяют строить практически приемлемые расписания учебных занятий в школах, колледжах или высших учебных заведениях. Система апробирована на реальной информации.
About the Authors
С. Балтак
СП ЗАО «Научсофт»
Belarus
Belarus
Ю. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
References
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.
Review
For citations:
, . Informatics. 2006;(3(11)):58-69. (In Russ.)
Views: 963
Email this article 