Модели, алгоритмы и программные средства обработки информации и принятия решений при составлении расписаний занятий на основе эволюционных методов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Абухания Амер Ю А

• Абухания Амер Ю А
• кандидат наук
• 2016

Оглавление диссертации кандидат наук Абухания Амер Ю А

ВВЕДЕНИЕ

1. ОБЗОР И АНАЛИЗ МОДЕЛЕЙ, МЕТОДОВ И ПРОГРАММНЫХ КОМПЛЕКСОВ ДЛЯ СОСТАВЛЕНИЯ РАСПИСАНИЙ ЗАНЯТИЙ

1.1 Обзор и анализ постановок, методов и алгоритмов решения задачи составления расписаний занятий

1.2 Обзор автоматизированных систем составления расписаний

занятий

Выводы по главе

2. СИСТЕМНЫЙ АНАЛИЗ, ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ И ИНФОРМАЦИОННОЙ МОДЕЛЕЙ ЗАДАЧИ СОСТАВЛЕНИЯ

РАСПИСАНИЙ ЗАНЯТИЙ

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

2.1.1 Формализация объекта «ресурс»

2.1.2 Формализация объекта «временной интервал»

2.1.3 Формализация объекта «деятельность»

2.1.4 Анализ взаимозависимости учебных групп

2.1.5 Формализация объекта «расписание»

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

2.2.1 Обязательные требования

2.2.2 Статические жесткие ограничения

2.2.3 Динамические жесткие ограничения

2.2.4 Желательные требования (мягкие ограничения)

2.3 Критерий качества расписания

2.4 Общая схема обработки информации при составлении расписаний занятий

2.5 Информационная модель в нотации Information Engineering

Выводы по главе

3. МЕТОДЫ И АЛГОРИТМЫ СОСТАВЛЕНИЯ РАСПИСАНИЙ ЗАНЯТИЙ НА ОСНОВЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА

3.1 Общая схема решения задачи составления расписания учебных занятий вуза

3.2 Эвристический алгоритм построения допустимого расписания путем последовательного размещения учебных единиц

3.3 Локально оптимальная стратегия построения расписания на основе генетического алгоритма

3.3.1 Формулировка задачи последовательной локальной оптимизации

3.3.2 Выбор способа кодирования решений

3.3.3 Разработка класса chromosome_b

3.3.4 Разработка класса population_b

3.3.5 Оператор мутации

3.3.6 Оператор скрещивания

3.3.7 Построение следующей популяции хромосом

3.3.8 Интеграция генетического алгоритма в процедуру локальной оптимизации

3.4 Применение генетического алгоритма для управления локальной оптимизацией

3.4.1 Общая схема гибридизации

3.4.2 Выбор способа кодирования решений

3.4.3 Разработка класса chromosome_p

3.4.4 Разработка класса population_p

3.4.5 Оператор мутации

3.4.6 Операторы скрещивания

3.4.7 Построение следующей популяции хромосом

3.4.8 Интеграция глобального генетического алгоритма в общую схему решения задачи составления расписания занятий

!4 Выводы по главе

4. ВЕБ-ОРИЕНТИРОВАННЫЙ ПРОГРАММНЫЙ КОМПЛЕКС

«РАСПИСАНИЕ»

4.1 Общая архитектура программного комплекса «Расписание» и организация диалога с пользователями

4.2 Создание базы данных программного комплекса

4.3 Разработка объектно-ориентированного вычислительного ядра

программного комплекса

Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. Исходные данные и результаты прогона алгоритмов

решения UCTP для модельного примера

ПРИЛОЖЕНИЕ 2. Операторы кроссовера и мутации для хромосом,

кодируемых перестановками

ПРИЛОЖЕНИЕ 3. Исходные коды программ

ПРИЛОЖЕНИЕ 4. Копия свидетельства о регистрации программы

ПРИЛОЖЕНИЕ 5. Копия документа об использовании результатов

Введение диссертации (часть автореферата) на тему «Модели, алгоритмы и программные средства обработки информации и принятия решений при составлении расписаний занятий на основе эволюционных методов»

ВВЕДЕНИЕ

Актуальность и степень разработанности темы исследования.

Задача составления расписания учебных занятий вуза (University Course Timetabling Problem - UCTP) является типичной проблемой, с которой периодически сталкиваются все университеты мира. Она привлекает внимание математиков и ИТ-специалистов уже достаточно продолжительное время и к настоящему времени сделано большое количество постановок этой задачи, имеющих разную степень строгой математической формализации, предложены различные методы и алгоритмы решения UCTP и разработаны многочисленные информационные системы «Расписание», в том числе и представленные на рынке коммерческие системы. Актуальность поиска эффективных методов и алгоритмов решения UCTP подтверждается фактом проведения с 2002 г. международных соревнований по этой проблематике (International Timetabling Competition). Третье по счету такое соревнование (ITC2011) проводилось в 2011-2012 гг. и на нем было представлено 35 участников из 10 стран.

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

Проблеме атоматического составления оптимальных расписаний занятий посвящены многочисленные диссертационные исследования в России (Лопатеева О.Н., Маслов М.Г., Галузин К.С., Низамова Г.Ф., Милехина Т.В., Асвад Фирас М. и др.) и за рубежом (R. Lewis, M. Marte, H. Larget, M.T. Jensen, C. Mihaila и др.)

Количество публикаций в периодических изданиях и трудах конференций по данной тематике исчисляется тысячами. Для решения UCTP

предлагают использовать: классические методы (теория графов, целочисленное линейное программирование); метаэвристические (эволюционные и генетические алгоритмы, метод имитации отжига -simulated annealing, табу-поиск - tabu search, метод муравьиных колоний - ant colony optimization, максиминная муравьиная система - max-min ant system, оптимизация роем частиц - particle swarm optimization); мультиагентные системы; метод решения по прецедентам.

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

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

В постоянном развитии находится рынок автоматизированных систем составления расписаний занятий, игроками на котором являются даже такие «киты» ИТ-индустрии, как фирма «1С» со своей разработкой «1С: Автоматизированное составление расписания. Университет». Верхние

строчки мировых рейтингов занимают также такие зарубежные разработки, как Lantiv Scheduling Studio 7 (Израиль) и OROLOGIO 13.x (Греция).

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

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

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

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

Задачи диссертационной работы:

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

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

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

3) Обосновать интегральный критерий качества расписания, составляющими которого являются количественные оценки меры нарушения мягких ограничений, «взвешенные» нормирующими множителями. Реализовать в виде завершенного программного модуля алгоритм оценки качества расписания, допускающий его использование на различных этапах решения оптимизационной задачи составления расписания.

4) Сформулировать задачу последовательной локальной оптимизации расписания; разработать и программно реализовать алгоритм ее решения, основанный на гибридизации «жадного» и генетического алгоритмов.

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

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

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

Научная новизна. В диссертации получены следующие новые научные и практические результаты:

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

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

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

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

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

- предложены оригинальные модификации генетических операторов скрещивания для двух способов кодирования хромосом (двоичного кодирования и кодирования перестановками);

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

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

Теоретическая значимость диссертационной работы:

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

что позволяет одновременно строить математическую, информационную и алгоритмическую модели задачи;

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

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

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

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

Практическая значимость диссертационной работы:

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

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

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

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

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

- результаты диссертационной работы используются в высших учебных заведениях Ирака (Al-Furat Al-Awsat Technical University, Babylon Technical Institute) при составлении расписаний занятий;

- результаты диссертационной работы могут быть использованы при реализации магистерских программ и программ обучения в аспирантуре по направлениям подготовки 09.04.01, 09.06.01 «Информатика и вычислительная техника», 09.04.04 «Программная инженерия», 02.04.03 «Математическое обеспечение и администрирование информационных

систем», 02.06.01 «Компьютерные и информационные науки», 01.04.04 «Прикладная математика».

Методология и методы исследования. Для решения поставленных в работе задач использованы: методы системного анализа, методы математического моделирования, теория графов, структуры и базы данных, методы поисковой оптимизации, теория реляционных отношений, эволюционные и генетические алгоритмы, методы обобщенного и объектно-ориентированного программирования, методы построения многозвенных программных приложений с веб-интерфейсом. Для практической реализации результатов исследований использованы продукты мирового лидера -компании Microsoft: сервер баз данных Microsoft SQL Server, веб-сервер IIS, технологии ASP.NET и ADO.NET, фреймворк MVC, среда разработки Visual Studio, а также языки программирования С++ и C#.

Положения, выносимые на защиту:

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

2) математическая, информационная и алгоритмическая модели задачи составления расписания занятий;

3) метод и алгоритм решения задачи составления расписания занятий, использующий схему «двойной гибридизации» для генетического и «жадного» алгоритмов;

4) модификации генетических операторов скрещивания и мутации;

5) реализация вычислительного ядра программного комплекса с использованием парадигм обобщенного и объектно-ориентированного программирования.

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

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

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

- II Международная научная конференция преподавателей, аспирантов, магистров и студентов вузов «Наука. Образование. Культура: вклад молодых исследователей» (г. Новочеркасск, ЮРГПУ(НПИ), 23-24 апреля 2013 г.)

- Международные научно-практические конференции «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» (г. Новочеркасск, ЮРГПУ(НПИ), 2014 и 2015 гг.)

- "The first international conference of Information Technology In Yemen" / Saba Journal of Information Technology and Networking (SJITN) is a peer-reviewed international journal, published under the Faculty of Computer and Information Technology at Saba University in Yemen (Sana'a, 2014)

Кроме того, результаты диссертационного исследования регулярно размещаются для обсуждения на персональной странице автора на Интернет-площадке «Социальная сеть для учёных» (https://npi-tu.academia.edu/AmEr ).

Глава 1. Обзор и анализ моделей, методов и программных комплексов для составления расписаний занятий

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

1.1 Обзор и анализ постановок, методов и алгоритмов решения задачи

составления расписаний занятий

Задача составления расписаний учебных занятий вуза (University Course Timetabling Problem - UCTP) привлекает внимание математиков и ИТ-специалистов уже достаточно продолжительное время. К настоящему времени сделано большое количество постановок этой задачи, имеющих разную степень строгой математической формализации, предложены различные методы и алгоритмы решения UCTP и разработаны многочисленные информационные системы «Расписание», в том числе и представленные на рынке коммерческие системы. Актуальность задачи поиска эффективных методов и алгоритмов построения расписаний занятий доказывается фактом проведения с 2002 г. международных соревнований по этой проблематике (International Timetabling Competition) [1]. Третье по счету такое соревнование (ITC2011) проводилось в 2011-2012 гг. [2]. На нем было представлено 35 участников из 10 стран.

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

В диссертации и статьях Лопатеевой О.Н. [3, 4, 5] UCTP формулируется как задача распределения ресурсов для множества работ, которые, в свою очередь, размещаются на временной сетке. Работа - это пара "учебная дисциплина (г) + вид занятия (у)", требующая для своего выполнения тройку ресурсов "преподаватель (р) + учебная группа + аудитория (а)". Работы вместе с ресурсами размещаются в часовой сетке расписания (матрице) «день недели (с!), учебная пара (/)». Для каждого ресурса задан «календарь доступности» - список ячеек сетки расписания, для которых ресурс доступен (например, преподватель присутствует в вузе). Факт распределения фиксируется мультииндексными булевыми переменными хрС/, хё!/ и хаС/, которые позволяют учесть 3 "жестких" ограничения, связанные с занятостью определенного ресурса в определенный отрезок времени (совместимостью ресурсов по времени). С использованием этих переменных сформулированы 4 критерия оптимальности (минимизация "окон" у преподавателей и студенческих групп и минимизация потерь от переходов между учебными корпусами преподавателей и студенческих групп для смежных учебных пар) и одно ограничение в форме равенства (весь недельный учебный план должен быть выполнен). Доказана КР-полнота иСТР. Предложены эвристики для «жадного» алгоритма последовательного распределения работ и ресурсов. Разработана информационная модель (база данных) и выполнена программная реализация в виде системы.

В диссертации Маслова М.Г. [6] выполнена детальная формализация иСТР с описанием всех сущностей (преподаватели, учебные группы, аудитории, учебные дисциплины, временные интервалы и др.) и связей между ними. Рассмотрены 11 обязательных ограничений и 11 желательных требований, из которых конструируется критерий оптимальности расписания. В итоге иСТР сформулирована как задача нелинейного булева программирования с ограничениями и критериями в виде формул исчисления предикатов. Обсуждается проблема КР-полноты иСТР. Для решения задачи предлагается использовать эвристические методы (для

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

В диссертации Галузина К.С. [7] параметры иСТР вводятся обычным образом через определение ресурсов: множества преподавателей Т, учебных групп О и аудиторий Я, а также задание часовой сетки расписания В для планируемого периода (которая в этой формулировке задается не матрицей, а вектором, образованным конкатенацией строк матрицы) и учебного плана Ь, перечисляющего все занятия всех видов для всех учебных групп на планируемый период (одну или две недели). Для каждого вида ресурсов задается «календарь доступности», разрешеющий использовать данный ресурс в указанный временной интервал. Отличительной особенностью данной постановки задачи является введение «обобщенных» преподавателей, «обобщенных» учебных групп и «обобщенных» аудиторий для учета деления академических групп на подгруппы и объединения групп в потоки. Вектор решения задачи (т.е. расписание) задается множеством пар «занятие из учебного плана, номер ячейки часовой сетки расписания». В этой работе также формулируются жесткие и нежесткие (мягкие) ограничения, причем для последних применяется аппарат нечетких множеств (функции принадлежности). Построены два обобщенных критерия оптимальности расписания, являющиеся взвешенной аддитивной сверткой двух множеств частных критериев: учитывающих интересы студентов и учитывающих интересы преподавателей. При построении критериев также используется аппарат нечетких множеств. Вводятся понятия множества допустимых расписаний и множества Парето-оптимальных (по отношению к двум

обобщенным критериям) расписаний. Предложен гибридный алгоритм построения оптимального решения UCTP, состоящий из трех этапов:

1) Построение множества допустимых расписаний методами распространения ограничений с применением эвристики.

2) Оптимизация на полученном множестве методом стохастического поиска (с использованием эволюционной стратегии).

3) Поиск распределения аудиторий в найденном расписании по времени с помощью метода ветвей и границ.

Выполнена программная реализация в 2-звенной архитектуре «клиент-сервер».

В диссертации и статьях R. Lewis [8, 9, 10, 11] выполнена наиболее последовательная и полная формализация UCTP как задачи размещения заданного множества мероприятий (учебных занятий) E в ячейках матрицы RxT, где R - множество аудиторий (rooms) и T - множество учебных пар (таймслотов, timeslots) в планируемом периоде (рис. 1.1). При этом аудитории имеют заданную вместимость, а для каждого мероприятия указаны преподаватель и студенты.

•- time* 123456789 Jots » 10 11 12 13 14... -\

р rooms m-1 ▼ ni 7

11 8 IS

12 2 14

3 $

1 16 4 20 Г -V J

10 6

17 5 9 13

18 19

^ J Y Day

Y F Day 1 c kn "eod-of-ay" tmeslot 2

Рисунок 1.1 - Принцип распределения мероприятий по таймслотам и

аудиториям (рисунок из [8])

Между множеством студентов S и множеством мероприятий E существует отношение "многие-ко-многим", вследствие чего некоторые пары мероприятий являются потенциально конфликтующими, если хотя бы один студент должен посещать оба мероприятия. Еще одно отношение "многие-ко-многим" имеется между множеством аудиторий R и множеством мероприятий E, обусловленное предпочтительностью определенных аудиторий для определенных мероприятий (аудитории для лекционных потоков, компьютерные классы, химические лаборатории и пр.). Вводится понятие допустимого расписания (feasible timetable), в котором для каждого мероприятия назначена одна аудитория, один таймслот и выполнены "жесткие" ограничения (hard constraints):

1) Конфликтующие по студентам мероприятия не должны быть распределены в один таймслот.

Список литературы диссертационного исследования кандидат наук Абухания Амер Ю А, 2016 год

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1. Paechter, B., Gambardella, L. M., & Rossi-Doria, O. (2002). The first international timetabling competition. http://www.idsia.ch/Files/ttcomp2002/ .

2. Gerhard Post, Luca Di Gaspero, Jeffrey H. Kingston, Barry McCollum & Andrea Schaerf (2013). The Third International Timetabling Competition. http://www.cs.sfu.ca/~mitchell/cmpt-827/2015-Fall/Proiects/TT-ITC-2011-Report.pdf/ .

3. Лопатеева О.Н. Система автоматизированного формирования учебного расписания в высшем учебном заведении на основе эвристических алгоритмов : Дис. ...канд. тенх. наук : 05.13.01 / Лопатеева Ольга Николаевна - Красноярск, 2006. - 205 с.

4. Воробович Н.П., Лопатеева О.Н. Математическая модель, алгоритмы и структуры данных для задачи формирования расписания занятий в вузе / Н.П. Воробович, О.Н. Лопатеева // Вестник Красноярского государственного университета. Гуманитарные, естественные и физико-математические науки.- 2006.- №4.- С. 27-35. -URL:http://library.krasu.ru/ft/ft/ articles/0112305.pdf .

5. Воробович Н.П. О NP-полноте задач формирования расписания в вузе / Н.П. Воробович, О.Н. Лопатеева // Вестник Крас. ГАУ / Красноярский гос. аграр. ун-т. - 2006. - Вып.11. - С. 385-391.

6. Маслов М. Г. Разработка моделей и алгоритмов составления расписаний в системах административно-организационного управления : Дис. .канд. тенх. наук : 05.13.18 / Маслов Михаил Геннадьевич. - М., 2004. - 217 с.

7. Галузин К. С. Математическая модель оптимального учебного расписания с учетом нечетких предпочтений : Дис. .канд. физ.-мат. наук : 05.13.18 / Галузин Константин Станиславович. - Пермь, 2004. - 148 с.

8. Lewis R. Metaheuristics for University Timetabling Problem : doctoral thesis / Rhydian Lewis ; Napier University . - Edinburgh, 2002. - 180 p.

9. Lewis R., Paechter B. New Crossover Operators for Timetabling with Evolutionary Algorithms / Rhydian Lewis, and Paechter // Centre for Emergent Computing, School of Computing, Napier University, Edinburgh.

10. Lewis, R., and B. Paechter. (2007) Finding Feasible Timetables Using Group-Based Operators. IEEE Transactions on Evolutionary Computation, vol. 11(3), pp. 397-413.

11. Lewis, R. and B. Paechter (2005). Application of the Grouping Genetic Algorithm to University Course Timetabling. In Evolutionary Computation in Combinatorial Optimisation (Lecture Notes in Computer Science vol. 3448), J. Gottlieb and G. Raidl (Eds.), Berlin: Springer-Verlag, pp. 144-153. URL: http://www.rhydlewis.eu/papers/EvoCop2005.pdf

12. E. Falkenauer. Genetic Algorithms and Grouping Problems, Wiley, Chichester, 1998.

13. Wangmaeteekul P. Using Distributed Agents to Create University Course Timetables Addressing Essential & Desirable Constraints and Fair Allocation of Resources : doctoral thesis / Pennee Wangmaeteekul; Durham University. -Durham, 2011. - 178 p.

14. Wangmaeteekul, P. and Budgen, D. 2011. Using Agents to Create a University Timetable Addressing Essential & Desirable Constraints and Fair Allocation of Resources. In Proceeding on IADIS International Conference Intelligent Systems and Agents 2011.

15. Marte, M. Models and Algorithms for School Timetabling - A Constraint-Programming Approach : Dissertation an der Fakultät für Mathematik, Informatik und Statistik / Michael Marte ; Ludwig-Maximilians-Universität. - München, 2002. - 127 p.

16. Низамова Г. Ф. Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов: автореф. дис. ...канд. тенх. наук : 05.13.11 / Низамова Гузель Фанисовна. - Уфа, 2006. - 19 с.

17. Кабальнов Ю.С., Шехтман Л.И. Композиционный генетический алгоритм составления расписания учебных занятий / Ю.С. Кабальнов, Л.И. Шехтман, Г.Ф. Низамова, Н.А. Земеченкова // Научные статьи и доклады, информационные технологии, Уфа: Вестник УГАТУ.- 2006

18. Милехина Т. В. Повышение эффективности кластерных систем обработки информации при решении оптимизационных задач (на примере задачи составления расписания занятий): автореф. дис. .канд. тенх. наук : 05.13.01 / Милехина Татьяна Викторовна. - М., 2011. - 23 с.

19. Асвад Ф. М. Модели составления расписания занятий на основе генетического алгоритма на примере вуза Ирана : автореф. дис. .канд. тенх. наук : 05.13.17 / Асвад Фирас М. - Воронеж, 2013. - 16 с.

20. Chohan O. University Scheduling using Genetic Algorithm / Ossam Chohan. Department of Computer Engineering, Dalarna University / Master Thesis Nr: E3719D , 2009. - 58 p.

21. Lovelace A. L. On the complexity of scheduling university courses : diss. Master of Science in Computer Science / April Lin Lovelace. California Polytechnic State University, San Luis Obispo. - March 2010. - 105 p.

22. Ramirez E. R. Using genetic algorithms to solve high school course timetabling problems : diss. Master of Science in Computer Science / Eugene Ruben Ramirez. San Diego State University. - 2010. - 57 р.

23. Заманова Э.Э. Модель системы принятия решений при составлении учебного расписания [электронный ресурс] / Э.Э. Заманова // Системы обработки информации. - 2011. - № 7(97). - C. 12-15. -http://archive.nbuv.gov.ua/portal/natural/soi/2011 7/0 Zaman.pdf.

24. Безгинов А.Н., Трегубов С.Ю., Комплекс алгоритмов построения расписания вуза. Система, оценка качества расписания на основе нечетких множеств, особенности алгоритма поиска оптимального расписания / А.Н. Безгинов, С.Ю. Трегубов // Вестник Балтийского государственного университета им. И. Канта.- 2011.- Ч. 1, Вып. 5.- С. 127 - 135.-

URL:http://journals.kantiana.ru/upload/iblock/d92/qxgafedeezduusyz%20to.%20v x.,%20grbvtunwheeybkzh%20pc.%20lt..pdf .

25. Дворянкин А.М. Обзор методов составления расписания вузов/ А.М. Дворянкин, В.С. Чалышев // Изв. ВолгГТУ. Серия Актуальные проблемы управления, вычислительной техники и информатики в технических системах: межвуз. сб. науч. ст. / ВолгГТУ.- Волгоград, 2011. - Вып. 11, № 9. -С. 110-113.- URL: http://www.vstu.ru/kafedry/poas/publikatsii.html .

26. Семенов С. П. Сравнительный анализ подходов к автоматизации составления расписаний учебных занятий в образовательных учреждениях / С.П. Семенов, Я.Б. Татаринцев // Изв. Алтайского гос. ун-та. - 2010. - № 1(65). -С. 103-105.

27. Ерунов В.П. Формирование оптимального расписания учебных занятий в вузе / В.П. Ерунов, И.И. Морковин // Вестник ОГУ. - 2001. № 3. - С. 55-63.

28. Завьялов А.М. Автоматизация задачи составления учебного расписания [электронный ресурс] / А.М. Завьялов, А.В. Новиков // Системный анализ в науке и образовании : электрон. журн. - 2009. - № 1. -URL:http://www.sanse .ru/archive/12

29. Клеванский Н.Н. Формирование расписания занятий высших учебных заведений/ Н.Н.Клеванский// Образовательные ресурсы и технологии-2015'1(9) - С. 34-44 - URL:https://www.muiv.ru/vestnik/pdf/pp/ot 2015 1 34-44.pdf

30. Попов Г.А. Формализация задачи составления учебного расписания в высшем учебном заведении / Г.А. Попов // Журнал Вестник Астраханского государственного технического университета. - 2006.- Вып. № 1. -URL:ttp://cyberleninka.ru/article/n/formalizatsiya-zadachi-sostavleniya-uchebnogo-raspisaniya-v-vysshem-uchebnom-zavedenii .

31. Chen R.M., Shih H.F. Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search / R.M. Chen, H.F. Shih // Algorithms ISSN 1999-4893. - 2013. - pp 227 - 244 URL:http://www.mdpi.com/1999-4893/6/2/227/pdf.

32. Nanda A., Pai M.P., Gole A. An Algorithm to Automatically Generate Schedule for School Lectures Using a Heuristic Approach/ A.Nanda, M.P. Pai., A. Gole // International Journal of Machine Learning and Computing,Vol. 2, No.4, August 2012 - URL: http://www.ijmlc.org/papers/174-L031.pdf

33. Aldasht M.M. University course scheduling using parallel multi-objective evolutionary algorithms / M. M. Aldasht, M. H. Saheb, I. Najjar, M. H. Tamimi, T. O. Takruri // Journal of Theoretical and Applied Information Technology. - 2010. Vol 22. No. 2. - pp. 129-136. - URL: http://www.jatit.org/volumes/research-papers/Vol22No2/8Vol22No2.pdf .

34. Oluwasefunmi T. A. A Genetic Algorithm Approach for a Real-World University Examination Timetabling Problem / Oluwasefunmi T. Arogundade, Adio T. Akinwale, Omotoyosi M. Aweda // International Journal of Computer Applications. - 2010. - Vol. 12, No.5, December 2010. - 4 p. - URL: http://www.ijcaonline.org/volume12/number5/pxc3872083.pdf

35. Erben W, Keppler J. A genetic algorithm solving a weekly course-timetabling problem. / W. Erben, J. Keppler // First International Conference Edinburgh, U.K., August 29 - September 1, 1995. - Selected Papers, 1996. - pp 198 - 211. - URL: http://link.springer.com/chapter/10.1007%2F3-540-61794-9 60#page-1

36. Socha K. Ant Algorithms for the University Course Timetabling Problem with Regard to the State-of-the-Art / K.Socha, Michael Sampels, and Max Manfrin//IRIDIA, Universit'e Libre de Bruxelles, CP 194/6. - URL: http://www.metaheuristics.net/downloads/ttantcmp03.pdf.

37. Sandeep S.K. A Timetable prediction for technical educational system using genetic algorithm / S.K Sandeep, R Lakshmi //Journal of Theoretical and Applied Information Technology-2005-2010, JATIT. URL: http://www.jatit.org/volumes/research-papers/Vol13No1/8Vol13No1.pdf.

38. Aycan E., Ayav T .Solving the Course Scheduling Problem Using Simulated Annealing/ E. Aycan.,T. Ayaw//Department of Computer Engineering,Izmir Institute of Technology -URL:http://www.iyte.edu.tr/~tolgaayav/papers/Aycan CourseSch.pdf .

39. Ross P. Successful Lecture Timetabling with Evolutionary Algorithms / Peter Ross, Dave Corne, Hsiao-Lan Fang// Department of Arti cial Intelligence University of Edinburgh, , (1994). revised version to appear in Applied Intelligence.-URL:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.8945&rep=rep1&typ e=pdf .

40. Sadaf Naseem Jat, Shengxiang Yang. A Guided Search Genetic Algorithm for the University Course Timetabling Problem / N.J Sadaf, Yang S // Department of Computer Science, University of Leicester- Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2009) 10-12 August 2009, Dublin, Ireland - URL: http://www.cs.le.ac .uk/~syang/Papers/MISTA09.pdf.

41. S andor Gy'ori Zolt an Petres Annam aria R. V arkonyi-K oczy. Genetic Algorithms in Timetabling. A New Approach./ G S'andor., P Zoltan., Annam'aria R. V'arkonyi-K'oczy // Budapest University of Technology and Economics Department of Measurement and Information SystemsURL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.21.8056&rep=rep 1&type=pdf.

42. Jonathan Domrös, Jörg Homberger. An Evolutionary Algorithm for High School Timetabling/ D Jonathan, H Jörg// Practice and Theory of Automated Timetabling (PATAT 2012), 29-31 August 2012, Son, Norway, URL: http://www.patatconference.org/patat2012/proceedings/5 2.pdf.

43. Spyros Kazarlis, Vassilios Petridis and Pavlina Fragkou. Solving University Timetabling Problems Using Advanced Genetic Algorithms/ P. Kazarlis, V.

TH

Petridis, P. Fragkou // 5 International conference on technology and automation, October 15-16, 2005, Thessaloniki, Greece, Proceedings of the ICTA'05. URL:http://icta05.teithe.gr/papers/24.pdf.

44. S. Daskalaki, T. Birbas, E. Housos. An integer programming formulation for a case study in university timetabling/ Daskalaki S., Birbas T., Housos E// European Journal of Operational Research 153 (2004) 117-135,URL:

http://www.opt.math.tugraz.ac.at/~cela/Vorlesungen/MathOptSS13/Miniprojekt/Ti metablingDaskalaki04 .pdf.

45. Ms. Premlata A. Sonawane, Dr.Leena Ragha. Hybrid Genetic Algorithm and Tabu Search Algorithm to Solve Class Time Table Scheduling Problem/ Premlata Ms. Sonawane A., Dr.Leena Ragha //International Journal of Research Studies in Computer Science and Engineering (IJRSCSE) Volume. 1, Issue 4, August 2014, PP 19-26 ISSN 2349-4840 (Print) & ISSN 2349-4859 (Online) www.arcjournals.org,URL: https://www.arcjournals.org/pdfs/ijrscse/v1-i4/3.pdf.

46. Naveen kumar, Karambir, Rajiv Kumar. A Comparative Analysis of PMX, CX and OX Crossover operators for solving Travelling Salesman Problem/ kumar N, Karambir, Kumar R // International Journal of Latest Research in Science and Technology ISSN (Online):2278-5299 Vol.1, Issue 2 : Page No. 98-101, July-August (2012) URL: https://www.mnkjournals.com/ijlrst files/Download/Vol%201%20Issue%202/303-%20Naveen.pdf.

47. Anirudha Nanda, Manisha P. Pai, and Abhijeet Gole . An Algorithm to Automatically Generate Schedule for School Lectures Using a Heuristic Approach/Anirudha Nanda, Manisha P. Pai, and Abhijeet Gole// International Journal of Machine Learning and Computing, Vol. 2, No.4, August 2012 - URL: http://www.ijmlc.org/papers/174-L031.pdf

48. Kusum Deep, Hadush Mebrahtu. Variant of partially mapped crossover for the Travelling Salesman problems/ K. Deep, H.A. Mebrahtu // International Journal of Combinatorial Optimization Problems and Informatics. - Vol. 3, N.1. - 2012. - pp. 47-69. EDITADA. ISSN: 2007-1558. URL: http://ijcopi.org/ojs/index.php?journal=ijcopi&page=article&op=view&path[]=74 &pathn=135.

49. Samuel Lukas, Arnold Aribowo and Milyandreana Muchri. Solving Timetable Problem by Genetic Algorithm and Heuristic Search Case Study: Universitas Pelita Harapan Timetable/ S. Lukas, A. Aribowo, M. Muchri // Real-World Applications of Genetic Algorithms, Dr. Olympia Roeva (Ed.), ISBN: 978-953-51-0146-8,

InTech, DOI: 10.5772/36626. Available URL: http://cdn.intechopen.com/pdfs-wm/30303.pdf.

50. Teddy Wijaya, Ruli Manurung. Solving University Timetabling As a Constraint Satisfaction Problem with Genetic Algorithm/ W Teddy, M Ruli // Faculty of Computer Science, University of Indonesia, Journal Proceedings of the International Conference on Advanced Computer Science and Information Systems (ICACSIS 2009), Depok- 2009 URL: http://www.academia.edu/2876050/Solving University Timetabling As a Constr aint Satisfaction Problem with Genetic Algorithm

51. Ghaemi S., Vakili M.T. Using a genetic algorithm optimizer tool to solve University timetable scheduling problem / S. Ghaemi, M.T. Vakili // Signal Processing and Its Applications, 2007. ISSPA 2007. 9th International Symposium on, pp. 12-15 Feb. 2007. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.4&rep=rep1 &type=pdf.

52. Meysam S.K., Mohammad S,A. Hybrid Genetic Algorithms for University Course Timetabling / S.K. Meysam, S.A. Mohammad // IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 2, No 2, March 2012 ISSN (Online): 16940814 - URL:http://ijcsi.org/papers/IJCSI-9-2-2-446-455.pdf.

53. Omar Ibrahim Obaid, MohdSharifuddin Ahmad, Salama A. Mostafa, Mazin Abed Mohammed. Comparing Performance of Genetic Algorithm with Varying Crossover in Solving Examination Timetabling Problem/ Omar I.O, MohdSharifuddin A., Salama A.M., Mazin A.M. // Journal of Emerging Trends in Computing and Information Sciences- VOL. 3, NO.10, Oct 2012 ISSN 2079-8407,URL:http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.454.570&rep =rep1&type=pdf.

54. Pawel Myszkowski, Maciej Norberciak. Evolutionary algorithms for timetable problems/ Myszkowski P., Norberciak M // Annales Universitatis Mariae Curie-Sklodowska, Sectio AI, Informatica, Vol. 1 (2003), s. 115-125. URL: http://dlibra.umcs.lublin.pl/Content/17284/zip/ .

55. Liviu Lalescu, Costin Badica. An evolutionary approach for school timetabling / Liviu Lalescu, Costin Badica//University of Craiova, Faculty of Control, Computers and Electronics Vol-II, pp 114-120. July 2-5, 2003 - URL: http:// software.ucv.ro/~cbadica/ cercetare/papers/ cscs14.pdf.

56. Nawat N, Supachate I. A Novel Approach of Genetic Algorithm for Solving University Timetabling Problems: a case study of Thai Universities/ N Nawat, I Supachate // 7th WSEAS International Conference on APPLIED COMPUTER SCIENCE, Venice, Italy, November 21-23, 2007, pp. 242-252. URL: http://www.wseas.us/e-library/conferences/2007venice/papers/600-482.pdf.

57. Ruey-Maw Chen, Hsiao-Fang Shih. Solving University Course Timetabling Problems Using Constriction Particle Swarm Optimization with Local Search/ Ruey-Maw Chen, Hsiao-Fang Shih // Algorithms 2013, 6, 227-244; URL: http://www.mdpi.com/1999-4893/6/2/227/pdf.

58. Shu-Chuan Chu, Yi-Tin Chen. Timetable Scheduling Using Particle Swarm Optimization/Shu-Chuan Chu, Yi-Tin Chen// 1 Conference: Innovative Computing, Information and Control, 2006. ICICIC '06. First International Conference on, Volume: 3 - URL: http://www.researchgate.net/publication/224647262 Timetable Scheduling Using

Particle Swarm Optimization

59. Najet A, Salah B. A, Noureddine E. Evolutionary Potential Timetables Optimization by Means of Genetic and Greedy Algorithms/ Najet A, Salah B. A, Noureddine E// Dept. Electr, Ecole Nat. d'Ingenieurs de Tunis, Conference: Information Intelligence and Systems, 1999. Proceedings. 1999 International Conference on Source: IEEE Xplore - URL: https://www.researchgate.net .

60. Branimir Sigl, Marin Golub, Vedran Mornar. Solving Timetable Scheduling Problem by Using Genetic Algorithms/ B Sigl, M Golub, V Mornar // Information Technology Interfaces, 2003. ITI 2003. Proceedings of the 25th International Conference on, 16-19 June 2003, pp 519 - 524.

61. Tomás Müller. Some Novel Approaches to Lecture Timetabling/ Tomás Müller // Charles University, Faculty of Mathematics and Physics, Malostranské námestí 2/25, CPDC'2002.

62. Tomás Müller. University Course Timetabling & Student Sectioning System/ Tomás Müller, Keith Murray, Stephanie Schluttenhofer// Space Management and Academic Scheduling, Purdue University 400 Centennial Mall Drive, West Lafayette, IN 47907-2016, USA URL: http://www.unitime.org/papers/icaps07.pdf.

63. Белоусов А. И., Ткачев С. Б. Дискретная математика: Учебник для вузов / Под редакцией В. С. Зарубина, А. П. Крищенко. - 3-е издание. - М.: Изд. МГТУ им. Н. Э. Баумана, 2004. - 744 с.

64. John D. Cook. Multi-index notation. - September 18, 2008. - URL: http://www.johndcook.com/multi index.pdf

65. Hugh Darwen. An Introduction to Relational Database Theory. 3rd edition (2012) Hugh Darwen & bookboon.com . p. 239

66. Hugh Darwen. Exercise Book for An Introduction to Relational Database Theory. (2011) Hugh Darwen & bookboon.com . p. 85

67. Jeffrey David Ullman. Database Systems: The Complete Book (with H. GarciaMolina and J. Widom), Prentice-Hall, Englewood Cliffs, NJ, 2002.

68. Elmasri Ramez. Fundamentals of database systems / Ramez Elmasri, Shamkant B. Navathe. - 6th ed. - 2012. - 1201p.

69. Date C. J., Hugh Darwen. Database explortations / Essays on the third manifesto and related topics, revision 2, October 2013. - 544p.

70. Ahmed Yusuf Almulla. Translating between SQL and Tutorial D: Dissertation, Bachelor of Applied Science with Honours in Software Engineering, University of otago. - 2007-10. - p 99., - URL: https://ourarchive.otago.ac.nz/handle/10523/1189

71. Marc Gregoire, Nicholas A. Solter, Scott J. Kleper. Professional C++ / Marc Gregoire, Nicholas A. Solter, Scott J. Kleper // 3rd Edition. - Publisher Wrox. -2014. - 984p.

72. Страуструп Б. Программирование: принципы и практика использования C++ (для C++11 и C++14). - М.: «Вильямс», 2015. - 1300 с.

73. Мейерс С. Эффективный и современный С++: 42 рекомендации по использованию C++11 и C++14. - М.: «Вильямс», 2016. - 320 с.

74. Nicolai M. Josuttis. The C++ Standard library: A Tutorial and reference (2nd edition) / Nicolai M. Josuttis // Publisher Addison-Wesley Professional. - 2012. -1128p.

75. Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разработка. - СПб.: «Питер», 2007. - 540 с.

76. Новиков Ф.А., Иванов Д.Ю. Моделирование на UML. Теория, практика, видеокурс. - СПб.: «Наука и техника», 2010. - 640 с.

77. Зыков А.А. Основы теории графов. - М.: «Вузовская книга», 2004. - 664 с.

78. Кормен Т.Х. и др. Алгоритмы: построение и анализ. - М.: «Вильямс», 2006. -1296 с.

79. Маликов А.В. Ориентированные графы в реляционных базах данных/ А.В. Маликов // управление , вычислительная техника и информатика. Доклады ТУСУРа, № 2 (18), ч.2, 2008.

80. Иванченко А.Н., Абухания А.Ю. О постановке задачи составления расписаний для вуза // Изв. вузов. Сев.-Кавк. регион. Техн. науки. - 2012. № 6. - C. 9-13

81. Ivanchenko, A., Abuhania, A. Automatization of university timetabling problems. Saba Journal of Information Technology and Networking. Vol. 2, No. 1 (2014), pp. 28-34.

82. Иванченко А.Н., Абухания А.Ю. Информационная модель задачи составления расписаний для вуза // Изв. вузов. Сев.-Кавк. регион. Техн. науки. - 2013. - № 3. - С. 14-16.

83. Martin, James and Carma McClure (1985), Diagramming Techniques for Analysts and Programmers, Englewood Cliffs, NJ: Prentice-Hall.

84. Clive Finkelstein. An Introduction to Information Engineering: From Strategic Planning to Information Systems - Sydney: Addison-Wesley, 1989.

85. Роб П., Коронел К. Системы баз данных: проектирование, реализация и управление. - 5-е изд.: Пер. с англ. - СПб.: БХВ-Петербург, 2004. - 1024 с.

86. Хемди А. Таха. Введение в исследование операций. 7-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2005. - 912 с.

87. Gross, Jonathan L. (2008), Combinatorial Methods with Computer Applications, Chapman & Hall, p. 644

88. Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd ed.), Harcourt, Brace, Jovanovich, p. 486

89. Bogart, Kenneth P. (2004), Combinatorics Through Guided Discovery, Kenneth P. Bogart, 2004, p.190

90. M. Matsumoto and T. Nishimura, Mersenne Twister: A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator, ACM Transactions on Modeling and Computer Simulation, Vol. 8, No. 1, January 1998, pp. 3-30. -URL: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

91. Костенко В.А., Шестов П.Е. Жадный алгоритм совместного планирования вычислений и обменов в системах реального времени / В. А. Костенко, П.Е. Шестов // Известия РАН. Теория и системы управления.- 2012.- № 5.- С. 3549. - URL: http://arccn.ru/knowledge-base?pdf=515978a6cb837.pdf .

92. Ahuja .R.K., Orlin. J.B., Tiwari A.A. Greedy genetic algorithm for the quadratic assignment problem / R.K. Ahuja, J.B. Orlin, A.A. Tiwari // Computers&Operations Research 27. - 2000. - pp. 917-934 / URL: http://jorlin.scripts.mit.edu/docs/publications/64greedy%20genetic%20algorithm.p df .

93. Курейчик, В.В. Теория эволюционных вычислений / В.В. Курейчик, В.М. Курейчик, С.И. Родзин. - М. : Физматлит, 2012. - 260 с.

94. Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы / Д. Рутковская, М. Пилиньский, Л. Рутковский. - М. : Горячая линия -Телеком, 2013. - 384 с.

95. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учебное пособие / А.П. Карпенкою -М.: Изд-во МГТУ им. Н.Э Баумана, 2014. - 446 с.

96. David E. Goldberg, Mike Rudnick. Genetic Algorithms and the Variance of Fitness / David E. Goldberg, Mike Rudnick // Complex Systems Vol.5, Iss.3. -1991. - pp. 265 - 178. - URL: https://www.complex-systems.com/pdf/05-3-1.pdf

97. Goldberg D. Genetic Algorithms In Search, Optimization, and Machine Learning / D. Goldberg. - USA: Addison-Wesley Publishing Company, Inc., 1989.

98. Brownlee J. Clever Algorithms Nature-Inspired programming Recopes / J. Brownlee. - Australia, 2011. - 436 p.

99. Affenzeller M., Winkler S., Wagner S., Beham A. Genetic Algorithms and Genetic Programming. Modern Concepts and Practical Applications / M. Affenzeller, S. Winkler, S. Wagner, A. Beham // GMD-FIRST, Berlin, Germany, 2009. - 377 p.

100. Alba E., Dorronsoro B. Cellular Genetic Algorithms / E. Alba, B. Dorronsoro. - Springer 2008. - 247 p.

101. Mitsuo Gen, Runwei Cheng. Genetic algorithms & engineering optimization / Mitsuo Gen, Runwei Cheng // John Wiley & Sons, 2000. - 495 p.

102. Randy L. Haupt, Sue Ellen Haupt. Practical genetic algorithms / Randy L. Haupt, Sue Ellen Haupt // John Wiley & Sons, 2004. - 253 p.

103. Thomas Bäck. Evolutionary Algorithms in Theory and Practice / Bäck Thomas. - Oxford New York, 1996. - 319 p.

104. Bryan A.N, James C.B. A Genetic Algorithm Methodology for Complex Scheduling Problems / A.N. Bryan, C.B. James. - USA, 1997. - 27 p.

105. The Practical Handbook of Genetic Algorithms. Applications / Edited by Lance Chambers. - Chapman & Hall, 2001. - 520 p.

106. David A. Coley. An Introduction to Genetic Algorithms for Scientist and Engineers / David A. Coley // World Scietific Publishing, 1999. - 227 p.

107. Шаповалов, Т. С. Планирование выполнения заданий в распределенных вычислительных системах с применением генетических

алгоритмов : дис. ... канд. техн. наук : 05.13.11 / Шаповалов Тарас Сергеевич. - Хабаровск, 2010. - 146 с.

108. Инзамова Г. Ф. Математическое и программное обеспечение составления расписания учебных занятий на основе агрегативных генетических алгоритмов: автореф. дис. .канд. тенх. наук : 05.13.11 / Инзамова Гузель Фанисовна. - Уфа, 2006. - 19 с.

109. Ржеуцкий А. В. Модель, метод и комплекс программ для решения задачи классификации с использованием генетических алгоритмов : автореф. дис. .канд. тенх. наук : 05.13.18 / Ржеуцкий Александр Викторович. -Санкт-Петербург, 2012. - 18 с.

110. Алгулиев Р.М., Алыгулиев Р.М. Быстрый генетический алгоритм решения задачи кластеризации текстовых документов / Р.М. Алгулиев, Р.М. Алыгулиев // Искусственный интеллект.- 2005.- № 3.- C. 698-707.- URL: http://iai.dn.ua/public/JournalAI 2005 3/Razdel9/01 Alguliev Alyguliev.pdf .

111. Алгулиев Р.М. Генетический подход к оптимальному назначению заданий в распределенной системе / Р.М. Алгулиев, Р.М. Алыгулиев // Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004: Материалы Международной научной конференции.- 2004.-Т.1.- C. 302-307

URL:http://iai.dn.ua/public/JournalAI 2004 4/Razdel2/02 Alguliev Alyguliev.pd f

112. Евгенев Г.Б. Многоагентные системы проектирования с использованием генетических алгоритмов для поиска лучших решений / Г.Б. Евгенев // Интеллектуальные системы и технологии. Научная сессия МИФИ-2007. - Т.3. - URL: http://library.mephi.ru/data/scientific-sessions/2007/t3/0-1-9.doc .

113. Каширина И. Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида / И. Л. Каширина // Вестник ВГУ: Серия Физика, математика. - 2003. - № 1. - URL: http://www.vestnik.vsu.ru/pdf/physmath/2003/01/kashirina.pdf .

114. Коробкин А. А. Использование агрегативного генетического алгоритма для составления расписания учебных занятий ВУЗа / А.А. Коробкин // Современные проблемы науки и образования. - 2009.- №6. - C. 10 URL: http://online.rae.ru/432 .

115. Слепцов Н.В. Эффективное управление генетическим поиском с помощью операций кроссовера / Н.В. Слепцов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2009. - № 3(11). - С. 3246. - URL: http://izvuz tn.pnzgu.ru/files/izvuz tn.pnzgu.ru/4309.pdf .

116. Слепцов Н.В. Формальные представления эволюционно-генетических преобразований / Н.В. Слепцов // Известия высших учебных заведений. Поволжский регион. Технические науки. - 2010. - № 1(13).- С. 15-24. - URL: http://izvuz tn.pnzgu.ru/files/izvuz tn.pnzgu.ru/2110.pdf .

117. Yilmaz A. Genetic algorithm for personnel assegment problem with multiple objectives/A Yilmaz // MS, Department of Computer Engineering Supervisor: January 2006. - 68 p. URL: http://www.lania.mx/~ccoello/EMOO/thesis-arslanoglu.pdf.gz .

118. Han L., Kendall G. Guided Operators for a Hyper-Heuristic Genetic Algorithm / Lю Han, G. Kendall // The 16th Australian conference on artificial intelligence (AI'03). - 2003. - pp. 807-820 - URL: http://pdf.aminer.org/000/059/407/guided operators for a hyper heuristic geneti c algorithm.pdf .

119. Zurada J. Genetic algorithms, optimization, traveling salesman problem / J. Zurada // Review of Business Information Systems. - Third Quarter 2010 Vol. 14, N.3. - pp. 5-10. - URL: http://journals.cluteonline.com/index.php/RBIS/article/viewFile/491/478

120. Бубарева О. А. К вопросу проектирования автоматизирования системы управления учебным процессом вуза / О.А. Бубарева // XVII Всероссийская научно-методическая конференция «Телематика-2010». - 2010. - URL: http://www.ict.edu.ru/vconf/files/11815.pdf

121. Донецков А.М. Автоматизация составления расписания учебных занятий в вузе // Материалы Всероссийской научно-технической конференции «Наукоемкие технологии в приборо - и машиностроении и развитие инновационной деятельности в ВУЗе». - М.: Изд. МГТУ им. Н.Э. Баумана, 2008. - Т.2. - С. 98. - URL: http://www.ict.edu.ru/vconf/files/11095.doc

122. Chad Z. Hower. Tier Pressure and Isolationism / Chad Z. Hower // CodeProject AdOps : electron. Journal - 23 Jul 2014 - URL: http://www.codeproject.com/Articles/10943/Tier-Pressure-and-Isolationism.

123. Chanda S., Foggon D. Beginning ASP.NET 4.5 Databases / Sandeep Chanda, Damien Foggon // Publisher Apress. - 2013. - 280p.

124. Spaanjaars I. Beginning ASP.NET 4.5 in C# and VB / Imar Spaanjaars // Indianapolis, Indiana, 2013. - 890 p.

125. MacDonald M. Beginning ASP.NET 4.5 in C# / Matthew MacDonald // Apress, 2012. - 900 p.

126. Freeman A. Pro ASP.NET MVC 3 Framework. Third Edition / Adam Freeman, Steven Sanderson // 2011. - 837p. - URL: http://www.it-ebooks.info

127. Galloway J., Haack P., Wilson B., Allen K.S. Professional ASP.NET MVC 4 / Jon Galloway, Phil Haack, Brad Wilson, K. Scott Allen // 2012 - 443p. URL: http://ebook-dl.com .

128. Ross M., Stacia M. Introducing Microsoft SQL Server 2014 Technical Overview / M. Ross, M. Stacia // Copyright © 2014 by Microsoft Corporation. -URL: http://blogs.msdn.com/b/user ed/archive/2014/04/09/new-free-ebook-introducing-microsoft-sql-server-2014-power-bi.aspx - 125p.

129. Natarajan J., Shaw S., Bruchez R., Closes M. Pro T-SQL 2012 Programmer's Guide / Jay Natarajan, Scott Shaw, Rudi Bruchez, Michael Closes // Third Edition, Springer Verlag GmbH. - 2012 - 516p.

130. Natarajan J., Shaw S., Bruchez R., Closes M. Pro T-SQL 2012 programmer's Guide / Jay Natarajan, Scott Shaw, Rudi Bruchez, Michael Closes // Expert guidance for T-SQL prograammers in sql server 2012. - 679 p.

131. Basit A. Masood-Al-Farooq. SQL Server 2014 Development Essentials / Basit A. Masood-Al-Farooq // Packt Publishing. - 2014. - 140p.

132. Musser D.A., Stepanov A.A. Generic Programming / David A. Musser, Alexander A. Stepanov // Proceeding of International Symposium on Symbolic and Algebraic Computation, vol. 358 of Lecture Notes in Computer Science, pp. 13-25, Rome, Italy, 1988.

133. Степанов А. А., Мак-Джонс П. Начала программирования : пер. с англ. /

A. А. Степанов, П. Мак-Джонс // М.: ООО «И. Д. Вильямс», 2011. - 272 с.

134. Sastry K., Goldberg D., Kendall G. Genetic Algorithms / Search Methodologies. Introductory Tutorials in Optimization and Decision Support Techniques. Edited by Edmund K. Burke & Graham Kendall // Springer Science+Business Media, LLC, 2005. - pp. 97-126

135. Beyer H.-G., Schwefel H.-G. Evolution strategies. A comprehensive introduction / Natural Computing 1: pp. 3-52, 2002 // Kluwer Academic Publishers.

136. Кобак В.Г. Повышение эффективности модифицированной модели Голдберга в однородных системах обработки информации алгоритмическими преобразованиями [Электронный ресурс]: монография /

B.Г. Кобак, Д.В. Титов, Н.И. Троцюк; Дон. гос. техн. ун-т. - Электрон. текстовые дан. - Ростов н/Д: ДГТУ, 2015. - 86 с. - Режим доступа: http://www.ntb.donstu.ru/content/2015191.

137. Holland J. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence / J. Holland. - USA: University of Michigan, 1975.

ПРИЛОЖЕНИЕ 1.

Исходные данные и результаты прогона алгоритмов решения иСТР для

модельного примера

1 Исходные данные

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

В качестве периода планирования примем одну неделю, состоящую из 5 рабочих дней, пронумерованных от 1 до 5. Каждый рабочий день состоит из 4 учебных пар (таймслотов). Таким образом, общее количество таймслотов в периоде планирования равно 20. Наглядное представление о сетке времени дает таблица П1.1.

Таблица П1.1 - Сетка таймслотов на одну неделю

Пн Вт Ср Чт Пт

1 1 5 9 13 17

2 2 6 10 14 18

3 3 7 11 15 19

4 4 8 12 16 20

Примем, что все учебные аудитории расположены в трех корпусах, имеющих номера 1, 2 и 3 и условные названия "Корпус 1", "Корпус2" и "КорпусЗ". Учебный корпус 2 находится на значительном удалении от учебных корпусов 1 и 3 (это необходимо знать для определения достижимости аудиторий для смежных пар). Данные по аудиторному фонду для модельного примера представлены в табл. П1.2.

Будем считать, что учебный процесс обеспечивают 6 преподавателей, данные по которым представлены в табл. П1.3, а в учебном процессе участвуют 14 учебных групп, из которых 6 являются академическими группами, а остальные - потоки и подгруппы (табл. П1.4). Наглядное представление о взаимозависимости групп по студентам дает рис. П1.1.

Таблица П1.2 - Исходные данные по аудиториям

Код ауд. Код корп. Название Вид ауд. Кол-во мест Запреты (дни и пары) Запреты (таймслоты)

1 1 Поток 1 1 100 Пн(4), Вт(1), Ср(3,4), Пт(1) 4,5,11,12,17

2 1 Класс 1 2 30 Чт(2-4) 14,15,16

3 2 Поток2 1 100 - -

4 2 Класс2 2 30 Ср(1-3) 9,10,11

5 3 Лаб1 3 15 Пн(1-4) 1,2,3,4

6 3 Лаб2 3 15 Пт(1-4) 17,18,19,20

Таблица П1.3 - Исходные данные по преподавателям

Код преп. Имя Запреты (дни и пары) Запреты (таймслоты)

1 Проф1 Пн(1-4), Пт(1-4) 1,2,3,4,17,18,19,20

2 Доц1 Вт(2-4) 6,7,8

3 Доц2 Чт(1-4) 13,14,15,16

4 Асс1 Ср(1-2) 9,10

5 Асс2 Пн(1-4) 1,2,3,4

6 Асс3 Пт(1-4) 17,18,19,20

Таблица П1.4 - Исходные данные по учебным группам

Код группы Название Тип Кол-во студ

1 ФИТУ 1-5, 5Б поток 35

2 ФИТУ 1-5, 5Б, ФМФ 1-2, 3 поток 65

3 ФИТУ 1-5, 5Б, ФМФ 1-2, 3, 4 поток 80

4 ФМФ 1-2, 3, 4 поток 45

5 ФИТУ 1-5 акад. группа 10

6 ФИТУ 1-5Б акад. группа 25

7 ФИТУ 1-5м акад. группа 10

8 ФМФ 1-2 акад. группа 10

9 ФМФ 1-3 акад. группа 20

10 ФМФ 1-4 акад. группа 15

11 ФИТУ 1-5Б (1/2) подгруппа 12

12 ФИТУ 1-5Б (2/2) подгруппа 13

13 ФМФ 1-3 (1/2) подгруппа 10

14 ФМФ 1-3 (2/2) подгруппа 10

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

Рисунок П1.1 - Граф структурной иерархии типа '^Б-рай-оР для учебных

групп

Таблица П1.5 - Исходные данные по учебным единицам

Код уч. ед. Учебная группа (код, название) Преподаватель (код, имя) Вид уч. занятия(код, название) Запреты (аудитории)

1 1, ФИТУ 1-5, 5Б 1,"Проф1" 1, лекция 2,4-6

2 2, ФИТУ 1-5, 5Б, ФМФ 1-2, 3 2,"Доц1" 1, лекция 2-6

3 3, ФИТУ 1-5, 5Б, ФМФ 1-2, 3, 4 2,"Доц1" 1, лекция 1,2,4-6

4 4, ФМФ 1-2, 3, 4 3,"Доц2" 1, лекция 2,4-6

5 5, ФИТУ 1-5 1,"Проф1" 2, практ. 5,6

6 6, ФИТУ 1-5Б 4,"Асс1" 2, практ. 5,6

7 8, ФМФ 1-2 3,"Доц2" 2, практ. 5,6

8 8, ФМФ 1-2 6,"Асс3" 2, практ. 5,6

9 9, ФМФ 1-3 5,"Асс2" 2, практ. 5,6

10 9, ФМФ 1-3 6,"Асс3" 2, практ. 5,6

11 10, ФМФ 1-4 2,"Доц1" 2, практ. 5,6

12 11, ФИТУ 1-5Б (1/2) 4,"Асс1" 3, лаб. 1-4

13 12, ФИТУ 1-5Б (2/2) 4,"Асс1" 3, лаб. 1-4

14 13, ФМФ 1-3 (1/2) 6,"Асс3" 3, лаб. 1-4

15 14, ФМФ 1-3 (2/2) 5,"Асс2" 3, лаб. 1-4

2 Ввод исходных данных в программу

Как было показано в гл. 4, все данные (исходные, промежуточные и выходные) и необходимая функциональность по их обработке инкапсулированы в классе Tables. Полями класса являются структуры данных, представляющие реляционные таблицы, а для заполнения данными этих структур класс содержит закрытые функции make_X() (где X - имя соответствующей структуры данных). Вызов функций make_X(), отвечающих за наполнение исходными данными соответствующих структур данных, и функций, выполняющих предварительную обработку данных и формирование вспомогательных структур данных содержатся в единственном конструкторе класса, не имеющем параметров. Поэтому при создании экзепляра класса Tables (например, так: Tables t;) происходит заполнение соответствующих структур исходными данными, а также формируются данные, которые могут быть получены до начала выполнения основного алгоритма решения UCTP.

В модельном примере исходные данные вводятся в программу с помощью списков инициализации функциями: make_TW(), make_TD(), make_TP(), make_BCR(), make_FAR_B(), make_CR(), make_BAN_CR_T(), make_TCH(), make_BAN_TCH_T(), make_GROUPS(), make_HGR(), make_U(), make_U1(), make_U2(), make_U3(), make_BAN_U_CR(), исходные коды которых приведены в приложении 4 (п. 3.2).

3 Формирование промежуточных данных

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

- сетка расписания - SPG,

- условие недостижимости для пар аудиторий - FAR_CR,

- список кластеров учебных групп - CLGR,

- отношение S-конкурентности групп - SCGR,

- состав кластеров учебных групп - CIG,

- списки допустимых ячеек сетки расписания для каждой учебной единицы - CU,

- отношение Т-конкурентности учебных единиц - TCTU. Формирование соответствующих стуктур данных происходит в

конструкторе класса Tables в результате вызова функций: make_SPG(), make_FAR_CR(), make_CLGR(), make_SCGR(), make_CIG(), make_CU(), make_TCTU(). Для визуализации результатов выполнения этих функций класс Tables содержит соответствующие функции print_X(), исходные коды которых приведены в приложении 4 (п. 3.2).

Так, результат выполнения функции make_SPG() выводится на экран функцией print_ SPG() (рис. П1.2).

—Сетка раписания (Ляч.-аудитормя-таймслот)---

Рисунок П1.2 - Сетка расписания Этому результату можно придать наглядную форму (табл. П1.6). Как видно, сетка включает 101 ячейку, доступную для планирования учебных занятий (всего ячеек 120, но на 19 ячеек наложен запрет из-за занятости аудиторий). Данная таблица позволяет выполнить переход от номера ячейки к номерам аудитории и таймслота (в силу этого её можно назвать матрицей кодирования ячеек).

Таблица П1.6 - Матрица кодирования ячеек сетки расписания

Таймслоты

Ауд. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

1 1 2 3 х х 4 5 6 7 8 х х 9 10 11 12 х 13 14 15

2 16 17 18 19 20 21 22 23 24 25 26 27 28 х х х 29 30 31 32

3 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

4 53 54 55 56 57 58 59 60 х х х 61 62 63 64 65 66 67 68 69

5 х х х х 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

6 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 х х х х

Результат выполнения функции таке_ БЛЯ_СК() представлен на рис. П1.3. Здесь первое число - номер аудитории, список после двоеточия -аудитории, недостижимые из неё.

—Удаленность аудиторий

1: 3, 4,

2: 3, 4,

3: 1, 2, 5, 6,

4: 1, 2, 5. 6,

5: 3, 4,

6: 3. 4.

Рисунок П1.3 - Удаленность (недостижимость) пар аудиторий Список кластеров учебных групп формируется функцией таке_СЬОЯ() (рис. П1.4). Получилось 8 кластеров по числу вершин графа с нулевой полустепенью захода. Каждый кластер идентифицируется вершиной исходного графа - корнем соответствующего поддерева.

—Список кластеров (^кластера - Авершини-корня)

1 5

2 7

3 8

4 10

5 11

6 12

7 13

8 14

Рисунок П1.4 - Список кластеров учебных групп Для наполнения кластеров номерами групп вначале установливается Б-конкурентность групп с помощью функции таке_8СОЯ() (рис. П1.5). Здесь первое число - номер группы, список после двоеточия - Б-конкурентные группы, т.е. группы, имеющие общих студентов.

—Б-граф групп- --

1: 5, 6, 11, 12 . 2, 3.

2: 5, 6, 8. 9. 11, 12, 13, 14, 1, 3, 4,

3: 5, 6, 8, 9, 10, 11, 12, 13, 14, 1, 2, 4,

4: 8, 9. 10, 13, 14, 2 3,

5: 1, 2. 3,

6: 1, 2, 3, И, 12.

7:

8: 2, 3. 4,

9: 2. 3. 4, 13, 14.

10: 3 4

11: 6 1 2, 3,

12: 6 1 2, 3,

13: 9 2 3, 4,

14: 9 2 3, 4,

Рисунок П1.5 - Б-граф учебных групп В завершение процесса обработки информации о группах производится формирование кластеров с помощью функции шаке_СЮ() (рис. П1.6). Здесь первое число - номер кластера, список после двоеточия - входящие в кластер учебные группы. Эти результаты совпали с описанным в гл.2 разложением структурной иерархии на ориентированные деревья (рис. П1.7).

— Состав кластеров---

1: 5. 1. 2. 3,

2: 7.

3: 8. 2. 3. 4,

4: 10, 3. 4.

5: 11. 6. 1. 2. 3,

6: 12. 6. 1. 2. 3,

7: 13. 9. 2, 3, 4,

8: 14. 9. 2. 3. 4,

Рисунок П1.6 - Состав кластеров

Рисунок П1.7 - Разложение графа структурной иерархии на

ориентированные деревья

С использованием данных о запрете размещения учебных единиц в определенных аудиториях и данных о занятости преподавателей в определенные таймслоты функция таке_Си() формирует вспомогательную структуру данных Си (рис. П1.8). Здесь первое число - номер учебной единицы, список после двоеточия - номера допустимых для данной учебной единицы ячеек сетки расписания. На рисунке представлены только два фрагмента структуры данных CИ из-за большого объема данных.

—Матрица Си (уч.сд. - допустимые ячейки)---

и=1: 4,5,6,7,8,9,10,11,12,37,38,39,49,41,42,43,44,45,46,47,48, и=2: 1,2,3,7,8,9,10,11,12,13,14,15,

и=3: 33,34,35,36,37,41,42,43,44,45,46,47,48,49,50,51,52, и=4:

1,2,3,4,5,6,7,8,13,14,15,33,34,35,36,37,38,39,40,41,42,43,44,49,50,51,52, и=5:

4,5,6,7,8,9,10,11,12,20,21,22,23,24,25,26,27,28,37,38,39,40,41,42,43,44,4 5,46,47,48,57,58,59,60,61,62,63,64,65,

и=14:

70,71,72 73,74 75 ,76, 77 ,78, 79 80, 81 86, 87, 88, 89 ,90, 91 92 93 94 95, 96 ,97, 9

8,99,100 101,

и=15:

70,71,72 73,74 75 ,76, 77 ,78, 79 80, 81 82, 83, 84, 85 ,90, 91 92 93 94 95, 96 ,97, 9

8,99,100 101,

Рисунок П1.8 - Списки допустимых ячеек В завершение работы конструктора ТаЫев() вызывается функция таке_ТСТИ(), формирующая структуру данных ТСТИ (рис. П1.9), позволяющую установить факт конкуренции между учебными единицами за один таймслот. Здесь первое число - номер учебной единицы, список после двоеточия - Т-конкурентные учебные единицы.

—Т-граф уч. единиц---

1: 2, 3, 5, 6, 12, 13.

2: 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,

3: 1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,

4: 2, 3, 7, 3, 9, 1Э, 11, 14, 15,

5: 1. 2, 3,

6: 1, 2, 3, 12, 13,

7: 2, 3, 4, 8,

8: 2, 3, 4, 7, 10, 14.

9: 2, 3, 4, 10, 14, 15,

10: 2 3, 4, 8, 9. 14, 15,

11: 2 3, 4,

12: 1 2, 3, 6, 13,

13: 1 2, 3, 6, 12,

14: 2 3, 4, 8, 9, 19,

15: 2 3, 4, 9, 10,

Рисунок П1.9 - Отношение Т-конкурентности учебных единиц

4 Результат решения UCTP для модельного примера

После вызова конструкторе Tables(), выполняющего ввод и предварительную обработку исходных данных, создается объект g -экземпляр основного класса GA_permut. Этот класс обеспечивает реализацию глобального ГА, включает в качестве поля экземпляр класса population_p и является классом-клиентом Tables. Создание объекта g выполняется конструктором с двумя параметрами, имеющими значения по умолчанию, поэтому в "минимальном" варианте это будет выглядеть так: GA_permut g;. При этом глобальный ГА по умолчанию будет использовать одноточечный частично отображающий кроссовер PMX1, а в качестве фитнесс-функции будет использована функция SLO, реализующая алгоритм последовательной локальной оптимизации (см. п.3.3.8).

После создания объекта g запускается процесс решения UCTP вызовом открытой функции GA_perm - члена класса GA_permut: g.GA_perm(&t);. Для доступа к данным, подготовленным конструктором Tables(), в функцию передается ссылка на объект t - экземпляр класса Tables. В результате работы функции GA_perm получается квазиоптимальное расписание, которое будет находиться в структуре данных S (поле объекта t) в виде пар значений "номер учебной единицы - номер ячейки сетки расписания". Для визуализации расписания S класс Tables содержит функцию Post(), которая кроме печати расписания в «расшифрованном» виде подсчитывает и печатает значения частных критериев оптимизации. Исходные коды функции Post(), а также функции подсчета частных критериев оптимизации make_F() приведены в приложении 4 (п. 3.2).

Ниже на рис. П1.10 представлен один из вариантов квазиоптимального расписания, полученного в результате работы функции GA_perm(). В более наглядном и привычном виде это же расписание для каждого дня недели показано на рис. П1.11 - П1.15. Этому расписанию соответствуют значения частных критериев оптимизации, показанные на рис. П1.16.

уч.ед-день- тара-корп.-ауд.- -вмест.- -вид-прсп.-гр.-студ.

11 1 3 2 Класс2 38 2 Доц1 ФМФ 1-4 15

3 1 2 2 Поток2 108 1 Доц1ФИТУ 1-5,5Б, ФМФ 1-2,3,4 88

14 2 4 3 Ла62 15 3 АссЗ ФМФ 1-3(1/2) 18

6 2 4 2 Класс2 38 2 Асс1 ФИТУ 1-5Б 25

9 2 3 1 Класс1 38 2 Асс2 ФМФ 1-3 28

4 3 1 1 Поток1 108 1 Доц2 ФМФ 1-2,3,4 45

7 3 2 1 Поток! 108 2 Доц2 ФМФ 1-2 10

12 3 4 3 Лаб1 15 3 Асс1 ФИТУ 1-5Б(1/2) 12

13 3 3 3 Лаб1 15 3 Асс1 ФИТУ 1-5Б(2/2) 13

10 4 3 2 Поток2 100 2 АссЗ ФМФ 1-3 20

1 4 1 2 Поток2 108 1 Проф! ФИТУ 1-5,5Б 35

8 4 2 2 Класс2 38 2 АссЗ ФМФ 1-2 10

5 4 2 2 Поток2 100 2 Проф1 ФИТУ 1-5 10

2 5 2 1 Поток1 100 1 Доц1ФИТУ 1-5,5Б, ФМФ 1-2,3 65

15 5 1 3 Ла61 15 3 Асс2 ФМФ 1-3(2/2) 10

Рисунок П1.10 - Вариант квазиоптимального расписания

Понедельник

1 2 3 4

Поток 1

Класс 1

Поток2 лекция ФИТУ 1-5, 5Б, ФМФ 1-2, 3, 4 (Доц1)

Класс2 практ. занятия ФМФ 1-4 (Доц1)

Лаб1

Лаб2

Рисунок П1.11 - Расписание на понедельник

Вторник

1 2 3 4

Поток 1

Класс 1 практ. занятия ФМФ 1-3 (Асс2)

Поток2

Класс2 практ. занятия ФИТУ 1-5Б (Асс1)

Лаб1

Лаб2 лаб.занятия ФМФ 1-3 (1/2) (Асс3)

Рисунок П1.12 - Расписание на вторник

Среда

1 2 3 4

Поток 1 лекция ФМФ 1-2, 3, 4 (Доц2) практ. занятия ФМФ 1-2 (Доц2)

Класс 1

Поток2

Класс2

Лаб1 лаб. занятия ФИТУ 1-5Б (2/2) (Асс1) лаб. занятия ФИТУ 1-5Б (1/2) (Асс1)

Лаб2

Рисунок П1.13 - Расписание на среду

Четверг

1 2 3 4

Поток 1

Класс 1

Поток2 лекция практ. занятия практ. занятия

ФИТУ 1-5, 5Б ФИТУ 1-5 ФМФ 1-3

(Проф1) (Проф1) (Асс3)

Класс2 практ. занятия ФМФ 1-2 (Асс3)

Лаб1

Лаб2

Рисунок П1.14 - Расписание на четверг

Пятница

1 2 3 4

Поток 1 лекция ФИТУ 1-5, 5Б, ФМФ 1-2, 3 (Доц1)

Класс 1

Поток2

Класс2

Лаб1 лаб.занятия ФМФ 1-3 (2/2) (Асс2)

Лаб2

Рисунок П1.15 - Расписание на пятницу

Критерии :

1. Количество лекций после утренних часов: О

2. Количество избыточных мест в аудиториях: 506

3. Сумма превышений дневной нагрузки для всех преподавателей: О

4. Сумма "окон" в расписании по всем преподавателям: 0

5. Сумма переходов между корпусами по всем преподавателям: 0

6. Сумма превышений дневной нагрузки для студентов: 0

7. Сумма "окон" в расписании по всем студентам: 0

8. Сумма переходов между корпусами по всем студентам: 2

Рисунок П1.16 - Значения частных критериев оптимизации для

составленного расписания Как следует из данных рис.П1.16, "минусами" данного расписания являются избыточные посадочные места в аудиториях во время проведения в них занятий, а также два перехода между учебными корпусами для студентов: во вторник студенты подгруппы ФМФ 1-3 (1/2) совершат переход из первого учебного корпуса в третий после третьей пары и в пятницу студенты подгруппы ФМФ 1-3 (2/2) совершат переход из третьего учебного корпуса в первый после первой пары.

ПРИЛОЖЕНИЕ 2. Операторы кроссовера и мутации для хромосом, кодируемых

перестановками

1 Частично отображающие кроссоверы

Семейство частично отображающих кроссоверов (Partially Matched Crossover - PMX) реализует одну общую идею: в родительских хромосомах-перестановках выбирается некоторое множество позиций (множество обменных позиций - МОП) и в этих позициях происходит обмен значениями между хромосомами. Неизбежные нарушения свойства перестановок в результате такого обмена (обязательное появление повторяющихся элементов в одной перестановке) устраняются путем корректировки, следующей сразу за обменом значениями: после выполнения первого (основного) обмена в обеих хромосомах определяются позиции, значения в которых совпали с «новыми» значениями, и между этими позициями также происходит обмен. Будем говорить, что к каждой обменной позиции применяется процедура двойного обмена (Double-Exchange Procedure - DEP). Конечно, эта процедура не применяется, когда значения на одной обменной позиции в обоих родительских хромосомах совпадают. Пример выполнения DEP показан на рис. П4.1.