Содержание к диссертации
Введение
1. Общая постановка задачи составления оптимального учебного расписания для школ 4
1.1. Обзор существующих систем автоматизированного составления учебного расписания и классификация задач учебного расписания 4
1.2. Содержательная постановка задачи составления оптимального учебного расписания для школ с учетом предпочтений 23
1.3. Концептуальная постановка задачи составления оптимального учебного расписания для школ с учетом нечетких предпочтений 32
2. Математическая постановка задачи составления оптимального учебного расписания с учетом нечетких предпочтений 44
2.1. Декомпозиция задачи и выбор параметров оптимизации 44
2.2. Ограничения в задаче оптимального учебного расписания для школ ... 50
2.3. Построение обобщенных критериев оптимальности 53
2.4. Математическая постановка задачи многокритериальной оптимизации учебного расписания школы с учетом нечетких предпочтений 64
3. Гибридный алгоритм решения задачи составления оптимального учебного расписания 67
3.1. Обзор и классификация методов составления учебного расписания 67
3.2. Алгоритм получения допустимых расписаний в задаче составления оптимального учебного расписания с учетом нечетких предпочтений 79
3.3. Алгоритм многокритериальной оптимизации учебного расписания для школ с учетом нечетких предпочтений 87
4. Реализация алгоритма в виде модуля информационной системы и решение тестовых задач 101
4.1. Модуль «Расписание» и его использование для составления оптимального учебного расписания с учетом нечетких предпочтений 101
4.2. Эвристические алгоритмы ослабления ограничений в модуле «Расписание» информационной системы «Школа» 108
4.3. Сходимость к решению исходной задачи и устойчивость численных схем эвристических алгоритмов модуля «Расписание» 113
4.4. Решение задачи составления оптимального учебного расписания школы с учетом нечетких предпочтений на примере МОУ «Лицей №1» 120
5. Основные результаты и выводы 133
6. Список литературы 135
Приложение
- Содержательная постановка задачи составления оптимального учебного расписания для школ с учетом предпочтений
- Ограничения в задаче оптимального учебного расписания для школ
- Алгоритм получения допустимых расписаний в задаче составления оптимального учебного расписания с учетом нечетких предпочтений
- Эвристические алгоритмы ослабления ограничений в модуле «Расписание» информационной системы «Школа»
Введение к работе
В данной работе рассматривается задача составления учебного расписания. Учебное расписание является частью учебного процесса и определяет то, каким образом учебное заведение работает весь год (или четверть, или семестр). Составление учебного расписания - это частная форма задачи календарного планирования[23]. В наиболее общем случае есть набор объектов (ресурсов) и набор процессов, которые должны быть совершены для каждого объекта (операции или работы в терминах теории календарного планирования[17]). Например, деталь на заводе может проходить несколько операций согласно технологического маршрута: сверления, шлифования и т.д. В образовательной среде каждый учащийся (студент) должен пройти в точности столько занятий или лекций в неделю, сколько положено по учебному плану. В данном случае студент является объектом, а уроки - процессами. Следует отметить, что при совершении технологических операций над деталями жестко задана последовательность операций, для студента же порядок занятий может варьироваться (хотя ограничения на порядок расстановки занятий также существуют). Например, есть ограничения на порядок проведения определенных предметов, таких как физкультура и физика.
Расписание - это описание движения и группировки ресурсов по времени, часто преследующее достижение некоторой цели или целей и/или удовлетворяющее набору ограничений[28].
Ресурсы могут охватывать некоторое количество объектов, которые могут быть сгруппированы по типу или по иному признаку (например, типом ресурса в школьном расписании может быть класс). Точно так же существуют человеческие ресурсы (учителя) и материальные ресурсы (проекторы, аудитории и т.д.). Предметом данной работы является учебное расписание. Задача составления расписания заключается в следующем: имеются учебные группы, каждая из которых занимается по своему учебному плану. Расписание, как функциональный аналог учебного плана, предназначено для установления порядка реализации учебных планов учебных групп. Расписание устанавливает порядок проведения занятий по времени (ограниченный набор занятий в ограниченное количество периодов времени). Составление расписания, таким образом, заключается в распределении занятий из учебных планов учебных групп по времени. При составлении учебного расписания важно выполнить поставленные цели и не выйти за рамки набора связанных с задачей ограничений, специфичных для каждого образовательного учреждения. Каждый частный случай общей задачи календарного планирования имеет свой собственный набор терминов, правил и требований. Чаще всего задачи так сильно различаются, что их очень трудно классифицировать, поэтому используется условное деление задач учебного расписания на следующие группы задач [22]: задачи составления школьного учебного расписания; задачи составления расписания университета (так называются задачи составления расписания для студентов, которые выбирают часть курсов для собственного обучения. Учитывая специфику обучения в российских университетах, эту задачу можно назвать задачей составления расписания факультативов); задачи составления расписания экзаменов; задачи академического расписания. Сложностей при составлении расписания очень много. Метод решения, эффективный для одной задачи, может быть неэффективным для другой [30]. Реальные задачи отличаются большой размерностью вектора неизвестных. Количество занятий, которые требуется расставить в сетку расписания, формируемую из ограниченного набора периодов времени, может колебаться от пятисот для небольшой школы до трех тысяч для большого университета[27]. Известно, что задачи с большим числом ограничений являются очень сложными для решения вручную, поэтому в ВУЗах расписанием обычно занимаются диспетчерские службы (бюро расписаний), которые ведут деятельность по составлению и модификации расписания непрерывно в течение рабочей недели. Составлением расписания в школе обычно занимается отдельный диспетчер или завуч, выполняющий обязанности диспетчера. Процесс составления расписания длится от нескольких недель (для школ) до нескольких месяцев (для крупного ВУЗа). Кроме этого, к обязанностям диспетчера или диспетчерской службы относится составление расписания «замен», то есть внесение корректив в действующее расписание в случае ремонта аудиторий, временной нетрудоспособности преподавателей и иных причин. Следует отметить, что на период 2001-2010 года правительством РФ принята Концепция модернизации российского образования, главной целью которой является обеспечение современного качества образования. Согласно принятой Концепции в сфере образования проводятся изменения, усложняющие учебный распорядок образовательных учреждений и устанавливающие более жесткие требования к расписанию. Расписание должно учитывать большее количество ограничений различного вида, что связано с введением системы профильного обучения, учитывающей потребности рынка труда и цели заказчиков, планируемой оптимизацией учебной, психологической и физической нагрузки учащихся, внедрением интегрированных программ обучения. В частности, это выражается в потребности учитывать действующие нормы СаНПИН [10], деление учебных групп на подгруппы по профилю (в школе), наличие преподавателей-совместителей (преподающих профильные предметы в школе и имеющие основное место работы в ВУЗе). При составлении расписания диспетчеру необходимо учитывать дидактические требования по организации учебного процесса, указания администрации по распределению аудиторного фонда (и иных ресурсов, необходимых для реализации учебного процесса), а также личные пожелания преподавателей и учебных групп к составлению расписания. Помимо этого, специфика конкретного образовательного учреждения отражается в задаче составления расписания в виде специфичных целей и ограничений. В результате всего вышеизложенного, задача составления расписания становится очень сложной для решения вручную. В настоящее время при актуальности вопроса качества образовательных услуг и требований экономии ресурсов на практике востребовано не только составление некоторого «чернового» варианта расписания, но и получение оптимального (с точки зрения введенных критериев и имеющихся ограничений) либо близкого к оптимальному (по некоторой мере) расписания. И если составление расписания вручную является трудной и затратной по времени задачей, то решение задачи оптимизации учебного расписания вручную практически не реализуемо по следующим причинам:
- при составлении расписания вручную возможности перебора вариантов ограничены, а размерность вектора неизвестных в задаче велика;
- как указано в [50], даже опытный диспетчер единовременно не способен оценивать расписание более чем по 12 критериям, хотя в реальных задачах может быть востребован учет до 40 и более различных критериев оптимальности;
- в работе [24] отмечено, что реальные задачи составления расписания являются перегруженными ограничениями, поэтому диспетчер «отбрасывает» некоторые ограничения в ходе решения задачи, полагаясь на свой опыт и предпочтения, поэтому может действовать субъективно;
- для проверки оптимальности либо суб-оптимальности полученного расписания диспетчер не имеет никакого формального аппарата либо инструмента для исследования множества решений задачи;
согласно данным из работы [35], до 20% ограничений в задаче составления учебного расписания могут меняться ежегодно, и приемы, использованные диспетчером для улучшения расписания в этом году, могут быть неэффективными для улучшения решений изменившейся задачи.
Поэтому разработка системы составления оптимального учебного расписания является актуальной задачей и требует применения методов математического моделирования и современных информационных технологий.
Существующие средства автоматизации составления учебного расписания могут использоваться для решения задач в трех режимах: ручном, автоматическом и интерактивном [45]. В первом режиме компьютер лишь хранит данные, требуемые для составления расписания (обычно в виде некоторой базы данных), и контролирует действия диспетчера, не давая ему совершить ошибки с наложением занятий одного преподавателя по времени при размещении занятий в часовую сетку, показывает некоторую статистику (сколько свободных ячеек в сетке расписания имеется, какова загрузка преподавателей и аудиторий, учебных групп), что позволяет диспетчеру лучше ориентироваться в процессе решения задачи. Кроме этого, некоторые разработки имеют так называемый эвристический модуль, который способен подсказывать диспетчеру, куда желательно расставить занятие, исходя из некоторого набора правил (например, требования равномерной загрузки аудиторий). Следуя определению, приведенному в [11], под эвристикой далее будем понимать некоторую эвристическую меру и алгоритм поиска решения. В целом применение эвристик позволяет сузить пространство возможных вариантов, что основывается на некоторых рациональных суждениях из опыта диспетчера, позволяющих отбирать из всего множества вариантов наиболее «перспективные», и искать решение только среди них. Однако, следует отметить, что такие эвристики лишь ограниченно пригодны для построения универсального решателя существующих задач, так как каждый диспетчер использует свои приемы решения задачи [15]. Во втором режиме (автоматическом) пользователю предлагают задать исходные данные, после чего автоматически составляется расписание и пользователю выдается готовый результат, на чем процедура решения заканчивается. В интерактивном режиме сочетаются ручной и автоматический режимы, которые обычно повторяются циклически, то есть за этапом автоматического составления расписания следует этап его изменения вручную и изменения условий задачи, а затем повторяется этап автоматического решения. В теории принятия решений [49] и работе по человеко-машинному интерфейсу [46] наличие интерактивного режима рассматривается как желательный элемент при построении систем с участием экспертов. Так как задачу составления расписания сложно решить вручную, то практически обязательным элементом решателя должен являться автоматический режим составления расписания. Помимо этого, как следует из устных просьб диспетчеров и из имеющихся технических заданий на систему составления учебного расписания, для внесения оперативных изменений в расписание и возможности менять расписание должен присутствовать режим составления расписания вручную. Таким образом, решатель задач составления учебного расписания, должен быть по возможности универсальным, и поэтому должен включать в себя все три режима составления расписаний.
Учет специфики задачи составления расписания в конкретном образовательном учреждении в рассматриваемых системах автоматизации обычно заключаются в возможности использования встроенного набора критериев оптимальности и ограничений, учитываемых различным способом. Возможности построения произвольного критерия оптимальности автору не встречалось ни в одной из разработок среди большинства коммерчески предлагаемых учебным заведениям (см. приложение 1). Набор учитываемых критериев оптимальности часто фиксирован и добавление произвольных критериев не предусматривается. В качестве средства настройки иногда возможно изменение весовых коэффициентов для критериев из имеющегося набора [13]. Учитывать ограничения произвольного вида также не позволяет ни одна из описанных разработок. Ограничения, которые требуется учитывать при составлении ученых расписаний - это деление учебных групп на подгруппы, выполнение требований САНПИН (в состав которых, например, входит требование соблюдения баланса учебной нагрузки, рассчитываемой с помощью специальной таблицы баллов сложности учебных дисциплин), учет вместимости аудиторий, учет личных предпочтений преподавателей и учебных групп и другие. По способу учета ограничений возможен жесткий учет ограничений, нежесткий учет, либо учет ограничения по критерию оптимальности. Произвольное ограничение, учитываемое жестко, должно обязательно выполняться в полученном расписании. При составлении расписания обязательно должны выполняться условия совместности по времени для учащихся, преподавателей, аудиторий и иных задействованных в учебном процессе ресурсов. Кроме этого, существуют жесткие ограничения на количество ресурсов и требование точного соблюдения учебного плана. Расписание, которое удовлетворяет жестким ограничениям, назовем допустимым. Нежесткий способ учета ограничений подразумевает, что в полученном после окончания расчетов расписании ограничения могут выполняться не полностью, то есть частично нарушаться. Мера возможного нарушения ограничений может задаваться различным способом: в виде допустимого интервала[53], в виде некоторого списка допустимых значений[41], упорядоченных по степени предпочтения и т.д. Последним вариантом учета ограничений из перечисленных является преобразование существующего ограничения, например, с помощью штрафной функции, в критерий оптимальности, и поиска расписания, где данное ограничение выполняется наилучшим образом.
Несмотря на большой выбор систем составления расписания и способов учета ограничений в них, на практике нередкой является ситуация, когда выбранная система не имеет возможности учесть конкретное ограничение, важное в текущем состоянии при составлении расписания в образовательном учреждении.
При выборе средств автоматизации учебного расписания следует также учитывать размерность реальной задачи составления расписания, которая может быть весьма велика даже для небольшого учебного заведения, например, в случае деления учебных групп на подгруппы. Часть имеющихся разработок по составлению расписания в силу используемого алгоритма имеют ограничения на размерность решаемой задачи, и поэтому могут оказаться непригодными. Большинство реальных задач составления учебного расписания, кроме этого, являются П?-трудными[54]. Для подобных задач, согласно теории сложности [3], не существует алгоритма с полиномиальной оценкой сложности, а число вариантов для перебора растет экспоненциально с ростом длины вектора неизвестных. Одним из используемых подходов, применяемых для решения таких задач, является декомпозиция. Учитывая также большую размерность (до 3000 отдельных занятий) этих задач, для их решения могут быть непригодны системы автоматизированного составления расписаний, не имеющие возможности декомпозиции всей задачи на подзадачи[21]. Если же такая возможность присутствует, то задача составления расписания обычно решается как последовательность связанных подзадач[31].
Диспетчеры выдвигают к системе составления учебного расписания требование получения так называемого «расписания замен». Фактически это возможность изменения учебного расписания согласно меняющимся условиям внешней среды. Поэтому задачу составления расписания можно считать динамически изменяющейся со временем. На динамический характер реальных задач указывают также автор работы [18]. Поэтому важным свойством систем составления учебного расписания является возможность коррекции расписания в случае изменения некоторых ограничений, причем изменения в расписании должны быть сведены к минимуму, что определено спецификой учебного процесса..
Реальные задачи составления учебного расписания являются многокритериальными [39]. Кроме этого, как отмечено в работе [50], между частными критериями оптимальности могут быть некоторые зависимости. Например, критерии могут быть поддерживающими или конфликтующими. Поддерживающие критерии таковы, что увеличение значения одного критерия оптимальности в решении ведет к росту значения связанного с ним другого критерия. Для конфликтующих критериев рост значения одного критерия связан с уменьшением значения другого критерия. Упущение из рассмотрения подобных зависимостей может привести к невозможности нахождения оптимального решения с помощью автоматизированного средства составления расписания.
Помимо этого, данные в реальных задачах таковы, что все ограничения точно практически никогда не бывают известными. Это связано, с тем, например, что предпочтения преподавателей точно не формулируются. Если педагог желает проводить занятия во вторник и четверг в первую половину дня, а время проводимых им занятий приходится на начало второй половины дня, то трудно заранее оценить степень, с которой данное расписание устраивает либо не устраивает этого преподавателя. В работе [41] отмечено, что учет предпочтений преподавателей необходим для получения действующих расписаний, а в работе [55] приводится утверждение, что личные пожелания преподавателей всегда противоречат друг другу, и поэтому полный учет пожеланий даже пяти педагогов может сделать задачу составления расписания неразрешимой. На практике диспетчер, составляющий расписание, старается учесть наиболее важные, по его мнению, пожелания преподавателей, а остальные личные предпочтения отбрасывает. При этом диспетчер может договариваться с конкретным педагогом и выяснять, какие из возможных вариантов расстановки занятий устраивают педагога. Таким образом, требованием к автоматизированным системам составления расписаний является учет личных предпочтений учащихся и преподавателей. Но данные о предпочтениях преподавателей всегда известны с некоторой неопределенностью, на что также ссылаются авторы работ [41,55] . Размерность реальных задач и объем информации для составления расписания велики, поэтому для сбора и хранения информации обычно используются специальные базы данных [7]. Одной из связанных с этим проблем являются наличие ошибок при вводе данных. Как указано в работе [55], подобные ошибки трудно искать и устранять. При этом, если вся информация задается точно, то наличие даже одной ошибки может вести к невозможности нахождения решения. Подобное поведение автоматизированных систем составления расписания отмечено в работах [40,44]. Одним из выходов из этой ситуации является тщательная многократная верификация используемых данных [1], что увеличивает затраты, связанные с использование автоматизированной системы, и способно привести к отказу от ее применения по этой причине. Другим выходом является признание существования ошибок в исходных данных и учет данных как заданных неточно, с некоторой неопределенностью. Как отмечено в работах [1,55], в этом случае средство автоматизации составления расписания будет устойчивым к незначительным изменениям исходных данных задачи. Поэтому в автоматизированных системах составления учебного расписания следует учитывать возможные неточности в собираемых данных и ошибки при переносе информации на машинный носитель.
Из опыта использования автоматизированных систем составления расписания известна эффективность применения различных подходов с обучением (нейронных сетей [51], экспертных систем, обучением на базе случаев [29]). Применение подобных подходов способно улучшить характеристики получаемых решений.
Рассмотрим существующие системы автоматизированного составления учебного расписания с учетом перечисленных выше требований. Часть из существующих разработок не имеет автоматического режима, и предусматривает только ручной режим составления расписания - например, «Хронограф 2.0», «АССР», «Директор школы» , «Расписание 1.1» (г. Уфа), «Подготовка расписаний для Windows 95», «СПОРА», «Расписание+» (г. Абакан). Другая часть разработок не предусматривает использования каких-либо критериев оптимальности, то есть возможности подобных систем составления учебного расписания ограничены получением только допустимого расписания - например, «Расписание ПРО 2.3» (фирма «DigSee Ltd», г. Киев), «Методист 1.4.» (фирма «Инфоресурс»), «Расписание -замены 2001» (автор Горбунов А.И.), «Расписание 4.0.» («Линтех» г.Москва), «Sweet School», «Расписание 2000» (автор Н. Цигуро), «Мечта» (автор Клюев В.А., г. Санкт-Петербург). Наличие автоматического режима составления расписания у перечисленных программ позволяет получать некоторый «черновой» вариант учебного расписания и возможность его ручного улучшения, «доводки вручную», как это называют диспетчеры. Невозможность учитывать какие-либо критерии оптимальности, напротив, снижает ценность практического использования этих систем. Диспетчеры, использовавшие некоторые из перечисленных разработок, отмечают, что составленное программой расписание часто является неприемлемым, а исправление такого расписания по сложности сравнимо с составлением расписания вручную. Поэтому возможен отказ диспетчера от использования таких автоматизированных систем в пользу ручного способа составления расписания, что часто случается на практике. Тот же результат может быть вызван невозможностью учета какого-либо ограничения, важного для диспетчера в контексте решаемой им задачи.
В системе составления учебных расписаний «АВТОР-2+» (автор Губенко, г. Ростов-на-Дону) существует возможность учета двух критериев оптимальности - минимизации числа «окон» в расписании («окном» диспетчеры считают перерыв длиной в одно занятие в течение дня в расписании преподавателя) и некоторой функции, отвечающей за равномерность распределения учебной нагрузки в расписании. Имеется возможность анализа системы исходных данных. Принят следующий порядок решения задачи: автоматически составляется допустимое расписание, а если оно не составляется, то в интерактивном режиме имеется возможность устранения ошибок, выявленных блоком анализа исходных данных, либо возможность работы в ручном режиме. Автоматическое ослабление ограничений отсутствует.
В разработке «АРМ Администратора школы» критерии оптимальности явно не учитываются, а отсутствие «окон» в расписании задано как ограничение. С одной стороны, расписания, получаемые в результате работы с этой системой, должны обладать отсутствием «окон» как таковых. С другой стороны, в расписаниях, действующих в образовательных учреждениях, «окна» обязательно есть, поэтому такое ограничение на практике является слишком жестким. Также в данной разработке указано на программное определение методических дней преподавателей, то есть в алгоритм заложена некая эвристика, способная оценивать возможность выделения свободного от занятий методического дня для преподавателя. Как известно[], применение эвристик эффективно, если эвристика соответствует решаемой задаче. Ясно, что применение конкретной эвристики (без возможности каких-либо настроек на конкретную задачу) не может быть признано универсальным. Также указано, что применяемый алгоритм ограничен в размерности решаемых задач.
Программа «Ректор 3.8.» (фирма «OptimeSoft») обеспечивает поиск только допустимых расписаний (оптимизации нет), при этом указывается на возможность уменьшения числа «окон» в расписании преподавателей. Во всех режимах работы - ручном, автоматическом и интерактивном -отслеживается допустимость расписания.
В информационной системе «Расписание занятий» (автор А.Сердцев) предлагается автоматическая расстановка 85-100% занятий, а далее ручная доводка пользователем. Критериев оптимальности нет, но указано на возможность учета равномерности распределения учебной нагрузки по дням с помощью встроенной эвристики. Применение данной разработки ограничено тем, что при составлении учебного расписания не учитываются личные предпочтения преподавателей. » Авторы программы «Ника» при построении решателя учли следующую особенность: диспетчер не может долго ждать решения, получаемого в результате работы программы оптимизации, так как часто что-либо в полученном расписании диспетчера не устраивает и задачу приходится решать вновь, ожидая получения нового решения. Предлагаемый авторами подход заключается в том, что решатель строится только с использованием так называемых методов распространения ограничений [47], которые не дают возможностей оптимизации, но позволяют получать допустимые решения, которые выступают черновыми вариантами расписания. Диспетчер при этом должен решить, что в получаемом варианте решения его не устраивает, и попытаться в соответствии с этим ослабить некоторые ограничения. Преимуществом данного подхода представляется заложенная интерактивность и возможность оценки диспетчером получаемых решений. Однако данный подход имеет и свои недостатки. Главный из них заключается в том, что диспетчер является человеком, и его возможности по анализу вариантов расписания ограничены (эксперт просто может устать). В работе [45] указывается, что системы поддержки принятия решений не должны полностью полагаться на эксперта (иначе не понятно, зачем такая система нужна) и не приводить к сильной умственной перегрузке человека. Данный подход можно считать адекватным, если задача составления расписания достаточно проста, имеет небольшое число ограничений и малую размерность. Однако на практике задача обычно имеет противоположные свойства, поэтому качество составления расписания будет зависеть только от возможностей диспетчера. Кроме того, так как применяются методы распространения ограничений, то говорить о получении некоторого оптимального варианта не приходится. В целом, предложенное средство хорошо для предварительного анализа ограничений в задаче. Однако » ослаблять ограничения диспетчер должен вручную, а при их большом количестве не известно, какое ограничение в конкретной ситуации потребуется ослабить. » В системе редактирования расписаний «Хронограф 2.0» (фирма «Хронобус») реализованы средства поддержки процесса составления расписания, включая расчет нагрузки, различные способы представления информации в процессе составления расписания, но не предполагается автоматического составления оптимального расписания. Из интеллектуальных средств расстановки занятий в систему включено средство подсказки диспетчеру оптимального времени расстановки текущего занятия (с точки зрения некоторых характеристик - например, загрузки аудиторий, или свободного времени преподавателя).
Более совершенной версией редактора расписаний является «Хронограф 3.0. Мастер», причем указано, что введенные ограничения учитываются в ходе построения допустимого решения, а оптимизация не предусмотрена.
Разработка фирмы «5 профессиональный менеджмент» под названием «5Рт: расписание» - адаптированная к условиям задачи составления расписания для школ система решения задач календарного планирования. Для получения решения применяется генетический алгоритм. В работе [36] отмечено, что возможности генетических алгоритмов по составлению учебного расписания очень сильно зависят от выбора оператора кроссинговера (мутации) и применяющихся для селекции решений методик. Поэтому, хотя данный подход является гибким и предоставляет возможность решения любых задач оптимизации, при большой размерности задачи решение может быть найдено очень поздно, так как нет строгих гарантий сходимости результатов работы генетического алгоритма к решению задачи, на что указывают авторы работы [51]. Кроме этого, в работе [37] показано, что с помощью так называемого меметического алгоритма (гибрида генетического алгоритма и алгоритмов локального поиска) может быть • получено решение лучшее, чем с помощью большинства известных генетических алгоритмов. Кроме этого, данная разработка не имеет поддержки ограничений, связанных с требованиями САНПиН [10]. То есть, хотя некоторая возможность задавать критерии оптимизации есть, возможности задавать произвольные ограничения в задаче отсутствует.
Программа «АСТРА» - одна из наиболее современных разработок для составления школьного расписания. В программу заложено 6 критериев оптимальности расписания: равномерность распределения нагрузки классов, преподавателей, смешанной нагрузки, минимального количества уроков/пар в классах, обеспечение разброса занятий по одному предмету, обеспечение требований СЭС. Для каждого из критериев задается приоритет от 0 до 6. Режим разброса занятий делится на частные требования, которые могут учитываться жестко, мягко или по критерию оптимальности. Поиск производится алгоритмом перебора с возвратом при ограниченной глубине перебора, которая может задаваться. В таком случае очень большую роль играют заложенные в алгоритм эвристики, и если они не соответствуют решаемой задаче, то возможно, что решение, если оно существует, будет найдено при переборе в последнюю очередь, либо, так как глубина перебора ограничивается алгоритмом, не найдено никогда. Возможности использовать при поиске решений специфичные для конкретной задачи эвристики не предусматривается. Ослаблять ограничения диспетчер также должен вручную, хотя для помощи эксперту в программу встроен блок анализа. К недостаткам программы «АСТРА» можно также отнести то, что расширить набор критериев и ограничений нельзя, и по этой причине программа может оказаться непригодной для решения конкретной задачи. К тому же, в работе [35] отмечено, что до 20% ограничений задачи составления учебного расписания ежегодно меняются.
Система «Пенал» (фирма «Трисстар», г.Минск) позволяет составлять только допустимое расписание, не имеет возможностей оптимизации. При этом используемая для расстановки занятий эвристика может настраиваться под конкретную задачу с помощью весовых коэффициентов для каждого преподавателя по следующим признакам: соблюдению последовательности занятий при проведении занятий в параллелях учебных групп, числу «окон»,
• равномерности нагрузки в расписании преподавателя и учета его пожеланий. Недостатком данной разработки является ограничение на размер решаемых задач. Данная система ориентирована на использование операционной системы DOS, которая большинством пользователей считается сейчас морально устаревшей. Кроме этого, «Пенал» был разработан в 1991 году и не учитывает современных требований САНПИН 2003 года.
Система «АСПРУЗ 8.0.» (фирма «Incotus») рассчитана на составление расписаний в ВУЗе, предполагает большую размерность задачи и учитывает специфику ВУЗа с несколькими корпусами. Система предлагает возможности оптимизации по шести критериям. Есть функция «постоптимизации», пытающаяся устранить «окна» в полученном расписании. Дополнительными опциями оптимизации являются возможность уменьшения числа переходов между корпусами и максимизация пропускной способности аудиторий. Имеются статистические оценки получаемого расписания, например, коэффициент загрузки аудиторий. Преимуществом данной системы является соответствие выходных форм стандартным, применяемым в учебном процессе ВУЗов. Недостатком является отсутствие возможности учета личных предпочтений преподавателей., невозможность задания произвольного критерия оптимальности и необходимость ослабления ограничений вручную.
Таким образом, возможностей построения произвольного набора критериев и ограничений нет ни в одной разработке из рассмотренных. Хотя в работе [24] отмечено, что применение автоматического ослабления ограничений эффективно в ситуации, когда допустимое расписание не составляется, таких возможностей не предусматривает ни одно автоматизированное средство составления учебных расписаний. Кроме этого, практически во всех системах составления расписаний данные задаются четко, то есть не учитывается возможная неточность исходной информации и наличие ошибок при вводе данных. В современных работах, посвященных составлению учебного расписания, также отмечается эффективность построения гибридных алгоритмов решения[26], параллельных вычислительных алгоритмов [12], алгоритмов кооперативного поиска[25], возможностей накопления знаний о конкретной задаче и их использования в ходе решения [29]. Однако в большинстве существующих разработок перечисленные особенности не учитываются. Не рассматривается и возможность использования одного из ранее действующих расписаний, например, прошлогоднего, в качестве начального приближения для составления нового расписания, хотя диспетчеры пользуются этим. Отмеченные недостатки существующих систем составления учебного расписания показывают их ограниченную пригодность для решения реальных задач. Кроме устранения недостатков существующих систем, при построении автоматизированной системы составления учебного расписания важно учитывать современные требования к системам составления расписания, к которым, как указано в обзоре [25], можно отнести следующие: 1. Требуются алгоритмы, стабильно работающие на классе задач, а не на одной конкретной задаче.
2. Востребован анализ критериев оптимальности, связанных с выбором того или иного варианта расписания, необходимо обоснование применения многокритериальных постановок и методов решения. С практической точки зрения интересно исследование связей между критериями и учет этих связей в алгоритмах решения.
3. Требуется исследовать аспекты задач, связанные с многокритериальностью - например, варианты агрегирования частных критериев оптимальности и получения качественных компромиссных решений.
4. В алгоритмах с применением гипер-эвристик (под гипер-эвристикой будем понимать эвристику более высокого уровня, управляющая выбором обычных эвристик) требуются экспериментальные исследования поведения подобных алгоритмов.
5. В алгоритмах решения требуется исследование влияния добавления различных ограничений в процессе решения, а также связи ограничений с пространством поиска. Важно изучение вариантов лучшей формулировки критериев оптимальности для повышения эффективности алгоритмов решения.
6. Требуется разработка средств, повышающих эффективность работы известных алгоритмов и их настройка на конкретную задачу
7. Востребованы исследования метрик и индикаторов состояния поиска в задаче, оценки верхних и нижних границ значения оптимального решения в задаче расписания, конструирование гипер-эвристик.
8. Важно исследовать эффективность применения методов обучения и совершенствовать существующие методы. Например, в методе обучения по базе случаев [29] до настоящего времени не обоснован выбор признаков для составления базы случаев.
9. Требуется более полное изучение процессов интерактивного взаимодействия диспетчера с компьютером и методов решения задач с изменением ограничений в ходе решения задачи.
Таким образом, актуальной задачей является построение автоматизированной системы составления учебного расписания с учетом недостатков существующих систем составления учебного расписания и перечисленных современных требований.
Следует отметить, что теоретическая сложность задач и их большая размерность, различия в условиях учебного процесса в образовательных учреждениях не позволяют решить задачу составления оптимального учебного расписания. В общем случае, если учесть, что фактически каждая существующая задача составления учебного расписания является уникальной по набору и структуре ограничений задачи, по критериям оптимальности, то становится понятным, что существующие задачи составления расписания сложно уложить в рамки единого программного продукта. Для получения приемлемого результата, как показывает практический опыт, необходима разработка системы составления расписания для конкретного образовательного учреждения, что достаточно трудоемко. Если образовательное учреждение не способно нести издержки по разработке, внедрению и сопровождению данной системы в полном объеме, то выходом из сложившейся ситуации может служить быстрая и экономически приемлемая технологии создания подобной системы. Например, для школ эта технология может быть представлена в виде методики построения системы автоматизированного составления расписания. Одним из вариантов ее реализации представляется некоторый «конструктор», позволяющий «собирать» из готовых элементов систему автоматизированного составления расписания и разрабатывать несуществующие элементы. Реализация методики в такой форме дает возможность в полной мере учесть специфику конкретной задачи составления расписания, снизить стоимость разработки системы составления расписания и превратить этот процесс из творческого неформализованного процесса в некий производственный график, позволяющий создавать такую систему за обозримое время. Кроме этого, такой подход позволяет на этапе создания системы заложить допущения и гипотезы, важные для решения данной конкретной задачи, и, таким образом, учесть экспертные знания уже на этапе постановки задачи. Подобных методик в литературе автору не встречалось, поэтому актуальной задачей является создание методики построения системы автоматизированного составления учебного расписания с учетом недостатков существующих систем составления учебного расписания, специфики решаемой задачи и современных требований к системам составления расписаний.
Содержательная постановка задачи составления оптимального учебного расписания для школ с учетом предпочтений
Объектом исследования данной работы является задача составления учебного расписания для школ. Предметом исследования является автоматизация процесса составления учебного расписания с учетом предпочтений учащихся и преподавателей. Для решения сложных информационных задач в сфере образования на кафедре математического моделирования систем и процессов Пермского государственного технического университета под руководством заведующего кафедрой д.ф.-м.н., проф. Трусова П.В. была разработана единая информационная система образовательного учреждения «Школа» [9]. Составление расписания требует накопления и обработки большого количества информации, поэтому рационально реализовать методику составления расписания в виде универсального модуля единой информационной системы образовательного учреждения [7]. Целью данной работы является разработка методики составления оптимального учебного расписания, удовлетворяющей современным образовательным требованиям и реализация ее в виде универсального вычислительного модуля в рамках единой информационной системы «Школа». К задачам исследования относятся: 1) постановка задачи составления расписания с учетом нечетких предпочтений; 2) Разработка эффективного алгоритма решения; 3)Реализация данной методики в виде модуля единой информационной системы «Школа».
При постановке задачи необходимо учитывать жесткие требования, которые обязательно присутствуют в любой задаче составления учебного расписания для школ. Это условия совместности по времени для учебных групп и преподавателей, а также условия для аудиторий и иных ресурсов, задействованных в учебном процессе . Время дня в учебном заведении обычно делится на несколько периодов для занятий, разделенных промежутками времени на обед или перемены. Часовой сеткой расписания назовем множество периодов времени для занятий в течение недели, причем каждый период пронумеруем соответствующим ему числом, например, первое занятие в понедельник будет 1-ым, а последнее занятие в пятницу -45-м периодом времени (при девяти занятиях в день и пяти учебных днях). Количество ресурсов, доступных в данный период времени для проведения занятий, является ограниченным, и это ограничение следует учитывать как жесткое. Вместимость имеющихся аудиторий ограничена, поэтому ее также требуется жестко учитывать. Жестким ограничением является также выполнение учебного плана - учебная нагрузка группы в неделю должна соответствовать числу занятий по учебному плану. Кроме этого, преподаватели (или учебные группы) могут быть недоступны в некоторые периоды времени, что может быть связано, например, с несколькими местами работы у преподавателей-совместителей.
Как отмечено в работе [24], жесткий учет всех ограничений существенно осложняет поиск допустимого решения. Противоречивые требования, например, личные пожелания преподавателей по составлению расписания, учитываемые жестко, способны вести к вырожденному множеству допустимых решений. Напротив, в работе [55] указана эффективность учета ограничений нежестким способом, что позволяет быстрее находить допустимые решения за счет расширения пространства поиска. Поэтому рационально жестко учитывать только те ограничения, которые не могут быть ослаблены, а остальные ограничения учитывать нежестким образом. Например, личные пожелания преподавателей и учебных групп по составлению расписания логично учитывать нежестким способом по причине противоречивости этих ограничений. Примером таких ограничений являются ограничение на минимальную и максимальную учебную нагрузку в день или неделю для группы или преподавателя, наличие общих предпочтений (например, по времени проведения методического семинара), наличие свободных от занятий методических дней у преподавателей, баланс учебной нагрузки для групп (по баллам САНПИН [10]), существование так называемых «предустановок» (занятий с фиксированным временем проведения), учет недоступности преподавателей-совместителей в некоторые периоды времени, возможность «закрепления» аудитории за учебной группой, учет особенностей аудиторного фонда образовательного учреждения (и правил размещения учебных групп в аудиториях), а также способ организации и проведения занятий - занятия могут проходить у разных учебных групп параллельно или блоками, и может существовать определенный порядок проведения занятий, связанный с дидактическими или иными требованиями. Учебный процесс в разных образовательных учреждениях строится различным образом, поэтому при постановке задачи необходимо существование различных вариантов организации учебного процесса, например, проведение поточных лекций, деления учебных групп на подгруппы по профилю обучения и т.д. Участвующие в образовательном процессе стороны, например, учащиеся, преподаватели, администрация ставят перед расписанием цели относительно разных аспектов организации учебного процесса. Например, цели могут быть дидактические, организационные, цели по учету личных пожеланий к составляемому расписанию и др. Так как целей много и при составлении расписания вручную диспетчер стремится учесть их, то следует учитывать многокритериальность задачи оптимизации учебного расписания для школ. Кроме этого, как отмечено в работах [32,50], между частными критериями оптимальности могут быть зависимости, учет которых способен улучшить решение. Так как в реальных задачах требуются оптимальные решения либо близкие к ним, то зависимости между частными критериями оптимальности также следует учитывать для улучшения результатов расчета по алгоритму оптимизации.
При вводе данных в автоматизированную систему составления учебных расписаний возможны ошибки. При большом количестве разнообразных сведений, которые требуется для автоматизированного составления учебного расписания (список преподавателей и учебных групп, учебные планы групп, сведения об учебном распорядке образовательного учреждения, личные пожелания учебных групп и преподавателей по составлению расписания и другие), такие ошибки становятся практически неизбежными. Как отмечают авторы работы [1], затраты времени на поиск и устранение подобных ошибок в исходных данных могут быть весьма значительными, а не устраненные ошибки ведут к противоречивой системе ограничений и невозможности найти решение в некоторых случаях. Как отмечено в работе [1], ошибки в исходных данных могут быть учтены различными способами. Одним из способов является построение системы многократной верификации исходных данных. Однако для образовательного учреждения создание такой системы может быть неоправданным, так как издержки, связанные с ее организацией и использованием способны вести к отказу от применения средств автоматизации составления учебного расписания. Другим способом является введение исходных данных как известных неточно, с некоторой неопределенностью. В этом случае при построении системы автоматизированного составления расписания требуется учитывать неопределенность. Кроме этого, данные о личных пожеланиях учебных групп и преподавателей не известны точно. Например, выраженные преподавателем предпочтения могут измениться, например, по причине устройства на работу по совместительству и т.д. Кроме этого, иногда преподаватель не имеет четко выраженных предпочтений и описывает свои пожелания в терминах «лучше», «хорошо», «плохо». По этим причинам при постановке задачи составления оптимального учебного расписания с учетом предпочтений необходимо учитывать возникающую неопределенность по исходным данным. Более того, существует неопределенность, связанная с введением критериев оптимальности и формулировкой ограничений в реальных задачах составления учебного расписания.
Ограничения в задаче оптимального учебного расписания для школ
Как было отмечено ранее, ограничения в задаче составления оптимального учебного расписания с учетом предпочтений делятся на жесткие и нежесткие. Сформулируем сначала жесткие требования непротиворечивости расписания: 1. В каждый момент времени преподаватель или группа могут быть заняты только в одном занятии (это условия совместности по времени): V)eZ,VkeZ:} k= (xrxk) 0, Z = {zG[l,N]gi GZZ}, i = l (2.1) Для преподавателя: В зависимости от условий задачи, жесткие ограничения (2.6)-(2.9) могут быть ослаблены, и учитываться с помощью нежестких ограничений, либо вообще не учитываться. Например, в задаче составления расписания экзаменов в одной аудитории могут принимать экзамены несколько экзаменаторов. Далее рассмотрим нежесткие ограничения. Нежесткие ограничения в задаче составления учебного расписания имеют различный вид. Например, пожелание преподавателя о том, чтобы его занятия в расписании были расставлены компактно в два следующих друг за другом дня, с помощью нежесткого ограничения формулируется следующим образом: где і-номер преподавателя, pe[l,NF]-HOMep нежесткого ограничения (NF-общее количество таких ограничений в задаче), (рр(х)-скалярная функция, отражающая смысл нежесткого ограничения, а %-операция целочисленного деления. Носитель Vp нечеткого множества, соответствующего нежесткому ограничению, формируется из всех значений скалярной функции, для которых функция принадлежности не равна нулю: Vp = срр(хшр(фр(х)) о). Функция принадлежности нечеткого множества цр(ур),ур є Vp задается преподавателем, например, так, как показано нарис. 2.1. Эта функция показывает, что пожелание преподавателя выполняется полностью, если занятия в его расписании расставлены в один или два следующих друг за другом дня недели, например, в понедельник и вторник, или в среду и четверг.
Если расписание преподавателя распределено по трем дням недели, идущим последовательно, то такой вариант нежелателен для преподавателя, но, в крайнем случае, возможен (со степенью выполнения пожелания, равной 0,3). Если же расписание распределено по четырем и более идущим подряд дням недели, то такое расположение занятий в расписании полностью противоречит пожеланию преподавателя. Для введения предпочтения С , кроме нежесткого ограничения Ср =(фр(х),(ір(ур))(ур є Vp требуется задать норму а є[0,і] и относительную степень важности данного нежесткого ограничения s є {" совсем_не _ важно","не _важно"," нейтрально"," важно"," очень _ важно"}. Общий вид предпочтений в задаче составления учебного расписания записывается следующим образом: Например, если для задания некоторого первого предпочтения в задаче использовать описанные выше Фр(х) вида (2.10) и функцию цр(ур), показанную на рис. 2.1., то это предпочтение может быть записано в следующем виде: Помимо ограничений, для математической формулировки задачи оптимизации необходимо задать критерии оптимальности, которые будут рассмотрены в следующем параграфе. Как было отмечено в первой главе, рассматриваемая задача является многокритериальной. Учитывая большое число критериев оптимальности, ранее в первой главе была обоснована необходимость применения свертки частных критериев.
Были выделены две группы частных критериев оптимальности, отвечающих за учет интересов учащихся и учет интересов преподавателей. Для построения обобщенных критериев оптимальности, соответствующих двум группам частных критериев, введем сначала частные критерии оптимальности. Частные критерии оптимальности могут быть как четкими, так и нечеткими. Четкие критерии оптимальности могут быть представлены как нечеткие критерии оптимальности с функцией принадлежности цр(ур), равной единице на всей области ее определения, поэтому далее будем рассматривать только нечеткие частные критерии оптимальности. Общий вид таких критериев записывается в следующей где f jpsljNj -группа частных критериев, описывающих интересы учащихся (Nj -число частных критериев в группе). Группу частных критериев, описывающих интересы преподавателей обозначим fp2\p = 1,N2, где N2 - число таких критериев.
Алгоритм получения допустимых расписаний в задаче составления оптимального учебного расписания с учетом нечетких предпочтений
Общий объем вычислений, необходимый для получения решения, складывается из вычислительных затрат на перебор вариантов и вычислительных расходов на проверку выполнения ограничений С. В работе [52] указано, что использование глобальных ограничений совместно со специальными алгоритмами проверки их выполнения (называемыми иначе фильтрующими алгоритмами) позволяет существенно (на порядки) уменьшить количество вычислений, необходимых для нахождения решения в задачах большой размерности.
Методы распространения ограничений широко используются для составления учебных расписаний для школ [5 2]. Преимуществом этой группы методов является то, что для составления учебного расписания этими методами на практике требуется относительно небольшое количество машинного времени (порядка минут на современном персональном компьютере). Еще одним преимуществом является возможность предварительной оценки множества решений задачи. Если решение найдено, то ясно, что множество решений исходной задачи не вырождено. Если решение задачи не найдено, то существует возможность изменить набор ограничений и повторить процесс решения, чтобы определить, какое из ограничений значительно сужает множество решений задачи. Недостатком данного подхода можно считать то, что оптимальность расписаний, получаемых таким способом, может быть не высокой с точки зрения введенных критериев оптимальности, так как эти критерии не учитываются в процессе поиска решения. Однако, если рассматривать данный подход как возможность оценки допустимого множества решений задачи, и получения некоторого начального приближения - множества так называемых «черновых» расписаний, то такой подход представляется достаточно перспективным. Еще одним преимуществом данного подхода является возможность встраивания в алгоритм эвристик, отражающих специфику конкретной задачи, что повышает эффективность применения данного метода для решения задачи составления учебного расписания[52].
К четвертой группе мета-эвристических методов автор работы [25] относит методы локального поиска [42], включающие в себя поиск с запретами[43] и стохастический поиск (распространенный вариант которого носит в зарубежной литературе название simulated annealing[19]), а также генетические алгоритмы[30]. Особенностью данной группы методов является возможность получения нескольких оптимальных либо суб-оптимальных решений и использование «черновых» решений в начале поиска. Поиск оптимального решения производится путем последовательного улучшения каждого из «черновых» решений. Обычно в этих алгоритмах предусматривается возможность выхода в процессе оптимизации из точек локальных минимумов оптимизируемой функции. Указанные методы широко применяются в настоящее время для составления учебных расписаний (например, с помощью генетических алгоритмов [30] или метода simulated annealing [19]). Следует отметить, что работах, посвященных решению задач составления учебного расписания, эти методы иногда называются эволюционными. Преимуществом этой группы методов является то, что оптимизация проводится сразу для некоторого множества решений, и возможен выбор наилучшего (по некоторому дополнительному критерию) расписания из множества допустимых. Помимо преимуществ, рассматриваемые методы обладают и недостатками. Например, к недостаткам генетических алгоритмов можно отнести то, что сходимость к оптимальному решению задачи для этих методов, в общем случае, строго не доказана. Кроме этого, в работе [37] отмечено, что в задачах составления учебного расписания, решаемых с помощью генетических алгоритмов, большое влияние на результат оптимизации оказывает выбор оператора мутации. Попытка провести обоснование выбора такого оператора сделана в работе [36], однако конкретных рекомендаций по выбору оператора мутации в зависимости от особенностей задачи автор не приводит. В отличие от генетических алгоритмов, методы стохастического поиска в некоторых случаях имеют математическое доказательство сходимости к оптимальному решению задачи. Например, для метода, называемого в зарубежной литературе Pareto simulated annealing [19], для двухкритериальной задачи оптимизации доказана сходимость по вероятностной мере решения к множеству Парето оптимальных решений исходной задачи. Кроме этого, в работе [19] рассматривается влияние выбора параметров алгоритма стохастического поиска на результаты оптимизации, в том числе с учетом специфики задач составления учебного расписания, и имеются конкретные рекомендации по выбору значений параметров метода стохастического поиска. Также существует адаптивный алгоритм стохастического поиска типа simulated annealing [19], в котором параметры метода подбираются автоматически в процессе решения конкретной задачи.
Приведенная условная классификация методов не является полной, но отражает основные классы существующих методов составления учебного расписания. При выборе метода решения следует учитывать следующие важные свойства. Например, одним из важных свойств метода комбинаторной оптимизации является его полнота. Полный метод гарантирует нахождение решения задачи в случае его существования. Однако при этом не исключается ситуация, в которой решение будет найдено в самом конце поиска, что при большой размерности пространства поиска в задаче может быть неприемлемо из практических соображений (например, ограничения на время для получения решения). К полным методам можно отнести методы математического программирования, метод ветвей и границ, метод поиска в графе в глубину и в ширину, а также методы, основанные на теории потоков в сетях (например, поиска максимального потока в сети и т.д.). Перечисленные методы многократно использовались для решения задач составления учебного расписания.
Эвристические алгоритмы ослабления ограничений в модуле «Расписание» информационной системы «Школа»
Как было отмечено в предыдущем параграфе, для проведения анализа причин, по которым (допустимое или оптимальное) расписание не составляется, следует использовать специальное программное обеспечение. Для проведения анализа такого вида в модуле «Расписание» реализованы следующие возможности: при поиске допустимого расписания -статистический анализ сведений о процессе поиска допустимого расписания и анализ графа ограничений задачи; при поиске оптимального расписания -корреляционный анализ значений частных критериев оптимальности.
При поиске допустимого расписания возможны следующие случаи, в которых составить допустимое расписание не удается: 1) множество XD = 0 при заданной системе ограничений и исходных данных; 2) эвристика, управляющая поиском допустимого расписания, сформулирована таким образом, что в первую очередь рассматриваются варианты, бесперспективные для нахождения решения.
Первый из перечисленных случаев может быть результатом ошибки в заданных ограничениях, либо недостатка ресурсов (например, свободных аудиторий) для составления допустимого расписания. Так как сведения о процессе поиска допустимого расписания сохраняются в файле, куда записывается причина, по которой тот или иной рассматриваемый вариант расписания V был отклонен, то существует возможность статистической обработки этих данных. Это позволяет выявить занятия, наиболее трудные для расстановки в часовую сетку расписания, а также наиболее загруженные ресурсы (аудитории). Для составления допустимого расписания во втором случае из перечисленных требуется правильно задать эвристику, управляющую поиском допустимого расписания, и учесть особенности решаемой задачи (например, так, как это предложено в третьей главе данной работы).
Еще одной возможностью, реализованной в модуле «Расписание», является исследование графа ограничений задачи составления учебного расписания с помощью сервисной программы «Граф ограничений задачи». Эта программа изображает структуру ограничений задачи в виде графа, вершинами которого являются занятия учебного плана L, а также обобщенные преподаватели (группы, аудитории) и реальные преподаватели (группы, аудитории). Дуги между вершинами отражают отношение включения. Например, если для некоторого занятия из учебного плана назначен обобщенный преподаватель, то вершины, соответствующими этому занятию и указанному обобщенному преподавателю, в графе будут соединены дугой. Если сравнить результаты проведенного статистического анализа с видом данного графа, то из этого сравнения могут быть получены новые сведения. Например, о том, что некоторая достаточно «плотная» группа жестких ограничений задачи «мешает» алгоритму найти допустимое решение. В этом случае сформулированную эвристику по поиску допустимого расписания следует скорректировать таким образом, чтобы занятия, связанные «плотными» ограничениями, расставлялись в расписание ранее остальных.
Так как в процессе поиска оптимального расписания сведения об оптимальности рассматриваемых вариантов расписаний также записываются в отдельный файл, то эти данные можно проанализировать и выявить взаимосвязи между частными критериями оптимальности. В качестве математического аппарата такого анализа в данной работе предлагается использовать парный корреляционный анализ. Если коэффициент корреляции для значений двух частных критериев оптимальности меньше, чем -0.5 (знак минус в коэффициенте корреляции указывает, что увеличение значения одного критерия соответствует уменьшению значения другого частного критерия), то предлагается считать такие критерии конфликтующими и явно учитывать это с помощью сервисной программы «Редактор обобщенных критериев оптимальности». В этой программе задаются взаимосвязи частных критериев оптимальности в виде графа, вершинами которого являются частные критерии оптимальности, а дуги между вершинами отражают наличие конфликта между частными критериями оптимальности. Воспользовавшись перечисленными программными инструментами и выяснив причину, по которой расписание составить не удается, можно ослабить ограничения в задаче составления расписания вручную.
Для автоматического ослабления ограничений в модуле «Расписание» реализованы специальные эвристические алгоритмы, которые применяются на разных этапах поиска решения задачи. Ранее в третьей главе была предложена эвристика, управляющая поиском допустимого расписания.
Применяемая в этой эвристике топологическая сортировка значений домена )j переменной j позволяет сократить число ситуаций, когда составление допустимого расписание невозможно по причине нарушения предпочтений (2.11). Сортировка значений из С): ведется таким образом, чтобы сначала учесть ограничения (2.1)-(2.3), и лишь затем - предпочтения (2.11). Когда в домене j остается лишь несколько значений, для которых выполняются ограничения (2.1)-(2.3), вероятность нахождения среди этих значений таких, что предпочтения (2.11) выполняются с заданными нормами ар, снижается, то есть предпочтения (2.11) автоматически ослабляются. На этапе поиска оптимального расписания методами стохастического поиска существует другой эвристический алгоритм ослабления ограничений. Фактически этот алгоритм заменяет диспетчера и решает за него, какие операции требуется совершить для ослабления ограничений. Предлагаемый алгоритм заключается в следующем
Похожие диссертации на Математическая модель оптимального учебного расписания с учетом нечетких предпочтений
