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

Исходные данные задачи заносятся втаблицы базы данных с помощью запросных форм. Одна из таких форм приведена нарис. 3.

Рис.3.Форма занесения исходных данных

Данных,получаемых в результате решения задачи, недостаточно для вывода расписаниязанятий непосредственно после решения задачи, поэтому был написан модульпостобработки данных. Конечное расписание занятий выводится в виде таблицы, примеркоторой см .рис. 4.

Рис.4. Пример расписания занятий

Алгоритмы решения задачи былипротестированы на различных выборках исходных данных. Тестированиепроизводилось на ЭВМ с процессором IntelPentium 350 Мгц,СУБД Oracle 8i был установлен на двухпроцессорномсервере: 2 CPU Intel Pentium II350 Мгц, ОЗУ 384 Мб; в качестве канала связи использовалась LAN с пропускной способностьюдо 100 Мбит/с. В качестве тестовых исходных данных были использованы какреальные данные о группах, преподавателях и читаемых предметах вечерней формыобучения ЧГУ на 1999/2000 учебные годы, так и случайно формируемые исходныеданные (читаемым предметам случайным образом определяли аудитории дляпроведения занятий). В среднем производилось от 5 до 10 тестов длякаждой тестируемой размерности исходных данных. В результате получили данные,приведенные в таблице 2. На рисунке 5. приведен график зависимости среднеговремени решения задачи от количества читаемых предметов и количества групп.

2.5. Анализ полученных результатов

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

Во-первых, использованная математическая модель содержит всебе “лишние” ограничения, существование которых обусловлено линейнойцелочисленной моделью, кроме этого каждому читаемому на потоке (поток можетсостоять и из одной группы) предмету ставится в соответствие 12 (для случаявечерников) переменных, каждая из которых представляет изсебя булеву переменную. Во-вторых, резко возрастает время решения задачипри увеличении входных данных. Это происходит из-за резкого увеличенияколичества переменных и ограничений в модели, в результате чего возрастаетразмерность массивов и соответственно время решения задачи. В-третьих,формализованная математически задача охватывает только задачу составлениярасписания для студентов вечерней формы обучения без учета переходов междукорпусами. Учет дополнительных требований увеличит количество ограниченийзадачи, что отрицательно повлияет на скорость работы алгоритмов решения.

Обратим внимание на возрастающую разницу между минимальным исредним значением времени решения задачи по мере увеличения размерности задачи.Эта разница соответствует тому, насколько “удачно” (наиболее близко к оптимальному) было найдено начальное допустимое базисноерешение задачи. Поэтому время решения задачи можно значительно уменьшить,“удачно” найдя начальное базисноедопустимое решение. Для поиска такого решения лучше всего использоватьэвристические и декомпозиционные алгоритмы.

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

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

ЛИТЕРАТУРА

1. Лагоша Б.А., Петропавловская А.В.Комплекс моделей и методов оптимизации расписания занятий в вузе // Экономика имат. методы. 1993. Т. 29. Вып. 4.

2. Ху Т.Целочисленное программирование и потоки в сетях. М.: Мир, 1979.

3. Лебедев С.С. Модификация методаБендерса частично целочисленного линейного программирования // Экономика и мат.методы. 1994. Т. 30. Вып. 2.

4. Лебедев С.С., Заславский А.А.Использование специального метода ветвей и границ для решения целочисленнойобобщенной транспортной задачи // Экономика и мат. методы. 1995. Т. 31. Вып. 2.

5. Заславский А.А. Использованиестратегии расслоения переменных в общих задачах целочисленного линейногопрограммирования // Экономика и мат. методы. 1997. Т. 33. Вып. 2.

6. Лебедев С.С. О методе упорядочивающейиндексации целочисленного линейного программирования // Экономика и мат.методы. 1997. Т. 33. Вып. 2.

7. Лебедев С.С., Заславский А.А.Модифицированный метод пометок для задач булева программирования // Экономика имат. методы. 1998. Т. 34. Вып. 4.

8. Заславский А.А. Комбинированныйметод решения задач о рюкзаке // Экономика и мат. методы. 1999. Т. 35. Вып. 1.

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

1. Система АВТОР-2+

Система АВТОР-2+ предназначена для быстpогои удобного составления расписаний занятий и сопровождения их в течение всегоучебного года.
АВТОР-2+ - универсальная система. Есть несколько версий программы,рассчитанные на любые учебные заведения:

- сpедниеи специализиpованные (математические, языковые и т.п.) школы, лицеи, гимназии;

- техникумы, училища иколледжи;

- ВУЗы с одним учебнымкорпусом;

- ВУЗы с несколькимиучебными корпусами (с учетом переездов между корпусами).

АВТОР-2+ позволяет максимально облегчить и автоматизиpовать сложный тpуд составителей расписания. Системапомогает легко стpоить, коppектиpовать и pаспечатыватьв виде удобных и наглядных документов:

- pасписания занятий классов (учебных групп);

- расписания пpеподавателей;

- расписание аудиторий(кабинетов);

- учебные планы;

- тарификацию.

АВТОР-2+ имеет пpиятный дизайн идpужеcтвенный сеpвис. Программа достаточно проста в освоении. Имеется подробноеруководство, в котором описаны все возможности и способы работы с программой.
Программа работает на любых IBM-совместимых компьютерах, начиная с486DX с оперативной памятью 4Mb (и выше), занимает около 1 Mb на жестком диске.Операционная система: MS DOS, либо WINDOWS 95/98.
Время работы зависит от размерности учебного заведения и мощностикомпьютера. Полный расчет и оптимизация расписания школы среднего размера (30классов, 60 преподавателей, две смены) идет около 15 минут на компьютере типаCeleron-400.

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

АВТОР-2+ позволяет:

- оптимизировать'окна' в расписании;

- учитывать требуемыйдиапазон дней/часов как для классов, так и дляпреподавателей;

- оптимально pазмещать занятия по кабинетам (аудиториям) с учетомособенностей классов, предметов, пpеподавателей и вместимости кабинетов;

- учитывать хаpактеp pаботы и пожелания как штатных сотpудников, так исовместителей-почасовиков;

- легко соединять('спаpивать') несколько классов (учебныхгрупп) в потоки пpи пpоведении любых занятий;

- pазделять классы пpи пpоведении занятий по иностранному языку,физической культуре, тpуду, информатике (и любым другим предметам) на любоеколичество подгрупп (до десяти!);

- вводить (помимоосновных пpедметов) спецкуpсы и факультативы;

- оптимизироватьравномерность и трудоемкость расписания.

Пожеланию заказчика АВТОР-2+ модифициpуется под условияконкретного учебного заведения.

2. Система “Расписание” ver 4.0 Москва – ЛинТех

Необходимо сразу жеотметить, что программа “Расписание” ориентирована на составление школьногорасписания, использование в ВУЗ`ах и колледжахвозможно лишь с некоторыми оговорками. Составление расписания производится врамках комплекса условий, которые определяются на шагах ввода исходных данных.Полный перечень возможных условий приведен ниже:

- Ограничен максимальныйномер урока – т.е. количество уроков, максимально допустимое в день;