informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-703Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGПОСТРОЕНИЕ РАСПИСАНИЙ УЧЕБНЫХ ЗАНЯТИЙ НА ОСНОВЕ РАСКРАСКИ ВЕРШИН ГРАФАБалтакС. В.СотсковЮ. Н.СП ЗАО «Научсофт»BelarusОбъединенный институт проблем информатики НАН БеларусиBelarus20062012201803(11)5869Copyright © Балтак С.В., Сотсков Ю.Н., 20182018Балтак С.В., Сотсков Ю.Н.Балтак С.В., Сотсков Ю.Н.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/703

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

ReferencesГэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 c.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 c.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.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.Werra, D. de. An introduction to timetabling / D. de Werra // European Journal of Operations Research. – Vol. 19. – 1985. – P. 151–162.Werra, D. de. An introduction to timetabling / D. de Werra // European Journal of Operations Research. – Vol. 19. – 1985. – P. 151–162.Tuza, Z. Graph colorings with local constraints: a survey / Z. Tuza // Discussions Mathematical Graph Theory. – Vol. 17. – 1997. – P. 101–228.Tuza, Z. Graph colorings with local constraints: a survey / Z. Tuza // Discussions Mathematical Graph Theory. – Vol. 17. – 1997. – P. 101–228.Расписание Про 2.3. – Mode of access: http://www.softsearch.ru/programs/28-705-raspisanie-pro-download.shtml.Расписание Про 2.3. – Mode of access: http://www.softsearch.ru/programs/28-705-raspisanie-pro-download.shtml.Magic Timetable Master. – Mode of access: http://www.imagictimetablesoftware.com/Magic Timetable Master. – Mode of access: http://www.imagictimetablesoftware.com/TimeTabler. – Mode of access: http://www.timetabler.com/TimeTabler. – Mode of access: http://www.timetabler.com/Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев, Ю.Н. Сотсков, В.А. Струсевич. – М.: Наука, 1989. – 328 c.Танаев, В.С. Теория расписаний. Многостадийные системы / В.С. Танаев, Ю.Н. Сотсков, В.А. Струсевич. – М.: Наука, 1989. – 328 c.Харари, Ф. Теория графов / Ф. Харари – М.: Мир, 1973. – 300 c.Харари, Ф. Теория графов / Ф. Харари – М.: Мир, 1973. – 300 c.Haupt, R.L. Practical Genetic Algorithms / R.L. Haupt, S.E. Haupt. – NJ: John Wiley & Sons, 2004. – 261 p.Haupt, R.L. Practical Genetic Algorithms / R.L. Haupt, S.E. Haupt. – NJ: John Wiley & Sons, 2004. – 261 p.

The authors declare that there are no conflicts of interest present.