Logo GenDocs.ru

Поиск по сайту:  


Загрузка...

Диплом - Разработка математической модели и программного обеспечения для задач составления расписания занятий - файл 1.doc


Диплом - Разработка математической модели и программного обеспечения для задач составления расписания занятий
скачать (1162 kb.)

Доступные файлы (1):

1.doc1162kb.18.11.2011 00:47скачать

содержание
Загрузка...

1.doc

  1   2   3   4   5   6   7   8   9   10
Реклама MarketGid:
Загрузка...


Содержание


Введение 4

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

^ 1. ОПИСАНИЕ ТЕХНОЛОГИЧЕСКОЙ ОБЛАСТИ 6

1.1. Формулировка задачи составления расписания 6

1.1.1. Общая формулировка задачи составления расписаний 6

1.1.2. Формулировка задачи составления раписания в применении к расписанию учебных занятий. 6

1.2. Анализ существующего ПРОГРАМНОГО ОБЕСПЕЧЕНИЯ 7

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

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

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

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

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

2.1.3. Ограничения 13

2.1.4. Целевая функция 15

^ 2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ 17

2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ 18

2.2.2 Прямой алгоритм целочисленного программирования 22

2.2.3. ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА 27

^ 2.3. ОСОБЕННОСТИ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ СИСТЕМЫ 30

2.3.1. ВЫБОР МОДЕЛИ 30

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

Наименование реквизитов 34

Характеристика реквизитов 34

Тип 34

Макс. длина 34

Точность 34

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

2.3.4. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ОГРАНИЧЕНИЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ 36

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

A Xa B Xb C Xc D Xd E 37

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

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

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

41

Выводы 43

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

Приложение 2. 58

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

Введение




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

Одна из основных составляющих этого процесса - расписание занятий - регламентирует трудовой ритм, влияет на творческую отдачу преподавателей, поэтому его можно рассматривать как фактор оптимизации использования ограниченных трудовых ресурсов - преподавательского состава. Технологию же разработки расписания следует воспринимать не только как трудоемкий технический процесс, объект механизации и автоматизации с использованием ЭВМ, но и как акцию оптимального управления [10, 11]. Таким образом, это - проблема разработки оптимальных расписаний занятий в вузах с очевидным экономическим эффектом. Поскольку интересы участников учебного процесса многообразны, задача составления расписания - многокритериальная.

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

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


Для реализации указанной цели необходимо решение следующих задач:

– анализ существующего программного обеспечения по составлению расписания занятий и их развитие;

– выявление требований, которые предъявляются к программного обеспечения как к специализированному продукту, ориентированному на работу в компьютерной сети;

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

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

Задачу составления расписания не стоит рассматривать только как некую программу, реализующую функцию механического распределения занятий в начале семестра, на которой ее (программы) использование и заканчивается. Экономический эффект от более эффективного использования трудовых ресурсов может быть достигнут только в результате кропотливой работы по управлению этими трудовыми ресурсами [5]. Расписание здесь является лишь инструментом такого управления, и для наиболее полного его использования необходимо, чтобы программа сочетала в себе не только средства для составления оптимального расписания, но и средства для поддержания его оптимальности в случае изменения некоторых входных данных, которые на момент составления расписания считались постоянными. Кроме этого оптимальное управление такой сложной системой невозможно без накопления некоей статистической информации о процессах, происходящих в системе[14]. Потому сама задача составления оптимального расписания является лишь частью сложной системы управления учебным процессом.
^

1. ОПИСАНИЕ ТЕХНОЛОГИЧЕСКОЙ ОБЛАСТИ




1.1. Формулировка задачи составления расписания

1.1.1. Общая формулировка задачи составления расписаний




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

^

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



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

Поэтому при переносе общей теории расписаний на расписание учебных занятий были сделаны следующие допущения:

  • все процессоры (т.е. в случае учебного расписания - аудитории) имеют вместимость - некоторое число C ≥ 1. Вместимость процессора определяет количество заданий, которые он может одновременно "обрабатывать" в данный момент времени (в отношении неединичности процессоров было бы интересным рассмотреть вариант, когда в качестве процессора выступает не аудитория, а преподаватель, а в качестве задания - поток из одной или более учебных групп, с которыми он работает);

  • в качестве множества заданий для распределения выступают учебные занятия преподавателя с учебными группами;

  • модель времени в системе является дискретной; все распределение предполагается периодически повторяющимся на протяжении некоторого временного интервала;

  • все задания выполняются за одинаковое время, которое принимается за единицу дискретизации временного интервала;

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

В итоге, формулировка задачи составления расписания учебных занятий звучит следующим образом: "Для заданного набора учебных аудиторий (в данном случае под учебной аудиторией понимается широкий круг помещений, в которых проводятся учебные занятия (от компьютерной аудитории до спортивного зала)) и заданного набора временных интервалов (т.е. по сути, уроков или учебных пар) построить такое распределение учебных занятий для всех объектов (учителя и учебные группы), для которого выбранный критерий оптимальности является наилучшим" [1].
  1   2   3   4   5   6   7   8   9   10



Скачать файл (1162 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru