ФОРМУЛИРОВКИ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЙ

Общая формулировка задачи составления расписаний

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

Формулировка задачи составления расписаний в применении к расписанию учебных занятий

Общая теория расписаний предполагает, что все обслуживающие устройства (или процессоры) не могут выполнять в данный момент времени более одного задания, что для расписания учебных занятий не является достаточным, если в качестве процессора при распределении заданий принять учебную аудиторию. Так как в некоторых случаях в одной аудитории могут проводится занятия с более чем одной группой одновременно, например общие лекции для нескольких потоков.

Поэтому, при переносе общей теории расписаний на расписание учебных занятий нами были сделаны следующий допущения:

  • все процессоры (т.е. в случае учебного расписания - аудитории) имеют вместимость - некоторое число C>=1. Вместимость процессора определяет количество заданий, которые он может одновременно "обрабатывать" в данный момент времени (в отношении неединичности процессоров было бы интересным рассмотреть вариант, когда в качестве процессора выступает не аудитория, а преподаватель, а в качестве задания - поток из одной или более учебных групп, с которыми он работает);
  • в качестве множества заданий для распределения выступают учебные занятия преподавателя с учебными группами;
  • модель времени в системе является дискретной; все распределение предполагается переодически повторяющимся на протяжении некоторого временного интервала (например две недели - числитель/знаменатель - на протяжении всего семестра);
  • все задания выполняются за одинаковое время, которое принимается за единицу дескретизации временного интервала;
  • задания имеют принадлежность к объектам, в качестве которых выступают учебные группы и преподаватели.

В итоге, формулировка задачи составления расписания учебных занятий звучит следующим образом: "Для заданного набора учебных аудиторий (в данном случае под учебной аудиторией понимается широкий круг помещений, в которых проводятся учебные занятия (от компьютерной лаборатории до спортивного зала)) и заданного набора временных интервалов (т.е. по сути, уроков или учебных пар) построить такое распределение учебных занятий для всех объектов (учителя и учебные группы), для которого выбраный критерий оптимальности является наилучшим".

В качестве критерия оптимальности в данном случае могут выступать различные показатели.

МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

Математическая модель

Проанализировав значительное число вариантов математических моделей задачи построения расписания, мы остановились на следующем.

Расписание представляется семеркой объектов: 

 G, <, [tijk], P, R, <', U
G = {T1, T2, …, Tn}-множество заданий;
<-отношение частичного порядка, заданное на множестве заданий G;
[tijk]-трехмерная матрица размером n x m x p, представляющая распределение заданий по процессорам в заданный интервал времени;
P = {P1, P2,…,Pm}-множество процессоров;
R = {R1, R2,…,Rp}-множество временных интервалов;
<'-отношение частичного порядка, заданное на множестве R;
U-множество ограничений.

Замечания:

  • В качестве операторов частичного порядка < и <', вообще говоря, можно выбрать любую функцию, которая упорядочивает заданные множества необходимым образом. Для оператора <' это может быть функция, выстраивающая временные интервалы таким образом, чтобы занятия с наименьшим временем начала были <' ("меньше") занятий с большим временем начала.
  • Выбор операторов упорядочивания должен основываться на предположениях оптимальности распределения (например, пусть нам надо максимально равномерно (примерно одинаково время начала и протяженность занятия) распределить учебные занятия по дням недели. Тогда мы можем выбрать следующее отношение частичного порядка <': 830 любого дня недели <'("меньше") 1010 любого дня недели).
  • При малой вместимости процессоров матрица распределения будет сильно разрежена.
  • Множество ограничений в общем случае может состоять из ограничений, наложенных на любые элементы системы, например, все занятия для аудитории P34 должны начинаться не раньше времени R46. Однако, при практической, реализации учитывать всевозможные ограничения не представляется возможным, поэтому реализовывая систему построения расписаний необходимо четко определить характер ограничений.

Особенности практической реализации модели системы

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

В качестве основных способов организации рекомендуется выбирать реляционный способ - данные в виде реляционных таблиц, организацию в виде иерархической структуры и сетевой способ организации с помощью сетевой базы данных.

Оценка - 1.0 (11)
2010-04-14 • Просмотров [ 3577 ]