Средства моделирования и численные методы в задаче формирования начального расписания занятий

Информатизация процессов управления деятельностью высшего учебного заведения отнесена к одному из основных направлений «Концепции информатизации высшего образования РФ». Информационные системы различной степени интеграции созданы для управления учебным процессом. В большинстве случаев они представляют собой совокупность разрозненных подсистем, каждая из которых решает свою отдельную задачу, используя локальную базу данных (БД).

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

Составление расписания занятий, являясь итерационным процессом, состоит вместе с тем из двух основных этапов. На первом этапе формируется начальное расписание на основе исходных данных об аудиторной нагрузке преподавателей. Основная проблема здесь связана со стратегией включения в расписание всей нагрузки. Расписание должно быть непротиворечивым и, по возможности, оптимальным. Непротиворечивость связана с соблюдением обязательных ограничений: у академической группы или преподавателя в одно и то же время может быть только одно занятие, отсутствие «окон» в занятиях студентов и др. Оптимальность расписания обеспечивается соблюдением желательных ограничений. Например, минимизация количества «окон» у преподавателей и/или равномерность распределения занятий студентов по дням недели и др. Всё это определяет сложность формирования начального расписания, а также его существенную значимость для следующего этапа. На втором этапе производится глобальная корректировка расписания с целью его оптимизации. Методы глобальной корректировки расписания рассмотрены в диссертации Костина С. А. «Модели и методы многокритериальной оптимизации начального расписания занятий» [58].

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

В составлении начального расписания занятий используются два подхода. В первом первоначально распределяются два ресурса — контингент учащихся и учебные аудитории, то есть формируется «сетка» занятий, заполняемая затем занятиями конкретных преподавателей. Во втором подходе начальное расписание формируется на основе одновременного распределения всех трех ресурсов (учащиеся, преподаватели, аудитории).

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

Второй подход (работы Давыдова С. В., Лагоша Б. А., Петропавловской A.B., Пантелеева Е.Р.) [61, 81] требует более сложных и трудоемких в вычислительном плане алгоритмов, но позволяет оптимизировать загруженность трех основных ресурсов, благодаря чему он был принят к использованию в данной работе.

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

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

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

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

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

К основным задачам работы, обеспечивающим достижение указанной цели, отнесены:

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

— реализация алгоритмов составления начального расписания занятий вуза;

— разработка средств генерации тестовых заданий;

— исследование характеристик разработанных методов и алгоритмов.

Объект исследования — теория расписаний.

Предмет исследования — задача подготовки расписания занятий вуза.

Методологическая и теоретическая основа исследования — в диссертационной работе использован математический аппарат теории множеств, исследования операций, теории графов и целочисленного линейного программирования, а также общей теории расписаний.

В работе использованы методы системного анализа, статистики, оптимизации, компьютерной графики.

Научная новизна исследования состоит в следующем:

— разработана модель расписания занятий на основе учебных поручений в составе общей модели управления учебным процессом вуза;

— предложен метод решения задачи формирования начального расписания занятий, отличающийся от известных решений:

— возможностью реализации в интегрированных системах управления учебным процессом вуза;

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

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

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

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

Основные результаты работы докладывались на 2-й Всероссийской научной конференции молодых ученых и аспирантов (г.Таганрог, 1999), XI, XII, XIII и XV международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2001,2002,2003 и 2005).

Публикации. По теме диссертации опубликовано 8 работ.

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

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

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

В четвертой главе проанализированы полученные варианты расписаний, результаты вычислительных экспериментов.

1. СОСТОЯНИЕ ВОПРОСА И ЗАДАЧИ ИССЛЕДОВАНИЙ.

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

1.1 Анализ работ в области решения задачи автоматизированного формирования расписания занятий.

В настоящем постиндустриальном обществе роль информационных технологий (ИТ) чрезвычайно важна, они занимают сегодня центральное место в процессе интеллектуализации общества, развития его системы образования и культуры. Система образования и наука являются одним из объектов процесса информатизации общества [57].

Концепция информатизации высшего образования РФ" была разработана РосНИИ информационных систем и утверждена Министерством образования Российской Федерации в 1993 году. В концепции было объявлено, что стратегическая цель информатизации образования состоит в глобальной рационализации интеллектуальной деятельности за счет использования информационных технологий, радикального повышения эффективности и качества подготовки специалистов до уровня, достигнутого в развитых странах, т. е. за счет подготовки кадров с новым типом мышления, соответствующим требованиям постиндустриального общества.

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

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

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

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

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

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

На составление расписания учебных занятий на семестр всей учебной части вуза может требоваться до одного месяца работы [85]. Расписание должно удовлетворять многочисленным требованиям организационного и методического характера, имеющим различные степени обязательности, часто взаимно противоречивым или даже взаимоисюпочаемым [25, 91]. Это затрудняет построение даже допустимых расписаний, не говоря уже об оптимальных. Во многих отечественных [25, 91] и зарубежных [98, 100, 128] работах указывается ряд требований и ограничений к расписанию занятий ВУЗ’а с разделением их на обязательные (hard constraint) и желательные (soft constraint). В таблицах табл. 1.1 и табл. 1.2 приводятся все выявленные требования и ограничения с разделением на соответствующие группы, а также их оценка.

Таблица 1.1.

Методические требования к расписанию занятий ВУЗ’а.

Требования и ограничения Оценка.

Обязательные.

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

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

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

Желательные (в порядке приоритета).

Требования и ограничения Оценка.

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

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

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

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

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

Требования и ограничения Оценка.

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

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

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

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

Равномерное распределение в течение недели сложных и трудоемких видов учебной работы Требование спорное по тем же причинам, что и предыдущее.

Таблица 1.2 Организационные требования к расписанию занятий ВУЗ’а.

Требования и ограничения Оценка.

Обязательные.

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

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

Требования и ограничения Оценка.

Отсутствие «окон» в расписании студенческих групп.

Желательные (в порядке приоритета).

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

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

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

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

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

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

Задача автоматизированного составления расписаний учебных занятий выделяется руководителями учебных заведений как наиболее актуальная в планировании работы вуза, так как расписания приходится существенно изменять от семестра к семестру, в отличие от учебных планов и учебных программ. Интерес администрации учебных заведений к этой задаче вызвал большое количество исследований и разработок, как автономных программных систем, так и подсистем АСУ учебными заведениями. Первые работы по рассматриваемой тематике выполнялись в начале 60-х годов, когда в вузах появились ЭВМ массовых моделей. Для систем составления расписаний занятий в целом характерна сильная зависимость от специфики конкретных учебных заведений уже на уровне математических моделей и представления данных, что затрудняет использование типовых систем. Многие исследователи считают, что эффективно могут применяться только системы, спроектированные и реализованные от начала до конца для конкретных учебных заведений [25, 101].

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

В 1982 г. вышла публикация, касающаяся разработки и эксплуатации комплекса задач АСУ Пензенского политехнического института, ныне Пензенский государственный технический университет (ПГТУ) [15]. В составе системы на тот момент эксплуатировалось или находилось на стадии опытной эксплуатации 7 подсистем. Среди них подсистемы учебного процесса (учет абитуриентов, учет студентов, учет выпускников, учет успеваемости, семестровое расписание) и подсистемы НИС (расчет заработной платы НИС, учет и планирование НИР). Большинство систем было запрограммировано на базе ОС/ЕС и в качестве основного языка программирования использован ПЛ/1. Подсистемы имели общую организационную структуру, единую информационную базу, что облегчало процесс расширения и модернизации разработанных систем, а так же обеспечивало преемственность в развитии информации. Например, массив абитуриентов модернизировался: абитуриент-студент-выпускник.

Информационная система Владимирского государственного университета [72] автоматизирует получение следующих документов: академические справки и приложения к диплому, личные карточки студентов по результатам экзаменационных сессий, отчеты об успеваемости по факультету. То есть, решаются задачи, связанные с деятельностью деканата в рамках одного факультета. Примерно такой же круг задач решается информационными системами Российского химико-технологического университета им. Д. И. Менделеева [87], где объединена вся информация об абитуриентах и студентах в рамках института. Более широкий охват разных сторон учебного процесса представлен информационной системой [87], разработанной в г. Новочеркасске, Ростовской области для работы в рамках локальной учебной структуры типа филиала института, учебно-инженерного центра и тому подобных структур связанных с заочной формой обучения. По мнению разработчиков этой системы, она может решать следующие задачи: расчет общей нагрузки по кафедрам, расчет учебной нагрузки для специальностей, расчет аудиторных занятий. В нашем университете функционирует несколько разрозненных информационных систем, связанных с: учетом студентов и преподавателей на уровне отдела кадров и бухгалтерии, оформлением абитуриентов перед вступительными экзаменами, подготовкой информации по результатам сессий, подготовкой учебных поручений, формированием расписания занятий для всего университета и т. д.

В Тамбовском государственном университете функционирует автоматизированная система, созданная с целью автоматизации планирования и сопровождения процессов принятия решений в ТГУ им. Державина [20]. Функциональная структура системы включает в себя следующие подсистемы: «Студент», «Деканат», «Учебный отдел», «Рейтинг». Каждая подсистема работает с отдельной базой данных. Подсистемы «Деканат» и «Учебный отдел» связаны сетью, а информация по сети поступает в виде отчетов из деканатов в учебный отдел и накапливается в БД учебного отдела, это свидетельствует о том, что возможность из подсистемы «Учебный отдел», обратится к базе данных подсистемы «Деканат» отсутствует.

Подобные информационные системы, несомненно имеющие ряд своих особенностей функциональной и организационной структуры, реализованные с помощью различных программных средств, имеющие свои специальные возможности были разработаны в 90-е годы в таких вузах, как Таганрогский государственный радиотехнический университет, Воронежским государственный педагогический университет (ВГГГУ), Новосибирский государственном технический университет (НГТУ), Комсомольскийна Амуре государственный технический университет, Пермский государственный техническом университет, Санкт-Петербургский государственный университет (система электронного документооборота ЬатЮосБ), прототип автоматизированной информационной подсистемы с элементами искусственного интеллекта для поддержки обучения и управления учебным процессом был разработан в МГТУ им. Баумана [67] и т. д.

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

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

В Санкт-Петербургском государственном университете ведется активная работа по информатизации университета. Разработаны система управления персоналом, включающая программные комплексы отдел кадров и штатное расписание. В настоящий момент разрабатываются следующие продукты: АбитуриентСтудентСтипендияБард-СтудентАспирантАИС БТИ;

На всероссийском форуме «Современная образовательная среда-2004» в Москве на ВВЦ НИИ ИТ СПбГУ представлял также новую свою разработку — программную систему «Бард-Студент». Информационная система «Бард-Студент» была разработана специально для Смольного института свободных искусств и наук. Система «Бард-Студент» поддерживает такие особенности обучения, как: индивидуальный учебный план, междисциплинарный подход в преподавании, кредитная система обучения, российская и американская система оценок, получение двух дипломов о высшем образовании.

Существует ряд известных систем для автоматизации процесса составления расписания занятий учебного заведения. Среди них: система формирования школьного расписания «Пенал» [11], разработчик ВП «ТетраПлюс», г. Минсксистема управления учебным процессом «Методист» [11, 20], в состав который входит модуль формирования расписания занятийсистема «Расписание 2000» [28, 33, 34, 35]- система «Мечта» [55, 56]- система «ХроноГраф», ООО «Хронобус» и др. [72, 87, 88]. Все они находятся в постоянном развитии, появляются новые возможности. Рассмотрим некоторые из них и другие системы более подробно.

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

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

ТОО «ИНТЕГПРОГ» при НИВЦ Московского государственного университета им. М. В. Ломоносова (МГУ), разработала «Информационную систему для автоматизации составления расписаний занятий в ВУЗ’е» [14], которая предназначена для автоматизации работ по составлению расписаний учебных занятий. В данной системе процесс составления расписаний занятий разделен на два уровня: уровень учебной части, на котором составляется сетка часов для всех кафедр в соответствии с учебным планом занятий по факультетам, курсам, потокам и имеющимися аудиториями, уровень кафедр, на котором происходит расстановка в уже построенную сетку часов учебных групп, предметов, преподавателей, типов и продолжительностей занятий в соответствии с почасовой нагрузкой, ограничениями и т. д. В соответствии с этим система состоит из двух частей: подсистема учебной части «У-Часть», подсистема кафедральных расписаний «Ка-Рас». Подсистема «У-Часть» обеспечивает следующие функциональные возможности: автоматизацию составления сетей часов занятий по всем кафедрам, печать сетки часов занятий и других расчетных документов, формирование данных для работы и полную совместимость с подсистемой «Ка-Рас». Подсистема «Ка-Рас» обеспечивает следующие функциональные возможности: автоматизацию составления расписаний занятий учебных групп по отдельной кафедре, расчет нагрузки преподавателей, автоматизацию составления замен преподавателей кафедры, печать расписаний занятий учебных групп, преподавателей и кафедры в целом.

Система «Методист» [11, 20] позволяет составлять и корректировать расписание как для школ, так и для вузов. Система также помогает в решении следующих задач: распределение и контроль учебной нагрузки, учет методических рекомендаций и личных пожеланий преподавателей (окна, методические дни и т. д.), учет объединения групп (классов) в потоки и/или разбиение их на подгруппы, закрепление специальных аудиторий (компьютерные классы, лингафонные кабинеты и т. д.), возможность введения приоритетов преподавателей и т. д. Система состоит из трех модулей: «Учебная часть».

— является центральной координирующей частью комплекса. Здесь вводятся исходные данные, также проводится просмотр и печать расписания- «Кафедральные заявки» — предназначен для заполнения заявок кафедр (преподавателей) на проведение занятий. Заявка составляется для каждой дисциплины, каждой учебной группы (класса). В заявке указываются конкретные преподаватели, что и в какой группе они проводят, желаемые аудитории, пожелания к составлению расписания- «Формирование расписания" — позволяет задавать время решения задачи, изменять степень влияния различных учитываемых факторов, изменять готовое расписание.

Разработкой системы формирования расписания для факультета занималось в 2001;2002 г СКБ «Токен», созданное при Уральском государственном горном университете [11]. Попытка создания системы автоматизированного составления расписания занятий была разработана в Днепропетровском национальном университете Украины в 2004 году. Авторы — В. В. Резник, Ю. С. Морозов, A.M. Кулабухов. В программе используются следующие базы данных: БД преподавателей, БД групп, учитывающую, БД аудиторий, БД заявок на расписание, которые составляются и подаются выпускающими и кафедрами. Каждая база данных (БД) имеет свою жесткую структуру, которая может при необходимости модернизироваться. Также, имеется возможность составлять новые базы данных [11,20].

Также следует отметить такие системы для автоматизации составления расписания как система «Хронограф» фирмы Хронобус, систему автоматиза-рованного составления расписания фирмы Exos (г. Москва), систему Аверс-распиание, разработанную информационно-внедренческим центром «Аверс» (г. Москва) [11].

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

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

Разработаны средства генерации тестовых заданий. Проанализированы характеристики разработанных методов и алгоритмов.