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

| Категория реферата: Рефераты по информатике, программированию
| Теги реферата: мировая торговля, соціологія шпори
| Добавил(а) на сайт: Филофея.

1.2. Анализ существующего ПО

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

[pic]

[pic]

В силу объективных причин система составления расписания в вузе
(имеется в виду крупный государственный вуз) обязательно должна реализовывать ряд основных функций:

- учет пожеланий преподавателей;

- закрепление обязательных аудиторий;

- указание желательных аудиторий;

- учет перехода между корпусами;

- объединение групп в потоки по любой совокупности дисциплин;

- разбиение на подгруппы;

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

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

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

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

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

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

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

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

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

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

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

ГРУППЫ

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

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