Содержание к диссертации
Введение
1. Состояние вопроса и задачи исследований 8
1.1. Анализ работ в области решения задачи автоматизированного формирования расписания занятий 8
1.2. Основные подходы к формализации решения задачи составления расписания 21
1.3.Многокритериальность задачи составления расписания 26
Основные понятия и определения 26
Многокритериальность в задаче формирования начального расписания занятий 27
1.4.Постановка задач исследования 30
2. Разработка метода составления начального расписания занятий вуза 31
2.1.Общая постановка задачи составления начального расписания занятий в составе интегрированной системы управления учебным процессом вуз.31
2.2. Разработка математической модели начального расписания занятий 40
2.3. Метод составления начального расписания занятий вуза на основе многокритериальной выборки с использованием переопределяемых критериев загруженности 49
3. Моделирование информации в задаче расписания 54
3.1.Разработка критериев исходной информации 54
3.2. Формирование тестовых заданий 56
3.3.Разработка критериев анализа начального расписания занятий 63
4. Применение метода составления начального расписания занятий вуза 73
4.1.Расчеты без использования мультипликативного критерия выборки 73
4.2. Расчеты с использованием мультипликативного критерия выборки для четырех «пар» 81
4.3. Расчеты с использованием мультипликативного критерия выборки для трех «пар» 89
Заключение 95
Литература 96
Приложения
- Основные подходы к формализации решения задачи составления расписания
- Разработка математической модели начального расписания занятий
- Формирование тестовых заданий
- Расчеты с использованием мультипликативного критерия выборки для четырех «пар»
Введение к работе
Информатизация процессов управления деятельностью высшего учебного заведения отнесена к одному из основных направлений «Концепции информатизации высшего образования РФ». Информационные системы различной степени интеграции созданы для управления учебным процессом. В большинстве случаев они представляют собой совокупность разрозненных подсистем, каждая из которых решает свою отдельную задачу, используя локальную базу данных (БД).
Составление расписания занятий является одной из самых сложных задач информатизации учебного процесса, характеризуемой значительной трудоемкостью, а ее успешная реализация возможна только при учете всех подразделений учебного заведения. Автоматизация подготовки расписания занятий наиболее эффективна в рамках интегрированной системы управления учебным процессом. Вместе с тем большинство известных систем автоматизированного составления расписания занятий являются автономными, не интегрированными системами, требующими ввода больших объемов входной информации, как правило, сходного характера.
Составление расписания занятий, являясь итерационным процессом, состоит вместе с тем из двух основных этапов. На первом этапе формируется начальное расписание на основе исходных данных об аудиторной нагрузке преподавателей. Основная проблема здесь связана со стратегией включения в расписание всей нагрузки. Расписание должно быть непротиворечивым и, по возможности, оптимальным. Непротиворечивость связана с соблюдением обязательных ограничений: у академической группы или преподавателя в одно и то же время может быть только одно занятие, отсутствие «окон» в занятиях студентов и др. Оптимальность расписания обеспечивается соблюдением желательных ограничений. Например, минимизация количества «окон» у преподавателей и/или равномерность распределения занятий студентов по дням недели и др. Всё это определяет сложность формирования начального
4 расписания, а также его существенную значимость для следующего этапа. На втором этапе производится глобальная корректировка расписания с целью его оптимизации. Методы глобальной корректировки расписания рассмотрены в диссертации Костина С.А. «Модели и методы многокритериальной оптимизации начального расписания занятий» [58].
Основное отличие между этапами заключается в характере входных данных и способах их обработки. Входные данные первого этапа как объекта формализации являются неупорядоченным множеством элементов, отдельные атрибуты которых представляют три распределяемых ресурса - учащихся, преподавателей и учебные аудитории. Входные данные второго этапа являются упорядоченным во времени множеством тех же элементов. Задача первого этапа заключается в упорядочении неупорядоченного множества, тогда как задача второго этапа связана с обработкой уже упорядоченного множества. Следует также отметить идентичность обязательных ограничений для задач обоих этапов и различие в наборах желательных ограничений. Решение задач второго этапа существенно зависит от эффективности решения задач первого этапа.
В составлении начального расписания занятий используются два подхода. В первом первоначально распределяются два ресурса - контингент учащихся и учебные аудитории, то есть формируется «сетка» занятий, заполняемая затем занятиями конкретных преподавателей. Во втором подходе начальное расписание формируется на основе одновременного распределения всех трех ресурсов (учащиеся, преподаватели, аудитории).
Уменьшение числа распределяемых ресурсов в первом подходе (работы Ерунова В.П., Морковина И.Н.) [25] упрощает алгоритмы решения, кроме того, возможны минимизация количества требуемых учебных аудиторий и обеспечение равномерности загрузки академических групп. Оптимизация работы преподавателей при этом затруднена.
Второй подход (работы Давыдова СВ., Лагоша Б.А., Петропавловской А.В., Пантелеева Е.Р.) [61, 81] требует более сложных и трудоемких в вычис-
5 лительном плане алгоритмов, но позволяет оптимизировать загруженность трех основных ресурсов, благодаря чему он был принят к использованию в данной работе.
Практически не исследованными при составлении начального расписания занятий являются: реализация подсистем подготовки расписания занятий в составе интегрированных систем управления учебным процессом вуза, приводящих к значительному уменьшению требуемой исходной информации; подходы с использованием рассчитываемых на каждой итерации приоритетов не включенных в расписание элементов входного множества, благодаря чему возможно автоматическое управление выбором элементов с наиболее загруженными ресурсами и их включением в формируемое расписание; вопросы создания средств генерации тестовых заданий для задач составления расписания занятий. Использование этих средств обеспечит отладку и анализ процессов составления начального расписания занятий.
Изложенное определяет актуальность диссертационной работы, целью которой является разработка, исследование и реализация математических моделей и методов составления начального расписания занятий для интегрированной системы управления учебным процессом вуза.
К основным задачам работы, обеспечивающим достижение указанной цели, отнесены: разработка метода составления начального расписания занятий для интегрированных систем управления учебным процессом вуза; реализация алгоритмов составления начального расписания занятий вуза; разработка средств генерации тестовых заданий; исследование характеристик разработанных методов и алгоритмов.
Объект исследования - теория расписаний.
Предмет исследования - задача подготовки расписания занятий вуза.
Методологическая и теоретическая основа исследования - в диссертационной работе использован математический аппарат теории множеств, исследования операций, теории графов и целочисленного линейного программирования, а также общей теории расписаний.
В работе использованы методы системного анализа, статистики, оптимизации, компьютерной графики.
Научная новизна исследования состоит в следующем: разработана модель расписания занятий на основе учебных поручений в составе общей модели управления учебным процессом вуза; предложен метод решения задачи формирования начального расписания занятий, отличающийся от известных решений: - возможностью реализации в интегрированных системах управления учеб ным процессом вуза; сочетанием многокритериальной выборки ресурсов с многокритериальной оценкой их включения в расписание занятий. Многокритериальная оценка в отличие от всех существующих производится по сформированной части расписания, а не для всего расписания, и носит прогностический характер, а ее применение прямо влияет на эффективность решений второго этапа -оптимизации начального расписания; впервые реализован алгоритм составления начального расписания занятий вуза с использованием многокритериальной выборки на основе переопределяемых на каждой итерации критериев загруженности основных распределяемых ресурсов и многокритериальной оценки принимаемых решений по расстановке. В отличие от весовых коэффициентов вообще критерии загруженности являются объективными характеристиками, не зависящими от суждений разработчика.
Практическая значимость работы - предложенные в диссертации модели, методы и алгоритмы используются при разработке и практической реализации информационных систем управления учебным процессом вуза.
7 Апробация результатов исследования - предложенные в диссертации модели, методы и алгоритмы были использованы при разработке и практической реализации информационных систем управления учебным процессом вуза. Система прошла внедрение в Саратовском государственном техническом университете и Саратовской государственной академии права и продолжает совершенствоваться.
Основные результаты работы докладывались на 2-й Всероссийской научной конференции молодых ученых и аспирантов (г.Таганрог, 1999), XI, XII, XIII и XV международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2001,2002,2003 и 2005).
Публикации. По теме диссертации опубликовано 8 работ.
В первой главе проведен анализ существующих информационных систем для автоматизации управления учебным процессом, а также систем для автоматизации процесса составления расписания занятий. Рассматриваются основные подходы к решению задачи составления расписания учебных занятий.
Во второй главе рассматривается общая постановка задачи составления расписания занятий в составе интегрированной системы управления учебным процессом вуза, разработана и исследована математическая модель начального расписания занятий, рассмотрен предложенный метод составления начального расписания занятий вуза на основе многокритериальной выборки с использованием переопределяемых критериев загруженности.
Третья глава посвящена разработке критериев исходной информации, тестового задания и критериев анализа готового расписания. Моделирование задачи составления расписания включает разработку средств (критериев) оценки исходной и выходной информации, а также тестовых заданий, моделирующих реальные условия учебного процесса вуза.
В четвертой главе проанализированы полученные варианты расписаний, результаты вычислительных экспериментов.
Основные подходы к формализации решения задачи составления расписания
Наиболее общая формулировка задачи составления расписаний состоит в следующем: с помощью некоторого множества ресурсов или обслуживающих устройств должна быть выполнена некоторая фиксированная система заданий. Цель заключается в том, чтобы при заданных свойствах заданий и ресурсов и наложенных на них ограничениях найти эффективный алгоритм упорядочивания заданий, оптимизирующий или стремящийся оптимизировать требуемую меру эффективности. В качестве основных мер эффективности изучаются длина расписания и среднее время пребывания заданий в системе. Модели этих задач являются детерминированными в том плане, что вся информация, на основе которой принимаются решения об упорядочивании, известны заранее [21, 90, 89].
Задача составления расписания является NP- полной. Иногда такие задачи называют полиномиально полными или просто полными. Это широкий класс задач, которые либо все разрешимы за полиномиальное время, либо все неразрешимы за полиномиальное время. Для решения подобных задач специалисты десятилетиями ищут решения, требующие менее чем экспоненциального времени, поэтому имеются серьезные основания считать, что ни одна из NP-полных задач неразрешима за полиномиальное время. Поэтому в случае NP-полной задачи чаще всего используют эвристические методы, позволяющие получить приближение к оптимальному решению [21, 89, 90].
Большинство точных методов использует графовую модель расписаний. В ней учебный план и другие исходные данные представляются в виде графа, мультиграфа, гиперграфа или набора графов. Вершины графов, как правило, представляют преподавателей, учебные группы, дисциплины и аудитории, а ребра - учебные занятия. Необходимо сопоставить ребрам графа периоды времени («пары»), причем требование отсутствия накладок означает, что это сопоставление должно быть реберной раскраской графа: никаким двум ребрам, инцидентным одной вершине, не должно соответствовать одно и тот же учебное занятие.
Первая модель такого рода предложена в [116]. В ней гиперграф учебного плана и желательности проведения занятий в определенное время представлялся в виде трехмерной таблицы, а составление расписания сводилось к трехмерной задаче о назначениях (требования к дисциплинам и распределение аудиторий не рассматривалось).
Многие последующие работы использовали такое представление и его обобщения как основу для точных и эвристических методов. В [7, 108, 120] учитывалось разделение групп на подгруппы и объединение в потоки, в [104, 121] к этому же фактору добавились требования к аудиториям.
Чаще всего рассматривалось представление, в котором расписания для преподавателей и учебных групп строились как реберные раскраски двудольного мультиграфа учебного плана [102,103]. Расписание на одно занятие оказывается паросочетанием мультиграфа. Реберную раскраску двудольного мультиграфа с Е ребрами без дополнительных условий можно построить за 0(ElogE) операций [106], но учет других требований превращает задачу в NP-полную [21]. В [114] доказана NP-полнота задачи с запретами на некоторые «пары» для преподавателей.
Методы сетевого [18, 79, 104] и календарного планирования [95, 115] привлекаются, если необходимо проводить занятия в заданном порядке, минимизировать переходы учащихся и преподавателей в аудитории и здания. Такие методы близки к методам планирования технологических процессов и часто сводятся к NP-трудной квадратичной задаче о назначениях.
При учете наиболее трудных требований привлекаются известные общие задачи математического программирования [16, 27, 96, ПО]. В [27] задача целочисленного линейного программирования формулируется для учета разделения групп на подгруппы и объединения в потоки и решается методом вектора спада. В [127] расписание строится по индивидуальным учебным планам студентов посредством решения задачи целочисленного линейного программирования методом лагранжевой релаксации. В ряде работ задача составления расписания, выраженная в терминах целочисленного линейного программирования, решается методом ветвей и границ или методом отсечений.
Теоретические и эмпирические оценки трудоемкости показали, что с помощью точных методов построить расписание на реальных данных учебного заведения часто практически невозможно. Такие методы могут справиться лишь с задачами крайне малой размерности или без учета многих необходимых требований [114]. В силу этого большинство автоматизированных систем составления расписания занятий основаны на эвристических методах.
Эвристические методы генерации расписаний Первые эвристические подходы моделировали работу человека, составляющего расписание занятий вручную. По схеме работы такие алгоритмы можно подразделить на следующие типы: - так называемые, жадные, выбирающие очередные занятия по некоторому правилу без дальнейшего их переназначения. Эти алгоритмы не могут самостоятельно выйти из тупиковой ситуации, в которой назначение очередного занятия невозможно; - алгоритмы неполного перебора с возвратом, изменяющие ранее назначенные занятия, если на каком-то шаге назначение очередного занятия невозможно; - алгоритмы, ищущие возможность назначения очередного занятия и варианты переназначения ранее спланированных занятий, конфликтующих с очередным. Если переназначение одного занятия найти не удается, некоторые методы ищут цепочки переназначений ранее спланированных занятий; - декомпозиционные эвристики, разделяющие исходную задачу на подзадачи меньшего размера и применяющие к ним другие методы или дальнейшие шаги декомпозиции.
Среди многочисленных эвристических численных методов применяющихся для автоматизированного формирования расписания занятий [101, 108, 117], наиболее распространенными являются метод моделирования отжига (simulated annealing) [109, 113, 119] и так называемые эволюционные алгоритмы (evolutionary algorithms).[74, 107]. Общим, в таких подходах, является введение критериев оптимальности и целевой функции оптимизации взамен требований к расписанию.
Эволюционные алгоритмы (evolutionary algorithms) являются поисковыми методами, основная идея которых заимствована из биологического процесса естественного отбора и процесса выживания. Такие алгоритмы отличаются от традиционных методов оптимизации тем, что поиск производится из «популяции» решений, а не из одной точки. Каждая итерация метода производит «естественный отбор», который отсеивает неподходящие решения. Решения с высокой пригодностью («биологической реакцией на естественный отбор») «скрещиваются» с другими решениями путем обмена частей одних решений на другие. Решения могут «мутировать» из-за небольших замен одного элемента решения. Скрещивания и мутации генерируют новые решения, которые «генетически» настроены на области допустимого множества, для которых уже было обнаружено хорошее решение.
Разработка математической модели начального расписания занятий
Дадим определение гиперграфа [99]. Гиперграф H(Vt Е) задается множеством \\ элементы которого называются вершинами, и семейством Е подмножеств 1\ называемых ребрами гиперграфа. Гиперграф можно отобразить на плоскости, сопоставляя вершинам точки плоскости, а ребрам — связные области, охватывающие вершины, инцидентные этим ребрам. Например, гиперграф Н с множеством вершин V = {vl, v2, v3, v4, v5, v6} и семейством ребер E « {el e2 {vl, v2), e3 {v2, v4, v5), e4 {v3, v4}, e5={v5), c6= 0} можно изобразить на плоскости, как показано на рис. б.
Множество аудиторийR. AR ={am,aR2,aR3,aR4} - атрибуты (am - количество запланированных «пар» занятий в аудитории за две недели; а - количество распределенных в расписании «пар» занятий в аудитории; а/у - критерий загруженности аудитории; aR4 - атрибут, представляющий вместимость аудитории). R3 \2 N-aR2 Гиперграф учебных поручений U = {L,R,IV}, где Іц- инцидентор, порождающий множество пар М = {(/, r\lv (/, г), leL, re R). Инцидентность между /иг означает, что поручение М для занятия / содержит требуемую аудиторию г или «пустую» аудиторию, вместо которой необходимо распределить подходящую при составлении расписания занятий.
Для моделирования временных сущностей введено множество тайм-слотов Г, элементы которого включают атрибуты учебного дня, «пары» и признака недели. Гиперграф расписания Е={А/,Р,/В}, где 1в - инцидентор, порождающий множество учебных «пар» %ту v)/B (м, v), т A/, v є v]. В работе представлен и исследован эвристический алгоритм преобразования гиперграфа U в гиперграф Я.
Гиперграф учета загрузки ГРУПП 2 = {G, D, 1г}, где h - инцидентор, порождающий множество пар Zs - %g, d]lt (g, d), g є G, d є D\ At = fan, «21} атрибуты Zg (fifc/ - количество «пар» группы g в учебный день d; an - разница количеств «пар» группы g в учебный день d для двух недель расписания). Аналогичным образом определены гиперграфы учета загрузки преподавателей и аудиторий, необходимые для интенсификации процесса формирования начального расписания занятий. Для решения задачи составления начального расписания необходимо ввести следующие понятия:
Модель учебного поручения - включает пять обязательных параметров, три из которых могут иметь «пустые» значения. Сочетание «пустых» и конкретных значений двух параметров - потока и подгруппы с конкретным значением параметра группы моделирует учебные поручения для всех трех типов занятий. G - множество академических групп Т - множество преподавателей Р - множество потоков (подмножеств групп), включая «пустой» поток Q - множество подгрупп (подмножеств студентов группы), включая «пустую» подгруппу А - множество учебных аудиторий, включая специализированные и «пустую» аудиторию 1, если преподаватель t доллсен проводить занятие с с группой g, входящей в поток р, или содержащей подгруппу q с = c[g, р, q, t, о) = в обязательной или пустой аудитории. О, в противном случае. где geG, р єР, q eQ, t єТ, а є A Модель учебного занятия по сравнению с моделью учебного поручения включает еще один параметр - таимслот. Аудитория при этом не может быть «пустой». G - множество академических групп Т- множество преподавателей Р - множество потоков, включая «пустой» поток М- множество таймслотов, однозначно определяющих признак и день недели, и «пару» проведения занятия Q - множество подгрупп, включая «пустую» подгруппу А - множество учебных аудиторий 1, если группой g в таймслоте т проводится ( . \ занятие в аудитории а, s = sig,p,q,t,a,m\ = t О, в противном случае. где geG, р єР, q eQ, t єТ, а єА, m єМ Мл = {tlH, t\} - множество признаков недели Мд - множество дней недели МП - множество "пар" М - Мн х МД х МП Обе модели объединяют распределяемые ресурсы (множества групп, преподавателей и аудиторий) и формируемые занятия.
Решение задачи составления начального расписания занятий в составе интегрированной системы управления учебным процессом наиболее эффективно на основе централизованной базы данных. В данной работе задача составления расписания решается средствами СУБД (системы управления базой данных) [93]. Реляционное представление модели исследования в виде схемы фрагмента базы данных в нотации унифицированного языка моделирования UML представлено на рис. 2.9. Отношение НАГРУЗКА содержит учебные поручения преподавателей кафедр для проведения занятий с академическими группами. Контингент студентов представлен в реляционной модели тремя сущностями ГРУППА, ПОТОК и ПОДГРУППА. В зависимости от студенческого контингента на проводимом занятии в учебном поручении может присутствовать информация о потоке или подгруппе (в виде первичных ключей соответствующих сущностей).
В учебном поручении указывается студенческий контингент (поток, группа или подгруппа), преподаватель, дисциплина, вид занятия и требуемая или желаемая аудитория. Сущность ЗАНЯТИЕ, содержит информацию о занятиях, т.е. расписании. Номер аудитории может иметь неопределенное значение. Этим объясняется наличие связей сущности АУДИТОРИЯ с сущностями НАГРУЗКА и ЗАНЯТИЕ. Учебные поручения формируются для каждой «пары» занятий двух недель расписания. Они же являются исходными данными для формирования расписания, то есть определения элементов множества занятий. Формирование начального расписания занятий завершено, если каждому учебному поручению поставлены в соответствие: - время - день недели, «пара» академических часов, признак одной из двух возможных недель занятий; - место - требуемая по учебному поручению или выбираемая аудитория.
Начальное расписание должно быть непротиворечивым. Под этим понимается отсутствие совпадения разных занятий в одно и то же время для групп, преподавателей и аудиторий. Помимо этого в расписании должны отсутствовать «окна» для студентов, а также отсутствовать дни занятий у групп с количеством «пар» менее двух и более четырех. Эти требования являются обязательными (hard) ограничениями задачи составления начального расписания занятий. К обязательным требованиям относятся: - для каждой группы и каждого преподавателя должны выполняться все виды аудиторной нагрузки в течение двух недель расписания; - отсутствие совпадения разных занятий в одном и том же таймслоте для групп, преподавателей и аудиторий; - расписание занятий для каждой группы не должно содержать «окон»; - количество занятий каждой группы в любой день не должно быть больше четырех и меньше двух; - общее число всех видов занятий в каждом таймслоте не должно превышать аудиторный фонд вуза.
Формирование тестовых заданий
Автоматизация подготовки расписания занятий вуза [38, 51, 37] потребовала создания средств генерации тестовых заданий, максимально соответствующих организации учебного процесса.
Исходя из того, что расписание занятий вуза в большинстве случаев ориентируется на факультеты или подобные им учебные подразделения, в разработанных тестовых заданиях рассматривается факультет, на котором обучаются студенты пяти специальностей, входящих в четыре направления. То есть, две специальности входят в одно направление. В тестовых заданиях рассматриваются дисциплины только четырех циклов дисциплин: - цикл гуманитарных и социально-экономических дисциплин (далее ГСЭ); - цикл математических и естественнонаучных дисциплин (далее ЕН); - цикл общепрофессиональных дисциплин (далее ОПД); - цикл специальных дисциплин (далее СД). Дисциплины задания распределены по циклам учебных планов специальностей при следующих ограничениях: - дисциплины циклов ГСЭ приняты одинаковыми для всех пяти учебных планов; - дисциплины цикла СД приняты различными для различных специальностей; - дисциплины циклов ЕН и ОПД приняты различными для различных направлений.
На каждом курсе формируются потоки: - из пяти групп для дисциплин цикла ГСЭ; - из одной, двух, трех и четырех групп направлений для дисциплин циклов ЕН и ОПД; - из одной, двух и трех групп специальностей для дисциплин цикла СД. Сравнение характеристик различных учебных планов специальностей СГТУ, а также полученные усредненные значения трудоемкости показали, что распределение трудоемкости по циклам происходит по определенным зависимостям. Полученные зависимости были использованы при формировании тестового задания.
Эта геометрическая форма согласуется с результатами диссертации Наумовой СВ. «Разработка и применение средств моделирования в автоматизированных системах синтеза учебных планов высшего образования» [76]. Верхние маркеры показывают величину аудиторной нагрузки в неделю. Нижние - количество часов лекционных занятий. Для всех курсов обучения недельная аудиторная нагрузка каждой группы принята равной 27 часам.
Все учебные планы с точки зрения количественных показателей, определяющих геометрическую форму распределения трудоемкостей (аудитор 58 ной нагрузки) отдельных циклов дисциплин по семестрам (курсам) [41], приняты одинаковыми.
Организационная структура студенческого контингента факультета представлена в табл. 3.4. Такая структура позволяет создавать на курсах потоки из пяти групп для цикла ГСЭ. Потоки для цикла СД создаются на курсе из групп одной специальности (потоки из одной, двух и трех групп). Потоки для циклов ЕН и ОПД создаются на курсе из групп одного направления. Прежде всего, это относится к группам третьей и четвертой специальности, входящим в одно направление, что дает потоки из четырех групп.
Все дисциплины учебных планов связаны с кафедрами (табл. 3.2.), ответственными за проведение этих дисциплин. Кафедры ГСЭ и ЕН отвечают за дисциплины соответствующих циклов учебных планов всех специально 59 стей. Пять других кафедр отвечают за проведение дисциплин циклов ОПД и
Количество преподавателей и персональный состав каждой кафедры могут регулироваться, так же как и перечень лабораторий каждой кафедры. Еще одним фактором, влияющим на качество получаемого расписания занятий, является количество аудиторий, распределяемых для лекционных и практических занятий. В алгоритме формирования расписания для лекционных и практических занятий студенческих коллективов (группы или потока) используется наиболее подходящая по вместимости свободная аудитория.
Расчеты с использованием мультипликативного критерия выборки для четырех «пар»
Представленные на рис.4.5 данные показывают более равномерную нагрузку групп по количеству «пар» в день (рис.4.5,а) при использовании мультипликативного критерия по сравнению с данными рис.4.1,а. 2 "пары" Расчетное количество аудиторий для лекционных и практических занятий Распределение ресурса "ГРУППЫ" по дням (а) и "парам"(б). Разница в количестве одновременно занимающихся групп на различных «парах» (рис.4.1,6 и рис.4.5,б) практически неразличима. Распределение занятий преподавателей по учебным дням
Количество аудиторий для лекционных и практических занятий 18 19 20 21 22 23 24 25 26 27 1 «пара» 414 423 443 431 408 459 430 434 460 433 422 2 «пары» 232 240 217 245 241 209 237 242 222 222 230 3 «пары» 73 70 76 68 65 76 71 61 79 72 73 4 «пары» 20 16 18 13 23 18 15 19 9 21 19 Табл.4.10. Распределение занятий преподавателей по учебным «парам» Количество аудиторий для лекционных и практических занятий 18 19 20 21 22 23 24 25 26 27 1-я «пара» 28,8 30,6 31,5 31,8 31,2 30,2 32,9 32,2 32,2 31,0 31,4 2-я «пара» 32,7 31,3 33,8 34,8 34,4 35,9 36,6 37,2 37,6 35,4 36,7 3-я «пара» 25,0 23,7 22,9 23,4 22,4 22,4 21,8 20,6 21,0 23,0 21,8 4-я «пара» 11,6 10,5 9,9 8,1 10,1 9,5 6,8 8,0 7,2 8,7 8,3
Данные по загрузке преподавателей при составлении начального расписания с использованием мультипликативного критерия (рис.4.6) по сравнению с исходными расчетами (рис.4.2) показали следующее: - снижение количества рабочих дней преподавателей с одной «парой» занятий (рис.4.2,а и рис.4.6,а); - независимость трех других типов рабочих дней от изменяемого параметра; - изменение характера зависимостей одновременно занятых преподавателей от изменяемого параметра.
Качественный характер зависимостей загрузки аудиторий для лекционных и практических занятий от изменяемого параметра для расчетов в п.4.1 (рис.4.3) и с использованием мультипликативного критерия (рис.4.7) не содержат качественных различий и достаточно близки по количественным характеристикам. 2 "пары".
Анализ современного состояния подходов к формализации и решению задачи составления начального расписания занятий показал актуальность создания подсистем автоматизированного формирования расписания в составе интегрированной системы управления учебным процессом вуза. Предложена математическая модель расписания занятий в составе общей модели управления учебным процессом вуза.
Разработан метод составления начального расписания занятий вуза на основе многокритериальной выборки с использованием переопределяемых критериев загруженности основных ресурсов и многокритериальной оценки для выбора места и времени проведения занятий.. Создан алгоритм составления начального расписания занятий вуза с откатом.
Разработаны средства генерации тестовых заданий. Проанализированы характеристики разработанных методов и алгоритмов.
