Содержание к диссертации
ВВЕДЕНИЕ 8
1. РАСПРЕДЕЛИТЕЛЬНЫЕ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ.. 17
1.1. Краткая характеристика распределительных задач теории
расписаний 17
Примеры возникновения и применения распределительных задач в различных сферах человеческой деятельности 17
Распределительные задачи и теория расписаний 18
Класс статических распределительных задач 19
Основные понятия теории решения распределительных задач 21
Однородные распределительные задачи теории расписаний. 22
Характеристика сложности решения распределительных задач теории расписаний 23
1.2. Математическое описание однородной распределительной
задачи 25
Теоретико-множественная формулировка однородной распределительной задачи 25
Критериально-оценочная составляющая однородной распределительной задачи 27
Оптимизационная составляющая однородной распределительной задачи 27
1.3. Методы решения однородных распределительных задач и их
классификация 32
Детерминированные методы точного решения однородных распределительных задач 32
Анализ методов точного решения однородных распределительных задач 35
Детерминированные методы приближённого решения однородных распределительных задач 36
Анализ детерминированных методов приближённого решения однородных распределительных задач 40
Эвристические методы приблиэюённого решения однородных распределительных задач 40
Выводы по применению эвристических методов приближённого решения однородных распределительных задач 45
1.4. ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ ПРИБЛИЖЕННОГО
РЕШЕНИЯ ОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ 45
Общий принцип работы эволюционно-генетических алгоритмов 45
Представление данных в генах 47
Стратегии отбора 48
Стратегии формирования нового поколения 50
Генетические операторы 57
1.5. Алгоритм Романовского точного решения однородных
распределительных задач 54
Особенности и возможности алгоритма Романовского 54
Ход работы алгоритма Романовского 56
1.6. Выводы ПО ПЕРВОЙ главе 58
2. БИНАРНО-ДЕКОМПОЗИЦИОННЬШ ПОДХОД К РЕШЕНИЮ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ ВЫСОКОЙ РАЗМЕРНОСТИ.... 60
2.1. Декомпозиция как метод повышения эффективности
решения распределительной задачи 60
Блочная декомпозиция как возможный подход к решению распределительных задач 60
Пример применения блочной декомпозиции к решению распределительной задачи 62
Второй пример решения распределительной задачи на основе алгоритма бинарной декомпозиции 65
2.2. Критерии оценки ресурсной и оптимизационной
эффективностеи методов решения распределительных задач .... 70
Проблема эффективной оценки сравниваемых методов решения распределительных задач 70
Точностная оценка эффективности сравниваемых методов решения распределительных задач 72
Ресурсная оценка эффективности сравниваемых методов решения распределительных задач 75
2.3. Практическое применение блочно-декомпозиционного
подхода к решению распределительных задач 78
Алгоритм блочно-декомпозиционного решения РЗ 78
Вычислительный эксперимент бинарно-декомпозиционного решение распределительных задач на базе эволюционно-генетического алгоритма 80
2.4. ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ 82
3. СТРУКТУРНО-ПАРАМЕТРИЧЕСКОЕ УСОВЕРШЕНСТВО
ВАНИЕ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКОГО АЛГОРИТМА 83
3.1. Базовая модель эволюционно-генетических алгоритмов . 83
Математическая модель базового эволюционно-генетического алгоритма 83
Алгоритмическая реализация базового эволюционно-генетического алгоритма 86
Пример использования базового эволюционно-генетического алгоритма 91
3.2. Модификация стратегии формирования нового поколения в
эволюционно-генетических алгоритмах 94
Алгоритмическое улучшение формирования нового поколения в эволюционно-генетическом алгоритме 94
Пример использования модифицированного эволюционно-генетического алгоритма 96
3.2.3. Вычислительный эксперимент сравнения эффективности
модифицированного и базового эволюционно - генетических
алгоритмов 100
3.3. ЗАВИСИМОСТЬ ОПТИМИЗАЦИОННОЙ ЭФФЕКТИВНОСТИ
ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ОТ РАЗМЕРНОСТИ ЗАДАЧИ И
ПАРАМЕТРОВ АЛГОРИТМА 103
Влияние количества устройств на оптимизационную эффективность эволюционно-генетических алгоритмов 103
Исследование оптимизационной эффективности эволюционно-генетических алгоритмов с использованием элитных особей 105
Повышение оптимизационной эффективности эволюционно-генетических алгоритмов с помощью бинарной декомпозиции 107
3.4. ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ 109
4. МОДИФИКАЦИЯ АЛГОРИТМА РОМАНОВСКОГО С
ИСПОЛЬЗОВАНИЕМ ПРИБЛИЖЕННЫХ МЕТОДОВ 110
4.1. Алгоритмическое повышение быстродействия алгоритма
романовского уточнением верхней границы по
Модификация начального этапа алгоритма Романовского с использованием списочного алгоритма 110
Пример использования традиционного приёма вычисления верхней границы алгоритма Романовского 112
Пример использования для вычисления верхней границы списочного алгоритма 117
Анализ работы алгоритма Романовского и его списочной модификации по результатам примеров 119
Сравнение эффективности работы алгоритма Романовского и его списочной модификации по результатам вычислительного эксперимент 120
4.2. Разработка эффективных способов выделения z-задачи
алгоритма Романовского 121
Способ использования метода двоичного деления для выделения z-задачи алгоритма Романовского 121
Пример использования метода двоичного деления для выделения z-задачи алгоритма Романовского 122
Способ использования метода линейного спуска для выделения z-задачи алгоритма Романовского 124
Пример использования метода линейного спуска для выделения z-задачи алгоритма Романовского 125
Пример использования метода последовательного спуска для выделения z-задачи алгоритма Романовского 126
Сравнение и анализ примеров использования разных способов выделения z-задачи 127
Вычислительный эксперимент для сравнения эффективности модификацией алгоритма Романовского с использованием разных способов выделения z-задачи 129
4.3. Модификация начального этапа алгоритма Романовского
с использованием эволюционно-генетических алгоритмов 130
Пример использования эволюционно-генетической модификации алгоритма Романовского 130
Вычислительный эксперимент по сравнению списочной и эволюционно - генетической модификаций алгоритма Романовского 132
4.4. Выводы ПО ЧЕТВЕРТОЙ ГЛАВЕ 134
5. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ВЫЧИСЛИТЕЛЬНЫХ
ИССЛЕДОВАНИЙ РЕШЕНИЯ ОДНОРОДНЫХ
РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ 135
5.1. Структура программного обеспечения 135
5.1.1. Задачи и функции программного обеспечения
диссертационных исследований 735
Структурные составляющие программного обеспечения решения распределительных задач 137
Функциональная структура программного обеспечения 138
5.2. Объектно-ориентированная модель программного
обеспечения 140
Организация данных программного обеспечения 140
Структура хранения данных программного обеспечения 143
5.3. Интерфейс программного обеспечения 145
Основной оконный интерфейс 145
Компонент интерфейса программного обеспечения «Меню» 147
Компонент интерфейса программного обеспечения «Панель инструментов» 149
Компонент интерфейса программного обеспечения «Эксперименты» 150
Компонент интерфейса программного обеспечения «Вкладки эксперимента» 151
Компонент интерфейса программного обеспечения «Статус» 157
5.4. Выводы ПО ПЯТОЙ ГЛАВЕ 158
ЗАКЛЮЧЕНИЕ 159
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 161
ПРИЛОЖЕНИЯ 172
Введение к работе
Во многих областях инженерных и управленческих задач широкое практическое распространение получают задачи теории расписания [63,67,77, 85]. При упорядочивании и распределении какого-либо ресурса между исполнителями возникает вопрос эффективного планирования. Оптимальность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. В теории распределительных задач (РЗ), которая является одним из широко исследуемых направлений теории расписаний, основное внимание уделяется вопросам, связанным с построением наилучших календарных планов. Календарный план — это расписание последовательно-параллельного исполнения конечного множества требований, обслуживаемых детерминированными системами одного или нескольких устройств.
Классические РЗ теории расписаний являются схематичными теоретическими моделями многих задач, встречающихся на практике. Они в подавляющем большинстве случаев относятся к классу NP-полных задач, поэтому чрезвычайно сложны для теоретического и экспериментального изучения [46]. Задача составления расписания в наиболее общей формулировке сводиться распределению некоторое конечное множество независимых работ между некоторым множеством независимых устройств. Возникает необходимость в поиске наилучшего алгоритма упорядочения работ, оптимизирующего желаемую меру эффективности - длину результирующего расписания, равномерность загрузки устройств и т.п.
Для получения оптимального решения однородной РЗ используются точные методы решения. Однако, в силу её NP-полноты, с увеличением размерности распределительной задачи, а также при сужении диапазона ресурсных оценок распределяемых заданий получение оптимального решения за доступное время может стать недостижимым. В этой ситуации приходится
ориентироваться на быстрые, но приближенные методы. Однако они не
обеспечивают оптимальность результатов, и могут давать большую погрешность, достигающую 30% [67]. Для практических задач такая потеря точности не всегда является приемлемой. Возникает необходимость в методах, характеризующихся сочетанием противоречивых свойств: зависимостью времени счета от размерности задачи не хуже полиноминальной при точности решения близкой к оптимальной. К такому классу методов относятся эволю-ционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных приближенных алгоритмов [47]. В случаях, когда недопустимо решение отличное от оптимального, появляется необходимость в повышение эффективности методов точного решения за счет их алгоритмических модификаций, позволяющих повысить размерность задач, для которых оказывается возможным получать решения за доступное время.
Все перечисленные положения обусловили тот факт, что диссертационная работа посвящается решению актуальной научно-технической проблемы: исследованию закономерностей решения однородных распределительных задач теории расписаний с целью развития существующих и разработки новых методов её решения.
Цели и основные задачи диссертационной работы
Основной целью диссертационной работы является повышение эффективности решения однородных РЗ теории расписаний. Поставленная цель актуальна как для приближенных, так и для точных методов. При этом для приближенных методов она связана с улучшением точностных показателей, т.е. с приближением решения РЗ к оптимальному. Для точных методов основной проблемой является повышение ресурсных показателей, т.е. снижение потребного для решения задачи ресурса (времени, памяти, пространства и т.п.). Чаще всего, при этом, речь идёт о снижении времени решения
В связи с этим возникла необходимость решения следующих научных
и практических задач:
разработка и исследование методов повышения точностной эффективности ЭГА при решении РЗ высокой размерности;
разработка и обоснование критериев оценки эффективности решения РЗ, информативной для сравнения свойств различных методов и алгоритмов, в особенности, приближённых;
разработка и исследование методов повышения возможностей ЭГА при решении однородных РЗ теории расписаний;
разработка и исследование методов использования приближенных алгоритмов для повышения ресурсной эффективности точного алгоритма Романовского (АР) при решении однородных РЗ теории расписаний;
разработка программного обеспечения (ПО) разработанных методов, способов и алгоритмов решения однородных РЗ, позволяющего проводить сравнительные вычислительные эксперименты и предварительную обработку накопленных статистических данных.
Существенные научные результаты и степень их новизны
Метод бинарной декомпозиции решения РЗ высокой размерности с чётным количеством устройств обработки заданий, существенно повышающий точность решения приближёнными методами, в частности, методом ЭГА (среднее отклонение решения от минимальной оценки сокращается практически до 0), и уменьшающий время решения для некоторых алгоритмов (в 1,5 раз).
Критериальная оценка точностной эффективности приближённого решения РЗ теории расписаний по величине и экспериментальной оценке вероятности отклонения решения от условного минимума, которая, при невозможности оценки оптимума точными методами, информативнее традиционной оценки минимального и среднего значений по серии опытов в условиях имитационного вероятностного моделирования.
Критериальная оценка ресурсной эффективности решения РЗ теории расписаний по экспериментальной оценке границы доверительной вероятности превышения ресурса, которая при объективно присущей используемым для этого алгоритмам, в особенности точным, вероятностной асимметрии, информативнее традиционной оценки минимального, максимального и среднего значений ресурса в эксперименте.
Модифицированная стратегия формирования нового поколения ЭГА путём реализации бинарного турнирного отбора между особями «родителей» и «потомков», которая отсутствует в классических прототипах, и позволяет, по данным статистически представительных исследований (9000 опытов), повысить точность находимого решения в 5-60 раз, в зависимости от размерности и структуры задачи.
Структурная модификация АР путём формирования первого приближения решения РЗ быстрыми приближенными методами, которая позволяет увеличить быстродействие (до 3-4 кратного, а для двух устройств было получено улучшение в несколько тысяч раз) в сравнении с классическим вариантом алгоритма.
Методы исследования
В диссертации применялись методы математического анализа, исследования операций, поисковой оптимизации, теории расписаний и статического анализа.
Для реализации экспериментальных исследований разработано ПО для ЭВМ «Система вычислительных исследований однородных распределительных задач «Optimal», проведено большое количество имитационных экспериментов, результаты которых использованы для получения статистически достоверных оценок результатов исследований. Для реализации ПО применялись концепции объектно-ориентированного программирования.
Практическая значимость диссертационной работы
Рассмотренные в диссертационной работе алгоритмы решения однородных РЗ теории расписаний могут быть использованы в различных сферах человеческой деятельности. Они представляют собой идеализацию для решения многих практических задач, являющихся частью более сложных социальных, экономических, технических и технологических и др. проблем.
Значимыми практическими эффектами применения результатов диссертационных исследований являются:
существенное повышение точности решения для РЗ высокой размерности с чётным количеством устройств, в частности, при использовании ЭГА (среднее отклонение решения от минимальной оценки сокращается для ЭГА практически до 0);
повышение точности решения однородных РЗ (до 60-кратного) для ЭГА, в зависимости от размерности и структуры задачи;
существенное улучшение быстродействия точных алгоритмов решения однородных РЗ (в основном, в 2-3 раза, а для некоторых частных задач - в несколько тысяч раз).
Кроме того, работа дала хорошее практическое приложение в учебном и научном процессе, т.к. предложенные решения позволяют изучать на практике задачи теории расписаний. Автором опубликованы методические указания по теме «Теория расписаний» для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование», «Теория принятия решений», «Теория оптимизации».
В рамках диссертационной работы разработано ПО «Система вычислительных исследований однородных распределительных задач «Optimal» (ФГУ ФИПС свидетельство № 2009616118 от 06.11.2009), с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов при выполнении лабораторных, курсовых и дипломных работ.
Основное содержание работы
Первая глава диссертации посвящена обзору РЗ теории расписаний и существующих методов их решения. Анализ литературных источников позволил выделить в качестве объекта исследования однородную РЗ. В данной главе рассмотрены области применения РЗ, описана их концептуальная модель. Дано математическое описание статической однородной РЗ теории расписаний, которая выделена для исследования.
Данная задача относится к классу NP полных задач, т.е. теоретическая сложность нахождения наилучшего распределения связано с решением экстремальных задач комбинаторного типа, для решения которых требуются большие вычислительные ресурсы. Было выделено два способа решения данных задач: точными методами и приближенными. Точные методы являются наиболее ресурсоемкими, т.к. получение оптимального решения за доступное время может стать недостижимым при увеличении размерности распределительной задачи и сужении диапазона ресурсных оценок распределяемых заданий. Для решения таких трудных задач можно использовать приближенные методы, но решение будет получаться с некоторой погрешностью относительно оптимального.
Для решения однородных РЗ были выделены наиболее перспективные направления исследований: структурная модификация самой РЗ и методов её решения. В связи с этим принято решение о необходимости исследования возможности декомпозиции РЗ, как превентивного этапа её решения. Кроме того, сделан вывод о необходимости совершенствования математических и алгоритмических инструментов решения.
Для исследования возможностей совершенствования были выделены наиболее перспективные методы решения однородных РЗ. В качестве приближенных методов был выбран ЭГА, показавший хорошие точностные результаты в предыдущих исследованиях, проводимых в ДГТУ школой проф. Нейдорфа Р.А. в области теории расписаний. В качестве точного метода был
выбран АР, основанный на методе ветвей и границ, который по производительности в худшем случаи может совпадать с методом полного перебора, но в общем случае работает намного быстрее.
Во второй главе предложена и обоснована блочно-декомпозиционная схема бинарной модификации РЗ и исследовано её влияние на эффективность решения. Данная схема применена для увеличения эффективности решения РЗ высокой размерности.
Рассмотренный алгоритм, не реализующий принцип бинарности на последнем этапе, назван в работе алгоритмом частной бинарной декомпозиции, а в случаи, когда принцип бинарности реализуется на последнем этапе — алгоритмом абсолютной бинарной декомпозиции. Эффективность предложенного метода и построенных на его основе алгоритмов показана в работе на многочисленных примерах, в которых проводились статистически представительные имитационные эксперименты.
Поскольку в первой главе показано, что при решении РЗ у исследователей возникают серьёзные проблемы с оценкой эффективности методов, эта проблема рассмотрена в работе особо тщательно. Показано, что для алгоритмов решения РЗ информативны две оценки: ресурсная и точностная. Под первой понимают затраты (обычно - временные) на решение РЗ данным алгоритмом, а под второй - степень близости полученного решения к оптимуму используемого критерия. При таком определении совершенно очевидно, что для «точных» методов точностной оценки не существует. Ресурсная же оценка характерна и для точных, и для приближённых методов.
В третьей главе диссертации исследуется влияние на решение однородной РЗ структуры ЭГА. Согласно модели выбранной базовой схемы ЭГА используется побитовое представление особи (хромосомы), в которой каждый ген представляет собой закодированный порядковый номер устройства, на которое назначена работа, причем номер гена определяет номер работы.
В связи с поставленной в первой главе задачей была предложена модификация формирования нового поколения для ЭГА. Она заключается в использовании бинарного турнирного отбора, в котором участвуют вновь созданная особь и ее родительская особь. Данная модификации экспериментально сравнивалась с базовым ЭГА, и показала свою эффективность.
Также показана зависимость оптимизационной эффективности ЭГА от количества устройств. Были рассмотрены способы повышения оптимизационной эффективности ЭГА при решении РЗ на большое количество устройств. В данном случае при совместном использовании с модифицированным ЭГА хорошие результаты показал алгоритм блочной декомпозиции, предложенный во второй главе.
В четвертой главе исследуется способы повышения эффективности точного алгоритма Романовского. В качестве начального значения верхней границы в АР берется суммарное количество необходимого ресурса для выполнения всех работ на любом из устройств, что соответствует такому распределению работ по устройствам, при котором все работы назначены на одно из устройств. Эта оценка с очевидностью завышена, поэтому в качестве начального распределения работ по устройствам целесообразнее взять распределение, которое было получено с помощью приближенного алгоритма, причем в качестве начального значения верхней границы нужно брать значение максимальной загрузки устройств для данного распределения. Использование такого подхода уменьшит интервал поиска оптимального распределения, вследствие чего уменьшится количества шагов итераций алгоритма.
Что касается нижней границы поиска, то Романовский для выделения z-задач использовал полусумму нижней и верхней границ. Было показано, что можно использовать другие способы, которые дают повышение скорости нахождения решения, а именно использовать линейный спуск с шагом h, который равняется 1 или 2. Было показано, что использование линейного спуска с шагом 1 увеличивает эффективность алгоритма.
Рассмотрен ещё один приём, связанный с формированием первого приближения. В качестве приближенного метода для получения первого приближения в АР можно использовать метод критического пути или ЭГА.
При использовании в качестве первого приближения ЭГА в АР для некоторых задач могут получаться очень значимые результаты. Так, например, для РЗ с двумя устройствами выигрыш составил несколько тысяч раз. Однако с ростом количества устройств метод, модифицированный на основе ЭГА, практически сравнивается по ресурсным характеристикам с АР, использующим метод критического пути.
Пятая глава посвящена алгоритмической разработке программного обеспечения, позволяющего проводить имитационное моделирование. Для проведения вычислительных экспериментов при исследовании решения однородных РЗ теории расписаний различными методами, а так же для накопления статистической информации по результатам решения данных задач необходимо удобное в использовании ПО. Автором показано, что эта цель в работе достигнута, и разработанное, испытанное и использованное им в исследованиях ПО зарегистрировано в Роспатенте.
В заключении сформулированы основные выводы по результатам диссертационных исследований и разработок, в которых показывается, что цель работы достигнута, и все отдельные задачи, намеченные для достижения цели решены, а также намечаются перспективы использования результатов работы для дальнейшего развития теории расписаний.
