Вверх
Українська   English
ДонНТУ   Портал магистров

Реферат

Содержание

Введение

Одной из важнейших проблем качественной организации учебного процесса в высшем учебном заведении является задача формирования качественного учебного расписания. Эта задача является основной в деятельности диспетчерской службы ВУЗа. Качественно составленное расписания должно обеспечить равномерную загрузку студенческих групп и профессорско-преподавательского состава, оно влияет на комфортность обучения студентов, творческую отдачу преподавателей и эффективность использования ресурсов аудиторного фонда и лабораторий [1].

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

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

2. Актуальность

Составление эффективного расписания учебных занятий является важной задачей управления учебным процессом. A проблема автоматизации составления расписания занятий в высших учебных заведениях является одной из актуальных проблем организации учебного процесса [2]. На практике от того насколько эффективно составлено расписание зависит:

  1. качество обучения;
  2. экономическая эффективность обучения;
  3. комфортность учебы студентов и работы профессорско-преподавательского состава;
  4. а также позволяет без сбоев проводить учебный процесс и избежать необходимости корректировки расписания после начала учебного семестра [3].

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

  1. учесть все требования, предъявляемые к расписанию;
  2. определить критерии для оценки эффективности и оптимизации расписания;
  3. уменьшить временные затраты на составление расписания, что особенно важно при необходимости быстро получить расписания после изменения внешних условий;
  4. позволит учесть пожелания преподавателей, относительно времени проведения занятий и обеспечит возможность работы по совместительству.

Задачи теории расписаний имеют не только важное теоретическое значение, как относящееся к классу NP-полных задач, но и получили широкое практическое распространение. Для нахождения оптимального решения такого класса задач необходимо произвести полный перебор всех возможных вариантов, что не всегда возможно сделать в виду ограниченности ресурсов. Построение оптимального плана распределения занятий может занять слишком много времени и ресурсов, при использовании точных методов решения, в данном случае – полный перебор вариантов, что при увеличении размерности задачи приводит к логарифмическому росту затрачиваемых ресурсов для нахождения решения. Возникает необходимость в методах, характеризующихся сочетанием полиноминальной зависимости времени счета от размерности задачи и точностью близкой к оптимальной [4].

К такому классу методов относятся эволюционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных приближенных алгоритмов [1].

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

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

Таким образом, исследование возможности решения задач теории расписаний с помощью приближенных методов класса ГА и автоматизация составления расписания занятий в ВУЗах является актуальной задачей.

2. Цели и задачи работы

Основной целью работы является составление алгоритма способного генерировать эффективное расписание занятий в условиях ДонНТУ.

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

  1. определение интеллектуальных методов, для составления корректного расписания;
  2. модификация алгоритма для повышения его эффективности;
  3. проверка эффективности полученного алгоритма;
  4. изучение влияния различных параметров алгоритма на скорость и результат решения задачи;
  5. определение эффективных значений параметров для решения задачи;
  6. проектирования базы данных для унификации алгоритма.

3. Научная новизна и практическая ценность

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

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

4. Обзор существующих подсистем

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

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

  1. программа «1С: Автоматизированное составление расписаний. Университет»;
  2. программа «Ректор-ВУЗ»;
  3. программа «Галактика».

Сравнение функциональных возможностей выбранных подсистем приведены в таблице 1.1 [6,7,8,9].

Таблица 1.1 – Сравнение функциональных возможностей подсистем

Функция 1С Ректор-ВУЗ Галактика
режимы составления расписания ручной, автоматический, смешанный ручной, автоматический, смешанный ручной, автоматический, смешанный
возможность составления нескольких вариантов расписания в автомат. режиме и выбор лучшего да нет нет
учет пожеланий и возможностей преподавателей, групп студентов, помещений да нет да
консолидация расписаний да нет нет
выбор критериев оптимизации да неизвестно да
проверка на допустимость да, при всех режимах неизвестно да, при всех режимах
учет максимального допустимого количества занятий в день для группы студентов или преподавателя при составлении расписания да только кол-во пар в день да
построение расписания для 2х и более смен да да да
оперативное резервирование помещений да нет да
просмотр расписаний и ввод предпочтений по web интерфейсу да нет да
загрузка справочников в форматах excel, xml нет excel, xml
оперативное изменение расписаний да (путем перетаскивания) занятий на шахматке неизвестно неизвестно
составление расписания сессии да нет неизвестно
приоритетность использования ресурсов неизвестно нет да
учет параллельных занятий, разбиения на подгруппы и потоковых лекций при составлении расписания да нет неизвестно
соблюдение интервала между определенными занятиями неизвестно нет да
разграничение прав доступа да нет нет

Системные требования подсистем:

  1. «1с» СУБД - MS SQL, IBM DB2, Oracle Database, ОС Windows, Linux, Mac OS, iOS [7];
  2. «Ректор вуз» ОС Windows XP, Windows Vista или Windows 7, СУБД не требуется [8];
  3. «Галактика» ОС Windows (XP, 7), NET Framework v.4 и выше СУБД MS Server 2008, Server 2003 [9].

Программа «Ректор вуз» является самой простой, она плохо масштабируется, не использует СУБД, что весьма плохо сказывается на ведении справочной информации, совершенно не приспособлена для взаимодействия с другими подсистемами, имеет малое количество настроек для составления расписания в автоматическом режиме и малое количество ограничений. Из выше сказанного можно сделать вывод, что данная программа не способна автоматически сформировать расписание с учетом всех ограничений и предпочтений, при этом исходный код является закрытым и самостоятельное внесение изменений, или дополнений в него невозможно. Программа является платной и распространяется по лицензии. Лицензия на 1 компьютер – 8.001.00 руб [8].

Программа «1С: Автоматизированное составление расписаний. Университет» является хорошо масштабируемым программным продуктом с возможностью отображения в системе большого количества ограничений, требований и предпочтений к составляемому расписанию. При этом система имеет встроенную систему интеграции с 1С: Университет и 1С: Университет ПРОФ. Продукт реализует функционал составления расписания в автоматизированном режиме, в дополнение к ручному режиму, имеющемуся в 1С: Университет ПРОФ. При этом 1С: Автоматизированное составление расписаний. Университет может работать и как самостоятельный продукт, что обеспечивает взаимодействие всех подразделений ВУЗа и объединяет их в одну систему управления вузом. При этом все компоненты системы могут работать на компьютерах как под управлением Windows, так и под управлением Linux 1С: Предприятия 8.2, а с появлением Веб-клиента для пользователей появилась возможность работать с системой через браузеры Microsoft Internet Explorer или Mozilla Firefox. К недостаткам данной системы можно отнести ее стоимость 1С: Предприятие 8.2 лицензия на сервер - 13 200.00 гривен, 1С: Автоматизированное составление расписания. Университет. - 70.000.00 руб., лицензии на рабочие места 1-место - 1 800.00 грн [10].

5. Методы решения задач составления расписания [11]

  1. Методы целочисленного программирования

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

    Применение алгоритма:

    1. выделение переменных;
    2. составление математической модели (выделение ограничений для переменных);
    3. составление целевой функции;
    4. нахождение максимума (минимума) целевой функции с помощью математических методов.

    Основные недостатки:

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

  2. Метод теории графов

    В этом случае строится неориентированный граф, в котором каждая вершина представляет собой запланированное учебным планом занятие. Если между какими-то двумя вершинами возможны конфликты, то они соединяются ребром. Это эквивалентно запрету одновременного проведения занятий. Тогда задача сводится к раскраске графа в заданное количество цветов.

    Применение алгоритма:

    1. выделение множества занятий в учебном плане;
    2. представление каждого занятия в виде вершины графа;
    3. соединение вершин графа ребрами в случае невозможности одновременного проведения занятий;
    4. решение задачи раскраски графа в заданное количество цветов.

    Основные недостатки:

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

    Преимущества:

    1. простая в понимании математическая модель;
    2. применение графа вместе с эвристическими методами может давать хорошие результаты.

  3. Агентный подход

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

    Применение алгоритма:

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

    Основные недостатки:

    1. отсутствует гарантия получения приемлемого решения задачи построения расписания занятий (на тестах соревнования ITC 2007 мульти-агентная система не нашла ни одного допустимого расписания);
    2. практически невозможным становится оценка влияния значений параметров для внутренней логики каждого из агентов на результат решения задачи.

    Преимущества:

    1. возможность гибкой настройки индивидуальных предпочтений за счет возможности реализации собственной логики для каждого из агентов;
    2. возможность динамического изменения предпочтений.

  4. Метод муравьиной колонии

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

    Применение алгоритма:

    1. представить задачу в виде взвешенного графа;
    2. определить значение следа феромона;
    3. определить эвристику поведения муравья при построении решения;
    4. реализовать локальный поиск.

    Основные недостатки:

    1. сходимость алгоритма гарантируется, но время сходимости не определено;
    2. высокая итеративность алгоритма;
    3. результат работы метода сильно зависит от начальных параметров поиска, которые подбираются экспериментально;
    4. теоретический анализ значения начальных параметров затруднен, исследования являются больше экспериментальными.

    Преимущества:

    1. может использоваться в динамических приложениях;
    2. использует память всей колонии, что достигается за счет моделирования выделения феромонов;
    3. сходимость к оптимальному решению гарантируется.

  5. Метод имитации отжига

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

    Применение алгоритма:

    1. составить корректное расписание и задать высокое значение температуры T = T0;
    2. изменить расписание Z = Z';
    3. вычислить целевую функцию для измененного расписания Δ = f(Z') – f(Z);
    4. заменить предыдущее расписание полученным, если оно является лучше предыдущего (Δ ≤ 0), если нет, то вероятность замены p = e–Δf/T;
    5. понизить температуру;
    6. пока не выполнен критерий остановки переход к пункту 2.

    Основные недостатки:

    1. малоэффективен для составления расписаний в современных системах массового образования в виду большой размерности задачи;
    2. для получение эффективного решения необходимо применять схему Больцмана, или Коши, что приводит к значительным затратам вычислительных мощностей.

  6. Генетический алгоритм

    Генетические алгоритмы основаны на использовании механизмов теории естественной эволюции.

    Применение алгоритма:

    1. сгенерировать случайным образом популяцию размера P;
    2. вычислить целевую функцию;
    3. выполнить операцию репродукции;
    4. выполнить операцию скрещивания (рисунок 1);
    5. выполнить операцию мутации;
    6. выполнить оператор редукции;
    7. проверит критерий останова и, если он не достигнут, перейти к шагу 2, иначе завершить работу.
    Операция скрещивания

    Рисунок 1 – Операция скрещивания

    (анимация: объем - 81 876 байт; размер - 554х216 пикселей; состоит из 5 кадров; задержка между кадрами - 120 мс)

    Основные недостатки:

    1. качество решения значительным образом зависит от размера и разнообразия начальной популяции;
    2. решения, полученные в результате нескольких экспериментов для одной и той же задачи, могут незначительно различаться [3];
    3. слабый учет специфики задачи составления расписания учебных занятий при организации ее решения [3].

    Преимущества:

    1. алгоритм работает с кодами, в которых представлен набор параметров, напрямую зависящих от аргументов целевой функции;
    2. в процессе поиска алгоритм использует несколько точек поискового пространства, а не переходит от точки к точке;
    3. в процессе работы алгоритм может не использовать никакой дополнительной информации о задаче, но, если такая имеется можно ускорить сходимость алгоритма [3];
    4. генетический алгоритм использует как вероятностные правила для порождения новых точек поиска, так и детерминированные для перехода от одних точек к другим [3];
    5. для задач высокой размерности скорость работы алгоритма можно «регулировать» размерами популяции [3].

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

6. Математическая постановка задачи

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

S (P,G,A,T,D,V),
где G Множество обучающихся групп;
A – Множество аудиторий;
D – Множество дисциплин;
P – Множество преподавателей;
T – Множество учебных пар (временных интервалов проведения занятий);
V – Рабочие учебные планы трехмерная матрица, определяющая для каждого занятия какие преподаватели его проводят, и какие группы на нем присутствуют.

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

S=G×P×A×T→{0,1},
где G множество обучающихся групп;
A – множество аудиторий;
P – множество преподавателей;
T – множество учебных пар (временных интервалов проведения занятий).

Данное выражение расшифровывается следующим образом: если в определенное время Т преподаватель Р у группы G проводит занятие в аудитории А, то значение выражения равно 1, иначе 0.

Целевая функция Р является суммой штрафов за нарушения предпочтений при составлении расписания.

Целевая функция P, (1)


где NW – количество требований;
W – список штрафных коэффициентов длиной NW, соответствующий требованиям;
N – количество занятий в расписании (количество генов в хромосоме);
Z – список занятий длиной N;
zir– список из булевых длиной NW значений, где каждому значению соответствует требование и штрафной коэффициент из списка W.

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

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

7. Предполагаемые результаты

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

8. Выводы

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

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

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

Определены критерии эффективности расписания в условиях ДонНТУ.

Проведенные экспериментальные исследования подтверждают эффективность составленных расписаний, а также определены параметры, позволяющие повысить эффективность алгоритма.

На основании результатов экспериментальных исследований сформулированы и даны рекомендации по составлению эффективных расписаний в условиях ДонНТУ.

Список литературы

  1. Будиловский Дмитрий Михайлович Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий // Системный анализ, управление и обработка информации (по отраслям) // Ростов-на-Дону 2007;
  2. Лопатеева Ольга Николаевна Система автоматизированного формирования учебного расписания в высшем учебном заведении на основе эвристических алгоритмов // Системный анализ, управление и обработка информации (по отраслям) // Диссертационная работа Красноярск 2006;
  3. Низамова Гузель Фанисовна Математическое и программное обеспечение составления расписания учебных занятий на основе агрегатных генетических алгоритмов // автореферат // Уфа 2006;
  4. Секирин А. И. Программный комплекс для моделирования, анализа и оптимизации работы автоматизированных технологических комплексов механообработки // Научные труды Донецкого национального технического университета. Серия: "Вычислительная техника и автоматизация". Выпуск 90 - Донецк: ДонНТУ, 2005;
  5. Конькова И.С. Генетические алгоритмы в решении задачи со-ставления расписания занытий в вузе. // Проблемы информатики в образовании, управлении, экономике и технике: Сб. статей XII Междунар. Научно-техн. Конф. – Пенза: ПДЗ, 2012. – С. 26 29;
  6. О выпуске программного продукта 1С: Автоматизированное составление расписаний. Университет [Электронный ресурс]. – Режим доступа: http://www.1c.ru/news/info.jsp?id=18039 – Загл. с экрана;
  7. 1С: Автоматизированное составление расписания. Университет, [Электронный ресурс]. – Режим доступа: http://solutions.1c.ru/asp_univer– Загл. с экрана;
  8. Программа Ректор-ВУЗ [Электронный ресурс]. – Режим доступа: http://rector.spb.ru/raspisanie-vuz-4u.php – Загл. с экрана;
  9. Программа: Галактика [Электронный ресурс]. – Режим доступа: http://www.galaktika.ru/ruz – Загл. с экрана;
  10. Прайс-Лист 1С [Электронный ресурс]. – Режим доступа:http://www.bgs-solutions.com.ua/prices/price.php – Загл. с экрана;
  11. М.А. Безуглый, А.И. Секирин, доц. каф. АСУ. Методы повышения эффективности составления расписания в условиях учебного заведения. // Международная научно-техническая конференция студентов, аспирантов и молодых ученых Компьютерная и программная инженерия – 2015 // Донецкий национальный технический университет 2015.