Содержание к диссертации
Введение
1 Распределительные задачи теории расписаний и методы их решения 20
1.1 Распределительные задачи в технике, технологиях и научных исследованиях 20
1.2 Сущность и математическая модель распределительной задачи и ее однородного варианта 23
1.2.1 Основные понятия и базовая структура распределительной задачи 23
1.2.2 Математическая модель однородной распределительной задачи 28
1.2.3 Критериальная оценка решений однородной распределительной задачи 30
1.3 Анализ методов решения однородной распределительной задачи 32
1.3.1 Точные методы решения однородных распределительных задач 33
1.3.2 Списочные методы приближенного решения однородных распределительных задач 38
1.3.3 Эвристические методы приближенного решения оптимизационных задач 42
1.4 Выводы по первой главе 54
2 Построение сравнительной базы для имитационного исследования новых алгоритмов решения рз 56
2.1 Задачи и возможности построения эталонных алгоритмов решения ОРЗ 56
2.1.1 Перспективы сравнительного исследования новых алгоритмов решения РЗ 56
2.1.2 Планирование экспериментального исследования ресурсно-временных возможностей точных алгоритмов решения ОРЗ 57
2.2 Исследование ресурсно-временных возможностей алгоритма полного перебора при решении ОРЗ 59
2.3 Анализ ресурсно-временных возможностей АР при решении ОРЗ 65
3
2.4 Комбинационно модифицированный алгоритм Романовского точного решения ОРЗ 69
2.4.1 Исследование возможных способов повышения быстродействия АР при решении ОРЗ 69
2.4.2 Комбинационная модификация АР точного решения ОРЗ 74
2.4.3 Пример применения комбинационно модифицированного алгоритма Романовского 76
2.5 Экспериментальное исследование ресурсных характеристик
комбинационно модифицированного АР 79
2.5.1 Исследование ресурсной эффективности КМАР при решении РЗ малой размерности 79
2.5.2 Расширенное исследование ресурсной эффективности КМАР на трех исполнительной системе 83
2.5.3 Расширенное исследование ресурсной эффективности КМАР на четырех исполнительной системе 87
2.5.4 Исследования ресурсной эффективности КМАР на исполнительной системе с m>4 91
2.6 Выводы по второй главе 99
3 Структурная модификация алгоритма романовского для быстрого приближенного решения однородных распределительных задач 101
3.1 Модификация алгоритма Романовского методом глубокого отката и максимальной загрузки 101
3.1.1 Исследование ресурсоемких для КМАР вариантов РЗ и возможных путей их решения 101
3.1.2 Ресурсоэффективная модификация КМАР максимизацией загрузки исполнителей и глубоким откатом 108
3.1.3 Структурно-модифицированный алгоритм решения z-задачи в методе Романовского 110
3.1.4 Пример применения структурно-модифицированного алгоритма Романовского 112
3.1.5 Перспективы расширенного использования структурно-модифицированного алгоритма Романовского 115
3.2 Экспериментальное исследование эффективности СМАР при решении РЗ
малой размерности 116
3.2.1 Исследование ресурсно-временных характеристик СМАР 116
3.2.2 Расширенное исследование ресурсных характеристик на трех и четырех исполнительных системах 121
3.2.3 Исследование точностных характеристик СМАР 123
3.3 Экспериментальное исследование эффективности СМАР при решении РЗ
повышенной размерности 127
3.3.1 Планирование эксперимента по исследованию СМАР и разработка показателей оценки его результатов 127
3.3.2 Исследование решения ОРЗ на оптимальность 131
3.3.3 Исследование точностных характеристик СМАР на основе ПФЭ 134
3.3.4 Расширенное исследование ресурсных характеристик структурно-модифицированного алгоритма Романовского 137
3.4 Дополнительные экспериментальные исследования эффективности СМАР
на повышенной размерности РЗ 141
3.4.1 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 3-5 исполнительной системы и широкого диапазона размеров заданий 141
3.4.2 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 5-7 исполнительной системы и дополнительно расширенного диапазона размеров заданий 146
3.4.3 Выборочные исследования ресурсно-точностной эффективности СМАР на повышенной размерности РЗ 149
3.5 Исследование возможных путей улучшения точностной эффективности 3.6 Выводы по третьей главе 154
4 Исследование селективно-перестановочного алгоритма приближенного решения орз и методов улучшения его точностной эффективности 156
4.1 Решение ОРЗ на основе комбинированного использования СМАР и СПА с
одинарными перестановками 156
4.1.1 Условия комбинированного применения СМАР и СПА с одинарными перестановками для решения ОРЗ 156
4.1.2 Исследование точностной эффективности СПАО при решении РЗ малой размерности 157
4.1.3 Расширенное исследование точностной эффективности СПАО на 4-х исполнительной системе 160
4.1.4 Анализ возможных способов повышения точности работы СПАО 163
4.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием мультиперестановок 164
4.2.1 Базовые понятия и определения СПА с мультиперестановками 164
4.2.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием мультиперестановок 170
4.3 Решение ОРЗ на основе комбинированного использования СМАР и СПА с
мультиперестановками 172
4.3.1 Исследование точностной эффективности комбинированного алгоритма «СПАО-СПАМ» на четырех исполнительной системе 172
4.3.2 Исследование точностной эффективности комбинации алгоритма «СПАО-СПАМ» при решении РЗ повышенной размерности 177
4.3.3 Исследование возможных способов повышения точности работы СПАМ 181
4.4 Селективно-перестановочный алгоритм решения ОРЗ с использованием эквивалентных перестановок 184
4.4.1 Эквивалентные преобразования распределительных матриц 184
4.4.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием эквиперестановок 186
4.4.3 Повышение точности решения ОРЗ на основе комбинации СМАР и СПА с эквиперестановками 188
4.5 Исследование ресурсно-временных характеристик СПА 196
4.5.1 Исследование ресурсно-временных характеристик СПА при решении РЗ малой размерности 196
4.5.2 Исследование ресурсно-временных характеристик СПА на 4-х исполнительной системе 200
4.5.3 Исследование ресурсно-временных характеристик СПА при решении РЗ повышенной размерности 205
4.6 Выводы по четвертой главе 211
Заключение 212
Список сокращений 214
Список используемых источников 215
- Математическая модель однородной распределительной задачи
- Исследование ресурсно-временных возможностей алгоритма полного перебора при решении ОРЗ
- Ресурсоэффективная модификация КМАР максимизацией загрузки исполнителей и глубоким откатом
- Расширенное исследование точностной эффективности СПАО на 4-х исполнительной системе
Введение к работе
Актуальность темы. Расширение масштабов современного производства, необходимость координации совместных действий социумов и коллективов требует жесткого планирования работ, процессов, действий во всех сферах человеческой деятельности. Эффективность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. Поэтому в последние годы много внимания уделяется исследованиям в области теории расписаний, занимающейся проблемами упорядочивания.
Наиболее известной в теории расписаний задачей упорядочивания является задача построения оптимального расписания процесса выполнения некоторого конечного множества заданий некоторым множеством исполнителей. Эта задача относится к классу NP-полных задач, поэтому чрезвычайно сложна для теоретического и экспериментального исследования. Существующие точные методы решения распределительной задачи (РЗ) характеризуются экспоненциальной сложностью относительно ее размерности и при определенных условиях не позволяют даже для задач невысокой размерности получать оптимальные решения за приемлемое время. Приближенные методы обладают высокой скоростью решения и достаточно хорошими точностными свойствами, однако иногда погрешность получаемых ими решений может быть существенной и не удовлетворять предъявляемым к ней требованиям. Доказано, например, что отклонение от оптимума решения РЗ методом критического пути (МКП) может достигать 30%. В связи с этим, возникает задача в создании быстрых приближенных алгоритмов решения РЗ, обладающих высокими точностными показателями. В случаях, когда требуется получение точного решения РЗ, появляется необходимость в повышении ресурсно-временной результативности существующих точных алгоритмов решения, что позволит расширить область задач, для которых оказывается возможным получать решения за приемлемое время.
Таким образом, диссертационная работа посвящена решению актуальной научно-технической задачи связанной с исследованием однородных распределительных задач (ОРЗ) с целью разработки высокоэффективных алгоритмов их решения.
Степень разработанности темы исследований. Исследованию проблем, связанных с решением распределительных задач теории расписаний, посвящены труды многих отечественных ученых, таких как Танаев B.C., Шкурба В.В., Романовский И.В., Алексеев О.Г., Головкин Б.А., Пашкеев
С.Д., Шафранский Я.М., Соколов Б.В., Португал В.М., Бирман И.Я., Еме-личев В.А., Комлик В.И., Алибеков Б.И., Лазарев А.А., Ларионов А.М., Майоров С.А., Нейдорф Р.А., Кобак В.Г., Севастьянов С.В., Твердохлебов В.А., Кушников В.А., Резчиков А.Ф., Иващенко В.А., Охтилев М.Ю. и др. Не меньшее внимание исследованию данной проблемы уделяли и зарубежные коллеги: Беллман Р., Джонсон С.М., Джексон Дж.Р., Коффман Э.Г., Конвей Р.В., Максвелл В.Л., Миллер Л.В., Гэри М., Джонсон Д., Brucker P., Kelley J., Walker M., Krone M., Таха Х.А., Pinedo M.P., Blaze-wicz J. и многие другие.
За последнее время заметно ослабление интереса к исследованию классических схем решения этих задач. Скорее всего, это произошло по двум причинам. Во-первых, абстрактный, даже выхолощенный характер постановки задачи теории расписаний формирует у многих ученых мнение об их слабой практической полезности. Во-вторых, долгие попытки построить точные и быстрые алгоритмы решения РЗ не давали до сих пор существенных результатов. Они ограничивались обычно несколькими процентами. Поэтому основные усилия были направлены на построение приближенных алгоритмов. Однако, по мнению автора, оба мнения об актуальности работ над методами решения РЗ по меньшей мере спорны. Это обусловлено тем, что, с одной стороны, эти методы лежат в основе любых прикладных методов решения реальных задач, а, с другой стороны, поисковые возможности их усовершенствования не исчерпаны.
В Южном регионе в выбранной для исследования области можно отметить работы этого направления Нейдорфа Р.А. и Кобака В.Г., а также их учеников (Будиловского Д.М., Красного Д.Г., Титова Д.В.). Кобаком В.Г. под руководством проф. Нейдорфа Р.А. защищена докторская диссертация на тему «Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки». Этой группой ученых предложено и решено много интересных задач различной направленности. Однако, проблема NP-полноты распределительной задачи по-прежнему не решена. Существующие точные алгоритмы решения РЗ, гарантирующие нахождение оптимума по заданному критерию, не обеспечивают решение многих задач за приемлемое время при их высокой размерности или неблагоприятном сочетании размеров заданий. Для решения таких РЗ используют быстрые приближенные алгоритмы, которые не гарантируют оптимум, но позволяют находить приемлемые по точности решения. Часто оценка у этих решений лучше, чем у решений, полученных точными алгоритмами за ограниченное время. Решения РЗ, найденные приближенными ал-
горитмами, но имеющие оценку по критерию оптимизации лучшую или ту же, что дает точный алгоритм за ограниченное условиями решения время, в данной работе названы фактически полученными алгоритмом решениями РЗ.
Однако, при определенных условиях точность существующих приближенных алгоритмов решения РЗ может резко снижаться. Поэтому в теории расписаний актуальны две задачи: снижение ресурсоемкости точных алгоритмов решения РЗ и разработка быстродействующих алгоритмов, являющихся приближенными, но с высокой вероятностью гарантирующих точность решения, приближающуюся к оптимальной.
Цель и основные задачи диссертационной работы. Основной целью диссертационного исследования является сокращение времени точного решения ОРЗ и разработка алгоритмов быстрого улучшения тех решений, которые получены либо при остановке точного алгоритма в связи с временным ограничением, либо в результате работы приближенного алгоритма.
Для достижения поставленной цели необходимо решить ряд научных и практических задач:
-
Исследовать возможности существующих алгоритмических средств точного решения ОРЗ и использования их как эталонов для обеспечения научно-исследовательских задач теории расписаний.
-
Разработать точный алгоритм решения ОРЗ с существенно повышенными по сравнению с алгоритмом Романовского (АР) ресурсно-временными характеристиками.
-
Разработать алгоритм приближенного решения ОРЗ с высокими ресурсно-временными характеристиками, обеспечивающий высокую вероятность получения оптимального решения и невысокую ошибку для фактически полученных решений.
-
Разработать и исследовать эффективные варианты селективно-перестановочного подхода как инструмента повышения точности приближенных решений ОРЗ при приемлемых ресурсно-временных затратах.
-
Создать программное средство, автоматизирующее групповое проведение вычислительных экспериментов и их статистическую обработку, для решения ОРЗ с применением существующих и вновь разработанных алгоритмов.
Основные научные результаты и положения, выносимые на защиту, и их научная новизна:
-
Разработан, концептуально обоснован и экспериментально проверен с использованием специально разработанного программного средства комбинационно модифицированный АР (КМАР), содержащий новый для АР механизм обеспечения комбинационной уникальности загрузки исполнителя при обходе ветвей дерева вариантов решений, что существенно повышает его быстродействие (в среднем в 5600 раз) с сохранением свойств точного оптимизационного алгоритма (с. 69-79). Например, в диапазоне от 4 до 8 исполнителей, и до 50 заданий выигрыш по времени решения составляет от 10- до 15000-кратного (с. 87-99), а при 3-х исполнителях может достигать 200000-кратного (с. 83-87).
-
Разработан, концептуально обоснован и экспериментально проверен структурно-модифицированный приближенный вариант КМАР - СМАР, новизна которого состоит во включении в АР алгоритмов формирования максимальной загрузки исполнителей во время перебора заданий и глубокого отката к первому исполнителю с целью дополнительного сокращения рассматриваемых вариантов решения задачи (с. 102-117). Это позволило получить ресурсно-временную результативность на 1-2 порядка выше, а в некоторых частных случаях и на 5 порядков выше, чем у КМАР при незначительном ухудшении точности решения ОРЗ (с. 117-153). Так, для задач с 2 исполнителями СМАР обеспечивает оптимум решения в 100% случаев, для 3-8 исполнителей и 12-31 распределяемых заданий – в основном от 75 до 100%, а в среднем в ~98% случаев, при этом ошибка у неоптимальных решений оказывается в пределах 0,5 - 4% от значения оптимума (с. 117-128, с. 143-153). Для 3-5 исполнителей и 31-51 распределяемых заданий по имеющимся данным СМАР обеспечивает оптимум решения в 100% случаев (с. 128-143).
-
Разработаны, программно реализованы и экспериментально исследованы варианты селективно-перестановочных алгоритмов, новизна которых заключается во введении в известный алгоритм одинарных перестановок групповых мульти- и эквиперестановок (с. 166-174 и 186-190), существенно улучшающих точность решений ресурсно-ограниченных и приближенных алгоритмов. Они обеспечивают улучшение результатов СМАР по проценту оптимальных и приближенных к оптимальным решений от ~47% до 100% в зависимости от конкретной размерности и структуры ОРЗ (с. 190-198).
4. Предложен, концептуально обоснован и экспериментально проверен алгоритм приближенной оценки оптимальности решения распределительных задач с узким относительно номинала диапазоном значений оценочного ресурса распределяемых заданий (с. 132-135).
Теоретическая значимость диссертационной работы:
-
Разработанная модификация КМАР улучшения ресурсно-временных характеристик алгоритма Романовского с сохранением его статуса точного алгоритма раскрывает новые возможности создания быстродействующих модификаций метода ветвей и границ, как для решения ОРЗ, так и для решения других сводящихся к ним задач теории расписаний.
-
Разработанная модификация КМАР - СМАР, понижающая его статус до приближенного, существенно расширяет область применения метода ветвей и границ в ОРЗ за счет повышения его быстродействия при возможности решать задачи теории расписаний и подобные им задачи дискретной оптимизации с высокой, достигающей 0,98, вероятностью получения оптимального решения.
-
Исследование возможностей и результатов комбинированного применения селективно-перестановочного подхода с использованием, как известных ранее одинарных, так предложенных в ходе разработки мультиперестановок и эквиперестановок, показали его существенную эффективность, и как метода улучшения исходного допустимого решения ОРЗ, и как самостоятельного метода решения задач ОРЗ.
-
Предложенный приближенный алгоритм оценки оптимальности решения ОРЗ ограниченной размерности позволяет в ряде частных случаев получать более достоверную нижнюю оценку решения ОРЗ по минимаксному критерию по сравнению с теоретической нижней оценкой и, тем самым, более достоверно оценивать близость найденного приближенным алгоритмом решения к оптимуму при невозможности получения гарантированно оптимального решения точным алгоритмом за приемлемое время.
-
Теоретическая значимость результатов работы, указанная в первом и четвертом пунктах обусловливает существенный вклад в создание сравнительной базы для обеспечения научно-исследовательских изысканий по развитию существующих и созданию новых методов и алгоритмов решения задач теории расписаний.
Практическая значимость диссертационной работы:
-
Ресурсно-временная результативность точного решения ОРЗ повышена в среднем в 5600 раз (для некоторых частных задач до 200000), что на порядки уменьшает время решения как производственных, так и научно-исследовательских ОРЗ.
-
Обеспечена ресурсно-временная результативность решения ОРЗ на 1-2 порядка выше (в частных случаях на 5), чем у КМАР при ухудшении его точности не более 4% от оптимума, что обеспечивает уменьшение еще на несколько порядков времени решения практических задач, не требующих абсолютного оптимума.
-
Повышена точность работы селективно-перестановочного алгоритма приближенного решения ОРЗ введением мульти- и эквипереста-новок в среднем на 15%, а для некоторых частных случаев в ~2 раза, что повышает вероятность получения оптимальных и приближенных к ним быстрых решений ОРЗ.
-
Разработанный комплекс точного и приближенных алгоритмов решения ОРЗ позволяет применять их комбинированное использование на основе мониторинга хода решения распределительной задачи, добиваясь получения за ограниченное время решения, характеризующегося высокой вероятностью оптимальности и приемлемой близостью к оптимуму неоптимальных результатов.
-
Практическая проверка программного комплекса и разработанных в диссертации алгоритмов при решении производственных, научных и учебных задач показали их работоспособность и подтвердили заявленные положительные эффекты от их применения.
-
На основе разработанных в диссертационной работе алгоритмов решения ОРЗ построены программные средства, на которые получены свидетельства о государственной регистрации № 2013616055, № 2013616060, № 2013615965 и № 2013616088, ссылки на которые помещены в раздел "Основные публикации по теме диссертации". Их можно использовать для решения ОРЗ внешними программами. Программное обеспечение «Автоматизированная система экспериментальных исследований однородных распределительных задач теории расписаний «Autoscheduler» (свидетельство № 2013616055), позволяет сократить трудозатраты при проведении вычислительных исследований в области ОРЗ и повысить точность их приближенных решений.
Реализация результатов работы. Разработанные в диссертационной работе алгоритмы решения задач теории расписаний большой размерности были реализованы в ЗАО "СКБ "Орион" (г. Санкт-Петербург) на этапе эскизного проектирования системы мониторинга состояния сложных технических объектов в реальном масштабе времени и позволили обоснованно подойти к процедурам диспетчеризации вычислительных процессов, а также рационального распределения ограниченных информационных ресурсов. Кроме того, полученные в диссертации научные и прикладные результаты нашли применение в научно-исследовательских разработках кафедры программного обеспечения вычислительной техники и автоматизированных систем ДГТУ по направлению «Технологии распределенных вычислений и систем», а также внедрены в учебный процесс кафедры при изучении задач теории расписаний в рамках курсов «Исследование операций» и «Структуры и алгоритмы обработки данных».
Соответствие паспорту специальности. Область диссертационных исследований соответствует паспорту специальности 05.13.01 – «Системный анализ, управление и обработка информации (вычислительная техника и информатика)», пунктам: 1 – «Теоретические основы и методы системного анализа, оптимизации, ... принятия решений и обработки информации»; 2 – «Формализация и постановка задач системного анализа, оптимизации, ... принятия решений и обработки информации»; 3 – «Разработка критериев и моделей описания и оценки эффективности решения задач системного анализа, оптимизации, ... принятия решений и обработки информации»; 4 – «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, ... принятия решений и обработки информации»; 5 – «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, ... принятия решений и обработки информации».
Методы исследования. В диссертационной работе применялись методы системного анализа, исследования операций, теории расписаний, поисковой дискретной оптимизации, математической статистики и теории планирования экспериментов. При создании программного средства решения ОРЗ использовались методы объектно-ориентированного программирования.
Достоверность результатов исследования. Достоверность полученных в ходе диссертационного исследования научных результатов обеспечивается правильным применением методов системного и статистического анализа, имитационного моделирования, обоснованным по-
строением вычислительных экспериментов. Количество численных экспериментов при исследованиях составило более 150000 опытов. Статистическая представительность вычислительных экспериментов обеспечивалась обоснованным количеством опытов. Программное обеспечение исследований, с помощью которого осуществлялось проведение численных экспериментов, прошло государственную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам. Подтверждает достоверность работы высокий статус ее поддержки госбюджетной тематикой Минобрнауки, апробацией результатов на форумах Международного уровня, публикацией результатов в изданиях, признаваемых ВАК.
Соответствие диссертации научному плану работ и целевым
комплексным программам. Тема диссертации сформулирована в соот
ветствии с тематическим планом Донского государственного
технического университета и списком «Приоритетные направления
развития науки, технологий и техники и перечень критических технологий
Российской Федерации», утвержденного Президентом Российской
Федерации (№ Пр-842 и № Пр-843 от 21 мая 2006 г).
Апробация результатов диссертационной работы. Основные
результаты диссертационной работы докладывались и обсуждались на
международных научных конференциях «Математические методы в
технике и технологиях – ММТТ»: ММТТ-26 (НГТУ, Нижний Новгород,
27 – 30 мая 2013 г.), ММТТ-27 (ТГТУ, Тамбов, 3 – 5 июня 2014 г.); на
международных научных семинарах (МНС): I МНС «Системный анализ,
управление и обработка информации» (Дивноморское, 27-29 сентября
2010 г.), II МНС «Системный анализ, управление и обработка
информации» (Дивноморское, 27 сентября – 2 октября 2011 г.), III МНС
«Системный анализ, управление и обработка информации»
(Дивноморское, 27 сентября – 2 октября 2012 г.), IV МНС «Системный анализ, управление и обработка информации» (Дивноморское, 29 сентября – 3 октября 2013 г.); на X международном научно-техническом форуме «Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012)» (ДГТУ, Ростов-на-Дону, 9-11 октября 2012 г.).
Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета в 2012-2014 гг.
Публикации по теме диссертационной работы. Основные результаты диссертационной работы опубликованы в 21 работах, из которых 6 –
самостоятельные публикации. При этом 3 статьи опубликованы в ведущих изданиях, входящих в список ВАК РФ. Получено 4 свидетельства о государственной регистрации программ для ЭВМ.
В 15 совместных работах лично автором проведена алгоритмическая проработка, программная реализация и экспериментальные исследования комбинационной и структурной модификаций АР [1,2,16,21], вариантов СПА [3,9,10,12,13,17], комбинированного алгоритма «СМАР-СПА» [1,8]. В [5,15] автором разработана общая структура программного средства решения ОРЗ и осуществлена его программная реализация.
Математическая модель однородной распределительной задачи
Достоверность результатов исследования. Достоверность полученных в ходе диссертационного исследования научных результатов обеспечивается правильным применением методов системного и статистического анализа, имитационного моделирования, представительности по числу опытов вычислительных экспериментов. Общее количество численных экспериментов, проведенных при решении различных задач и параметров алгоритмов, составило около 150000 опытов. Статистическая представительность вычислительных экспериментов обеспечивалась не менее 100 параллельными опытами. Программное обеспечение исследований, с помощью которого осуществлялось проведение численных экспериментов, прошло государственную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.
Кроме того, достоверность подтверждается высоким статусом поддержки работы на уровне госбюджетной тематики Минобрнауки, широкой апробацией результатов на научных форумах Международного уровня, публикацией основных результатов в изданиях, признаваемых ВАК. Соответствие диссертации научному плану работ и целевым комплексным программам. Тема диссертационной работы сформулирована в соответствии с тематическим планом Донского государственного технического университета, а также лежит в русле задач из списка «Приоритетные направления развития науки, технологий и техники и перечень критических технологий Российской Федерации», утвержденного Президентом Российской Федерации (№ Пр-842 и № Пр-843 от 21 мая 2006 г).
Апробация основных теоретических и практических результатов диссертационной работы. Основные результаты диссертационной работы докладывались и обсуждались на международных научных конференциях «Математические методы в технике и технологиях – ММТТ»: ММТТ-26 (НГТУ, Нижний Новгород, 27 – 30 мая 2013 г.), ММТТ-27 (ТГТУ, Тамбов, 3 – 5 июня 2014 г.); на международных научных семинарах (МНС): I МНС «Системный анализ, управление и обработка информации» (Дивноморское, 27-29 сентября 2010 г.), II МНС «Системный анализ, управление и обработка информации» (Дивноморское, 27 сентября – 2 октября 2011 г.), III МНС «Системный анализ, управление и обработка информации» (Дивноморское, 27 сентября – 2 октября 2012 г.), IV МНС «Системный анализ, управление и обработка информации» (Дивноморское, 29 сентября – 3 октября 2013 г.); на X международном научно-техническом форуме «Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012)» (ДГТУ, Ростов-на-Дону, 9-11 октября 2012 г.).
Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета в 2012-2014 гг.
Публикации по теме диссертационной работы. Основные результаты диссертационной работы опубликованы в 21 работах, из которых 6 – самостоятельные публикации. В 15 работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. При этом 3 статьи опубликованы в ведущих рецензируемых изданиях, входящих в список ВАК РФ. Получено также 4 свидетельства о государственной регистрации программы для ЭВМ.
Диссертационная работа состоит из введения, четырех глав, заключения и приложений.
Первая глава диссертации посвящена обзору РЗ теории расписаний и методам их решения. В первых параграфах главы описана общая модель РЗ и ее основные характеристики и свойства. Приведено подробное математическое описание однородной РЗ, которая выбрана для диссертационного исследования.
В последующих параграфах проведен аналитический обзор существующих методов решения РЗ, который позволил выделить наиболее перспективные направления исследований: усовершенствование алгоритма Романовского в части его ресурсно-временной эффективности при условии минимальной потери точности решения, а также применение селективно-перестановочного алгоритма как инструмента быстрого повышения точности приближенных решений.
Во второй главе с целью эталонного обеспечения экспериментов по исследованию точности разработанных новых методов и алгоритмов решения РЗ проведено исследование ресурсно-временных возможностей двух известных алгоритмов точного решения однородной РЗ: алгоритма полного перебора и алгоритма Романовского. Исследование показало, что эти методы малопригодны, как для решения реальных задач теории расписаний, так и для инструментального алгоритмического обеспечения научно-исследовательских задач разработки новых методов и алгоритмов в этой области знания.
Далее во второй главе проведено системное исследование алгоритмического механизма решения z-задачи АР, которое выявило одну из причин логически неоправданного затягивания ее решения. Она состоит в том, АР осуществляет перебор на каждом исполнителе всех возможных наборов заданий, тогда как оценку варианта определяют лишь сочетания их размеров.
Описана разработанная комбинационая модификация АР, которая позволяет устранить обнаруженный дефект АР путем избирательного пропуска в процедуре решения z-задач тех правил, этапов и шагов, которые приводили к перебору на исполнителях наборов заданий, заведомо повторяющих уже проверенный ранее результат.
В последнем параграфе главы приведены результаты экспериментальных исследований ресурсно-временных характеристик КМАР на различных диапазонах РЗ, которые подтверждают его высокую эффективность по сравнению с классическим АР.
Третья глава диссертации посвящена структурно-модифицированному приближенному варианту КМАР, сущность и модификация которого состоит в максимальной загрузке каждого из исполнителей и глубоком откате к первому исполнителю с сокращением рассматриваемых вариантов.
Исследование ресурсно-временных возможностей алгоритма полного перебора при решении ОРЗ
В силу NP-полноты решаемых ОРЗ, комбинаторное исследование и аналитическая оценка точности новых и модифицированных методов и алгоритмов, а также их ресурсно-временной эффективности, не представляется возможным. Поэтому единственно доступным инструментом анализа их свойств, возможностей и перспектив применения является имитационное моделирование решений различных РЗ на достаточно больших и статистически значимых выборках с различными исходными данными. Такое исследование позволяет качественно и количественно оценить, как условную (относительно идеального оптимума) точность, так и временные ресурсы решений. Кроме того, возникает возможность оценить некие абсолютные количественные характеристики показателей качества этих решений. Это, например, фактические результаты распределений в виде оценок максимальной загрузки исполнителя (1.5), неравномерности загрузки исполнителей и т.п. Сравнение же с оптимальным решением каждой РЗ возможно только в случае ее решения каким-либо из точных методов, гарантирующих получение оптимального решения.
Однако в силу NP-полноты и связанной с нею высокой ресурсоемкостью существующие точные методы позволяют находить оптимальные решения за приемлемое время в основном только для распределительных задач малых размерностей. Поэтому экспериментальное исследование ресурсно-точностных свойств любого нового метода или алгоритма решения РЗ следует начать с изучения его работы при решении задач малых размерностей. Это позволит получить достоверную оценку близости находимых разработанным алгоритмом решений к оптимальным в исследуемом диапазоне исходных данных РЗ и, тем самым, оценить условия, при которых перспективы его применения могут оказаться наиболее обнадеживающими, и провести само исследование алгоритма для больших размерностей и его доработку более эффективно.
В связи с этим разработан, спланирован и реализован имитационный вычислительный эксперимент по исследованию ресурсно-временных возможностей двух известных точных алгоритмов классического решения ОРЗ: алгоритма полного перебора (АПП) и алгоритма Романовского (АР). Нужно заметить, что алгоритм полного перебора использован и для проверки правильности работы запрограммированного классического алгоритма Романовского. Кроме того, данный вычислительный эксперимент и все последующие реализованные в работе эксперименты проведены с помощью разработанного в рамках диссертационного исследования программного средства для имитационного моделирования и решения ОРЗ «Autoscheduler», в котором реализованы основные существующие и разработанные в настоящей работе алгоритмы. На разработанное программное средство получено свидетельство о государственной регистрации программы для ЭВМ № 2013616055 (см. рис. А.1 в приложении А) [102]. Материалы, посвященные алгоритмической разработке и описанию программного средства «Autoscheduler», приведены в приложении Б.
Описание исследований ресурсно-временных возможностей АПП и АР и их результаты приводятся в следующих пунктах.
Планирование экспериментального исследования ресурсно-временных возможностей точных алгоритмов решения ОРЗ
Для экспериментального решения поставленной задачи целесообразно применить методы планирования экспериментов, которые позволяют значительно экономить ресурсно-временные затраты, и регуляризовать оценку их результатов. В работе выбран метод планирования факторных двухуровневых экспериментов, в частности, двухуровневый полнофакторный эксперимент (ПФЭ), отличающийся простотой в реализации и минимальными ресурсными затратами на эксперимент, но достаточно хорошей информативностью [103,104].
Для реализации этого подхода составлен план проведения эксперимента, который позволяет наиболее достоверно оценить влияние важнейших параметров размерности и структуры распределительной задачи на ресурсные характеристики любого исследуемого алгоритма при минимально возможном количестве реализованных опытов. Факторами в планируемом полнофакторном эксперименте выбраны следующие основные параметры, определяющие, согласно накопленного опыта исследования и решения однородной распределительной задачи, качество ее решения [6,7,50,51,78]:
Выбор малых начальных уровней и интервалов варьирования факторов x1 и x2 определяется высокой ресурсоемкостью алгоритма полного перебора, а также, в отдельных случаях, алгоритма Романовского при решении однородных распределительных задач размерности выше третьей [78]. Основным ограничителем размерности точек плана (а значит количества построений одного варианта решения РЗ) являлся при этом АПП. Для получения ожидаемого времени решения им задачи перебора использовалась приближенная оценка времени рассмотрения АПП одного варианта решения РЗ, получаемая на основе предварительных оценок времени работы данного алгоритма. Соответствующие расчеты приведены в Приложении В.
Выбор начального уровня и интервала варьирования фактора х3 основан на опыте изучения влияния этого параметра ОРЗ на результаты работы различных точных и приближенных алгоритмов ее решения. Размеры заданий в опытах имитационных экспериментов генерируются в пределах выбранной ширины диапазона по равномерному закону распределения с одинаковым средним значением, равным 50.
Для обеспечения статистической представительности вычислительного эксперимента запланирована реализация по 100 опытов в каждой точке плана. Всего для трехфакторного эксперимента размерность ПФЭ составляет вместе с центром плана - 9 опытов. Поэтому объем эксперимента составил 900 опытов. В следующем пункте приводятся и анализируются результаты запланированных и проведенных вычислительных экспериментов.
Ресурсоэффективная модификация КМАР максимизацией загрузки исполнителей и глубоким откатом
На диаграмме 4.5 также видно, что применение КРЗ в СПАМ, как и в СПАО, позволяет получить лучшие по точности результаты (примерно в 3 раза больше найденных оптимальных решений) по сравнению с ММК. Дальнейшее экспериментальное подтверждение этого феномена позволит сделать вывод, что использование данного критерия в СПА при решении РЗ является предпочтительным.
Результаты проведенного вычислительного эксперимента также показали, что среднее отклонение (рассчитанное по всем опытам эксперимента) полученных после применения СПАМ приближенных решений РЗ от оптимальных осталось примерно таким же (как при использовании в нем ММК, так и КРЗ), что и до его применения, и составило для СПАМ-ММК примерно относительно оптимума, а для СПАМ-КРЗ – 0,6%. Это говорит о том, что СПАМ в пределах исследуемого в данных опытах диапазона РЗ примерно в равной степени улучшает приближенные решения СМАР и СПАО, характеризующиеся как небольшим, так и более значительным отклонением от оптимального.
Максимальное отклонение (также рассчитанное по всем опытам эксперимента) полученных после применения СПАМ приближенных решений РЗ в случае использования в алгоритме ММК также сохраняется и составляет 3,47% относительно оптимума, однако при использовании КРЗ в СПАМ оно существенно снижается (примерно в 2 раза) и составляет 1,81%. Это еще раз подтверждает эффективность применения КРЗ в СПА по сравнению с ММК.
Таким образом, по результатам проведённого в данном пункте исследования общий процент оптимально решенных СМАР распределительных задач с применением СПАМ достиг в случае использования в последнем ММК 99,06%, а при использовании КРЗ – 99,48%. Это на 0,16 и 0,23 % соответственно больше по сравнению с применением только одинарных перестановок в СПА для улучшения полученных СМАР приближенных решений относительно всей исходной выборки. Если рассмотреть процент оптимально решенных СПАМ задач не от общей совокупности, а только от выборки неоптимизированных СМАР задач, то данный процент вырос более значительно (примерно на 8,5-12,3% по сравнению со СПАО) и составляет в случае использования в СПАМ минимаксного критерия 50,8%, а при использовании КРЗ – 72,9%. То есть комбинированное применение СПАО и СПАМ позволяет примерно на 50-70% (в зависимости от используемого в алгоритме критерия оптимизации) сократить количество неоптимизированных СМАР до оптимума решений РЗ.
Исследованию эффективности применения СПАМ на РЗ повышенной размерности (вариант п. 3.4.1) посвящен следующий пункт. Исследование точностной эффективности комбинации алгоритма «СПАО-СПАМ» при решении РЗ повышенной размерности
Результаты применения СПАМ для улучшения неоптимизированных СМАР и СПАО приближенных решений РЗ повышенной размерности в рассмотренном в пункте 3.4.1 варианте эксперимента (см. приложение Н) приведены в таблице 4.4.
В первом столбце таблицы указаны номера опытов и в скобках значения варьируемых в эксперименте параметров РЗ. Далее для каждого рассматриваемого алгоритма указано количество и процент от общей выборки в 300 РЗ (в скобках) полученных данными алгоритмами доказано неоптимальных решений (НОР). Поскольку в 0-4 опытах СМАР оптимизировал все РЗ, для краткости результаты данных опытов объединены в одну строку (1-ую в рассматриваемой таблице). Аналогичным образом объединены результаты 7 и 8 опытов (4-я строка).
Анализ представленных в таблице 4.4 результатов показал, что применение СПАМ для решения РЗ повышенной размерности позволяет достаточно хорошо улучшить точностную эффективность решения РЗ, поскольку общее по эксперименту количество НОР снизилось в случае использования в данном алгоритме ММК примерно на 13%, а при использовании КРЗ – на 25%.
Кроме того, анализ таблицы 4.4 показывает, что на точность работы СПАМ так же, как и на точность СПАО, существенное влияние оказывает ширина диапазона размеров распределяемых заданий. Причем в отличие от СПАО эффективность СПАМ с увеличением данного параметра, наоборот, возрастает.
Данный вывод достаточно хорошо иллюстрируются приведенной на рисунке 4.6 диаграмме, на которой представлена зависимость доли (относительно общего числа неоптимизированных СПАО решений) оптимально улучшенных СПАМ неоптимальных решений от ширины диапазона размеров распределяемых заданий. Этот же рисунок наглядно иллюстрирует более высокую эффективность СПАМ с КРЗ, особенно для большего диапазона ресурсных размеров заданий в распределяемой выборке.
Таким образом, использование СПАМ позволяет улучшить точность СПАО при решении наиболее трудных для него РЗ с большим разбросом размеров заданий. Это является еще одним подтверждением эффективности использования данного алгоритма и комбинированного подхода в целом.
Аналогично предыдущим исследованиям (см. приложение Н), дальнейшее подробное изучение эффективности работы СПАМ продолжено на тех РЗ рассматриваемого эксперимента, которые СПАО не позволил оптимизировать (в выборке объемом 54 РЗ для СПАМ-ММК и 44 РЗ для СПАМ-КРЗ). Результаты данного исследования представлены в таблице 4.5.
В первом столбце таблицы указаны номера исследуемых опытов ПФЭ. В следующем блоке столбцов для сравнения приведены результаты работы СПАО: 179 количество НОР NH и отклонения НОР от гарантированно оптимальных решений (ГОР) в процентах: среднее %а и максимальное %т. В следующем (втором) блоке столбцов представлены результаты применения к полученным СМАР и СПАО результатам, оцененных, как НОР, СПАМ с применением ММК. В первом столбце этого блока построчно приведены: количество оптимально улучшенных N+, количество субоптимально улучшенных /Vі (улучшенных, но не до оптимального варианта, решений РЗ) и количество неулучшенных N данным алгоритмом НОР. Во втором столбце блока указаны значения среднего (%я), максимального (%т) и суммарного (%s) процентов отклонения НОР от ГОР для каждой полученной выборки оптимально улучшенных, субоптимально улучшенных и неулучшенных решений РЗ. Далее в третьем блоке аналогичным образом приведены результаты работы СПАМ с КРЗ.
Расширенное исследование точностной эффективности СПАО на 4-х исполнительной системе
Класс RepEstimates отвечает за формирование статистических данных по результатам вычислительного опыта, которые позволяют оценить точность, а класс RepTimes - ресурсоемкость работы исследуемых в опыте алгоритмов.
Методы класса RepEstimates формируют таблицу со статистическими данными, в которой для каждого исследуемого в опыте алгоритма приводится оценка по минимаксному критерию результата решения данным алгоритмом каждой заданной в опыте РЗ, а также рассчитанные отклонения (в условных величинах и в процентах) этой оценки от оценки гарантировано оптимального решения (ГОР) и от оценки его теоретически оптимального варианта (ТОР). Кроме того, в таблице для каждой РЗ указывается оценка ее ТОР и минимально хвостовая (МХО) оценка.
Также для каждого исследуемого в опыте алгоритма методы класса RepEstimates рассчитывают и выводят в статистическую таблицу максимальное, среднее и суммарное по опыту отклонения (в условных величинах и в процентах) полученных им решений от ГОР и от ТОР. Кроме того, рассчитывается количество полученных исследуемым алгоритмом ГОР, количество решений, оптимальность которых доказана с помощью оценок ТОР и МХО, количество ФАР (решений, для которых не доказано, являются ли они оптимальными) и НОР (доказано неоптимальных решений).
Методы класса RepTimes формируют статистическую таблицу, в которой для каждого исследуемого в опыте алгоритма приводится оценка времени решения данным алгоритмом каждой заданной в опыте РЗ, а также рассчитывают максимальное, минимальное и среднее по опыту значение этой оценки и ее среднеквадратичное отклонение.
Кроме того, методы данного класса осуществляют анализ совокупности временных оценок на неоднородность по критерию Стьюдента. Если неоднородность выявлена, то исходная совокупность разделяется на три совокупности: основную совокупность оценок и совокупности минимальных и максимальных оценок. Для каждой из этих выборок рассчитывается среднее значение временной оценки и ее среднеквадратичное отклонение, которые также выводятся в статистическую таблицу временных ресурсов исследуемых в опыте алгоритмов.
Класс MathStats содержит набор методов по расчету стандартных статистических величин (таких как среднее выборочное, дисперсия, среднеквадратичное отклонение и др.), а также метод, реализующий анализ выборки на наличие в ней резко отклоняющих значений от ее средней величины по критерию Стьюдента. 246 Б.3.4 Объектно-ориентированная модель блока взаимодействия с пользователем Общая объектно-ориентированная модель блока взаимодействия с пользователем представлена на рисунке Б.3.
Как отмечено в пункте Б.3.1, главным классом блока взаимодействия с пользователем является класс MainForm, который непосредственно организует взаимодействие всех остальных классов и реализует интерфейс главного окна программного средства. Все классы можно функционально разделить на три группы (на рисунке Б.3 выделены прямоугольниками).
Рисунок Б.3 – Объектно-ориентированная модель блока взаимодействия с пользователем 1. В состав первой группы входят классы, отвечающие за ввод параметров вычислительных опытов и вывод результатов их реализации. 2. Вторая группа классов отвечает за ввод параметров работы исследуемых в опыте алгоритмов. 3. Третья группа классов реализует функции чтения (класс ExperimentXmlReader) и сохранения (класс ExperimentXmlWriter) параметров вычислительного опыта и результатов его реализации в файл в унифицированном формате XML. 247 Класс ExperimentListForm отвечает за отображение списка созданных пользователем или загруженных им из файла вычислительных опытов на отдельной форме (панели) программного средства.
Класс ExperimentForm отвечает за ввод условий исследуемых в опыте РЗ, а также формирование списка исследуемых в нем алгоритмов. Кроме того, данный класс реализует вывод на экран полученных исследуемыми в опыте алгоритмами расписаний, а также отображение статистических таблиц по результатам реализованного опыта.
Основные методы класса ExperimentForm приведены в таблице Б.7. Таблица Б.7 – Основные методы класса ExperimentForm Название Назначение void createListsTasksButton_Click (object sender, EventArgs e) Устанавливает введенные пользователем на форме условия исследуемых в опыте РЗ, а также при необходимости (если пользователем выбрана соответствующая опция) генерирует случайным образом размеры распределяемых заданий в заданном диапазоне void addTestButton_Click(object sender, EventArgs e); void deleteTestButton_Click (object sender, EventArgs e) Реализуют добавление и удаление алгоритмов решения РЗ из списка исследуемых в опыте алгоритмов void UpdDecisionDGView (DataGridView ADGView, Decision decision) Отображает на экране полученное алгоритмом расписание для заданной пользователем РЗ void UpdReportDGView() Отображает на экране заданную пользователем статистическую таблицу по результатам опыта Класс ExperimentExecForm представляет собой форму, которая позволяет пользователю выбрать (из общего списка исследуемых в опыте) алгоритмы решения РЗ, которые будут запущены при проведении данного опыта.
Для ввода дополнительных параметров проведения вычислительного опыта (ограничения времени решения алгоритмом отдельной РЗ и имени файла протокола выполнения опыта) используется класс ExperimentsOptionsForm. 248 Класс TestEditForm представляет собой форму добавления выбранного пользователем алгоритма решения РЗ в общий список исследуемых в опыте алгоритмов. Классы CriticalPathParamsForm, GeneticAlgParamsForm и SelPermAlgParamsForm отвечают за настройку параметров работы алгоритма критического пути, эволюционно-генетического алгоритма и селективно-перестановочного алгоритма соответственно.
Описанная выше объектно-ориентированная модель была реализована на языке C# в среде Visual Studio. В результате, было разработано программное средство автоматизированного проведения экспериментальных исследований в области ОРЗ «Autoscheduler», удовлетворяющее приведенным в параграфе Б.1 функциональным требованиям. На разработанное программное средство получено свидетельство о государственной регистрации программы для ЭВМ (Роспатент № 2013616055; заявл. 2013613628; зарег. 26.06.2013) [102].
Классы реализующие разработанные в ходе диссертационного исследования алгоритмы (КМАР, СМАР, СПА, ЭГА с использованием структурно-дифференцируемого элитизма) были реализованы в виде отдельных универсальных программных модулей, которые позволяют использовать их для решения РЗ сторонними программами из различных сфер человеческой деятельности, в которых возникает необходимость планирования выполняемых работ. На большую часть реализованных программных модулей получены свидетельства о государственной регистрации программы для ЭВМ:
