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

• Жикулин, Артем Александрович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Жикулин, Артем Александрович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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 Исследование возможных путей улучшения точностной эффективности СМАР

3.6 Выводы по третьей главе

4 ИССЛЕДОВАНИЕ СЕЛЕКТИВНО-ПЕРЕСТАНОВОЧНОГО АЛГОРИТМА

ПРИБЛИЖЕННОГО РЕШЕНИЯ ОРЗ И МЕТОДОВ УЛУЧШЕНИЯ ЕГО

ТОЧНОСТНОЙ ЭФФЕКТИВНОСТИ

4.1 Решение ОРЗ на основе комбинированного использования СМАР и СПА с одинарными перестановками

4.1.1 Условия комбинированного применения СМАР и СПА с одинарными перестановками для решения ОРЗ

4.1.2 Исследование точностной эффективности СПАО при решении РЗ малой размерности

4.1.3 Расширенное исследование точностной эффективности СПАО на 4-х исполнительной системе

4.1.4 Анализ возможных способов повышения точности работы СПАО

4.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием мультиперестановок

4.2.1 Базовые понятия и определения СПА с мультиперестановками

4.2.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием мультиперестановок

4.3 Решение ОРЗ на основе комбинированного использования СМАР и СПА с мультиперестановками

4.3.1 Исследование точностной эффективности комбинированного алгоритма «СПАО-СПАМ» на четырех исполнительной системе

4.3.2 Исследование точностной эффективности комбинации алгоритма «СПАО-СПАМ» при решении РЗ повышенной размерности

4.3.3 Исследование возможных способов повышения точности работы СПАМ

4.4 Селективно-перестановочный алгоритм решения ОРЗ с использованием

эквивалентных перестановок

4.4.1 Эквивалентные преобразования распределительных матриц

4.4.2 Селективно-перестановочный алгоритм решения ОРЗ с использованием эквиперестановок

4.4.3 Повышение точности решения ОРЗ на основе комбинации СМАР и СПА с эквиперестановками

4.5 Исследование ресурсно-временных характеристик СПА

4.5.1 Исследование ресурсно-временных характеристик СПА при решении РЗ малой размерности

4.5.2 Исследование ресурсно-временных характеристик СПА на 4-х исполнительной системе

4.5.3 Исследование ресурсно-временных характеристик СПА при решении РЗ повышенной размерности

4.6 Выводы по четвертой главе

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

ПРИЛОЖЕНИЕ А Свидетельства о государственной регистрации программ для

ЭВМ

ПРИЛОЖЕНИЕ Б Программное средство «Autoscheduler» имитационного

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

ПРИЛОЖЕНИЕ В Приближенный расчет ожидаемого времени решения РЗ

а

4

ï алгоритмом полного перебора

ПРИЛОЖЕНИЕ Г Построение мат. зависимости среднего времени решения РЗ

методом АПП от параметров ее размерности и структуры

ПРИЛОЖЕНИЕ Д Таблицы ресурсных характеристик КМ АР для 5-8

исполнительных систем

ПРИЛОЖЕНИЕ Е Таблицы ресурсных характеристик СМАР для 3-х и 4-х

исполнительных систем

ПРИЛОЖЕНИЕ Ж Исследование точностных феноменов при решении РЗ малой размерности структурно-модифицированным АР

ПРИЛОЖЕНИЕ 3 Исследование ресурсно-точностных свойств СМАР при решении РЗ для 3-5 исполнительной системы и широкого диапазона размеров

заданий

ПРИЛОЖЕНИЕ И Исследование ресурсно-точностных свойств СМАР при решении РЗ для 5-7 исполнительной системы и дополнительно расширенного

диапазона размеров заданий

ПРИЛОЖЕНИЕ К Методика оценки асимметричных ресурсно-временных

свойств СМАР при решении РЗ

ПРИЛОЖЕНИЕ Л Опытные данные по ресурсным характеристикам СМАР при

решении наиболее ресурсоемких для КМАР задач

ПРИЛОЖЕНИЕ М Сущность и возможности СПА с одинарными перестановками

ПРИЛОЖЕНИЕ Н Исследование точности работы СПАО при решении РЗ

повышенной размерности

ПРИЛОЖЕНИЕ О Пример применения СПАМ для решения ОРЗ

ПРИЛОЖЕНИЕ П Пример применения СПАЭ для решения ОРЗ

ПРИЛОЖЕНИЕ Р Исследование точностной эффективности комбинированного алгоритма «СПАО-СПАМ-СПАЭ» при решении РЗ повышенной размерности

ПРИЛОЖЕНИЕ С Таблицы ресурсных характеристик СПА при решении РЗ

малой размерности

ПРИЛОЖЕНИЕ Т Таблицы ресурсных характеристик СПА для 4-х

исполнительной системы

ПРИЛОЖЕНИЕ У Таблицы ресурсных характеристик СПА для РЗ повышенной размерности

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

ВВЕДЕНИЕ

Актуальность темы. Расширение масштабов современного производства, необходимость координации совместных действий социумов и коллективов существенно усложнили функции организационного управления. Это требует жесткого планирования работ, процессов, действий во всех сферах человеческой деятельности: экономической, управленческой, инженерной и т.д. Эффективность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. Поэтому в последние годы много внимания уделяется исследованиям в области теории расписаний, занимающейся проблемами упорядочивания.

Наиболее известной в теории расписаний задачей упорядочивания является задача построения оптимального расписания процесса выполнения некоторого конечного множества заданий некоторым множеством исполнителей. Эта задача относится к классу тУР-полных задач, поэтому чрезвычайно сложна для теоретического и экспериментального исследования. В связи с этим возникает необходимость в создании эффективного алгоритма распределения заданий между исполнителями, оптимизирующего желаемую оценку результирующего расписания: длина расписания, равномерность загрузки исполнителей и т.д.

Однако, в силу А^Р-полноты распределительной задачи (РЗ), нахождение за приемлемое время точного решения задачи даже невысокой размерности является труднодостижимым. Поэтому на практике для их решения в основном используют быстрые приближенные методы. Эти методы позволяют в большинстве случаев находить решения достаточно высокой степени приближения к оптимальному результату, но иногда погрешность может быть существенной и не удовлетворять предъявляемым к ней требованиям. Доказано, например, что отклонение от оптимума решения РЗ методом критического пути (МКП) может достигать 30%. В связи с этим, возникает задача в создании быстрых приближенных алгоритмов решения РЗ, обладающих высокими точностными показателями при низких требованиях к вычислительным ресурсам.

В случаях, когда требуется получение точного решения РЗ, появляется необходимость в повышении ресурсной эффективности существующих точных методов решения за счет их алгоритмических модификаций, позволяющих расширить область задач, для которых оказывается возможным получать решения за приемлемое время.

Таким образом, диссертационная работа посвящена решению актуальной научно-технической проблемы, связанной с исследованием однородных распределительных задач (ОРЗ) с целью разработки высокоэффективных методов их решения.

Степень разработанности темы исследований. Исследованию проблем, связанных с решением распределительных задач теории расписаний, посвящены труды многих отечественных ученых, таких как Танаев B.C., Шкурба В.В., Романовский И.В., Алексеев О.Г., Головкин Б.А., Пашкеев С.Д., Ларионов A.M., Майоров С.А., Новиков Г.И., Португал В.М., Лазарев A.A., Севастьянов C.B., Безгинов А.Н., Нейдорф P.A., Кобак В.Г. и др. Не меньшее внимание исследованию данной проблемы уделяли и зарубежные коллеги: Беллман Р., Джонсон С.М., Джексон Дж.Р., Коффман Э.Г., Конвей Р.В., Максвелл В.Л., Миллер Л.В., Гэри М., Джонсон Д., Brucker P., Kelley J., Walker M., Krone M., Taxa X.A, Pinedo M.P., Blazewicz J. и многие другие.

За последнее время интерес к этим задачам несколько ослаб. Скорее всего, это произошло по двум причинам. Во-первых, абстрактный, даже выхолощенный характер постановки задачи теории расписаний формирует у многих ученых мнение об их слабой практической полезности. Во-вторых, долгие попытки построить точные и быстрые алгоритмы решения РЗ не давали до сих пор существенных результатов. Они ограничивались обычно несколькими процентами. Поэтому основные усилия были направлены на построение приближенных алгоритмов. Однако, по мнению автора, оба мнения об актуальности работ над методами решения РЗ по меньшей мере спорны. Это обусловлено тем, что, с одной стороны, эти методы лежат в основе любых

прикладных методов решения реальных задач, а, с другой стороны, поисковые возможности их усовершенствования не исчерпаны.

В Южном регионе в выбранной для исследования области можно отметить работы этого направления Нейдорфа P.A. и Кобака В.Г., а также их учеников (Будиловского Д.М., Красного Д.Г., Титова Д.В.). Кобаком В.Г. под руководством проф. Нейдорфа P.A. защищена докторская диссертация на тему «Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки». Этой группой ученых предложено и решено много интересных задач различной направленности. Однако, проблема ./VP-полноты распределительной задачи по-прежнему не решена. Существующие точные методы решения исследуемой задачи характеризуются экспоненциальной сложностью ее решения, а приближенные алгоритмы не всегда обеспечивают необходимую точность. Поэтому, как решение проблемы снижения ресурсоемкости точных методов решения РЗ, так и решение проблемы построения быстродействующих приближенных алгоритмов такого решения до сих пор актуальны, и заслуживают внимания в плане их дальнейшего исследования и разработки.

Цель и основные задачи диссертационной работы. Основной целью диссертационного исследования является повышение ресурсной эффективности решения однородных распределительных задач теории расписаний при максимально возможном сохранении точности решения. Для этого необходимо решить ряд научных и практических задач:

1. исследовать возможности существующих алгоритмических средств точного решения ОРЗ для эталонного обеспечения экспериментов по исследованию точности новых методов и алгоритмов их решения;

2. разработать точный алгоритм решения ОРЗ с существенно повышенными по сравнению с алгоритмом Романовского (АР) ресурсно-временными характеристиками;

3. разработать метод приближенного решения ОРЗ с высокими ресурсно-временными характеристиками при минимальной потере качества относительно оптимального;

4. разработать и исследовать эффективные варианты селективно-перестановочного подхода как инструмента преобразования приближенных решений ОРЗ с повышением точности решения при приемлемых ресурсно-временных затратах;

5. создать программное средство, автоматизирующее групповое проведение вычислительных экспериментов и их статистическую обработку, для решения ОРЗ с применением существующих и вновь разработанных алгоритмов.

Основные научные результаты и положения, выносимые на защиту, и их научная новизна.

1. Разработан, теоретически обоснован и экспериментально проверен комбинационно модифицированный АР (КМАР), содержащий новый для АР механизм обеспечения комбинационной уникальности загрузки исполнителя при обходе ветвей дерева вариантов решений, что существенно повышает его быстродействие (в среднем в 5600 раз) с сохранением свойств точного оптимизационного алгоритма (с. 69-79). Например, в диапазоне от 4 до 8 исполнителей, и до 50 заданий выигрыш по времени решения составляет от 10 - до 15000-кратного (с. 87-99), а при 3-х исполнителях может достигать 200000-кратного (с. 83-87).

2. Разработан, теоретически обоснован и экспериментально проверен структурно-модифицированный приближенный вариант КМАР (СМАР), новизна которого состоит в формировании максимальной загрузки исполнителей во время перебора заданий и в глубоком откате к первому исполнителю с целью дополнительного сокращения рассматриваемых вариантов решения задачи (с. 102-117). Это позволило получить ресурсную эффективность на 1-2 порядка выше, а в .некоторых частных случаях и на 5 порядков выше, чем у КМАР при незначительном ухудшении точности

решения (с. 117-153). Так, для ОРЗ с 2 исполнителями СМАР обеспечивает оптимум решения в 100% случаев, для 3-7 исполнителей и 12-31 распределяемых заданий - в основном от 75 до 100%, а в среднем в -98 % случаев, при этом ошибка у неоптимальных решений оказывается в пределах 0,5 - 4% от значения оптимума (с. 117-128, с. 143-153). Для 3-5 исполнителей и 31-51 распределяемых заданий по имеющимся данным СМАР обеспечивает оптимум решения в 100% случаев (с. 128-143).

3. Алгоритмически разработаны, программно реализованы и экспериментально исследованы варианты селективно-перестановочных алгоритмов, новизна которых заключается во введении групповых мульти-и эквиперестановок (с. 166-174 и 186-190), существенно повышающих точность результатов работы ресурсно-ограниченных и приближенных алгоритмов, обеспечивая улучшение результатов СМАР по проценту оптимальных и приближенных к оптимальным решений от -47% до 100% в зависимости от структуры распределительной задачи (с. 190-198).

4. Предложен, теоретически обоснован и экспериментально проверен алгоритм приближенной оценки оптимальности решения распределительных задач с узким относительно номинала диапазоном значений оценочного ресурса распределяемых задач (с. 132-135). Теоретическая значимость диссертационной работы.

1. Разработанный метод КМАР повышения ресурсной эффективности алгоритма Романовского с сохранением его статуса точного метода раскрывает новые возможности . создания быстродействующих модификаций метода ветвей и границ, как для решения ОРЗ, так и для решения других сводящихся к ним задач теории расписаний и общих задач дискретной оптимизации.

2. Разработанный метод СМАР повышения ресурсно-временной эффективности КМАР с изменением его статуса из точного в приближенный метод существенно расширяет границы применения метода ветвей и границ за счет создания его сверхбыстродействующих

модификаций, позволяющих решать как ОРЗ, так и другие сводящиеся к ним задачи теории расписаний и общие задачи дискретной оптимизации, причем с очень высокой вероятностью получения оптимального решения.

3. Исследование возможностей и результатов комбинированного применения селективно-перестановочного подхода с использованием, как известных ранее одинарных, так предложенных в ходе разработки мультиперестановок и эквиперестановок, показали его существенную эффективность, и как метода вторичной оптимизации исходного допустимого решения ОРЗ, и как самостоятельного метода решения задач ОРЗ.

4. Предложенный алгоритм оценки оптимальности решения ОРЗ ограниченной размерности позволяет в ряде частных случаев получать более достоверную нижнюю оценку решения ОРЗ по минимаксному критерию по сравнению с классической нижней оценкой и, тем самым, более достоверно оценивать близость найденного приближенным алгоритмом решения к оптимуму при невозможности получения гарантированно оптимального решения точным алгоритмом за приемлемое время.

5. Теоретическая значимость результатов работы, указанная в первом и четвертом пунктах обусловливает существенный вклад в создание инструментально-алгоритмической базы эталонного обеспечения научно-исследовательских изысканий по развитию существующих и созданию новых методов решения задач теории расписаний и дискретной оптимизации вообще.

Практическая значимость диссертационной работы:

1. существенно снижена ресурсоемкость точного решения однородных РЗ: в среднем в 5600 раз, а для некоторых частных задач - в 200000 раз, что на многие порядки уменьшает время решения как производственных, так и научно-исследовательских распределительных задач;

2. значительно повышена ресурсно-временная эффективность решения РЗ (на 1-2 порядка выше, а в некоторых частных случаях и на 5 порядков выше, чем у КМАР) с небольшим ухудшением его точностных характеристик (не более 4%), что еще более уменьшает время решения практических задач, не требующих абсолютного оптимума при распределении;

3. повышена точность работы селективно-перестановочного алгоритма (СПА) приближенного решения РЗ введением мульти- и эквиперестановок в среднем на 15%, а для некоторых частных случаев - почти в 2 раза, что в соответствующей доле повышает качество сверхбыстрого решения РЗ приближенными алгоритмами;

4. разработанный комплекс точного и приближенных методов решения ОРЗ позволяет применять комбинированное их применение на основе мониторинга хода решения распределительной задачи, добиваясь высокоэффективных результатов и в ресурсно-временном, и в критериально-качественном отношении.

Кроме того, на основе разработанных в рамках диссертационной работы алгоритмов решения РЗ построены эффективные программные средства, на которые получены свидетельства о государственной регистрации № 2013616055, № 2013616060, № 2013615965 и № 2013616088, ссылки на которые помещены в раздел "Основные публикации по теме диссертации" автореферата. Эти средства можно использовать для решения РЗ внешними программами из различных сфер человеческой деятельности, в которых возникает необходимость распределения. Программное обеспечение «Автоматизированная система экспериментальных исследований однородных распределительных задач теории расписаний «АиШзсЬесШег» (свидетельство № 2013616055), позволяет сократить трудозатраты при проведении вычислительных исследований в области однородных распределительных задач и повысить точность их приближенных решений.

Методы исследования. В диссертационной работе применялись методы системного анализа, исследования операций, в частности, теории расписаний,

методы поисковой дискретной оптимизации, математической статистики и теории планирования экспериментов. При создании программного средства имитационного моделирования и решения однородных РЗ использовались методы объектно-ориентированного программирования.

Достоверность результатов исследования. Достоверность полученных в ходе диссертационного исследования научных результатов обеспечивается правильным применением методов системного и статистического анализа, имитационного моделирования, представительности по числу опытов вычислительных экспериментов. Общее количество численных экспериментов, проведенных при решении различных задач и параметров алгоритмов, составило около 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 свидетельства о государственной регистрации программы для ЭВМ.

Диссертационная работа состоит из введения, четырех глав, заключения и приложений.

Первая глава диссертации посвящена обзору РЗ теории расписаний и методам их решения. В первых параграфах главы описана общая модель РЗ и ее основные характеристики и свойства. Приведено подробное математическое описание однородной РЗ, которая выбрана для диссертационного исследования.

В последующих параграфах проведен аналитический обзор существующих методов решения РЗ, который позволил выделить наиболее перспективные направления исследований: усовершенствование алгоритма Романовского в

части его ресурсно-временной эффективности при условии минимальной потери точности решения, а также применение селективно-перестановочного алгоритма как инструмента быстрого повышения точности приближенных решений.

Во второй главе с целью эталонного обеспечения экспериментов по исследованию точности разработанных новых методов и алгоритмов решения РЗ проведено исследование ресурсно-временных возможностей двух известных алгоритмов точного решения однородной РЗ: алгоритма полного перебора и алгоритма Романовского. Исследование показало, что эти методы малопригодны, как для решения реальных задач теории расписаний, так и для инструментального алгоритмического обеспечения научно-исследовательских задач разработки новых методов и алгоритмов в этой области знания.

Далее во второй главе проведено системное исследование алгоритмического механизма решения г-задачи АР, которое выявило одну из причин логически неоправданного затягивания ее решения. Она состоит в том, АР осуществляет перебор на каждом исполнителе всех возможных наборов заданий, тогда как оценку варианта определяют лишь сочетания их размеров.

Описана разработанная комбинационая модификация АР, которая позволяет устранить обнаруженный дефект АР путем избирательного пропуска в процедуре решения г-задач тех правил, этапов и шагов, которые приводили к перебору на исполнителях наборов заданий, заведомо повторяющих уже проверенный ранее результат.

В последнем параграфе главы приведены результаты экспериментальных исследований ресурсно-временных характеристик КМАР на различных диапазонах РЗ, которые подтверждают его высокую эффективность по сравнению с классическим АР.

Третья глава диссертации посвящена структурно-модифицированному приближенному варианту КМАР, сущность и модификация которого состоит в максимальной загрузке каждого из исполнителей и глубоком откате к первому исполнителю с сокращением рассматриваемых вариантов.

В первом параграфе третьей главы детально описан и теоретически обоснован разработанный СМАР. В последующих параграфах проведены подробные экспериментальные исследования ресурно-точностных характеристик СМАР на широком диапазоне РЗ, которые, во-первых, показали его высокую эффективность при решении наиболее ресурсоемких для КМАР задач при незначительном ухудшении точности их решения. Во-вторых, позволили получить ресурсно-точностные оценки его работы в широко употребительных диапазонах РЗ.

Также в третьей главе разработан, описан и экспериментально проверен алгоритм приближенной оценки оптимальности решения распределительных задач с узким относительно номинала диапазоном значений оценочного ресурса распределяемых задач.

Четвертая глава посвящена исследованию эффективности применения селективно-перестановочного алгоритма в составе комплекса способов улучшающей точностные свойства предложенной в диссертационной работе структурной модификации АР.

В первом параграфе четвертой главы проведено экспериментальное исследование эффективности работы СПА с использованием одинарных перестановок заданий по улучшению качества полученных СМАР приближенных решений РЗ. Проведенное исследование показало высокую точностную эффективность исследуемого алгоритма по снижению процента полученных СМАР неоптимальных решений.

Однако применение одинарных перестановок в СПА не всегда позволяет улучшить приближенные решения СМАР. Поэтому в последующих параграфах были разработаны, подробно описаны и экспериментально исследованы варианты селективно-перестановочных алгоритмов, основанные на использовании групповых мульти- и эквиперестановок заданий между исполнителями, что позволило получить более высокие по точности результаты по сравнению с применением в СПА только одинарных перестановок.

В последнем параграфе проведено исследование ресурсных характеристик разработанных вариантов СПА, которые показали, что рассматриваемый алгоритм на исследуемом в диссертационной работе диапазоне РЗ обладает не только высокими точностными характеристиками, но и низкими требованиями к вычислительным ресурсам.

В заключении сжато формалируются основные полученные в работе результаты и их значение для области знания, к которой они относятся, а также для области их практического применения.

В приложениях приведены материалы, посвященные алгоритмической разработке и описанию функциональных возможностей разработанного программного средства имитационного моделирования и решения РЗ, поскольку эти материалы представляют собой скорее технический, чем научный компонент исследований и разработок.

Кроме того, в приложениях приведены не вошедшие в основную часть диссертации дополнительные материалы, которые позволяют более подробно охарактеризовать и проиллюстрировать проведенные в рамках диссертационной работы исследования. В них вынесена большая часть таблиц с численными результатами реализованных в работе вычислительных экспериментов, их описание и другая вспомогательная информация.

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

ИХ РЕШЕНИЯ

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

исследованиях

Теория расписаний является одним из широко распространенных и востребованных разделов исследования операций, в котором строятся и анализируются математические модели календарного планирования (т.е. упорядочивания во времени) различных целенаправленных действий с учетом целевой функции и различных ограничений [1]. Данное научное направление возникло в 1903 году с опубликования известной работы Генри Гантта [2], предложившего одну из самых популярных графических форм представления расписаний, впоследствии названной диаграммой Гантта. Однако активное исследование задач теории расписаний началось с середины 20-го века в связи со стремительным развитием автоматизации производства. Именно в этот период появляются работы Беллмана [3], Джонсона [4], Джексона [5], которые посвящены первым теоретическим исследованиям проблем составления расписаний.

Одним из наиболее распространенных направлений исследований в области теории расписаний является исследование классических распределительных задач (РЗ). В своей общей постановке распределительные задачи представляют собой задачи построения наилучшего плана выполнения некоторого конечного множества работ некоторым множеством исполнителей. Эти задачи возникают во многих сферах человеческой деятельности, в которых требуется организовать эффективное планирование работ, заданий, требований [6-10]:

• организация производственных и сборочных работ на предприятии;

• планирование вычислительных процессов в многоядерных, многопроцессорных и многомашинных комплексах;

• управление системами массового обслуживания потребителей;

• организация расписаний движения поездов, самолетов, общественного городского транспорта;

• управление сложными продолжительными проектами строительства архитектурных сооружений, создания крупных индустриальных объектов и т.п.;

• проведение спортивных мероприятий.

Классическим примером распределительной задачи является задача построения процесса обработки «заготовок» некоторой совокупностью «станков» [11]. Процесс изготовления партии деталей представляет собой последовательно-параллельную обработку множества независимых заготовок некоторой совокупностью станков. Заготовка может быть обработана на любом станке из заданного множества, при этом изготовление деталей из заготовок осуществляется в произвольном порядке.

Длительность изготовления каждой детали предполагается известной и может быть как детерминированной, так и случайной величиной. При этом время изготовления может быть различным и зависит как от вида детали, так и от технических характеристик станка. Каждый станок одновременно может обрабатывать не более одной заготовки. При этом считается, что производственный процесс обработки детали на станке не прерывается до ее окончательного изготовления.

Список литературы диссертационного исследования кандидат наук Жикулин, Артем Александрович, 2014 год

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Лазарев, А.А. Теория расписаний. Задачи и алгоритмы / А.А. Лазарев, Е.Р. Гафаров. - М.: МГУ им. М.В. Ломоносова, 2011. - 222 с.

2. Gantt, H.L. A graphical daily balance in manufacture / H.L. Gantt // ASME Transactions, 1903. - №24. - pp. 1322-1336.

3. Bellman, R. Mathematical aspects of scheduling theory / R. Bellman // Journal of the Society for Industrial and Applied Mathematics, 1956. - vol. 4. - pp. 168-205.

4. Johnson, S.M. Optimal two- and three-stage production schedules with setup times included / S.M. Johnson // Naval Research Logistics Quarterly, 1954. -vol. 1. - pp. 61-68.

5. Jackson, J.R. Scheduling a production line to minimize maximum tardiness / J.R. Jackson // Research Report № 43. Los Angeles University of California Management Sciences Research Project, 1955. - 72 p.

6. Коффман, Э.Г. Теория расписания и вычислительные машины / Э.Г. Коффман. - М.: Наука, 1984. - 334 с.

7. Конвей, Р.В. Теория расписаний / Р.В. Конвей, В.Л. Максвелл, Л.В. Миллер. - М.: Наука, 1975. - 360 с.

8. Танаев, B.C. Теория расписаний. Одностадийные системы / B.C. Танаев, B.C. Гордон, Я.М. Шафранский - М.: Наука, 1984. - 384 с.

9. Танаев, B.C. Теория расписаний. Многостадийные системы / B.C. Танаев, Ю.Н. Сотсков, В.А. Струсевич - М.: Наука, 1989.-328 с.

10. Blazewicz, J. Scheduling Computer and Manufacturing Processes / J. Blazewicz, K.H. Ecker, E. Pesch, G. Schmidt, J. Weglarz. - New York: Springer, 2001.-485 p.

11. Танаев, B.C. Введение в теорию расписаний / B.C. Танаев, В.В. Шкурба. -М.: Наука, 1975.-256 с.

12. Головкин, Б.А. Параллельные вычислительные системы / Б.А. Головкин. -М.: Наука, 1980.-520 с.

13. Ларионов, A.M. Вычислительные комплексы, системы и сети / A.M. Ларионов, С.А. Майоров, Г.И. Новиков. - СПб.: Энергоатомиздат, 1987. -288 с.

14. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. -М.: Мир, 1982 - 416 с.

15. Pinedo, М.Р. Scheduling: Theory, Algorithms, and Systems / M.P. Pinedo. -New York: Springer, 2008. - 671 p.

16. Панкратьев, E.B. Алгоритмы и методы решения задач составления расписаний и других экстремальных задач на графах больших размерностей / Е.В. Панкратьев, A.M. Чеповский // Фундаментальная и прикладная математика, 2003. - Т.9. - №1. - С. 235-251.

17. Красный, Д.Г. Алгоритмические методы повышения эффективности решения неоднородных распределительных задач теории расписаний: дис.... к-та техн. наук: 05.13.01 / Д.Г. Красный; ДГТУ. - Ростов н/Д, 2008.- 185 с.

18. Кофман, А. Методы и модели исследования операций / А. Кофман, А. Анри-Лабордер. - М.: Мир, 1977. - 432 с.

19. Leung, J. Y-T. (editor) Handbook of Scheduling: Algorithms, Models, and Performance Analysis / J. Y-T. Leung (editor). - Danvers: CRC Press, 2004. -1224 p.

20. Гафаров, E.P. Гибридный алгоритм решения задачи минимизации суммарного запаздывания для одного прибора / Е.Р. Гафаров // Информационные технологии, 2007. - № 1. - С. 30-37.

21. Танаев, B.C. Теория расписаний. Групповые технологии / B.C. Танаев, М.Я. Ковалев, Я.М. Шафранский - Минск: Институт технической кибернетики НАН Беларуси, 1998. - 290 с.

22. Севастьянов, С.В. Введение в теорию расписаний / С.В. Севастьянов. -Новосибирск, 2003. - 173 с.

23. Таха, Х.А. Введение в исследование операций. 6-е издание.: Пер. с англ. / Х.А. Таха.- М.: «Вильяме», 2001. - 902 с.

24. Кофман, А. Введение в прикладную комбинаторику / А. Кофман. - М.: Наука, 1975. -480 с.

25. Португал, В.М. Теория расписаний / В.М. Португал, А.И. Семенов. - М.: Знание, 1972.-64с.

26. Нейдорф, P.A. Методологические проблемы теории расписаний / P.A. Нейдорф, В.Г. Кобак // Системный анализ, управление и обработка информации: 1-й межвуз. сб. науч. ст. / ДГТУ; ТТИ ЮФУ. - Ростов н/Д, 2007.-С. 101-108.

27. Нейдорф, P.A. Селективно-перестановочный метод решения задач параллельного распределения заданий между исполнителями. Одинарные перестановки / P.A. Нейдорф // Вестн. Донск. гос. техн. ун-та, 2011.-№ 8.-С. 1185-1200.

28. Нейдорф, P.A. Критериальная инвариантность распределительных задач в однородных двухприборных системах // P.A. Нейдорф, В.Г. Кобак, В.М. Радченко // Известия вузов. Электромеханика, 2003 . - №2. - С. 59-61.

29. Сигал, И.Х. Введение в прикладное дискретное программирование: теория и вычислительные алгоритмы / И.Х. Сигал, А.П. Иванова. - М.: ФИЗМАТЛИТ, 2003. - 240 с.

30. Кобак, В.Г. Соотношение квадратичного и минимаксного оптимальных распределений загрузки однородных трехприборных систем / В.Г. Кобак, P.A. Нейдорф // Известия высших учебных заведений. Электромеханика, 2005. - №3. - С. 60-65.

31. Нейдорф, P.A. О взаимосвязи квадратичного и минимаксного критериев в однородной n-приборной системе с монолитами / P.A. Нейдорф, В.Г. Кобак // Известия ТТИ ЮФУ. Технические науки. - Таганрог: Изд-во ТТИ ЮФ, 2008. - № 5. - С. 168-170.

32. Нейдорф, P.A. Структурно-параметрические условия различия распределений, оптимальных по минимаксному и квадратичному критериям // Нейдорф P.A., Кобак В.Г. // Системы управления и информационные технологии, 2007. - №2. - С. 12-16.

33. Brucker, P. Scheduling Algorithms / P. Brucker. - New York: Springer, 2004. -367 p.

34. Безгинов, A.H. Обзор существующих методов составления расписания. Информационные технологии и программирование / А.Н. Безгинов, С.Ю. Трегубов // Межвузовский сборник статей. Вып. 2(14). - М.:МГИУ, 2005. -60 с.

35. Кобак, В.Г. Эффективные методы решения однородных распределительных задач на основе минимаксного критерия: учеб. пособие / В.Г. Кобак, Д.В. Титов, Т.А. Медведева и др. - Ростов н/Д: Издательский центр ДГТУ, 2013. - 99 с.

36. Baptiste, Ph. Constraint-based scheduling: applying constraint programming to scheduling problems / Ph. Baptiste, C. Le Pape, W. Nuijten // Kluwer Academic Publishers, 2001 - 198 p.

37. Mastrolilli, M. Efficient Approximation Schemes for Scheduling Problems with Release Dates and Delivery Times / M. Mastrolilli // J. of Scheduling, 2003.-V. 6, N6.-P. 521 -531.

38. Севастьянов, С.В. Геометрические методы и эффективные алгоритмы в теории расписаний: дисс. ... д-ра физ.-мат. наук / С.В. Севастьянов-Новосибирск, 2000. - 280 с.

39. Корбут, А.А. Дискретное программирование / А.А. Корбут, Ю.Ю. Финкелыдтейн. -М.: Наука, 1969. - 388 с.

40. Хачатуров, В.Р. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности / В.Р. Хачатуров, В.Е. Веселовский, А.В. Злотов и др. - М.: Наука. 2000. - 354 с.

41. Романовский, И.В. Алгоритмы решения экстремальных задач / И.В. Романовский. - М.: Наука, 1977. - 352 с.

42. Алексеев, О.Г. Комплексное применение методов дискретной оптимизации / О.Г. Алексеев. - М.: Наука, 1987. - 248 с.

43. Кобак, В.Г. Алгоритмический подход к уменьшению времени работы точного метода в однородных системах / В.Г. Кобак, Д.В. Титов // Вестн. Донск. гос. техн. ун-та, 2009. — Т.9. — Спец. выпуск. — С. 24-29.

44. Кобак, В.Г. Модификация алгоритма Алексеева при точном решении минимаксной задачи теории расписания / В.Г. Кобак, С.Е. Федоров // Информатика и системы управления, 2004. - №2. - С. 144-156.

45. Нейдорф, P.A. Модификация алгоритма Алексеева для систем с избирательными свойствами приборов // P.A. Нейдорф, В.Г. Кобак, С.Е. Федоров // Математические методы в технике и технологиях - ММТТ-19: сб. тр. XIX Междунар. науч. конф. - Воронеж: ВГТА, 2006. - Т. 2, секц. 2.

46. Лазарев, A.A. Теория расписаний. Оценки абсолютной погрешности и схема приближённого решения задач теории расписаний / A.A. Лазарев. - М.: МФТИ, 2008. - 221 с.

47. Land, А.Н. An automatic method of solving discrete programming problems / A.H. Land, A.G. Doig // Econometrica, 1960 - №28. - pp. 497-520.

48. Little, J.D.C. An algorithm for the traveling salesman problem / J.D.C. Little, K.G. Murty, D.W. Sweeney, C. Karel // Operations Research, 1963 - №11. -pp. 972-989.

49. Романовский, И.В. Решение дискретных минимаксных задач методом дихотомии / И.В. Романовский, Н.П. Христова // Журнал вычислительной математики и математической физики, 1973. - № 5. - С. 1200-1209.

50. Кобак, В.Г. Методология сопоставительно-критериальной аналитической оценки распределительных задач - и средства ее программно-алгоритмической поддержки: дисс. ... д-ра техн. наук / В.Г. Кобак. -Ростов-на-Дону: Издательский центр ДГТУ, 2008.

51. Титов, Д.В. Методы повышения эффективности алгоритмов решения распределительных минимаксных задач в однородных системах: дисс. ... канд. техн. наук / Д.В. Титов. - Ростов-на-Дону: Издательский центр ДГТУ, 2010.

52. Кобак, В.Г. Анализ работы алгоритма Романовского с использованием разных подходов к формированию верхней и нижней границ / В.Г. Кобак, Д.В. Титов // Математические методы в технике и технологиях -ММТТ-20: сб. тр. XX Междунар. науч. конф., 28-31 мая / ЯГТУ -Ярославль, 2007. - Т.2, секц. 2, 6.

53. Головкин, Б.А. Расчет характеристик и планирование параллельных вычислительных процессов / Б.А. Головкин. - М.: Радио и связь, 1983. -272 с.

54. Кобак, В.Г. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи для однородных приборов / В.Г. Кобак, Д.М. Будиловский // Вестн. Донск. гос. техн. ун-та, 2006. - № 4. - С. 327-334.

55. Woolf, Murray В. Faster Construction Projects with CPM Scheduling / Murray B. Woolf. - New York: McGraw Hill, 2007. - p. 456.

56. Kelley, J. Critical-Path Planning and Scheduling / J. Kelley, M. Walker // Proceedings of the Eastern Joint Computer Conference, 1959. - pp. 160-173.

57. Пашкеев, С.Д. Машинные методы оптимизации в технике связи / С.Д. Пашкеев, Р.И. Минязов, В.Д. Могилевский. - М.: Связь, 1976. - 272 с.

58. Будиловский, Д.М. Сравнительный анализ списочных алгоритмов решения минимаксной задачи для однородных приборов / Д.М. Будиловский, В.Г. Кобак // Математические методы в технике и технологиях - ММТТ-19: сб. тр. XIX Междунар. науч. конф.: В 10 т. - Воронеж: ВГТА, 2006. - Т. 2, секц. 2.-с. 194-196.

59. Кобак, В.Г. Сравнение приближенных алгоритмов решения однородной минимаксной задачи по точности / В.Г. Кобак, Д.В. Титов, O.A. Золотых // Системный анализ, управление и обработка информации: тр. 1-го Междунар. семинара студентов, аспирантов и учёных / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: ИЦ ДГТУ, 2010. - С. 94-97.

60. Лопатин, A.C. Метод отжига / A.C. Лопатин // Стохастическая оптимизация в информатике, 2005. - № 1. - С. 133-149.

61. Kirkpatrick, S. Optimization by Simulated Annealing / S. Kirkpatrick, Jr. C.D. Gelatt, M.P. Vecehi // Science, 1983. - vol. 220. - pp. 671-680.

62. Suman, B. A survey of simulated annealing as a tool for single and multiobjective optimization / B. Suman, P. Kumar // Journal of the Operational Research Society, 2006. - №57. - pp. 1143-1160.

63. Тихомиров, A.C. О быстрых вариантах алгоритма отжига (simulated annealing) / A.C. Тихомиров // Стохастическая оптимизация в информатике, 2009. - № 5. - С. 65-90.

64. Жикулин, А.А. Возможности и перспективы применения методов отжига в задачах поисковой оптимизации / А.А. Жикулин // Системный анализ, управление и обработка информации: тр. 1-го Междунар. семинара студентов, аспирантов и учёных / под общ. ред. Р.А. Нейдорфа. - Ростов н/Д: Изд. центр Донск. гос. техн. ун-та, 2010. - С. 223-228.

65. Хамухин, А.А. Применение адаптивного бинормального распределения в методе поиска глобального минимума simulated annealing / А.А. Хамухин // Известия Томского политехнического университета, 2006. - № 7. - С. 116-120.

66. Гришин, А.А. Исследование эффективности метода пчелиного роя в задаче глобальной оптимизации. [Электронный ресурс]: А.А. Карпенко, А.А. Гришин // Инженерное образование, электронное научно-техническое издание «Наука и образование», 2010. Режим доступа: http://technomag.edu.ru/doc/154050.html.

67. Карпенко, А.П. Обзор методов роя частиц для задачи глобальной оптимизации. [Электронный ресурс]: А.П. Карпенко, Е.Ю. Селиверстов // Инженерное образование, электронное научно-техническое издание «Наука и образование», 2009. Режим доступа: http://technomag.edu.ru/doc/l 16072.html.

68. Маляренко, И. Планирование и оптимизация: от Вергилия до ... APS системы. [Электронный ресурс]: Корпоративные системы PC Week / Re

№27, 2006. Режим доступа:

http://www.masters.donntu.edu.ua/2009/fem/bazarova/library/tez2.htm.

69. Аитух, А.Э. Исследование канонического метода роя частиц (PSO) для топологий типа «клика» и «кластер». [Электронный ресурс]: А.Э. Антух // Инженерное образование, электронное научно-техническое издание «Наука и образование», 2009. Режим доступа: http://technomag.edu.ru/doc/127975.html.

70. Скляренко, А.А. Методы решения задачи попиксельной S-аппроксимации мультитоновых изображений и их оптимизация: дисс. ... канд. техн. наук / А.А. Скляренко. - Ростов-на-Дону: Издательский центр ДГТУ, 2012.

71. Holland, J. Н. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. — USA: University of Michigan, 1975. - p. 211.

72. Goldberg, D. E. Genetic Algorithms in Search, Optimization, and Machine Learning. - USA: Addison-Wesley Publishing Company, Inc., 1989. - p. 432.

73. Исаев, С. Популярно о генетических алгоритмах. [Электронный ресурс]: С. Исаев. Режим доступа: http://algolist.manual.ru/ai/ga/gal.php.

74. Емельянов, В.В. Теория и практика эволюционного моделирования / В.В. Емельянов, В.В. Курейчик, В.М. Курейчик. - М.: ФИЗМАТЛИТ, 2003. -432 с.

75. Батищев, Д.И. Применение генетических алгоритмов к решению задач дискретной оптимизации. Учебно-методический материал по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике» / Д.И. Батищев, Е.А. Неймарк, Н.В. Старостин. - Нижний Новгород, 2007. - 85 с.

76. Панченко, Т.В. Генетические алгоритмы: учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. - Астрахань: Издательский дом «Астраханский университет», 2007. - 87 с.

77. Langdon, P. Foundations of Genetic Programming / P. Langdon, R. Poli. -Berlin: Springer Verlag, 2002. - 260 p.

78. Будиловский, Д.М. Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий: дисс. ... канд. техн. наук / Д.М. Будиловский. - Ростов-на-Дону: Издательский центр ДГТУ, 2007.

79. Титов, Д.В. Анализ работы списочных и генетических алгоритмов в однородных системах обработки информации / Д.В. Титов, В.Г. Кобак // Математические методы в технике и технологиях - ММТТ-22: сб. тр. XXII Междунар. науч. конф., 25-30 мая . - Псков: ППИ, 2009. - Т. 10, секц. 11.-С. 124-126.

80. Kobayashi, S. An Efficient Genetic Algorithm for Job Shop Scheduling Problem / S. Kobayashi, I. Ono, M. Yamamura // Proc. of 6th Int. Conf. on GA, Morgan Kaufmann Publ., San Francisco, 1995.

81. Будиловский, Д.М. Генетический подход к решению минимаксной задачи в однородных системах обработки информации/ Д.М. Будиловский, В.Г. Кобак // Математические методы в технике и технологиях - ММТТ-19: сб. тр. XIX Междунар. науч. конф.: В 10 т.Воронеж: ВГТА, 2006. - Т.2, секц.2. - С. 196-198.

82. Будиловский, Д.М. Исследование принципа "элитизма" генетического алгоритма решения минимаксной задачи в однородных системах обработки информации / Д.М. Будиловский, P.A. Нейдорф, В.Г. Кобак // Научное знание: новые реалии: сборник научно-исследовательских работ. — М: «Учебная литература», 2006. - Вып.2.

83. Будиловский, Д.М. Влияние структуры и параметров генетического алгоритма на эффективность решения минимаксных задач / Д.М. Будиловский // Системный анализ, управление и обработка информации: 1-й межвуз. сб. науч. ст. / ДГТУ; ТТИ ЮФУ. - Ростов н/Д, 2007. - С. 135140.

84. Жикулин, А.А. Двукритериальная стратегия элитизма эволюционно-генетического алгоритма многоэкстремальной оптимизации / Р.А. Нейдорф, А.А. Жикулин // Математические методы в технике и технологиях - ММТТ-26: сб. трудов XXVI Междунар. науч. конф.: в 10 т. Т. 9. Секция 11/ под общ. ред. А.А. Большакова. - Нижний Новгород: Нижегород. гос. техн. ун-т, 2013. - С. 290-294.

85. Krone, M. Heuristic programming applied to scheduling models // Proc. 5th Annual Princeton Conf. Inform. Sci. and Syst., 1971. - p. 193-196.

86. Кобак, В.Г. Сравнительный анализ алгоритмов решения задачи планирования в однородных вычислительных системах / В.Г. Кобак, М.С. Иванов // Математические методы в технике и технологиях — ММТТ-20: сб. тр. XX Междунар. науч. конф., 28-31 мая. - Ярославль: ЯГТУ, 2007. - С. 56-57.

87. Нейдорф, Р.А. Селективно-минимизирующий метод повышения эффективности работы приближенных распределительных алгоритмов / Р.А. Нейдорф, А.В. Филиппов, З.Х. Ягубов // Системный анализ, управление и обработка информации: тр. 1-го Междунар. семинара студентов, аспирантов и ученых / под общ. ред. Р.А. Нейдорфа. - Ростов н/Д: Издательский центр ДГТУ, 2010. - С. 106-115.

88. Нейдорф, Р.А. Эквивалентно-селективный метод повышения эффективности работы распределительных алгоритмов / Р.А. Нейдорф, А.В. Филиппов, З.Х. Ягубов // Инновация, экология и ресурсосберегающие технологии на предприятиях машиностроения, авиастроения, транспорта и сельского хозяйства: тр. IX Междунар. науч.-техн. конф. - Ростов н/Д: Издательский центр ДГТУ, 2010. - С. 366-373.

89. Кобак, В.Г. Повышение эффективности алгоритма Крона за счет модификации начального распределения заданий / В.Г. Кобак, Д.В. Титов, О.А. Золотых // Современные проблемы информатизации в моделировании и социальных технологиях: Сб. трудов. Вып. 16. -Воронеж: «Научная книга», 2011. - С. 246-250.

90. Нейдорф, P.A. Перестановочный алгоритм биэкстремального решения однородной распределительной задачи / P.A. Нейдорф, A.B. Филиппов, З.Х. Ягубов // Вестн. Донск. гос. техн. ун-та, 2011. - Т. 11. - № 5. - С. 655-666.

91. Жикулин, A.A. Исследование селективно-перестановочного метода решения однородной распределительной задачи с использованием мультиперестановок / P.A. Нейдорф, A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: Изд. центр Донск. гос. техн. ун-та, 2012. - С. 57-68.

92. Жикулин, A.A. Исследование вариантов модификации приближенных алгоритмов решения однородных распределительных задач, повышающих их эффективность / P.A. Нейдорф, A.A. Жикулин // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): Труды X Междунар. науч.-техн. форума. - Ростов н/Д: ИЦ ДГТУ, 2012. -С. 370-375.

93. Жикулин, A.A. Метод повышения эффективности работы селективно-перестановочного алгоритма решения распределительных задач на основе эквивалентных перестановок / A.A. Жикулин // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): Труды X Междунар. науч.-техн. форума. - Ростов н/Д: ИЦ ДГТУ, 2012. - С. 376381.

94. Жикулин, A.A. Результаты исследования мультиперестановочного подхода при решении распределительных задач / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях - ММТТ-26: сб. трудов XXVI Междунар. науч. конф.: в 10 т. Т. 9. Секция 11/ под общ. ред. A.A. Большакова. - Нижний Новгород: Нижегород. гос. техн. ун-т, 2013.-С. 332-335.

95. Жикулин, A.A. Эквиперестановочный подход к решению распределительных задач. Возможности и перспективы / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях -

ММТТ-26: сб. трудов XXVI Междунар. науч. конф.: в 10 т. Т. 9. Секция 11 / под общ. ред. A.A. Большакова. - Нижний Новгород: Нижегород. гос. техн. ун-т, 2013. - С. 305-308.

96. Жикулин, A.A. Селективно-перестановочный метод приближенного решения однородной распределительной задачи. Комбинационные перестановки / P.A. Нейдорф, A.A. Жикулин // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». -Таганрог: Изд-во ТТИ ЮФУ, 2013. - № 7(144). - С. 167-172.

97. Кобак, В.Г. Порядок совмещения алгоритма Крона и его модификации в однородных системах обработки информации / В.Г. Кобак, Д.В. Титов, O.A. Золотых // Системный анализ, управление и обработка информации: сб. тр. 2-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. — Ростов н/Д: ИЦ ДГТУ, 2011. - С. 48-51.

98. Кобак, В.Г. Различные подходы для увеличения эффективности алгоритма Крона в однородных системах обработки информации / В.Г. Кобак, А.Ю. Чижов, Д.В. Титов, O.A. Золотых // Известия высших учебных заведений. Электромеханика, 2012. - №5. - С. 74-77.

99. Кобак, В.Г. Анализ использования критериев оптимизации при решении однородной распределительной задачи при четном количестве устройств / В.Г. Кобак, Д.В. Титов, O.A. Золотых // Системный анализ, управление и обработка информации: сб. тр. 2-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: ИЦ ДГТУ, 2011. - С. 46-47.

100. Кобак, В.Г. Исследование алгоритма Крона при различных исходных данных / В.Г. Кобак, Д.В. Титов, O.A. Золотых // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: ИЦ ДГТУ, 2012. -С. 169-174.

101. Кобак, В.Г. Исследование алгоритма Крона и его модификации при различных исходных данных / В.Г. Кобак, Д.В. Титов, O.A. Золотых // Вестн. Донск. гос. техн. ун-та, 2012. - № 8. - С. 62-67.

102. Автоматизированная система экспериментальных исследований однородных распределительных задач теории расписаний «Autoscheduler»: свидетельство о государственной регистрации программы для ЭВМ № 2013616055 / P.A. Нейдорф, A.A. Жикулин. - № 2013616055; заявл. 2013613628; зарег. 26.06.2013.

103. Адлер, Ю.П. Планирование эксперимента при поиске оптимальных условий / Ю.П. Адлер, Е.В. Маркова, Ю.В. Гранковский. - М.: Наука, 1976.-278 с.

104. Ермаков, С.М. Математическая теория оптимального эксперимента / Ермаков С.М., Бродский В.З., Жиглявский A.A. и др. - М.: Наука, 1983. — 392 с.

105. Жикулин, A.A. Исследование ресурсно-временных возможностей алгоритма полного перебора при решении однородных распределительных задач / A.A. Жикулин // Системный анализ, управление и обработка информации: Тр. 4-го Междунар. семинара (п. Дивноморское, 29 сентября - 3 октября 2013 г.) / Под общ. ред. P.A. Нейдорфа. - Ростов н/Д: ДГТУ, 2013. - С. 17-22.

106. Кобзарь, А.И. Прикладная математическая статистика. Для инженеров и научных работников / А.И. Кобзарь. - М.: ФИЗМАТЛИТ, 2006. - 816 с.

107. Бочаров, П.П. Теория вероятностей. Математическая статистика / П.П. Бочаров, A.B. Печинкин. - М.: ФИЗМАТЛИТ, 2005. - 296 с.

108. Жикулин, A.A. Повышение ресурсной эффективности алгоритма точного решения однородной распределительной задачи / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях - ММТТ-27: сб. трудов XXVII Междунар. науч. конф.: в 12 т. Т. 3. Секции 6, 7, 8 / под общ. ред. A.A. Большакова. — Тамбов: Тамбовск. гос. техн. ун-т, 2014.-С. 42-46.

109. Модификация алгоритма Романовского методом глубокого отката и максимальной загрузки для приближенного решения распределительных задач «Deep Rollback and Full Loading» (DR&FL): свидетельство о

государственной регистрации программы для ЭВМ № 2013615965 / P.A. Нейдорф, A.A. Жикулин. - № 2013615965; заявл. 2013613627; зарег. 25.06.2013.

110. Жикулин, A.A. Модифицированный алгоритм Романовского быстрого нахождения приближенного решения однородной распределительной задачи / P.A. Нейдорф, A.A. Жикулин // Вестн. Донск. гос. техн. ун-та. -2012.-№6(67).-С. 87-92.

111. Жикулин, A.A. Алгоритм быстрого поиска решения распределительной задачи высокой степени приближения на основе алгоритма Романовского / A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: Изд. центр Донск. гос. техн. ун-та, 2012. - С. 6875.

112. Жикулин, A.A. Структурная модификация алгоритма Романовского с улучшением ресурсно-временных характеристик решения однородных распределительных задач / A.A. Жикулин // Системный анализ, управление и обработка информации: Тр. 4-го Междунар. семинара (п. Дивноморское, 29 сентября - 3 октября 2013 г.) / Под общ. ред. P.A. Нейдорфа. - Ростов н/Д: ДГТУ, 2013. - С. 187-192.

113. Будиловский, Д.М. Повышение точности решения минимаксной задачи теории расписания с кратностью / Д.М. Будиловский // Математические методы в технике и технологиях - ММТТ-20: сб. тр. XX Междунар. науч. конф.: В 10 т. - Ярославль: ЯГТУ, 2007. - Т.2, секц. 2. - С. 54-56.

114. Нейдорф, P.A. Практическое использование метода псевдократной загрузки / P.A. Нейдорф, Д.Г. Красный, В.Г. Кобак // Математические методы в технике и технологиях - ММТТ-21: сб. тр. XXI Междунар. науч. конф. - Саратов: СГТУ, 2008. — Т.5.

115. Жикулин, A.A. Комбинированное решение однородных распределительных задач на основе модифицированного алгоритма Романовского и селективно-перестановочного алгоритма / P.A. Нейдорф,

A.A. Жикулин // Вестн. Донск. гос. техн. ун-та. - 2012. - № 5(66). - С. 5054.

116. Жикулин, A.A. Селективно-перестановочная модификация алгоритма Романовского и перспективы ее использования / P.A. Нейдорф, A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. -Ростов н/Д: Изд. центр Донск. гос. техн. ун-та, 2012. - С. 115-120.

117. Гмурман, В.Е. Теория вероятностей и математическая статистика: Учеб. пособие для вузов / В.Е. Гмурман - М.: Высш. шк., 2003. - 479 с.

118. Жикулин, A.A. Исследование свойств многоэкстремальности решения распределительных задач / P.A. Нейдорф, A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 2-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: Изд. центр Донск. гос. техн. ун-та, 2011. - С. 377-380.

119. Жикулин, A.A. Программное средство для исследования свойств многоэкстремальности решения однородных распределительных задач / A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 2-го Междунар. науч. семинара / под общ. ред. P.A. Нейдорфа. - Ростов н/Д: Изд. центр Донск. гос. техн. ун-та, 2011. - С. 245-248.

120. Автоматизированное средство решения распределительных задач селективно-перестановочным методом «Selective-Permutational Scheduler»: свидетельство о государственной регистрации программы для ЭВМ № 2013616088 / P.A. Нейдорф, A.A. Жикулин. - № 2013616088; заявл. 2013613626; зарег. 26.06.2013.

121. Автоматизированное средство решения распределительных задач эволюционно-генетическим алгоритмом с использованием структурно-дифференцируемого элитизма «Structure-Differentiable Elitism»: свидетельство о государственной регистрации программы для ЭВМ №

2013616060 / Р.А. Нейдорф, А.А. Жикулин. - № 2013616060; заявл. 2013613632; зарег. 26.06.2013.

ПРИЛОЖЕНИЕ А Свидетельства о государственной регистрации

программ для ЭВМ

(обязательное)

7^/УЗ

«

т

й й

Й

й й й й

ш -й Й й й Й Й й Й й

ЙЙЙЙЙЙ

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2013616055

Автоматизированная система экспериментальных исследовании од породных распределительных задач теории расписаний «Аи^сЬесМег»

Правообладатель: федеральное государственное бюджетное образовательное учреждение высшего профессионал ьного образования «Донской государственный технический университет» (ДГТУ) (Я11) ..

Авторы: Нейдорф Рудольф Анатольевич (Я11), Жикулин Артем Александрович (1Ш)

Заявка № 2013613628 / Дата поступления 30 апреля 2013 Г. Дата государственной регистрации в Реестре программ для ЭВМ 26 ШОНЯ 2013 г.

Руководитель Федеральной службы интеллектуальной собственности

Б. П. Симонов

й

Й

; Й Й й Йй й Й й Й Й Й Й й й ЙЙ й ЙЙ йЙ й й йй Й Й Й й Й &Ы

Й

Й

Й Й Й Й

Й

ЗРТСШЯЮЕАШ ФВДШРАЩШШ

ш^шщшшм ш\

№

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2013615965

Модификация алгоритма Романовского методом глубокого

отката и максимальной загрузки для приближенного решения распределительных задач «Deep Rollback and Full

Loading» (DR&FL)

Правообладатель: федеральное государственное бюджетное образовательное учреждение высшего профессионального образованы <<Донской государственный технический университет» (ДГТУ) (Ш)

Авторы: Нейдорф Рудольф Анатольевич (1Ш), Жикулин Артем Александрович (ЯЦ),

Заявках» 2013613627

: , Дата поступления 30 апреля 2013 Г. '" ¿'.'.-Л1"*/^?— Дата государственной регистрации

' в Реестре программ для ЭВМ 25 НЮНЯ 2013 г.

- / . Руководитель Федеральной службы ■'■ - ' ' по интеллектуальной собственности

' Б.П. Симонов

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2013616088

Автоматизированное средство решения распределительных: задач селективно-перестановочным методом «Бексиуе-Регпнйа^опа! 8с11е(1и1ег» -

правообладатель: федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Донской государственный технический университет» (ДГТУ) (ЯЦ)

Авторы: Нейдорф Рудольф Анатольевич (Ли), Жикулин Артем Александрович (Ш!)

Заявка № 2013613626

Дата поступления 30 апреля 2013 Г.

Дата государственной регистрации

в Реестре программ для ЭВМ 26 ИЮНЯ 2013 г.

■ - ' Руководитель Федеральной службы по интеллектуальной собственности

': Б. П. Симонов

шшшшшшшшшшшш шшшшшш Ш ШШ ШШШШ ШШШШ Ш <

ftmynetfo * *-о У. /3

ш щщшшш

аааааа 'а ш

СВИДЕТЕЛЬСТВО

о государственной регистрации программы для ЭВМ

№ 2013616060

Автоматизированное средство решения распределительных

задач эволгоционио-генетическим алгоритмом с использованием структурно-дифференцируемого элитизма «Structure-Differentiable Elitism»

Правообладатель: федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Донской государственный технический университет» (ДГТУ) (ЯЦ)

Авторы: Нейдорф Рудольф Анатольевич (1Ш), Жикулип Артем Александрович (ЯЦ)

Заявках» 2013613632 • Датапоступления 30 апреля 2013 Г. Дата государственной регистрации 'Ш'Ш Реестре программ для ЭВМ 26 НЮНЯ 2013 г.

Руководитель Федеральной службы : по интеллектуальной собственности

Б П. Симонов

Й

а ш а а а а а а а а а а а а

а а а а а а а а а а а а а а а а а а а

b$g>aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa<

ПРИЛОЖЕНИЕ Б Программное средство «Аи1о8сЬес1и1ег» имитационного моделирования и решения однородной распределительной задачи

(информативное)

Б.1 Постановка задачи

Как отмечено во второй главе, исследование ресурсно-точностных свойств и возможностей новых и модифицированных методов и алгоритмов решения ОРЗ, а также взаимосвязи внутренних зависимостей самой задачи требует проведения вычислительных экспериментов на больших и статистически значимых выборках РЗ. В связи с этим, возникает необходимость в создании удобного и производительного программного средства, позволяющего автоматизировать данный процесс. Для этого программное средство должно выполнять следующие основные функции:

1. ввод условий исследуемых ОРЗ следующими способами: случайным генерированием, вручную, загрузкой из файла;

2. решение массива РЗ в автоматическом режиме с помощью выбранных пользователем из библиотеки алгоритмов;

3. решение ОРЗ разработанными и основными существующими алгоритмами: полного перебора, критического пути, алгоритмом Романовского (АР), комбинационно-модифицированным АР (КМАР), структурно-модифицированным АР (СМАР), селективно-перестановочным алгоритмом (СПА), эволюционно-генетическим алгоритмом (ЭГА);

4. протоколирование хода работы алгоритмов во время решения РЗ в текстовый файл;

5. статистическая обработка результатов вычислительных экспериментов;

6. сохранение параметров и результатов вычислительных экспериментов в файл в унифицированном формате;

7. возможность остановки и дальнейшего продолжения выполнения ресурсоемких вычислительных экспериментов с сохранением промежуточных результатов;

8. параллельное выполнение нескольких вычислительных экспериментов. Исходя из перечисленных функциональных требований к программному средству, разработана его концептуальная схема функционирования. В основу данной схемы положена предложенная в работе [78] схема. Описанию разработанной схемы посвящен следующий пункт.

Б.2 Концептуальная схема функционирования программного средства

Программное средство можно условно разделить на три функциональных блока:

1. блок выполнения вычислительного эксперимента;

2. блок статистической обработки результатов эксперимента;

3. блок взаимодействия с пользователем.

Блок выполнения вычислительного эксперимента непосредственно осуществляет проведение опыта, т.е. выполняет приведенные в предыдущем пункте функции с номерами 2 и 3.

Блок статистической обработки результатов эксперимента осуществляет расчет обобщенных по опыту статистических данных, позволяющих оценить ресурсно-точностные свойства исследуемых в опыте алгоритмов.

Блок взаимодействия с пользователем отвечает за ввод условий и вывод результатов опыта, а также управление процессом проведения массива вычислительных опытов.

Общий алгоритм работы программного средства представлен на рисунке Б.1 в виде схемы и состоит из следующих основных шагов.

1. Ввод массива РЗ: случайным генерированием, вручную или загрузкой из файла.

2. Выбор исследуемых алгоритмов решения РЗ и их параметров работы.

3. Решение введенных РЗ выбранными алгоритмами в последовательном порядке.

4. Вывод в режиме реального времени результатов решения РЗ на экран.

5. Сохранение условий и результатов вычислительного эксперимента в файл в унифицированном формате XML.

6. Если необходимо, то выполнение статистической обработки результатов вычислительного эксперимента для оценки ресурсно-точностной эффективности исследуемых алгоритмов.

На основе разработанной в данном пункте концептуальной схемы функционирования программного средства разработана его объектно-ориентированная модель. Описание данной модели приводится ниже.

Б.З Объектно-ориентированная модель программного средства

Б.3.1 Главный класс объектно-ориентированной модели программного

средства

Главным классом объектно-ориентированной модели программного средства является класс MainForm. Данный класс выполняет следующие основные функции:

1. осуществляет взаимодействие между функциональными частями программного средства;

2. организует работу пользователя с несколькими вычислительными опытами в одном сеансе работы программного средства;

3. осуществляет управление процессом проведения массива вычислительных опытов.

Класс MainForm также является основным классом блока взаимодействия с пользователем (объектно-ориентированная модель этого блока описана в следующих пунктах) и реализует основную функцию данного блока, а именно: реализует взаимодействие пользователя с программным средством посредством оконного интерфейса.

Блок выполнения вычислительного эксперимента

Критерий оптимизации

Блок статистической обработки результатов эксперимента

( Опыт

V_________

Расчет

Расписания ' *

Статистическая обработка

Статистика по опыту

Генерация размеров заданий

Загрузка из файла

Сохранение в файл

Просмотр

Блок взаимодействия с пользователем Рисунок Б.1 - Общая схема работы программного средства

Основные поля и методы класса MainForm описаны в таблицах Б.1 и Б.2.

Таблица Б.1 - Основные поля класса MainForm

Название Описание

FExperiments Список вычислительных опытов, с которыми работает пользователь с момента запуска программы

executingExperiments Список параллельно выполняющихся вычислительных опытов

_CurExperiment Вычислительный опыт, с которым в данный момент работает пользователь

_MaxExecExperimentsCount Максимальное количество параллельно выполняющихся опытов

_ExperimentsQueue Очередь запущенных на выполнение вычислительных опытов

FExperimentsForm Форма отображения списка вычислительных опытов, с которыми работает пользователь с момента запуска программы

FContentExpForm Форма отображения данных вычислительного опыта, выбранного пользователем из списка на форме РЕхрепте^эРогт

Таблица Б.2 - Основные методы класса MainForm

Название Назначение

void createExperimentMenuItem_Click (object sender, EventArgs e); void copyExperimentMenuItem_Click (object sender, EventArgs e); void deleteExperimentMenuItem_Click (object sender, EventArgs e) Методы, осуществляющие создание, копирование и удаление вычислительного опыта

void ExecuteExperiment(Experiment AExperiment) Запускает вычислительный опыт на выполнение в отдельном фоновом потоке

void AddExperimentsQueue(Experiment AExperiment) Добавляет вычислительный опыт в очередь на выполнение

void ExperimentProgressChanged (Object sender, ProgressChangedEventArgs e); void ExperimentCompleted(Object sender, RunWorkerCompletedEventArgs e) Обновляют информацию о статусе выполнения вычислительного опыта

void stopExperimentMenuItem_Click (object sender, EventArgs e) Останавливает выполнение вычислительного опыта

Как видно из приведенной в таблицах Б.1 и Б.2 структуры класса MainForm, в состав данного класса входят поля, содержащие информацию о созданных пользователем или загруженных им из файла вычислительных опытах, а также методы, реализующие функции по созданию, копированию и удалению данных опытов.

Данный класс также содержит методы, реализующие параллельное или последовательное (в зависимости от заданных пользователем настроек) выполнение вычислительных опытов, возможность остановки их выполнения и дальнейшего продолжения с сохранением промежуточных результатов.

Описанию разработанных объектно-ориентированных моделей функциональных блоков (частей) программного средства посвящены следующие пункты.

Б.3.2 Объектно-ориентированная модель блока выполнения вычислительного эксперимента

Общая объектно-ориентированная модель блока выполнения вычислительного эксперимента представлена на рисунке Б.2.

Как видно из рисунка Б.2, основным классом блока выполнения вычислительного эксперимента является класс Experiment. Данный класс содержит общую информацию о вычислительном опыте (название опыта, дата и время его создания и др.), параметры проведения опыта (протоколировать ли выполнение опыта, ограничивать ли по времени решение алгоритмом РЗ и др.) и условия исследуемых РЗ. Функционально класс Experiment отвечает за управление процессом проведения всего вычислительного опыта. Основные поля и методы класса Experiment описаны в таблицах Б.З и Б.4.

Класс Experiment состоит из объектов класса Test. Данный класс представляет собой часть вычислительного опыта (подопыт), связанную с исследованием работы отдельного (а не всего массива исследуемых в опыте алгоритмов, как в классе Experiment) алгоритма при решении РЗ с заданными в опыте параметрами. Класс Test содержит информацию о параметрах

исследуемого алгоритма и отвечает за последовательное решение массива РЗ данным алгоритмом. Основные методы класса Test имеют аналогичное методам класса Experiment (см. табл. Б.З) функциональное назначение, но только применительно к отдельной его части (подопыту), а не ко всему вычислительному опыту.

Рисунок Б.2 - Объектно-ориентированная модель блока выполнения

вычислительного эксперимента

Класс Test, в свою очередь, состоит из объектов класса Problem. Данный класс является наименьшей единицей вычислительного опыта и отвечает за решение отдельной РЗ (а не всего массива исследуемых в опыте РЗ, как в классе Test) конкретным алгоритмом. Также он содержит информацию о результатах работы алгоритма при решении заданной РЗ: полученное алгоритмом распределение заданий по исполнителям и время его работы. Результат решения РЗ описывается классом Decision.

Классы ExhaustiveAlgorithm, CriticalPathMethod, GeneticAlgorithm, RomanovskyAlgorithm, RomanovskyCombModAlg, RomanovskyStructModAlg, SelectPermutationMethod представляют собой классы, реализующие отдельные

алгоритмы решения ОРЗ: полного перебора, критического пути, эволюционно-генетический алгоритм, классический АР, комбинационно-модифицированный АР, структурно-модифицированный АР, селективно-перестановочный алгоритм соответственно.

Таблица Б.З - Основные поля класса Experiment

Название Описание

Name Название опыта

CreateDateTime Дата и время создания опыта

State Статус выполнения опыта

FileName Имя файла опыта

LogFile Файл, в который записывается протокол выполнения опыта

TimeLimitTask Ограничение на время решения алгоритмом отдельной РЗ

CountListsTasks Количество исследуемых в опыте РЗ

CountExecutors, CountTasks MinTimeTask, MaxTimeTask, ListsTasks Условия РЗ (количество исполнителей, количество заданий, диапазон размеров заданий (нижняя и верхняя границы), матрица размеров заданий)

Таблица Б.4 - Основные методы класса Experiment

Название Назначение

void Execute() Осуществляет . последовательное решение РЗ заданными алгоритмами

void Stop() Останавливает выполнение опыта

void NextProblem() Останавливает решение текущей РЗ и осуществляет решение следующей по порядку РЗ

Experiment CopyQ Формирует копию вычислительного опыта

Для алгоритма критического пути, эволюционного-генетического и селективно-перестановочного алгоритмов можно задавать параметры их работы. Данные параметры перечислены в таблице Б.5.

Для взаимодействия реализующих алгоритмы решения ОРЗ классов с классом Test используется абстрактный класс OptimizationAlgorithm. Класс OptimizationAlgorithm фактически представляет собой интерфейс, который должен быть реализован любым классом, представляющим собой отдельный

метод решения ОРЗ, для того, чтобы класс Test мог его использовать для решения РЗ. Это позволяет не только структурно отделить условие РЗ от метода ее решения, но и легко расширять библиотеку алгоритмов программного средства. Основные методы класса OptimizationAlgorithm описаны в таблице Б.6.

Таблица Б.5 - Параметры работы алгоритмов решения РЗ

Название Описание

Алгоритм критического пути

SortType Порядок сортировки распределяемых заданий перед началом работы алгоритма. Варианты: по возрастанию или убыванию их размеров, без сортировки.

Эволюционно-генетический алгоритм

RunsCount Количество параллельных запусков алгоритма

IndividualsCount Количество особей в поколении

BestlndividualsCount Количество элитных особей

LimitPopulationsCount Условие останова работы алгоритма по количеству поколений, в течение которых лучшая особь не изменяется

CrossoverProbability Вероятность выполнения оператора кроссинговера

MutlndividProbability Вероятность выполнения оператора мутации особи

MutBitGeneProbability Вероятность мутации для каждого бита гена

InversionProbability Вероятность выполнения оператора инверсии

Селективно-перестановочный алгоритм

Criterion Критерий оптимизации: минимаксный критерий или критерий равномерности загрузки

InitEstimateMethod Алгоритм оптимизации, с помощью которого рассчитывается начальное приближение: алгоритм критического пути или структурно-модифицированный АР

MaxDimMultiperms Максимальный размер анализируемых алгоритмом мультиперестановок

UseEquivConversion Определяет, использовать ли во время работы алгоритма эквивалентные перестановки

Классы DistributionMatrix, AugmentMatrix и CombinationMatrix являются

вспомогательными классами для класса реализующего селективно-перестановочный алгоритм SelectPermutationMethod. Данные классы представляют собой программные реализации распределительной матрицы (РМ),

расширенной РМ и комбинационной матрицы (см. гл. 4) соответственно, а также включают методы по работе с ними.

Таблица Б.6 - Основные методы класса OptimizationAlgorithm

Название Назначение

Decision Evaluate(ProblemParameters problemParameters) Осуществляет распределение заданий по исполнителям в соответствии с реализованным алгоритмом решения ОРЗ

void StopQ Останавливает выполнение реализованного алгоритма решения ОРЗ

OptimizationAlgorithm CloneQ Формирует копию экземпляра реализованного алгоритма решения ОРЗ

Б.3.3 Объектно-ориентированная модель блока статистической обработки результатов эксперимента

Блок статистической обработки результатов эксперимента состоит из следующего набора классов:

1. ЯерЕзйп^ез;

2. ЯерТ1тез;

3. МаШ81а1Б.

Класс ИерЕзйп^еэ отвечает за формирование статистических данных по результатам вычислительного опыта, которые позволяют оценить точность, а класс Яер^теБ - ресурсоемкость работы исследуемых в опыте алгоритмов.

Методы класса КерЕзйгг^ез формируют таблицу со статистическими данными, в которой для каждого исследуемого в опыте алгоритма приводится оценка по минимаксному критерию результата решения данным алгоритмом каждой заданной в опыте РЗ, а также рассчитанные отклонения (в условных величинах и в процентах) этой оценки от оценки гарантировано оптимального решения (ГОР) и от оценки его теоретически оптимального варианта (ТОР). Кроме того, в таблице для каждой РЗ указывается оценка ее ТОР и минимально хвостовая (МХО) оценка.

Также для каждого исследуемого в опыте алгоритма методы класса ИерЕБЙпШез рассчитывают и выводят в статистическую таблицу максимальное, среднее и суммарное по опыту отклонения (в условных величинах и в процентах) полученных им решений от ГОР и от ТОР. Кроме того, рассчитывается количество полученных исследуемым алгоритмом ГОР, количество решений, оптимальность которых доказана с помощью оценок ТОР и МХО, количество ФАР (решений, для которых не доказано, являются ли они оптимальными) и НОР (доказано неоптимальных решений).

Методы класса ЯерТтез формируют статистическую таблицу, в которой для каждого исследуемого в опыте алгоритма приводится оценка времени решения данным алгоритмом каждой заданной в опыте РЗ, а также рассчитывают максимальное, минимальное и среднее по опыту значение этой оценки и ее среднеквадратичное отклонение.

Кроме того, методы данного класса осуществляют анализ совокупности временных оценок на неоднородность по критерию Стьюдента. Если неоднородность выявлена, то исходная совокупность разделяется на три совокупности: основную совокупность оценок и совокупности минимальных и максимальных оценок. Для каждой из этих выборок рассчитывается среднее значение временной оценки и ее среднеквадратичное отклонение, которые также выводятся в статистическую таблицу временных ресурсов исследуемых в опыте алгоритмов.

Класс МаШ81а1з содержит набор методов по расчету стандартных статистических величин (таких как среднее выборочное, дисперсия, среднеквадратичное отклонение и др.), а также метод, реализующий анализ выборки на наличие в ней резко отклоняющих значений от ее средней величины по критерию Стьюдента.

Б.3.4 Объектно-ориентированная модель блока взаимодействия с

пользователем

Общая объектно-ориентированная модель блока взаимодействия с пользователем представлена на рисунке Б.З.

Как отмечено в пункте Б.3.1, главным классом блока взаимодействия с пользователем является класс MainForm, который непосредственно организует взаимодействие всех остальных классов и реализует интерфейс главного окна программного средства. Все классы можно функционально разделить на три группы (на рисунке Б.З выделены прямоугольниками).

1. В состав первой группы входят классы, отвечающие за ввод параметров вычислительных опытов и вывод результатов их реализации.

2. Вторая группа классов отвечает за ввод параметров работы исследуемых в опыте алгоритмов.

3. Третья группа классов реализует функции чтения (класс ExperimentXmlReader) и сохранения (класс ExperimentXmlWriter) параметров вычислительного опыта и результатов его реализации в файл в унифицированном формате XML.

Рисунок Б.З - Объектно-ориентированная модель блока взаимодействия с

пользователем

Класс Ехрептеп£[л81Рогт отвечает за отображение списка созданных пользователем или загруженных им из файла вычислительных опытов на отдельной форме (панели) программного средства.

Класс Ехрептег^Рогт отвечает за ввод условий исследуемых в опыте РЗ, а также формирование списка исследуемых в нем алгоритмов. Кроме того, данный класс реализует вывод на экран полученных исследуемыми в опыте алгоритмами расписаний, а также отображение статистических таблиц по результатам реализованного опыта.

Основные методы класса ЕхрептеШРогт приведены в таблице Б.7.

Таблица Б.7 - Основные методы класса ExperimentForm

Название Назначение

void createListsTasksButton_Click (object sender, Event Args e) Устанавливает введенные пользователем на форме условия исследуемых в опыте РЗ, а также при необходимости (если пользователем выбрана соответствующая опция) генерирует случайным образом размеры распределяемых заданий в заданном диапазоне

void addTestButton_Click(object sender, EventArgs e); void deleteTestButton_Click (object sender, EventArgs e) Реализуют добавление и удаление алгоритмов решения РЗ из списка исследуемых в опыте алгоритмов

void UpdDecisionDGView (DataGridView ADGView, Decision decision) Отображает на экране полученное алгоритмом расписание для заданной пользователем РЗ

void UpdReportDGView() Отображает на экране заданную пользователем статистическую таблицу по результатам опыта

Класс Ехрептеп1ЕхесРогт представляет собой форму, которая позволяет пользователю выбрать (из общего списка исследуемых в опыте) алгоритмы решения РЗ, которые будут запущены при проведении данного опыта.

Для ввода дополнительных параметров проведения вычислительного опыта (ограничения времени решения алгоритмом отдельной РЗ и имени файла протокола выполнения опыта) используется класс Ехрептег^БОр^ошРогт.

Класс TestEditForm представляет собой форму добавления выбранного пользователем алгоритма решения РЗ в общий список исследуемых в опыте алгоритмов. Классы CriticalPathParamsForm, GeneticAlgParamsForm и SelPermAlgParamsForm отвечают за настройку параметров работы алгоритма критического пути, эволюционно-генетического алгоритма и селективно-перестановочного алгоритма соответственно.

Описанная выше объектно-ориентированная модель была реализована на языке С# в среде Visual Studio. В результате, было разработано программное средство автоматизированного проведения экспериментальных исследований в области ОРЗ «Autoscheduler», удовлетворяющее приведенным в параграфе Б.1 функциональным требованиям. На разработанное программное средство получено свидетельство о государственной регистрации программы для ЭВМ (Роспатент № 2013616055; заявл. 2013613628; зарег. 26.06.2013) [102].

Классы реализующие разработанные в ходе диссертационного исследования алгоритмы (КМАР, СМАР, СПА, ЭГА с использованием структурно-дифференцируемого элитизма) были реализованы в виде отдельных универсальных программных модулей, которые позволяют использовать их для решения РЗ сторонними программами из различных сфер человеческой деятельности, в которых возникает необходимость планирования выполняемых работ. На большую часть реализованных программных модулей получены свидетельства о государственной регистрации программы для ЭВМ:

1. «Модификация алгоритма Романовского методом глубокого отката и максимальной загрузки для приближенного решения распределительных задач «Deep Rollback and Full Loading» (DR&FL)» (свидетельство № 2013615965) [109];

2. «Автоматизированное средство решения распределительных задач селективно-перестановочным методом «Selectrive-Permutational Scheduler» (свидетельство № 2013616088) [120];

3. «Автоматизированное средство решения распределительных задач эволюционно-генетическим алгоритмом с использованием структурно-

дифференцируемого элитизма «Structure-Differentiable Elitism»

(свидетельство № 2013616060) [121].

Описание интерфейса программного средства «Autoscheduler» приведено

ниже.

Б.4 Описание интерфейса программного средства «Autoscheduler»

Б.4.1 Главное окно программы. Главное окно программного средства «Autoscheduler» представлено на рисунке Б.4. Основными элементами главного окна программного средства являются следующие.

1. Панель «Опыты» (левая часть окна). Отображает список вычислительных опытов, с которыми работает пользователь в данном сеансе работы программного средства. Предоставляет возможность редактирования набора опытов и управления процессом их проведения.

2. Панель «Вычислительный опыт» (основная часть окна). Отображает информацию об условиях и результатах проведения выбранного опыта: параметры РЗ, исследуемые алгоритмы и параметры их работы, полученные алгоритмами расписания и оценки времени их нахождения. Также предоставляет возможность редактирования параметров вычислительного опыта и статистической обработки результатов его реализации.

3. Главное меню (верхняя часть окна). Осуществляет доступ к основным функциям программы по работе со списком вычислительных опытов, чтению/сохранению вычислительных опытов из/в файл, настройке параметров работы программного средства.

4. Панель инструментов (верхняя часть окна, под главным меню). Предоставляет пользователю быстрый доступ к часто используемым функциям программного средства.

5. Панель статуса отображает состояние выполнения выбранного пользователем вычислительного опыта.

Файл Вид Опыт Конфигурация

-.1.'."'.У^ *

Опыты

» X

№ п/п Название Создан Состояние

1 4-41-10040-60 ¡2014-02-01 Выполнен

■2 5-31-100-50-55 2014-02-01 .. Выполнен

| 5-51-100-50-55 2014-02-01 . | Остановлен |

Условия

Результаты | Статист, обработка I

е:

Количество исполнителей Количество заданий Количество векторов заданий Диапазон размеров заданий от [50 Тип векторов заданий

н

Размеры заданий

100

а

а

|55

Установить

чи Ж2] ига Я[41 ВД Ж6] И[7) Н[8] Я[Э1 Р ж

¡ЗЦ 55 55 53 52 50 51 51 51 5о

гЯ * 54 55 54 50 50 52 54 53 5'

гИ 52 53 53 54 53 52 50 53 54 5'