Алгоритмы решения задачи составления оптимального расписания без прерываний

• Автор: Красовский, Дмитрий Владимирович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 109 с. : ил.

СОДЕРЖАНИЕ
Введение

Глава 1. Основные понятия и формальная постановка задачи

1.1. Модель

1.2. Оценка погрешности и времени составления расписания

1.3. Задачи большой размерности

Глава 2. Характеристика задачи и существующие методы ее решения

2.1. Результаты для задач минимизации длины расписания

г 2.2. Оценки характеристик алгоритмов составления расписаний

2.3. Анализ существующих точных и приближенных алгоритмов

2.4. Анализ существующих параллельных стратегий

Глава 3. Алгоритмы составления расписания без прерываний
3.1. Алгоритм Процессор с ранним окончанием первым
3.2. Вероятностный алгоритм
3.3. Псевдополиномиалъные алгоритмы
3.3.1. Различные интерпретации псевдополиномиальных алгоритмов
3.3.2. Псевдополиномиальный алгоритм с поиском в ширину
3.3.3. Псевдополиномиальный алгоритм с поиском в глубину
3.4. Метод агрегирования
3.4.1. Формальное описание
3.4.2. Задача составления расписания п работ на т идентичных
процессорах
3.4.3. Вспомогательные алгоритмы
3.4.4. Агрегирующие алгоритмы
3.5. Анализ возможности совместного использования методики
агрегирования с другими алгоритмами
Глава 4. Алгоритмы с гарантированной точностью
4.1. Псевдополиномиальный алгоритм с поиском в глубину
4.2. Вероятностный алгоритм
4.3. Алгоритм Процессор с ранним окончанием первым
4.4. Алгоритм Самая длинная работа первой
Глава 5. Результаты для некоторых частных случаев
5.1. Длительности работ, заданные арифметической прогрессией
5.2. Длительности работ, близкие к арифметической прогрессии
5.3. Фиксированное число процессоров
Глава 6. Параллельное выполнение вычислений
6.1. Комбинированный псевдополиномиальный алгоритм
6.2. Параллельное построение дерева решения
Глава 7. Результаты экспериментов
7.1. Экспериментальная система
7.2. Таблицы и графики
Заключение
Список использованных источников


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