Дипломная работа: Разработка математической модели и ПО для задач составления расписания
В случае вузов спрос на системы составления расписаний пожалуй даже больше, чем для школ, но дело осложняется большой спецификой организации учебного процесса в каждом отдельно взятом вузе. Создать унифицированное программное обеспечение не представляется возможным, а стоимость создания специализированного продукта у сторонних разработчиков оказывается неоправданно велика. Кроме того, обязательным условием является наличие "устоявшегося" расписания, что предполагает наличие возможности осуществлять замену преподавателей или время проведения занятий. Пока ни один программный продукт не позволяет достаточно просто этого делать (хотя некоторые возможности и есть в "Методисте").
1.3. Постановка задачи.Целью данной работы было создание такой математической модели расписания в вузе, которая позволяла бы эффективно (в заданные сроки и с заданной степенью оптимальности) решать задачу автоматического составления расписания и обладала бы гибкостью (незначительных изменений в случае изменений входной информации) для адаптации системы в рамках конкретной практической задачи. Для некоторого упрощения задачи на начальном этапе проектирования были сделаны некоторые допущения:
- расписание составляется из расчета не более двух пар в день (что вполне подходит для случая вечерней формы обучения);
- все пары проводятся в одном корпусе;
- задача ставится в терминах линейного программирования;
- дальнейшая декомпозиция модели не производится;
- все коэффициенты модели и искомые переменные целочисленны;
Поставленная задача должна решаться одним из универсальных (не зависящих от целочисленных значений коэффициентов) методов целочисленного линейного программирования.
2. Разработка математической модели и практическая реализация системы автоматического составления расписания 2.1. Математическая модель расписания в вузе
Построим математическую модель расписания в вузе в терминах линейного программирования. Введем обозначения и определим переменные и ограничения.
2.1.1. ОбозначенияГРУППЫ
В вузе имеется N учебных групп, объединенных в R потоков; r – номер потока, r = 1, ..., R, kr – номер учебной группы в потоке r, kr = 1, …, Gr.
Разбиение на групп на потоки осуществляется исходя из принципов:
1. Использование двумя группами одного и того же аудиторного фонда для своих лекций автоматически предполагает помещение их в 1 поток (предполагается, что все лекции учебных групп проходят вместе).
2. Группа(или ее часть), как единица учебного процесса в вузе, может входить в разные потоки, но только по одному раз в каждый из них.
3. Количество потоков не лимитируется.
ЗАНЯТИЯ
Занятия проводятся в рабочие дни в полуторочасовые интервалы, которые будем называть парами.
Обозначим:
t – номер рабочего дня недели, t Є Tkr, где
Tkr – множество номеров рабочих дней для группы kr;
j – номер пары, j = 1 ,…, J;
J – общее количество пар.
С каждой учебной группой kr потока r в течение недели, согласно учебному плану, проводится Wkr занятий, из которых Sr лекционных и Qkr практических. Обозначим:
sr – номер дисциплины в списке лекционных занятий для потока r, sr = 1 ,…,Sr;
qkr – номер дисциплины в списке практических занятий для группы kr, qkr = 1 ,…, Qkr.
Предполагается, что лекции проводятся у всех групп потока одновременно и в одной аудитории. Тогда, если по какой-то дисциплине в течение недели проводится более одного занятия, эта дисциплина упоминается в списке лекций или практических занятий столько раз, сколько их предусматривается учебным планом для каждого потока или группы.
ПРЕПОДАВАТЕЛИ
Пусть
p – номер
(имя) преподавателя, p =
1 ,…, P. Введем в
рассмотрение булевы значения 
и 
:
|
 |
|
=
Учебная
нагрузка преподавателей планируется до составления расписания занятий, вследствие
чего на данном этапе величины 
и 
можно считать заданными. Для каждого преподавателя p, p = 1 ,…,P,
задана также его аудиторная нагрузка - Np часов в неделю.
АУДИТОРНЫЙ ФОНД
Занятия каждого потока могут проводиться только в определенных аудиториях (например, практические занятия по информатике могут проводится только в дисплейных классах). Пусть:
{A1r} – множество аудиторий для лекций на потоке r;
{A2r} – множество аудиторий для практических занятий на потоке r;
A1r – число элементов множества {A1r};
A2r – число элементов множества {A2r};
A1r + A2r –
число аудиторий объединения множеств {A1r}∩{A2r}.
Аудиторный фонд определяется до начала составления расписания, поэтому множества можно считать заданными.
2.1.2. ПеременныеЗадача составления расписания заключается в определении для каждой лекции (на потоке) и практического занятия (в группе) дня недели и пары в этот день с учетом выполнения конструируемых ниже ограничений и минимизации некоторой целевой функции.
Введем следующие искомые булевы переменные:
 |
|
|
=
=
В случае составления расписания для групп вечерней формы обучения J=2. Обобщение модели на все формы обучения см. [1], стр. 669.
2.1.3. ОграниченияДля каждой группы kr должны выполняться все виды аудиторной работы в течение недели:
|
В любой день t на каждой паре j для каждой группы kr может проводиться не более одного занятия:
|
Каждые лекция sr и практическое занятие qkr соответственно для всех потоков r и всех групп kr могут проводиться не более одного раза в любой день t:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 |
