Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки тема диссертации и автореферата по ВАК РФ 05.13.01, доктор технических наук Кобак, Валерий Григорьевич

• Кобак, Валерий Григорьевич
• доктор технических наук
• 2008

Оглавление диссертации доктор технических наук Кобак, Валерий Григорьевич

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.2.1. Введение

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Кобак, Валерий Григорьевич

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

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

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

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

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

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

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

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

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