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

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

003177597

БУДИЛОВСКИЙ ДМИТРИЙ МИХАЙЛОВИЧ

ОПТИМИЗАЦИЯ РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИИ НА ОСНОВЕ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКОЙ МОДЕЛИ РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ

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

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

2 7 ДЕК 2007

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

003177597

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

д т н, профессор Р А Нейдорф

д т н., профессор В.М. Курейчик д т.н , профессор В.А Фатхи

Северо-кавказский филиал Московского технического университета связи и информатики Защита состоится « декабря 2007 года в « t?'-0^ » на заседании диссертационного совета Д 212 058 04 Донского государственного технического университета по адресу

344010, г Ростов-на-Дону, пл Гагарина, 1 ДГТУ а. № 252 С диссертацией можно ознакомиться в библиотеке Донского государственного технического университета

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

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

Научный руководитель-

Официальные оппоненты.

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

АД Лукьянов

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

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

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

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

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

1 разработка, обоснование и исследование эволюционно-генетической модели (ЭГМ) распределительной задача" (РЗ) теории расписаний,

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

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

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

Существенные научные результаты, полученные в диссертации:

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

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

3 найденная по этой методике область эффективных значений параметров системы «РЗ-ЭГА», обеспечивающих максимальную доверительную вероятность получения оптимального решения в диапазоне параметров РЗ п = 3 (число исполнителей) и т = 17 -25 (число работ), (и = 4 и /и = 17-19), а также я = 5 и т = 17

4 имитационно-статистический подход к параметрической оценке доверительной вероятности определения оптимального решения РЗ и методика его реализации*.

5 найденные по этой методике доверительные значения количества параллельных опытов по оценке с помощью ЭГА величины оптимума решения РЗ, обеспечивающих заданную вероятность достоверности результата® в диапазоне параметров РЗ п = 3 (число исполни-

® Так, для параметров РЗ п = 3 и т = 17 получена оценка нижней границы точности р = 0,76 при следующих параметрах модели ЭГА. Р„„„ = 0,41, />„„„,,„ = 0,07 , Р_, = 1, Мш = 1050 , NсЬ) = 50

® Иными словами, для заданных параметров РЗ и и и может быть

получено необходимое количество параллельных опытов г , результат применения которых к данной РЗ даст оценку значения ее оптимального решения £7''" с заданной вероятностью р (например, 0,99 или 0,99999)

телей) и т-П-25 (число работ), (и = 4и т = 17-19), а также п = 5 и т —17

Научная новизна существенных результатов диссертации

определяется следующими отличительными признаками:

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

2 параметры области настроечных значений ЭГА, обеспечивающих максимальную доверительную вероятность нахождения оптимального решения РЗ, значительно отличаются от рекомендованных в литературе теории и практике применения ГА, так вероятность мутации особи составила Р„„ =0,41 вместо рекомендуемых />„„„ =0,1, вероятность мутации бита в гене РтшЬи - 0,07 вместо рекомендуемых РтиЛи = 0,1, вероятность участии особи в кроссовере Ра,к,оге, = 1 вместо рекомендуемых Раоштя =0,9 (при этом для параметров РЗ п = 3 и от = 17 выигрыш по нижней оценке точности составил ртт / рху<) = 13

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

4 разработанная методика оценки оптимального решения с наперед заданной доверительной вероятностью обеспечивает возможность применении ЭГА в качестве эталонного метода при работе с задачами большой размерности, что дает большой выигрыш по ресурсам решения сравнительных задач, так исследования показали, что для получения оптимального решения, с доверительной вероятностью Р(Ш - 0,9999 (при числе исполнителей п = 3 , числе работ т = 17 ) необходим запуск всего 2 = 7 параллельных ЭГА

Методы исследования. В диссертации применялись методы исследования операций, в частности, методы теории расписаний и методы статического анализа. При реализации имитационных исследований и построения программного средства «Система для проведения исследований в области задач построения расписаний» («Рго]ес±5Иес1и1ег») использовались методы объектно-ориентированного программирования и нормализации баз данных

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

Объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил не менее 106 опытов Программное средство «Система для проведения исследований в области задач построения расписаний» («Ргс^ейБИесМег») на котором осуществлялось автоматизированное проведение имитационных экспериментов прошло официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство №2007612127 (роспатент) от 23 05.2007).

Практическая значимость диссертационной работы определяется несколькими составляющими-

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

2. разработанный и апробированный метод параметрической оптимизации позволяет определить близкую к оптимальным область параметров модели ЭГА, гарантирующую эффективное решение РЗ в диапазоне ее важнейших параметров (в работе исследовались области п = 3 (число исполнителей) и т - 17 - 25 (число работ), (п = 4 и т = \1 -19), а также п = 5 и т = 17 ),

3 разработанная и апробированная методика параллельного запуска ГА с доверительным количеством запусков г дает исследователю возможность получать оценки оптимумов и близкие к оптимальным решения в тех областях параметров РЗ, где невозможно использование точных методов;

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

5 разработанное программное средство «РгозеЛБИесМег» показало себя эффективным инструментом решения и исследования РЗ и подтвердило возможность эффективной реализации предложенной ЭГМ на современном аппаратно-программном комплексе,

6 «Рго]ес±5Ьес1и!ег» позволяет производить оценку ЭГМ при различных параметрах системы «РЗ-ЭГА», обеспечивает легкую расширяемость функциональных возможностей, позволяет добавление новых модификаций моделей ЭГА или других методов

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

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

Апробация диссертационной работы. Материалы диссертационной работы апробировались на двух международных научных конференциях XIX Международная научная конференция "Математические методы в технике и технологиях" ММТТ-19 (ВГТА, Воронеж, 2006) и XX Международная научная конференция "Математические методы в технике и технологиях" ММТТ-20 (ЯГ-ТУ, Ярославль, 2007) Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета

Публикации по теме диссертационной работы. Всего по теме диссертационных исследований опубликовано 10 работ, в которых освещены наиболее существенные ее результаты Одна работа опубликована в центральной печати, в журнале "Вестник ДГТУ" Большая часть работ опубликована в сборниках научных трудов международных конференций ММТТ-19, ММТТ-20.

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

Первая глава диссертации посвящена обзору существующих методов решения РЗ теории расписаний Методы классифицированы по свойственным им точностным и временным характеристикам Показано, что для решения задач реальной размерности необходимо применение приближенных методов, наиболее гибкими из которых являются методы класса ЭГА Для диссертационного исследования из всех задач теории расписаний выделен класс однородных задач (в англоязычных изданиях - «open shop»), в которых нет ограничений на порядок выполнения работ, и каждая работа состоит только из одной операции

Таким образом, для исследования выбрана система, состоящая из п несвязанных идентичных исполнителей Р = {,, р2 >•••> Р „ } На обслуживание поступает множество S = {s, 11 = 1, т} независимых параллельных

работ Известен объем ресурса, необходимого t, для выполнения работы исполнителем.

Задача составления расписания сводится к разбиению исходного множества работ S на п непересекающихся подмножеств, т е

(jS^S, (1)

j=1

где S - исходное множество работ, п - число исполнителей, т -число работ

Задача оптимизации загрузки исполнителей реализуется на основе минимаксного критерия, который определяется следующим выражением:

Qmm = max {г,: j = l,n}-> min (2)

где T = " общая оценка загрузки j -го исполнителя выполнением

ке!1

назначенных для него т} работ; Ij = {l,q, ..}. (/ ^q)&{l,q,. .е {l,т}), k{Ij)~ т], а к() мощность множества индексов /.

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

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

2. исследовать взаимосвязь точностных и временных эксплуатационных характеристик ЭГМ в зависимости от параметров системы «РЗ-ЭГА»;

3 разработать механизм статистического анализа точностных и временных характеристик модели и с помощью него провести параметрическую оптимизацию модели,

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

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

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

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

X = = {рп,},<32 = {рп= {рщ},...,в,,, = {/?«„,}}, (3)

где О - ген, -порядковый номер исполнителя, на который назначена работа, номер исполнителя кодирован числом размером м> бит.

Для РЗ, рассматриваемых в данной диссертации, решение может быть полностью представлено кодированием одной хромосомы для особи. При этом размер хромосомы имеет линейную зависимость от числа работ яйео/"(ЛГ) = т* м>/8 и логарифмическую от числа исполнителей w = \\og(n)l\og(2)\ + \ . В связи с тем, что номер исполнителя кодируется избыточностью, кратной байту, раскодирование осуществляется с помощью линейного закона вида А = 2'"/и, где А - величина ]-го интервала, по которому значение гена преобразуется в номер исполнителя. Границы .¡-го интервала определяются следующей формулой:

Д/ = [0'-1)*А,у*Л1, где ) - номер исполнителя; А] - диапазон, из которого значение гена преобразуется в номер] исполнителя.

Побитовое представление операторов ЭГА позволяет исполнять их без

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

преобразования и анализа генетических характеристик легко реализуются на любом современном аппаратно-программном комплексе.

В заключение второй главы приведены данные об исследовании эффективности применения ЭГА на основе пооитовои генетической модели. I |ри этом для РЗ малой размерности с помощью полного перебора получено косвенное подтверждение эвристической гипотезы о том, что эффективность ЭГА может объясняться расположения большинства решений РЗ в области значений, близких к оптимальным (рис.1), т.е. наличием нескольких «плато», содержащих локальные «субоптимальные» экстремумы.

Третья глава посвящена статистическому анализу и параметрической оптимизации характеристик системы «РЗ-ЭГА».

700 800 • л 500 • 1т С 2 СО $ 100 • 3.15.125-301

40? 33(1 ООО 273 243 227 207 ■Пи*; 195 163 139

Рис. 1. Пространство поиска решения

При решении РЗ с фиксированными параметрами ЭГА дает довольно большой разброс значений оценок оптимума. Поэтому для анализа его точностных характеристик введена величина = у"""' /V, где у"'"" - число опытов с полученным точным решением, V - общее число опытов, которая представляет собой частоту наступления положительных событий - нахождений оптимума. Она является экспериментальной оценкой вероятности правильной оценки оптимума р для исследуемой системы «РЗ-ЭГА». Чем ближе величина р к 1,

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

Для получения оценки ртЫ использовался итеративный поиск по случайным распределениям с фиксацией нижней границы и проверкой точного решения алгоритмом МВГ (рис.2). Факт смены нижнего предела рассматривался как самостоятельное случайное событие с, а порогом остановки являлось ограничение (я, +\)/(па +1) < Р , где пх- число смен границы и п0 - число опытов

(рис. 3.). Например, для области параметров РЗ: п = 3 , т - 17 при диапазоне работ [25..30], с использованием ограничения Рщтт =0,001, зафиксировано наихудшее значение р3 - РтЫ = 0,06.

Рис. 3. Вероятность Рб

50 40 30 20 10 0

Поиск рггап

1 4001 8001

N распределения

Рис. 2. Поиск Ртю

Вероятность Рб

1.000 -1

2 0.100

0.001

1 4001 8001 N распределения

С помощью поэтапной оптимизации исследуемой системы «РЗ-ЭГА» данное значение было существенно улучшено и составило р = 0,78 при значениях

параметров ЭГА значительно отличающегося от рекомендуемых в литературе (например уровень мутации особи составила Рпш =0,41

вместо рекомендуемых РтШ = 0,1, а вероятность мутации бита в гене осталась близкой к рекомендуемому РтшЫ, = 0,1 и

составила Р1тМ1 = 0,07, несколько сместилась также вероятность кроссовера РСГ(ШЮСГ = 1 вместо Рсттг = 0,9).

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

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

Четвертая глава посвящена исследованиям по обоснованию и реализации предложенной в работе схемы получения точного решения РЗ с заданной доверительной вероятностью использованием некоторого числа параллельных запусков ЭГА. Имея вероятность получения точного решения р можно получить оценку минимального числа необходимых опытов УУ3 (параллельных запусков ЭГА) по формуле И'т{„ = 1п(^„)/ 1п(1 - р). Такое количество ЭГА, повторенных для исследуемой РЗ, необходимо для того, чтобы с заданной вероятностью РЛт получить точное решение хотя бы в одном из опытов. Число необходимых опытов для размерности РЗ /7 = 3 т ~\1 при диапазоне весов работ ¡25..30] приведено в таблице 1.

Число необходимых параллельных опытов

Таблица 1

■*1ШП [*«.» 1

0,05 1,9785 2

0,01 3,0415 4

0,005 3,4993 4

0,001 4,5622 5

0,0005 5,0200 6

0,0001 1 6,0829 7

16 17 18 19 20 21 22 23 2А Число эадач

Рис. 4. Влияние кратности

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

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

Алгоритмы

Матрица весов

> Опыт

Загрузка из БД ;

Критерий оптимиз.

-»[ Расчет

Расписание L

Генерация опытов

Экспорт ; результатов

Просмотр

I Сохранение в БД

Рис. 5. Концептуальная модель объектов ПС

модействия представлена на рис 5. Программное средство (ПС) выполнено по объектно-ориентированной парадигме на языке Object Pascal в среде Turbo Delphi. Система «Project-Sheduler» обладает разделенной структурой методов и объектов представления РЗ теории расписаний, что обеспечивают простую модификацию параметров ЭГМ или добавления новых методов решения. Система не требовательна к ресурсам, может быть запущена на любом ПК с установленной ОС Windows 2000 и выше. Конкретные показатели потребления аппаратных ресурсов напрямую зави-

V Л.

I»« 1......

Рис. б. Интерфейс главной формы системы ProjectSheduler

сят от размерности РЗ и количества введенных экспериментов Пользователю предлагается удобная система управления созданным им же набором экспериментов, с возможностью модификации параметров алгоритмов и просмотром результатов вычислений в реальном времени Предусмотрен также гибкий механизм экспорта-импорта данных в другое ПО Общее представление об интерфейсе «Рго^сКЬесМег» можно получить на рис б, где представлена главная форма приложения

ЗАКЛЮЧЕНИЕ

1 Необходимость в решении практических задач теории расписаний большой размерности приводит к неизбежности использования приближенных методов решения, среди которых признанным лидером является класс методов, основанных на эволюционно-генетическом подходе Чрезвычайная чувствительность свойств ЭГА к его предметной основе, структуре и параметрам вызвала необходимость построения специальной побитовой эволюционно-генетической модели, которая показала эффективность и возможность практического применения вероятностно-эвристических методов для решения распределительных задач с получением результатов, близких к оптимальным и при незначительных, по сравнению с МВГ, временных затратах

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

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

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

Таким образом, цель диссертационного исследования достигнута

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

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

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

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

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

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

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

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

6 Методы получения расписаний для однородных систем обработки информации, метод указания к лабораторным занятиям для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование»/ ДГТУ. Каф "ПОВТиАС", Сост В.Г Кобак, Д М. Будиловский - Ростов н/Д, 2007 -Юс

7 Свидетельство об официальной регистрации программ для ЭВМ № 2007612127 Российская Федерация Система для проведения исследований в области задач построения расписаний/ РА Нейдорф, Д M Будиловский, В Г Кобак.-2007611215; заявл 04.04 2007; зарег 23 05.2007

8. Будиловский Д М Анализ эффективности генетического алгоритма при решении задач теории расписаний большой размерности/ Д М Будиловский, В Г. Кобак// меж, вуз. сб. Системный анализ, обработка информация, управление - Ростов н/Д, 2007.

9. Будиловский Д.М Влияние структуры и параметров генетического алгоритма на эффективность решения минимаксных задач/Д М Будиловский, Р А Нейдорф// меж вуз сб Системный анализ, обработка информация, управление - Ростов н/Д, 2007

10 Использование генетического алгоритма при оценке точности решения однородной минимаксной задачи метод указания к лабораторным занятиям для дисциплин «Алгоритмические языки и программирование», «Вычислительная техника и программирование»/ ДГТУ Каф "ПОВТиАС", Сост Д М Будиловский - Ростов н/Д, 2007.-10с.

В набор 23 11 2007 В печать 26 11 2007

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

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

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

введение.

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

1.1. параллельное упорядочивание как важнейший этап составления расписаний.

1.2. Математическое описание задачи параллельного упорядочивания.

1.2.1. Работы и операции при составлении расписаний.

1.2.2. Критерии составления расписаний.

1.2.3. Характеристика и функциональная классификация задач теории расписаний.

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

1.3. Основные аспекты выбора методов решения задач теории расписаний.

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

1.4.1. Целочисленное линейное программирование.

1.4.2. Методы ветвей и границ. Заполнение работ по устройствам.

1.4.3. Методы ветвей и границ. Заполнение устройств по работам.

1.4.4. Приближенные методы списочного составления расписаний. Алгоритм критического пути.

1.4.5. Возможности и сферы применения детерминированных методов.

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

1.5.1. Предпосылки появления приближенных вероятностных и эвристических методов.

1.5.2. Комбинаторно-эвристический поиск.

1.5.3. Методы отжига.

1.5.4. Метод роящихся частиц (particle swarm).

1.5.5. Табуированный поиск (Tabu Search).

1.5.6. Эволюционно-генетический подход.

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

1.6.1. Общая характеристика эволюционно генетического подхода.

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

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

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

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

1.6.6. Модели ЭГА.

1.6.7. Некоторые обобщения.

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

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

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

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

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

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

2.1. Побитовая генетическая модель распределительной задачи.

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

2.1.2. Модель гена распределительной задачи теории расписаний.

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

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

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

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

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

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

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

2.3.1. Итерационный процесс поиска ЭГА.

2.3.2. Пример организации итерационного поиска в ЭГА.

2.3.3. Особенности системы поиска эволюционного алгоритма.

2.4. Сравнительный анализ примеров решений. распределительной задачи эвристическими алгоритмами.

2.4.1. Задачи и алгоритмы для сравнения.

2.4.2. Решение задачи эволюционно-генетическим алгоритмом.

2.4.3. Решение задачи методом отэ/сига.

2.4.4. Решение задачи методом роящихся частиц.

2.4.5. Сравнительная оценка результатов применения к РЗ различных методов и алгоритмов решения.

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

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

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

3. исследование эволюционной генетической модели распределительной задачи.

3.1. Система «РЗ-ЭГА», задачи и методы её исследования.

3.2. Исследование свойств «РЗ-ЭГА» для 2-х устройств.

3.2.1. Исследование точностных показателей.

3.2.2. Исследование показателей быстродействия.

3.2.3. О перспективных направлениях дальнейших исследований системы «РЗ-ЭГА».

3.3. Некоторые результаты исследования свойств системы «РЗ-ЭГА» для 3-х устройств

3.3.1. Исследование нестабильности ЭГА для 3-х устройств.

3.3.2. Предварительные выводы о нестабильности ЭГА.

3.4. Исследование влияния параметров ЭГА на вероятностную точность решения РЗ

3.4.1. Постановка задачи исследования.

3.4.2. Широкодиапазонное исследование 4-х факторного пространства ЭГА.

3.4.3. Исследование найденного перспективного диапазона факторного пространства.

3.4.4. Реализация стратегии крутого восхождения для отыскания области экстремума

3.4.5. Исследование подозрительного на экстремум диапазона.

3.4.6. Градиентный поиск в экстремальной области по факторам X ^ и X2 .//

3.4.7. Детальное исследование предполагаемой экстремальной области.

3.4.8. Эксперимент по проверке экстремальной области.

3.5. Влияние весов работ в распределении на степень точности ЭГА.

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

3.6.1. Исследование показателей системы «РЗ-ЭГА» для двух устройств.

3.6.2. Исследование показателей системы «РЗ-ЭГА» для трех устройств.

3.6.3. Исследование показателей системы «РЗ-ЭГА» в зависимости от распределения весов работ

4. исследование феномена вероятностной точности решения распределительной задачи при использовании эга.

4.1. Теоретико-экспериментальное обоснование оценки эффективности ЭГА вероятностной то чностью.

4.1.1. Теоретические предпосылки оценки эффективности ЭГА вероятностной точностью

4.1.2. Экспериментальное исследование влияния кол-ва заданий на эффективность ЭГА

4.1.3. Исследование стабильности работы ЭГА.

4.1.4. Поиск наихудших распределений для ЭГА.

4.2. Имитационно-статистический подход к оценке оптимальности решения ЭГА.

4.2.1. Исследование распределительной задачи «РЗ-ЭГА» на наличие закономерностей формирования вероятностной точности.

4.2.2. Теоретические основы оценки заданных вероятностно точностных условий решения РЗ

4.2.3. Предельная ресурсная оценка решения РЗ параллельными ЭГА.

4.3. Исследование быстродействия применения пакетной обработки.

4.3.1. Предпосылки нестабильности времени выполнения операций ЭГА.

4.3.2. Экспериментальное исследование временных характеристик при фиксированном порядке выполнения ЭГА.

4.3.3. Экспериментальное исследование временных характеристик при свободном порядке выполнения ЭГА.

4.3.4. Методика оценки верхней границы по времени выполнения ЭГА.

4.4. Исследование алгоритма адаптации уровня мутации в процессе решения.

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

5. программный комплекс «projectsheduler» имитационного моделирования решения распределительной задачи.

5.1. Функциональная структура ПК.

5.2. Объектно-ориентированное конструирование функциональных блоков.

5.3. Структура баз данных ПК ProjectSheduler.

5.4. Интерфейс ПК ProjectSheduler и работа с ним.

Задачи теории расписаний имеют не только важное теоретическое значение, как относящееся в основном к классу NP-полных задач, но и получили широкое практическое распространение во множестве инженерных и управленческих задач [41,46,46,67]. Везде, где требуется упорядочить и распределить какие либо ресурсы между агентами (исполнителями), возникает вопрос эффективного планирования. Оптимальность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. Построение оптимального плана распределения может занять даже на современных многопроцессорных системах многие месяцы и годы, при использовании точных методов решения, например, ветвей и границ (МВГ). С другой стороны, сейчас применяемые для таких задач быстрые, но приближенные списочные методы, такие, как метод критического пути (МКП), могут давать большую погрешность, приближающуюся к 30%[46]. Такое отклонение от оптимума в большинстве случаев является неприемлемым. Возникает необходимость в методах, характеризующихся сочетанием противоречивых свойств: полиноминальной зависимостью времени счета от размерности задачи и точностью близкой к оптимальной (по крайне мере значительно лучшей, чем у МКП). К такому классу методов относятся эволюционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных приближенных алгоритмов[26].

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

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

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

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

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

3. исследование возможности применения ЭГА в качестве метода оценки фактического значения оптимума для РЗ большой размерности;

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

Существенные научные результаты, полученные в диссертации:

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

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

3. найденная по этой методике область эффективных значений параметров системы «РЗ-ЭГА», обеспечивающих максимальную доверительную вероятность получения оптимального решения в диапазоне параметров РЗ: п = Ъ (число исполнителей) и m = 17 — 25 (число работ), (п = 4 и т-\1 -19), а также п = 5и т = 17 *;

4. имитационно-статистический подход к параметрической оценке доверительной вероятности определения оптимального решения РЗ и методика его реализации;

5. найденные по этой методике доверительные значения количества параллельных опытов по оценке с помощью ЭГА величины оптимума решения РЗ, обеспечивающих заданную вероятность достоверности результата** в диапазоне параметров РЗ: п = 3 (число исполнителей) и т = П-25 (число работ), {п = 4и т-\1 -19), а также п = 5и т = 17 .

Так, для параметров РЗ п = 3 и т = 11 получена оценка нижней границы точности р = 0,76 при следующих параметрах модели ЭГА: Pmut = 0,4\,Pmutbjt = 0,07, crossover = 1' -^lim = 1050 , Nchr = 50

Иными словами, для заданных параметров РЗ п и т может быть получено необходимое количество параллельных опытов z, результат применения которых к данной РЗ даст оценку значения ее оптимального решения Q"p' с заданной вероятностью Р (например, 0,99 или 0,99999).

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

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

2. параметры области настроечных значений ЭГА, обеспечивающих максимальную доверительную вероятность нахождения оптимального решения РЗ, значительно отличаются от рекомендованных в литературе теории и практике применения ГА, так вероятность мутации особи составила Pmut- 0,41 вместо рекомендуемых Pmut = 0,1, вероятность мутации бита в гене Pmutbit = 0,07 вместо рекомендуемых Pmutbit = 0,1, вероятность участии особи в кроссовере Pcrossover= 1 вместо рекомендуемых Pcrossover = 0,9 (при этом для параметров РЗ п = 3 и т = 17 выигрыш по нижней оценке точности составил ропт1 Рхуд = 13);

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

4. разработанная методика оценки оптимального решения с наперед заданной доверительной вероятностью обеспечивает возможность применении ЭГА в качестве эталонного метода при работе с задачами большой размерности, что дает большой выигрыш по ресурсам решения сравнительных задач, так исследования показали, что для получения оптимального решения, с доверительной вероятностью Рдов= 0,9999 (при числе исполнителейя = з, числе работт = 17) необходим запуск всего z = 1 параллельных ЭГА.

Методы исследования. В диссертации применялись методы исследования операций, в частности, методы теории расписаний и методы статического анализа. При реализации имитационных исследований и построения программного средства «Система для проведения исследований в области задач построения расписаний» («ProjectSheduler») использовались методы объектно-ориентированного программирования и нормализации баз данных.

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

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

2. разработанный и апробированный метод параметрической оптимизации позволяет определить близкую к оптимальным область параметров модели ЭГА, гарантирующую эффективное решение РЗ в диапазоне ее важнейших параметров (в работе исследовались области: п = Ъ (число исполнителей) и т = 17-25 (число работ), (п = 4и т = 17 -19), а также п = 5 и т = 17);

3. разработанная и апробированная методика параллельного запуска ГА с доверительным количеством запусков z дает исследователю возможность получать оценки оптимумов и близкие к оптимальным решения в тех областях параметров РЗ, где невозможно использование точных методов;

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

5. разработанное программное средство «ProjectSheduler» показало себя эффективным инструментом решения и исследования РЗ и подтвердило возможность эффективной реализации предложенной ЭГМ на современном аппаратно-программном комплексе;

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Первая глава диссертации посвящена обзору существующих методов решения РЗ теории расписаний. Методы классифицированы по свойственным им точностным и временным характеристикам. Показано, что для решения задач реальной размерности необходимо применение приближенных методов, наиболее гибкими из которых являются методы класса ЭГА. Для диссертационного исследования из всех задач теории расписаний выделен класс однородных задач (в англоязычных изданиях open shop»), в которых нет ограничений на порядок выполнения работ, и каждая работа состоит только из одной операции.

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

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

2. исследовать взаимосвязь точностных и временных эксплуатационных характеристик ЭГМ в зависимости от параметров системы «РЗ-ЭГА»;

3. разработать механизм статистического анализа точностных и временных характеристик модели и с помощью него провести параметрическую оптимизацию модели;

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

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

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

X = {G\={pni}>G2={pn2},G3={pn3},.,Gm ={рпт}}, (3) где G - ген, рп -порядковый номер исполнителя, на который назначена работа, номер исполнителя кодирован числом размером w6ит.

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

Третья глава посвящена статистическому анализу и параметрической оптимизации характеристик системы «РЗ-ЭГА».

При решении РЗ с фиксированными параметрами ЭГА дает довольно большой разброс значений оценок оптимума. Поэтому для анализа его точностных характеристик введена величина p3=vonm/v, где vonm - число опытов с полученным точным решением, v - общее число опытов, которая представляет собой частоту наступления положительных событий -нахождений оптимума. Она является экспериментальной оценкой вероятности правильной оценки оптимума р для исследуемой системы «РЗ-ЭГА». При этом в пределах ограниченной по размерам выборки испытуемых РЗ, для каждой из этих выборок может быть получено различное значение оценки рэ. Для повышения надежности количественной оценки свойств «РЗ-ЭГА» в работе принято решение об оценке вероятности р по нижней границе значений рэ - pmin.

С помощью поэтапной оптимизации исследуемой системы «РЗ-ЭГА» значение нижней границы было существенно улучшено и составило р = 0,78 (вместо pmin = 0,06 до оптимизации) при значениях параметров ЭГА значительно отличающегося от рекомендуемых в литературе (например уровень мутации особи составила Pmut = 0,41 вместо рекомендуемых Pmut = 0,1, а вероятность мутации бита в гене осталась близкой к рекомендуемому Pmutbit = 0,1 и составила = 0,07, несколько сместилась также вероятность кроссовера Pcrossover =1 вместо Pcrossover = 0,9).

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

Пятая глава диссертации посвящена алгоритмической разработке модели и реализации программного средства автоматизированного проведения имитационного моделирования. Программное средство (ПС) выполнено по объектно-ориентированной парадигме на языке Object Pascal в среде Turbo Delphi. Система «ProjectSheduler» обладает разделенной структурой методов и объектов представления РЗ теории расписаний, что обеспечивают простую модификацию параметров ЭГМ или добавления новых методов решения. Система не требовательна к ресурсам, может быть запущена на любом ПК с установленной ОС Windows 2000 и выше. Конкретные показатели потребления аппаратных ресурсов напрямую зависят от размерности РЗ и количества введенных экспериментов. Пользователю предлагается удобная система управления созданным им же набором экспериментов, с возможностью модификации параметров алгоритмов и просмотром результатов вычислений в реальном времени. Предусмотрен также гибкий механизм экспорта-импорта данных в другое ПО.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

2. Архангельский А. Я. Программирование в Delphi для Windows. Версии 2006, 2007, Turbo Delphi. М.:Бином-Пресс, 2007.-1248с

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

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

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

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

7. Бин Д. XML для проектировщиков. Повторное использование и интеграция/Д.Бин. -М:КУДИЦ-Образ,2004. -256 с.

8. Боггс У. UML и Rational Rose 2002.: Пер. с англ. М.:Лори, 2002. - 510 с.:ил.

9. Большев Л.Н. Таблицы математической статистики / Болынев Л.Н., Смирнов Н.В. М.: Наука. - 416с.

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

11. Гандэрлой М. ADO и ADO. NET. Полное руководство / Гандэрлой М. -М.:Корона, 2003.-912с.

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

13. Гиббонс Д. XML. / Гиббоне Д., Кэгл К., Хантер Э. М: Лори, 2006. -408 с.

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

15. Голицына О.Л. Основы алгоритмизации и программирования / Голицына О.Л., Попов И.И. 2-е изд. - М.: Форум:Инфра-М, 2006. -432 с.

16. Гринченко Н. Н. Проектирование баз данных. СУБД Microsoft Access. Учебное пособие/Н. Н. Гринченко, Е. В. Гусев, Н. П. Макаров. -М.:Горячая Линия Телеком, 2004.-240с

17. Грэхем И. Объектно-ориентированные методы. Принципы и практика: Пер. с англ. М.: Издательский дом «Вильяме», 2004. - 880 с.:ил.

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

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

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

21. Ермаков С.М. Математическая теория оптимального эксперимента: учебное пособие / Ермаков С.М., Жиглявский А.А. М.:Наука, 1987. -320с.29.3латопольский Д. Программирование. Типовые задачи, алгоритмы, методы. -М.:Бином. Лаборатория знаний, 2007.-222с

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

23. Измаилов А.Ф. Численные методы оптимизации / Измаилов А.Ф., Солодов М.В. -М.: Физматлит, 2005. 304с.

24. Касимов А.С. Сокращение объема статистических испытаний, проводимых с целью выявления эффективных эвристических алгоритмов решения задач теории расписаний / Касимов А.С. // Информационное противодействие угрозам терроризма. 2005. - №5. -С. 115-121.

25. Кендалл С. UML Основные концепции.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. - 144 с.:ил.

26. Клемент Росс. Генетические алгоритмы: почему они работают? когда их применять? Компьютерра. 1999. - № 11. - С.71 - 76.

27. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск/Кнут Д. Кнут.—М.: Финансы и статистика, 2002.

28. Кобак В. Г. Соотношение квадратичного и минимаксного оптимальных распределений загрузки однородных трехприборных систем/В. Г.

29. Кобак, Р.А. Нейдорф// Из. вузов, <Электромеханика>, 2005, №3, с. 6065.

30. Кобак В. Г. Сравнительный анализ алгоритмов решения минимаксной задачи в однородных системах/Кобак В. Г., Федоров C.E./Математические методы в технике и технологиях ММТТ-16: сб. тр. XVI Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2003. - Т. 8, секц.12

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

32. Колесов А. Павлова. О. Доступ к данным с помощью технологии ADO / Колесов А. Павлова. О. // КомпьютерПресс. 1999. - №7. - С.71 - 76.

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

34. Кормен Т. Алгоритмы: построение и анализ/Т. Кормен ,4. Лейзерсон, Р. Ривест —М.:МЦНМО, 1999.

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

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

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

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

39. Крамер Г. Математические методы статистики/Г. Крамер .- М.: Регулярная и хаотическая динамика, 2003. 648с.

40. Круг Г.К. Планирование эксперимента в задачах идентификации и экстрополяции / Круг Г.К., Сосулин Ю.А., Фатуев В.А.- М.:Наука, 1977.-206с.

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

42. Кучеренко В. Создание таблиц и OLE-приложений в среде программирования Delphi / Кучеренко В. М.: Познавательная книга плюс, 2000.-192с.51 .Моненко А. Д. Delphi 7 / Моненко А. Д. СПб.: БХВ-Петербург, 2006. -476с.

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

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

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

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

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

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

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

50. Рейнгольд Э. Комбинаторные алгоритмы. (Теория и практика)./Э. Рейнгольд ,Ю. Нивергельт,А. Део.-М.: Мир, 1980.

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

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

53. Соммервилл И. Инженерия программного обеспечения / Соммервил И. 6-е изд. - М.:Издательский дом Вильяме, 2002. - 624 с.

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

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

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

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

58. Фаулер М. UML. Основы.: Пер. с англ./М. Фаулер .- М.:Символ-Плюс, 2006.- 192 с.:ил.

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

60. Флорес И. Структуры и управление данными / Флорес И. -М.:Финансы и статистика, 1982. 319 с.

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

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

63. Шенк X. Теория инженерного эксперимента. / пер. с англ. под ред. Н. П. Бусленко. М.:Мир 1972. - 384с.

64. Chen. В. A review of machine scheduling: Complexity, algorithms and approximability. Handbook of Combinatorial Optimization (Volume 3)/B. Chen, C.N. Potts and G.J. Woeginger.-Kluwer,1998

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

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

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

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

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

70. 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.

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

72. Dai J. G. A fluid heuristic for minimizing makespan in job-shops/J. G. Dai, W. Gideon, // Oper. Res, Georgia Institute of Technology,Atlanta, GA 303320205, USA;

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

74. Eberhart R. C. Computational Intelligence PC Tools/R. C. Eberhart, R. W. Dobbins, P. Simpson, -Boston: Academic Press , 1996.

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

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

77. Fogel, L.J. Artificial Intelligence through Simulated Evolution/ L.J. Fogel,A.J. Owens,M.J. Walsh.-USA:John Wiley, 1966.

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

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

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

81. Handbook of Genetic Algorithms / Edited by Lawrence Davis.— USA, New

82. York: Van Nostrand Reinhold, 1991.197

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

84. Kirkpatrick, S. Optimization by Simulated Annealing-Science 220:671680., 1983

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

86. Koza J.R.Genetic Programming IV: Routine Human-Competitive Machine Intelligence. Berlin: Springer, 2005.

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

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

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

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

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

92. Notation for theoretic scheduling problems Электронный ресурс. / Wikipedia. Режим доступа: http://en.wikipedia.org/wiki/Notationfortheoreticschedulingproblems, свободный. - Загл. с экрана.

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

94. Schwefel H. P. Numerical optimization of computer models/H. P. Schwefel.-Chichester: Wiley, 1981.

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

96. 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.