Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий

Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий

Автор: Будиловский, Дмитрий Михайлович

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

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

Год защиты: 2007

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

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

Артикул: 3385045

Автор: Будиловский, Дмитрий Михайлович

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

Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий  Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий 

ВВЕДЕНИЕ .
1. РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ И МЕТОДЫ ИХ РЕШЕНИЯ
1. . Параллельное упорядочивание как важнейший этап составления расписаний
1.2. Математическое описание задачи параллельного упорядочивания.
1.2.1. Работы и операции при составлении расписаний.
1.2.2. Критерии составления расписаний
1.2.3. Характеристика и функциональная классификация задач теории расписаний
1.2.4. Математическая модель классической распределительной задачи
1.3. Основные аспекты выбора методов i 1ия задач теории расписаний
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.5.3. Методы отжига
1.5.4. Мет од роящ ихся частиц i .
1.5.5. Табуированный поиск Т
1.5.6. Эволюционногенетический подход
1.6. ЭВОЛЮЦИОННОГЕНЕТИЧЕСКИЕ методы решения распределительных задач.
1.6.1. Общая характеристика эволюционно генетического подхода.
1.6.2. Представление данных в генах.
1.6.3. Стратегии отбора.
1.6.4. Стратегии формирования нового поколения
1.6.5. Генетические операторы.
1.6.6. Модели ЭГА.
1.6.7. Некоторые обобщения
1.7. ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ
1.7.1. Причины использования приближенных алгоритмов в распределительных задачах
1.7.2. Основания для исследования возможностей эволюционногенетических алгоритмов в
теории расписаний
1.7.3. Основные направления исследований по использованию эволюционногенетических алгоритмов в теории расписаний
1.7.4. Проблемы инструментальной поддержки исследований эволюционногенетических
алгоритмов в теории расписаний
2. ЭВОЛЮЦИОННОГЕНЕТИЧЕСКАЯ МОДЕЛЬ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ И ЕЕ ОСНОВНЫЕ СВОЙСТВА
2.1. Побитовая генетическая модель распределительной задачи.
2.1.1. Влияние сущностных свойств распределительных задач теории расписаний на
генетические модели.
2.1.2. Модель гена распределительной задачи теории расписаний.
2.1.3. Примеры построения и использования побитового гена распределительной задачи.
2.2. Эволюционная модель распределительной задачи и ее основные составляющие
2.2.1. Оператор кроссовера в распределительной задаче.
2.2.2. Оператор мутации в распределительной задаче
2.2.3. Оператор инверсии распределительной задаче.
2.2.4. Оператор выбора в распределительной задаче.
2.3. Эволюционная модель распределительной задачи.
2.3.1. Итерационный процесс поиска ЭГА
2.3.2. Пример организации итерационного поиска в ЭГА
2.3.3. Особенности системы поиска эволюционного алгоритма
2.4. Сравнительный анализ примеров решений
распределительной задачи эвристическими алгоритмами.
2.4.1. Задачи и алгоритмы дм сравнения
2.4.2. Решение задачи эволюционногенетическим алгоритмом.
2.4.3. Решение задачи методом отжига
2.4.4. Решение задачи методом роящихся частиц.
2.4.5. Сравнительная оценка результатов применения к РЗ различных методов и
алгоритмов решения
2.5. ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ.
2.5.1. Состоятельность эволюционногенетических алгоритмов при решении
распределительных задач.
2.5.2. Основные направления исследования и оптимизации свойств эволюционно
генетических алгоритмов в теории расписаний.
3. ИССЛЕДОВАНИЕ ЭВОЛЮЦИОННОЙ ГЕНЕТИЧЕСКОЙ МОДЕЛИ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ
3.1. Система РЗЭГА, задачи и методы ее исследования
3.2. исследование свойств РЗЭГА для 2х УСТРОЙСТВ
3.2.1. Иссчедование точностных показателей
3.2.2. Иссчедование показателей бы стродействия
3.2.3. О перспективных направлениях далънейш их исследований системы РЗЭГА.
3.3. ЕК0Т0РЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ СВОЙСТВ СИСТЕМЫ РЗЭГА ДЛЯ 3Х УСТРОЙСТВ
3.3.1. Исследование нестабильности ЭГА для 3х устройств
3.3.2. Предварительные выводы о нестабильности ЭГА
3.4. Исследование влияния параметров ЭГА на вероятюстную точность решения РЗ
3.4.1. Постановка задачи исследования.
3.4.2. Широкодиапазонное исследование 4х факторного пространства ЭГА.
3.4.3. Исследование найденного перспективного диапазона факторного пространства. .
3.4.4. Реализация стратегии крутого восхождения для отыскания области экстремума ИЗ
3.4.5. Исследование подозрительного на экстремум диапазона
3.4.6. Градиентный поиск в экстремальной области по факторам X и X
3.4.7. Детальное исследование предполагаемой экстремальной области
3.4.8. Эксперимент по проверке экстремальной области
3.5. Влияние весов работ в распределении на степень точности ЭГА.
3.6. Выводы по третье главе
3.6.1. Исследование показателей системы РЗЭГА для двух устройств.
3.6.2. Исследование показателей системы РЗЭГА для трех устройств.
3.6.3. Исследование показателей системы РЗЭГА в зависимости от распределения
весов работ
4. ИССЛЕДОВАНИЕ ФЕНОМЕНА ВЕРОЯТНОСТНОЙ ТОЧНОСТИ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ ПРИ ИСПОЛЬЗОВАНИИ ЭГА
4.1. Теоретикоэкспериментальное обоснование оценки эффективности ЭГА
вероятностной точностью.
4.1.1. Теоретические предпосылки оценки эффективности ЭГ4 вероятностной
точностью
4.1.2. Экспериментальное исследование влияния колва заданий на эффективность ЭГ
4.1.3. Исследование стабильности работы ЭГ4.
4.1.4. Поиск наихудших распределений для ЭГА
4.2. ИМИТАЦИОННОСТАТИСТИЧЕСКИЙ ПОДХОД К ОЦЕНКЕ ОПТИМАЛЬНОСТИ РЕШЕИЯ ЭГА.
4.2.1. Исследование распределительной задачи РЗЭГА на наличие закономерностей
формирования вероятностной точности
4.2.2. Теоретические основы оценки заданных вероятностно точностных условий решения
4.2.3. Предельная ресурсная оценка решения РЗ параллельными ЭГА.
4.3. ИССЛЕДОВАНИЕ БЫСТРОДЕЙСТВИЯ ПРИМЕНЕНИЯ ПАКЕТНОЙ ОБРАБОТКИ
4.3.1. Предпосылки нестабильности времени выполнения операций ЭГЛ.
4.3.2. Экспериментальное исаедование временных характеристик при фиксированном порядке выполнения ЭГА
4.3.3. Экспериментальное исаедование временных характеристик при свободном порядке выполнения ЭГ
4.3.4. Методика оценки верхней границы по времени выполнения ЭГА
4.4. Исследование алгоритма адаптации уровня мутации в процессе решения.
4.5. Выводы по четвертой главе
5. ПРОГРАММНЫЙ КОМПЛЕКС РИОЗЕСТСНЕОиЬЕИ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ .
5.1. Функциональная структура ПК
5.2. Объектноорииггированное конструирование функциональных блоков.
5.3. Структура баз данных ПК РшлнетЗнЕоиик.
5.4. Интерфейс ПК РкоЕСгЗНЕоии и работа с ним
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ


Пятая глава диссертации посвящена алгоритмической разработке модели и реализации программного средства автоматизированного проведения имитационного моделирования. Программное средство ПС выполнено по объектноориентированной парадигме на языке в среде i. Система I обладает разделенной структурой методов и объектов представления РЗ теории расписаний, что обеспечивают простую модификацию параметров ЭГМ или добавления новых методов решения. Система не требовательна к ресурсам, может быть запущена на любом ПК с установленной ОС i и выше. Конкретные показатели потребления аппаратных ресурсов напрямую зависят от размерности РЗ и количества введенных экспериментов. Пользователю предлагается удобная система управления созданным им же набором экспериментов, с возможностью модификации параметров алгоритмов и просмотром результатов вычислений в реальном времени. Предусмотрен также гибкий механизм экспортаимпорта данных в другое ПО. Теория расписаний ТР является одним из наиболее востребованных разделов исследования операций,,. В ней исследуются задачи, в которых необходимо разбить совокупность назначенных к выполнению работ на группы. При этом каждая группа представляет собой обособленную совокупность работ ОСР, выполняемых конкретным техническим средством из нескольких, назначенных для обеспечения всей исходной совокупности работ ИСР. Работы, выделенные в ОСР, выполняются представленным им техническим средством последовательно и независимо от хода выполнения работ других ОСР. Работы каждой ОСР также выполняются в определенной последовательности. Таким образом, процесс выполнения ИСР превращается параллельнопоследовательный, ход его выполнения определяется составленным для этого расписанием, упорядочивающим решение задачи. Задачи упорядочения носят самый общий характер. Результаты, к которым приводит то или иное упорядочение, существенно отличаются. В ряде практических случаев эти различия принимают стоимостной характер или определяются какойлибо другой величиной. Таким образом, составление расписания на данном уровне обобщения представляет собой сочетание процессов упорядочивания двух видов распределение работ на параллельно выполняемые ОС и распределение их в последовательности по исполнителям. Зачастую проблему упорядочивания можно сформулировать так, чтобы выделить параллельное упорядочивание работ как отдельную задачу. Задачи параллельного упорядочивания в теории расписаний рассматриваются при условии, что решены все вопросы, относящиеся к тому, что и каким образом должно быть выполнено. Есть определенное различие между терминами упорядочение и составление расписания. Упорядочение подразумевает формирование очередности операций, выполняемых одним устройством, в то время как составление расписания означает задание последовательности действий нескольким устройствам. Теория расписаний, выделяет вопросы, общие для большинства задач упорядочения. Получающиеся при этом идеализированные модели не могут в точности соответствовать конкретным ситуациям, однако в силу их общности позволяют получать оценки для широкого круга задач в различных областях производства. Основным понятием теории расписаний является понятие операции,. Операцию можно рассматривать как элементарную задачу, подлежащую к выполнению. Набор связанных операций определяет работу. В случае наличия всего одной операции в работе одностадийные системы понятия операции и работы являются идентичными. За исполнение работ расписания ответственны некоторые условные устройства, или, в более общем понимании, исполнители. Разбиение исходного множества работ по исполнителям приводит к взаимно непересекающимся подмножествам работ, относящихся к определенным устройствам. Устройством будем называть исполнителя, способного выполнить целиком некоторую работу. Системой обслуживания называют множество всех устройств, используемых для выполнения некоторого множества работ. Совокупность устройств, работ и условий назначения работ по соответствующим машинам называется процессом обслуживания. Постановка задачи в теории расписаний начинается с описания системы устройств и множества работ. I 1,.

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

28.06.2016

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

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

15.02.2015

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

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


Все новости

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