Автоматизированная система планирования учебной работы университета

· Ограничения (значения устанавливаются экспертно для каждой категории (группы) дисциплин, кафедры и вида учебных занятий):

o минимальный размер потока (количество студенческих групп в потоке);

o максимальный размер потока (количество студентов в потоке).

2. Задачи оптимизации структуры учебных планов и специализации кафедр университета (2.1, 2.2, 2.3, 2.4 и 2.5)

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

Оценка (+/- в аудиторных часах и процентах) производится относительно базового варианта - реального варианта, актуального для текущего учебного года, для которого уже выполнены все расчеты объемов учебной нагрузки (по реализуемым образовательным программам, кафедрам, факультетам).

Задача 2.1. Сравнительный анализ учебных планов различных специальностей (направлений подготовки) с целью выработки рекомендаций по унификации учебных планов и специализации кафедр для оптимизации потоков при проведении аудиторных занятий:

· выявление дисциплин (различных учебных планов), обеспечивающих формирование одинаковых (по существу) наборов компетенций у обучающихся;

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

· унификация структуры аудиторных занятий для близких по содержанию дисциплин разных учебных планов (что позволит в дальнейшем более эффективно формировать потоки).

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

Шаг 1. Дисциплины группируются по критерию близости формируемых компетенций (аналогично рассмотренному выше для задачи оперативного планирования); результат - множество групп дисциплин, близких по составу формируемых компетенций. Для каждой группы приведен (для справки) список обобщенных компетенций.

Группа №<>.

Список обобщенных компетенций, формируемых дисциплинами группы

Дисциплина	Специальность	Семестр	ЗЕТ	Часов аудиторных занятий	Кафедра
				Лекций	Практич.	Лаб.
							Каф_1
							Каф_1
							Каф_2
							Каф_2
							Каф_3
							Каф_3
							Каф_3
							Каф_3

Шаг 2. Для каждой из сформированных групп дисциплин визуально анализируется состав обеспечивающих кафедр.

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

Разумеется, решение такого рода вопросов не следует поручать компьютеру, однако пользователь вправе смоделировать различные варианты изменения состава обеспечивающих кафедр и получить количественные оценки результатов такого моделирования (абсолютная и относительная величина изменения суммарного объема аудиторной нагрузки), например:

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

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

· Разумных вариантов перераспределения дисциплин между кафедрами будет не так уж и много, и многократно выполняя описанную выше процедуру, пользователь сможет подобрать оптимальный вариант закрепления учебных дисциплин за кафедрами и одновременно получить оценку снижения объема аудиторной нагрузки.

· Можно рассмотреть и программную реализацию описанного выше оптимизационного алгоритма.

Шаг 3. Для каждой группы дисциплин, сформированных на шаге 2, анализируется возможность "перемещения" дисциплин между семестрами (такое перемещение может потребовать внесения и других изменений в учебные планы и должно согласовывается с заинтересованными кафедрами).

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

· Однако, такой вариант в ряде случаев может оказаться неприемлемым (например, из-за неравномерности загрузки ППС, работающих на "моно"-кафедрах), и тогда перемещение дисциплин группы должно производиться по критерию выравнивания объема нагрузки по семестрам.

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

Шаг 4. Для каждой группы дисциплин, сформированных на шаге 3, анализируется возможность унификации структуры дисциплин (по согласованию с заинтересованными кафедрами; без изменения суммарного объема часов аудиторных занятий):

· Выравниваются объемы лекционных занятий по дисциплинам группы (например, путем замены части лекционных занятий практическими или наоборот).

· Выравниваются объемы практических занятий по дисциплинам группы (например, путем замены части (или всех) практических занятий лабораторными или наоборот).

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

5.2.8 Описание прототипа компонента 2.2.2 "Формирование норм времени для расчета штатов ППС"

Цель - определение нормативов трудоемкости выполнения учебной работы, соответствующих:

· заданным ограничениям численности ППС, установленным на планируемый (следующий) учебный год;

· ограничениям максимального годового объема учебной нагрузки, выполняемой преподавателем, занимающим одну должностную ставку;

· принятой в КГУ системе нормирования и структуре учебной работы (Приложение 1).

Исходные условия:

1. Справочники 1.1 и 1.2 (см. выше) актуализированы для следующего учебного года:

· Утверждены все новые учебные планы и все изменения в действующие учебные планы; изменения сохранены в базе данных.

· Определена расчетная численность студенческих групп, в том числе и для групп первого курса в соответствии с планами приема.

2. Определены параметры численности ППС на следующий учебный год.

3. Определен максимальный годовой объем учебной работы, выполняемой преподавателем, занимающим одну должностную ставку.

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

Задачи, решаемые пользователями приложения.

1. Для всех категорий и видов учебной работы (см. Приложение 1), необходимых для реализации ООП всех образовательных уровней, определить следующие показатели нормирования, обеспечивающие выполнение ограничений по численности ППС:

· База нормирования, например:

o "поток групп" - для лекционных занятий,

o "подгруппа" - для лабораторных занятий,

o "процент от объема курса лекций по дисциплине" - для консультаций,

o "студент" - для экзаменов, зачетов, контрольных и курсовых работ,

o "студент Ч недель" - для руководства производственной практикой,

o и т.д. (см. Приложение 1)

· Нормы времени - акад. часов за единицу базы нормирования.

· Правила и ограничения, используемые при применении норм, например:

o "каждому их 4-х экзаменаторов" - при приеме творческого вступительного экзамена или кандидатского экзамена у аспиранта или соискателя,

o " доцентам - не более 4-х, профессорам - не более 6 аспирантов" - для руководства аспирантами и соискателями,

o и т.д. (см. Приложение 1)

2. Подготовка печатного документа "Примерные нормы времени для расчета штатов ППС на ______ учебный год".

Технология работы пользователя приложения

На начальном этапе решается обратная задача: рассчитывается объем учебной нагрузки ППС, запланированной на следующий учебный год, по нормам времени, установленным для текущего года. Результаты расчета сравниваются с объемом учебной нагрузки, выполняемой в текущем учебном году, и параметрами численности ППС, установленными на следующий учебный год.

Базовый вариант: нормы времени 20__ / __ учебного года

Категории учебной работы	Всего часов за год	Всего ставок ППС	В % к данным прошлого года
Вступительные испытания
Учебные занятия по дисциплинам
Аудиторные занятия
Консультации
Контрольные работы
Курсовые работы и проекты
Зачеты и экзамены
Практика и НИР
ВКР и ГИА
Учебно-административная работа
ВСЕГО

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

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

В противном случае (если расчетное количество ставок ППС оказалось существенно больше (или меньше) установленного значения) пользователь может:

· получить детальную информацию по каждой категории учебной работы: при неведении фокуса на любую ячейку строки таблицы "всплывает" подсказка с информацией о базе нормирования, норме времени, правилах и ограничениях, используемых при нормировании;

· по результатам визуального анализа предварительно определить категории учебной работы, изменение норм для которых может привести к желаемому результату;

· перейти к следующему этапу моделирования.

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

· просматривает установленные нормы для выбранных им категорий и видов учебной работы, модифицирует данные (нормы времени и/или правила их применения) по своему усмотрению и анализирует результаты расчета, соответствующие сделанным изменениям;

· при этом все промежуточные варианты сохраняются во временной базе данных, и всегда имеется возможность отката на предшествующие этапы моделирования;

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

· После согласования и утверждения предлагаемых норм в установленном порядке соответствующая информация сохраняется в основной базе данных и устанавливается "флаг" готовности системы к выполнению процедуры "Расчет учебной нагрузки кафедр на следующий учебный год".

5.2.9 Описание прототипа компонента 2.2.3 Формирование объемов годовой учебной нагрузки кафедр и факультетов

Процедура "Расчет учебной нагрузки кафедр на следующий учебный год" выполняется автоматически по факту готовности системы (см. выше "Флаг готовности").

В результате пользователям компонентов АРМ "Учебный отдел" и АРМ "Кафедра" становится доступной информация о планируемых объемах годовой учебной работы и установленных сроках завершения работ по персональному распределению учебной нагрузки между ППС кафедр.

Прототип компонента в составе АРМ "Учебный отдел" подобен прототипу одноименного компонента, детально описанному в разделе "АРМ Кафедра".

5.2.10 Описание прототипа компонента 2.2.4 Расчет численности ППС кафедр и факультетов

Цель: определение расчетной численности ППС кафедр (общее количество ставок) на планируемый учебный год.

Пользователь - начальник учебного отдела.

Исходные условия:

1. Актуализирован для планируемого учебного года справочник "Образовательные программы и Рабочие учебные планы" (для всех учебных планов определены кафедры, обеспечивающие подготовку по дисциплинам).

2. Актуализирован для планируемого учебного года справочник "Контингент студентов" (определена численность студентов, обучающихся на каждом курсе по ООП всех видов и форм обучения, в том числе, за счет бюджетного финансирования и на коммерческой основе).

3. Актуализирован для планируемого учебного года справочник "Штаты ППС" (определен состав факультетов и кафедр на факультетах).

4. Актуализирован для текущего учебного года справочник "Штаты ППС" (определен состав преподавателей кафедр по должностным ставкам).

5. Выполнена процедура "Расчет учебной нагрузки кафедр на следующий учебный год" (в том числе, определены потоки студенческих групп при проведении учебных занятий).

Технология

1 этап: Анализ контингента обучающихся на ООП по факультетам

Пользователь выбирает факультет из предложенного ему списка и получает для просмотра и анализа информацию о контингенте обучающихся и расчетной численности ППС в планируемом учебном году:

<планируемый> учебный год Факультет <Наименование факультета>

1. ООП бакалавриата

Код	Направление подготовки	Форма обучения	Контингент обучающихся	Норма	Ставок ППС
			Всего	Бюджет	Платн.		Всего	Бюдж.	Н/Б
09.03.03	Прикладная информатика	Очная
		Заочная
		ВСЕГО:				-
09.03.04	Программная инженерия	Очная
		Заочная
		Заоч. ускор.
		ВСЕГО:				-
10.03.01	Информационная безопасность	Очн.-заоч.
		ВСЕГО:				-
…..	…..	…..
		ВСЕГО:				-
ИТОГО по ООП бакалавриата:				-

2. ООП специалитета

Код	Направление подготовки	Форма обучения	Контингент обучающихся	Норма	Ставок ППС
			Всего	Бюджет	Платн.		Всего	Бюдж.	Н/Б
10.05.03	Информационная безопасность	Очная
		ВСЕГО:				-
…..	…..	…..
		ВСЕГО:				-
ИТОГО по ООП специалитета:				-

3. ООП магистратуры

Код	Направление подготовки	Форма обучения	Контингент обучающихся	Норма	Ставок ППС
			Всего	Бюджет	Платн.		Всего	Бюдж.	Н/Б
15.04.01	…	Очная
		Заочная
		ВСЕГО:				-
09.04.04	Программная инженерия	Очная
		Заочная
		ВСЕГО:				-
…..	…..	…..
		ВСЕГО:				-
ИТОГО по ООП магистратуры:				-
ИТОГО по факультету <……>:				-

Примечания:

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

2. В графе "Норма" указывается установленный норматив (количество обучающихся на одну ставку ППС). Этот параметр можно хранить в базе данных (справочник "Контингент студентов") или дать возможность пользователю самому вводить соответствующие данные.

3. При наведении "фокуса" на ячейку таблицы в графах "Контингент обучающихся" или "Ставок ППС" на экране "всплывает" подсказка, детализирующая соответствующие данные по курсам (годам обучения) студентов.

2 этап: Расчет численности ППС кафедр

Пользователь:

· выбирает факультет из предложенного ему списка;

· далее - выбирает кафедру из списка кафедр выбранного факультета;

· получает для просмотра и анализа информацию в табличной форме (см. ниже) о:

o годовой учебной нагрузке и штатах ППС кафедры в текущем учебном году;

o трудоемкости реализации дисциплин всех учебных планов, обеспечиваемых кафедрой в планируемом учебном году (в ЗЕТ и в часах годовой учебной нагрузки по каждой такой дисциплине);

o расчетной численности ППС кафедры в планируемом учебном году в соответствии с долей трудоемкости реализации дисциплин (и всех прочих компонентов учебных планов), обеспечиваемых кафедрой, в общей годовой трудоемкости реализации соответствующего учебного плана.

· По результатам анализа расчетных данных пользователь принимает решение (или формирует предложения для принятия решения в установленном порядке) о численности ППС кафедры в планируемом учебном году.

Факультет <……………….> Кафедра <……………………>

Штаты ППС: всего ставок ______ в т.ч. бюджетных _____

Объем годовой учебной нагрузки кафедры <текущий> учебный год

Образовательные программы

Компоненты учебных планов

Группы студентов

Учебная нагрузка кафедры (часов в год)

Образовательный уровень

Код специальности (направления подготовки)

Форма обучения

Наименование дисциплины, практики, НИР, ГИА и пр.

Трудоемкость, ЗЕТ в год

Группа

Количество студентов

Ауд. занятия

Неаудиторная работа

Всего часов за год

Лекции

Практические

Лаб. работы

Консультации

Контр. работы

Курс. работы

Курс. проекты

Зачет

Дифф. зачет

Экзамен

Б

09.03.02

О

О

З

10.03.01

В

09.03.04

ЗУ

Всего часов по ООП бакалавриата

С

10.05.03

0

17.04.01

0

Всего часов по ООП специалитета

М

09.04.04

О

З

14.04.01

З

15.04.01

О

Всего часов по ООП магистратуры

А

09.06.04

0

З

09.06.03

О

Всего часов по ООП аспирантуры

ИТОГО, объем годовой учебной нагрузки кафедры

Примечания:

· Первоначально на экране отображаются только строки с промежуточными итоговыми данными и последняя строка с итоговым объемом годовой учебной нагрузки.

· При наведении "фокуса" на соответствующую строку с промежуточным итогом отображается детальная информация для выбранной категории.

· При наведении "фокуса" на последнюю строку отображается вся таблица.

Факультет <……………….> Кафедра <……………………>

Расчет численности ППС кафедры на <планируемый> учебный год

Расчет производится последовательно для ООП всех образовательных уровней и форм обучения, в учебных планах которых имеются дисциплины, обеспечиваемые кафедрой (в примере рассмотрена одна ООП).

1. Отображается информация о контингенте студентов и общей численности ППС, обеспечивающих реализацию данной ООП в соответствии с установленными нормами (кратко - только строки "ВСЕГО" и "ИТОГО", или детально - по курсам):

Направл. подготовки

Форма обучения

Норма

Курс

ЗЕТ в год

Часов в год

Контингент обучающихся

Ставок ППС

Всего

Бюдж.

Платн.

Всего

Бюдж.

Н/Б

09.03.04

Программная инженерия

Очная

1

2

3

4

Всего

Заочная

1

2

3

4

5

Всего

Заоч. ускор.

1

2

3

4

ВСЕГО

ИТОГО:

2. Отображается информация о составе и трудоемкости дисциплин данной ООП, обеспечиваемых кафедрой:

Компоненты учебных планов	Трудоемкость, ЗЕТ в год	Доля от годовой трудоемкости реализации ООП, %	Расчетное количество ставок ППС (по ЗЕТ)	Группы студентов	Объем учебной нагрузки по дисциплине (часов в год)	Доля от объема учебной на грузки по всей ООП, %	Расчетное количество ставок ППС (по объему нагрузки)
Наименование дисциплины, практики, НИР, ГИА и пр.				Группа	Количество студентов	Аудиторные занятия	Неаудиторная работа	Всего часов за год
…
…
…
…
…
ИТОГО:

Примечания:

· Расчеты производятся отдельно по каждой форме обучения.

· Расчетное количество ставок ППС рассчитывается по двум критериям:

o пропорционально "вкладу" дисциплины в суммарную годовую трудоемкость реализации ООП (ЗЕТ), что проще, но не совсем точно отражает существо вопроса;

o пропорционально "вкладу" дисциплины в суммарный годовой объем учебной нагрузки, необходимой для реализации всех дисциплин ООП, что явно точнее, но сложнее в реализации.

5.2.11 Описание прототипа компонента 3.2 "Формирование расписания учебных занятий"

Цель: подготовка расписаний проведения аудиторных и аттестационных учебных занятий на предстоящий семестр (или на установочную / зачетно-экзаменационную сессию - для ООП заочной формы обучения)

Исходные условия:

1. Все справочники актуализированы для планируемого учебного года:

· Образовательные программы и Рабочие учебные планы

· Контингент студентов

· Аудиторный фонд

· Нормы времени для расчета штатов

2. Определены потоки групп для проведения лекционных, практических и лабораторных занятий.

3. Выполнены процедуры "Распределение годовой учебной нагрузки между преподавателями кафедр", в результате которых:

· Определены связи "преподаватель-дисциплина-группа-вид занятий".

· Сформированы рекомендации по использованию специализированных аудиторий кафедр для проведения учебных занятий по дисциплинам.

· Определены ограничения по использованию рабочего времени преподавателей.

Пользователи - диспетчеры учебного отдела (для базовых ОП).

Пользователь, в соответствии с установленными для него правами доступа, просматривает доступный ему фрагмент списка учебных занятий, с каждым элементом которого связаны (обязательно) кафедра и преподаватель, а также (возможно) - список допустимых аудиторий.

Технология:

1 этап: выбор аудиторий (с учетом рекомендаций, ограничений, расположения по корпусам и факультетам, текущей загруженности).

2 этап: время проведения занятия (известно количество в неделю для группы (подгруппы, потока).

Эти два этапа циклически повторяются.

· На каждом проходе по циклу возможны дополнения, а также изменения или отмена результатов предыдущих проходов.

· В конце каждого прохода по циклу:

· рассчитывается процентная доля выполненной работы;

· отображается недораспределенная часть формируемого фрагмента расписания;

· рассчитывается оценочный показатель качества сформированного расписания.

· Критерии завершения работы (готовность к утверждению формируемого фрагмента расписания):

· 100% сформировано

· Интегральный показатель качества расписания не ниже установленной нормы (подбирается эмпирически на базе экспертных оценок)

клиентский алгоритм сетевой учебный

Список использованных источников

1. Фаулер М. Архитектура корпоративных программных приложений: Пер. с англ. -- М.: Из-дательский дом "Вильяме", 2006. -- 544 с.

2. Richardson L., Ruby S. RESTful Web service. --O'Reilly Media, 2007. - 454 p.

3. ISO/IEC 14882:2014 Information technology - Programming languages -- C++, ISO., 2014. 1358 с.

4. Руководство пользователя ORB ODB: официальный сайт ODB, 2015

5. Henning M., Vinoski S. Advanced CORBA Programming with C++. -- Addison Wesley Longman, 1999. - 1120 p.

6. Gray N. Comparison of Web Services, Java-RMI, and CORBA service implementations / N. Gray // Fifth Australasian Workshop on Software and System Architectures (ASWEC 2004), Melbourne, Australia, April (2004)

7. Michael H. Ruby on Rails Tutorial

8. Волк В.К. Информационная модель учебного плана как основа электронной образовательной среды. [Текст] / В.К. Волк // Вестник Курганского государственного университета. Серия "Технические науки". Вып. 12 - Курган: Изд-во Курганского государственного ун-та, 2017. - с. 110-113.

9. Яковенко Н.И., Головко А.П., Волк В.К.. Автоматизированная система формирования и контроля качества расписания учебных занятий [Текст] // Сб. научн. трудов Тюменского государственного университета "Математическое и информационное моделирование". Вып. 15 Часть 1. - Тюмень, 2017. - с. 521-528.

Приложение 1

Система оценки качества расписания

1. Общая стратегия решения задачи оценки готового расписания

1.1. Постановка задачи

На входе имеем несколько вариантов расписания одних и тех же занятий.

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

Необходимо найти вариант, наилучший в некотором отношении, то есть наиболее отвечающий некоторым нашим пожеланиям.

Эти пожелания имеют вид типа «Должно быть поменьше "окон" у студентов и преподавателей», «Профессору Сидорову желательно не ставить занятия во вторник» и т.п.

1.2. Общая схема алгоритма

Задача решается в 3 этапа.

1. Расчет показателей (не)соответствия пожеланиям.

Для каждого варианта расписания по каждому пожеланию рассчитывается числовой показатель: насколько этот вариант расписания не соответствует данному пожеланию. Например, общее количество «окон»; количество пар во вторник у профессора Сидорова и т.д.

Этот этап осуществляется полностью автоматически.

2. Предварительный отсев.

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

Этот этап также осуществляется полностью автоматически.

3. Выбор лучшего варианта расписания из оставшихся.

Этот этап может выполняться по-разному. Есть полностью автоматические методы, есть автоматизированные, имеются такие, когда степень автоматизации будет постепенно возрастать в ходе эксплуатации системы. Они не являются взаимоисключающими, то есть могут применяться совместно

Разумеется, человек может в любой момент вмешаться и решить вопрос по-своему.

2. Представление входных данных алгоритма на логическом уровне

2.1. Состав входных данных

На вход алгоритма подаётся:

1) вариант расписания,

2) наши пожелания,

3) при необходимости -- справочная информация.

2.2. Расписание

На логическом уровне считаем, что есть таблица. Говоря в терминах реляционных БД эта таблица, находится в первой нормальной форме.

Это основа и дальше всё изложение ведётся в основном вокруг нее.

Строку в неё дальше зовем Запись, не уточняя, чья запись.

Запись включает поля:

1) неделя (четная/нечетная или к.-л. еще)

2) день недели

3) пара

4) аудитория

5) группа / подгруппа

6) дисциплина

7) вид занятий

8) преподаватель

9) кафедра

10) корпус.

Если преподавателя 2, то 2 записи.

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

2.3. Пожелания

2.3.1.Множество пожеланий являются основанием для оценивания вариантов расписания.

Каждое пожелание Пж формулируется таким образом, что оно напрямую связывается с некоторым числовым показателем ЧПt, который можно однозначно определить (вычислить) для конкретного варианта расписания.

Здесь рассматривается случай, когда речь идёт о каких-то нежелательных вещах, и каждый ЧП показывает, насколько плох вариант расписания, а не насколько хорош. Обобщить для случая положительных оценок не составляет труда.

2.3.2.Значение ЧП для каждого Пж может быть переведено в лингвистическое значение (ЛЗ), то есть словесную формулировку типа «многовато». Для каждого ЧП имеется свой Измеритель нежелательности ИН (см. «Формальная модель») Имеется фиксированный набор ЛЗ (определяется пользователем произвольно), общий для всех ЧП, при этом каждый ИН может использовать только некоторые значения (не меньше 2).. Все ЛЗ упорядочены по степени нежелательности (начиная, например, от «Ещё вполне приемлемо» и до «Совсем скверно»). Каждое ЛЗ имеет соответствующий этой упорядоченности числовой код (порядковый показатель - ПП): целое число от 0 (ноль) и выше. Таким способом пользователь может определить, например, что 1 окно в неделю для преподавателя -- вполне приемлемо и вообще не является недостатком (данного варианта расписания), 2 или 3 окна -- примерно одинаковый минус и ещё не очень страшный, а вот даже одно окно у академика Петрова -- проблема на грани забраковки (данного варианта расписания) и т.д.

2.3.3. Пользователь произвольным образом упорядочивает пожелания, попросту говоря -- присваивает каждому порядковый номер: 1, 2,… Нумерация может отражать важность пожелания, а может нет. Пользователь может отдать этот вопрос программе, и она как-то перенумерует. Для алгоритма это не имеет значения.

3. Основные этапы алгоритма

3.1. Расчет показателей несоответствия пожеланиям

1. Для каждого Пж рассчитывается ЧП.

2. На основе этих ЧП (1-го порядка) можно вычислять другие ЧП (2-го порядка и выше). Например, максимальное среднее недельное количество окон у преподавателей кафедр Технологического факультета.

3. Для всех ЧП определяются ПП.

4. Таким образом, на выходе данного этапа -- 2 вектора, компоненты которых упорядочены в соответствии с п.2.3.3:.

1) вектор чисел (целых, дробных) -- ЧП для всех Пж;

2) вектор целых чисел -- аналогично ПП для всех Пж.

3.2. Предварительный отсев вариантов

3.2.1. Алгоритм предварительного отсева следующий.

1) Для каждой пары вариантов (т.е. векторов) выясняем, можно ли считать один из них «лучше». Для этого используем критерий Парето: вариант А лучше варианта В тогда, когда он не хуже по любому показателю и лучше хотя бы по одному. Такое отношение заведомо транзитивно, то есть если А лучше В, а В лучше С, то А лучше С.

2) Находим среди всех вариантов «максимальные». Максимальный вариант -- это такой, который не хуже ни одного другого. После этого все не максимальные отбрасываем. Возможность того, что максимальных вообще не будет, в принципе исключена.

3) Если остался только один вариант -- он и есть лучший. Иначе ищем наилучший среди максимальных. В худшем случае все варианты окажутся максимальными, то есть этот шаг ничего не даст..

3.2.2. Процедура отсева проводится дважды: с использованием векторов ЧП и с использованием векторов ПП. Варианты, отсеянные на первом шаге, на второй уже не проходят. Такой порядок позволяет избежать некоторых нежелательных ситуаций.

3.2.3. Нужно отметить, что здесь мы сравниваем ВР по объективным критериям. Действительно, если нужно поменьше окон, то 3 окна хуже, чем 2, и т. д.

Про любые два ВР, успешно прошедшие отсев, всегда можно сказать, что один в чем-то лучше второго, а второй -- чем-то лучше первого.

3.3. Выбор лучшего варианта

Необходимо отметить, что здесь мы имеем дело с субъективными оценками, отражающими практический опыт пользователя по вопросу «какое из зол выбрать».

Имеется несколько подходов.

3.3.1. На основе интегрального показателя несоответствия пожеланиям

Для каждого варианта расписания ВР вычисляется некоторый интегральный показатель ИП на основе вектора ЧП или ПП. Как правило, ПП, так как ЧП измеряются в различных единицах.

Лучший тот ВР, у которого ИП наименьший.

В самом простом варианте ИП -- это просто сумма ПП по всем Пж.

Возможно, например ИП = maх((ПП).

Возможны другие варианты, они легко реализуются.

Недостаток такого подхода заключается в следующем.

1) Он подразумевает, что показатели качества расписания, с одной стороны, независимы, с другой стороны, недостаток в одном можно компенсировать хорошим качеством в другом. Отчасти это так и есть, но далеко не всегда.

2) Суммируя порядковые величины мы рискуем допустить умозаключение типа «Три двоечника знают вместе лучше, чем один отличник».

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

3.3.2. На основе попарного сравнения вариантов

Такой подход позволяет лучше учесть именно субъективные предпочтения пользователя. Сопоставляя 2 (а не много) вариантов, человек, как правило может действовать более уверенно, так задача более-менее обозрима.

Наиболее подходящим представляется метод Саати. Его использование выглядит следующим образом.

1) Эксперт (пользователь) сравнивает варианты попарно и определяет кто кого лучше и насколько. «Насколько» определяется целым числом от 1 (практически равноценны) до 9 (один лучше другого по всем статьям). В нашем случае варианты огромного превосходства маловероятны после предварительного отсева.

2) Далее уже в автоматическом режиме программа ранжирует сравниваемые варианты и оценивает каждый положительным числом не более 1 (оценка 1 означает, что данный вариант -- абсолютный лидер). Это позволяет определить не только лучший вариант, но и насколько он превосходит ближайших конкурентов. Если оценки противоречивы, это отслеживается автоматически.

3.3.3. С использованием машинного обучения

Если у нас есть прецеденты, когда при попарном сравнении принималось решение, какой ВР лучше и насколько, то естественно использовать эту информацию в дальнейшем.

Для этого нужно, во-первых, все прецеденты хранить.

Далее, нужно построить нейронную сеть (НС), обучать её на прецедентах и далее доучивать при появлении новых. Сеть будет подражать пользователю, отражая «невольно» его предпочтения. В дальнейшем можно разгрузить пользователя от работы по «ручному» сравнению ВР, так как сеть будет «думать так же».

В случае, если мы используем метод Саати, НС будет иметь 9 выходов и столько входов, сколько у нас пожеланий.

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

4. Формальная модель

Формальная модель определяет способы выражения пожеланий (критериев качества расписания) в терминах функций, множеств, логики, лингвистический переменных.

4.1. Типы объектов

4.1.1. Записи

См. п.2.2.

4.1.2. Скаляры

1) арифметические

2) порядковые (например, номер пары или дня недели)

3) логические (T / F)

4) номинативные, например, номер аудитории, ФИО преподавателя (их коды, на самом деле)

4.1.3. Наборы

1) М1: Множество записей

2) М2: Множество множеств типа М1/М4 или М2

3) М3 (образ): Набор скаляров какого-то определенного типа (возможны повторы). Элементы набора находятся во взаимно-однозначном соответствии с элементами какого-то множества типа М1 или М2. То есть попросту мы для всех элементов множества вычислили какой-то показатель и сформировали набор. Например: М1 -- множество преподавателей определенной кафедры. Образ -- набор чисел: недельной нагрузки преподавателей. Значения нагрузки могут совпадать, но за каждым преподавателем закреплено определенное значение.

Образ не является множеством, так как возможны повторы. Практически, например, реляционная таблица с идентификатором объекта и одним полем -- значением показателя.

Ниже об Образе говорится более подробно.

4) М4: Набор скаляров какого-то типа.

4.1.4. Условия

1) Типа У1: условие выделения подмножества. Например,

Преп = Сидоров И Предмет = Базы данных

2) Типа У2: условие объединения объектов в подмножество. Например: Преп = const

4.1.5. Диапазоны допустимых значений.

Просто пара чисел.

4.1.6. Лингвистические значения, шкалы и измерители нежелательности

4.1.6.1. Лингвистические значения (ЛЗ) -- это просто слова/словосочетания естественного языка, используемые для субъективного («человеческого») оценивания каких-то ситуаций. Например, «замечательно», «очень плохо» и т.д.

Лингвистическая шкала -- упорядоченное множество из двух или более ЛЗ. Например: {нежелательно, плохо, совсем плохо}.

4.1.6.2. Вводится понятие Общая лингвистическая шкала (ОЛШ). В ней пользователь отражает все градации нежелательности, которые он практически для себя использует при сравнении различных вариантов («какое зло меньше»).

Самое левое/первое ЛЗ (наименее нежелательной) является «Практически не имеет значения» или что-то равное по смыслу, то есть недочет, на который вполне можно закрыть глаза. Далее по возрастанию нежелательности. Последнее ЛЗ, вероятно, означает нечто вроде «Формально пригодно, но практически- нет».

Элементы ОЛШ нумеруются по порядку целыми числами 0, 1, 2,… Эти числа образуют Общую порядковую шкалу (ОПШ). Между элементами ОЛШ и ОПШ, таким образом, имеется взаимно однозначное соответствие.

4.1.6.3. Измеритель нежелательности служит для перевода числового показателя (ЧП )в лингвистическую и, далее, порядковую шкалу.

Для каждого Пж и его ЧП выбирается некоторое подмножество ОПШ, получаем локальную порядковую шкалу (ЛПШ). Множество возможных значений ЧП разбивается на столько интервалов, сколько ПП в ЛПШ и сопоставляем каждый интервал определенному ПП. Эта последовательность пар (ЧП, ПП) и представляет собой Измеритель нежелательности (ИН) для данного Пж.

Например.

Допустим, пользователь определил такую шкалу (ОЛШ / ОПШ):

{ ( 0 / нормально), (1 / ничего страшного), (2 / многовато), (3 / довольно плохо), … (10 / недопустимо плохо)}

Допустим далее, ЧП -- максимальное количество окон у преподавателей кафедр Технологического факультета. Можно получить такой ИН:

{ (1 / 0), (3 / 1), (6 / 3), (20 / 10) },

что можно интерпретировать так:

· одно окно в неделю --нормально (степень неприемлемости - 0),

· 2 или 3 -- ничего страшного (степень неприемлемости - 1),

· 4, 5, 6 -- довольно плохо (степень неприемлемости -- 3; ПП = 2 в данной ЛПШ отсутствует),

· больше 6 (20 -- это заведомо большое число, больше которого всё равно не будет) -- недопустимо плохо (степень неприемлемости -- 10, максимальное значение по нашей ОПШ).

4.2. Функции

При описании функций будут использовать обозначения М1, М2, М3, М4, У1, У2 именно в смысле типа объекта; М -- множество типа М1 или М2.

4.2.1. Интегративные функции

ФИ(М4) -> Скаляр

Результат: отдельный скаляр - какая-то функция от элементов аргумента (интегральная оценка множества). В SQL их, наверное, запасено на все случаи жизни.

Для арифметических: среднее, сумма, …

Для порядковых: МИН, МАКС, РАЗМАХ, м.б.. что-то еще.

Для логических: наверное, только кванторы существования и всеобщности.

Для номинативных: трудно сказать.

4.2.2. Функции над записями

Вычисление значения по параметрам одной записи.

Аргумент -- одна запись.

Результат -- скаляр любого типа.

В частности, просто получение значения какого-то атрибута записи.

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

4.2.3. Функции над множествами

Одна из следующих:

1) определение мощности

2) получение подмножества

3) разбиение на подмножества

4) получение образа

5).получение интегральной характеристики

4.2.3.1. Определение мощности

Мощность (М) -> Число

Например, А -- все занятия Петрова.

К = Мощность(А) // Недельная нагрузка Петрова

4.2.3.2. Получение подмножества

Подмн(М1, У1) -> М1 или Подмн(М2, У1) -> М2

Так как если исходное множество записей/множеств, то и его подмножество -- того же типа.

Например, исходное множество А -- все занятия Петрова. Получаем множество В тех, что ведутся на Технологическом факультете.

В = Подмн(А, “Факультет = ТФ“

или в 2 шага

С = “Факультет = ТФ“ // условие типа У1

В = Подмн(А, С)

4.2.3.3. Разбиение на подмножества

Разб(М, У2) -> М2

Исходное множество (М1 или М2) разбиваем на множество его подмножеств.

Например, А -- все занятия Петрова.

В = Разб(А, “День = const“)

В -- множество из 6 подмножеств, каждое из которых -- множество записей: занятия Петрова в конкретный день недели.

4.2.3.4. Получение образа

Уточним это понятие.

Образ: от всех элементов множества вычисляется какая-то допустимая для него функция и набор значений (привязанных к породивших им элементам) -- это и есть образ множества.

Если элементы множества -- записи, то образ - это набор каких-то характеристик записей.

Например, множество записей: множество занятий Петрова за пятницу. Характеристика каждой записи -- корпус, в котором проводятся занятия. Значит образ -- набор идентификаторов корпусов. Будет содержать столько элементов, сколько пар в этот день, многие могут совпадать. (Кстати, в этом случае интегральную характеристику вычислить невозможно, так как это -- номинативная величина).

Если элементы -- множества, то характеристики этих множеств могут быть:

1) мощность (число),

2) интегральная характеристика (скаляр)

3) подмножество, выделенное по какому-то признаку.

Пример.

Допустим А -- множество записей о всех занятиях Петрова.

Разбиваем его на подмножества по условию День = const. Получаем множество В, состоящее из шести множеств про каждый день: {В1,…, В6}.

Мы можем построить несколько образов множества В. Например:

1) Для каждого элемента (дня) - его мощность. Это будет 6 чисел, показывающие, сколько пар у Петрова в какой день.

2) Для каждого элемента (дня) -- его интегральная характеристика, например -- максимальный номер пары среди всех занятий в этот день. Это нам покажет, когда Петров заканчивает занятия в каждый день. (То есть в принципе для каждого дня будет построен его образ: набор номеров пары для каждой записи. А потом будет вычислена интегральная характеристика -- максимум из этих величин).

3) Для каждого элемента (дня) -- множество записей про занятия на третьем курсе. Где-то оно может быть и пустым. То есть образ будет набором множеств.

Образ(А, Ф) -> Рез,

где А -- множество типа М1 или М2, А = {а1, …, аN}

Ф - функция, которую мы применяем к каждому элементу множества,

Рез -- множество, Рез = {Ф(а1), …, Ф(аN)}

4.2.3.5. Получение интегральной характеристики множества

Интегральная характеристика: сначала строится образ множества, затем на нем вычисляется какое-то скалярное значение. Например, наибольшее, среднее арифметическое и пр. Для этого образ должен состоять из арифметических или порядковых значений. Может реализовываться одной функцией, если это удобнее.

ФМИ(А, Ф, ФИ) -> Скаляр,

где А -- множество типа М1 или М2,

Ф - функция, которую мы применяем к каждому элементу множества,

ФИ -- какая-то интегративная функция.

То же можно достичь в 2 шага

В = Образ(А, Ф) // В -- набор типа М4

К = ФИ(В). // Скаляр.<...