Содержание к диссертации
Введение
1. Состояние вопроса и задачи исследований 8
1.1. Анализ работ в области решения задачи автоматизированного формирования расписания занятий 8
Общая характеристика задачи 8
Подходы к формализации и точные методы генерации расписаний 14
Эвристические методы генерации расписаний 16
1.2. Многокритериальность задачи оптимизации расписания занятий 18
Основные понятия и определения 18
Особенности решения задач оптимизации расписания 20
Многокритериальность в задаче формирования оптимального расписания занятий 22
1.3. Математические основы многокритериальной оптимизации 25
Векторные критерии оптимальности 25
Принцип Эджворта-Парето 28
Методы свертывания векторного критерия 30
Способы назначения весовых коэффициентов 32
1.4. Постановка задач исследования 38
2. Разработка метода оптимизации расписания занятий вуз'а и моделирование характеристик учебных планов 40
2.1. Разработка метода многокритериальной оптимизации расписания .40
Разработка математической модели многокритериальной оптимизации начального расписания занятий 40
Интегральная оценка расписания 46
Метод решения поставленной задачи 50
2.2. Аналитическое исследование характеристик учебных планов 57
Источник статистической информации 57
Анализ характеристик учебных планов 59
2.3 Формирование тестовых заданий и их визуализация 65
Формирование тестовых заданий 65
Графическая визуализация формирования расписания занятий 71
3. Применение метода многокритериальной оптимизации расписания занятий вуз'а 77
3.1. Оценка качества начальных расписаний 77
3.2. Анализ работы алгоритма оптимизации 82
3.3. Анализ многокритериальной оптимизации расписания 98
Заключение 104
Литература
- Подходы к формализации и точные методы генерации расписаний
- Многокритериальность задачи оптимизации расписания занятий
- Разработка математической модели многокритериальной оптимизации начального расписания занятий
- Анализ работы алгоритма оптимизации
Введение к работе
Составление расписания учебных занятий является одной из основных задач автоматизации управления учебным процессом ВУЗ'а. Качественное расписание занятий определяет эффективность учебного процесса и, как следствие, отражается на подготовке специалистов.
Составление расписания занятий является многоэтапным. На первом этапе формируется непротиворечивое начальное расписание на основе учебных поручений, включающих дисциплину, вид занятия, студенческий контингент и преподавателя. Затем для всего учебного заведения осуществляется оптимизация начального расписания. При необходимости может проводиться последующая корректировка расписания в виде локальных оптимизаций на низших уровнях управления учебным процессом (факультеты, специальности, кафедры и т.д.).
Автоматизированное составление расписания на любом этапе является многофазным процессом, включающим:
формализацию задачи формирования расписания занятий и определение ограничений;
реализацию алгоритма поиска решений, удовлетворяющих ограничениям поставленной задачи;
оценку полученного множества решений и выбор наиболее приемлемого.
Получаемое на каждом этапе расписание занятий должно быть непротиворечивым, то есть соответствовать обязательным (hard) ограничениям:
ни одна группа не может находиться более чем на одном занятии в одно и тоже время;
ни один преподаватель не может проводить более одного занятия одновременно;
учебные помещения для всех видов занятий должны быть подходящими как по назначению, так и по количеству мест.
Для улучшения качества формируемого расписания, уже на этапе формирования начального расписания к обязательным ограничениям добавляется ряд непротиворечивых, желательных (soft) ограничений (отсутствие у группы дней с одной «парой» занятий, недопустимость возникновения «окон» в расписании групп и т.п.). На практике, начальное расписание требует дальнейшей оптимизации в соответствии с рядом желательных ограничений, не учитываемых на первом этапе формирования расписания. Количество и качество этих ограничений могут существенно повлиять на трудоемкость и возможность получения решения. Во избежание этого желательные ограничения вводятся в виде набора критериев оптимальности, приводя тем самым проблему составления расписания занятий к задаче многокритериальной оптимизации.
Для оценки расписаний занятий, получаемых на этапе оптимизации начального расписания, используется совокупность критериев. Как правило, относительная значимость этих критериев неизвестна до тех пор, пока не будут определены все основные свойства модели оптимизации и не будут полностью установлены все возможные взаимосвязи. Таким образом, стратегия составления расписания занятий состоит, прежде всего, в возможности адекватной постановки задачи многокритериальной оптимизации, а также в отображении желаемых предпочтений в форме числовых зависимостей.
При использовании аддитивной целевой функции оптимизации различные критерии оптимальности выражаются едиными единицами «полезности» (значениями критериев). Использование статичных весов, характеризующих относительную значимость критериев, образует новый, единый критерий (целевую функцию) в виде суммы первоначальных критериев, умноженных на свои веса. Далее проводится оптимизация по полученной целевой функции. Для описания получаемых решений вводится концепция множества точек не-ухудшаемых решений (оптимальность по Парето). Неухудшаемым решением принимается такое, в котором-улучшение по одному из критериев не приводит к некоему ослаблению по любому другому критерию.
Применение такого подхода с использованием статичных весов критериев связанно с рядом существенных недостатков. Прежде всего, потеря качества по одному из критериев компенсируется приращением качества по другому. Это может привести к расписанию с низким качеством по ряду частных критериев и быть, в связи с этим, абсолютно неприемлемым. Во-вторых, в ряде случаев нет никакой информации о важности критериев.
Практически не исследованными являются методы многокритериальной оптимизации расписания занятий с использованием динамических, изменяющихся в процессе расчета весов, а также вопросы создания визуальных средств моделирования для задач оптимизации расписания занятий. Кроме того, в известных работах по автоматизированному составлению расписания занятий недостаточно учтены требования интегрированных систем. Изложенное определило актуальность данной работы, целью которой является разработка, реализация и исследование математических моделей и методов многокритериальной оптимизации начального расписания занятий в интегрированной системе управления учебным процессом ВУЗ'а.
В соответствии с целью в диссертации поставлены следующие задачи:
разработка метода многокритериальной оптимизации начального расписания занятий ВУЗ'а;
реализация алгоритма оптимизации расписания;
разработка визуальных средств моделирования информации в задаче формирования расписания занятий;
исследование характеристик разработанных алгоритмов и методов.
Объект исследования - расписание занятий ВУЗ'а.
Предмет исследования - многокритериальная оптимизация начального расписания занятий ВУЗ'а.
Методологическая и теоретическая основа исследования. В диссертационной работе использован математический аппарат теории множеств, теории графов, исследования операций, общей теории расписаний.
В работе использованы методы системного анализа, статистики, оптимизации, компьютерной графики.
Научная новизна исследования состоит в следующем:
применен метод аддитивной оценки значений критериев оптимальности для каждого учебного занятия расписания;
получен метод интегральной оценки расписания занятий по заданным критериям оптимальности, показывающий разницу между текущим и «идеальным» расписанием занятий;
разработан метод многокритериальной оптимизации начального расписания занятий для интегрированных систем управления учебным процессом
. ВУЗ'а, объединяющий обобщенный критерий с системой обязательных и желательных ограничений;
применен градиентный подход для предложенного метода многокритериальной оптимизации;
реализована компьютерная система многокритериальной оптимизации начального расписания занятий ВУЗ'а с использованием динамически формируемых весов критериев в функции выбора занятия. Для исследования были использованы следующие критерии:
минимизация количества занятий для указанной «пары»;
равномерность распределения занятий учебных групп по количеству «пар» каждого учебного дня для обеих недель расписания;
равномерность занятий групп для обеих недель расписания.
- разработаны статические и динамические средства визуального моделирова
ния расписания занятий.
Практическая значимость диссертационного исследования состоит в том, что представленная модель, метод и алгоритм могут быть использованы при разработке и практической реализации подсистем автоматизированного формирования расписания для интегрированных систем управления учебным процессом ВУЗ'а.
7 Апробация результатов исследования. Предложенные в диссертации
модели, методы и алгоритмы были использованы при разработке и практической реализации информационных систем управления учебным процессом ВУЗ'а. Система прошла внедрение в Саратовской государственной академии права и продолжает совершенствоваться.
Основные результаты работы докладывались на XV Международной конференции «Применение новых технологий в образовании» (г. Москва, 2004), XIII, XIV и XV Международных конференциях-выставках: «Информационные технологии в образовании» (г. Москва, 2003, 2004, 2005).
Публикации. По теме диссертации опубликовано 14 работ общим объемом 2 печатных листа.
В первой главе, носящей обзорный характер, дается анализ состояния и развернутая постановка проблемы. Рассматриваются основные методы решения задачи составления оптимального расписания учебных занятий. Анализируются существующие подходы к формализации, точные и эвристические алгоритмы генерации расписаний, основанные на общей теории расписаний, теории графов, теории множеств, математическом программировании, искусственном интеллекте.
Во второй главе разработана и исследована математическая модель многокритериальной глобальной оптимизации расписания занятий ВУЗ'а, рассматриваются общая постановка задачи и стратегия оптимизации расписания с использованием динамически формируемых весов критериев оптимальности. Показана методика формирования тестовых начальных расписаний. Описывается метод графической визуализации расписания занятий ВУЗ'а.
В третьей главе предложенный метод многокритериальной оптимизации применен для решения задачи многокритериальной оптимизации начального расписания занятий ВУЗ'а. Оптимизация расписания проводилась с использованием как статических, так и динамических весовых коэффициентов функции выбора занятий.
Подходы к формализации и точные методы генерации расписаний
Большинство точных методов использует графовую модель расписаний. В ней учебный план и другие исходные данные представляются в виде графа, мультиграфа, гиперграфа или набора графов. Вершины графов, как правило, представляют преподавателей, учебные группы, дисциплины и аудитории, а ребра - учебные занятия. Необходимо сопоставить ребрам графа периоды времени («пары»), причем требование отсутствия накладок означает, что это сопоставление должно быть реберной раскраской графа: никаким двум ребрам, инцидентным одной вершине, не должно соответствовать одно и тот же учебное занятие.
Первая модель такого рода предложена в [69]. В ней гиперграф учебного плана и желательности проведения занятий в определенное время представлялся в виде трехмерной таблицы, а составление расписания сводилось к трехмерной задаче о назначениях (требования к дисциплинам и распределение аудиторий не рассматривалось).
Многие последующие работы использовали такое представление и его обобщения как основу для точных и эвристических методов. В [3; 61; 73] учитывалось разделение групп на подгруппы и объединение в потоки, в [57; 74] к этому же фактору добавились требования к аудиториям.
Чаще всего рассматривалось представление, в котором расписания для преподавателей и учебных групп строились как реберные раскраски двудольного мультиграфа учебного плана [55; 56]. Расписание на одно занятие оказывает 15 ся паросочетанием мультиграфа. Реберную раскраску двудольного мультигра фа с Е ребрами без дополнительных условий можно построить за 0(ElogE) операций [59], но учет других требований превращает задачу в NP-полную [10]. В [67] доказана NP-полнота задачи с запретами на некоторые «пары» для преподавателей.
Методы сетевого [8; 41; 58] и календарного планирования [48; 68] привлекаются, если необходимо проводить занятия в заданном порядке, минимизировать переходы учащихся и преподавателей в аудитории и здания. Такие методы близки к методам планирования технологических процессов и часто сводятся к NP-трудной квадратичной задаче о назначениях.
При учете наиболее трудных требований привлекаются известные общие задачи математического программирования [7; 15; 49; 63]. В [15] задача целочисленного линейного программирования формулируется для учета разделения групп на подгруппы и объединения в потоки и решается методом вектора спада. В [81] расписание строится по индивидуальным учебным планам студентов посредством решения задачи целочисленного линейного программирования методом лагранжевой релаксации. В ряде работ задача составления расписания, выраженная в терминах целочисленного линейного программирования, решается методом ветвей и границ или методом отсечений.
Теоретические и эмпирические оценки трудоемкости показали, что с помощью точных методов построить расписание на реальных данных учебного заведения часто практически невозможно. Такие методы могут справиться лишь с задачами крайне малой размерности или без учета многих необходимых требований [67]. В силу этого большинство автоматизированных систем составления расписания занятий основаны на эвристических методах. Эвристические методы генерации расписаний
Первые эвристические подходы моделировали работу человека, составляющего расписание занятий вручную. По схеме работы такие алгоритмы можно подразделить на следующие типы: - так называемые, жадные, выбирающие очередные занятия по некоторому правилу без дальнейшего их переназначения. Эти алгоритмы не могут самостоятельно выйти из тупиковой ситуации, в которой назначение очередного занятия невозможно; - алгоритмы неполного перебора с возвратом, изменяющие ранее назначенные занятия, если на каком-то шаге назначение очередного занятия невозможно; - алгоритмы, ищущие возможность назначения очередного занятия и варианты переназначения ранее спланированных занятий, конфликтующих с очередным. Если переназначение одного занятия найти не удается, некоторые методы ищут цепочки переназначений ранее спланированных занятий; - декомпозиционные эвристики, разделяющие исходную задачу на подзадачи меньшего размера и применяющие к ним другие методы или дальнейшие шаги декомпозиции.
Среди многочисленных эвристических численных методов применяющихся для автоматизированного формирования расписания занятий [54; 61; 70], наиболее распространенными являются метод моделирования отжига (simulated annealing) [62; 66; 72] и так называемые эволюционные алгоритмы (evolutionary algorithms). [37; 60]. Общим, в таких подходах, является введение критериев оптимальности и целевой функции оптимизации взамен требований к расписанию.
Многокритериальность задачи оптимизации расписания занятий
Термином «оптимизация» в литературе [4; 6] обозначают процесс или последовательность операций, позволяющих получить уточненное (наилучшее) решение. Хотя конечной целью оптимизации является отыскание наилучшего или «оптимального» решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают стремление к совершенству, которое, возможно, и не будет достигнуто.
Каждое возможное решение характеризуется определенной степенью достижения цели. В соответствии с этим формируется некое представление о достоинствах и недостатках решений, на основании которого одно решение, предпочитается другому. Оптимальное решение - это решение, которое по заданному набору признаков, предпочтительнее других возможных решений. Такие признаки часто субъективны и их математическая формализация может составить сложную задачу.
Проектные параметры (искомые переменные). Этим термином обозначают независимые переменные параметры, которые полностью и однозначно определяют решаемую задачу проектирования.
Проектные параметры - неизвестные величины, значения которых вычисляются в процессе оптимизации. В качестве проектных параметров могут служить любые основные или производные величины, служащие для количественного описания системы. Так, применительно к задаче составления расписания занятий, это могут быть значения выявленных обязательных и желательных требований к расписанию. Число проектных параметров характеризует степень сложности данной задачи проектирования. Обычно число проектных парамет ров обозначают через п, а сами проектные параметры через х с соответствующими индексами: ЛГ, Л , Х ,...,Хп
Целевая функция (критерий оптимальности) - это выражение, значение которого необходимо сделать максимальным или минимальным. Целевая функция позволяет количественно сравнить два альтернативных решения. С математической точки зрения целевая функция описывает некоторую многомерную поверхность. Ее значение определяется проектными параметрами L = L\X\,X2, ",Xn) Значение целевой функции, в многокритериальной задаче оптимизации расписания занятий, определяет качество оцениваемого расписания.
Целевая функция в ряде случаев может принимать самые неожиданные формы. Например, ее не всегда удается выразить в замкнутой математической форме, в других случаях она может представлять собой кусочно-гладкую функцию. В ряде случаев проектные параметры принимают только целые значения. Иногда проектные параметры имеют только два значения - да или нет. Качественные параметры тоже возможно учитывать в процессе оптимизации, хотя их сложно охарактеризовать количественно. Однако, в каком бы виде ни была представлена целевая функция, она должна быть однозначной функцией проектных параметров.
Поиск минимума и максимума. Одни алгоритмы оптимизации приспособлены для поиска максимума, другие - для поиска минимума. Однако независимо от типа решаемой задачи на экстремум можно пользоваться одним и тем же алгоритмом, так как задачу минимизации можно легко превратить в задачу на поиск максимума, поменяв знак целевой функции на обратный.
Множество допустимых решений - пространство решений, определяемое всеми проектными параметрами. Пространство решений не столь велико, как может показаться, поскольку оно обычно ограничено рядом условий, связанных с физической сущностью задачи. Ограничения могут быть столь силь ными, что задача не будет иметь ни одного удовлетворительного решения. Следует отметить, что очень часто в связи с ограничениями оптимальное значение целевой функции достигается на одной из границ области множества допустимых решений задачи.
Локальный оптимум. Так называется точка пространства решений, в которой целевая функция имеет наибольшее значение по сравнению с ее значениями во всех других точках ее ближайшей окрестности.
Часто пространство проектирования содержит много локальных оптиму-мов и следует соблюдать осторожность, чтобы не принять первый из них за оптимальное решение задачи.
Глобальный оптимум — это оптимальное решение для всего множества допустимых решений. Оно лучше всех других решений, соответствующих локальным оптимумам, и именно его необходимо найти. Возможен случай нескольких равных глобальных оптимумов, расположенных в разных частях пространства проектирования, то есть может существовать два и более различных расписания, имеющих экстремальное значение целевой функции оптимизации.
Разработка математической модели многокритериальной оптимизации начального расписания занятий
Дадим определение гиперграфа [52]. Гиперграф H(V, Е) задается множеством V, элементы которого называются вершинами, и семейством Е подмножеств V, называемых ребрами гиперграфа. Гиперграф можно отобразить на плоскости, сопоставляя вершинам точки плоскости, а ребрам — связные области, охватывающие вершины, инцидентные этим ребрам. Например, гиперграф Н с множеством вершин V = {vl, v2, v3, v4, v5, v6} и семейством ребер E = {el=e2={vl, v2}, e3={v2, v4, v5J, e4={v3, v4}, e5-{v5}, еб=0} можно изобразить на плоскости, как показано нарис. 2.1.
Если каждое ребро гиперграфа имеет степень, равную двум, то гиперграф является просто графом. На рис. 2.1 множественность ребер представлена ребрами ei и в2\ «петля» отображается ребром еу, v представляет собой изолированную вершину.
Построим математическую модель расписания занятий в множественно-графовой интерпретации:
Множества академических групп, подгрупп и потоков.
Для проведения аудиторных занятий в ВУЗ е контингент студентов N объединяется в учебные группы geG. Обозначим через wg количество занятий группы (согласно учебному плану) за две недели. Множество G разбивается на подмножества GK0 групп курсов и факультетов, либо на подмножества
GKC групп курсов и специальностей. Подмножества групп некоторых специальностей могут образовывать подмножества GKH групп направлений. Лекционные занятия проводятся в потоках, поэтому обозначим множество R, определяющее каждый поток и входящие в него группы г є R. В свою очередь множество потоков разбивается на подмножества потоков курсов и факультетов RK0, либо на подмножества потоков курсов и специальностей RKC.
Для проведения лабораторных занятий студенты каждой группы делятся на подгруппы d. Обозначим множество D, определяющее каждую подгруппу d є D. В некоторых случаях, подгруппы различных групп могут объединяться в подмножества подгрупп (например, практические занятия по иностранному языку), но для упрощения предложенной модели этот вариант рассматриваться не будет.
Введем гиперграф структуры групп, подгрупп и потоков Нг =(G,D,R,Er), где Ег - инцидентор, порождающий множество пар M = {(g,z)\Er(g,z),g =G,zEDvRvG}. Множество преподавателей. Пусть реР - идентификатор преподавателя. Рассчитываемая и распределяемая аудиторная нагрузка включает проведение занятий: - одной группы с одним преподавателем; - потока (многих групп) с одним преподавателем; - подгруппы с одним преподавателем (группы с несколькими преподавателями).
Введем гиперграф учебной нагрузки Нун = (М, Р, ЕУП), где Еун - инци дентор, порождающий множество пар Ьв ={(т,р)\Еун(т,р),теМ,реРи{0}}. Инцидентность между т и р оз начает, что занятие lBeLBB учебном подразделении т (группа, подгруппа или поток) проводит преподаватель p. B = {b{,b2,b3} - атрибуты lBeLB (6, идентификатор дисциплины; Ь2 - вид занятия; Ъъ - количество часов занятий за две недели). Множество аудиторий. Пусть: Алп - множество аудиторий для лекций и практических занятий; АЛАБ - множество аудиторий для лабораторных занятий; а є Алп и АЛАБ - идентификатор аудитории; I Алп +1АЛАБ - количество аудиторий в ВУЗ е.
Аудиторный фонд (номера аудиторий, вместимость, предназначение) является исходной информацией для составления расписания. Аудитории для лекционных и практических занятий выделяются из множества Алп в зависимости от их вместимости.
Гиперграф учебных поручений Нуп = (LB, Алп, АЛАБ,ЕУП), где Еуп - ин цидентор, порождающий множество пар V = {{1В,а) Еун(lB,a),lBeLB,ae Алп и АЛАБ и {0}}. Инцидентность между 1В и а означает, что учебное поручение v є V для занятия 1В содержит требуемую аудиторию а или «пустую» аудиторию (например, для занятий физической культурой). Множество таймслотов. Занятия проводятся в рабочие дни в полуторачасовые интервалы, которые будем называть «парами». Обозначим: td є Тд- идентификатор рабочего дня недели; tn єТп - идентификатор «пары»; Тч ={t\,tl} - множество идентификаторов четности недели. Введем множество таймслотов Т = ТдХ.ТпхТч, элементы которого однозначно определяют четность, день недели и номер «пары».
Анализ работы алгоритма оптимизации
В качестве исходных данных для работы алгоритма используются начальные варианты расписания, нуждающиеся в оптимизации. Начальные расписания формировались для двух шестидневных учебных недель одного из семестров учебного года для групп пяти курсов факультета, на котором обучаются студенты пяти специальностей. Для всех пятидесяти групп факультета недельная аудиторная нагрузка составляет 27 часов, из которых 14 - лекции, 5 и 8 соответственно лабораторные и практические занятия, проводимые преподавателями различных кафедр. При этом возможны три варианта занятий: - одна группа - один преподаватель; - несколько групп - один преподаватель; - одна группа - несколько преподавателей.
Для предложенных начальных расписаний изменялось только количество аудиторий для лекционных и практических занятий. Этот фактор сказывался на сложности начального расписания. Меньшее количество аудиторий увеличивало значения критериев оптимальности. Вычисление нормированной функции частных показателей качества (2.11) выбранных критериев К\, К2 и Кз для всех начальных расписаний производилась следующим образом.
Для критерия К\ (минимизация количества занятий для заданного номера «пары» ҐпєТп) параметром t n была четвертая «пара» расписания занятий. Следовательно, максимальное значение этого критерия для занятия группы будет равным 1, если в таймслоте t „ = 4 есть занятие и 0 - если занятия нет. Текущее значение критерия для выбранного занятия К вычислялось так: Г 1, если в таймслоте есть занятие на четвертой «паре» К, = -і [ 0, в противном случае При вычислении значений критерия Кг (равномерность распределения занятий учебных групп по количеству «пар» в день для обеих недель) для занятий начального расписания необходимо установить оптимальное количество занятий группы в день yeY . В предложенном начальном расписании число занятий каждой группы за обе недели расписания \S\ = 27, количество рабочих дней недели Тд = 6, а количество недель расписания \ТЧ \ = 2. Оптимальное ко личество занятий группы в день будет содержать два значения: — Mod6 0 27 ух = — Div 6 = 2и у2=У\+1 = 3 Y = {2,3}. Для этого критерия К1" принимается равным 0. Так как рассматриваемые начальные расписания не имеют занятий позже четвертой «пары», то ГЯ = 4, тогда количество всех таймслотов в расписании группы \т\ = 4x6x2 = 48. Исходя из этого, рассчитаем максимальное значение крите рИЯ Л 2 Крх = шах{4 - 3,2 - тах{0,27 + 4 - 48} } = 2. Текущее значение критерия К для выбранного занятия вычисляется исходя из количество «пар» х в дне недели этого занятия: К 2=\ О, если 3yeYx = y; х-3, если х 3; 2-х, если х 2. Для расчета значений критерия Кз (равномерность занятий учебных групп для различных недель) необходимо знать оптимальное количество занятий группы на одной неделе расписания у є Y . Это значение вычисляется делением общего количества занятий группы на количество недель расписания: 27Mod2 0 = yl=27Div2 = \3uy2 = yl+l = \4 = Y = {13,14}. Для этого критерия Кт также принимается равным 0. Максимальное значение критерия Ках рассчитывается следующим образом: до ДО К?ах = max{min{—,27} -14,13 - тах{0,27 }} = 10. Текущее значение критерия К% для выбранного занятия вычисляется исходя из количество «пар» х недели этого занятия: J4 0, если Зу є Y х = у; х 14, если х \4; 13-х, если х 13.
В созданной компьютерной программе оптимизации расписания занятий, при вычислении нормированной функции частных показателей качества (2.11) критерия Кз, значения получали только те занятия, для которых количество занятий группы на текущей недели было больше 14. Это допущение было введено с учетом особенностей рассматриваемых начальных расписаний, и не всегда применимо к другим.
В серии оптимизаций использовались различные варианты начального расписания, в которых количество аудиторий для лекционных и практических занятий изменялось. В табл. 3.1 представлены значения критериев оптимальности для различных вариантов начального расписания.
Занятия начального расписания для 28 лекционных и практических аудиторий выделены цветом (рис. 3.1). В каждом столбце отображены занятия одной группы, в каждой строке - занятия групп в одном таймслоте. Все занятия расписания представлены 30 блоками. Каждый блок занятий представляет заня тая групп одного курса в один учебный день. Часть этого расписания, но в обычной текстовой форме, представлена в приложении 7.
Лекционные занятия проводятся в потоках. Поэтому перестановка занятия отдельной группы потока недопустимо, то есть перестановка занятий потока осуществляется для всех занятий групп входящих в поток. Если занятие группы 5 , входящей в поток г, не оптимально по і-му критерию, то значение /-го критерия делится поровну на все занятия групп, входящих в поток г . При использовании такого подхода, в масштабе расписания группы s" є г , занятий требующих оптимизации может и не быть, но в масштабе всего расписания занятие s будет так же неоптимально как и s .
На рис. 3.2 показан результат оптимизации начального расписания (рис. 3.1). Из рисунков видно, что после оптимизации количество неоптимальных занятий существенно сократилось.
Выделим из начального расписания (рис. 3.1) группы пятой специальности (ГрупЮ, Груп20, ГрупЗО, Груп40, Груп50). Расписание этих групп представлено в табл. 3.2. Таймслоты занятий групп содержат обозначение дисциплины, преподавателя, вида занятия, а также номер аудитории.
