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

Кобак Валерий Григорьевич

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

МЕТОДОЛОГИЯ СОПОСТАВИТЕЛЬНО-КРИТЕРИАЛЬНОЙ АНАЛИТИЧЕСКОЙ ОЦЕНКИ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ И СРЕДСТВА ЕЕ ПРОГРАММНО-АЛГОРИТМИЧЕСКОЙ ПОДДЕРЖКИ

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

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

АВТОРЕФЕРАТ

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

1 5 Ш 2008

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

003457993

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

Научный консультант: д.т.н., профессор P.A. Нейдорф

Официальные оппоненты: д.т.н., профессор В.М. Курейчик

д.т.н., профессор В.А.Фатхи д.т.н., профессор C.B. Жак

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

Кафедра «Прикладная математика» ФГОУ ВПО «Южно-Российский государственный технический университет»

Защита состоится « ZS » декабря 2008 года в « /о°" » на заседании диссертационного совета Д 212.058.04 Донского государственного технического университета по адресу:

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

Автореферат разослан « ¿У » hjcS¿^-J 2008 года. Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим направлять в адрес совета.

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

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

к.т.н., доцент J?Ас&Ш-^/ - Н.С. Могилевская

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

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

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

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

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

венное снижение вычислительной сложности, а с другой, сохранение вычислительной точности (или незначительную её потерю).

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

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

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

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

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

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

> разработка аналитических методов оптимизации вариантов решения распределительных задач для 2-4 приборных систем и, ограниченно, для п приборных систем;

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

> разработка вероятностно-эвристических методов решения распределительных задач и оценки их оптимальных вариантов;

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

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

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

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

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

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

что позволило повысить эффективность решения неоднородных распределительных задач за счет повышения (до 20%) быстродействия решения.

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

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

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

6) Обоснование метода использования генетического алгоритма как инструмента субоптимизации решения распределительной задачи, поддержанной статистически достоверной оценкой доверительности результата, согласно которому, например, можно найти оценку оптимума распределительной задач для т = 17 -25 работ и я = 3 приборов с

вероятностью более 0,999 на основе 7 опытов реализации ЭГА, требующих несколько десятков миллисекунд счёта (затраты на АА составляют сотни сек.).

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

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

Достоверность результатов исследования. Достигается за счёт корректного применения системного анализа, методов математического анализа и моделирования, их статистической обработки. Общий

объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил более 10б опытов. Минимальный статистически представительный эксперимент обеспечивался не менее, чем 100 опытами. Программное средство «Система для проведения исследований в области задач построения расписаний» («Рго]есЛ5Ьес1и!ег»), на котором осуществлялось автоматизированное проведение имитационных экспериментов в однородных средах, прошло официальную регистрацию в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (ФГУ ФИПС свидетельство № 2007612127 (роспатент) от 23.05.2007). Другое программное средство «Система вычислительных исследований неоднородной распределительной задачи» находится в «Роспатенте» на рассмотрении.

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

: > почти двукратное снижение ресурсоемкое™ решения задач оптимизации в многоприборных системах при использовании многокритериальных оценок;

' > существенное (до 20%) снижение времени решения неоднородных и однородных распределительных задач точными алгоритмами, являющихся основным инструментом оценки оптимального решения;

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

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

> апробирована совокупность программных комплексов решения распределительной задачи в различных средах и с различными критериями оптимальности, а также настраиваемыми параметрами и характеристиками распределительных задач [54], что позволяет решать практически всю гамму распределительных задач теории расписаний и создает основу для построения проектно-йсследовательского и учебного программного комплекса поддержки решения 'задач изучаемой, предметной области.

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

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

Апробация диссертационной работы. Материалы диссертационной работы апробировались на четырнадцати международных научных конференциях: «Использование ЭВМ в учебной и научно-исследовательской работе студентов» - тез. докл. на респ. совещ.-семинара, 26-28 янв. / НГУ.- Новосибирск, 1988.- Ч. II; «Новые информационные технологии. Разработка и аспекты применения» - тез. докл. IV Всерос. науч. конф. с междунар. участием молодых ученых и аспирантов, 15 нояб.,/ ТРТУ.- Таганрог, 2001; «Компьютерное и математическое моделирование в естественных и технических науках» - тр. III Всерос. науч. ¡nternet-конф., сент.- нояб. / ТГУ. -Тамбов,2001.-Вып. 13; «Электроника и информатика-2002»: тез. докл. IV Междунар. науч.-техн. конф., Зеленоград, 19-21 нояб. / МИЭТ (ТУ). - М., 2002. -4.2; «Новые информационные технологии. Разработка и аспекты применения»: тез. докл. пятой Всерос. конф. с междунар. участием молодых ученых и аспирантов, 28 нояб. / ТРТУ. - Таганрог, 2002; «Современные проблемы информатизации в технике и технологиях»: сб. тр. по итогам VIII Междунар. открытой науч. конф. / ВГТУ.-Воронеж, 2003.-Вып.8; «Математические методы в технике и технологиях - ММТТ-16»: сб. тр. XVI Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2003. - Т. 8, секц.12; «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем»: материалы II Междунар. науч.-практ. конф., 21 мая / ЮРГГУ (НПИ). - Новочеркасск, 2004; «Математические методы в технике и технологиях - ММТТ-17»: сб. тр. XVII Междунар. науч. конф. / КГТУ. - Кострома, 2004. - Т.2, секц.2; «Математические методы в технике и технологиях» - ММТТ-18: сб. тр. XVIII Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2005. - Т. 2, секц. 2; «Современные

проблемы информации в непромышленной сфере и экономике»: сб. тр. - Воронеж, 2005. - Вып. 10; «Математические методы в технике и технологиях - ММТТ-19»: сб. тр.Х1Х Междунар. науч. конф./ ВГТА. - Воронеж, 2006. - Т. 2, секц. 2; «Математические методы в технике и технологиях - ММТТ-20»: сб. тр.ХХ Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 2, секц. 2; Труды 8 международной научно-технической конференции «Динамика технологических систем», - Ростов н/Д, Том 2; «Математические методы в технике и технологиях - ММТТ-21»: сб. тр. Междунар. науч. конф./ ВГТА. - Саратов, 2008. - Т. 5.

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета, Таганрогского радиотехнического университета (ныне. - ТТИ ЮФУ) и Новочеркасского политехнического института (ныне - ЮРГТУ).

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

Структура диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и приложений. Общий объем работы составляет 317 страниц машинописного текста, в том числе 78 рисунков и 45 таблиц.

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

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

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

Таким образом, для исследования выбрана система, состоящая из п несвязанных исполнителей (приборов) Р = {р],р2,..., рп} .На

обслуживание поступает множество = < = 1, m) независимых параллельных работ (задач)®. Известен объем ресурса (,■ , необходимого для

выполнения работы исполнителем.

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

Sj: Vj,k e[l, л S} П^ = 0 , (J Sj = 5 , (1)

r-i

где s - исходное множество заданий , п - число исполнителей, т -число заданий.

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

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

(2)

Каждому варианту разбиения Л (о) соответствует вариант

г{т,п)={)Щ,т2,...т„} (3)

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

!>, = «. (4)

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

Опт (°)] = |ШХ 0 = Ьп } / (5)

где 7} = X'* " общая оценка загрузки ] -го исполнителя выполнением

назначенных для него т/ заданий; = {!,(/,■■■} ■

(/*<7)&(/,<5г,...е к{/^=т}, а суть кардинальное число или мощность множества индексов 1}.

Кроме основного (наиболее распространенного и содержательного) критерия (5) используется квадратичный оценочный критерий, предложенный в работе [1],

а,М= Ь] ■ ./1

(6)

Если при распределении ставится задача оптимизации его результата, алгоритм распределения завершается отношением

(7)

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

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

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

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

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

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

> методологию структурно-параметрических условий различия распределений, оптимальных по минимаксному и квадратичному критериям;

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

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

> алгоритмическая модификация алгоритма Романовского, опирающаяся на формирование первого приближения с использованием быстрых методов приближенного решения оптимизационных распределительных задач;

> обобщение методологии списочного' подхода к распределению заданий распределительной системы на количественно и качественно неоднородные системы;

> алгоритмическая модификация точного алгоритма Алексеева, основанная на использовании обобщённого списочного подхода и учете специфики качественной неоднородности решаемой задачи.

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

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

дач теории расписаний и имитационно исследовать точностные и временные характеристики подхода;

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

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

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

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

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

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

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

Так, для систем малой размерности показано [3,4,7], что в ряде случаев существует связь, между результатами оптимизации распределения заданий по критериям (5) и (6). В общей постановке для т работ, обслуживаемых п приборами оценить такую связь трудно, и, даже, вряд ли возможно. Однако при п =2, как показали исследования, можно получить точное решение задачи. Такой результат достаточно важен, поскольку двухприборные варианты обслуживания работ весьма распространены. Примером могут служить двухпроцессорные вычислительные системы.

В частности, задача распределения т работ с ресурсными оценками rf на 2 подмножества т, и т2 между 2-мя приборами обладает следующими свойствами: ■

wl ml от

Т, Т2 = £т>; г\ +тг =Zr! =т = const, (8)

1 i=l 1=1

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

На основе (8) в диссертации проводится исследование поставленной задачи и показывается, что оптимизации распределения по одному из критериев (5) или (6) достаточно для оптимальности этого решения по второму. Полученный результат позволяет существенно (почти в 2 раза) уменьшить время на точное решение по обоим критериям. Исследование построено в виде совокупности лемм и их следствий.

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

--т1 3 т

V/ = l,3-*7}=5>, ; YJi =Er(=r = co/7ji,

(9)

где 1) - суммарные ресурсы совокупностей работ, назначенных каждому прибору. Далее обозначения Т} принимаются предметные обозначения

т т т

max ' * mid I 1 min *

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

А Лемма 1 об условиях максимальности квадратичного критерия. В оптимальном по критерию (5) или (6) трехприборном распределении квадратичный критерий будет принимать максимальное значение при Tmid ~ Ттях, если 7тах фиксировано.

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

А Лемма 3 об условиях совпадения оптимумов по квадратичному и минимаксному критериям. Оптимальное по критерию (6)

трехприборное распределение,, у которого Ттах - тш < 3@ невозможно перестроить в распределение с меньшим 7тлх и большей оценкой критерия (б).

Следствием доказанных лемм является свойство, по которому оптимальное по (6) распределение является оптимальным и по (5), если разница между и не превышает 2. Если же эта разница для

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

возможно перераспределение заданий с уменьшением 7'пик и, по крайней

мере, не уменьшением квадратичного критерия.

Полученный результат позволяет поставить задачу оценки возможного уменьшения 7ти в зависимости от значений Тш, 7;,11П и построить алгоритм нахождения максимального отклонения оптимального значения минимаксного критерия от максимальной загрузки распределения, оптимального по критерию (6). Алгоритм находит возможное максимальное отклонение от оптимального квадратичного распределения, не решая задачу распределения по критерию (5). Поэтому, как и предыдущие, этот результат позволяет существенно (также практически в 2 раза) уменьшить время на получение оценки точных решений для дополнительно привлекаемых критериев.

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

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

> при каком начальном расположении заданий такая ситуация возможна;

> какое конечное расположение этих заданий будет в данной ситуации;

> каков минимальный размер заданий, создающих данную ситуацию.

Сформулированная задача решается через доказательство двух лемм, обосновывающих частные свойства и характеристики исследуемых распределений [9].

® Наименьший размер ресурса выполнения задания традиционно считается единичным.

А Лемма 4 о структуре и нижней границе числа перераспределяемых заданий. Минимально допустимое число заданий, оптимально распределенных по КВ критерию, которые при определенных параметрических условиях могут быть преобразованы в. распределение, оптимальное по ММ критерию, не может быть меньше шести, а структура их компоновки по 3 приборам может быть задана только распределением 2КЙ [б,з]= {2,2,2:}.

Л Лемма 5 о минимальной загрузке прибора после перераспределения. Конечный результат г,"т[б,з]={т1,т2,от3} перераспределения заданий из распределения /^[б,з]= {2,2,2}, не может содержать нулевых элементов, т.е. V/ = 1,3 •-» т, * 0.

Результатом этих лемм, является тот факт, что при перераспределении единственно возможной исходной структуры (рис.1) /кп[б,з]= {2,2,2} могут быть получены три структурно различных варианта распределения. Исследование этой задачи для произвольных размеров оценок заданий наталкивается на серьезные комбинаторные трудности. Поэтому исследован частный ее вариант для граничных параметров исходного распределения. Результаты такого исследования обобщаются теоремой.

Л Теорема 1 о возможности структурного перераспределения заданий. Единственным структурно допустимым вариантом преобразования распределения 2^[б,з]= {2,2,2} к распределению

Кт [б>31 = {«1.Щ >»Ч) является преобразование вида {2,2,2 }—> {з,2,1}.

Иллюстрацию доказанного свойства дает перераспределение {2,2,2 }—> {з,2,1} (рис. 2) с уменьшением критерия (5). Для множества из 6 работ 5 = {х,,...5'6} и соответствующего множества Г = {4,6,4,9,6,4} оценок ищется вариант, уменьшающий максимальную загрузку. Распределение имеет вид /<£, (Л\ з) = {{.?,, л4}, {$2, л-3}, ,56}}, и ему соответствует

распределение оценок {{4,9}, {б,4}, {б,4}}, со значением крите-

рия (?аГ[°]=369 и оценкой максимальной загрузки (¿„,„[°]=13. Его перестроение С и /С(^3)={{9},{6,6},{4,4,4}) даёт минимаксную оценку и квадратичную оценку &,[°]=369.

Ттах<

/

А

<

В

Гт/с/ <

г С г Е

< Р Ттт < Р

1 приб. 2 приб. 3 приб.

Рис. 2. Оптимальное распределение 6 заданий на 3 исполнителя по 2

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

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

пределение, оптимальное по критерию (6), то можно аналитически доказать следующую теорему.

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

деленного монолита, то это же распределение работ оптимально по критерию (5).

Несовпадение оптимумов загрузок однородной трёхприборной системы по критериям (5) и (6) возможно только при определённых условиях, которым отвечают загрузки конкретного распределения, что доказывается очередной теоремой.

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

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

Аналогичный подход применим к анализу четырехприборных систем. Так, для четырехприборной системы, основные свойства которой аналогичны трёхприборной

--"Ч 4 т

У/ = 1,4->7) = £г ; £7' =£т,=Г = сою/, (10)

¡=1 >1 2

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

Например, рассматривая 4-приборную систему с 2 монолитами. Используя предыдущие результаты, аналитически показывается, что результат, полученный для трех приборов переносится на 4 прибора, то есть такое распределение будет обладать инвариантностью относительно квадратичного критерия. Иными словами, показано, что если имеется распределение, оптимальное по критерию (6), где загрузка двух приборов представляет собой монолит, а другие два загружены остальными заданиями (рис.3), то справедлива следующая теорема, опирающаяся на результаты теорем 2 и 3. '

тг1

»1,

ш2 /

Монолит

1114=1

1-й 2-й 3-й 4-й

Рис. 3 Распределение с двумя немонолитами

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

оценка времени выполнения выделенного монолита, то это же распределение работ оптимально по критерию(5).

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

Поскольку по результату этой теоремы ясно, что добавление монолита, который лежит в пределах Т^.Лк1п!и, тт) не влияет на значение

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

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

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

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

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

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

по значению критерия, полученного методом критического пути. Эффект от такой замены обусловливается тем, что списочные алгоритмы отличаются простотой в построении и реализации, а, кроме того, характеризуются высокой эффективностью с точки зрения получения результата близкого к оптимальному. Реализация расписаний в них основана на применении линейных списков операторов, упорядоченных по убыванию (возрастанию) приоритетов в соответствии с принятым алгоритмом последовательного отбора операторов [10,58].

Для оценки влияния выбора оценки ожидаемого максимума на скорость выполнения классического и модифицированного алгоритмов Романовского был поставлен вычислительный эксперимент. Условия испытаний были ориентированы на использование наиболее трудный для всех точных алгоритмов интервала варьирования распределяемых работ [25-30], на котором они «циклятся», что приводит к серьезным затруднениям при отыскании решения . Результаты вычислительного эксперимента приведены на рис. 4-6.

Интервал 25-30 число приборов = 2

время выполнения, с

150 100 50 0

Ж

ш/ Класс

17 18 19

число задач

□ Класс

□ Смкп

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

Интервал 25-30 число приборов = 3

40- 'Ш

время выполнения, 20 ^ с

о

ж

V

16

Класс

17 18

□ Класс И Смкп

число задач

Рис. 5. Зависимость времени решения задачи распределения от способа

формирования начальной оценки для трех приборов Интервал 25-30 число приборов = 4

время 300 выполнения, 200 с 100 0

400

г Смкп Класс

□ Класс Н Смкп

16

17

число задач

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

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

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

® Локальное нарушение тенденции роста времени решения задачи с увеличением размерности на рис. 5 объясняется так называемым эффектом «кратности», который исследуется ниже.

Среднее время выполнения заданий для 2х-приборной системы

Рис. 7. Зависимость среднего времени решения от размерности распределительных задач для двух приборов двумя точными алгоритмами

В работе также приводится модификация алгоритма Алексеева для однородных систем, которая заключается в следующем: исходная матрица [г ] длительностей обслуживания заданий может быть заменена вектором г,- ,где г, = (й, /=1, 2, ..., т, так как для однородных приборов выполняется равенство / ( ~1п = , / =1, 2, ..., т. Для упрощения оценки нижней границы варианта распределения следует перед началом выполнения процедуры ветвления упорядочить элементы ц, таким образом, чтобы соблюдалось неравенство

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

РГ7ЯД1 МАА

Размерность задачи 2хш

Рис.9 Сравнение АР и МАА для двухприборных систем

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

Найденные способы повышения эффективности АР не исчерпывают все возможности сокращения времени решения. В частности, автором выявлен упомянутый выше эффект «кратности». Его суть заключается в феномене резкого снижения времени решения для количества работ, кратных числу приборов, что хорошо иллюстрируется рис.8, на котором построена зависимость времейи решения задачи от количества заданий. Логарифмическая зависимость скрадывает эффект увеличения времени при нарушении кратности. Однако хорошо видно, что в «кратных» случаях время решения растёт с увеличением размерности незначительно. Подобная зависимость наблюдается и при других количествах приборов.

Т среднее

Размерность задачи Зхт

Рис.8 Иллюстрация эффекта 'фатности

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

работ т и приборов п , количественно выраженной остатком от деления этих целых

Kr = mmodn (12)

где mod операция получения остатка от деления ш на п .

Выявленный феномен, проявляющийся для наиболее распространенных алгоритмов решения распределительных задач, позволяет сформулировать удивительно простой и, вместе с тем, эффективный подход к их решению на подготовительном этапе формализации. Этот подход выражается в сформулированном ниже правиле, которому автор дал название «метод псевдократной загрузки» [37,6].

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

5 = {^|»б[1,1я]} (13)

привести к псевдосписку (псевдопоследовательности)

S'^liekmJ}, (14)

у которой mp = K-n:K = 1,2,..., а К- ближайшее к целому от деления m на п либо снизу

К = int(w/«), (15)

т.е. из списка удаляется часть работ, либо сверху

К = inl(m/«)+ я, (16)

т.е. в список добавляются (с учётом знака) некоторые псевдоработы, количество которых вычисляется по формуле

Am = m-К. (17)

После решения распределительной задачи расписание вновь корректируется: в случае (14), в списки работ наименее загруженных приборов добавляются исключенные перед распределением работы; в случае (15) из списков работ приборов исключаются псевдоработы.

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

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

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

X - {С, = {рл,},С2 = {рп2},С3 ={рпг},...,Ст = {рп.}}, (18)

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

Для распределительных задач, рассматриваемых в данной диссертации, решение может быть полностью представлено кодированием одной хромосомы для особи. При этом размер хромосомы имеет линейную зависимость от числа работ зкео/{Х) = т*-н/8 и логарифмическую м> = 11оя(л)/1<^(2)}+1 от числа приборов. В связи с тем, что номер прибора кодируется избыточностью, кратной байту, раскодирование осуществляется с помощью линейного закона вида Д = 2'" / п, где Д - величина /го интервала, гю которому значение гена преобразуется в номер прибора. Границы/го интервала определяются следующей формулой:

ДМО-ОМ.уМ], (19)

где/ - номер прибора; Д/ - диапазон перевода значение гена в номер/ прибора.

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

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

Для проверки эффективности ЭГА проведён эксперимент п = 3, т = 7 . Основные значения генетических операторов задавалась, согласно классическим рекомендациям, следующими значениями: вероятность кроссовера - 0,9, -вероятности мутации и изменения бита - 0,1, вероятность инверсии - 0,05. Процесс решения такой задачи с помощью ЭГА показан на рис.10, где можно наблюдать изменчивость получаемых

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

.г " ............................................................. .............................."""]

Процесс решения

к го

£ X Й-

2 Е § Ь

>. О

400 300 200 100 0

25,5 25

со Е Н

24,5 « 3

24

2.3,5

0 10 20 30 40 50 60 70 80 90 N Поколения

»Суммарная —»»Лучшая особь

у

Рис. 10. Иллюстрация решения методом ЭГА Исследование свойств ЭГА показало, что для «удобного» для распределительных задач диапазона распределяемых работ ¡5-50] он показывает хотя и большую, в сравнении с методом критического пути, но практически линейную зависимость времени сходимости от размерности (рис. 11) и позволяет решать недоступные для точных алгоритмов задачи, давая значительно более точные результаты (рис. 12).

Время получения решения

20

ъг Ш 15

О о;" 10

г ш 5

о. ш 0

□

□ п

0 |---ттшп,

17 117 217 317 417 Число работ

Точность решения

100

-5 98

.а ь 96

о

о X 94

У о 92

Н-

□

17 117 217 317 417 Число работ

Рис. И Быстродействие ЭГА

Рис. 12 Точность ЭГА

Кроме того, для ЭГА проявляется описанный в третьей главе эффект «кратности», иллюстрируемый на рис.13 для трёхприборной системы.

Точность ГА

1,2

1,0

¡5 0,8 о

§ 0,6 £ 0,4 0,2 0,0

16 17 18

19 20 21 Число задач

22 23 24

Рис. 13. Влияние кратности на работу ЭГА

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

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

количественной оценки свойств ЭГА при решении РЗ в работе принято решение об оценке вероятности по нижней границе значений - р'"т. Для её получения использовался итеративный поиск по случайным распределениям с фиксацией нижней границы р0 и проверкой точного

решения АР. При этом, например, для области параметров РЗ: п = 3 ,

т = 17 , диапазоне работ [25..30], стандартных настройках ЭГА и ограничением Рщтт - 0,001, зафиксировано наихудшее значение р™т = 0,06 .

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

значительно отличаются от рекомендуемых в литературе (например, вероятность мутации особи составила рш,~ 0,41 вместо рекомендуемых 0,1, вероятность мутации бита в гене Рт,„ш = 0,07 осталась близкой к рекомендуемой, увеличилась вероятность кроссовера: Р„,кжт= 1 вместо 0,9).

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

№ по запуску ЭГА по формуле

Кы^Ы/41-рГ). (20)

Такое количество ЭГА, повторенных для исследуемой РЗ, необходимо для того, чтобы с заданной вероятностью РЙ1Х< получить точное

решение хотя бы в одном из опытов. Число необходимых опытов для размерности РЗ п-Ъ т = \1 при диапазоне работ [25..30] и полученной вероятности р™ш =0,78 приведено в таблице 1.

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

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

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

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

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

Сущность использования такой( векторной) совокупной оценки ресурса работы состоит в реализации следующего обобщенного алгоритма:

I. Строки матрицы загрузки [33] упорядочиваются с образованием двух блоков: содержащий индексы КН и не содержащий таких индексов.

II. Строки полученных блочных матриц упорядочиваются в соответствии с количественной оценкой качественной и количественной оценок соответственно.

III. Строки блочной матрицы КАН упорядочиваются по количеству не-исполняющих работ/ приборов.

IV. Строки блочной матрицы КОН упорядочиваются по сумме ресурсных оценок.

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

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

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

Сравнение приближенных алгоритмов для г(<^/)е [25,30]

Таблица 2

N М Модиф. алгор. Ал-ва Алгор. Плот-ва-Зверева

Время (мс) V тэх Время (мс) Т шах

2 25 0.0711 345.1 0.0104 351.32

2 45 0.097 609.7 0.0192 622.12

2 65 0.1813 875.5 0.0222 895.32

2 85 0.297 1142.43 0.0311 1170.27

2 105 0.4067 1407.78 0.0428 1440.86

3 25 0.0634 234.2 0.0103 238.72

3 45 0.1594 400.73 0.0249 409.99

3 65 0.2518 579.11 0.0305 594.65

3 85 0.4462 756.52 0.0448 780.72

3 105 0.6568 930.63 0.0571 959.04

4 25 0.0757 180.38 0.0102 182.99

4 45 0.1895 308.9 0.0216 316.91

4 65 0.3339 437.59 0.0302 451.52

4 85 0.5208 567.31 0.0434 586.05

4 105 0.7319 697.03 0.0607 721.51

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

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

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

Массовая постановка эксперимента требует наличия удобного автоматического программного средства проведения экспериментов с

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

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

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

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

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

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

Программный продукт "РкуейБИесМег" предназначен для проведения исследований в области теории расписания (ФГУ ФИПС свиде-

Алгоритмы

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

Матрица

Опыт

Расчет

Расписание

Загрузка из Генерация

БД опытов

/—^

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

Просмотр

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

Рис. 14. Концептуальная модель объектов ПС решения тельство № 2007612127 (роспатент) от 23.05.2007)[55]. Концептуальные модели объектов и их взаимодействия представлены на рис 14. Про-грамм-мное средство (ПС) выполнено по объектно-ориентиро-ванной парадигме на языке Object Pascal в среде Turbo Delphi.

Общее представление об интерфейсе ProjectSheduler можно получить на рис.15, где представлена главная форма приложения.Система

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

Кроме описанного выше комплекса, ориентированного на решение однородных задач, использовался разработанный и направленный в Роспатент для регистрации программный комплекс, ориентированный на

'v^A 7 «л SjJii ЖШъ. с

ш И«мдое»нц* спраск» берйм. 1ЛЛЛ5

Имя

W) Ш

1,002 Опыт.002 15.00-40.00_С05_060 00 1JXB ОпыгООЗ 15.00-40.00_С05_080 80 1,0« Опыт ам 15_00-40.00_005.080 80 1,005 0пыг:00515л0-40.00_005_сюа 00

^OOSanrfT.OOSt5.03«3.<«_005_08C ее

1^0070,^01/ ! 5.00-40.00_С05_080 80 1.000 0яьл:С08 1S.CO-4aCC_C05_080 80 1 009 Слыт.00915.00 40,00_С05_080 80 1_010 0(Ь(Т.010I5.u0-40.00_C05_080 80 1.011 Orwt.Oll 15.00-40.00_005_000 00 1J)120rbr012 15.00-40ДИЮ5_080 80 1 _013 Oiwt 01315.00-40,00_0Q5 JB0 80 1.014 0гыг.014 1 5,00-40.00_0й5_0С0 60 1_015(]г*,1г01515.00-40.00_005_080 80 1_0160(Ы1.016! 5.00"tO.GO_G05_OSO 80 lj>}? Опыг.Ш 80

1.019 0лыт:01815,00 40.00_005_080 80 1 nian.».„ni4 ";пл.лппп пгк поп ип

)Раб [При^Тщак ]Т|

реи

imSL4Z$lE 0Ж2Ж 429.00-435.« 0.30-212£ 440,00-448.« 0,41 127С 435.00-440.QC 0,42-131'. 445.0CM5i.0C 0.5f-t59C 424.0042«.« 0.41-123; 463,00-450.01 0.Е6-Ш 429.CKH29.0i 0.3974.?

И встройки Огыта Имя Опыта; 1..С0

Л/горпм Рсьнповсг.со Мет св Генетический

Настройки Параметры

Пр1

1 ш

.2 31

: 3 38

4 27

:5 г?

30

|Ствтдс ¡Грасч.пи ¡Тпв^гВ-ар/сс^Комменгару

Семге Ш Ш Ш

Готово 1.22 466 110.33 Pcu»iHiv на«

Готово 1 305.75 470 0.45 Л>,*иая хроме

I 8,2718061255302

Работ. 80 Приборов: 5

ШиюроднСие

РозупьтгНЬ! ПланфовМж Мет с« критического пути. Олыг.

Ракцхздепемие робот

Диаграмма Роспрсвея

I II

Пр1

Пр2 8) N НИ П| NU(t3?| N:ll

ПоЗ 8! N:llfc3Sl N l35t2SJ N:t!

•mxli:

и-fesiWi Hisfi ¡эй wfol zulnm M*iW l-S.T»/|

»KiKiirie Kiwi's;*,! ¿Si HIMi,l Ml iwj«»is:

>1*1 «мк ж « »11. ¡:| Bit* Ш «М KSWtl а:и,( кол ММ «з* Wi

»в! м>„| -и,! siiri si -шЛ «Ыи) ьЫ от»

-CC '-i 2И KB 3iO ЭИ ten

Рис. 15. Интерфейс главной формы системы РгсуейБИесМег

решение неоднородных задач. Наряду с исследуемыми задачами теории расписаний он использовался для решения задачи раскраски взвешенного графа, для которой автор нашел решение с использованием одного из разработанных алгоритмов.[1,12,13]

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. 1.Кобак В.Г. Алгоритм раскраски взвешенного графа (статья) // Букин В.В. // Известия СКНЦВШ. Техн. науки.- 1988.-№3.

2. Кобак В.Г. Статистическая оценка способа ускоренного заряда никель-кадмиевых аккумуляторов (статья) // Кукоз Ф.И., Сметанкин Г.Л., Бурдюгов A.C. // Известия вузов. Электромеханика.-2001. - № 4-5.

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

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

5. Кобак В.Г. Энергосбережение при управлении шаговым двигателем (статья) // Солоха A.A. // Известия ТРТУ. - 2005. - №11.

6. Кобак В.Г. Ресурсная оптимизация процесса заряда щелочных аккумуляторов (статья) // Нейдорф P.A. // Известия ТРТУ. - 2005. - №11.

7. Кобак В.Г. Оценка различия квадратичного и минимаксного оптимальных распределений загрузки однородных трехприборных систем (статья). // Известия ТРТУ. - 2006. - №15.

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

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

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

Монография

И. Кобак В.Г. Модели и свойства распределений независимых заданий в технических системах: моногр. / ДГТУ (монография) // Ростов н/Д, 2006

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

12. 12.Кобак В.Г. Распределение функциональных программ в специализированных мультимикропроцессорных системах, с учетом требуемых для них объемов памяти (статья) // Букин В.В. // Гибкие производственные системы и их компоненты: межвуз. сб. науч. ст. / НПИ. -Новочеркасск, 1987.

13. 13.Кобак В.Г. Минимизация числа микропроцессоров при условии сохранения максимальной асинхронности в специализированных мультимикропроцессорных системах (статья) // Робототехнические системы и комплексы: межвуз. сб. науч. ст. / НПИ.-1988

14. Кобак В.Г. Задачи учебной САПР микропроцессорных систем обработки информации (статья) // Букин В.В. // Использование ЭВМ в учебной и научно-исследовательской работе студентов: тез. докл. респ. со-вещ. -семинара, 26-28 янв. / НГУ.- Новосибирск, 1988.- Ч. II

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

(статья) // Букин В.В. // Электровозостроение: сб. науч. тр.-Новочеркасск, 1996.-Т.36.

16. Кобак В.Г. О взаимосвязи минимаксного и среднеквадратического критериев распределения работ (статья) // Букин В.В. // Электровозостроение: сб. науч. тр.- Новочеркасск, 1998.-Т.40.

17. Кобак В.Г. Условие получения различных распределений по минимаксному и среднеквадратическому критериям (статья) // Букин В.В // Электровозостроение: сб. науч. тр.- Новочеркасск, 1999.-Т.41.

18. Кобак В.Г. Модель надежности однородной трех приборной системы без восстановления с двух кратным раздельным нагруженным резервированием при экспоненциальном законе распределения наработки на отказ (тезисы) // Финаев В.И. // Новые информационные технологии. Разработки и аспекты применения : тез. докл. IV Всерос. науч. конф. с междунар. участием молодых ученых и аспирантов, 15 нояб.,/ ТРТУ.- Таганрог, 2001.

19. Кобак В.Г. Математическая модель однородной трехприборной системы без восстановления с М-кратным общим нагруженным резервированием при экспоненциальном законе распределения наработки на отказ (статья) // Финаев В.И. // Компьютерное иматематическое моделирование в естественных и техническихнауках: тр. III Всерос. науч. ¡Шегле^конф., сент.- нояб. /ТГУ. -Тамбов,2001.-Вып. 13.

20. Кобак В.Г. О возможности полученияраспределений при решении задачи оптимального планирования по критериям равномерности и минимизации производственного цикла (статья) // Букин В.В. // Электровозостроение: сб. науч.тр,- Новочеркасск,2001.-Т.43.

21. Кобак В.Г. Надежность однородных систем при различных критериях загрузки (статья) // Букин В.В. // Электровозостроение: сб. науч.тр.-Новочеркасск,2001.-Т.43. . .

22. Кобак В.Г. Модель однородной трехприборной системы без восстановления с экспоненциальной наработкой на отказ (тезисы) // Финаев В.И., Радченко В.М. // Электроника и информатика-2002: тез. докл. IV Междунар. науч.-техн. конф., Зеленоград, 19-21 нояб. / МИЭТ (ТУ). -М., 2002. -4.2.

23. Кобак В.Г. Модель надежности трехприборной системы при двойном нагруженном резервировании и экспоненциальной наработкой на отказ (тезисы) // Финаев В.И., Радченко В.М. // Новые информационные технологии. Разработка и аспекты применения: тез. докл. пятой Всерос. конф. с междунар. участием молодых ученых и аспирантов, 28 нояб. / ТРТУ. - Таганрог, 2002.

24. Кобак В.Г. Определение оптимального значения критерия равномерности по оптимальному минимаксному критерию для однородных

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

25. Кобак В.Г. Модель надежности трехприборной системы при двух резервных нагруженных элементах и экспоненциальной наработки на отказ (статья) // Финаев В.И. // Электровозостроение: сб. науч. тр. -Новочеркасск, 2002.- Т.44,

26. Кобак В.Г. Разработка моделей планирования заданий для однородных двух-трехканальных систем на основе анализа взаимосвязи критериев эффективности: автореф. дис.... канд. техн. наук: 05.13.18 / ТРТУ // Ростов н/Д, 2002.

27. Кобак В.Г. Модель надежности однородной трехприборной системы при одном нагруженном резерве и экспоненциальной наработке на отказ (статья) // Современные проблемы информатизации в технике и технологиях: сб. тр. по итогам VIII Междунар. открытой науч. конф. / ВГТУ.-Воронеж, 2003.-Вып.8.

28. Кобак В.Г. Уменьшение времени работы точного алгоритма при решении задачи о камнях (статья) // Современные проблемы информатизации в технике и технологиях: сб. тр. по итогам VIII Междунар. открытой науч, конф. / ВГТУ.-Воронеж, 2003.-Вып.8.

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

30. Кобак В.Г. Программная реализация эвристических алгоритмов при решении минимаксной задачи в однородных системах (статья) // Коньков A.A. // Математические методы в технике и технологиях - ММТТ-16: сб. Tp.XVI Междунар. науч. конф. / СПбГТИ (ТУ). -СПб., 2003,- Т. 2, секц. 2.

31. Кобак В.Г. Модель надежности трехприборной системы при двойном нагруженном резервировании и экспоненциальной наработкой на отказ (статья) // Финаев В.И., Радченко В.М. // Математические методы в технике и технологиях - ММТТ-16: сб. тр. XVI Междунар. науч. конф. / СПбГТИ (ТУ). -СПб., 2003.- Т. 5, секц. 2.

32. Кобак В.Г. Критериальная инвариантность алгоритма обслуживания по/критическому пути в однородных системах (статья) // Нейдорф P.A. // Математические методы в технике и технологиях - ММТТ-16: сб. Tp.XVI Междунар. науч. конф. / СПбГТИ (ТУ). -СПб., 2003.- Т. 2, секц. 2.

33. Кобак В.Г. Модификация алгоритма обслуживания по «критическому пути» для систем с избирательными свойствами приборов (статья) // Информатика и системы управления. - 2003. - №2.

34. Кобак В.Г. О быстродействии алгоритмов решения минимаксной задачи теории расписания в зависимости от среднего времени выполне-

ния требований (статья) // Федоров С.Е. // Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем: материалы II Междунар. науч.-практ. конф., 21 мая / ЮРГТУ (НПИ). - Новочеркасск, 2004.

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

36. Кобак В.Г. Исследование эффективности точного и приближенного алгоритмов решения минимаксной задачи теории расписания (статья) // Федоров С.Е. // Математические методы в технике и. технологиях -ММТТ-17: сб. тр. XVII Междунар. науч. конф. / КГТУ. - Кострома, 2004. -Т.2, секц.2.

37. Кобак В.Г. Метод псевдократной загрузки в задачах многоприборного распределения вычислительных работ (статья) // Нейдорф P.A., Федоров С.Е. // Математические методы в технике и технологиях -ММТТ-17: сб. тр. XVII Междунар. науч. конф. / КГТУ. - Кострома, 2004. - Т.2, секц.2.

38. Кобак В.Г. Сравнительный анализ точных алгоритмов решения минимаксной задачи (статья) // Федоров С.Е // Технические средства и технологии для построения тренажеров: материалы науч. - техн. семинара, Звездный городок,13-14 окт. - М., 2004. - Вып. 5.

39. Кобак В.Г. Анализ приближенных алгоритмов решения задачи планирования в однородной двухприборной системе (статья) // Федоров С.Е. // Математические методы в технике и технологиях - ММТТ-18: сб. тр. XVIII Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2005. - Т. 2, секц. 2.

40. Кобак В.Г. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи в однородной двухприборной системе (статья) // Федоров С.Е. // Современные проблемы информации в непромышленной сфере и экономике: сб. тр. - Воронеж, 2005. - Вып. 10.

41. Кобак В.Г. Сравнение алгоритмов распределения несвязанных задач в функционально неоднородных системах (статья) // Математические методы в технике и технологиях - ММТТ-18: сб. тр. XVIII Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2005. - Т. 2, секц. 2.

42. Кобак В.Г. О выборе алгоритмов решения минимаксной задачи однородной двухприборной системы обслуживания (статья) // Нейдорф. Р. А. // Научное знание: новые реалии: межвуз. сб. - М.: Учеб. литература,-2005.

43. . Кобак В.Г. Взаимосвязь минимаксного и квадратического критериев в однородной трехприборной системе (статья) // Нейдорф P.A. // Информатика и системы управления. - 2005. - №2. ,

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

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

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

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

48. Кобак В.Г. Сравнительный анализ алгоритмов решения задачи планирования в однородных вычислительных системах (статья) // Иванов М.С. // Математические методы в технике и технологиях - ММТТ-20: сб. тр.ХХ Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 2, секц. 2.

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

50. Кобак В.Г. Условия несовпадений оптимумов распределений по минимаксному и квадратичному критериям (статья) // Математические методы в технике и технологиях - ММТТ-20: сб. тр.ХХ Междунар. науч. конф./ ВГГА. - Ярославль, 2007. - Т. 2, секц. 2.

51. Кобак В.Г. Взаимосвязь критериев эффективности при решении однородной минимаксной задачи на трех приборах // Кобак В.Г. // Математические методы в технике и технологиях - ММТТ-20: сб. тр.ХХ Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 10.

52. Кобак В.Г. Исследование принципа «элитизма» генетического алгоритма решения минимаксной задачи в однородных системах обработки информации // Нейдорф P.A., Будиловский Д. М. // Кисловодск, 2007.

53. Кобак В.Г. Модификация алгоритма распределения в неоднородной системе обработки информации // Нейдорф P.A., Красный Д.Г, // Кисловодск, 2007.

54. Кобак В.Г. Задача минимизации времени выполнения параллельных технологических операций в машиностроении // Нейдорф P.A. // Труды

8 международной научно-технической конференции по динамике технологических систем, Том 2.

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

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

57. Кобак В.Г. Анализ условий минимального отличия квадратичного и минимаксного критериев в однородных трехприборных системах // Кобак В,В. // Сборник науч. Статей. Ростов на Дону: ДГТУ, Таганрог: ТТИ ЮФУ, 2007. .

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

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

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

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

62. Кобак В.Г. Исследование турнирного отбора в генетическом алгоритме для решения однородной минимаксной задачи // Титов Д.В. // Математические методы в технике и технологиях - ММТТ-21: сб. тр. Междунар. науч. конф./ ВГТА. - Саратов, 2008. - Т. 5.

63. Кобак В.Г. Сравнение генетического и списочного алгоритмов при решении распределительной задачи по квадратичному критерию // Кобак В.В., Будиловский Д. М. // Математические методы в технике и технологиях - ММТГ-21: сб. тр. Междунар. науч. конф./ ВГТА. - Саратов, 2008.-Т. 6.

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

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

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

ВВЕДЕНИЕ

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

1.1 Сферы человеческой деятельности, попадающие в сферу решения распределительных задач 17 1Л Л Параллельные вычислительные процессы 17 1Л .2 Классификация расписаний 21 1Л .3 Условия проведения вычислительных экспериментов

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

1.2.1 Основная модель распределения независимых заданий

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

1.2.3 Критериальная стратегия решения распределительных задач

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

1.3.1. Понятие сложности алгоритмов построения расписаний

1.3.2. Понятие внутренней сложности алгоритмов

1.3.3. Алгоритм полного перебора

1.3.4. Алгоритм, основанный на идее ветвей и границ

1.4. Обзор приближенных алгоритмов решения задачи распределения

1.4.1 Списочные расписания

1.4.2 Вероятностные расписания 51 1.4.2.1 Методы отжига

1.4.2.2 Метод роящихся частиц

1.4.2.3 Табуированный поиск

1.4.2.4 Эволюционный подход 53 1.4.3 Эвристические расписания

1.5. Постановка задачи исследования (выводы по первой главе).

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

2.1. Критериальноя инвариантность распределительных задач в однородных двухприборных системах.

2.2. Исследование соотношения квадратичного и минимаксного вариантов оптимальных распределений однородных трехприборных систем при наличии выделенного монолита

2.3. Анализ условий критериальной инвариантности в однородных трехприборных системах

2.4. Методика аналитической оценки несовпадения оптимумов по различным критериям в однородных трехприборных системах

2.5. Аналитическое исследование п-приборной распределительной задачи с выделенными монолитами

2.6. Выводы по главе.

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

3.1. Решение распределительных задач методом полного перебора

3.2. Алгоритмы точного решения РЗ. Алгоритм Романовского (АР) 107 3.2.1. Краткое описание алгоритма

3.2.2. Пример работы алгоритма Романовского

3.2.3. Анализ АР и возможных путей его усовершенствования

3.3. Модификация алгоритма Алексеева

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

Алгоритм Алексеева (АА).

3.3.2 Модифицированный алгоритм Алексеева для идентичных приборов

3.3.3 Пример работы модифицированного алгоритма Алексеева

3.3.4. Сравнительное исследование алгоритмов Романовского и Алексеева

3.4. Модификация алгоритма Алексеева с учетом времени выполнения каждого задания

3.5. Повышение ресурсной эффективности точных алгоритмов.

3.6. Выводы по главе

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

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

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

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

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

4.1.4 Табуированный поиск 147 4.1.5. Эволюционно-генетический подход

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

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

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

4.2.3. Стратегия отбора.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.5.3. Сравнительная оценка результатов применения к РЗ различных методов и алгоритмов решения. 190 4.6 Имитационно-статистический подход к оценке оптимальности решения ЭГА.

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

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

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

4.7. Выводы по главе

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

5.1 Приближенные алгоритмы решения, основанные на списочных расписаниях.

5.1.1. Списочный подход к решению распределительных задач.

5.1.2. Составление расписаний методом критического пути.

5.1.3. Составление расписаний методом БРТ.

5.1.4. Составление расписаний методом КРТ.

5.2. Алгоритм по направлению.

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

5.4. Перспективы повышения эффективности решения РЗ в неоднородных системах на основе унификации списочного подхода.

5.4.1. Основания для исследования.

5.4.2. Формирование универсальной критериальной стратегии оценки ресурсов заданий распределительной задачи.

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

5.5.1. Последовательная модификация алгоритма МКП при качественной неоднородности.

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

5.6. Приближенные алгоритмы решения, для решения неоднородной минимаксной задачи.

5.6.1. Решение задачи алгоритмом Плотникова-Зверева

5.6.2. Получение, приближенного решения с помощью алгоритма Алексеева

5.6.3. Экспериментальное сравнение алгоритмов

5.7. Повышение ресурсной эффективности точных алгоритмов за счет уступок по точности (метод псевдократной загрузки)

5.8. Выводы по главе.

6. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ АЛГОРИТМОВ РЕШЕНИЯ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ В МНОГОПРИБОРНЫХ ОДНОРОДНЫХ И УСЛОВНО-ОДНОРОДНЫХ СИСТЕМАХ

6.1. Применение приближенных и точных алгоритмов при решении задачи раскраски взвешенного графа.

6.2. Программно-информационная система (ПИС) поддержки имитационного решения и оптимизации распределительных задач

6.2.1. Введение

6.2.2. Организация данных и внутреннего интерфейса

6.2.3. Главное окно программы

6.2.4. Редактор опыта

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

6.2.6. Экспорт и импорт данных

6.2.7. Алгоритмы решения задачи 276 6. 3. Схема сопряжения данных с Excel

6.4. Выбор языка программирования и среды разработки

6.5. Выводы по главе.

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

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

Как показывают теоретические исследования и накопленный вычислительный опыт, многие дискретные задачи эквивалентны с точки зрения их вычислительной сложности. Это так называемые универсальные или полиномиально полные задачи. В настоящее время существует значительное число задач, имеющих экспоненциальную оценку сложности. К ним относятся задачи целочисленного и линейного программирования, задачи о коммивояжере, о размещениях, об обработке деталей на станках и т.д. Решением этих задач занимались известные отечественные ученые Алексеев О.Г., Романовский И.В., Поспелов Д.А., Тараканов В.Е., Горбатов В.Е. и многие другие. Существуют предположение, что все эти задачи неразрешимы за полиномиальное время. [15,19,22,25]

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

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

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

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

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

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

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

Разработка моделей планирования заданий актуальна не только для ВС. Подобные модели существуют и в промышленности (распределение заданий по станкам, по участкам и т.д.), на транспорте (планирование перевозок) и т.д. Поэтому в диссертационной работе использованы понятия из теории массового обслуживания: задание ( распределительная задача), работа, прибор, канал обслуживания (любое устройство, выполняющее задание). [36,38,40,47,49,50]

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

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

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

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

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

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

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

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

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

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

4) Алгоритмическая модификация метода Романовского, состоящая в формировании первого приближения на основе использования быстрых приближенных методов решения задачи, в частности, метода критического пути, генетического алгоритма, отличие которого от классического состоит в значительном для №>-полных задач (до 90%!) увеличении быстродействия.

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

6) Обоснование метода использования генетического алгоритма как инструмента субоптимизации решения распределительной задачи, поддержанной статистически достоверной оценкой доверительности результата, согласно которому, например, можно найти оценку оптимума распределительной задач для т = 17 -25 работ и п = 3 приборов с вероятностью более 0,999 на основе 7 опытов реализации ЭГА, требующих несколько десятков миллисекунд счёта (затраты на АА составляют сотни сек.).

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

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

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

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

6.5. Выводы по глав^

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

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

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

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

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

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

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

Программный продукт "ProjectSheduler" предназначен для проведения исследований в области теории расписания (ФГУ ФИПС свидетельство № 2007612127 (роспатент) от 23.05.2007)[]. Концептуальные модели объектов и их взаимодействия подробно описаны в данной главе. Программное средство (ПС) выполнено по объектно-ориентированной парадигме на языке Object Pascal в среде Turbo Delphi.