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

Во многих областях инженерных и управленческих задач широкое практическое распространение получают задачи теории расписания [6,34, 41,42]. При упорядочивании и распределении какого-либо ресурса между исполнителями возникает вопрос эффективного планирования. Оптимальность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. В теории распределительных задач (РЗ), которая является одним из широко исследуемых направлений теории расписаний, основное внимание уделяется вопросам, связанным с построением наилучших календарных планов. Календарный план — это расписание последовательно-параллельного исполнения конечного множества требований, обслуживаемых детерминированными системами одного или нескольких устройств.

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

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

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

Цели и основные задачи диссертационной работы.

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

В связи с этим возникла необходимость решения следующих научных и практических задач:

1. разработка и исследование методов повышения точностной эффективности ЭГА при решении РЗ высокой размерности;

2. разработка и обоснование критериев оценки эффективности решения РЗ, информативной для сравнения свойств различных методов и алгоритмов, в особенности, приближённых;

3. разработка и исследование методов повышения возможностей ЭГА при решении однородных РЗ теории расписаний;

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

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

Существенные научные’результаты и степень их новизны.

1. Метод бинарной декомпозиции решения РЗ высокой размерности с чётным количеством устройств обработки заданий, существенно повышающий точность решения приближёнными методами, в частности, методом ЭГА (среднее отклонение решения от минимальной оценки сокращается практически до 0), и уменьшающий время решения для некоторых алгоритмов (в 1,5 раз).

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

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

4. Модифицированная стратегия формирования нового поколения ЭГА путём реализации бинарного турнирного отбора между особями «родителей» и «потомков», которая отсутствует в классических прототипах, и позволяет, по данным статистически представительных исследований (9000 опытов), повысить точность находимого решения в 5−60 раз, в зависимости от размерности и структуры задачи.

5. Структурная модификация АР путём формирования первого.

— приближения-решения—РЗ^быстрыми-приближенными методами^ которая позволяет увеличить быстродействие (до 3−4 кратного, а для двух устройств было получено улучшение в несколько тысяч раз) в сравнении с классическим вариантом алгоритма.

Методы исследования.

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

Для реализации экспериментальных исследований разработано ПО для ЭВМ «Система вычислительных исследований однородных распределительных задач «Optimal», проведено большое количество имитационных экспериментов, результаты которых использованы для получения статистически достоверных оценок результатов исследований. Для реализации ПО применялись концепции объектно-ориентированного программирования.

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

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

Значимыми практическими эффектами применения результатов диссертационных исследований являются:

1. существенное повышение точности решения для РЗ высокой размерности с чётным количеством устройств, в частности, при использовании ЭГА (среднее отклонение решения от минимальной оценки сокращается для ЭГА практически до 0) — ——.

2. повышение точности решения однородных РЗ (до 60-кратного) для ЭГА, в зависимости от размерности и структуры задачи;

3. существенное улучшение быстродействия точных алгоритмов решения однородных РЗ (в основном, в 2−3 раза, а для некоторых частных задач — в несколько тысяч раз).

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

В рамках диссертационной работы разработано ПО «Система вычислительных исследований однородных распределительных задач «Optimal» (ФГУ ФИПС свидетельство № 2 009 616 118 от 06.11.2009), с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов при выполнении лабораторных, курсовых и дипломных работ.

Основное содерэ/сание работы.

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

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

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

Для исследования возможностей совершенствования были выделены наиболее перспективные методы решения однородных РЗ. В качестве приближенных методов был выбран ЭГА, показавший хорошие точностные результаты в предыдущих исследованиях, проводимых в ДГТУ школой проф. Нейдорфа Р. А. в области теории расписаний. В качестве точного метода был выбран АР, основанный на методе ветвей и границ, который по производительности в худшем случаи может совпадать с методом полного перебора, но в общем случае работает намного быстрее.

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

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

Эффективность предложенного метода и построенных на его основе.

12 алгоритмов показана в работе на многочисленных примерах, в которых проводились статистически представительные имитационные эксперименты.

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

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

В связи с поставленной в первой главе задачей была предложена модификация формирования нового поколения для ЭГА. Она заключается в использовании бинарного турнирного отбора, в котором участвуют вновь созданная особь и ее родительская особь. Данная модификации экспериментально сравнивалась с базовым ЭГА, и показала свою эффективность.

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

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

Что касается нижней границы поиска, то Романовский для выделения z-задач использовал полусумму нижней и верхней границ. Было показано, что можно использовать другие способы, которые дают повышение скорости нахождения решения, а именно использовать линейный спуск с шагом h, который равняется 1 или 2. Было показано, что использование линейного спуска с шагом 1 увеличивает эффективность алгоритма.

Рассмотрен ещё один приём, связанный с формированием первого приближения. В качестве приближенного метода для получения первого приближения в АР можно использовать метод критического пути или ЭГА.

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

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

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

5.4. Выводы по пятой главе.

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

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

106.

ЗАКЛЮЧЕНИЕ

.

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

2. Метод бинарной декомпозиции существенно повышает точность решения приближёнными методами РЗ высокой размерности с чётным количеством устройств обработки заданий, а в сочетании с методом ЭГА даёт очень большое улучшение точностной оценки при незначительном проигрыше в оценке ресурсной.

3. Модификация стратегии формирования нового поколения ЭГА путём реализации бинарного турнирного отбора между особями «родителей» и «потомков», который отсутствует в классических прототипах, позволяет существенно повысить точность находимого алгоритмом решения, а в сочетании с методом бинарной декомпозиции эффективнее классического ЭГА.

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

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

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

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