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

На правах рукописи а *

КРАСНЫЙ ДМИТРИЙ ГЕОРГИЕВИЧ

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

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

Автореферат диссертации на соискание учёной степени кандидата технических наук

4 с

П!:Н 2008

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

003457991

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

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

Нейдорф Рудольф Анатольевич

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

Жак Сергей Вениаминович

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

Ведущая организация: ФГУ «Информационно-методический центр

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

Защита состоится « 25 » декабря 2008 года в « 12-00 » на заседании диссертационного совета Д 212.058.04 Донского государственного технического университета по адресу: 344000, г. Ростов-на-Дону, пл. Гагарина, 1. ДГТУ ауд. № 252.

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

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

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

Учёный секретарь

диссертационного совета, //

кандидат технических наук, /

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

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

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

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

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

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

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

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

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

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

1. исследование и модификация точного алгоритма Алексеева решения неоднородной распределительной задачи применительно к ко-

_ личесгвенным и качественным неоднородностям;

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

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

4. исследование и реализация возможностей параметрической оптимизации качества работы ЭГА применительно к изучаемой области неоднородных распределительных задач;

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

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

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

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

2. Разработана списочная модификация точного алгоритма Алексеева с применением качественно-количественной оценки неоднородности и избирательности матрицы загрузки для распределительных задач с качественной неоднородностью. Данная модификация позволяет значительно (не менее чем на 30%) уменьшить время поиска оптимального решения и расширить размерность задач (не менее чем на 20%), решение которых можно найти за приемлемое время.

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

4. Получено доказательство применимости зволюционно-генетической модели к неоднородным распределительным задачам с соответствующей критериальной доработкой, и выполнена оптимизация параметров ее настроек для решения неоднородных распределительных задач на основании статистически представительной выборки объёмом не менее 25 тыс. опытов, что дало повышение доверительной вероятности оптимального решения для исследуемого диапазона параметров задачи более 80%.

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

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

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

При реализации программного средства «Система вычислительных исследований неоднородной распределительной задачи «Ртс1№У1/Ме№ос)» применялись концепции объектно-ориентированного программирования и реляционных баз данных.

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

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

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

■ существенное (10-30%) снижение времени решения неоднородных и распределительных задач точными алгоритмами;

■ • существенное (16%) повышение точности решения неоднородных и

распределительных задач приближёнными алгоритмами;

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

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

Разработанное для исследований программное обеспечение «Система вычислительных исследований неоднородной распределительной задачи «РтсШеу/МеШос!», с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов, прошло официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2008613599 от 28.07.2008).

Апробация основных теоретических и практических результатов диссертационной работы. Материалы диссертационной работы докладывались и обсуждались на следующих международных научно-технических конференциях: «Математические методы в технике и технологиях - ММТТ-20»: сб. тр.ХХ Междунар. науч. конф./ ВГТА. - Яро-

славль, 200"?. - I 2, секц. 2,6; ^Математические методы в технике и технологиях - ММТТ-21»: сб. тр.ХХ1 Междунар. науч. конф./ ВГТА. - 'Саратов, 2008. - Т. 5, секц. 11;

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

Публикации по теме диссертационной работы. Основные результаты диссертации опубликованы в 9 работах, из которых 2 - самостоятельные публикации, а 7 опубликовано в соавторстве. При этом 3 статьи опубликованы в ведущих научных журналах, входящих в список 6АК РФ.

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

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

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

Анализ источников литературы по теории расписаний позволил выделить статическую неоднородную распределительную задачу в качестве объекта исследования, вследствие того, что данная задача относится к задачам календарного планирования и является № полной, т.е. теоретическая сложность нахождения наилучшего распределения связано с решением экстремальных задач комбинаторного типа, требующих больших вычислительных ресурсов. Существующие точные методы ограничены сравнительно узкой областью размерностей задач их возможного применения, а приближенные методы позволяют решать распределительные задачи с некоторой погрешностью, иногда превосходящей 30%.

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

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

Рассматривается математическая модель исследуемой задачи, которая ориентирована на то, что исследуется система обработки, состоящая из п несвязанных устройств Р = {pj | У = !,/?>, в которую на обработку поступает набор из т независимых параллельных работ 7" = {1 = 1, ту . В условиях неоднородности системы эти работы характеризуются множеством ресурсных оценок

5 = | /' = 1, /77; у = 1, пу, отображающих тот факт, что для выполнения отдельной /' -й работы на каком-либо / -м устройстве системы требуется различное количество необходимого ресурса . Применительно

к ЭВМ такими ресурсами могут быть ёмкость устройств оперативной и внешней памяти, процессорное время, стоимость обработки и т.п.

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

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

задачи по типу неоднородности на количественную ЯА'1 и качественную X . Когда существует избирательность типа - со, то / работа не может быть обслужена у -м устройством. Примеры матриц загрузки количественно и качественно неоднородных показаны ниже.

5КЛ =5 15 4! 12 9 2\

II 7 9|

5КЧ =5 15 да 8 6 12

оо оо 7

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

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

На основе выдвинутых предположений разработаны списочные модификации алгоритма Алексеева (СМ АА) для задач с количественной и качественной неоднородностью.

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

сложности 5 упорядочить по убыванию суммы всех элементов строки, т.е. обеспечить следующее свойство новой матрицы 5':

...> (1)

Преобразованную матрицу предложено обозначать 5' , где

5' = {5,- | /' = 1, /77; ] = 1, /7> и использовать в качестве базовой матрицы

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

Оптимальное решение, построенное на основе новой матрицы вычислительной сложности 5', достигается при дальнейшем выполнении, шагов исходного АА.

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

Для описываемых вариантов предполагается, что задана система, состоящая из п независимых устройств и множества т назначенных для обработки ею независимых работ. Для каждой /' -й работы, назначенной на устройство У , количество ресурса, необходимого для ее выполнения, определено в матрице вычислительной сложности 5 , либо такое, что ^ > 0, либо такое, что = да. Далее, в рамках решаемой

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

Списочная модификация АА с качественным учетом избирательности. Вводится вектор V, элементы которого определяться следующим образом:

V, =«=(/)// = 1..л», (2)

где ? - функция, которая возвращает 1, если в строке /' есть хотя бы один элемент = «>, иначе она возвращает 0. Таким образом, если

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

рядке убывания /,• и £5„ , / = 1..ш для г,у . Преобразованная

>1

матрица определяется как 5К . Далее она будет использована при выполнении шагов классического алгоритма Алексеева.

Списочная модификация АА с качественно-количественным учетом избирательности. Так же как и для первого варианта, вводится вектор V , элементы которого определяются следующим образом;

И,=ГС(/),/ = 1../77, (3)

где РС - функция, которая возвращает количество элементов в строке / равных бесконечности (5 у = да), если возвращается 0, то строке / нет элементов равных бесконечности.

Элементы вектора V упорядочиваются и соответствующие /' -е

п

строки 5 располагаются в порядке убывания у, и ■ , ¡-\..т для

± х . Таким образом, при упорядочивании строк преобразованной

матрицы 5Лд в строке учитывается количество элементов, равных бесконечности.

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

Имитационное исследование применения СМ АА для точного решения неоднородных распределительных задач. Для каждого из списочно-модифицированных алгоритмов реализован статистически представительный (не менее 15 тыс. опытов) эксперимент с использованием имитационного моделирования решения исследуемого класса и диапазона распределительных задач. В результате выполнения множества серий опытов накоплена статистическая информация, позволяющая оценить качественные и количественные оценки полученных решений. Для различных исходных данных по результатам экспериментов построены диаграммы изменения времени решения задачи для каждого из алгоритмов.

На диаграммах (рис. 1 и рис. 3) показана зависимость времени решения задачи с количественной и качественной неоднородностью от ее размерности для каждого из алгоритмов при п = 4 и 5;у е [15,40]. На

рис. 2 и рис. 4 показана оценка улучшения времени решения СМ АА в % с изменением т, при п = 4 и е [15,40] . Для задачи с качественной неоднородностью, это показано для каждой из модификаций алгоритма. Аналогично в работе проиллюстрировано сравнение решения задачи с качественной неоднородностью предложенными списочными модификациями алгоритма Алексеева и классическим АА.

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

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

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

Ь:р,С.

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 ,

-АА —&—СМ АА

Рис. 1 Решение СМ АА задач с количественной неоднородностью, при п = 4 и ге [15,40]

5г*

го

% 100.00 80.00 60.00 40.00 20.00 0.00

- — н

* . - О- ' + - -4- * * " Ф"

&--- Ж' Ж

»■ * • *

15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

■ Область доверительных значений

Рис. 2 Улучшение времени решения СМ АА в сравнении с АА для задач с количественной неоднородностью, при п = 4 и е [15,40]

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 т —♦— АА —■&— СМ АА (КК) СМ АА (кГ

Рис. 3 Решение СМ АА задач с качественной неоднородностью, при «=4 и « . е[15,40|

—&—см дд (ККл см дА . . . обл. довер. знач. I

Рис. 4 Улучшение времени решения СМ АА (К) и (КК) в сравнении с АА для задач с качественной неоднородностью, при п = 4 и 5,у е [15,40]

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

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

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

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

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

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

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

зависимость точности решения СМ АА без возвратов от размерности задачи. Показано, что с увеличением числа независимых параллельных работ и при малом числе устройств эффективность алгоритма по качеству решения увеличивается. Применение СМ АА без возвратов позволяет повысить качество решения по точности получаемых расписаний не менее чем на 4%. Повышение точности может достигать и 16% в зависимости от степени однородности значений матрицы вычислительной сложности и размерности задач. Результаты вычислительных экспериментов и рассчитанные значения оценок показаны в таблице 1.

Таблица 1

Диапазон 6 [5,50] 50 6 [25,30]

N 10 10 10 10 10 10 10 10

М 299 499 699 899 299 499 699 899

Ь:Р (АПЗ), сек. 0,01 0,01 0,02 0,02 0,01 0,02 0,02 0,02

Ь* (СМАА без возвратов), сек. 0,12 0,19 0,25 0,30 0,14 0,22 0,26 0,33

Опш» (ДПЗ) 327 541 759 974 808 1343 1879 2413

(СМАА без возвратов) 286 466 646 829 775 1289 1800 2311

ЪЦср >% 12,8 14,1 15,7 15,2 4Д 4,2 4,4 4,3

а,% 2,2 1,8 1,7 1,4 0,6 0,5 0,4 0,3

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

Общий подход к кодированию в гены можно рассматривать со следующей точки зрения. Хромосома сЛ, - это информация, представляющая некоторое возможное решение задачи, т.е. расписание работ по устройствам. Хромосома состоит из генов 6 = {д, | / = 1,2,...с0-> , где

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

представление кратное машинному слову. При таком представлении число геноЕ cG ^ т совпадает с количеством работ, а размер гена определяется максимальным числом устройств в системе обслуживания;

Строение хромосомы задается формой gs = {рг/,},..., дт а ее размер определяется из произведения числа генов в хромосоме на размер одного гена: s¡zeof(ch) - cG sizeof(g¡).

. ? . Пример кодирования расписания. R, построечного в результате решения неоднородной распределительной задачи из я = 3 устройств и т = 1 работ, в предложенной генной форме будет тогда выглядеть следующим образом; g¡ = {2} д2 - <1} д} = {!} £?4 ={2} ду - {?-> д„ = {2} д7 = <3>, а результирующее расписание имеет вид: Р, 5[3,р,]

/?=/?, S[l,£7,] Sl4,gJ 5[6,Oj . Ръ s[7,g7]

Для построенной эволюционно-генетической модели разработана методика проведения параметрической оптимизации ее настроек. Применение этой методики позволяет с достоверной вероятностной точностью получать наилучшие параметры ЭГА (вероятности мутаций генов РтиЫ = 0,062 и хромосом Pmutchr = 0,42 , вероятность скрещивания

Pcross -1 ' число популяций N йт = 800 , число особей в популяции N^ = 80). Так, например, применение этой методики позволило увеличить вероятность получения оптимального решения не менее, чем на 82% для задачи п=2, т=45, s0 е [5,50].

Это достигается при значениях параметров ЭГА значительно отличающихся от рекомендованных в литературе по генетическим алгоритмам. Найденное в работе максимальное значение вероятностной точности (рис. 7) соответствует следующим настройкам ЭГА: Pmutchr = 0,42 , РтиШ! = 0,062, Pmss = 1, NVim = 800 , Nchr = 80 при использовании равномерного закона для определения точки деления хромосомы при выполнении операции скрещивания.

Для оценки эффективности новых настроек для ЭГА поставлен вычислительный эксперимент решения задачи при значениях п=2 и т=45 обеспеченный 100 испытаниями для каждого параллельного опыта, на диаграмме рйс. 8 показано значение оценки вероятностной точности для ЭГА.

Вероятностная точность алгоритма после оптимизации параметров составила по минимальному значению оцени /?min = 0,82 , в то время

как максимальное значение оценки до оптимизации параметров составляло ртах = 0,32 . Таким образом, улучшение точностного показателя

ЭГА составило около 3, что является весьма значительным и убедительным результатом оптимизации.

= 0,836

Л,- ^0,842"

>'л =

0,820 ^ 5\,. =0,822

0,856.

Л, г 0,858

_ = 0,в20 10,39 у ^ =0,844 Я,-0,832

Рис. 7 Стационарная область соответствующая максимальному значению значения вероятностной точности

Р, 1 0.8 0.6 0.4 0.2 О

1

I

1 3 5 7 9 11 13 15 17 19 1а Об 1

Рис. 8 Оценки вероятностной точности ЭГА: а- по оптимизации; 6-после оптимизации значений параметров алгоритма

Таблица 2

п 2 2 3 3 4 4

171 24 294 24 2941 24 294

Ь:Р (ЭГА), сек. 1,60 108,92 2,13 87,76 2,47 68,12

ЬР (СМ АА без в.), сек. 0,01 0,04 0,01 0,16 0,01 0,23

(АПЗ), сек. 0,01 0,02 0,01 0,03 0,01 0,03

Оценка времени решения для каждого из приближенных алгоритмов исследуемых для решения неоднородных распределительных задач в рамках работы, показана в таблице 2. Для СМ АА без возвратов оценка времени для всех рассмотренных размерностей задач не превышает одной секунды и увеличивается с ростом размерности задачи медленно, что является положительной характеристикой алгоритма. Такая же оценка времени, сделанная для ЭГА, позволяет сделать вывод, что у этого алгоритма время также увеличивается медленно, однако зависимость размерности задачи и времени ее решения выражена сильнее, чем у СМ АА без возвратов,

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

В рамках диссертационной работы разработано программное обеспечение (ПО) «FindNewMethod», удовлетворяющее поставленным требованиям. Программное обеспечение «FindNewMethod» предназначено для проведения вычислительных экспериментов по исследованию решения неоднородных распределительных задач теории расписаний и прошло официальную регистрацию программы для ЭВМ в ФГУ ФИПС, с присвоением регистрационного номера №2008613599 от 28.07.2008.

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

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

В заключении сформулированы основные выводы и результаты диссертационной работы.

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

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

1. Красный Д.Г. Решение минимаксных задач в неоднородной среде избирательно работающих устройств модифицированным алгоритмом Алексеева// Вестник ДГТУ.- 2007.- Т.7. №4. - С. 395-401

2. Нейдорф P.A., Кобак В.Г., Красный Д.Г. Точное решение неоднородной распределительной задачи модификацией алгоритма Алексеева// Известия СКНЦВШ. Техн. науки. - 2008. - №1 - С.17-22

3. Нейдорф P.A., Кобак В.Г., Красный Д.Г. Перспективные алгоритмы решения неоднородной распределительной задачи теории расписаний// Известия ТТИ ЮФУ.- 2008.

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

4. Нейдорф P.A., Кобак В.Г., Красный Д.Г. Модификация алгоритма распределения в неоднородной системе обработки информации// Новые грани познания: межвуз. сб. науч. тр. - М.: Учеб. литература, 2007.

5. Кобак В.Г., Красный Д.Г. О возможности построения алгоритмов приближенного решения минимаксных задач в неоднородных средах// Системный анализ, управление и обработка информации: межвуз. сб. науч. тр. Ростов н/Д: ДГТУ, Таганрог: ТТИ ЮФУ, 2007. -С. 120-126.

6. Красный Д.Г. Анализ эффективности модифицированного алгоритма Алексеева приближенного решения неоднородной распределительной задачи// Системный анализ, управление и обработка информации: межвуз. сб. науч. тр. Ростов н/Д: ДГТУ, Таганрог: ТТИ ЮФУ, 2007. - С. 126-131.

7. Нейдорф P.A., Кобак В.Г., Красный Д.Г. Оценка точности приближенного алгоритма при решении минимаксной задачи теории расписаний// Международная научная конференция "Математические методы в технике и технологиях" - ММТТ-20 ВГТА. - Ярославль, 2007. - Т. 2. - С. 52-54.

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

9. Красный Д.Г. Официальная регистрация программы для ЭВМ ФГУ ФИПС «Система вычислительных исследований неоднородной распределительной задачи» // Нейдорф P.A., Кобак В. Г. // №2008613599 от 28.07.2008 г.

В набор 19.11.2008. В печать 20.11.2008. Объем 1,7 усл.п.л., 2,5 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ № 538. Тираж 120.

Издательский ДГТУ

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

ВВЕДЕНИЕ.

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

1.1. Распределительные задачи теории расписаний и области их применения

1.1.1. История возникновения и применения.

1.1.2. Распределение заданий в вычислительных системах.

1.1.3. Структура и технология решения распределительных задач.

1.2. Основные термины и концептуальная модель задач теории расписаний

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

1.3.1. Теоретико-множественная составляющая распределительной задачи.

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

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

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

1.4. Анализ существующих методов решения рас1 1ределительных задач.

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

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

1.4.3. Комбинаторный подход решения распределительных задач.

1.4.4. Эвристические и вероятностные методы.

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

2. СПИСОЧНО-МОДИФИЦИРОВАННЫЙ АЛГОРИТМ ТОЧНОГО РЕШЕНИЯ НЕОДНОРОДНОЙ РАСПРЕДЕЛИТЕЛЬНОЙ ЗАДАЧИ.

2.1. Списочно-модификацированиый алгоритм Алексеева.

2.1.1. Общая характеристика алгоритма Алексеева.

2.1.2. Списочная модификация алгоритма Алексеева для распределительной задачи с количественной неоднородностью.

2.1.3. Списочная модификация алгоритма Алексеева для распределительной задачи с качественной неоднородностью.

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

2.2.1. Решение распределительной задачи с количественной неоднородностью.

2.2.2. Решение распределительной задачи с качественной неоднородностью.

2.3. Имитационное исследование применения СМ АА для точного решения неоднородных распределительных задач.

2.3.1. Организация вычислительного эксперимента.

2.3.2. Исследование свойств СМАА при решении распределительных задач с количественной неоднородностью.

2.3.3. Исследование свойств СМАА (КК) и (К) при решении распределительных задач с качественной неоднородностью.

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.2.4. Исследование зависимости относительного улучшения точности СМАА без возвратов в сравнении с алгоритмом ПЗ от изменения параметров задачи.

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

3.3.1. Возможность решения неоднородной распределительной задачи генетическим алгоритмом.

3.3.2. Исследование ЭГА при решении неоднородной распределительной задачи.

3.3.3. Описание перспективной области значений параметров ЭГА.

3.3.4. Решение неоднородной распределительной задачи ЭГА.

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

3.4.1. Организация вычислительного эксперимента.

3.4.2. Результаты вычислительного эксперимента.

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

4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ

РЕШЕНИЯ НЕОДНОРОДНЫХ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ.

4.1. Вычислительный эксперимент и требования к программному обеспечению.

4.1.1. Требования к программному обеспечению.

4.1.2. Концептуальная схема функционирования программного обеспечения.

4.1.3. Объектно-ориентированная модель реализации ПО.

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

4.2.1. Использование базы данных.

4.2.2. Концептуальная модель объекта хранения и функциональные зависимости.

4.2.3. Реляционные выражения и таблицы базы данных.

4.3. Интерфейс взаимодействия с пользователем.

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

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

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

Основной характеристикой распределительной системы является однородность системы используемых устройств относительно выполняемых работ. Оптимальное решение неоднородной распределительной задачи чрезвычайно сложно даже для современных вычислительных систем, особенно при использовании точных методов решения. Применение таких методов для неоднородной распределительной задачи при её большой 5 размерности оказывается неэффективным, т.к. её КР-полнота приводит к недостижимости оптимального решения [14]. Повышение эффективности методов точного решения позволяет повысить размерность задач, для которых оказывается возможным получать решения за доступное время.

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

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

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

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

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

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

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

4. исследование и реализация возможностей параметрической оптимизации качества работы ЭГА применительно к изучаемой области неоднородных распределительных задач;

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

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

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

2. Разработана списочная модификация точного алгоритма Алексеева с применением качественно-количественной оценки неоднородности и избирательности матрицы загрузки для распределительных задач с качественной неоднородностью. Данная модификация позволяет значительно (не менее чем на 30%) уменьшить время поиска оптимального решения и расширить размерность задач (не менее чем на 20%), решение которых можно найти за приемлемое время.

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

4. Получено доказательство применимости эволюционно-генетической модели к неоднородным распределительным задачам с соответствующей критериальной доработкой, и выполнена оптимизация параметров ее настроек для решения неоднородных распределительных задач на основании статистически представительной выборки объёмом не менее 25 тыс. опытов, что дало повышение доверительной вероятности оптимального решения для исследуемого диапазона параметров задачи более 80%.

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

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

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

При реализации программного средства «Система вычислительных исследований неоднородной распределительной задачи «РтсГМечуМеШос!» применялись концепции объектно-ориентированного программирования и реляционных баз данных.

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

Практически значимыми эффектами применения результатов диссертационных исследований являются существенное (10-30%) снижение времени решения неоднородных и распределительных задач точными алгоритмами; существенное (16%) • повышение точности решения неоднородных и распределительных задач приближёнными алгоритмами; введение в практику решения неоднородных распределительных задач предметно оптимизированных эволюционно-генетических алгоритмов. Кроме того, работа дала хорошее практическое приложение в учебном процессе, т.к. предложенные решения позволяют изучать на практике задачи теории расписаний. Автором опубликованы методические указания по теме «Теория расписаний» (см. список публикаций) для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование», «Теория принятия решений», «Теория оптимизации».

Разработанное для исследований программное обеспечение «Система вычислительных исследований неоднородной распределительной задачи «РтсШелуМеШос!», с помощью которого осуществлялось автоматизированное проведение имитационных экспериментов, прошло официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2008613599 от 28.07.2008).

Основное содержание работы

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

Анализ источников литературы по теории расписаний позволил выделить статическую неоднородную распределительную задачу в качестве объекта исследования, вследствие того, что данная задача относится к задачам календарного планирования и является КР полной. Существующие точные методы ограничены сравнительно узкой областью размерностей задач их возможного применения, а приближенные методы позволяют решать распределительные задачи с некоторой погрешностью, иногда превосходящей 30%.

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

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

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

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

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

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

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

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

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

Для построенной эволюционно-генетической модели разработана методика проведения параметрической оптимизации ее настроек.

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

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

В заключении сформулированы основные выводы и результаты диссертационной работы.

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

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

2. Применение разработанного программного обеспечение для исследования алгоритмов решения неоднородных распределительных задач позволило провести множество численных экспериментов и получить сведения, необходимые для анализа эффективности рассматриваемых алгоритмов. Суммарное число опытов превысило 105.

ЗАКЛЮЧЕНИЕ

1. Точное решение неоднородной распределительной задачи теории расписаний является значимым для многих практических задач, и зачастую погрешность от методов приближенного решения не может быть приемлема. Применение СМ АА для поиска точного решения неоднородной распределительной задачи как количественной, так и качественной (для задачи с качественной неоднородностью применение СМ АА с качественно-количественным учетом избирательности) позволяет повысить эффективность нахождения точного решения не менее чем на 10-30%, и расширить область размерностей задач (не менее чем на 5%), для которых точное решение может быть найдено за приемлемые временные сроки.

2. Однако, возможность получения точного решения для задач большой размерности в силу КР полноты исследуемой задачи остается недостижимым в приемлемые временные сроки. В этом случае необходимость в решении практических задач теории расписаний большой размерности приводит к неизбежности использования приближенных методов решения, среди которых можно выделить СМ АА без возвратов и эволюционно-генетический алгоритм, адаптированный для неоднородной распределительной задачи. Причем СМ АА без возвратов позволяет получать приемлемое по точности решение и лучшее от 4% -16%, в зависимости от степени однородности значений матрицы вычислительной сложности, если сравнивать с алгоритмом Плотникова-Зверева. А в сравнении с эволюционно-генетическим алгоритмом эффект выигрыша по качеству решения для СМ АА без возвратов наблюдается для задач большой размерности, причем временные затраты на поиск решения незначительны, к примеру для задачи размерности п=10, т=899 время решения не превышает одной секунды.

3. ЭГА также показал эффективность применения его для решения неоднородной распределительной задачи, но в большей степени для случая двухприборной задачи. Исследования с использованием полнофакторного анализа позволили параметрически оптимизировать ЭГА для исследуемого в работе набора исходных параметров решаемой неоднородной распределительной задачи. Были получены более эффективные, по сравнению с рекомендуемыми в научной литературе по ЭГА, параметры, позволившие повысить точностные показатели при решении двухприборной распределительной задачи п=2, т=45 в 2,57 раза. Причем точность решения эволюционно-генетическим алгоритмом двухприборной неоднородной распределительной задачи выше, чем для решения этой же задачи, но СМ АА без возвратов или алгоритм Плотникова-Зверева. ЭГА минимум с 80% вероятностью позволяет получить точное решение задач п=2, т=45.

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

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

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

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

2. Айра Пол Объектно-ориентированное программирование на С++ — М.:Бином, 2001.-464 с.

3. Алексеев В.Ю. Комплексное применение методов дискретной оптимизации. М.: Наука, 1987 - 247с.

4. Ахназарова С.Л. Оптимизация эксперимента в химии и химической технологии / Ахназарова С.Л., Кафаров B.B. М.: Высшая школа, 1978.-319 с.

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

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

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

8. Будиловский Д.М. Анализ эффективности генетического алгоритма при решении задач теории расписаний большой размерности/ Будиловский Д.М., Кобак В.Г. Ростов-на-Дону: Издательство ДГТУ, 2007, 131-134с.

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

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

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

12. Гладков JI. А. Генетические алгоритмы/JI. А. Гладков, В. В. Курейчик В. М. Курейчик М.: ФИЗМАТ ЛИТ, 2006.-320с

13. Глушков В. М., Капитонова Ю. В., Летичевский А. А., Горлач С. П. Макроконвейерные вычисления функций над структурами данных -Кибернетика, 1981, № 4, 13 21 с.

14. Глушков В. М., Молчанов И. Н. О некоторых проблемах решения задач на ЭВМ с параллельной организацией вычислений Кибернетика, 1981, №4, 82-88 с.

15. Головкин Б.А. Параллельные вычислительные системы. М. : Энергия, 1980.

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

17. Дейт К. Введение в системы баз данных. М.: Диалектика, 1998. 784 с.

18. Джексон Г. Проектирование реляционных баз данных для использования с микро-ЭВМ М.: Мир, 1991. - 252 с.

19. Джон Макгрейтор, Девис Сайке Тестирование объектноориентированноных программ М.: ДиаСофт, 2002. - 417 с.

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

21. Еремеев A.B. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000

22. Ермаков С.М. Математическая теория оптимального эксперимента: учебное пособие / Ермаков С.М., Жиглявский A.A. М.:Наука, 1987. -320с.

23. Жак C.B. О методах решения задач, сочетающих эвристики и случайный выбор -М.: Кибернетика, 1972. №1 - с. 119-121.

24. Жак C.B. Приближенный метод выбора оптимальной системы сельскохозяйственных машин// Математические модели и методы оптимального планирования Новосибирск: Наука,1966. - с.255-162.

25. Задачи календарного планирования. Часть 1-2. // http://Math.nsc.ru/lbrt/k5/lec6.pdf

26. Ивоботенко Б.А. Планирование эксперимента в электромеханике /

27. Ивоботенко Б.А., Ильинский Н.Ф., Копылов И.П. М.:Наука, 1975. -184с.

28. Клемент Р. «Генетические алгоритмы: почему они работают? Когда их применять?», Компьютерра, №289, 1999, 20-23 с.

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

30. Кобак В. Г. Сравнительный анализ алгоритмов решения минимакс-ной задачи в однородных системах/ Кобак В. Г., Федоров С.Е./

31. Математические мето-ды в технике и техно-логиях ММТТ-16: сб. тр.169

32. XVI Междунар. на-уч. конф. / РГАСХМ.-Ростов н/Д, 2003. Т. 8, секц.12

33. Кобак В.Г. Определение оптимального значения критерия равномерности по оптимальному минимаксному критерию для однородных трехприборных систем (статья)// Электровозостроение: сб. науч. тр. Новочеркасск, 2002.- Т.44.

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

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

36. Корнеев В.В. Параллельные вычислительные системы/В.В Корнеев.-М.:Нолидж. 1999. 311 с.

37. Корнеев В.В. Современные микропроцессоры/В.В. Корнеев, А.В Киселев. М:Нолидж. - 1998. - 237 с.

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

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

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

41. Красный Д.Г. Анализ эффективности модифицированного алгоритма Алексеева приблеженного решения неоднородной распределительной задачи//«Системный анализ, управление и обработка информации» -Ростов-на-Дону: Издательство ДГТУ, 2007, 126-130 с.

42. Красный Д.Г. Официальная регистрация программы для ЭВМ ФГУ ФИПС «Система вычислительных исследований неоднородной распределительной задачи» // Нейдорф P.A., Кобак В. Г. // №2008613599 от 28.07.2008 г.

43. Красный Д.Г. Решение минимаксных задач в неоднородной среде избирательно работающих устройств модифицированным алгоритмом Алексеева// Вестник ДГТУ Ростов н/Д, 2007.- №4, Т.7. - С. 395-401170

44. Красовский Д.В., Фуругян М.Г. Комплексное применение методов дискретной оптимизации при решении задач минимаксной теории расписаний // МФТИ М., «Моделирование и обработка информации» -2003, 96-103 с.

45. Кузьменко В.М. Анализ современных методов искусственного интеллекта применительно к задачам календарного планирования единичного производства/ Кузьменко В.М., Таран C.B. Вестник Донбасской государственной машиностроительной академии, 2006 №1.

46. Курейчик В.М. Генетические алгоритмы, В.М. Курейчик, В.В. Курейчик, Л.А Гайдуков. -М.:ФИЗМАТЛИТ, 2006. 320 с.

47. Курейчик В.М., Родзин СИ. Эволюционные алгоритмы: генетическое программирование // Известия АН. Сер.: Теория и системы управления. 2002. —№1. - с. 127-137.

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

49. М. Мину. Математическое программирование. Теория и алгоритмы.-М.: Наука, 1990.

50. Мейер М. Теория реляционных баз данных М.Мир, 1987. - 608 с.

51. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации в дискретных сетевых задачах оптимального распределения ресурсов. -М.: Наука, 1983.

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

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

54. Нейдорф P.A. Точное решение неоднородной распределительной задачи модификацией алгоритма Алексеева//Р.А.Нейдорф, В.Г. Кобак, Д.Г. Красный Известия высших учебных заведений. СевероКавказский регион./Новочеркасск, 2008. №1. с. 17-22.

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

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

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

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

59. Плотников В.Н. Методы быстрого распределения алгоритмов в вычислительных системах./ В.Н. Плотников, В.Ю. Зверев Техническая кибернетика №3 М., 1974, 136- 143с.

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

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

62. Пупков К.А. Оценка и планирование эксперимента / Пупков К.А., Костюк Г.А. М.Машиностроение, 1977. 118с.

63. Растригин JI. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3-16.

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

65. Рутковская Д., Пилиньский М., Рутковский JI. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польского И.Д. Рудинский. М.: Горячая линия - Телеком, 2006 - 452 с.

66. Севастьянов C.B. Введение в теорию расписаний — Новосибирск, 2003, 173 с.

67. Сергиенко И. В., Лебедева Т. Т., Рощин В. А. Приближенные методы решения дискретных задач оптимизации Киев: Наукова думка, 1980. -276 с.

68. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач оптимизации Киев: Наукова думка, 1981.

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

70. Танаев B.C. Теория расписаний. -М.: Знание, 1988, 32 с.

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

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

73. Taxa, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. -М.: "Вильяме", 2005, 902 с.

74. Ульман Д. Базы данных на паскале. М.: Машиностроение, 1990. 386 с.

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

76. Федоров В.В. Теория оптимального эксперимента (планирование регрессионных экспериментов) / Федоров В.В. М.:Наука, 1971, 312с.

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

78. Хартман К. Планирование эксперимента в исследовании технологических процессов / Хартман, Э.Лецкий, В.Шефер и др-М.:Наука, 1977, 552с.

79. Эммерих В. Конструирование распределенных объектов. М.: Мир, 2001.-512 с.

80. Aarts Е. Local Serch in Combinatorial Optimization / E. Aarts, J.K. Lenstra John Wiley & Sons, 1997.

81. Blickle Т., Thiele L. A Comparison of Selection Schemes used in Genetic Algorithm /Т. Blickle, L. Thiele.-TIK-Report,1995.

82. Brucker P. Scheduling Algorithms/P. Brucker.- Springer, 2001

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

84. E.S.H. Hou, N. Ansari, H. Ren, «А Genetic Algorithm for Multiprocessor Scheduling» IEEE Transactions on Parallel and Distributed Systems, vol. 05, no. 2, pp. 113-120, Feb., 1994.

85. Gantt H.L. ASME Transactions, 1903, 24,- P. 1322-1336.

86. Goldberg D. E. Genetic algorithms in search, optimization, and machine learning. Reading, MA: Addison-Wesley. 1989.

87. Holland J. H. Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press. 1975.

88. Jackson J.R. Scheduling a production line to minimize maximum tardiness// Los Angeles, CA: University of California, 1955.- Manag. Sci. Res. Project. Research Report N 43.

89. Johnson S.M. Optimal two- and three-stage production schedules with setup times included// Naval Res. Logistics Quat.- 1954,- V. 1. P. 61 68.

90. Koza J.R. Genetic Programming.- Cambridge/MA:MIT Press, 1992.

91. Land A.H. An automatic method of solving discrete programming problems/ A.H. Land, A.G. Doig Econometrica. V28, 1960.

92. Michafewicz Z., Genetic Algorithm + Data Structures = Evolution Programs, Springer-verlag,1992

93. Mitchell M. An Introduction to Genetic Algorithms. Cambridge: MIT Press, 1996.

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

95. P. Björn-Jorgensen, J. Madsen, "Critical path driven cosynthesis for heterogeneous target architectures," codes, p. 15, 5th International Workshop on Hardware/Software Co-Design (Codes/CASHE "97), 1997.

96. S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983.

97. Sawada J. A Fast Algorithm to generate Beckett-Gray codes//Electronic notes in Discrete Mathematics (EuroComb 2007),2007lOl.Silvano Martello, Paolo Toth Knapsack Problem Algorithms and Computer Implementations// University of Bologna 1990.

98. Whitley D. A Genetic Algorithm Tutorial/D. Whitley D.-1993.

99. Whitley D.,Schedulong Problems and Traveling Saleman: the Genetic Edge Recombination Operator/D. Whitley, T. Starkweather, D. Fuduay // Proc. of 3d Int. Conf. on GA, 1989.