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

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

Красовский Дмитрий Владимирович

АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ БЕЗ ПРЕРЫВАНИЙ

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

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

Москва - 2007

□ ОЗОТ1213

003071213

Работа выполнена на кафедре математических основ управления Московского физико-технического института (государственного университета)

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

кандидат физико-математических наук, доцент Фуругян Меран Габибуллаевич

Официальные оппоненты доктор физико-математических наук Андрианов Александр Николаевич доктор технических наук, профессор Сигал Израиль Хаимович

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

Научно-исследовательский Институт Системных Исследований Российской Академии Наук

Защита состоится '¿¿¿^ Л^гиЯ _ 2007 г в ^ час

на заседании диссертационного совета К212 156 02 при Московском физико-техническом институте (государственном университете) по адресу 141700, Московская обл, г Долгопрудный, Институтский пер, 9, 903 КПМ

С диссертацией можно ознакомиться в библиотеке МФТЩГУ) Автореферат разослан ^уи^СсХ_ 2007 г

Ученый секретарь диссертационного совета к.ф -м н.

ОС Федько

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

Актуальность и характеристики задачи

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

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

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

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

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

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

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

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

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

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

Цели и новизна работы

Целями настоящей диссертационной работы являются

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

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

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

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

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

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

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

Методы исследований

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

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

Практическая ценность работы

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

Апробация работы

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

- XLV, XLVII и IL научных конференциях Московского физико-технического института (государственного университета), (Долгопрудный, 2002,2004,2006),

- X, XI и XII международных конференциях "Проблемы управления безопасностью сложных систем" (Москва, 2002,2003,2004),

- IV международной конференции по исследованию операций (Москва, 2004),

- II Всероссийской научной конференции «Методы и средства обработки информацию) (Москва, 2005);

- научных семинарах кафедры математических основ управления Московского физико-технического института (государственного университета),

- научных семинарах сектора проектирования систем реального времени Вычислительного центра им А А Дородницына Российской Академии Наук

Публикации

По материалам диссертации опубликовано 12 печатных работ, в том числе две - в ведущих научных журналах, рекомендованных ВАК РФ Список работ приведен в конце автореферата

Структура и объем работы

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

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

Во введении формулируется тема диссертации, обосновывается ее актуальность, формулируется ее цель, научная новизна, полученные результаты и структура диссертации

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

В рассматриваемой модели ресурсы состоят из набора процессоров Р-={ /¡, ,Рт} В зависимости от особенностей задачи они являются либо идентичными, либо одинаковыми только по функциональным возможностям, но разными по быстродействию, либо разными как по возможностям, так и по быстродействию

Система заданий " '

Общая система заданий для заданного набора ресурсов может быть определена как система 5= {Т, ||г1|} следующим образом

• Т = {Т\, ,Т„} есть набор работ, подлежащих выполнению,

• |] тц || представляет собой целочисленную матрицу размера пхт,

элемент которойгц>0 есть время выполнения работы Т, (1<г<л) на процессоре (15у <т) Будем полагать, чтогу = <», если работа Т, не может быть выполнена на процессоре Рр и что для каждого I существует, по крайней мере, одно у, для которого тд <м В случае, когда все процессоры идентичны, г, обозначает время выполнения Т, на любом процессоре Показатель эффективности расписаний

Будем рассматривать один из основных показателей эффективности, а именно, длину расписания, или максимальное время завершения,

В = тах{/'(5)},

где - сумма длительностей работ назначенных нау-й процессор

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

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

- математическое программирование,

- динамическое программирование,

- метод ветвей и границ,

- быстрые эвристические алгоритмы,

- метод имитации отжига,

- поиск с запретами (Табу-поиск),

- нейронные сети,

- генетические и эволюционные алгоритмы

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

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

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

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

Алгоритм «Процессор с ранним окончанием первым» (ПРОП) Процедура работы этого алгоритма состоит в следующем На к-м шаге распределяемая работа (ее индекс к) назначается на тот процессор, суммарное время выполнения работ на котором с учетом данной работы минимальное Иными словами, минимизируется по у выражение {В'к ] + ),

где В'к_х - суммарное время выполнения работ, назначенных на у-й процессор на первых к-1 шагах, Алгоритмическая сложность рассматриваемой эвристики составляет 0(пт)

Вероятностный алгоритм ("В А) Запишем задачу в следующем виде

2=В —> тт

Поясним смысл такой интерпретации Величина х^ е {0,1} есть

показатель того, будет ли выполнена работа Г, на процессоре Р} Так, если хл= 1, го в соответствующем расписании работа Т, будет выполнена на процессоре Р/, если хл= 0, то работа Т, не будет выполняться на процессоре Р} При этом первое ограничение означает, что каждая работа должна быть выполнена, а наложение условия целочисленности на х]1 означает, что работа будет выполнена только на одном процессоре (расписание без прерываний) Второе условие — это ограничение на длину расписания, а четвертое условие означает, что задача состоит в минимизации длины расписания

При работе алгоритма сначала находится решение релаксационной задачи линейного программирования, в которой х е[0, 1] Пусть получена

матрица с элементами хр Затем найдем такую целочисленную матрицу х, аппроксимирующую хл , что Р(х,1 = 1) = хр и выполняется первое из наложенных ограничений Это можно сделать следующим образом Будем заполнять элементы матрицы ||д;7,|| по строкам для каждого у будем брать последовательно элементы хР с г от 1 до и, полагая X/, равным 1 с вероятностью х,,* Если некоторый элемент хг., полученный таким образом, окажется равным 1, то остальные элементы строки (элементы с тем же значением у) полагаем равными 0

алгоритмическая сложность алгоритма есть 0{птк), где к - свободный параметр алгоритма В этой оценке не учитывается алгоритмическая сложность решения релаксационной задачи, которая зависит от выбранного

2>„=1,/ = 1, >">

*„е{0,1Ь

В работе доказано, что с вероятностью Р„(к)> 1-

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

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

Рис 1 Фазовый потрет Р„(к)

Псевдополиномиальный алгоритм с поиском в ширину ШАГП1Г) Дадим следующую интерпретацию рассматриваемой задачи

и -*

Необходимо решить оптимизационную задачу вида ^р, ->пип , где

/•1

- >

р,=(0, ,тл, ,0) - /я-мерный вектор В теории оптимизации задача в подобной формулировке называется «задачей об упаковке» Однако несложно заметить, что «задача об упаковке» имеет однозначное соответствие с рассматриваемой задачей достаточно провести соответствие

вектора р1 - (0, ,т1к, ,0) с работой Т„ где к - номер процессора, на который назначена эта работа Работу алгоритма, решающего поставленную задачу, опишем следующим образом Вычислим величину В, которую будем называть директивным сроком Число В можно получить, например, с помощью описанных выше 'алгоритмов1 ПРОП или ВА Затем будем

' Для произвольного вектора а = ,Ят), |а| = тахак - величина максимальной компоненты

рассматривать т-мерный куб со стороной В (в векторной интерпретации)

-* я

Необходимо выбрать вектора р1 так, чтобы каждая компонента вектора £ р,

не превосходила В Под выбором вектора /> будем понимать выбор процессора, на который назначена работа Т» что однозначно задает вектор Выбор осуществляем путем построения множества точек яг-мерного пространства, для каждой из которых на 1-й уровне проверяем, принадлежит ли точка »2-мерному кубу со стороной В (рис 2) Если условие не выполнено, то точка исключается из дальнейшего рассмотрения

Рис 2 Векторная интерпретация псевдополиномиального алгоритма

В работе доказано, что вычислительная сложность алгоритма есть 0(т2Вт) При фиксированном числе процессоров т алгоритм является псевдополиномиальным с алгоритмической сложностью 0(Вт)

Псевдополиномиальный алгоритм с поиском в глубину (ПАПП Псевдополиномиальный алгоритм с поиском в глубину отличается от рассмотренного в предыдущем разделе алгоритма следующим Вместо построения полного дерева решений, укладывающегося в /и-мерный куб со стороной В, находится одно решение, удовлетворяющее директивному сроку Затем производится уточнение директивного срока, например путем половинного деления Начальный интервал возможных значений В (В, В),

либо быстрым алгоритмом (например, ПРОП или ВА) Затем вычисляется величина В^=(В + В)/2, которая используется в качестве следующего значения директивного срока. В случае если решение с таким директивным

1-1

где 5 = шах

а В - значение, полученное каким-

сроком найдено, то директивный срок для последующей итерации вычисляется по формуле В2~(В1+В)/2, в обратном случае по формуле Вг=(В+В{)12, итд Таким образом, этот алгоритм является итерационным В худшем случае каждая итерация алгоритма может иметь такую же сложность, как и алгоритм с поиском в ширину, однако в среднем каждая итерация этого алгоритма работает существенно быстрее (это подтверждается экспериментальными данными) Представленный алгоритм обладает также тем преимуществом, что с его помощью можно находить как точные решения (для целочисленных задач), так и приближенные решения с заданной точностью Для этого следует остановить работу алгоритма при разности между верхней и нижней оценками, не превосходящей требуемой точности

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

Повторное элементарное агрегирование

Элементарное агпегиропание

Агрегирование заданий Решение .подзадач Исходный набор заданий и декомпозиция

Рис 4 Процесс агрегирования

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

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

2 Длительности работ в одной подзадаче должны быть близки

к

¿> - У шах I т. - г I - мало 1'

3 Время проведения декомпозиции достаточно мало

Работы сортировались по длительности Полученный таким образом набор разбивался на равные по количеству работ поднаборы (по числу подзадач, которое являлось параметром декомпозиции) В случае если количество работ в задаче не было кратно числу подзадач, работы «на стыке» добавлялись в поднабор в соответствии с минимизацией 5

Переборный Агрегирующий Алгоритм (ПАА)

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

Многоуровневый Агрегирующий Алгоритм (МАА) Проводится декомпозиция задачи упорядочения п работ по т процессорам на подзадач После решения подзадач (переборным алгоритмом) и агрегирования получим задачу упорядочения »?.9(1) работ по т процессорам Полученная задача снова декомпозируется на подзадачи, которые решаются аналогично Когда, после некоторого количества повторений, мы получим задачу упорядочения т.ч(ы ' работ по т процессорам, время решения которой приемлемо, назначение работ проводится в последний раз Таким образом, в этом методе число управляющих переменных составляет N Возможность их варьирования позволяет уменьшить погрешность метода, но увеличивает его алгоритмическую сложность В работе приведены результаты экспериментов, в которых ,у(0Цу, 5('н ,=[.?<1)/2]

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

Утверждение 4 11

С помощью ПАПГ можно найти решение с погрешностью е

В-В* В*

за время 0\ log

В-В еВ ,

+ 1

т

\B-ebJ

, если еВ > 1 и за время

о{\о^(в-В^т1 В™^, если еВ< 1, где В - длина расписания, найденного

ПАПГ, В* - длина оптимального расписания, В и В - первоначальные верхняя и нижняя оценки Утверждение 4 1 2

За время О

Т

V®/

т2В

с помощью ПАПГ можно найти

расписание длиной В, такое, что —В<В*<В, где В* — длина оптимального

расписания

Утверждение 4 2

С вероятностью Р„(к)>

1-Й--

т

за время 0{птк) с помощью

1

вероятностного алгоритма можно с вероятностью, большей 1--, найти

п

^_* / ^'

решение с погрешностью е = ——— < £>| В*,— \, где

В*

п

• о\в*,-\<

е\п п

В* 1п

Г е1пи^|

при В* < 1п п

Утверждение 4 3 1

Погрешность £ расписания, получаемого алгоритмом ПРОП,

в-в, . _

составляет е =-=<т-1, где т - число процессоров, В - длина

В

расписания,

полученного

алгоритмом

ПРОП,

Г ЕттгТ

В = тах-1тах^ш1пг,^, —-- нижняя оценка длины оптимального

расписания

Утверждение 4 3 2

При решении задачи составления расписания на идентичных процессорах, погрешность расписания е, получаемого алгоритмом ПРОП,

составляет £ = —--<1, где т - число процессоров, В - расписание,

В *

полученное алгоритмом ПРОП, В*— длина оптимального расписания Утверждение 4 4

При решении задачи составления расписания -работ на идентичных процессорах с использованием алгоритма СДРП погрешность е получаемого

В-В*

расписания составляет в =-< 1, где В — длина полученного расписания,

В*

В* - длина оптимального расписания

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

При доказательстве утверждения 5 1 предполагается, что длительности выполнения работ задаются зависимостью г, = г, + (г —Х)с1, с1> 0, \ <1<п Утверждение 5 1

При использовании алгоритма СДРП длительность полученного расписания задается формулой

В = [п/2т](2гп +й?-2отй?[и/2от]), при п=2кт, где к- целое число, В = [п/2т](2тп + й — 2тс1[п!2т]) + тп-2тс1[п/2т], при п — [п/2т]2т < т, В = [и / 2га](2г„ +с1- 2тй\п / 2т]) + 2т„ - 2тс1(2[п / 2т\ +1) + (1, при

п-[п/2т]2т> т

2г ~с!(п-1)

Следствие Пусть АВ-В-В', где В' = —— = —=-п Тогда

т 2т

АВ=0, при п=2тк,

АВ = ([п/2т\ - п/2т){2тп + <5?) + т, - 2т[п/2т]с1([п/2т] +1) + йпг 1(2т), при п-[п12т\2т<т,

ЛВ = 2([п/2т]-п/2т + 1)т„+([п/2т] - п / 2 т)<1 - 6 тс1\п /2 т] + +с1п2 /(2т) - 2тс1 + с1, при и - [п / 2т]2т > т при п-[п12т]2т>т

При доказательстве утверждения 5 2 предполагается, что длительности выполнения работ задаются зависимостью т^й^йх^^^т^й, где с/ натуральные числа Утверждение 5 2

При использовании алгоритма СДРП при выполнении условия 2[n/2m](d — d) < т, длина полученного расписания удовлетворяет соотношению B(d)<B<B(d), где B(d) и B(d) длины расписаний, полученных алгоритмом СДРП при решении задачи 5 1с разностью арифметической прогрессии d = d_ и d = d соответственно Утверждение 5 3

В случае фиксированного числа произвольных процессоров m задача составления расписания без прерываний с пустым отношением предшествования (K/w||Cmax) является псевдополиномиально разрешимой.

Необходимо отметить, что до данного момента не был определен характер NP-трудности рассматриваемой задачи (не было определено, является ли задача NP-трудной в сильном или NP-трудной в обычном смысле, т е псевдополиномиально разрешимой) Наиболее общая формулировка задачи составления расписания, для которой был известен псевдополиномиальный алгоритм, описывает распределение работ по фиксированному числу процессоров, которые могут различаться по быстродействию, по не по функциональным возможностям, при этом 2-ая работа становится доступна к назначению после некоторого момента времени г, (0/я|г,|Стах) Формулировка задачи, используемая в утверждении 5 3 предполагает более общий случай произвольных процессоров, однако, не учитывает времена, когда работы становятся доступными к назначению Определение того факта, что NP-трудная задача является псевдополиномиально разрешимой важно с практической точки зрения. Еще Гэри и Джонсон (1979) отмечают «Псевдополиномиальный алгоритм показывает «экспоненциальное поведение» только в случаях, содержащих «экспоненциально большие» величины, что достаточно редко встречается в задачах, в которых мы заинтересованы Таким образом, алгоритмы такого типа могут служить нашим целям также хорошо, как и полиномиальные алгоритмы»

В шестой главе приводится описание двух параллельных алгоритмов составления расписания

Комбинированный псевдополиномиальный алгоритм Для решения задачи составления расписаний большой размерности предлагается следующий алгоритм С помощью эвристического алгоритма строится расписание, длина которого Во берется за оценку сверху длины итогового расписания На следующем шаге проводится декомпозиция задачи на подзадачи в соответствии с полученным расписанием Для этого проводится разбиение процессоров на группы с некоторым задаваемым параметром М(Мравно количеству групп, на которое разбивается множество процессоров) таким образом, что в первую группу попадает [т!2М\ наиболее загруженных процессоров (суммарное время выполнения работ, на которых наибольшее), и столько же наименее загруженных Аналошчно строятся остальные группы из оставшихся процессоров Затем производится

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

Параллельный псевдополиномиальный алгоритм с поиском в глубину Опишем работу псевдополиномиального алгоритма поиска в глубину с использованием параллельного вычислительного кластера из <7+1 процессоров Будем использовать один из процессоров кластера в качестве управляющего, а в качестве стратегии распределения работ использовать метод выделяемых вершин Управляющий процессор строит дерево решения до уровня «о = (наименьшее целое, большее или равное \о%тд), т.е

производит назначение первых п0 работ на процессоры При этом количество концевых вершин дерева решений X (соответствующих возможным расписаниям распределенных работ) больше или равно д Будем предполагать следующее

- Порядок выбора первых работ не важен и не влияет на получение окончательного решения

- В случае, если X > из полученных концевых вершин йыбираются ц наиболее перспективных для дальнейшего решения Способ определения перспективности следующий Для каждой из X вершин определяется задача упорядочения оставшихся «-«о работ по т процессорам Для каждой из задач определяется нижняя и верхняя оценки длины расписания Нижняя оценка вычисляется путем решения релаксационной задачи линейного программирования (эта оценка заведомо не хуже аналитической,

Г , , Е™пг»1

вычисляемой по формуле Б = тах<тах|ттг-,^, --М. Верхняя

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

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

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

- В случае, если мощность множества активных вершин меньше д, проводится дополнительное ветвление до уровня щ + 1, вычисляется новый рекорд и снова строится множества активных вершин

Полученные д наиболее перспективных активных-вершин (или все полученные, если выделяются управляющим процессором рабочим

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

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

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

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

обладают особенностью, что с ростом отношения min растет и погрешность получаемого решения. Алгоритмы ВА и ПАПГ могут использоваться в виде пакета прикладных алгоритмов для решения практически любых задач: на входах со сравнительно малым числом задач (а следовательно большим отношением min) ПАШ" достаточно быстро улучшает решение, полученное ВА, до оптимума или до решения с гарантированной заданной точностью. При решении задач с большим числом работ, когда получение точного решения невозможно, использование ВА оправдано за счет малой погрешности получаемого расписания.

На диаграммах 1, 2 и 3 приводятся время работы алгоритмов и погрешность получаемого расписания при решении задачи составления расписания на идентичных процессорах. На диаграмме 1 приводятся результаты экспериментов при решении задачи, длительности работ в которой задавались формулой г, =/?-?'+], / = 1,и; на диаграмме 2 — формулой г, = п - i +1 + [1.2""'"' ], i = l,n; на диаграмме 3 приводятся результаты экспериментов при решении задачи, длительности работ в которой задавались с помошью программного генератора случайных чисел, позволяющего получать псевдослучайные числа с равномерным распределением на отрезке [1, 1000]. На диаграмме 4 приводится время работы алгоритмов, а на диаграмме 5 погрешность получаемого расписания при решении задачи составления расписания на произвольных процессорах (длительности работ также задавались в помощью генератора случайных чисел).

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

| j 1 i

.1 .1. .

тт К|а|||«|вШ|1|| 1 ite ;,t ■ j» 1 b*lo&J I N »до | «-«.«-mg 1

[qПогрешность выполнения [

Диаграмма 2, Результаты для длительностей работ, заданных геометрической профессией

ЕЬ

В.

ЩдХЯ

1Г1! з и! / |У1Т! 511 !¥ 1Т|Т| 1Г I

112

"I

Диаграмма 3. Статистические результаты

В Погреилость ■ Время выполнения

Диаграмма 4. Время работы алгоритмов составления расписания для произвольных процессоров

бремя составления расписания 1000 ООО чс П1ТН^*|ии—«ч»и«мчм—ни щчиничмтипни и . '

100000 мс

10 000 мс

1 ООО мс

1

100 мс 10

220 МС 320 000 мс 2 5бсмсв

103 «с 59 000 мс 1 840 мс

13 МС 120мс

20 мс 1 430 ИГ.

■К

183 мс 76 600 мс 2 040 мс

42,(1 ис 55 660 мс

63 700 мс

»ПРОПЛ Ш БЛ, 1 ¡П ПАПу ; □ мио. 1 1

720 мс

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

Погрешность расписания

а проп. е! 18,2% 14,6% 14,2% 13.6% 25.1% 17,6%

■ ВА. в 6.1% 3.2% 31%..... 0.2% 0,1% 46.3%

п ПАГТ. е Ь.0% Г 0.0% 2,в% 0,0%

□ МИО. е 12,6% ТзТ%" 16.4% 12,3% " 22.9% " 46,3%

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ:

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

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

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

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

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

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

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

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

1 Гончар ДР, Гуз ДС, Красовский ДВ, Фуругян МГ Эффективные алгоритмы планирования вычислений в многопроцессорных системах // Проблемы управления безопасностью сложных систем Труды 10-й международной конференции Книга 2 /ИПУ РАН - М, 2002 — С 207211

2 Красовский ДВ, Фуругян МГ Комплексное применение методов дискретной оптимизации при решении задач минимаксной теории расписаний // МФТИ — М, 2003 «Моделирование и обработка информации» - С 96-103

3 Гуз ДС, Красовский ДВ, Фуругян МГ Некоторые алгоритмы составления расписаний в многопроцессорных системах //Проблемы управления безопасностью сложных систем Труды 11-й международной конференции /ИПУ РАН - М, 2003 - С 12-14

4 Гуз ДС, Красовский ДВ, Фуругян МГ Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени / ВЦ РАН - М , 2004 - 65 с

5 Guz D, Krasovskiy D, Furugian M Effective scheduling algorithms for multiprocessor real-time systems //Proceedings of IV Moscow International Conference on Operations Research /ВЦ PAH - M , 2004 - С 100-103

6 Гуз ДС, Красовский Д В, Фуругян МГ Некоторые алгоритмы анализа многопроцессорных систем реального времени / ВЦ РАН - М , 2005 -42 с

7. Красовский Д В Решение задачи составления оптимального расписания без прерываний на произвольных процессорах с использованием вероятностного алгоритма // Современные проблемы фундаментальных и прикладных наук — общая и прикладная физика Сборник трудов 48-й научной конференции МФТИ / МФТИ - М, 2005, -С 76-78

8 Гуз ДС, Красовский ДВ, Фуругян МГ Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени // Методы и средства обработки информации Труды второй всероссийской научной конференции — Москва, издательский отдел факультета ВМиК МГУ 2005, - С 540-545

9 Красовский Д В , Фуругян МГ Агрегирование в задаче составления оптимального расписания для многопроцессорных АСУ // Автоматика и телемеханика —2006 —№12-С 205-212

10 Красовский ДВ, Фуругян МГ Псевдополиномиальные алгоритмы упорядочения работ без прерываний по произвольным процессорам // Вестник Московского университета, сер 15, Вычислительная математика и кибернетика, 2006, № 4, - С 25-29

11 Красовский Д В Алгоритм параллельного планирования работы многопроцессорных систем большой размерности // Современные проблемы фундаментальных и прикладных наук - общая и прикладная физика Сборник трудов 49-й научной конференции МФТИ, Т II / МФТИ-М 2006 -С 79-80 .

12 Красовский ДБ, Фуругян МГ Некоторые алгоритмы составления многопроцессорных расписаний с использованием параллельных вычислений / ВЦ РАН - М , 2006 - 27 с

ЛИЧНЫЙ ВКЛАД

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

Красовский Дмитрий Владимирович

АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧИ СОСТАВЛЕНИЯ ОПТИМАЛЬНОГО РАСПИСАНИЯ БЕЗ ПРЕРЫВАНИЙ

Подписано в печать 12.04 07 Формат 60x84 1/16 Бумага офсетная Уел печ л 1,0. Тираж 70 экз Заказ №327

Московский физико-технический институт (государственный университет) НИЧ МФТИ

141700, Московская обл., Долгопрудный, Институтский пер, 9

Введение

Глава 1. Основные понятия и формальная постановка задачи

1.1. Модель

1.2. Оценка погрешности и времени составления расписания

1.3. Задачи большой размерности

Глава 2. Характеристика задачи и существующие методы ее решения

2.1. Результаты для задач минимизации длины расписания

2.2. Оценки характеристик алгоритмов составления расписаний

2.3. Анализ существующих точных и приближенных алгоритмов

2.4. Анализ существующих параллельных стратегий

Глава 3. Алгоритмы составления расписания без прерываний

3.1. Алгоритм «Процессор с ранним окончанием первым»

3.2. Вероятностный алгоритм

3.3. Псевдополиномиальные алгоритмы

3.3.1. Различные интерпретации псевдополиномиальных алгоритмов

3.3.2. Псевдополиномиальный алгоритм с поиском в ширину

3.3.3. Псевдополиномиальный алгоритм с поиском в глубину

3.4. Метод агрегирования

3.4.1. Формальное описание

3.4.2. Задача составления расписания п работ на ш идентичных процессорах

3.4.3. Вспомогательные алгоритмы

3.4.4. Агрегирующие алгоритмы

3.5. Анализ возможности совместного использования методики агрегирования с другими алгоритмами

Глава 4. Алгоритмы с гарантированной точностью

4.1. Псевдополиномиальный алгоритм с поиском в глубину

4.2. Вероятностный алгоритм

4.3. Алгоритм «Процессор с ранним окончанием первым»

4.4. Алгоритм «Самая длинная работа первой»

Глава 5. Результаты для некоторых частных случаев

5.1. Длительности работ, заданные арифметической прогрессией

5.2. Длительности работ, близкие к арифметической прогрессии

5.3. Фиксированное число процессоров

Глава 6. Параллельное выполнение вычислений

6.1. Комбинированный псевдополиномиальный алгоритм

6.2. Параллельное построение дерева решения

Глава 7. Результаты экспериментов

7.1. Экспериментальная система78

7.2. Таблицы и графики

Актуальность и характеристики задачи

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

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

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

Исторически появлению дискретных методов оптимизации предшествовало развитие методов линейного программирования. Высокая вычислительная производительность этих методов позволила предполагать, что на их основе могут быть разработаны эффективные методы решения дискретных задач оптимизации. Однако вычислительные эксперименты не подтвердили это предположение. Принципиальные трудности решения дискретных задач показала и теория вычислительной сложности алгоритмов [1, 2, 3, 4]. В соответствии с этой теорией оценка эффективности производится по наихудшему случаю. Так как для большинства дискретных задач оптимизации в наихудшем случае не известен точный алгоритм кроме перебора всех или почти всех вариантов, то полученные оценки являются неудовлетворительными с точки зрения практического использования.

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

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

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

Понижение размерности системы приводит также к уменьшению накладных расходов на организацию обслуживания, которые, например, согласно некоторым исследованиям [5] в вычислительных системах реального времени достигают 70% (в отдельных случаях и выше) времени работы центрального процессора.

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

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

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

Цели и новизна работы

Целями настоящей диссертационной работы являются:

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

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

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

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

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

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

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

Методы исследований

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

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

Практическая ценность работы

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

Апробация работы

Результаты диссертации и материалы исследований докладывались, обсуждались и получили одобрение специалистов на:

- ХЬУ, ХЬУИ и 1Ь научных конференциях Московского физикотехнического института (государственного университета),

Долгопрудный, 2002,2004,2006);

- X, XI и XII международных конференциях "Проблемы управления безопасностью сложных систем" (Москва, 2002, 2003,2004);

- IV международной конференции по исследованию операций (Москва, 2004);

- II Всероссийской научной конференции «Методы и средства обработки информации» (Москва, 2005);

- научных семинарах кафедры математических основ управления Московского физико-технического института (государственного университета);

- научных семинарах сектора проектирования систем реального времени Вычислительного центра им. А.А. Дородницына Российской Академии Наук.

По материалам диссертации опубликовано 12 печатных работ. Структура работы

Работа состоит из данного введения, семи глав и заключения. В главе 1 вводится формальная постановка и описание задачи. Формализуются термины, которые используются далее в работе. В главе 2 приводится анализ исследований рассматриваемого и смежных классов задач, проведенные другими учеными. Проводится исследование описанных в литературе алгоритмов, которые могут использоваться для рассматриваемого класса задач, приводятся их сильные и слабые стороны. Выделен ряд наиболее перспективных алгоритмов и методик, которые были использованы для сравнения с разработанными в рамках данной работы алгоритмами. Глава 3 посвящена алгоритмам, разработанным в рамках данной работы: их формальному описанию, определению алгоритмической сложности. В главе 4 для разработанных ¿--приближенных алгоритмов определяется и доказывается их гарантированная точность. Глава 5 посвящена некоторым интересным математическим фактам, относящимся к разработанным алгоритмам, которые были определены в процессе этой диссертационной работы. В главе 6 исследуется параллельный процесс построения расписания. В главе 7 собраны и структурированы все полученные вычислительные результаты, приводится описание системы, которая использовалась для проведения экспериментов.

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

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

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

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

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

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

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

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

По результатам работы состоялись 12 публикаций [60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71].

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

• разработка новых методик агрегирования для задачи составления расписаний в общей постановке (с произвольными процессорами);

• исследование новых стратегий распараллеливания псевдополиномиальных алгоритмов и применение их в других параллельных архитектурах;

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

Заключение

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

1. Ульман Дж. Полиномиально полные задачи составления расписаний // Operating Systems Review, 1973.

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

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

4. Brucker P. Scheduling algorithms, 2nd edition // Springer, Heidelberg, 1998.

5. Bondy J. L., Freeman D. N. Putting supervisory routines into hardware // North-Holland Publ. Co., 1977.

6. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование // ФИЗМАТЛИТ. 2002.

7. Хачатуров В.Р., Веселовский В.Е., Злотов A.B. и др. Комбинаторные методы и алгоритмы решения задач дискретной оптимизации большой размерности // М.: Наука, 2000.

8. Сигал ИХ. Параметризация и исследование некоторых задач дискретного программирования большой размерности // М.: Известия академии наук. Теория и системы управления, 2001, №2, С. 60-69.

9. Сигал ИХ. Параметризация ¿"-приближенных алгоритмов решения некоторых классов задач дискретной оптимизации большой размерности // М.: Известия академии наук. Теория и системы управления, 2002, №6, С. 63-72.

10. Сигал ИХ. Оценки параметров алгоритмов ветвей и границ для задач дискретной оптимизации большой размерности // М.: Известия академии наук. Теория и системы управления, 2005, №4, С. 96-101.

11. Baker К. R. Introduction to Sequencing and Scheduling // John Wiley and Sons, Inc., 1974.

12. Conway R., Maxwell W., Miller L. Theory of Scheduling // Addison Wesley Publishing Company, 1967.

13. Giffler В., Thompson G. Algorithms for solving production scheduling problems // Operations Research, 8(4):487-503,1960.

14. Растригин JI.A. Статистические методы поиска // M.: Наука, 1968.

15. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискрет, анализ и исслед. операций Сер. 2,2002. Т. 9, №2. С. 13-30.

16. Кочетов Ю, Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций Сер. 2,2003. Т. 10, № 1,С. 11-44.

17. Кочетов Ю.А., Столяр А.А. Использование чередующихся окрестностей для приближенного решения задачи календарного планирования с ограниченными ресурсами // Дискрет, анализ и исслед. операций Сер. 2,2003. Т. 10, № 2, С. 29-56

18. Tripathy A. School timetabling a case in large binary integer linear programming //Management Science, 30(2): 1473-1480, 1984.

19. Ciriani Т., Leachman R., editors. Optimizing in Industry: Mathematical Programming and Modeling Techniques in Practice I I John Wiley and Sons, Ltd., 1993.

20. Алексеев О.Г. Комплексное применение методов дискретной оптимизации//Наука, 1986.

21. Held М., Karp R. A dynamic programming approach to sequencing problem // SIAM, 1962.

22. Land A.H., and Doig A. G. An automatic method of solving discrete programming problems // Econometrica. v28 (1960), pp 497-520.

23. ЛиттлД.Ж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи коммивояжера // Экономика и математические методы, Т. 1, вып. 1,С. 90-107,1965.

24. Корбут А.А., Финкелъштейн Ю.Ю. Дискретное программирование // М. Наука. Гл. ред. физ.-мат. лит. 1969.

25. Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов // М.: Радио и связь, 1983.

26. Panwalkar S., Iskander W. A survey of scheduling rules // Operations Research. 25(1):45-61,1977.

27. Штовба С. Д. Муравьиные алгоритмы // ExponentaPro. Математика в приложениях, № 4(4), 2003.

28. Laarhoven P., Aarts Е., Lenstra J. Job Shop Scheduling by Simulated Annealing // Operations Research, 40(1):113-125,1992.

29. Shen С., Pao K, Yip P. Scheduling multiple job problems with guided evolutionary simulated annealing approach // Proceedings of the First IEEE Conference on Evolutionary Computations, pages 702-706,1994.

30. Glover F., Laguna M. Chapter 3: Tabu search // In Colin R. Reeves, editor, Modern Heuristics Techniques for Combinatorial Problems, Blackwell Scientific Publications, 1993.

31. Taillard E. Benchmarks for basic scheduling problems // European Journal of Operations Research, 64:278-285,1993.

32. Ross P., Hallam J. Lecture Notes on Connectionist Computing // Department of Artificial Intelligence, University of Edinburgh, 1993.

33. Hulle M. A goal programming network for mixed integer linear programming: A case study for the job-shop scheduling problem // International Journal of Neural Systems, 2(3):201-209,1991.

34. Меламед И.И. Нейронные сети и комбинаторная оптимизация // Автоматика и телемеханика, 11, С. 3-40,1994.

35. Костенко В.А., Смелянский Р.П., Трекин А.Г. Синтез структур вычислительных систем реального времени с использованием генетических алгоритмов // Программирование, 2000, № 5.

36. Трекин A.F. Структурный синтез вычислительной системы с помощью генетических алгоритмов: Дис. канд. физ.-мат. наук. М., 2002. 111 с.

37. Holland J.N. Adaptation in Natural and Artificial Systems // Ann Arbor, Michigan: Univ. of Michigan Press, 1975.

38. Michalewicz Z Genetic Algorithms + Data Structures = Evolution Programs // Third, Revised and Extended Edition, Springer, 1999.

39. Goldberg D.E. Genetic Algorithms in Search Optimization & Machine Learning // Addison Wesley, Reading, 1989.

40. Mataric M., Cliff D. Challenges in Evolving Controllers for Physical Robots // Robotics and autonomous systems, 19(1), p. 67-83, 1996.

41. Periaux J. and Winter G. editors. Genetic Algorithms in Engineering and Computer Science // John Wiley & Sons Ltd., 1995.

42. Come D., Fang H.-L., Mellish C. Solving the Modular Exam Scheduling Problem with Genetic Algorithms // DAI Research Paper №622.

43. Bierwirth C., Kopfer H., Mattfeld D. C., Rixen I. Genetic Algorithm based Scheduling in a Dynamic Manufacturing Environment // Proceedings of the IEEE Conf. on Evolutionary Computation, Perth, IEEE Press, 1995, p.439-443.

44. Daaldr J., Eklund P. W., Ohmori K. High-Level Synthesis Optimization with Genetic Algorithms // Proceedings of the 4th Pacific Rim International Conference on Artificial Intelligence, Cairns (Australia), 26-30 August 1996, p.276-287.

45. Кормен Т., Лейзерсон 4., Pueecm Р. Алгоритмы: построение и анализ // М.-.МЦНМО, 2001.

46. Посыпкин М.А., Сигал И.Х., Гамилъянова Н.Н. Алгоритмы параллельных вычислений для решения некоторых классов задач дискретной оптимизации. М.: ВЦ РАН, 2005.

47. Rao V. Nageshwara and Kumar V. Parallel depth-first search, part I: Implementation//International Journal of Parallel Programming, 1987,16 (6). P. 479-499.

48. Rao V. Nageshwara and Kumar V. Parallel depth-first search, part II: Analysis // International Journal of Parallel Programming, 1987,16(6). P. 501-519.

49. Kumar V., Grama A., Rao V. Nageshwara. Scalable Load balancing Techniques for Parallel Computers // Journal of Parallel and Distributed Computing, 1994,22(1). P. 60-79.

50. Gotlieb A. The NYU ultracomputer designing a MIMD, shared memory parallel processor // IEEE Transactions on Computers, February, 1983. P. 175- 189.

51. Тимошевская H. E. Параллельные методы обхода дереваЛ Математическое моделирование. 2004,16(4). С.105-114.

52. Kouichi Kimura, Ichiyoshi Nobuyuki. Probabilistic analysis of the efficiency of the dynamic load distribution // Sixth Distributed Memory Computing Conference Proceedings, 1991. P. 145-152.

53. Shu W., Kale L. V. A dynamic scheduling strategy for the chare-kernel system // Supercomputing, 1989. P. 389-398.

54. Ranade A. Optimal speedup for backtrack search on butterfly network // ACM Symposium on Parallel Algorithms and Architectures, 1991. P. 40-48.

55. Raghavan R. Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs I I Journal of Computer and System Sciences 37,130-143,1988.

56. Сигал И.Х. Задача коммивояжера большой размерности // ВЦ АН СССР, 1986.

57. Трекин А.Г. Структурный синтез вычислительной системы с помощью генетических алгоритмов // Москва, 2002.

58. Michael J. Quinn. Designing Efficient Algorithms for Parallel Computers // McGraw-Hill, 1987.

59. Красовский Д.В., Фуругян М.Г. Комплексное применение методов дискретной оптимизации при решении задач минимаксной теории расписаний // МФТИ М., 2003. «Моделирование и обработка информации» - С. 96-103.

60. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Некоторые алгоритмы составления расписаний в многопроцессорных системах //Проблемы управления безопасностью сложных систем: Труды 11-й международной конференции /ИПУ РАН. М., 2003 - С. 12-14.

61. Гуз Д.С., Красовский Д.В., Фуругян М.Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени / ВЦ РАН. М., 2004. - 65 с.

62. Guz D., Krasovskiy D., Furugian M. Effective scheduling algorithms for multiprocessor real-time systems //Proceedings of IV Moscow International Conference on Operations Research /ВЦ PAH. M., 2004 - C. 100-103.

63. Гуз Д.С., Красовский Д. В., Фуругян М.Г. Некоторые алгоритмы анализа многопроцессорных систем реального времени / ВЦ РАН. М., 2005. -42 с.

64. Красовский Д. В. Решение задачи составления оптимального расписания без прерываний на произвольных процессорах с использованием вероятностного алгоритма // Современные проблемы фундаментальных и прикладных наук общая и прикладная физика:

65. Сборник трудов 48-й научной конференции МФТИ / МФТИ М., 2005, -С. 76-78.

66. Красовский Д.В., Фуругян М.Г. Агрегирование в задаче составления оптимального расписания для многопроцессорных АСУ // Автоматика и телемеханика. 2006. - №12 - С. 205-212.

67. Красовский Д.В., Фуругян М.Г. Псевдополиномиальные алгоритмы упорядочения работ без прерываний по произвольным процессорам // Вестник Московского университета, сер. 15, Вычислительная математика и кибернетика, 2006, № 4, С. 25-29

68. Красовский Д.В., Фуругян М.Г. Некоторые алгоритмы составления многопроцессорных расписаний с использованием параллельных вычислений / ВЦ РАН. М., 2006. - 27 с.72. http://www.mathematik.uni-osnabrueck.de/research/OR/class/