English
!

Архив публикаций

Тезисы

XVI-ая конференция

Моделирование задачи составления расписаний предфрактальными графами

Кононова Н.В.

Россия, г.Ставрополь, E-mail: knv_fm@mail.ru

1  стр. (принято к публикации)

Задача составления расписаний является одной из наиболее распространённых задач, решаемых каждым человеком практически ежедневно. Поэтому с развитием вычислительных технологий ведутся разработки автоматизированных систем составления расписания. В некоторых частных случаях удалось разработать алгоритмы, способные найти решение за приемлемое время. В то же время большинство реальных задач составления расписания относятся к классу NP-полных. Это делает разработку алгоритма, способного решить их за допустимое время, действительно сложной задачей, даже если соответствующую предметную задачу можно поставить как однокритериальную. Ситуация существенно усугубляется тем, что большинство реальных задач составления расписаний многокритериальны. Различные задачи составления расписаний могут иметь много общего. Например, в задачах составления расписания занятий в вузе и графика работ на предприятии можно провести следующие аналогии между ресурсами: группы студентов и служащие, преподаватели и смены, аудитория и квалификация служащих, предметы и работодатели . Поэтому методы, разработанные для одного подкласса задач, часто можно перенести на другие.

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

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

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



© 2004 Дизайн Лицея Информационных технологий №1533