Содержание к диссертации
Введение
ГЛАВА 1 Состояние вопроса и задачи исследования 12
1.1. Анализ работ в области решения задачи автоматизированного формирования расписания экзаменов 12
1.2. Многокритериальность задачи оптимизации расписания экзаменов 23
1.3 Математические основы многокритериальной оптимизации 31
1.4. Постановка задач исследования 45
Глава 2: Формирование и оптимизация начальнго расписания экзаменов 47
2.1 Общая постановка задачи 47
2.2 Множественно-графовая модель расписания экзаменов 48
2.3 Математическая модель процесса формирования начального расписания экзаменов 53
2.3.1 Ограничения, накладываемые на задачу 53
2.3.2. Критерии загруженности учебного поручения 55
2.3.3 Метод формирования начального расписания экзаменов 57
2.3.4 алгоритм формирования начального расписания экзаменов 61
2.4 визуализация информации в задаче формирования расписания экзаменов 63
2.5 Оптимизация начального расписания экзаменов 65
2.5.1. критерий равномерности распределения экзаменов групп 65
2.5.2 критерий равномерности распределения экзаменов групп 67
2.5.3 метод оптимизации начального расписания экзаменов 68
Глава 3 Применение методов формирования и оптимизации расписания экзаменов ВУЗ'а 71
3.1. Анализ формирования начальных расписаний экзаменов 71
3.2. Анализ работы алгоритма оптимизации 91
Заключенріе 100
Литература 102
- Многокритериальность задачи оптимизации расписания экзаменов
- Множественно-графовая модель расписания экзаменов
- Метод формирования начального расписания экзаменов
- Анализ работы алгоритма оптимизации
Введение к работе
Актуальность исследования. Формирование расписаний, то есть упорядоченных во времени и в пространстве различных видов целенаправленных действий, является типичной задачей планирования работы промышленных предприятий, административных организаций, учебных заведений и т.д.
Под математической моделью теории расписаний понимается
математическое описание некоторого управляемого производственного, организационного технологического процесса, в котором определено множество допустимых управлений (расписаний) этого процесса. Основным критерием оптимальности для задач теории расписаний является протяженность во времени некоторого дискретного процесса. Целью решения большинства задач теории расписаний является минимизация времени выполнения данного процесса. Классическими для теории расписаний задачами являются задачи сетевого планирования и календарного (B.C. Танаев, B.C. Гордон, Я.М. Шафранский, Д. Конвей, С. Максвелл, К. Миллер).
К задачам формирования расписаний так же относятся задачи на формирование временных таблиц (timetabling-задачи) и задачи распределения пакетов информации в информационных сетях (Packet routing-задачи). К timetabling-задачам относят задачи формирования расписаний ВУЗов, транспортные расписания и т.д. Существенным отличием timetabling-задач от классических задач теории расписания является фиксированная величина интервала времени, в котором необходимо распределить процессы. Вследствие этого целью оптимизации является достижение наилучшего распределения процессов в соответствии с принимаемыми требованиями и ограничениями. Подобные задачи решаются совместно теорией расписаний и другими дисциплинами, например теорией исследования операций.
Timetabling-задачи, как правило, не могут быть решены точными методами. Для решения таких задач используются различные эвристические алгоритмы (E.Burke, Y. Bykov и др.).
Задача формирования расписания занятий и экзаменационных сессий играет особую роль при организации учебного процесса. Качество сформированных расписаний занятий и экзаменов влияет на эффективность учебного процесса ВУЗа. Комплексный характер качества расписания связан с учетом требований организационного и методического характера. Формирование расписания занятий и экзаменов в ВУЗе с большим студенческим контингентом и множеством дисциплин различных учебных планов при учете всех требований и ограничений является сложной и комплексной задачей.
Процесс формирования расписания экзаменов является многоэтапным. На первом этапе на основе учебных поручений, включающих дисциплину, студенческий контингент, преподавателя, и ряда ограничений формируется начальное расписание экзаменов. На втором этапе осуществляется оптимизация начального расписания. На третьем этапе может проводиться локальная корректировка расписания для конкретных подразделений вуза (факультетов, специальностей, кафедр и т.д.).
Автоматизированное составление расписания на любом этапе формирования расписания является многофазным процессом, включающим:
-формализацию задачи формирования расписания и определение ограничений;
-реализацию алгоритма поиска решений, удовлетворяющих ограничениям поставленной задачи;
-оценку полученного множества решений и выбор наиболее приемлемого.
Получаемое на каждом этапе расписание экзаменов не должно содержать конфликтов, т.е. расписание быть непротиворечивым. Для обеспечения
непротиворечивости расписания достаточно его соответствия обязательным ограничениям.
Практика составления расписаний экзаменов показала, что при соблюдении всех перечисленных обязательных ограничений расписание непротиворечиво. То есть на первом этапе получается непротиворечивое начальное расписание, качество которого следует оценить.
Для оценки качества формируемого расписания, уже на этапе формирования начального расписания к обязательным ограничениям добавляется ряд непротиворечивых, желательных (soft) ограничений. Ограничения именуются «желательными» потому, что расписание может не отвечать данным ограничениям, отвечать частично или полностью. Оценка качества проводится по соответствию расписания желательным ограничениям. Количество и качество этих ограничений существенно влияет на возможность и трудоемкость получения решения. В соответствии с работами ряда авторов (И.И. Морковин, Э.А. Мухачева, А.А. Овчинников, Е. Zitzler, Y. Bykov) будем рассматривать проблему формирования расписания экзаменов как многокритериальную
Для оценки качества расписаний экзаменов, получаемых на этапе
оптимизации, используется совокупность критериев. Как правило,
относительная значимость этих критериев неизвестна до тех пор, пока не будут определены все основные свойства модели оптимизации и не будут полностью установлены все возможные взаимосвязи. Таким образом, стратегия составления расписания экзаменов состоит, прежде всего, в возможности адекватной постановки задачи многокритериальной оптимизации, а также в отображении желаемых предпочтений в форме числовых зависимостей.
Статичные критерии, характеризующие оптимальность расписания, образуют новый, единый критерий (целевую функцию) в виде суммы критериев. Следовательно, оптимизация полученного первоначального решения производится по полученной целевой функции. Для описания
получаемых решений вводится концепция множества точек неухудшаемых решений (оптимальность по Парето). Неухудшаемым решением принимается такое, в котором улучшение по одному из критериев не приводит к ухудшению по любому другому критерию.
Применение концепции оптимальности по Парето позволяет избежать «вырождения» решения, т.е. потери качества по одному из критериев при одновременном приращением качества по другому. Иначе может быть сформировано расписание с низким качеством по ряду частных критериев. Такое расписание может быть признано абсолютно неприемлемым.
Обязательность «пауз» для подготовки между экзаменами существенно изменяет задачу формирования расписания экзаменов по сравнению с известными решениями, представленными в диссертационных работах Макарцовой Е.А. и Костина С.А.
К принципиальным отличиям относятся:
использование обязательных ограничений принципиально отличных от ограничений, используемых при формировании расписания занятий. Например, в расписании экзаменов необходимо обязательное включение «пауз» между экзаменами группы таким образом, чтобы студенты имели время на подготовку, тогда как при формировании расписаний занятий отсутствие «окон» между занятиями являются одним из видов желательных ограничений.
повышение в полтора-два раза количества расставляемых в расписании событий по сравнению с задачей формирования расписания учебных занятий. Например, в описанном ниже примере расписания экзаменов, необходимо расставить 610 экзаменов. Необходимо наличие интервала между экзаменами каждой отдельной группы не менее 3 суток, причем каждые сутки содержат две смены для проведения экзаменов. Требуется выдержать интервал именно в календарных сутках, поэтому минимальное количество пропускаемых смен для группы варьируется от пяти до семи. Таким образом, каждый расставляемый в расписание экзамен группы связан с множеством расставляемых для него
пропусков, которые так же рассматриваются как расставляемые события, увеличивая первоначальное количество расставляемых событий, по крайней мере, в пять раз. Количество расставляемых занятий этой же формы обучения составило около двух тысяч.
Использование статистических критериев оптимальности является наиболее легко реализуемым методом решения задач формирования начального расписания экзаменов ВУЗа и его последующей оптимизации. Однако данный подход часто приводит к попаданию решения в область локального экстремума, что не позволяет получить наилучшее из доступных решений, хотя и позволяют достигать приемлемых результатов.
Использование динамических, изменяющихся в процессе расчета критериев позволяет избегать подобных проблем. Методы формирования расписания экзаменов с использованием динамических оценок остаются практически не исследованными. Необходимость оценки качества полученных расписаний экзаменов так же обуславливает необходимость создания визуальных средств моделирования информации для задач формирования расписаний ВУЗа.
Изложенное определило актуальность данной работы, целью которой являются разработка, исследование и реализация математической модели и многокритериальных методов формирования и оптимизации расписания экзаменов в интегрированной системе управления учебным процессом вуза.
В соответствии с целью в диссертации поставлены следующие задачи:
разработка математической модели и методов формирования и оптимизации расписания экзаменов вуза с использованием критериев загруженности ресурсов и критериев равномерности;
разработка метода визуального представления информации в задаче формирования расписания экзаменов;
анализ характеристик разработанных алгоритмов и методов;
4) реализация и практическое применение предложенных алгоритмов
формирования расписания экзаменов в виде программного обеспечения, позволяющего автоматизировать решение задачи формирования расписания экзаменов.
Объект исследования — расписание экзаменов вуза.
Предмет исследования - формирование начального расписания экзаменов вуза и его многокритериальная оптимизация.
Методологическая и теоретическая основа исследования. В
диссертационной работе использован математический аппарат теории множеств, теории графов, исследования операций, общей теории расписаний.
В работе использованы методы системного анализа, статистики, оптимизации, компьютерной графики.
Научная новизна исследования состоит в следующем:
-разработан метод формирования начального расписания экзаменов для интегрированных систем управления учебным процессом вуза с применением критерия загруженности учебных поручений. В отличие от существующих подходов предлагаемый метод использует централизованную базу данных вуза, в рамках которой автоматически формируются учебные поручения для проведения экзаменов. Критерии загруженности учебных поручений рассчитываются при каждом включении очередного экзамена в расписание сессии. Выбор очередного учебного поручения для его включения в расписание осуществляется на основании максимального значения критерия загруженности поручения;
-предложен метод визуального представления расписания экзаменов в виде круговой диаграммы. Круговая диаграмма впервые используется для
анализа и проверки соответствия расписания обязательным и желательным ограничениям;
-введены критерии равномерности экзаменов и расписания, отличающиеся тем, что отражают качественные характеристики всего расписания в целом, и влияние каждого экзамена в расписании группы и в составе конкретного таймслота сессии. Критерий равномерности экзаменов группы связан с обеспечением равномерности интервалов между экзаменами. Критерий равномерности экзаменов в таймслоте связан с обеспечением равного количества экзаменов в период сессии;
-разработан метод многокритериальной оптимизации начального расписания экзаменов. Метод основан на разработанной автором концепции равномерности распределения экзаменов групп, таймслотов и всего расписания. Оптимизация начального расписания основана на последовательном выборе экзамена для перестановки по максимальному значению мультипликативного критерия равномерности экзамена. Возможность перестановки определяется соблюдением Парето-ограничений.
На защиту выносятся:
модель и методы формирования и оптимизации начального расписания экзаменов вуза с использованием критериев загруженности ресурсов и критериев равномерности;
метод визуального представления информации в задаче формирования расписания экзаменов;
программное обеспечение, формирующее расписание экзаменов вуза.
Практическая значимость диссертационного исследования состоит в том, что представленные модель, методы и алгоритмы могут быть использованы при разработке и практической реализации подсистем
автоматизированного формирования расписаний экзаменов для интегрированных систем управления учебным процессом вуза.
Апробация результатов исследования. Предложенные в диссертации модели, методы и алгоритмы были использованы при разработке и практической реализации информационных систем управления учебным процессом вуза. Предложенные методы внедрены в Саратовской государственной академии права и Московской медицинской академии им. И.М. Сеченова.
Основные результаты работы докладывались на XVI и XVII Международных конференциях «Информационные технологии в образовании» в 2006 и 2007 гг.
Публикации. По теме диссертации опубликовано 7 работ, в том числе одна в издании, рекомендованном в ВАК РФ.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав и заключения, изложенных на 105 страницах, в том числе 18 рисунков, списка использованной литературы, включающего 83 наименования.
Публикации. По теме диссертации опубликовано 7 работ.
В первой главе, носящей обзорный характер, даются анализ состояния и развернутая постановка проблемы. Рассматриваются известные методы формирования начального расписания экзаменов и его оптимизации. Анализируются существующие подходы к формализации, точные и эвристические алгоритмы генерации расписаний, основанные на общей теории расписаний, теории графов, теории множеств, математическом программировании, искусственном интеллекте.
Во второй главе рассмотрены разработка и исследование математической модели формирования расписания экзаменов вуза, дается общая постановка задачи. Описаны разработанный метод и алгоритм формирования начального расписания с использованием критериев загруженности и алгоритм
последующей оптимизации сформированного начального расписания. Рассмотрен метод графической визуализации информации в задаче формирования расписания экзаменов.
В третьей главе представлены результаты применения разработанного метода формирования начального расписания экзаменов и его многокритериальной оптимизации для различных вариантов начального расписания. Оптимизация расписания производилась с использованием как аддитивных, так и мультипликативных критериев равномерности экзаменов.
Многокритериальность задачи оптимизации расписания экзаменов
Задача оптимизации расписания экзаменов [78; 79; 82] то есть нахождения глобального оптимума с помощью многокритериальной целевой функции, в общем случае является неразрешимой. Нельзя гарантировать, что решение задачи будет получено за конечное число операций.
Существует два способа ограничить количество операций алгоритма решения задач оптимизации. Первый способ - сформулировать условия в виде жестких требований, наложенных на целевую функцию и допустимое множество решений задачи, которые, по крайней мере, что даст возможность с уверенностью говорить о том, что точное решение будет найдено. Второй подход позволяет рассматривать более широкий класс задач: отказываясь от требования разрешимости, необходимо получить оценку решения по введенным критериям оптимальности. При таком подходе желательно иметь также некоторую границу приемлемости полученной оценки.
Развитее электронно-вычислительных средств и специализированных программных средств для решения математических задач является предпосылкой развития методов многокритериальной оптимизации. Учитывая сложность и возрастающую потребность в оптимизации процессов управления, развитие методов оптимизации является актуальной задачей. Проблемам оптимизации, разработке новых методов и другим важным исследованиям в области решения задач оптимизации посвящено немало работ [64; 65; 71; 83]
Процедуру (или алгоритм) решения задачи оптимизации можно представить в виде итеративного процесса, который порождает последовательность точек в соответствии с предписанным набором правил, включающим критерий окончания счета. Обычно, глобальное решение задачи оптимизации предлагается найти, перебрав все ее локальные решения. Такая задача, как правило, оказывается трудоемкой. Другой подход — искусственно ограничить количество получаемых решений. Необходимо перебрать часть локальных решений и показать, что оставшиеся локальные минимумы не влияют на точность решения. Таким образом, идея всех методов оптимизации сводится к оценке значений целевой функции оптимизации на некотором множестве точек из допустимого множествах, и различие методов заключается в способах выбора этих точек.
Оценить эффективность алгоритма оптимизации возможно ч по сходимости генерируемой им последовательности точек к глобальному оптимальному решению. Однако в большинстве случаев получаются менее благоприятные результаты: невыпуклость функций, большая размерность задачи или другие трудности вынуждают останавливать алгоритм, если получена точка, принадлежащая некоторому множеству приближенных решений. Другими словами, для любого численного алгоритма необходимы условия остановки. Это ключевой момент, так как без какой-либо дополнительной информации или предположений о задаче невозможно сделать выводы о точности решения, полученного за некоторое фиксированное число шагов алгоритма. Таким образом, для четкого определения условий остановки алгоритма необходима дополнительная информация или предположения, или же условия остановки должны быть эвристическими.
Все известные методы оптимизации можно разделить на две категории: детерминированные [12] и стохастические [50; 75; 77]. Детерминированные методы получают оптимальное решение посредством исчерпывающего поиска на всем допустимом множестве. Поэтому большинство детерминированных методов теряют эффективность и надежность с возрастанием размерности задачи. Более того, чтобы гарантировать успех, такие методы требуют соблюдения дополнительных ограничений, наложенных на функцию цели. Слабость детерминированных алгоритмов в том, что они зачастую останавливают вычисления найдя локальный оптимума и не предоставляя искомого решения в виде глобального оптимум.
Стохастические алгоритмы позволяют уйти от проблем детерминированных алгоритмов. Здесь стохастический подход присутствует не только в разработке и анализе алгоритма, но и используется в решении базовых проблем, например, при определении условия остановки. Большинство стохастических методов оценивают значение функции цели в случайных точках допустимого множества с последующей обработкой выборки. Так как выборка случайна, то стохастические методы не гарантируют нахождения глобального оптимума в пространстве решений.
Любой численный метод имеет свои преимущества и недостатки, в связи с чем возникает вопрос о сравнении различных методов. Существует ряд факторов, которые следует учитывать при оценке эффективности алгоритмов и их сравнении. Так, универсальность алгоритма определяется тем классом задач, для решения которых он предназначен, а также рамками требований, предъявляемых алгоритмом к задачам данного класса. Другими важными характеристиками алгоритма является его надежность (или устойчивость), точность, чувствительность к параметрам и исходным данным, затраты на предварительную обработку и вычисления.
Множественно-графовая модель расписания экзаменов
Построим математическую модель расписания экзаменов в множественно-графовой интерпретации.
Дадим определение гиперграфа [52]. Гиперграф H(V, Е) задается множеством V, элементы которого называются вершинами, и семейством Е подмножеств V, называемых ребрами гиперграфа. Гиперграф можно отобразить на плоскости, сопоставляя вершинам точки плоскости, а ребрам — связные области, охватывающие вершины, инцидентные этим ребрам. Например, гиперграф Н с множеством вершин V = {vl, v2, v3, v4, v5, v6} и семейством ребер E = {el=e2={vl, v2}, e3={v2, v4, v5}, e4={v3, v4}, e5={v5}, еб=0} можно изобразить на плоскости, как показано на рис. 2.1.
Если каждое ребро гиперграфа имеет степень, равную двум, то гиперграф является просто графом. На рис. 2.1 множественность ребер представлена ребрами в] и е2\ «петля» отображается ребром е5; v6 представляет собой изолированную вершину.
Множество учебных поручений Ь — JC; і — 1,...,1 f
В учебном поручении, представляющем часть индивидуальной нагрузки преподавателя, указывается студенческий контингент (группа или подгруппа), преподаватель, дисциплина, требуемая аудитория. Номер аудитории может иметь «пустое» значение. «Пустое» значение (Null) - это термин реляционных моделей данных. Означает отсутствие конкретной информации, которое может быть заменено конкретным значением по мере необходимости. Учебные поручения формируются для каждого экзамена каждой группы или подгруппы в сессии.
Множество учебных поручений включает два подмножества: 1. учебные поручения с требуемыми аудиториями, например, дисплейные классы для приема экзаменов по программированию. 2. учебные поручения без требуемых аудиторий. Множество таимслотов Т.
Введем множество таимслотов, элементы которого однозначно определяют номер недели, день недели и смену. Таким образом множество таимслотов получается путем декартового произведения трех сущностей: недели, дня и смены. Т = ТдхТпхТ# td є Тд — идентификатор дня недели; tn єТп — идентификатор смены; 1 # = /# # # / - множество идентификаторов недель сессии. Экзаменационная сессия, для очной формы обучения в ВУЗах, как правило, длится 21 календарный день и содержит 42 таймслота (3 недели, семь дней, две смены).
Множество академических групп X = \xmm = 1,...,М$ х = Xах\ ах2 ахз ах4 і - атрибуты каждой группы (аХІ- количество запланированных, согласно учебной нагрузке, экзаменов группы; аХ2 — количество уже распределенных по таймслотам экзаменов группы; сгхз — критерий загруженности группы; аХ4 - количество студентов группы). G3 \8 N-aG2 36-aG2 (2Л) где N — количество смен экзаменов в день. Данное количество обычно равно 2. Множество подгрупп сдающих экзамены.
В ряде случаев группы разбивают на подгруппы для сдачи экзаменов. Это может быть связанно со спецификой предмета или вместимостью аудитории. Множество групп и множество подгрупп охватывают все виды контингента студентов, участвующих в экзаменационной сессии. Введем следующее множество. Z = XuY Z = {zo\o = },...,0} - студенческий контингент. Введем гиперграф структуры групп и подгрупп A = {(X,Y)}.
На рис.2.2 данный гиперграф представлен двудольным графом для академических групп двух специальностей. В данном случае группы разбиваются на подгруппы для изучения иностранных языков. Причем первая группа разбивается на две подгруппы (например, для изучения английского и немецкого языков), а вторая группа на три подгруппы (английский, немецкий, французский языки).
Множество преподавателей Р, разделяемое на подмножества преподавателей кафедр. Лр = \аР],аР2,аР2\ - атрибуты (&р\- количество запланированных экзаменов преподавателя за время сессии; &р2 — количество распределенных в расписании экзаменов преподавателя; "РЗ - критерий загруженности преподавателя). аРЗ = apl рг (2-2) 36 — С1р2 Из двух составляющих сущностей студенческого контингента (ГРУППА, ПОДГРУППА) только (ГРУППА) является устойчивым образованием. Множество аудиторий А = \ак\к = 1,...,К] AR = {aRl,ain,aRi,aK4} - атрибуты каждой аудитории (aRJ - общее количество экзаменов, согласно учебной нагрузке кафедр, возможных для проведения в данной аудитории за период сессии; aR2 - количество распределенных в расписании экзаменов в данную аудиторию; aR3 - критерий загруженности аудитории; aR4 - атрибут, представляющий вместимость аудитории).
Метод формирования начального расписания экзаменов
Для анализа работы разработанного алгоритма формирования начального расписания экзаменов были созданы программные средства как генерации тестовых заданий, максимально соответствующих требованиям образовательных стандартов и организации учебного процесса, так и программные средства, реализующие алгоритм формирования начального расписания экзаменов.
Автоматизации подготовки расписания экзаменов потребовала создания средств генерации тестовых заданий, максимально соответствующих требованиям образовательных стандартов и организации учебного процесса.
В большинстве случаев расписание занятий и экзаменов ориентируется на факультеты или подобные им подразделения ВУЗ а. Исходя из этого, в качестве студенческого контингента тестовых заданий рассматривается факультет, на котором обучаются студенты пяти специальностей, входящих в четыре направления.
Для дисциплин учебных планов пяти специальностей были приняты следующие ограничения: - дисциплины цикла гуманитарных и социально-экономических дисциплин (ГСЭ) приняты одинаковыми для всех пяти учебных планов; - дисциплины цикла специальных дисциплин (СД) приняты различными для различных специальностей; - дисциплины циклов математических и естественнонаучных дисциплин (ЕН) и общепрофессиональных дисциплин (ОПД) приняты различными для разных направлений.
Такое представление учебных планов соответствует используемым в высшей школе образовательным стандартам. В табл.3.1 представлено принятое в тестовом задании количественное распределение дисциплин различных циклов учебных планов по курсам обучения.
Организационная структура студенческого контингента факультета представлена в табл.3.2. Это позволяет создавать на курсах потоки из пяти групп для цикла ГСЭ. Потоки для цикла СД создаются на курсе из групп одной специальности (потоки из одной, двух и трех групп). Потоки для циклов ЕН и ОПД создаются на курсе из групп одного направления. Прежде всего, это относится к группам третьей и четвертой специальностям третьего направления, что дает потоки из четырех групп.
Тестовое задание содержит 1600 учебных поручений 104 преподавателей для проведения занятий, зачетов и экзаменов у 50 групп факультета. Каждое учебное поручение содержит студенческий контингент (поток, группа или подгруппа), преподавателя, дисциплину, вид занятия или отчетности, а также требуемую или желаемую аудиторию. Учебные поручения являются исходными данными для составления расписания занятий и экзаменов.
Таким образом, каждое тестовое задание содержит информацию об учебных поручениях для приема экзаменов в 50 группах пяти курсов факультета дневного отделения. Общее количество учебных поручений каждого тестового задания составляет 250. Продолжительность экзаменационной сессии принята равной 21 дню. Каждый день сессии включает две смены сдачи экзаменов, вследствие чего расчетное количество таймслотов сессии составляет 42.
Таким образом, критерий загруженности учебного поручения является мультипликативным обобщенным критерием, включающим частные критерии загруженности группы, преподавателя и аудитории. Каждый из частных критериев является относительной величиной. Изменение количества последовательно включаемых в расписание экзаменов ресурса обеспечивает возможность переопределения значения частного критерия.
Так как по условиям тестовых заданий в учебных поручениях по приему экзаменов во всех группах осуществляется прием пяти экзаменов, то к х 5-Д2 (3.5) 42-«;
Для исходного расчета критериев загруженности учебных поручений перед началом формирования начального расписания выражение (3.5) принимает следующий вид Так как по условиям тестовых заданий в учебных поручениях по приему экзаменов во всех группах отсутствуют требуемые аудитории, а количество аудиторий для приема экзаменов В может изменяться, то к ґ = 250-а?» (3.7) Для исходного расчета критериев загруженности учебных поручений перед началом формирования начального расписания выражение (3.7) принимает следующий вид к (3.8) _ 250 1 425
Так как по условиям тестовых заданий в учебных поручениях по приему экзаменов во всех группах отсутствуют экзамены в подгруппах, то KY=\ (3.9) Таким образом, критерии загруженности учебных поручений в процессе формирования начального расписания экзаменов будут определяться согласно следующему выражению F 5-а 2 а{-а{ 250-а" п і m V —X— -X —- {J.IV) , 42-а 2 42 -а{ 42В-а " где / - текущая группа учебного поручения; j - текущий преподаватель учебного поручения. Для исходного расчета критериев загруженности учебных поручений тестовых заданий перед началом формирования начального расписания выражение (3.10) принимает следующий вид Vі = X —; — X 1х - х250 (3.11) 42 42 - а{ 42В Формирование непротиворечивого начального расписания для одного из тестовых заданий без использования прогноза о диапазонах таймслотов для включения в расписание последующих экзаменов привело к следующему. Частные критерии равномерности расписания составили к fac" =126,43 и К?" " -113,843
Анализ работы алгоритма оптимизации
Тестовое задание содержит 1600 учебных поручений 104 преподавателей для проведения занятий, зачетов и экзаменов у 50 групп факультета. Каждое учебное поручение содержит студенческий контингент (поток, группа или подгруппа), преподавателя, дисциплину, вид занятия или отчетности, а также требуемую или желаемую аудиторию. Учебные поручения являются исходными данными для составления расписания занятий и экзаменов.
Таким образом, каждое тестовое задание содержит информацию об учебных поручениях для приема экзаменов в 50 группах пяти курсов факультета дневного отделения. Общее количество учебных поручений каждого тестового задания составляет 250. Продолжительность экзаменационной сессии принята равной 21 дню. Каждый день сессии включает две смены сдачи экзаменов, вследствие чего расчетное количество таймслотов сессии составляет 42. Как отмечено во второй главе, каждому учебному поручению можно поставить в соответствие некоторый числовой критерий. vE =KXXKPXKAXKY (3.1) 0 Кх,КР,КА,Ку 1 где, KY,Kr,KA- частные критерии загруженности групп, преподавателя и аудитории, рассчитываемые в соответствии со следующим выражением: Ki-Ui а\-а\ (3.2) т і а —а-, ах - количество запланированных ресурсу экзаменов за период сессии; а 2- количество распределенных в расписание экзаменов ресурса; а — количество таймслотов в сессии.
Множество учебных поручений может содержать два подмножества, для которых значения частных критериев загруженности аудитории определяются различным образом: 1. учебные поручения с требуемыми аудиториями, например, дисплейные классы для приема экзаменов по программированию. Для них к, рассчитывается по формуле (3.2); 2. учебные поручения без требуемых аудиторий. Частный критерий для учебных поручений этого подмножества рассчитывается следующим образом: null „null к т,н _а\ -аг (3.3) Л null _ null а -а-, а""1 - количество учебных поручений без требуемых аудиторий; а"ш - количество включенных в расписание учебных поручений без требуемой аудитории; am" — количество таймслотов доступных аудиторий.
Частный критерий учета экзаменов подгрупп ку зависит от максимального количества сдающих экзамены подгрупп в группах. Кг =- -, (3.4) Чтах где qmax - максимальное количество подгрупп групп всех поручений qY - количество подгрупп группы.
Таким образом, критерий загруженности учебного поручения является мультипликативным обобщенным критерием, включающим частные критерии загруженности группы, преподавателя и аудитории. Каждый из частных критериев является относительной величиной. Изменение количества последовательно включаемых в расписание экзаменов ресурса обеспечивает возможность переопределения значения частного критерия. Так как по условиям тестовых заданий в учебных поручениях по приему экзаменов во всех группах осуществляется прием пяти экзаменов, то к х 5-Д2 (3.5) 42-«;
Для исходного расчета критериев загруженности учебных поручений перед началом формирования начального расписания выражение (3.5) принимает следующий вид Так как по условиям тестовых заданий в учебных поручениях по приему экзаменов во всех группах отсутствуют требуемые аудитории, а количество аудиторий для приема экзаменов В может изменяться, то к ґ = 250-а?» (3.7) Для исходного расчета критериев загруженности учебных поручений перед началом формирования начального расписания выражение (3.7) принимает следующий вид к (3.8) _ 250 1 425
Так как по условиям тестовых заданий в учебных поручениях по приему экзаменов во всех группах отсутствуют экзамены в подгруппах, то KY=\ (3.9) Таким образом, критерии загруженности учебных поручений в процессе формирования начального расписания экзаменов будут определяться согласно следующему выражению F 5-а 2 а{-а{ 250-а" п і m V —X— -X —- {J.IV) , 42-а 2 42 -а{ 42В-а " где / - текущая группа учебного поручения; j - текущий преподаватель учебного поручения. Для исходного расчета критериев загруженности учебных поручений тестовых заданий перед началом формирования начального расписания выражение (3.10) принимает следующий вид Vі = X —; — X 1х - х250 (3.11) 42 42 - а{ 42В Формирование непротиворечивого начального расписания для одного из тестовых заданий без использования прогноза о диапазонах таймслотов для включения в расписание последующих экзаменов привело к следующему. Частные критерии равномерности расписания составили к fac" =126,43 и К?" " -113,843
