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

Авторы: Бартенев А.С.

Источник: Современные научные исследования и инновации. – Сентябрь, 2011

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

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

Задача планирования расписания учебных занятий — это задача на составление расписания комбинаторного типа, характерной особенностью которой является огромная размерность и наличие большого числа ограничений сложной формы. Фактически, в настоящее время, не существует универсальных методов решения таких задач. Математическая (классическая) теория расписаний охватывает лишь узкий круг хорошо формализуемых проблем, которые обычно сводятся к задачам коммивояжера, транспортной и т.п. Прямое применение данных методов к задаче составления расписания учебных занятий не представляется возможным. Тем не менее есть ряд эвристических и переборных методов, которые вполне поддаются программированию [1].

Есть мнение, что опытный диспетчер сможет составить расписание так, что оно будет отвечать интересам учебного процесса и общественной жизни образовательного учреждения. Однако с этим нельзя согласиться. Ручное решение задачи составления расписания занятий требует больших затрат времени, квалифицированных специалистов, в то же время результат такого решения часто получается далеко не оптимальным. После ввода исходной информации требуется её согласование, в то время как невозможность получения требуемого расписания может быть определена ещё на этапе анализа. Во время составления расписания возможно возникновение тупиковых ситуаций. Всё это требует изменения исходных данных и ослабления ограничений, и здесь без человека не обойтись. Без внесения данных изменений расписание не будет иметь практической ценности. Также следует учесть тот момент, что расписание может меняться и во время его использования, т.е. после составления, и здесь весьма важен человеческий фактор. В этом плане важна поддержка данного процесса автоматизированными методами и процедурами. Основное преимущество состоит в том, что автоматизированное составление устраняет массу рутинной работы, такой как: поиск возможных вариантов внесения очередных элементов в расписание, проверку выполнения требований, поиск случайных ошибок в готовом расписании, оформление расписания на бумаге в виде различных таблиц (для преподавателей, групп, покабинетного), оставляя человеку больше времени на более интеллектуальные действия. Компьютер в данном случае также является инструментом, существенно усиливающим способности человека, т.к. человек не в состоянии перебрать и проанализировать такое же количество вариантов расписаний, как компьютер [2].

Изучение опыта создания подобных систем показывает, что в последние годы предпринимались множественные попытки совершенствования планирования учебного процесса путем построения алгоритмов оптимизации задач планирования учебной работы вуза и последующей их реализацией на вычислительной технике. Такие исследования в разное время проводились и продолжаются в некоторых вузах [4,5]. Однако практическое внедрение планирования учебного процесса с использованием компьютерной техники имеет место лишь в немногих вузах. Анализ состояния этих разработок позволяет сделать следующие выводы:

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

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

• Имеющиеся программы не предполагают многопользовательский режим работы и не поддерживают весь необходимый электронный документооборот.

• Почти не выполняется разработка типовых унифицированных элементов для создания единой автоматизированной системы управления высшей школой.

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

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

При разработке алгоритмов автоматизированного составления расписания занятий остро стоит проблема создания универсальных алгоритмов, учитывающих специфику условий каждой конкретной задачи. Такие алгоритмы должны быть достаточно "гибкими", т.е. без существенного их изменения можно было бы включать и исключать требования из системы требований к расписанию. Однако попытка решать задачу каким-либо одним единственным универсальным алгоритмом на данный момент не представляется возможной. Алгоритмы, позволяющие решать широкий класс задач, не дают той эффективности, которую обеспечивают более конкретные, адаптированные с учётом конкретных условий алгоритмы.

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

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