Preview

Информатика

Расширенный поиск

ПОСТРОЕНИЕ РАСПИСАНИЙ УЧЕБНЫХ ЗАНЯТИЙ НА ОСНОВЕ РАСКРАСКИ ВЕРШИН ГРАФА

Аннотация

Приводится описание алгоритмов и программ для построения расписаний учебных занятий. Процесс составления расписания представляется как раскраска вершин графа с дополнительными ограничениями на множества цветов. Для оптимизации раскраски графа разрабатываются эвристические алгоритмы, которые позволяют строить практически приемлемые расписания учебных занятий в школах, колледжах или высших учебных заведениях. Система апробирована на реальной информации.

Об авторах

С. В. Балтак
СП ЗАО «Научсофт»
Беларусь


Ю. Н. Сотсков
Объединенный институт проблем информатики НАН Беларуси
Беларусь


Список литературы

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.

Просмотров: 898


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)