Разработка программного обеспечения для подсистемы автоматизированного составления расписания

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

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

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

В последние годы предпринимаются  множественные попытки совершенствования планирования учебного процесса путем построения алгоритмов оптимизации задач планирования учебной работы вуза с использованием вычислительной техники и программного обеспечения Microsoft Excel. Практическое внедрение планирования учебного процесса с использованием веб-технологий имеет место лишь в немногих вузах. Анализ состояния этих разработок позволяет сделать следующие выводы:

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

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

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

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

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

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

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

1.3 Сравнительный анализ  подходов к автоматизации составления  расписаний учебных занятий в образовательных учреждениях

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1.1 - Потоки данных при локальном  подходе

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

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

Таким образом, схема потоков данных примет вид, представленный на рисунке 1.2.

Рисунок 1.2. Потоки данных при системном  подходе

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

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

Примером системы с применением  системного подхода будет служить, разработанное в рамках данной дипломной работы, автоматизированное расписание занятий высшего учебного заведения с использованием CMS/CMF Drupal 7.

База данных содержит 3 справочника, хранящих необходимый  для составления расписания минимум информации. Главные задачи при разработке информационной системы: автоматизация ввода расписаний занятий с учетом специфики вуза, автоматизация поиска при составлении расписания и предоставление расписаний занятий пользователям с помощью удобного web-интерфейса.

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