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

• Автор: Жикулин, Артем Александрович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Ростов-на-Дону
• Количество страниц: 325 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1 РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ И МЕТОДЫ ИХ РЕШЕНИЯ

1.1 Распределительные задачи в технике, технологиях и научных исследованиях

1.2 Сущность и математическая модель распределительной задачи и ее однородного варианта

1.2.1 Основные понятия и базовая структура распределительной задачи..

1.2.2 Математическая модель однородной распределительной задачи..

1.2.3 Критериальная оценка решений однородной распределительной задачи

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

1.3.1 Точные методы решения однородных распределительных задач

1.3.2 Списочные методы приближенного решения однородных распределительных задач

1.3.3 Эвристические методы приближенного решения оптимизационных задач
1.4 Выводы по первой главе
2 ПОСТРОЕНИЕ СРАВНИТЕЛЬНОЙ БАЗЫ ДЛЯ ИМИТАЦИОННОГО ИССЛЕДОВАНИЯ НОВЫХ АЛГОРИТМОВ РЕШЕНИЯ РЗ
2.1 Задачи и возможности построения эталонных алгоритмов решения ОРЗ..
2.1.1 Перспективы сравнительного исследования новых алгоритмов решения РЗ
2.1.2 Планирование экспериментального исследования ресурсновременных возможностей точных алгоритмов решения ОРЗ
2.2 Исследование ресурсно-временных возможностей алгоритма полного перебора при решении ОРЗ
2.3 Анализ ресурсно-временных возможностей АР при решении ОРЗ
2.4 Комбинационно модифицированный алгоритм Романовского точного
решения ОРЗ
2.4.1 Исследование возможных способов повышения быстродействия АР при решении ОРЗ
2.4.2 Комбинационная модификация АР точного решения ОРЗ
2.4.3 Пример применения комбинационно модифицированного алгоритма Романовского
2.5 Экспериментальное исследование ресурсных характеристик
комбинационно модифицированного АР
2.5.1 Исследование ресурсной эффективности КМАР при решении РЗ малой размерности
2.5.2 Расширенное исследование ресурсной эффективности КМАР на трех исполнительной системе
2.5.3 Расширенное исследование ресурсной эффективности КМАР на четырех исполнительной системе
2.5.4 Исследования ресурсной эффективности КМАР на исполнительной системе с т>4
2.6 Выводы по второй главе
3 СТРУКТУРНАЯ МОДИФИКАЦИЯ АЛГОРИТМА РОМАНОВСКОГО ДЛЯ
БЫСТРОГО ПРИБЛИЖЕННОГО РЕШЕНИЯ ОДНОРОДНЫХ
РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ
3.1 Модификация алгоритма Романовского методом глубокого отката и
максимальной загрузки
3.1.1 Исследование ресурсоемких для КМАР вариантов РЗ и возможных путей их решения
3.1.2 Ресурсоэффективная модификация КМАР максимизацией загрузки исполнителей и глубоким откатом
3.1.3 Структурно-модифицированный алгоритм решения г-задачи в методе Романовского

3.1.4 Пример применения структурно-модифицированного алгоритма Романовского
3.1.5 Перспективы расширенного использования структурно-модифицированного алгоритма Романовского
3.2 Экспериментальное исследование эффективности СМАР при решении РЗ малой размерности
3.2.1 Исследование ресурсно-временных характеристик СМАР
3.2.2 Расширенное исследование ресурсных характеристик на трех и четырех исполнительных системах
3.2.3 Исследование точностных характеристик СМАР
3.3 Экспериментальное исследование эффективности СМАР при решении РЗ повышенной размерности
3.3.1 Планирование эксперимента по исследованию СМАР и разработка показателей оценки его результатов
3.3.2 Исследование решения ОРЗ на оптимальность
3.3.3 Исследование точностных характеристик СМАР на основе ПФЭ
3.3.4 Расширенное исследование ресурсных характеристик структурно-модифицированного алгоритма Романовского
3.4 Дополнительные экспериментальные исследования эффективности СМАР на повышенной размерности РЗ
3.4.1 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 3-5 исполнительной системы и широкого диапазона размеров заданий
3.4.2 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 5-7 исполнительной системы и дополнительно расширенного диапазона размеров заданий
3.4.3 Выборочные исследования ресурсно-точностной эффективности СМАР на повышенной размерности РЗ
3.5 Исследование возможных путей улучшения точностной эффективности СМАР

slack = zxm- ^ r.

(1.12)
2. slj - «недогруженность» у-того исполнителя при рассматриваемом z, т.е.
3. tail- общий еще не использованный запас «недогруженное» к моменту комплектованияу'-того исполнителя, т.е.

tail = slack ~^slk . (1-14)

Решение z-задачи осуществляется в соответствии со следующими правилами.
Пр. 1. Подмножества Wj комплектуются заданиями иу е W последовательно, начиная с W].
Пр.2. Из элементов (заданий) множества W по убыванию значений их
которой осуществляются включения элементов В Wj .
Пр.З. Выбор очередного задания из очереди Ь для включения его в рассматриваемое }У] производится следующим образом.
Пр.3.1. Если «недогруженность» у'-того исполнителя л7у больше
включается первое задание очереди Ь .
Пр.3.2. В противном случае, из очереди к в IV; включается задание , которое удовлетворяет условию
slj =z-R).
(1.13)
размеров (г{ > гг'2 гi ) строится очередь
согласно
максимального размера распределяемых заданий rmax = max{?-. | r; e R], to в JVf

(1.15)