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

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоверность результатов исследования. Достигается за счёт корректного применения системного анализа, методов математического анализа и моделирования, их статистической обработки. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил более опытов. Минимальный статистически представительный эксперимент обеспечивался не менее, чем 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)

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

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

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

Наряду со свойствами распределений общего вида, которые в виду высокой комбинаторной сложности задач не позволяет получить сколько-нибудь существенные аналитические результаты для приборных систем размерности больше трех, в работе исследуются частные случаи, но часто встречающиеся на практике, варианты распределения. Так, рассмотрение трёхприборных систем с «выделенным монолитом» с позиций оценки связанности оптимумов критериев (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).

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

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

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

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

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

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

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

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



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

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

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

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

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

...