2.5. События и реакция на них

Модуль «Расписание» генерирует следующие системные события:

• утверждено расписание на неделю ;

• перенесена пара в утвержденном расписании, добавлена пара в утвержденном расписании, снята пара в утвержденном расписании;

После отмены либо переноса в другую аудиторию заявки на работу в аудитории по записи отсылается сообщение пользователю, подавшему заявку.

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

2.6. Требования к выдерживаемой нагрузке

Модуль «Расписание» должен поддерживать одновременную работу не менее 10 преподавателей. Скорость задержки при выставлении дополнительного занятия в расписание должна быть не более 5 секунд. Модуль «Расписание» должен выдерживать не меньше 100 запросов в минуту о расписании на конкретную неделю для конкретного пользователя.

Время расчета некорректностей в импортированном расписании для всего вуза в целом при количестве найденных некорректностей <=10 должно составлять не более:

• 10 секунд для первичной выверки (корректность списков дисциплин, аудиторий, групп, преподавателей);

• 20 секунд для вторичной выверки (соблюдение технологических карт курсов, включая требования к ресурсам, соответствие списков преподавателей и групп на курсах);

• 5 минут для окончательной выверки (пересечения по аудиториям, преподавателям, группам, занятия во внеучебные дни, занятия в недоступной аудитории, пересечения по отдельным студентам).

6. Порядок контроля и приёмки

Плановое начало выполнения работ: 24.10.2014г.

Плановое окончание работ: 24.12.2014 г.

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

После обучения персонала и завершения опытной эксплуатации модуля оформляется акт сдачи-приемки модуля в промышленную эксплуатацию.

На рис. 1. Изображена модель функциональной нагрузке в контексте модели деятельности ВУЗа.

7. Описание решения, алгоритма построения расписания.

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

1) построение одного или множества опорных допустимых расписаний;

2) оценка качества данного расписания;

3) поиск подмножества парето-оптимальных расписаний путем последовательного изменения текущего расписания (или множества расписаний) в направлении его (их) улучшения в соответствии с принятыми показателями качества.

В задачах составления расписания учитывают два типа требований:

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

Сформулируем качественное понимание «справедливости» расписания: будем называть его справедливым, если среди субъектов — участников учебного процесса нет такого, чьи интересы учтены значительно хуже других. Тогда вместо одного скалярного показателя качества расписания целесообразно использовать два:

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

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

Для формализации показателей качества расписания необходима схема формализации требований, предъявляемых к расписанию.

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

1) смысловой функцией, которая дает обобщенную характеристику

отклонения текущего расписания от ситуации идеального выполнения

требования;

2) лингвистической переменной «приоритет требования», например с множеством значений T = {«высокий», «средний», «низкий»};

3) весом требования [0,1];

4) областью допустимых значений смысловой функции;

5) целевой функцией требования.

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

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

Чтобы полученное расписание удовлетворяло условиям допустимости, необходимо выполнение следующих жестких требований (в скобках дается эквивалентная формулировка «на языке связей»):

— в каждой группе должны быть проведены все запланированные занятия (каждому занятию должна быть сопоставлена ровно одна активная связь);

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

— каждый преподаватель в каждый момент времени может вести неболее одного занятия (каждому преподавателю на каждой паре сопоставляется только одна активная связь);

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

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

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

Шаг 1. Строим описанную в предыдущем разделе структуру представления данных для обеих подзадач из числа выделенных в начале раздела 1 без указания активных связей. Рассчитаем в этих структурах вес, соответствующий каждой связи, а также доступный на каждой паре объем аудиторного фонда для занятий каждого типа. Далее на шагах 2—4 рассматривается алгоритм распределения занятий во временной сетке вуза, то есть решения первой подзадачи. Алгоритм распределения занятий по аудиториям (вторая подзадача) строится аналогично.

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

1) если занятие имеет только один вариант размещения в расписании, то связь, реализующая данный вариант, становится претендентом на активную связь;

2) если найдена только одна связь — претендент на активную, назначим ее активной и переходим к шагу 3. Если таких связей несколько, то проверим их на совместность. Связи будем называть совместными, если назначение их активными не приводит к нарушению жестких требований задачи. В случае совместности полученных связей назначаем их активными и переходим к шагу 3, в противном случае — к шагу 4;

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

Шаг 3. Исключим из дальнейшего рассмотрения все связи, противоречащие установленным активным связям. Вследствие этого изменятся веса некоторых связей; пересчитаем их и перейдем к шагу 2.

Шаг 4. Занятия могут оказаться несовместными, если для них необходимы ресурсы, использованные занятиями, уже размещенными в расписании. Для того чтобы такие занятия сделать совместными, необходимо высвободить нужные ресурсы по следующему алгоритму:

1) составим список размещенных в расписании занятий, исполь-

зующих недостающие ресурсы, и рассмотрим занятие из списка, раз-

мещенное в расписании последним;

2) высвободим необходимый для несовместных занятий ресурс, с

этой целью укажем рассматриваемому занятию альтернативную ак-

тивную связь. Если такой связи не существует (то есть других связей нет

или они заблокированы), то рассмотрим следующее занятие из списка

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

рассмотрены, то попытаемся на основе аналогичного алгоритма высво-

бодить ресурсы для перемещения активных связей занятий из рассмат-

риваемого списка. Будем повторять данную процедуру до тех пор, пока

не высвободим необходимые ресурсы для несовместных занятий или

не покажем, что это сделать невозможно (для этого потребуется после-

довательно перебрать все возможные варианты его освобождения), и

тогда алгоритм завершает работу;