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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Диплом решение задачи построения расписаний учебных организаций

Информация:

Тип работы: Диплом. Добавлен: 21.5.2014. Сдан: 2012. Страниц: 41. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Содержание
1 Аннотация 3
2 Введение 4
3 Цели дипломной работы 5
4 Постановка задачи 6
4.1 Исходные данные 6
4.2 Расписание 8
4.3 Ограничения на расписание 9
4.4 Критерии оптимальности 9
5 Исследование задачи 11
5.1 Обзор программных средств 12
5.1.1 Цели обзора 12
5.1.2 Результаты обзора 12
5.1.3 Выводы 14
5.2 Обзор алгоритмов 14
5.2.1 Генетические алгоритмы 14
5.2.2 Алгоритмы с локальным преобразованием расписания 16
5.2.3 Метод имитации отжига 17
5.2.4 Алгоритмы ограниченного перебора 18
5.2.5 Жадные алгоритмы 19
5.2.6 Выводы 20
6 Описание алгоритма 22
6.1 Структуры данных 22
6.2 Основные операции 24
6.3 Описание основного алгоритма 26
6.4 Описание алгоритма ограниченного перебора 28
6.5 Алгоритм корректировки расписания 30
7 Описание программной реализации 32
7.1 Описание алгоритмической части 32
7.2 Описание интерфейсной части 32
8 Исследование алгоритма 33
8.1 Оценка сложности алгоритмов 33
8.2 Результаты испытаний 35
8.2.1 Методика испытаний 35
8.2.2 Результаты испытаний 36
9 Заключение 37
10 Список литературы 38

1 Аннотация
В данной работе рассматривается решение задачи построения расписаний учебных организаций. Была исследована применимость различных алгоритмов для решения поставленной задачи, сделан обзор ряда существующих программных средств, предназначенных для автоматического построения расписаний учебных организаций. В рамках данной работы был разработан алгоритм построения расписаний учебных организаций, сочетающий жадные стратегии и стратегии ограниченного перебора, и проведено исследование эффективности этого алгоритма на данных факультета ВМиК МГУ. Также в данной работе описаны созданные программные средства, реализующие основные функциональные возможности данного алгоритма.
2 Введение
Задача составления учебного расписания при кажущейся простоте постановки является весьма сложной. При составлении учебного расписания приходится учитывать целый ряд условий и ограничений. Некоторые из этих требований являются безусловными, без которых учебный процесс не может нормально функционировать. Такими требованиями являются, к примеру, назначение занятий в соответствии с учебным планом или исключение из расписания накладок в проведении занятий. Другие ограничения в той или иной мере определяют качество учебного процесса, как, например, равномерное распределение нагрузки в течение недели или требования к проведению определенных занятий в специализированных аудиториях. Некоторые условия могут лишь частично влиять на качество расписания, однако тоже могут являться немаловажными: личные пожелания преподавателей и учащихся к времени проведения занятий или минимизация переходов между аудиториями в течение учебного дня. Кроме этого, хотя многие из требований являются общими для многих учебных заведений, важность этих требований для различных учебных заведений могут различаться [1,2].
Однако при этом во многих учебных заведениях расписание составляется вручную и обычно представляет собой корректировку устоявшегося расписания и внесение в него незначительных доработок. Значительные же изменения в расписании представляют серьезную проблему, особенно при условии ограниченности учебных ресурсов.
В настоящее время существует ряд программных средств, позволяющих автоматизировать процесс создания и корректировки учебного расписания, однако они либо обладают ограниченными возможностями по заданию дополнительных ограничений и критериев качества расписания, либо всего лишь предоставляют возможность полуавтоматического составления и корректировки расписания при непосредственном участии в этом процессе человека.
3 Цели дипломной работы
Целями данной дипломной работы являются:
- разработка алгоритма построения расписаний, сочетающего жадные стратегии и стратегии ограниченного перебора;
- исследование эффективности алгоритма на данных факультета ВМиК МГУ;
- разработка инструментальных средств построения расписаний учебных организаций, позволяющих:
o строить расписание в автоматическом режиме;
o корректировать существующее расписание с минимальными изменениями
4 Постановка задачи
В этом разделе будет приведена формальная постановка задачи построения расписания учебных организаций. В данной постановке задачи рассматривается построение расписания на двухнедельный срок. Для каждой учебной группы и для каждого потока задаются учебные курсы (здесь и далее под курсом будем понимать определенное количество занятий по данной дисциплине за две недели). При этом для курсов, заданных для потока, дополнительно указывается, должны ли занятия быть поточными (т.е. проводится сразу для всех групп потока в одно время в одной аудитории), или занятия назначены отдельно для каждой группы потока. Исходя этих курсов строится множество размещаемых работ. Работа может быть размещена на одну из двух недель («мигалка») или на обе недели в один и тот же день в одинаковое время, соответственно определяя размещение одного или двух занятий из учебного плана. Каждый курс разбивается на несколько работ так, что при четном количестве занятий в курсе все работы размещаются на обе недели, а при нечетном - одна работа размещается на одну неделю, а остальные - на обе. Таким образом, каждая работа определяется наименованием дисциплины и множеством учебных групп, для которых эта работа должна быть выполнена, а также количеством занятий за две недели (одно или два).
4.1 Исходные данные
Исходные данные представляют собой набор из нескольких списков. Для каждого элемента списков может быть задан текстовый идентификатор (номер группы, наименование дисциплины, ФИО преподавателя и т.д.); это поле в описании списков опущены. Список типов аудиторий и список учебных корпусов не содержат дополнительной информации, кроме указанного поля, поэтому их формальное описание также не приводится.
1. Список дисциплин: D={di}(i=1..ND), где ND - количество дисциплин.
di=<{Type}, {Teacher}>
{Type} - список типов аудиторий, пригодных для занятий по данной дисциплине,
{Teacher} - список преподавателей, которые могут вести занятия по данной дисциплине. Здесь же может быть указано максимальное количество пар по данной дисциплине для данного преподавателя за двухнедельный период.
2. Список аудиторий: A={ai}(i=1..NA) , где NA - количество аудиторий.
ai=
Capacity - ёмкость (в полугруппах),
Price - стоимость одной пары,
Type - тип аудитории,
Building - учебный корпус, в котором находится аудитория.
3. Список преподавателей: P={pi}(i=1..NP), где NP - количество преподавателей.
pi=
Price - стоимость одной пары.
4. Список учебных групп: G={gi}(i=1..NG) , где NG - количество групп.
gi=<{Course}>
{Course} - список курсов для данной группы.
5. Список потоков: T={ti}(i=1..NT) , где NT - количество потоков.
ti=<{Group}, {Course}>
{Group} - список групп в потоке. При этом одна и та же группа может присутствовать в нескольких потоках,
{Course} - список учебных курсов для данного потока.
6. Учебный план: C={ci}(i=1..NC) , где NC - количество курсов.
ci=
Thread - флаг поточного занятия,
Disc - дисциплина,
Count - количество пар за двухнедельный период,
Teacher - априорно заданный преподаватель,
Room - априорно заданная аудитория.
Если преподаватель и/или аудитория для курса заданы априорно, то именно они будут использованы при размещении работ, соответствующих данному курсу. Кроме того, при задании курса можно указать, что для его проведения используются «внешние» преподаватель и/или аудитория, либо они вообще не требуются. В этом случае преподаватель и/или аудитория для соответствующих работ не назначаются.
Следующие два списка определяют расстояния между корпусами и частичный порядок между занятиями различных курсов:
1. Расстояния между учебными корпусами: BDst={bdsti}(i=1..NBDst), где NBDst - количество элементов в данном списке.
bdsti =
Building1, Building2 - учебные корпуса, для которых задается расстояние,
Dist - расстояние, заданное в парах (время, необходимое на перемещение между двуми данными учебными корпусами).
2. Частичный порядок между курсами: COrd={cordi}(i=1..NCOrd), где NCOrd - количество элементов в данном списке.
cordi =
Course1, Course2 - курсы, для которых задается порядок и расстояние,
Dist - расстояние, заданное в днях.
Если два курса связаны таким отношением, то занятия, соответствующие этим курсам, в расписании должны располагаться в том же порядке. При этом заданное расстояние - это минимальное количество дней между занятиями (например, если расстояние равно 1, то занятия должны быть, как минимум, размещены на два соседних дня; если расстояние равно 0, то важен только порядок между занятиями).
Для аудиторий, преподавателей и учебных групп могут быть заданы блокировки:
1. Блокировки для аудиторий: AB={abi}(i=1..NAB)
abi=
Room - аудитория,
Pair, Day - пара и день недели, на которые аудитория заблокирована,
Флаг BlockType определяет, является ли блокировка обязательной («жесткая» или «мягкая» блокировка).
2. Блокировки для преподавателей: PB={pbi}(i=1..NPB) - задаются аналогично блокировкам для аудиторий.
3. Блокировки для групп: GB={gbi}(i=1..NGB) - задаются аналогично блокировкам для аудиторий.
Элемент списка блокировок определяет, что использование данной аудитории (преподавателя, учебной группы) в данное время нежелательно. При этом нарушений «жестких» блокировок не допускается; в то время как нарушение «мягких» блокировок допустимо, но сопровождается увеличением значения штрафной функции.
4.2 Расписание
Расписание представляет собой множество работ, для каждой из которых указано время проведения, преподаватель (если необходимо) и аудитория (если необходимо):
Расписание: R={ri}
ri=
Thread - флаг поточного занятия (в зависимости от него Group определяет номер группы или потока),
Group - группа или поток (в зависимости от флага Thread),
Disc - дисциплина,
Teacher - назначенный преподаватель,
Room - аудитория,
Pair, Day - время размещения,
Week - указывает, расположена ли пара на четной и нечетной неделях.
4.3 Ограничения на расписание
1. Расписание соответствует заданному учебному плану (но не все работы могут быть размещены).
2. В расписании отсутствуют коллизии (у двух работ, назначенных на одно и то же время, должны различаться преподаватель и аудитория и множества групп не должны пересекаться).
3. Выполнены ограничения на возможность использования ресурсов: аудитория (преподаватель), назначенная для проведения занятия, должна быть допустимой для данной дисциплины.
4. Выполнено ограничение на количество учебных дней (ограничение на размерность сетки расписания).
5. Выполнено ограничение на количество пар в день (ограничение на размерность сетки расписания).
6. «Жесткие» блокировки не нарушаются.
7. Выполнено ограничение на количество пар в день для групп.
8. Выполнено ограничение на количество пар в день для преподавателей.
9. Выполнено ограничение на максимальное количество пар в неделю по данной дисциплине для данного преподавателя.
10. Должно соблюдаться отношение частичного порядка между курсами в расписании.
11. Если подряд идущие занятия для одной группы в один день проводятся в разных зданиях, то в расписании должно быть «окно» между этими парами, соответствующее расстоянию между зданиями.
4.4 Критерии оптимальности
Критерием оптимизации является минимизация штрафной функции, представляющей собой сумму слагаемых, отвечающих за различные параметры расписания :
1. - штраф за «окна» в расписании для групп
2. - штраф за «окна» в расписании для преподавателей
3. - суммарная стоимость аудиторий, где MaxRCost - максимальная стоимость аудитории.
Здесь и далее запись ai.b означает параметр b i-го элемента списка {ai}.
4. - суммарная стоимость работы преподавателей, где MaxPCost - максимальная стоимость работы преподавателей.
5. - штраф за занятие на N-й паре (алгоритм должен стремиться к размещению занятий ближе к началу учебного дня)
6. - штраф за суммарное перемещение групп между зданиями в течение одного учебного дня (distij - матрица расстояний между зданиями)
7.
8.
9.
10. - штраф за использование аудитории (по числу использованных аудиторий)
11. - штраф за задействование преподавателя (по числу задействованных преподавателей)
Значения ki, i=1..17 определяют важность тех или иных параметров и являются параметрами алгоритма.
5 Исследование задачи
Задача построения учебного расписания является частным случаем задачи построения расписаний, которая в наиболее общей постановке заключается в следующем. Имеется некоторая фиксированная система работ и множество ресурсов, которые могут быть использованы для выполнения работ. Необходимо определить порядок либо временные сроки выполнения работ, а также ресурсы для выполнения каждой работы, в соответствии с заданным критерием оптимальности расписания. Кроме этого, могут быть заданы дополнительные условия на частичный порядок работ в расписании, директивные сроки их выполнения, ограничения на использование ресурсов и т.д.
В большинстве случаев, задача построения расписания принадлежит к классу NP-полных в строгом смысле задач [3]. NP-полнота задач построения расписаний обусловила широкое применение для их решения эвристических алгоритмов, основанных на жадных стратегиях, алгоритмов ограниченного перебора и различных итерационных алгоритмов: генетические и эволюционные алгоритмы, алгоритмы имитации отжига, алгоритмы детерминированной коррекции расписания.
Сложность задачи построения расписания для учебного заведения заключается в следующем. Во-первых, в ней, как правило, присутствуют два класса ресурсов, используемых для выполнения работ - преподаватели и аудитории. Во-вторых, на учебное расписание и использование ресурсов накладывается большое количество ограничений и критериев качества, что приводит к тому, что в пространстве решений присутствует значительное количество решений, не удовлетворяющих условию корректности, а целевая функция имеет очень сложный «рельеф». И, в-третьих, некоторые требования сами по себе тяжело формализуемы в виде компонента целевой функции или ограничения на корректность расписания, или вовсе носят субъективный характер. Все это приводит к тому, что многие подходы, применяемые при решении других вариантов задачи построения расписаний, либо оказываются неприменимыми, либо показывают плохие результаты, и могут применяться только для решения н........


10 Список литературы
1. Ерунов В.П., Морковин И.И. Формирование оптимального расписания учебных занятий в ВУЗе // Вестник ОГУ. Оренбург: ОГУ, 2001. №3. С.55-63.
2. Marte M. Models and Algorithms for School Timetabling - A Constraint Programming Approach. // Dissertation. Fakultдt f?r Mathematik, Informatik und Statisitk der Ludwig-Maximilians-Universitдt, M?nchen. 2002.
3. Теория расписаний и вычислительные машины/ Под ред. Э.Г.Коффмана. М.: Наука, 1984.
4. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
5. Костенко В.А. Принципы построения генетических алгоритмов и их использование для решения задач оптимизации. // Труды IV Международной конференции «Дискретные модели в теории управляющих систем» (19-25 июня 2000 г.). М.: МАКС Пресс, 2000. С.49-55.
6. Lalescu L. Timetabling Experiments Using Genetic Algorithms. // Lucrare de Diploma. Facultatea de Automatica, Calculatoare si Electronica, Universitatea din Craiova, Craiova. 2003.
7. Каширина И.Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида. // Вестник ВГУ, Серия физика, математика. 2003. №1. С. 128-131.
8. Калашников А.В., Костенко В.А. Алгоритмы локальной оптимизации расписаний // Труды первой всероссийской научной конференции «Методы и средства обработки информации» (МСО’2003, Москва, 1-3 октября 2003 г). М.: МАКС Пресс, 2003.
9. Костенко В.А. Задача построения расписания при совместном проектировании аппаратных и программных средств // Программирование. 2002. №3.
10. Безгинов А.Н., Трегубов С.Ю. Обзор существующих методов составления расписаний // Информационные технологии и программирование: Межвузовский сборник статей. М.: МГИУ, 2005. С.5-18.
11. Уоссермен Ф. Нейрокомпьютерная техника: теория и практика. М.: Мир, 1992.
12. Матусевич О. Алгоритмы имитации отжига для задачи построения расписаний. // Дипломная работа. Московский Государственный Университет имени М.В.Ломоносова, факультет Вычислительной Математики и Кибернетики. Москва. 2004.
13. Костенко В.А. Алгоритмы оптимизации, опирающиеся на метод проб и ошибок, в совместном проектировании аппаратных и программных средств ВС. // Труды Всероссийской научной конференции «Высокопроизводительные вычисления и их приложения» (30 октября - 2 ноября 2000 г., г. Черноголовка). М.: Изд-во МГУ, 2000. С.123-127.
14. Костенко В.А., Калашников А.В. Исследование различных модификаций алгоритмов имитации отжига для решения задачи построения расписания многопроцессорных расписаний. // Дискретные модели в теории управляющих систем. Труды VII Международной конференции. М.: МАКС Пресс, 2006. С.179-184
15. T.Muller. Some Novel Approach to Lecture Timetabling. In Proceedings of the 4th Workshop of Constraint Programming for Decision and Control. CDPC’2002, Gliwice, 2002.
16. E.K.Burke, D.G.Elliman, R.F.Weare. A University Timetabling System Based on Graph Colouring and Constraint Manipulation. // Journal of Research on Computing in Education. 1993.
17. O.Rossi-Doria, B.Paechter. An Opinion Algorithm for University Course Timetabling. Technical Report. Napier University, Edinburgh, UK, 2004.


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.