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

РГУ имени  С.А. Есенина 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Реферат по информатике

на тему:

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

                                                            Выполнила: студентка 

Факультета  экономики

1 курса, группы Ф 11

Кузина  Ольга

Проверил:

Андреев Валерий Владимирович 
 
 
 

Рязань, 2009 г.

Содержание:

1. Исследования         3
2. Автоматизированная система составления расписаний занятий  4
3. Автоматизированная система «Расписание»     5
4. Автоматизированная система генерирования учебного расписания ВУЗа 7

    «Университет»

5. Технология компьютерного составления расписания занятий   8
6. Программы для составления расписаний      10
7. Список литературы         13

Исследования

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

    Основным  объектом манипулирования являются занятия, которые в соответствии с учебным планом нужно распределить в расписании. Для преподавателей и аудиторий задаются специализации, т.е. множество занятий, которые может проводить (могут проводиться) этим преподавателем (в этой аудитории). Специализации не являются строгими, а отражают предпочтения в проведении. Для управления процессом вывода используются явные запрещающие правила, представляющие набор из 5 параметров (преподаватель, аудитория, занятие, группа, время). Параметр в правиле может быть указан явно (значение из справочных таблиц системы) или иметь значение "Любой". Правила, в которых значение "Любой" соответствует всем параметрам, запрещены. Правила сгруппированы по смыслу в группы, определяемые пользователем (например, группа предпочтений конкретного преподавателя). Время в системе является дискретной величиной, ограниченной количеством дней в неделю и количеством пар в день.

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

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

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

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

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

    Разработанная автоматизированная система, позволяет  учитывать многочисленные факторы, влияющие на процесс составления  расписания, например: наличие определенных аудиторий в конкретное время  и соответствие аудиторий проводимым занятиям (вместимость, тип аудитории – лекционная, практическая, компьютерный класс). Кроме того, системой отслеживается целый ряд “узких мест” процесса составления расписания занятий, что значительно уменьшает вероятность возникновения ошибок, основанных на человеческом факторе.

    Выходными данными системы являются карточки загрузки аудиторий, кафедр, непосредственно  само расписание занятий. Необходимо отметить, что информация о расписании занятий  используется другими автоматизированными системами, например: “автоматизированная система учета использования учебных помещений при решении задачи расчета себестоимости образовательных услуг”.

АВТОМАТИЗИРОВАННАЯ СИСТЕМА «РАСПИСАНИЕ»

    А.М.Донецков

    Организация учебного процесса в ВУЗе является основой подготовки высоко квалифицированных специалистов. Базисом учебного процесса обучения является составление «оптимального» расписания учебных занятий. Расписание учебных занятий должно удовлетворять требованиям по обеспечению все более возрастающих требований к будущим специалистам.

    На  сегодняшний день существует множество  различных подходов к решению  данной задачи. Автором предлагается описание автоматизированной системы «Расписание» составления расписания учебных занятий в ВУЗе. Основу математического обеспечения данной системы является оригинальный подход, разработанный автором.

    Для начала составления расписания необходимо подготовить следующую информацию:

1. Полное и краткое название ВУЗа.
2. Название составляемого расписания.
3. График учебы (количество пар в день, название пар, наименование времени начала окончания пар и выделение пар, в которые занятия не проводятся, например, воскресенье).
4. Список факультетов (факультет должен быть хотя бы один).
5. Список кафедр (кафедра должна быть хотя бы одна).
6. Список преподавателей по кафедрам (необходимо указать Ф.,И., О. год рождения, пол, список аудиторий , в которых желательно проводить занятия, перечень пар, в которых может проводить занятия данный преподаватель и максимальное количество часов в день).
7. Список групп (количество студентов, идентификаторы группы, закрепленные аудитории, пары, в которые данная группа может проводить занятия и максимальное количество часов в день).
8. Список потоков (поток – основа системы, состоящий из идентификаторов группы).
9. Список корпусов.
10. Список аудиторий, распределенных по корпусам (вместимость аудитории и описание аудитории, перечень пар, в которых может проводить занятия в данной аудитории).
11. Перечень списков аудиторий, предназначенный для уменьшения ввода информации о занятиях.
12. Перечень названий должностей преподавателей (профессор, доцент, старший преподаватель, ассистент).
13. Перечень названий степеней преподавателей (д.т.н., д.ф-м.н., к.т.н.).
14. Перечень типов названий занятий, проводимых в ВУЗе (лекция, семинар, лаб. работа, к.р., к.п.)
15. Список дисциплин, читаемых в ВУЗе.
16. Перечень занятий, которые необходимо расставить (занятие в системе «Расписание» есть совокупность следующих объектов: название дисциплины, тип занятия, поток, преподаватели, которые ведут занятие, количество часов в день, список аудиторий, в которых может проходить данное занятие).

    В качестве СУБД на данном этапе разработки автоматизированной системы для  хранения информации о расписании предложено использовать MS ACCESS. Информацию о расписании можно вводить как средствами  MS ACCESS, так и программой «Расписание».

    Преподаватели указывают возможные варианты проведения своих занятий, т.е. дни и пары, когда они могут проводить  занятия. Также указывается максимальное количество часов занятий в день, которое может проводить преподаватель. При составлении расписания есть занятия, у которых на момент составления не известен преподаватель или не важен. В этом случае используется «преподаватель-заглушка». «Преподаватель-заглушка» в системе «Расписание» считается преподаватель, фамилия которого начинается с символа «!».

    Для группы указывается график работы (первая, вторая или вечерняя смена), количество студентов и максимальное количество часов занятий в день, которое  может проводить в группе. Группа состоит из «идентификаторов» (условно их можно назвать студентов). Количество идентификаторов зависит от количества потоков, на которые делится группа, но должно быть не менее одного и не более количества студентов в группе. Если группа не делится на потоки, то идентификатор должен быть один. Например, группа делится на занятия «Информатики» на две подгруппы, а на занятия «Иностранный язык» на три подгруппы, то количество идентификаторов должно быть 2*3 (шесть).

    Поток есть единица расписания, которая  указывается в занятии. Поток  может состоять из одной группы, из нескольких групп или частей групп. Потоки необходимо формировать так, чтобы один студент (идентификатор) не мог одновременно присутствовать в двух различных занятий. Например, выше было показано, сколько должно быть идентификаторов в случае, если группа делится на две и три подгруппы, причем студент, занимающийся на занятии «Информатики» не должен одновременно заниматься на занятии «Иностранный язык». В этом случае допустим, группа содержит следующие идентификаторы: 1, 2, 3, 4, 5, 6. Первая подгруппа «Информатика» должна содержать идентификаторы: 1, 2, 3. Вторая подгруппа «Информатика» должна содержать идентификаторы: 4, 5, 6. Первая подгруппа «Иностранный язык» должна содержать идентификаторы: 1, 4. Вторая подгруппа «Иностранный язык» должна содержать идентификаторы: 2, 5. Третья подгруппа «Иностранный язык» должна содержать идентификаторы:3,6. Т.е. пересечение множеств идентификаторов потоков, в которых могут проходить занятия одновременно, равно пустому множеству. Пересечение множеств идентификаторов потоков, в которых не могут проходить занятия одновременно, не равно пустому множеству.