Теоретико-графовые модели и методы составления расписаний без прерываний

• Автор: Лугуев, Тимур Садыкович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Махачкала
• Количество страниц: 105 с. : ил.

Оглавление
Введение
1 Графовые модели задачи составления расписания без прерываний
1.1 Задача составления расписаний без прерываний
1.2 Модель интервальной раскраски графа
1.3 Модель инциденторной раскраски мультиграфа
2 Составление расписания без прерываний в случае четного числа требований, запланированных на выполнение для каждого прибора
2.1 Задача проверки существования совершенного расписания
как задача дефрагментации матрицы
2.2 Условия дефрагментации матриц
2.3 Бездефектный поток и его вычисление
2.4 Поиск кратчайших периодических цепей
3 Потоковые алгоритмы, используемые при проверке условий существования расписаний без прерываний
3.1 Алгоритмы поиска подграфов максимальной плотности
3.2 Потоковые методы, основанные на увеличивающих путях . .
3.3 Алгоритмы, основанные на проталкивании иредпотока

3.4 Случай несбалансированной двудольной сети
3.5 Результаты численного эксперимента
4 Некоторые приложения разработанных методов
4.1 Задача оптимизации расписания передачи информации в беспроводных сенсорных сетях
4.2 Программа проектирования и анализа беспроводных сетей .
4.3 Некоторые ПР-полные аспекты задач распознавания
4.4 Приложения задачи нахождения подграфа максимальной
плотности
Заключение
Литература

Введение
Актуальность темы
Проблема составления расписания возникает в различных областях науки и техники: в работе сетей передачи данных, при распределении процессорного времени между программами, при формировании расписаний учебных занятий, при составлении расписания движения транспорта, и во многих других.
Несмотря на многолетние поиски ряда исследователей, для большинства задач теории расписаний не удается найти точные эффективные алгоритмы. На практике, как правило, используют приближенные и эвристические алгоритмы. Объясняется это тем, что большинство задач составления расписаний относится к классу ЫР-полных задач, для которых не найдены алгоритмы с. полиномиальной вычислительной сложностью. Более того, если известная гипотеза верна, такие алгоритмы не существуют.
Поэтому актуальным является рассмотрение подзадач, имеющих важное теоретическое и практическое значение и допускающих решение за полиномиальное время.
Б наиболее общей формулировке задача составления расписания состоит в следующем. Заданное множество обслуживающих приборов должно выполнить некоторый фиксированный набор требований. В зависимости от области приложения под парой приборы-требования могут пониматься процессоры-программы, учителя-классы, станки-детали и т.д. Цель заклю-

поток в исходной сети С не существует“.
Рядом с каждой дугой указаны верхние и нижние потоковые ограничения. Следуя описанному выше алгоритму, построим новую сеть и найдем в ней максимальный поток.
На рис.2.5 приведен пример построения новой сети и нахождения в ней максимального потока. Дополнительно введенные дуги выделены сплошными линиями. У каждой дуги указаны потоковые; ограничения (первое число) и значение потока (второе число). Из рисунка видно, что значение максимального потока равно 12 и совпадает сг = ХЖв)- Следовательно, допустимый поток в начальной сети существует. Вычислим его.

Д ' • Д ' I
' I I
Рис. 2.5. Новая транспортная сеть с указанием максимального потока. Рассмотрим, например, дугу е = (ад, х^) с нижним потоковым ограни-