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

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

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

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

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

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

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

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. Введем в рассмотрение булевы значения и :

1, если на потоке r лекцию sr читает преподаватель p; 0 – в противном случае;