Разработка математической модели и ПО для задач составления расписания (стр. 2 из 12)

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

1.3.Постановка задачи.

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

- расписание составляется из расчета не более двух пар в день(что вполне подходит для случая вечерней формы обучения);

- все пары проводятся в одном корпусе;

- задача ставится в терминах линейного программирования;

- дальнейшая декомпозиция модели не производится;

- все коэффициенты модели и искомые переменные целочисленны;

Поставленнаязадача должна решаться одним из универсальных (не зависящих от целочисленныхзначений коэффициентов) методов целочисленного линейного программирования.

2.Разработка математической модели и практическая реализация системыавтоматического составления расписания2.1. Математическаямодель расписания в вузе

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

2.1.1.Обозначения

ГРУППЫ

В вузе имеется Nучебных групп, объединенных в Rпотоков; r – номерпотока, r = 1, ..., R, k_r – номер учебной группы в потоке r, k_r = 1, …, G_r.

Разбиение на групп на потоки осуществляется исходя изпринципов:

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

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

3. Количество потоков не лимитируется.

ЗАНЯТИЯ

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

Обозначим:

t – номер рабочего дня недели, t Є T_kr, где

T_kr–множество номеров рабочих дней для группы k_r;

j – номер пары,j = 1 ,…, J;

J – общееколичество пар.

С каждойучебной группой k_r потока r в течение недели, согласно учебномуплану, проводится W_kr занятий,из которых S_rлекционных и Q_krпрактических. Обозначим:

s_r – номердисциплины в списке лекционных занятий для потока r, s_r = 1 ,…,S_r;

q_kr – номердисциплины в списке практических занятий для группы k_r, q_kr = 1 ,…, Q_kr.

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

ПРЕПОДАВАТЕЛИ

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

Пустьp – номер(имя) преподавателя, p =1 ,…, P. Введем врассмотрение булевы значения и :

Учебнаянагрузка преподавателей планируется до составления расписания занятий, вследствиечего на данном этапе величины

и можно считать заданными. Для каждого преподавателя p, p = 1 ,…,P,задана также его аудиторная нагрузка - N_p часов в неделю.

АУДИТОРНЫЙФОНД

Занятия каждого потока могут проводиться только вопределенных аудиториях (например, практические занятия по информатике могут проводится только в дисплейных классах). Пусть:

{A₁_r} – множество аудиторий для лекций на потоке r;

{A₂_r} – множество аудиторий для практических занятий на потоке r;

A₁_r – число элементов множества {A₁_r};

A₂_r – число элементов множества {A₂_r};

A₁_r + A₂_r –число аудиторий объединения множеств {A₁_r}∩{A₂_r}.

Аудиторный фонд определяется до началасоставления расписания, поэтому множества можно считать заданными.

2.1.2.Переменные

Задача составления расписания заключается в определении длякаждой лекции (на потоке) и практического занятия (в группе) дня недели и парыв этот день с учетом выполнения конструируемых ниже ограничений и минимизациинекоторой целевой функции.

Введем следующие искомые булевы переменные: