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

обеспечение меры реляционности любого конкретного языка реляционных БД:

язык называется реляционным, если он обладает не меньшей выразительностью и

мощностью, чем реляционная алгебра или реляционное исчисление.

Наконец, в целостной части реляционной модели данных фиксируются два

базовых требования целостности, которые должны поддерживаться в любой

реляционной СУБД. Первое требование называется требованием целостности

сущностей. Второе требование называется требованием целостности по ссылкам.

После предварительного анализа математической модели системы и

способов организации данных, а также имеющегося на рынке ПО (иерархический

и сетевые способы организации предполагают объектно - орентированный подход

к организации данных и на сегодняшний день имеются такие СУБД (например,

Jasmin или Informix Dynamic Server), но на момент разработки возможности их

использования не было, в то же время существуют очень “мощные” реляционные

СУБД (к примеру Oracle 8i)) выбор был сделан в пользу реляционного способа

организации хранения данных.

2.3.2. ОПИСАНИЕ ВХОДНОЙ ИНФОРМАЦИИ

Вся необходимая для решения поставленной задачи информация задается до

начала итераций методов решения задачи составления расписания. Для

упрощения считается, что заданная информация является постоянной на всем

протяжении периода, для которого составляется расписание.

Не теряя определенной степени общности поставленной задачи, можно

определить некую совокупность входных данных, необходимых для формирования

ограничений и решения задачи, и в то же время общих для всех разновидностей

практических реализаций системы. В силу специфики поставленной задачи

(возможность сравнительно легкой адаптации математической модели для случая

практической реализации в рамках конкретного вуза) формы документов входной

информации не разрабатывались. Реквизиты входной информации описаны в

табл.2.

Таблица 2. Описание реквизитов входной информации

|Наименование реквизитов |Характеристика реквизитов |

|входных документов |Тип |Макс. длина|Точность |

| Фамилия, имя, отчество |текстов. | 100 | |

|преподавателя; | | | |

|Контактный телефон |текстов. |10 | |

|преподавателя; | | | |

|Ученая степень; |текстов. |50 | |

|Ученое звание; |текстов. |50 | |

|Кафедра; |текстов. |50 | |

|Название группы; |текстов. |50 | |

|Численный состав группы; |числов. |2 | |

|Название читаемого курса; |текстов. |50 | |

|Количество аудиторных часов; |числов. |2 | |

|Номера аудиторий; |числов. |3 | |

|Информация об аудиториях; |текстов. |50 | |

|Название предмета, читаемого |текстов. |50 | |

|преподавателем; | | | |

|Номер группы, где читается |числов. |3 | |

|предмет; | | | |

|Информация об аудиториях, где |текстов. |50 | |

|читается предмет. | | | |

Кроме этих данных для математической модели необходимо наличие еще

некоторых дополнительных данных, которые могут быть получены после анализа

входной информации программным путем.

2.3.3. РАЗРАБОТКА ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ ЗАДАЧИ

Произведем анализ исходной информации с целью определения состава и

структуры информации для последующей формализации и построения

информационно-логической модели данных (ИЛМ). Приведенная выше

математическая модель, а также дополнительные сведения из описания

предметной области позволяют определить роль реквизитов во взаимосвязанной

информации, содержащейся в документе. На основе такого анализа установим

функциональные зависимости реквизитов в соответствии с рекомендациями и

требованиями нормализации данных, после чего проведем саму нормализацию.

Цель нормализации состоит в том, чтобы уменьшить (но необязательно

устранить) избыточность данных. Однако иногда некоторая избыточность данных

создается намеренно, чтобы повысить эффективность работы программы. Дадим

определение трех форм нормализации базы данных.

Таблица находится в первой нормальной форме (1NF), если она имеет

первичный ключ, все атрибуты представляют собой простые типы данных и

отсутствуют повторяющиеся атрибуты. Чтобы соответствовать 1NF, домены

атрибутов должны быть атомарными значениями и не должно быть повторяющихся

групп атрибутов. Все повторяющиеся группы атрибутов должны быть перенесены

в новую таблицу.

Таблица находится во второй нормальной форме (2NF) тогда, когда она

находится в первой нормальной форме и каждый неключевой атрибут полностью

функционально зависит от первичного ключа (т.е. в 2NF каждый неключевой

атрибут должен полностью зависеть от полей первичного ключа).

Таблица находится в третьей нормальной форме (3NF), если она находится

в 2NF и не содержит транзитивных зависимостей. Транзитивные зависимости –

это функциональные зависимости между неключевыми атрибутами. Любой

неключевой атрибут, который функционально зависит от другого неключевого

атрибута той же таблицы, создает транзитивную зависимость и должен быть

перемещен в другую таблицу.

Получающиеся функциональные зависимости довольно тривиальны и очевидно

вытекают из математической модели, поэтому в дальнейшем описании они не

приводятся. Также в дальнейшем изложении опускаются промежуточные степени

нормализации. Поэтому приведем лишь окончательную инфологическую модель

базы данных (см. рис. 1.).

Рис.1. Инфологическая модель базы данных задачи

составления расписания занятий

2.3.4. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ОГРАНИЧЕНИЙ МАТЕМАТИЧЕСКОЙ

МОДЕЛИ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ

Составление ограничений (1) – (7) математической модели задачи

составления расписания является достаточно тривиальной задачей, решаемой с

помощью несложных SQL – запросов и не требующей предварительного анализа

входной информации. Поэтому подробнее лишь остановимся на ограничениях вида

(8).

Заметим, что в математической модели системы читаемый предмет

“привязывается” не к определенной аудитории проведения, а к некоторому

множеству аудиторий. Расстановка конкретных номеров аудиторий производится

уже после решения поставленной задачи. Ограничения вида (8) имеют смысл

только тогда, когда множества аудиторий пересекаются. В математической

модели системы предлагается учитывать все уникальные пересекающиеся пары в

виде ограничений. Количество этих пересечений может быть велико, что может

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

на скорость работы алгоритмов оптимизации. Однако можно существенно

уменьшить количество дополнительных ограничений.

Рассмотрим случай линейного расположения пересекающихся множеств (см.

рис. 2.).

Рис.2. Линейно пересекающиеся множества

В случае такого расположения множеств аудиторий для проведения занятий

общее число ограничений вида (8) будет n-1, где n – количество множеств.

Описанное выше расположение пересекающихся множеств может быть названо

линейным, так как при этом n пересекающихся множеств расположены как бы в

линию. Можно рассмотреть случай, когда множества пересекают друг друга

произвольным образом (см . рис. 3.).

Рис.3. Произвольно пересекающиеся множества

[pic]

Число ограничений вида (8) в этом случае можно уменьшить, проведя

формирование этих ограничений по аналогии со случаем линейного расположения

множеств. Для этого необходимо предположить, что, например, множества B и

D, пересекающиеся с A, являются одним множеством, определить область

пересечения такого множества с множеством A, после чего провести те же

самые действия с получившейся областью пересечения.

Подробнее об этом см. [2], стр. 210.

2.4. Результаты работы программы

При практической реализации системы особое внимание было уделено

задаче написания “ядра” системы – методам решения задачи и процедурам

формирования ограничений. Поскольку не ставилось задачи написать

полнофункциональный коммерческий продукт, интерфейсная часть была написана

для целей тестирования ядра и определения границ применимости алгоритмов,

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

модулей предобработки входных данных.

Ядро системы и интерфейсная часть были написаны на Delphi 6.0. Методы

решения и алгоритмы формирования ограничений написаны с использованием

объектно-ориентированнных технологий, что позволит в будущем легко

инкапсулировать их в дальнейшие модификации системы, не нарушая целостности

взаимодействия различных алгоритмов. Текст объектов методов решения задачи

приведен в приложении 2. База данных была реализована на СУБД Oracle 8i,

запросы к ней осуществляются на языке PL/SQL.

Исходные данные задачи заносятся в таблицы базы данных с помощью

запросных форм. Одна из таких форм приведена на рис. 3.

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

[pic]

Данных, получаемых в результате решения задачи, недостаточно для

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

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

в виде таблицы, пример которой см .рис. 4.

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

[pic]

Алгоритмы решения задачи были протестированы на различных выборках

исходных данных. Тестирование производилось на ЭВМ с процессором Intel

Pentium 350 Мгц, СУБД Oracle 8i был установлен на двухпроцессорном сервере:

2 CPU Intel Pentium II 350 Мгц, ОЗУ 384 Мб; в качестве канала связи

использовалась LAN с пропускной способностью до 100 Мбит/с. В качестве

тестовых исходных данных были использованы как реальные данные о группах,

преподавателях и читаемых предметах вечерней формы обучения ЧГУ на

1999/2000 учебные годы, так и случайно формируемые исходные данные

(читаемым предметам случайным образом определяли аудитории для проведения

занятий). В среднем производилось от 5 до 10 тестов для каждой тестируемой

размерности исходных данных. В результате получили данные, приведенные в

таблице 2. На рисунке 5. приведен график зависимости среднего времени

решения задачи от количества читаемых предметов и количества групп.

[pic]

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.

Программа отличается уникальным и очень мощным алгоритмом построения и

оптимизации расписания. Полученное автоматическое расписание практически не

требует ручной доработки, то есть даже при очень сложных и жестких

ограничениях автоматически размещаются все возможные занятия. Если в

исходных данных имеются неразрешимые противоречия, то их можно обнаружить и

устранить, используя специальный блок анализа.

Страницы: 1, 2, 3, 4