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

• Автор: Альрашайда Абед Альвахаб Хусейн
• Шифр специальности: 05.13.16
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Махачкала
• Количество страниц: 115 с. : ил.

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

1.2. Графы, пути, циклы.

1.3. Транспортные сети

Г лава 2. Раскрашиваемость двудольных графов

2.1. Выделение в матрице задачи ОУР двух областей

2.2. Равномерная реберная 2 раскрашиваемость двудольных графов

2.3.Теорема о разбиении объединения семейств 2х и 4х элементных

множеств.

2.4. О равномерной реберной 2раскрашиваемости графа

Глава 3. Разреженные расписания.

3.1. Устранимость окон в расписании с двумя занятиями у преподавателей.

3.2. Вычислительная схема устранения окон в расписании с двумя за
нятиями у преподавателей.
3.3. Теорема об полноте задачи оптимизации учебного расписания ОУР
Глава 4. Исследование задачи оптимизации учебного расписания ОУР.
4.1. Сведение задачи ОУР к поиск подматрицы класса .
4.2. Проверка условий существования подматрицы М как задача вычисления трансверсалей
4.3. Метод бездефектного потока
4.4. Поиск путей в графах
4.5. Вычислительная схема решения задачи о связности матрицы
Глава 5. Применение результатов и вопросы реализации алгоритмов.
5.1. Схема решения задачи ОУР.
5.2. Применение к проблеме оптимального размещения программ.
5.3 Компьютерное сопровождение алгоритмов
Литература


В следующей формулировке под сохраняющим преобразованием матрицы понимается преобразование, сохраняющее множество элементов в каждой линии. Задача Оптимизация учебного расписания. Дано Матрица учебного расписания М тхк, каждый столбец которого содержит некоторую перестановку чисел 1, 2, п, тп, и тп нулей, где п число различных учебных групп, т количество преподавателей, кколичество уроков в каждой учебной группой. Равенство Мк при к0 рассматривается как наличие ого урока го преподавателя в учебной группе с номером к. Равенство Мд0 является признаком отсутствия у преподавателя го урока, и если при этом найдутся 5, такие, что , МтЮ, Ми0, то Му называется окном для преподавателя . Требуется Найти необходимые и достаточные условия существования сохраняющего преобразования матрицы М к виду, где ненулевые элементы в каждой строке располагаются рядом. В случае существования такого преобразования указать эффективный алгоритм его реализации. Напомним, что во Введении исходную матрицу мы условились называть уплотнимой, если задача имеет решение в этом же случае результат искомого преобразования называется уплотненным вариантом или уплотнением. УСЛОВИЕ. Заданы множество Н рабочих часов, множество С преподавателей, множество Т учебных дисциплин, для каждого сеС дано подмножество Асс1Н, называемое допустимыми часами для преподавателя с, для каждой дисциплины 1еТ подмножество В1сЛ1, называемое допустимыми часами для дисциплины , и для каждой пары сДеСхТ число Щс,1 е о, называемое требуемой нагрузкой. ВОПРОС.