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

Авторы: Горбань А.С., Цололо С.А.

Источник: Конференция информационные управляющие системы и компьютерный мониторинг (ИУС КМ 2013)

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

• Множество преподавателей.

• Множество групп.

• Множество аудиторий.

• Множество предметов.

• Учебный план.

Также могут быть выдвинуты два ряда требований к расписанию:

• Жесткие или обязательные требования:

o Для определённых пар нужны вместительные аудитории (например, потоковые лекции).

o Для определённых пар нужны аудитории со специальным оборудованием (например, аудитории с аналого-вычислительными комплексами для практических занятий по предметам, связанными с электроникой).

• Мягкие требования:

o Отсутствие окон у студентов

o Отсутствие окон у преподавателей

o Минимальное количество переездов между группами корпусов, если университетский городок находится не в одном месте (например, Донецкий Национальный Технический Университет имеет 3 группы корпусов достаточно удалённых друг от друга).

o Лекции должны быть утром, практические занятия – на последних парах

o Равномерная нагрузка студентов

o «Библиотечные» дни для преподавателей

o Прочие условия

Как видно из постановки, оценить качество расписания возможно, только после его полного составления.

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

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

• Приближенные методы.

Их можно разбить на следующие группы:

o методы локальной оптимизации

o модификации точных методов

o эвристические методы, максимально учитывающие специфику решаемых задач

o методы случайного поиска

o методы, сочетающие локальную оптимизацию со случайным поиском.

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

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

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

Метод перебора или метод равномерного поиска – простейший из методов поиска значений. Любую задачу построения алгоритма можно решить с помощью этого метода, однако сложность перебора зависит от количества условий задачи.

Метод перебора интуитивно прост и понятен. Его единственное преимущество по сравнению с другими методами – он гарантировано дает идеальное решение, если оно конечно существует, даже с учетом всех ограничений и требований.

Суть этого метода – попробовать абсолютно все комбинации и перестановки в сетке расписаний.

Отсюда вытекают следующие характеристики этого метода: он прост, он гарантирует результат, при его существовании, он идеально эффективно справляется с малыми задачами, например составление расписания для начальной школы, где 3 параллели по 4 класса в каждой.

Единственный минус, который перечеркивает все преимущества, этого метода вытекает из его плюсов: этот метод абсолютно неэффективен при увеличении количества условий. Если для расписания начальной школы этот метод эффективен, то для расписания уже всей школы – результата придётся ждать уже гораздо большее количество времени. Для Донецкого национального технического университета с сотнями групп, преподавателей, аудиторий и предметов, перебор может длиться столетия. Ведь количество вариантов для одной только группы 2*25! (2 недели по 5 занятий 5 раз в день). Поэтому этот метод считается очень неудачным для заданной задачи.

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

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

В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества (рис. 1).

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

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

Минусы метода – он уже не настолько прост, как метод полного перебора, он тяжело применяется к теории расписания занятий, он всё еще слишком долгий по выполнению.

Генетический алгоритм является разновидностью эволюционных вычислений, с помощью которых решаются оптимизационные задачи с использованием методов естественной эволюции, таких как наследование, мутации, отбор и кроссинговер. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

Эвристический алгоритм – это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат. Проще говоря, эвристика – это не полностью математически обоснованный (или даже «не корректный»), но при этом практически полезный алгоритм. Она не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).

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

Задача составления расписания сводится к задаче удовлетворения ограничений. Процесс составления расписания представляется как процесс распределения времени и места между занятиями таким образом, чтобы выполнялось множество ограничений. На каждом шаге расставляется одна группа или курс. Если на каком-то шаге невозможно назначить время или аудиторию таким образом, чтобы не нарушились ограничения, то ослабляется одно из «мягких» ограничений. И так повторяется до тех пор, пока не станет возможным назначить время или аудиторию без нарушений оставшихся ограничений. Недостатком этого метода является то, что не всегда можно расставить группу или курс и поэтому это приходится делать вручную.

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

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

Перспективные задачи. В перспективе планируется программная реализация и тестирование выбранного метода для автоматизации процесса составления расписания и внедрения в АСУ «Деканат».