Методы повышения эффективности алгоритмов решения распределительных минимаксных задач в однородных системах

Методы повышения эффективности алгоритмов решения распределительных минимаксных задач в однородных системах

Автор: Титов, Дмитрий Вячеславович

Шифр специальности: 05.13.01

Научная степень: Кандидатская

Год защиты: 2009

Место защиты: Ростов-на-Дону

Количество страниц: 176 с.

Артикул: 4735049

Автор: Титов, Дмитрий Вячеславович

Стоимость: 250 руб.

Методы повышения эффективности алгоритмов решения распределительных минимаксных задач в однородных системах  Методы повышения эффективности алгоритмов решения распределительных минимаксных задач в однородных системах 

ВВЕДЕНИЕ
1. РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ.
1.1. Краткая характеристика распределительных задач теории расписания.
1.1.1. Примеры возникновений и применения распределительных задач в различных
сферах человеческой деятельности
1.1.2. Распределительные задачи и теория расписаний
1.1.3. Класс статических распределительных задач.
1.1.4. Основные понятия теории решения распределительных задач.
1.1.5. Однородные распределительные задачи теории расписаний.
1.1.6. Характеристика сложности решения распределительных задач теории
расписаний .
1.2. Математическое описание однородной распределительной задачи
1.2.1. Теоретикомножественная формулировка однородной распределительной задачи. .
1.2.2. Критериальнооценочная составляющая однородной распределительной задачи
1.2.3. Оптимизационная составляющая однородной распределительной задочи
1.3. Методы решения однородных распределительных задач и их классификация.
1.3.1. Детерминировонные методы точного решения однородных распределительных
1.3.2. Анализ методов точного решения однородных распределительных задач.
1.3.3. Детерминированные методы приближнного решения однородных
распределительных задач
1.3.4. Анализ детерминированных методов приближнного решения однородных
распределительных задач
1.3.5. Эвристические методы приближнного решения однородных распределительных
задач .
1.3.6. Анализ эвристических методов приближнного решения однородных
распределительных задач
1.4. Эволюционногенетические алгоритмы приближенного решения однородных
распределительных задач.
1.4.1. Общий принцип работы эволюционногенетических алгоритмов
1.4.2. Представление данных в генах
1.4.3. Стратегии отбора
1.4.4. Стратегии формирования нового поколения.
1.4.5. Генетические операторы
1.5. Алгоритм Романовского точного решения однсгодных распределительных задач
1.5.1. Особенности и возможности алгоритма Романовского.
1.5.2. Ход работы алгоритма Романовского
1.6. Выводы ПО ПЕРВОЙ ГЛАВЕ
2. БИНАРНОДЕКОМПОЗИЦИОННЫЙ ПОДХОД К РЕШЕНИЮ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ ВЫСОКОЙ РАЗМЕРНОСТИ
2.1. ДЕКОМПОЗИЦИЯ КАК метод ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ
2.1.1. Блочная декомпозиция кок возможный подход к решению распределительных задач
2.1.2. Пример применения блочной декомпозиции к решению распределительной задачи
2.1.3. Второй пример решения распределительной задачи на основе алгоритма бинарной декомпозиции
2.2. Критерии оценки ресурсной и оптимизационной эффективностей методов решения
РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ.
2.2.1. Проблема эффективной оценки сравниваемых методов решения распределительных задач
2.2.2. Точностная оценка эффективности сравниваемых методов решения распределительных задач.
2.2.3. Ресурсная оценка эффективности сравниваемых методов решения распределительных задач.
2.3. Практическое применение блочнодекомпозиционного подхода к решению распределительных ЗАДАЧ
2.3.1. Алгоритм блочнодекомпозиционного решения распределительных задач
2.3.2. Вычислительный эксперимент бинарнодекомпозиционного решение распределительных задач на базе эволюционногенетического алгоритма.
2.4. Выводы по второй главе
3. СТРУКТУРНОПАРАМЕТРИЧЕСКОЕ УСОВЕРШЕНСТВОВАНИЕ ЭВОЛЮЦИОННОГЕНЕТИЧЕСКОГО АЛГОРИТМА .
3.1. Базовая модель эволюционногенетических алгоритмов
3.1.1. Математическая модель базового эволюционногенетического алгоритма.
3.1.2. Алгоритмическая реализация базового эволюционногенетического алгоритма
3.1.3. Пример использования базового эволюционногенетического алгоритма
3.2. МОДИФИКАЦИЯ стратегии формирования нового поколения в эволюционногенетических
АЛГОРИТМАХ .
3.2.1. гмчк улучшение формирования нового поколения о эволюционногенетическом алгоритме.
3.2.2. Пример использования модифицированного эволюционногенетического алгоритма .
3.2.3. Вычислительный эксперимент для сравнения эффективности модифицированного и базового эволюционногенетических алгоритмов.
3.3. Зависимость оптимизационной эффективности эволюционно гнетичгских алгоритмов от
РАЗМЕРНОСТИ ЗАДАЧИ И ПАРАМЕТРОВ АЛГОРИТМЛ.
3.3.1. Влияние количества устройств на оптимизационную эффективность эволюционногенетических алгоритмов
3.3.2. Исследование оптимизационной эффективности эволюционногенетических алгоритмов с использованием элитных особей.
3.3.3. Повышение оптимизационной эффективности эволюционногенетических алгоритмов с помощью бинарной декомпозициино
3.4. Выводы ПО ТРЕТЬЕЙ ГЛАВЕ.
4. МОДИФИКАЦИЯ АЛГОРИТМА РОМАНОВСКОГО С ИСПОЛЬЗОВАНИЕМ ПРИБЛИЖЕННЫХ МЕТОДОВ
4.1. АЛГОРИТМИЧЕСКОЕ ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМА РОМАНОВСКОГО УТОЧНЕНИЕМ ВЕРХНЕЙ
ГРАНИЦЫ
4.1.1. Модификация начального этапа алгоритма Романовского с использованием списочного алгоритма.
4.1.2. Пример использования традиционного прима вычисления верхней границы алгоритма Романовского.
4.1.3. Пример использования для вычисления верхней границы списочного алгоритма
4.1.4. Анализ роботы алгоритма Романовского и его списочной модификации по результатам примеров.
4.1.5. Сравнение эффективности работы алгоритмо Романовского и его списочной модификации по результатам вычислительного эксперимент
4.2. Разработка эффективных слособов выделения 2задачи алгоритма Романовского.
4.2.1. Способ использования метода двоичного деления для выделения гзадачи алгоритма Романовского
4.2.2. Пример использования метода двоичного деления для выделения гзадачи алгоритма Романовского
4.2.3. Способ использования методе линейного спуска для выделения гзадачи алгоритма Романовского
4.2.4. Пример использования метода линейного спуска для выделения гзадачи алгоритма Романовского.
4.2.5. Пример использования метода последовательного спуска для выделения гзадачи алгоритма Романовского
4.2.6. Сравнение и анализ примеров использования разных способов выделения задачи .
4.2.7. Вычислительный эксперимент для сравнения эффективности модификацией алгоритма Романовского с использованием разных способов выделения задачи.
4.3. Модификация начального этапа алгоритма Романовского с использованием эволюционногенетических ал горитмо в
4.3.1. Пример использовании эволюционногенетической модификации алгоритма Романовского
4.3.2. Вычислительный эксперимент по сравнению списочной и эволюционногенетической модификаций алгоритма Романовского
4.4. Выводы по четвертой главе
5. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ ИССЛЕДОВАНИЙ РЕШЕНИЯ ОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ.1.
5.1. Структура программного обеспечения.
5.1.1. Задачи и функции программного обеспечения диссертационных исследований
5.1.2. Структурные составляющие программного обеспечения решения распределительных задач.
5.1.3. Функциональная структура программного обеспечения.
5.2. Объектноориентированная модель программного обеспечения.
5.2.1. Организация данных программного обеспечения.
5.2.2. Структура хранения данных программного обеспечения
5.3. Интерфейс программного обеспечения.
5.3.1. Основной оконный интерфейс
5.3.2. Компонент интерфейса программного обеспечения Меню
5.3.3. Компонент интерфейса программного обеспечения Панель инструментов
5.3.4. Компонент интерфейса программного обеспечения Эксперименты
5.3.5. Компонент интерфейса программного обеспечения Вкладки эксперимента
5.3.6. Компонент интерфейса программного обеспечения Статус
5.4. Выводы по пятой главе
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ


Также показана зависимость оптимизационной эффективности ЭГА от количества устройств. Были рассмотрены способы повышения, оптимизационной эффективности ЭГА при решении РЗ на большое количество устройств. ЭГА хорошие результаты показал алгоритм блочной декомпозиции, предложенный во второй главе. В четвертой главе исследуется способы повышения эффективности точного алгоритма Романовского. В качестве начального значения верхней границы в АР берется суммарное количество необходимого ресурса для выполнения всех работ на любом из устройств, что соответствует такому распределению работ по устройствам, при котором все работы назначены на одно из устройств. Эта оценка с очевидностью завышена, поэтому в качестве начального распределения работ по устройствам целесообразнее взять распределение, которое было получено с помощью приближенного алгоритма, причем в качестве начального значения верхней границы нужно брать значение максимальной загрузки устройств для данного распределения. Использование такого подхода уменьшит интервал поиска оптимального распределения, вследствие чего уменьшится количества шагов итераций алгоритма. Что касается нижней границы поиска, то Романовский для выделения гзадач использовал полусумму нижней и верхней границ. Было показано, что можно использовать другие способы, которые дают повышение скорости нахождения решения, а именно использовать линейный спуск с шагом к, который равняется 1 или 2. Было показано, что использование линейного спуска с шагом 1 увеличивает эффективность алгоритма. Рассмотрен ещ один прим, связанный с формированием первого приближения. В качестве приближенного метода для получения первого приближения в АР можно использовать метод критического пути или ЭГА. При использовании в качестве первого приближения ЭГА в АР для некоторых задач могут получаться очень значимые результаты. Так, например, для РЗ с двумя устройствами выигрыш составил несколько тысяч раз. ЭГА, практически сравнивается по ресурсным характеристикам с АР, использующим метод критического пути. Пятая глава посвящена алгоритмической разработке программного обеспечения, позволяющего проводить имитационное моделирование. Для проведения вычислительных экспериментов при исследовании решения однородных РЗ теории расписаний различными методами, а так же для накопления статистической информации по результатам решения данных задач необходимо удобное в использовании ПО. Автором показано, что эта цель в работе достигнута, и разработанное, испытанное и использованное им в исследованиях ПО зарегистрировано в Роспатенте. В заключении сформулированы основные выводы по результатам диссертационных исследований и разработок, в которых показывается, что цель работы достигнута, и все отдельные задачи, намеченные для достижения цели решены, а также намечаются перспективы использования результатов работы для дальнейшего развития теории расписаний. Примером распределительной задачи РЗ в машиностроении является задача построения расписания процесса обработки заготовок некоторой совокупностью независимых станков . Процесс изготовления партии деталей включает параллельную обработку каждой отдельной независимой заготовки станком. Не существует связи между заготовками, каждая заготовка может быть обработана на любом станке из заданного множества. Длительность изготовления каждой отдельной детали предполагается известной. Она может быть как детерминированной, так и случайной величиной. Каждый станок в определенный момент времени может обрабатывать не более одной заготовки, при этом обработка заготовки выполняется до изготовления детали, т. Время обработки каждой отдельной заготовки зависит от станка, на котором деталь изготавливается, т. При построении наилучшего по быстродействию расписания процесса изготовления деталей необходимо решить в какой именно последовательности должны обрабатываться заготовки каждым станком. В данной задаче работы, по характеру поступления на обработку в систему обслуживания, являются независимыми, при этом порядок их поступления в систему обслуживания не определен, и может носить случайный характер.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.321, запросов: 244