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

На правах рукописи ТИТОВ ДМИТРИЙ ВЯЧЕСЛАВОВИЧ

МЕТОДЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ МИНИМАКСНЫХ ЗАДАЧ В ОДНОРОДНЫХ СИСТЕМАХ

Специальность 05.13.01 - Системный анализ, управление и обработка информации

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата технических наук

1 7

ЛЕК 2009

Ростов-на-Дону 2009 г.

003488933

Работа выполнена на кафедре «Программное обеспечение вычислительной техники и автоматизированных систем». ФГОУ ВПО «Донской государственный технический университет».

Научный руководитель: Научный консультант: Официальные оппоненты:

Ведущая организация:

доктор технических наук, профессор Нейдорф Рудольф Анатольевич

кандидат технических наук, доцент Кобак Валерий Григорьевич

доктор технических наук, профессор Фатхи Владимир Ахатович

доктор технических наук, профессор Жак Сергей Вениаминович

ФГУ «Информационно-методический центр анализа»

Защита состоится «28» декабря 2009 года в «15:00» на заседании диссертационного совета Д 212.058.04 Донского государственного технического университета по адресу:

344000, г. Ростов-на-Дону, пл. Гагарина, 1. ДГТУ, ауд. № 252.

С диссертацией можно ознакомиться в библиотеке Донского государственного технического университета.

Автореферат разослан «27» ноября 2009 года.

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

Учёный секретарь диссертационного совета,

кандидат технических наук, $МбИи'^"

доцент / Могилевская Н.С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

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

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

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

3

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

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

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

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

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

1. разработка и исследование методов повышения точностной эффективности эволюционно-генетических алгоритмов (ЭГА) при решении распределительных задач (РЗ) высокой размерности;

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

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

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

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

эксперименты и предварительную обработку накопленных статистических данных.

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

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

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

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

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

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

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

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

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

Достоверность результатов исследования

В основу подхода, обеспечивающего достоверность исследований, решений и выводов, положено корректное применение методов системного и математического анализа, статистическая представительность имитационного моделирования и обработки результатов экспериментов. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил около ю6 опытов. Статистическая представительность данных и воспроизводимость свойств обеспечивалась не менее чем 100 параллельными опытами. Программный комплекс «Система вычислительных исследований однородных распределительных задач «Optimal», с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов, прошёл официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2009616118 от 06.11.2009).

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

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

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

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

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

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

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

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

Соответствие диссертации научному плану работ и целевым комплексным программам

Тема диссертационной работы сформулирована в соответствии с тематическим планом ДГТУ, а также лежит в русле списка «Приоритетные направления развития науки, технологий и техники и перечень критических технологий Российской Федерации», утвержденного Президентом Российской Федерации (№ Пр-842 и № Пр-843 от 21 мая 2006 г).

Апробация основных теоретических и практических результатов диссертационной работы

Материалы диссертационной работы докладывались и обсуждались на следующих международных научно-технических конференциях: «Математические методы в технике и технологиях - ММТТ-20» (ЯГТУ, Ярославль, 28-31 мая 2007 г.), «Математические методы в

технике и технологиях - ММТТ-21» (СГТУ, Саратов, 27-30 мая 2008 г.), «Математические методы в технике и технологиях - ММТТ-22» (ППИ, Псков, 25-30 мая 2009 г.); на VIII всероссийской научно-технической конференции «Проблемы информатики в образовании, управлении, экономике и технике» (Пенза, 19-20 ноября 2008 г.); в рамках Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09» на молодежной научно-технической конференции «Интеллектуальные системы - 2009» (Дивноморское, 3-10 сентября 2009 г.).

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях «Донского государственного технического университета» в 20072009 гг.

Публикации по теме диссертационной работы

Основные результаты диссертационной работы опубликованы в 12 работах, из которых 3 - самостоятельные публикации, а 9 опубликовано в соавторстве. При этом 4 статьи опубликованы в ведущих рецензируемых изданиях, входящих в список ВАК РФ. Также в соавторстве были опубликованы одни методические указания по теме диссертации, и получено свидетельство о государственной регистрации программы для ЭВМ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Так же, рассматривается математическая модель исследуемой задачи. Исследуемая однородная система обслуживания состоит из п несвязанных идентичных устройств Р = {р, |/' = 1,и}. На обслуживание поступает набор из т независимых параллельных работ Q = {qJ■\j = l,m}, которым сопоставляется множество ресурсных

оценок Т = \ ] = \,т). Для выполнения отдельной работы д) на каком-либо из устройств р1 системы обслуживания требуется одинаковое количество необходимого ресурса В каждый момент

времени отдельное устройство обслуживает не более одной работы, которая не передаётся на другое устройство.

Задача составления расписания сводится к разбиению исходного Множества работ = = \,т) на п непересекающихся под-

п

множеств, т.е. б,-: ^/Д е[1,и]-> б/Пб* = 0 и ибг = б/гДе л ~ чис"

ы

ло устройств, т - число работ.

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

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

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

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

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

Данная схема применена для увеличения эффективности решения РЗ высокой размерности. Она заключается в том, что исходное (чётное) множество устройств разбивается на два блока, которые условно считаются некоторыми «псевдоустройствами 1 очереди» (ПУ1) обработки заданий. Тогда начальному распределению на 2 ПУ1, состоящих из кх = п!2 реальных устройств каждое, подлежит множество Q из т заданий. Результатом является 2 непересекающихся «подмножества 1 очереди» (ПМ1) заданий. Далее каждое ПМ1 заданий gj и Q\ распределяются на два ПУ2 (псевдоустройства 2 очереди, включающие по k2 = kl/2 = n/4 реальных устройств каждое). В результате получается 4 непересекающихся подмножества заданий а2, Ql, öl, Ql, где ß?Uö22 =öi и ölU=02, образующих расписание для системы из 4 псевдоустройств 2 очереди. Подобные акты деления исходного и промежуточных множеств, рас-

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

конечным этапом декомпозиционного решения РЗ будет распределение /+1 подмножеств где /€ [1,72/2'], на устройств (реальных) каждое.

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

Эффективность предложенного метода и построенных на его основе алгоритмов показана в работе на многочисленных примерах, в которых проводились статичтически представительные имитационные эксперименты. Результаты, полученные в одном из таких примеров показаны в таблице 1. Иллюстрируются результаты решения РЗ для следующих её базовых параметров: п е {4,6,8,10}, т е {25,111,217} при диапазоне работ [25, 30]. В данном примере исследовалось решение РЗ методом ЭГА с заданными параметрами Рсго35= 1 и РтШ = 0.41.

Таблица 1

п т Сред, отклон. от мин. оценки Время решения задач (95%), мс

ЭГА (т.р.) МВД ЭГА ЭГА (т.р.) МБДЭГА

4 25 3,07 0,02 44 66

111 2,37 0 280 210

217 2,05 0 566 398

6 25 2,46 0,01 43 82

111 7,96 0 273 253

217 6,29 0 621 601

8 25 1,35 0,09 50 91

111 4,11 0 288 374

217 7,38 0 599 759

10 25 0,85 0,06 51 96

111 8,78 0 319 434

217 5,58 0 691 802

Решалось по 100 задач с реализацией двух схем распределения: традиционной и бинарно-декомпозицион-ной. Анализ данных табл. 1 показывает более чем существенный, выигрыш в точности. Средняя ошибка в нахождении минимума не превышает 9% (9 опытов из 100), и наличествует лишь для m = 25 (при малом количестве задач плохо выравниваются их промежуточные разбиения). При большем количестве задач реализуется 100% нахождение минимума. Временной ресурс решения, при этом, даёт двоякий результат. При небольшом количестве устройств обработки (4,6) и больших заданиях (111,217) наблюдается некоторый выигрыш в быстродействии (от 4 до 25%). При увеличений числа устройств и относительном снижении объёма заданий преимущество (в некоторых случаях до 50%) получает традиционная схема РЗ.

В третьей главе диссертации исследуется влияние на решение однородной распределительной задачи структуры ЭГА. В качестве базового варианта ЭГА для исследования выбрана модель, предложенная аспирантом проф. Нейдорфа P.A. Будиловским Д.М., защитившим кандидатскую диссертацию в 2007 г.

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

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

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

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

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

ет = ^оп /

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

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

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

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

В связи с поставленной в 1 главе задачей была предложенная модификация формирования нового поколения, заключающаяся в использовании бинарного турнирного отбора, в котором участвуют созданная особь и ее родительская особь. Данная модификации сравнивалась с базовым ЭГА, и показала свою эффективность для п=2.А, при диапазоне работ [25, 30] и заданными параметрами ЭГА Рсго^ = 1, Рти, = 0.41, при решении 100 задач (таблица 2).

п т Сред, отклон. от мин. оценки Время решения задач (95%), мс

ЭГА базовый ЭГА (т.р.) ЭГА базовый ЭГА (т.р.)

25 4,37 0,38 29 37

2 27 4,09 0,25 28 36

29 3,95 0,18 30 40

25 5,08 0,56 26 35

3 27 1,21 0,02 27 30

29 2,97 0,57 29 42

25 3,55 0,75 28 36

4 27 1,58 0,33 41 36

29 3,75 0,7 48 51

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

Таблица 3

и т Сред, отклон. от мин. оценки Время решения задач (95%), мс

МКП ЭГА (т.р.) МКП ЭГА (т.р.)

2 25 11,91 0 0,01 33,50

111 12 0 0,06 106,00

217 12 0 0,19 197,20

4 25 8,67 0 0,01 54,25

111 3,81 0 0,06 269,00

217 16,25 0 0,19 615,05

6 25 5,71 0 0,01 51,23

111 4,03 0 0,06 272,37

217 13,51 0 0,19 552,79

8 25 4,71 0 0,01 52,93

111 0,01 1,98 0,06 299,38

217 12,36 0 0,19 605,77

10 25 0,32 0,13 0,01 52,89

111 10,2 0 0,06 340,88

217 0,17 1,08 0,19 661,99

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

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

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

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

Так, например, для п=2.А, при диапазоне работ [25, 30], который является наиболее трудным для АР, при использовании метода критического пути и использовании линейного спуска с шагом 1, было получено значительное уменьшение скорости нахождения точного решения (таблица 4).

Таблица 4

л Время решения задач (95%), мс

ЬСлас. АР АР+МКП+П.с. АР+МКП+Ш1 АР+МКП+Ш2

2 17395 15491 5005 11482

3 4814 4523 3945 4763

4 714013 697047 190591 388781

При использовании в качестве первого приближения ЭГА в АР для некоторых задач могут получаться очень значимые результаты. Так, например для л=2..4, при диапазоне работ [25, 30] для двух устройств выигрыш составил несколько тысяч раз, но сростом количества устройств практически сравнялся с АР использующем метод критического пути (таблица 5).

п т Время решения задач (95%), мс

АР+МКП+Ш1 АР+ЭГА+Ш1

2 41 115886 46

43 203931 48

3 41 657421 334037

4 19 26512 26453

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

В рамках диссертационной работы разработано ПО «Система вычислительных исследований однородных распределительных задач «Optimal», удовлетворяющее предъявленным требованиям. Данное ПО прошло регистрацию в ФГУ ФИПС, и было получено свидетельство о государственной регистрации программы для ЭВМ № 2009616118 от 06.11.2009 г.

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Титов Д.В. Сравнительный анализ эффективности вариантов турнирного отбора генетического алгоритма решения однородных распределительных задач / P.A. Нейдорф, В.Г. Кобак, Д.В. Титов // Вестник ДГТУ. -2009. - Т.9. - №3(42). - С. 410-418.

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

3. Титов Д.В. Повышение эффективности генетического алгоритма для систем обработки заданий высокой размерности / Д.В. Титов // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'09». - М.: Физматлит, 2009. - Т.З. - С. 346-350.

4. Титов Д.В. Модификация генетического алгоритма для четного количества однородных приборов / Д.В. Титов // Известия вузов. Сев.-Кавк. регион. Техн. науки. - 2010. - №1. [В печати].

Публикации в других изданиях

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

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

7. Титов Д.В. Исследование принципа турнирного отбора генетического алгоритма для решения однородной минимаксной задачи / В.Г. Кобак, Д.В. Титов // Математические методы в технике и технологиях - ММТГ-21: сб. тр. XXI Междунар. науч. конф., 27-30 мая / СГТУ. - Саратов, 2008. - Т.2, секц. 2, 6. - С. 12-13.

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

9. Титов Д.В. Анализ подходов к улучшению результатов работы генетического алгоритма при решении однородной минимаксной задачи / Д.В. Титов, В.Г. Кобак // Проблемы информатики в образовании, управлении, экономике и технике: сб. ст. VIII Всерос. науч.-техн. конф., 19-20 нояб. -Пенза, 2008. - С. 76-78.

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

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

12.Титов Д.В. Алгоритмическое улучшение работы генетического алгоритма для четного количества процессоров / В.Г. Кобак, Д.В. Титов // Сб. науч.-метод. ст. ввузов связи МО РФ по математическим и общим естественно-научным дисциплинам / НВВКУС. - Новочеркасск, 2009. - Вып. 11. - С. 31-35.

13. Система вычислительных исследований однородных распределительных задач «Optimal»: свидетельство о государственной регистрации программы для ЭВМ № 2009616118 / Д.В. Титов, В.Г. Кобак, Р.А. Нейдорф. -№ 2009614987; заявл. 15.09.2009; зарег. 06.11.2009.

14.Титов Д.В. Исследование способа формирования элитной особи генетического алгоритма для однородных систем / В.Г. Кобак, Д.В. Титов, В.В. Кобак // Математические методы в технике и технологиях - ММТТ-22: сб. тр. XXII Междунар. науч. конф. IV Междунар. науч. метод, симпоз. «Современные проблемы многоуровневого образования» / ДГТУ. - Ростов н/Д, 2009. - С. 132-133.

В работах [1,2,5-9,11-14] автору принадлежат наиболее существенные результаты, связанные с разработкой и экспериментальным подтверждением основных положений диссертационной работы..

В набор 26.11.2009. В печать 27.11.2009.

Объем 1 усл.п.л., 1.0 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ № 539. Тираж 120.

Издательский ДГТУ Адрес университета и полиграфического предприятия: 344000, г.Ростов-на-Дону, пл.Гагарина,!.

ВВЕДЕНИЕ.

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

1.1. Краткая характеристика распределительных задач теории расписания.

1.1.1. Примеры возникновения и применения распределительных задач в различных сферах человеческой деятельности.

1.1.2. Распределительные задачи и теория расписаний.

1.1.3. Класс статических распределительных задач.

1.1.4. Основные понятия теории решения распределительных задач.

1.1.5. Однородные распределительные задачи теории расписаний.

1.1.6. Характеристика сложности решения распределительных задач теории расписаний

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

1.2.1. Теоретико-множественная формулировка однородной распределительной задачи.

1.2.2. Критериально-оценочная составляющая однородной распределительной задачи

1.2.3. Оптимизационная составляющая однородной распределительной задачи.

1.3. Методы решения однородных распределительных задач и их классификация.зз

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

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

1.3.3. Детерминированные методы приближённого решения однородных распределительных задач.

1.3.4. Анализ детерминированных методов приближённого решения однородных распределительных задач.

1.3.5. Эвристические методы приближённого решения однородных распределительных задач

1.3.6. Анализ эвристических методов приближённого решения однородных распределительных задач.'.

1.4. Эволюционно-генетические алгоритмы приближенного решения однородных распределительных задач.

1.4.1. Общий принцип работы эволюционно-генетических алгоритмов.

1.4.2. Представление данных в генах.

1.4.3. Стратегии отбора.

1.4.4. Стратегии формирования нового поколения.

1.4.5. Генетические операторы.

1.5. Алгоритм Романовского точного решения однородных распределительных задач.

1.5.1. Особенности и возможности алгоритма Романовского.

1.5.2. Ход работы алгоритма Романовского.

1.6. выводы по первой главе.

2. БИНАРНО-ДЕКОМПОЗИЦИОННЫЙ ПОДХОД К РЕШЕНИЮ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ ВЫСОКОЙ РАЗМЕРНОСТИ.

2.1. Декомпозиция как метод повышения эффективности решения распределительной задачи.

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

2.1.2. Пример применения блочной декомпозиции к решению распределительной задачи.

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

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

2.2.1. Проблема эффективной оценки сравниваемых методов решения распределительных задач.

2.2.2. Точностная оценка эффективности сравниваемых методов решения распределительных задач.

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

2.3. Практическое применение блочно-декомпозиционного подхода к решению распределительных задач

2.3.1. Алгоритм блочно-декомпозиционного решения распределительных задач.

2.3.2. Вычислительный эксперимент бинарно-декомпозиционного решение распределительных задач на базе эволюционно-генетического алгоритма.

2.4. выводы по второй главе.

3. СТРУКТУРНО-ПАРАМЕТРИЧЕСКОЕ УСОВЕРШЕНСТВОВАНИЕ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКОГО АЛГОРИТМА.

3.1. Базовая модель эволюционно-генегических алгоритмов.

3.1.1. Математическая модель базового эволюционно-генетического алгоритма.

3.1.2. Алгоритмическая реализация базового эволюционно-генетического алгоритма.

3.1.3. Пример использования базового эволюционно-генетического алгоритма.

3.2. Модификация стратегии формирования нового поколения в эволюционно-генетических алгоритмах

3.2.1. Алгоритмическое улучшение формирования нового поколения в эволюционно-генетическом алгоритме.

3.2.2. Пример использования модифицированного эволюционно-генетического алгоритма

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

3.3. Зависимость оптимизационной эффективности эволюционно-генетических алгоритмов от размерности задачи и параметров алгоритма.

3.3.1. Влияние количества устройств на оптимизационную эффективность эволюционно-генетических алгоритмов.

3.3.2. Исследование оптимизационной эффективности эволюционно-генетических алгоритмов с использованием элитных особей.

3.3.3. Повышение оптимизационной эффективности эволюционно-генетических алгоритмов с помощью бинарной декомпозиции.

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

4. МОДИФИКАЦИЯ АЛГОРИТМА РОМАНОВСКОГО С ИСПОЛЬЗОВАНИЕМ ПРИБЛИЖЕННЫХ МЕТОДОВ

4.1. Алгоритмическое повышение быстродействия алгоритма Романовского уточнением верхней границы

4.1.1. Модификация начального этапа алгоритма Романовского с использованием списочного алгоритма.

4.1.2. Пример использования традиционного приёма вычисления верхней границы алгоритма Романовского.

4.1.3. Пример использования для вычисления верхней границы списочного алгоритма.

4.1.4. Анализ работы алгоритма Романовского и его списочной модификации по результатам примеров.

4.1.5. Сравнение эффективности работы алгоритма Романовского и его списочной модификации по результатам вычислительного эксперимент.

4.2. Разработка эффективных способов выделения z-задачи алгоритма Романовского.

4.2.1. Способ использования метода двоичного деления для выделения z-задачи алгоритма Романовского.

4.2.2. Пример использования метода двоичного деления для выделения z-задачи алгоритма Романовского.

4.2.3. Способ использования метода линейного спуска для выделения z-задачи алгоритма Романовского

4.2.4. Пример использования метода линейного спуска для выделения z-задачи алгоритма Романовского.

4.2.5. Пример использования метода последовательного спуска для выделения z-задачи алгоритма Романовского.

4.2.6. Сравнение и анализ примеров использования разных способов выделения z-задачи.

4.2.7. Вычислительный эксперимент для сравнения эффективности модификацией алгоритма Романовского с использованием разных способов выделения z-задачи.

4.3. модификация начального этапа алгоритма романовского с использованием эволюционно-генетических алгоритмов.

4.3.1. Пример использования эволюционно-генетической модификации алгоритма Романовского

4.3.2. Вычислительный эксперимент по сравнению списочной и эволюционно-генетической модификаций алгоритма Романовского.

4.4. выводы по четвертой главе.

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

5.1. Структура программного обеспечения.

5.1.1. Задачи и функции программного обеспечения диссертационных исследований.

5.1.2. Структурные составляющие программного обеспечения решения распределительных задач.

5.1.3. Функциональная структура программного обеспечения.

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

5.2.1. Организация данных программного обеспечения.

5.2.2. Структура хранения данных программного обеспечения.

5.3. Интерфейс программного обеспечения.

5.3.1. Основной оконный интерфейс.

5.3.2. Компонент интерфейса программного обеспечения «Меню».

5.3.3. Компонент интерфейса программного обеспечения «Панель инструментов».

5.3.4. Компонент интерфейса программного обеспечения «Эксперименты».

5.3.5. Компонент интерфейса программного обеспечения «Вкладки эксперимента».

5.3.6. Компонент интерфейса программного обеспечения «Статус».

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

Во многих областях инженерных и управленческих задач широкое практическое распространение получают задачи теории расписания [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» (ФГУ ФИПС свидетельство № 2009616118 от 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. Применение разработанного ПО для исследования методов решения однородных РЗ позволило провести множество численных экспериментов и получить сведения, необходимые для анализа эффективности рассматриваемых в диссертационной работе методов, обеспечив выполнение и обработку более миллиона опытов.

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

2. Land, А.Н., Doig, A.G. An automatic method of solving discrete programming problems. 1960, Vol. 28, pp. 497-520.

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

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

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

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

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

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

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

10. Кобак В.Г. Взаимосвязь минимаксного и квадратического критериев в однородной трехприборной системе / В.Г. Кобак, Р.А. Нейдорф // Информатика и системы управления. 2005. — №2. - С. 162-168.

11. Коршунов Ю.М. Математические основы кибернетики: Учеб. пособие для вузов / Ю.М. Коршунов. М.: Энергоатомиздат, 1987. - 496 с.168

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

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

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

15. Финкелыптейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования / Ю.Ю. Финкелыптейн. М.: Наука, 1976.-264 с.

16. Woolf, Murray В. Faster Construction Projects with CPM Scheduling. New York: McGraw Hill, 2007. p. 456.

17. Newell, M; Grashina, M. The Project Management Question and Answer Book. New York: American Management Association, 2003. p. 98.

18. Haddock, Jorge; Mittenthal, John. Simulation optimization using simulated annealing. Computers & Industrial Engineering. 1992, Vol. 22, 4, pp. 387395.

19. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика / Ф. Уоссермен. М.: Мир, 1992. - 118 с.

20. Eberhart, R.C.; Dobbins, R.W.; Simpson, P. Computational Intelligence PC Tools. Boston: Academic Press, 1996.

21. Eberhart, R.C.; Kennedy, J.A. New Optimizer Using Particles Swarm Theory. Proc. Sixth International Symposium on Micro Machine and Human Science. IEEE Service Center, Piscataway, 1995.

22. Aarts, E.; Lenstra J.K. Local Search in Combinatorial Optimization. Chichester: John Wiley & Sons, 1997.

23. Боровков A.A. Теория вероятностей: Учебное пособие для вузов / А.А. Боровков. М.: Наука, 1986. - 432 с.

24. Brucker P. Scheduling Algorithms. New York: Springer Yerlag, 2001. p. 377.

25. Gantt, H.L. A Graphical Daily Balance in Manufacture. ASME Transactions. 1903, Vol. 24, pp. 1322-1336.

26. Jackson, J.R. Scheduling a production line to minimize maximum tardiness. Research Report 43. Management Science Research Project, University of California, Los-Angeles, 1955.

27. Johnson, S.M. Optimal two- and three-stage production schedules with setup times included. Naval Res. Logistics Quart. 1954, Vol. 1, 1, pp. 61-68.

28. Конвей. P.B. Теория расписаний / P.B. Конвей, В.JI. Максвелл, JI.B. Миллер. -М.: Наука, 1975. 360 с.

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

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

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

32. Michael, L.P. Scheduling: Theory, Algorithms, And Systems. New York: Springer Verlag, 2008. p. 678.

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

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

35. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкфорт, Дж. Ульман. М.: Мир, 1979. - 536 с.

36. Пападимитриу X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. -М.: Мир, 1985. 512 с.

37. Праневичус Г.И. Модели и методы исследования вычислительных систем / Г.И. Праневичус. Вильнюс: Монслас, 1982. - 228 с.

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

39. Brucker, P. Scheduling Algorithms. New York: Springer Verlag, 2001. p. 377.

40. Конвей. P.B. Теория расписаний / P.B. Конвей, В.JI. Максвелл, JT.B. Миллер. М.: Наука, 1975. - 360 с.

41. Танаев B.C. Теория расписаний. Групповые технологии / B.C. Танаев, М.Я. Ковалев, Я.М. Шафранский . Минск, 1998.

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

43. Псигин Ю.В. Основы математического модулирования. / Ю.В. Псигин, С.И. Рязанов. Ульяновск: УлГТУ, 2007. - 40 с.

44. Martello, S. Knapsack problems: algorithms and computer implementations. Chichester: John Wiley & Sons, Ltd., 1990.

45. Goldberg, D. Genetic Algorithms In Search, Optimization, and Machine Learning. USA: Addison-Wesley Publishing Company, Inc., 1989.

46. Holland, J. Adaptation in Natural and Artificial Systems: An, Introductory Analysis with Application to Biology, Control, and Artificial Intelligence. USA: University of Michigan, 1975.

47. Langdon, P. Foundations of Genetic Programming. Berlin: Springer Verlag, 2001.

48. Что такое генетические алгоритмы Электронный ресурс. / НейроПроект; Струнков Тимофей. Москва, 2007. - Режим доступа: http://www.neuroproject.ru/gene.php, свободный. - Загл. с экрана.

49. Шенк X. Теория инженерного эксперимента. М.: Мир, 1972. - 384с.

50. Fogel, L.J. Artificial Intelligence through Simulated Evolution. Walsh.-USA: John Wiley, 1966.

51. Bruns, R. Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling // Proc. of 5th Int. Conf. on GA, 1993.

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

53. Nakano, R. Conventional Genetic Algorithm for Job Shop Problems // Proc. of 4th Int. Conf. on GA, Morgan Kaufinann Publ., San Francisco, 1991.

54. Lawrence, D. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991.

55. Cohoon J.P., Martin W. N., Richards D.S. A multi-population genetic algorithm for solving the k-partition problem on huper-cube. San Diego, 1991.

56. De Jong, К.A. Genetic Algorithms: A 10 Year Perspective // In: Procs of the First Int. Conf. on Genetic Algorithms, 1985. pp.167-177.

57. Martello, S.; Toth, P. Knapsack problems: algorithms and computer implementations. Chichester: John Wiley & Sons, Ltd., 1990.

58. Schwefel, H.P. Numerical optimization of computer models. Chichester: Wiley, 1981.

59. Кобак В.Г. Уменьшение времени работы точного алгоритма, при решении задачи о камнях / Кобак В.Г. // Современные проблемы информатизации в непромышленной сфере экономики. 2003. №3 — С. 100-101.

60. Genetic algorithm Электронный ресурс. / Wikipedia. Режим доступа: http://en.wikipedia.org/wiki/Geneticalgorithm, свободный. - Загл. с экрана.

61. Генетические алгоритмы математический аппарат Электронный ресурс. / BaseGroup Labs; Стариков Алексей. - Рязань, 2007. - Режим доступа: http://www.basegroup.ru/genetic/math.htm, свободный. - Загл. с экрана.

62. Btuns, R. Direct Chromosome Representation and Advanced Genetic Operators for Production Scheduling II Proc. of 5th Int. Conf. on GA, Morgan Kaufmann Publ., 1993.

63. Gray code Электронный ресурс. / Wikipedia. Режим доступа: http://en.wikipedia.org/wiki/Gray code, свободный. - Загл. с экрана.

64. Sawada, J. A Fast Algorithm to generate Beckett-Gray codes II Electronic notes in Discrete Mathematics (EuroComb 2007), 2007.

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

66. Blickle, Т.; Thiele, L. A Comparison of Selection Schemes used in Genetic Algorithm. Thiele: TIK-Report, 1995.

67. Норенков И.П. Генетические методы структурного синтеза проектных решений // Информационные технологии, 1998. № 1. - .С. 9-13.

68. Bui, T.N.; Moon, B.R. A new approach on the traveling salesman problem by genetic algorithms // Evolutionary Computation. 1994. - pp. 7-12.

69. Coley, D.A. An introduction to genetic algorithms for scientists and engineers. World Scientific Publishing, 1999. 244 p.

70. Скурихин. A.H. Генетические алгоритмы // Новости искусственного интеллекта . 1995. - №4. - С. 6-46.

71. Афанасьев М.К. Конструктор генетических алгоритмов и способы кодирования хромосом // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. М.: Изд-во Московского университета, 2001. - №3. - С. 43-49.

72. Батищев Д.И. Генетические алгоритмы решения экстремальных задач / Батищев Д.И. Воронеж, ВГТУ, 1995. - 69 с.

73. Eiben Е. A. Introduction to Evolutionary Computing/E. A. Eiben, A. E. Eiben.-Berlin: Springer-Verlag, 2003.

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

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

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

77. Система вычислительных исследований однородных распределительных задач «Optimal»: свидетельство о государственной регистрации программы для ЭВМ № 2009616118 / Д.В. Титов, В.Г. Кобак, Р.А. Нейдорф. -№ 2009614987; заявл. 15.09.2009; зарег. 06.11.2009,

78. Буч Г. Объектно-ориентированный анализ и проектирование / Г. Буч. -М: Бином, 1998. 560 с.

79. Троелсен Э. С# и платформа .NET 3.0 / Э. Троелсен. Спб: Питер, 2008. -1456 с.

80. Нейдорф Р.А. Сравнительный анализ эффективности вариантов турнирного отбора генетического алгоритма решения однородных распределительных задач / Р.А. Нейдорф, В.Г. Кобак, Д.В. Титов // Вестник ДГТУ. 2009. - Т.9. - №3(42). - С. 410-418.

81. Титов Д.В. Повышение эффективности генетического алгоритма для систем обработки заданий высокой размерности / Д.В. Титов // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT09». -М.: Физматлит, 2009. Т.З. - С. 346-350.

82. Налимов В.В. Теория эксперимента. М.:Наука, 1971.

83. Вентцель Е.С. Исследование операций. М.: Наука, 1980. - 208 с.

84. Овчаров JI.A. Теория вероятностей и ее инженерные приложения: учебное пособие для втузов / Овчаров Л.А., Вентцель Е. С. М.: Высшая школа^ 2007. - 491с.

85. Кобак В.Г. Анализ работы алгоритма Романовского с использованием разных подходов к формированию верхней и нижней границ / В.Г. Кобак, Д.В. Титов // Математические методы в технике и технологиях

86. ММТТ-20: сб. тр. XX Междунар. науч. конф., 28-31 мая / ЯГТУ -Ярославль, 2007. Т.2, секц. 2, 6. - С. 57-59.

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