МЕТОДОЛОГИЯ СОПОСТАВИТЕЛЬНО-КРИТЕРИАЛЬНОЙ АНАЛИТИЧЕСКОЙ ОЦЕНКИ РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧ И СРЕДСТВА ЕЕ ПРОГРАММНО-АЛГОРИТМИЧЕСКОЙ ПОДДЕРЖКИ Специальность 05.13.01 - Системный анализ, управление и обработка информации Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ АВТОРЕФЕРАТ диссертации на соискание учёной степени доктора технических наук Ростов-на-Дону 2008

Авторефераты по всем темам >> Авторефераты по техническим специальностям

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

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

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

Специальность 05.13.01 - Системный анализ,

управление и обработка информации

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

численные методы и комплексы программ

АВТОРЕФЕРАТ

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

Ростов-на-Дону

2008 г.

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

Научный консультант:

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

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

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

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

д.т.н., профессор С.В. Жак

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

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

Защита состоится л декабря 2008 года в л на заседании диссертационного совета Д 212.058.04 Донского государственного технического университета по адресу:

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

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

Автореферат разослан л ___________ 2008 года.

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

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

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

к.т.н., доцент

Н.С. Могилевская

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Идея и методология сопоставительно-критериальной оценки результатов решения и оптимизации распределительных задач, а также отдельные методы ее реализации для двух-четырехприборных и частных случаев n-приборных систем, аналогов которым в отечественных и зарубежных источниках не обнаружено.
Расширение понятия списочного подхода к параллельной обработке заданий распределительной системы на количественно и качественно неоднородные системы введением нормы векторной оценки ресурса выполнения каждого задания распределительной системы в целом и введением списочного приоритета качественно неоднородных оценок, что позволило повысить эффективность решения неоднородных распределительных задач за счет повышения (до 20%) быстродействия решения.
Алгоритмическая модификация точного алгоритма Алексеева, основанная на учете специфики качественной неоднородности решаемой задачи, позволяющая значительно уменьшить количество рассматриваемых вариантов и, соответственно, времени счета (приблизительно на 15%). При решении однородных задач модифицированный алгоритм, существенно выигрывает по быстродействию для двухприборных, а в некоторых случаях, и для трехприборных систем.
Алгоритмическая модификация метода Романовского, состоящая в формировании первого приближения на основе использования быстрых приближенных методов решения задачи, в частности, метода критического пути, генетического алгоритма, отличие которого от классического состоит в значительном для NP-полных задач (до 90%!) увеличении быстродействия.
Генетические модели распределительных задач, отличающиеся своеобразной структурой и статистически обоснованной совокупностью их настроек применительно к распределительным задачам теории расписаний, а также высокой вероятностью получения решения близкого к оптимальному, значительно превышающей соответствующие показатели других приближённых алгоритмов.
Обоснование метода использования генетического алгоритма как инструмента субоптимизации решения распределительной задачи, поддержанной статистически достоверной оценкой доверительности результата, согласно которому, например, можно найти оценку оптимума распределительной задач для работ и приборов с вероятностью более 0,999 на основе 7 опытов реализации ЭГА, требующих несколько десятков миллисекунд счёта (затраты на АА составляют сотни сек.).
Обоснование возможности применения первого приближения алгоритма Алексеева как самостоятельного метода решения распределительных задач, показавшее его более высокие критериальные характеристики по сравнению с распространенными приближенными методами, включая наиболее эффективный среди них - генетический.
Модифицированный алгоритм критического пути для решения распределительных задач в качественно неоднородных системах, отличающийся от имеющихся применением приоритетно-нормированного списочного подхода.

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, для исследования выбрана система, состоящая из несвязанных исполнителей (приборов) . На обслуживание поступает множество независимых параллельных работ (задач)®1. Известен объем ресурса , необходимого для выполнения работы исполнителем.

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

, , (1)

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

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

(2)

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

(3)

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

. (4)

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

, (5)

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

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

. (6)

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

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

(9)

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

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

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

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

Δ емма 3 об условиях совпадения оптимумов по квадратичному и минимаксному критериям. Оптимальное по критерию (6) трехприборное распределение, у которого ©2 невозможно перестроить в распределение с меньшим и большей оценкой критерия (6).

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

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

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

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

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

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

Рис. 1. Варианты перераспределения

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

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

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

Δ Теорема 1 о возможности структурного перераспределения заданий. Единственным структурно допустимым вариантом преобразования распределения к распределению является преобразование вида .

Иллюстрацию доказанного свойства дает перераспределение (рис. 2) с уменьшением критерия (5). Для множества из 6 работ и соответствующего множества оценок ищется вариант, уменьшающий максимальную загрузку. Распределение имеет вид , и ему соответствует распределение оценок , со значением критерия =369 и оценкой максимальной загрузки =13. Его перестроение с и даёт минимаксную оценку =12, и квадратичную оценку =369.

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

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

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

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

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

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

(10)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

, (11)

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

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

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

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

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

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

(12)

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

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

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

(13)

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

, (14)

у которой , а К - ближайшее к целому от деления на либо снизу

, (15)

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

, (16)

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

. (17)

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

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

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

, (18)

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

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

, (19)

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

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

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

Рис. 10. Иллюстрация решения методом ЭГА

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

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

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

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

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

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

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

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

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

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

. (20)

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

Таблица 1

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

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

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

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

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

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

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

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

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

Сравнение приближенных алгоритмов для

Таблица 2

N	M	Модиф. алгор. Алексеева		Алгор. Плотникова-Зверева
N	M	Время (мс)	max, у.е.	Время (мс)	max, у.е.
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 главах разработан обширный комплекс методов алгоритмов, позволяющий решать практически все однородные несвязанные задачи практически любой разумной размерности, а также практически важный класс неоднородных задач. Для их исследования было разработано несколько программных комплексов, важнейшие из которых описаны в следующей главе.

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

На основе выдвинутой автором идеи сопоставительно-критериальной оценки результатов решения и оптимизации распределительных задач разработана её методология, а также отдельные методы ее реализации, предназначенные, преимущественно, для двух-четырехприборных систем. Достоинством такого подхода является значительный, практически двукратный выигрыш во времени решения двухкритериальных задач теории расписаний без дополнительных вычислительных ресурсов.
Как инструмент формирования оценочного эталона, повышающий эффективность сопоставительно-критериального подхода к оценке результатов оптимизации распределительных задач, разработана алгоритмическая модификация метода Романовского, опирающаяся на принцип формировании первого приближения с использованием быстрых списочных методов оптимизации, повышающих быстродействие не менее, чем на 5% при среднем снижение времени счёта в 10-12%, и генетических, имеющих тот же нижний предел быстродействия, снижающих среднее время счёта не менее, чем на 30%.
Как дополнительный инструмент формирования оценочного эталона для неоднородных и, частично, для однородных распределительных задач разработана алгоритмическая модификация точного алгоритма Алексеева, основанная на учете специфики качественной неоднородности решаемой задачи, что позволяет резко уменьшить количество рассматриваемых вариантов и существенно уменьшить время поиска. Однако при решении однородных задач модификация алгоритма Алексеева уступает в быстродействии алгоритму Романовского, демонстрируя максимальный эффект по сравнению с классическим прототипом в неоднородной среде.
На основании системного анализа результатов решения распределительных задач с общим объемом исследуемых выборок превышающим миллионы опытов выявлен эффект уменьшения времени поиска решения для количества задач кратного количеству приборов, что позволило разработать метод псевдократной загрузки, использующий возможность фиктивного изменения размера задачи для ускорения ее решения. Последующая коррекция связанная с коррекцией фиктивных изменений, несколько понижает точность, но время решения уменьшается до 90% и более.
На основании литературных данных и результатов пробных испытаний исследован и адаптирован к задачам теории расписаний метод, основанный на идее эволюционно-генетического поиска экстремума. Адаптацию обеспечило создание и параметрическая оптимизация оригинальной генетической модели и эволюционного алгоритма решения распределительной задачи.
Результаты испытания ЭГА при решении разнообразных распределительных задач показали столь высокие эксплуатационные характеристики, что оказалось возможным использовать его для оценки точных решений, наряду сточными алгоритмами. При этом вероятность достоверности оценок может быть практически сколь угодно большой с незначительными ресурсными затратами-неболее 10 независимых испытаний.
Разработанный в ходе диссертационных исследований комплекс быстрых списочных методов показал себя как эффективный инструмент предварительной оценки решений и включен в инструментарий программно-алгорит-мического обеспечения вычислительных комплексов решения распределительных задач.
Разработанная и апробированная совокупность программных комплексов решения распределительной задачи в различных средах и с различными критериями оптимальности, а также с настраиваемыми параметрами и характеристиками распределительных задач позволил решать большой спектр задач теории расписаний и создал основу для построения проектно-исследовательского и учебного программного комплекса поддержки исследований в изучаемой предметной области. Автором опубликованы учебное пособие и методические указания по теме диссертации для ряда дисциплин кафедры программного обеспечения, а его работа дала хорошие практические приложения в учебном процессе.

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

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

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

1.Кобак В.Г. Алгоритм раскраски взвешенного графа (статья) // Букин В.В. // Известия СКНЦВШ. Техн. науки.- 1988.-№3.
Кобак В.Г. Статистическая оценка способа ускоренного заряда никель-кадмиевых аккумуляторов (статья) // Кукоз Ф.И., Сметанкин Г.Л., Бурдюгов А.С. // Известия вузов. Электромеханика.-2001 . - № 4-5.
Кобак В.Г. Критериальная инвариантность распределительных задач в однородных двухприборных системах (статья) // Нейдорф Р.А., Радченко В.М. // Известия вузов. Электромеханика. - 2003 .-№2.
Кобак В.Г. Соотношение квадратичного и минимаксного распределений загрузки однородных трехприборных систем (статья) // Нейдорф Р.А. // Известие вузов. Электромеханика.-2005.- №3.
Кобак В.Г. Энергосбережение при управлении шаговым двигателем (статья) // Солоха А.А. // Известия ТРТУ. - 2005. - №11.
Кобак В.Г. Ресурсная оптимизация процесса заряда щелочных аккумуляторов (статья) // Нейдорф Р.А. // Известия ТРТУ. - 2005. - №11.
Кобак В.Г. Оценка различия квадратичного и минимаксного оптимальных распределений загрузки однородных трехприборных систем (статья) . // Известия ТРТУ. - 2006. - №15.
Кобак В.Г. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи для однородных приборов (статья) // Будиловский Д. М. // Вестник Дон. Гос. техн. ун-та. - 2006. - Т.6, № 4
Кобак В.Г. Структурно-параметрические условия различия распределений, оптимальных по минимаксному и квадратичному критериям (статья) // Нейдорф Р.А. // Системы управления и информационные технологии, Воронеж, 2007, №2.
Кобак В.Г. Точное решение неоднородной распределительной задачи модификацией алгоритма Алексеева // Нейдорф Р.А., Красный Д.Г. // Известия СКНЦВШ. Техн. науки.- 2008.-№1.

Монография

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

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

12.Кобак В.Г. Распределение функциональных программ в специализированных мультимикропроцессорных системах, с учетом требуемых для них объемов памяти (статья) // Букин В.В. // Гибкие производственные системы и их компоненты: межвуз. сб. науч. ст. / НПИ. -Новочеркасск,1987.
13.Кобак В.Г. Минимизация числа микропроцессоров при условии сохранения максимальной асинхронности в специализированных мультимикропроцессорных системах (статья) // Робототехнические системы и комплексы: межвуз. сб. науч. ст. / НПИ.-1988
Кобак В.Г. Задачи учебной САПР микропроцессорных систем обработки информации (статья) // Букин В.В. // Использование ЭВМ в учебной и научно-исследовательской работе студентов: тез. докл. респ. совещ. -семинара, 26-28 янв. / НГУ.- Новосибирск, 1988.- Ч. II
15. Кобак В.Г. Взаимосвязь критериев эффективности при решении задачи планирования для однородных двухпроцессорныхкомплексов (статья) // Букин В.В. // Электровозостроение: сб. науч. тр.-Новочеркасск, 1996.-Т.36.
Кобак В.Г. О взаимосвязи минимаксного и среднеквадратического критериев распределения работ (статья) // Букин В.В. // Электровозостроение: сб. науч. тр.- Новочеркасск, 1998.-Т.40.
Кобак В.Г. Условие получения различных распределений по минимаксному и среднеквадратическому критериям (статья) // Букин В.В // Электровозостроение: сб. науч. тр.- Новочеркасск, 1999.-Т.41.
Кобак В.Г. Модель надежности однородной трех приборной системы без восстановления с двух кратным раздельным нагруженным резервированием при экспоненциальном законе распределения наработки на отказ (тезисы) // Финаев В.И. // Новые информационные технологии. Разработки и аспекты применения : тез. докл. IV Всерос. науч. конф. с междунар. участием молодых ученых и аспирантов, 15 нояб.,/ ТРТУ.- Таганрог, 2001.
Кобак В.Г. Математическая модель однородной трехприборной системы без восстановления с N-кратным общим нагруженным резервированием при экспоненциальном законе распределения наработки на отказ (статья) // Финаев В.И. // Компьютерное иматематическое моделирование в естественных и техническихнауках: тр. III Всерос. науч. internet-конф., сент.- нояб. / ТГУ. -Тамбов,2001.-Вып.13.
Кобак В.Г. О возможности полученияраспределений при решении задачи оптимального планирования по критериям равномерности и минимизации производственного цикла (статья) // Букин В.В. // Электровозостроение: сб. науч.тр.- Новочеркасск,2001.- Т.43.
Кобак В.Г. Надежность однородных систем при различных критериях загрузки (статья) // Букин В.В. // Электровозостроение: сб. науч.тр.- Новочеркасск,2001.- Т.43.
Кобак В.Г. Модель однородной трехприборной системы без восстановления с экспоненциальной наработкой на отказ (тезисы) // Финаев В.И., Радченко В.М. // Электроника и информатика-2002: тез. докл. IV Междунар. науч.-техн. конф., Зеленоград, 19-21 нояб. / МИЭТ (ТУ). - М., 2002. -Ч.2.
Кобак В.Г. Модель надежности трехприборной системы при двойном нагруженном резервировании и экспоненциальной наработкой на отказ (тезисы) // Финаев В.И., Радченко В.М. // Новые информационные технологии. Разработка и аспекты применения: тез. докл. пятой Всерос. конф. с междунар. участием молодых ученых и аспирантов, 28 нояб. / ТРТУ. - Таганрог, 2002.
Кобак В.Г. Определение оптимального значения критерия равномерности по оптимальному минимаксному критерию для однородных трехприборных систем (статья)// Электровозостроение: сб. науч. тр. - Новочеркасск, 2002.- Т.44.
Кобак В.Г. Модель надежности трехприборной системы при двух резервных нагруженных элементах и экспоненциальной наработки на отказ (статья) // Финаев В.И. // Электровозостроение: сб. науч. тр. - Новочеркасск, 2002.- Т.44.
Кобак В.Г. Разработка моделей планирования заданий для однородных двух-трехканальных систем на основе анализа взаимосвязи критериев эффективности: автореф. дисЕ. канд. техн. наук: 05.13.18 / ТРТУ // Ростов н/Д, 2002.
Кобак В.Г. Модель надежности однородной трехприборной системы при одном нагруженном резерве и экспоненциальной наработке на отказ (статья) // Современные проблемы информатизации в технике и технологиях: сб. тр. по итогам VIII Междунар. открытой науч. конф. / ВГТУ.-Воронеж, 2003.-Вып.8.
Кобак В.Г. Уменьшение времени работы точного алгоритма при решении задачи о камнях (статья) // Современные проблемы информатизации в технике и технологиях: сб. тр. по итогам VIII Междунар. открытой науч. конф. / ВГТУ.-Воронеж, 2003.-Вып.8.
Кобак В.Г. Сравнительный анализ алгоритмов решения минимаксной задачи в однородных системах (статья) // Федоров СЕ.// Математические методы в технике и технологиях - ММТТ-16: сб. тp. XVI Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2003. - Т. 8, секц.12.
Кобак В.Г. Программная реализация эвристических алгоритмов при решении минимаксной задачи в однородных системах (статья) // Коньков А.А. // Математические методы в технике и технологиях - ММТТ-16: сб. тp.XVI Междунар. науч. конф. / СПбГТИ (ТУ). -СПб., 2003.- Т. 2, секц. 2.
Кобак В.Г. Модель надежности трехприборной системы при двойном нагруженном резервировании и экспоненциальной наработкой на отказ (статья) // Финаев В.И., Радченко В.М. // Математические методы в технике и технологиях - ММТТ-16: сб. тp. XVI Междунар. науч. конф. / СПбГТИ (ТУ). -СПб., 2003.- Т. 5, секц. 2.
Кобак В.Г. Критериальная инвариантность алгоритма обслуживания по/критическому пути в однородных системах (статья) // Нейдорф Р.А. // Математические методы в технике и технологиях - ММТТ-16: сб. тp.XVI Междунар. науч. конф. / СПбГТИ (ТУ). -СПб., 2003.- Т. 2, секц. 2.
Кобак В.Г. Модификация алгоритма обслуживания по критическому пути для систем с избирательными свойствами приборов (статья) // Информатика и системы управления. - 2003. - №2.
Кобак В.Г. О быстродействии алгоритмов решения минимаксной задачи теории расписания в зависимости от среднего времени выполнения требований (статья) // Федоров С.Е. // Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем: материалы II Междунар. науч.-практ. конф., 21 мая / ЮРГТУ (НПИ). - Новочеркасск, 2004.
Кобак В.Г. Модификация алгоритма Алексеева при точном решении минимаксной задачи теории расписания (статья) // Федоров С.Е. // Информатика и системы управления. - 2004. - №2.
Кобак В.Г. Исследование эффективности точного и приближенного алгоритмов решения минимаксной задачи теории расписания (статья) // Федоров С.Е. // Математические методы в технике и технологиях - ММТТ-17: сб. тр. XVII Междунар. науч. конф. / КГТУ. - Кострома, 2004. - Т.2, секц.2.
Кобак В.Г. Метод псевдократной загрузки в задачах многоприборного распределения вычислительных работ (статья) // Нейдорф Р.А., Федоров С.Е. // Математические методы в технике и технологиях - ММТТ-17: сб. тр. XVII Междунар. науч. конф. / КГТУ. - Кострома, 2004. - Т.2, секц.2.
Кобак В.Г. Сравнительный анализ точных алгоритмов решения минимаксной задачи (статья) // Федоров С.Е // Технические средства и технологии для построения тренажеров: материалы науч. - техн. семинара, Звездный городок,13-14 окт. - М., 2004. - Вып. 5.
Кобак В.Г. Анализ приближенных алгоритмов решения задачи планирования в однородной двухприборной системе (статья) // Федоров С.Е. // Математические методы в технике и технологиях - ММТТ-18: сб. тp. XVIII Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2005. - Т. 2, секц. 2.
Кобак В.Г. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи в однородной двухприборной системе (статья) // Федоров С.Е. // Современные проблемы информации в непромышленной сфере и экономике: сб. тр. - Воронеж, 2005. - Вып. 10.
Кобак В.Г. Сравнение алгоритмов распределения несвязанных задач в функционально неоднородных системах (статья) // Математические методы в технике и технологиях - ММТТ-18: сб. тp. XVIII Междунар. науч. конф. / РГАСХМ.-Ростов н/Д, 2005. - Т. 2, секц. 2.
Кобак В.Г. О выборе алгоритмов решения минимаксной задачи однородной двухприборной системы обслуживания (статья) // Нейдорф Р. А. // Научное знание: новые реалии: межвуз. сб. - М.: Учеб. литература, 2005.
. Кобак В.Г. Взаимосвязь минимаксного и квадратического критериев в однородной трехприборной системе (статья) // Нейдорф Р.А. // Информатика и системы управления. - 2005. - №2.
Кобак В.Г. Модификация алгоритма Алексеева для систем с избирательными свойствами приборов (статья) // Нейдорф Р.А, Федоров С.Е. // Математические методы в технике и технологиях - ММТТ-19: сб. тp.XIX Междунар. науч. конф./ ВГТА. - Воронеж, 2006. - Т. 2, секц. 2.
Кобак В.Г. Сравнительный анализ списочных алгоритмов решения минимаксной задачи (статья) // Будиловский Д.М. // Математические методы в технике и технологиях - ММТТ-19: сб. тp.XIX Междунар. науч. конф./ ВГТА. - Воронеж, 2006. - Т. 2, секц. 2.
Кобак В.Г. Генетический подход к решению минимаксной задачи в однородных системах обработки информации (статья) // Будиловский Д.М. // Математические методы в технике и технологиях - ММТТ-19: сб. тp.XIX Междунар. науч. конф./ ВГТА. - Воронеж, 2006. - Т. 2, секц. 2.
Кобак В.Г. Оценка точности приближенного алгоритма при решении минимаксной задачи теории расписаний (статья) // Нейдорф Р.А., Красный Д.Г.// Математические методы в технике и технологиях - ММТТ-20: сб. тp.XX Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 2, секц. 2.
Кобак В.Г. Сравнительный анализ алгоритмов решения задачи планирования в однородных вычислительных системах (статья) // Иванов М.С. // Математические методы в технике и технологиях - ММТТ-20: сб. тp.XX Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 2, секц. 2.
Кобак В.Г. Анализ работы алгоритма Романовского с использованием различных подходов к формированию верхней и нижней границ (статья) // Титов Д.В. // Математические методы в технике и технологиях - ММТТ-20: сб. тp.XX Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 2, секц. 2.
Кобак В.Г. Условия несовпадений оптимумов распределений по минимаксному и квадратичному критериям (статья) // Математические методы в технике и технологиях - ММТТ-20: сб. тp.XX Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 2, секц. 2.
Кобак В.Г. Взаимосвязь критериев эффективности при решении однородной минимаксной задачи на трех приборах // Кобак В.Г. // Математические методы в технике и технологиях - ММТТ-20: сб. тp.XX Междунар. науч. конф./ ВГТА. - Ярославль, 2007. - Т. 10.
Кобак В.Г. Исследование принципа лэлитизма генетического алгоритма решения минимаксной задачи в однородных системах обработки информации // Нейдорф Р.А., Будиловский Д. М. // Кисловодск, 2007.
Кобак В.Г. Модификация алгоритма распределения в неоднородной системе обработки информации // Нейдорф Р.А., Красный Д.Г. // Кисловодск, 2007.
Кобак В.Г. Задача минимизации времени выполнения параллельных технологических операций в машиностроении // Нейдорф Р.А. // Труды 8 международной научно-технической конференции по динамике технологических систем, Том 2.
Кобак В.Г. Официальная регистрация программы для ЭВМ ФГУ ФИПС Система для проведения исследований в области задач построения расписаний // Нейдорф Р.А., Будиловский Д. М. // №2007612127 от 23.05.2007 г.
Кобак В.Г. Методологические проблемы теории расписаний // Нейдорф Р.А. // Сборник науч. Статей. Ростов на Дону: ДГТУ, Таганрог: ТТИ ЮФУ, 2007.
Кобак В.Г. Анализ условий минимального отличия квадратичного и минимаксного критериев в однородных трехприборных системах // Кобак В.В. // Сборник науч. Статей. Ростов на Дону: ДГТУ, Таганрог: ТТИ ЮФУ, 2007.
Кобак В.Г. Исследование работы алгоритма Романовского с использованием списочных алгоритмов при формировании верхней границы // Титов Д.В. // Сборник науч. Статей. Ростов на Дону: ДГТУ, Таганрог: ТТИ ЮФУ, 2007.
. Кобак В.Г. О возможности построения алгоритмов приближенного решения минимаксных задач в неоднородных средах // Красный Д.Г. // Сборник науч. Статей. Ростов на Дону: ДГТУ, Таганрог: ТТИ ЮФУ, 2007.
Кобак В.Г. Анализ эффективности генетического алгоритма при решении задач теории расписаний большой размерности // Будиловский Д. М. // Сборник науч. Статей. Ростов на Дону: ДГТУ, Таганрог: ТТИ ЮФУ, 2007.
Кобак В.Г. Практическое использование метода псевдократной загрузки // Нейдорф Р.А., Красный Д.Г. // Математические методы в технике и технологиях - ММТТ-21: сб. тp. Междунар. науч. конф./ ВГТА. - Саратов, 2008. - Т. 5.
Кобак В.Г. Исследование турнирного отбора в генетическом алгоритме для решения однородной минимаксной задачи // Титов Д.В. // Математические методы в технике и технологиях - ММТТ-21: сб. тp. Междунар. науч. конф./ ВГТА. - Саратов, 2008. - Т. 5.
Кобак В.Г. Сравнение генетического и списочного алгоритмов при решении распределительной задачи по квадратичному критерию // Кобак В.В., Будиловский Д. М. // Математические методы в технике и технологиях - ММТТ-21: сб. тp. Междунар. науч. конф./ ВГТА. - Саратов, 2008. - Т. 6.

__________________________________________________________

В набор 30.09.2008. В печать 26.09.2008.

Объем 2,7 усл.п.л., 2,5 уч.-изд.л. Офсет. Формат 60×84/16.

Бумага тип №3. Заказ № 534. Тираж 100.

___________________________________________________________

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

Адрес университета и полиграфического предприятия:

344010, г.Ростов-на-Дону, пл.Гагарина,1.

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

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

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

Авторефераты по всем темам >> Авторефераты по техническим специальностям

Blog