Tuesday, May 19, 2009

Задача составления расписания для ВУЗа как задача теории расписаний

Аудиторное время:одновременно не более &xi студентов
Преподавательское время:одновременно не более одной аудитории
Студенческое время:одновременно не более одной аудитории
Дано множества аудиторий, студентов и преподавателей. Пускай аудитории и преподаватели будут машинами, а студенты работами.
Для выполнения любой работы требуется два ресурса: преподаватель и аудитория.
Кроме того, мы можем рассмотреть студентов также в качестве машин, поскольку одним из ограничений является равномерная загрузка студентов дисциплинами (предметами). Тогда предметы будут рассматриваться как работы, т.е. дополнительно определяется множество дисциплин (предметов), а занятия по данному предмету будут операциями данной работы.
Исходя из этого каждой операции данной работы ставится в соответствие множество подмножеств множества машин, на которых допустимо выполнение этой операции.
Таким образом задача составления расписания для ВУЗа представлена как задача теории расписаний.
Особенностями данной задачи являетя то, что все операции длятся одинаковое время и имеют заранее известное множество возможных времён их начала; одно множество машин может одновременно выполнять одну операцию; поскольку длина расписания задана условием, то критерием может быть распределение операций в расписании, отвечающее определённым требованиям, например равномерная загрузка машин работами; традиционно операции в таком расписании повторяются с заранее заданной периодичностью, например одно занятие в две недели.

1 comment: