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

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

005552363

Жикулин Артем Александрович

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

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

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

11 СЕН 2014

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

005552363

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

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

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

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

доктор технических наук, профессор Нейдорф Рудольф Анатольевич

Соколов Борис Владимирович, доктор технических наук, профессор, Заслуженный деятель науки РФ, ФГБУН Санкт-Петербургский институт информатики и автоматизации РАН, зам. директора по научной работе;

Алибеков Байрамбек Исаевич, доктор технических наук, доцент, ФГБОУ ВПО «Дагестанский государственный университет», профессор кафедры дискретной математики и информатики

ФГБУН Институт проблем точной механики и управления РАН

Защита состоится «9» октября 2014 года в 14-20 на заседании диссертационного совета Д 212.208.22 при ФГАОУ ВПО «Южный федеральный университет» (ЮФУ) по адресу: 347928, ГСП - 17А, Ростовская обл., г. Таганрог, пер. Некрасовский, 44, ауд. Д - 406.

С диссертацией можно ознакомиться в Зональной научной библиотеке ЮФУ по адресу: 344000, г. Ростов-на-Дону, ул. Зорге, 21ж.

Диссертация в электронном виде доступна по адресу:

http://hub.sfedu.ru/diss/anTiouncement/8d7ddel2-34ad-43b0-8eel-elcld0c26742/

Автореферат разослан « £ » 2014 г.

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

диссертационного совета Д 212.208.22, /^^У^ А.Н. Целых

доктор технических наук, профессор

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

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

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

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

Степень разработанности темы исследований. Исследованию проблем, связанных с решением распределительных задач теории расписаний, посвящены труды многих отечественных ученых, таких как Танаев B.C., Шкурба В.В., Романовский И.В., Алексеев О.Г., Головкин Б.А., Пашкеев

С.Д., Шафранский Я.М., Соколов Б.В., Португал В.М., Бирман И.Я., Еме-личев В.А., Комлик В.И., Алибеков Б.И., Лазарев A.A., Ларионов A.M., Майоров С.А., Нейдорф P.A., Кобак В.Г., Севастьянов C.B., Твердохлебов В.А., Кушников В.А., Резчиков А.Ф., Иващенко В.А., Охтилев М.Ю. и др. Не меньшее внимание исследованию данной проблемы уделяли и зарубежные коллеги: Беллман Р., Джонсон С.М., Джексон Дж.Р., Коффман Э.Г., Конвей Р.В., Максвелл В.Л., Миллер Л.В., Гэри М., Джонсон Д., Brucker P., Kelley J., Walker M., Krone M., Taxa X.A., Pinedo M.P., Blaze-wicz J. и многие другие.

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

В Южном регионе в выбранной для исследования области можно отметить работы этого направления Нейдорфа P.A. и Кобака В.Г., а также их учеников (Будиловского Д.М., Красного Д.Г., Титова Д.В.). Кобаком В.Г. под руководством проф. Нейдорфа P.A. защищена докторская диссертация на тему «Методология сопоставительно-критериальной аналитической оценки распределительных задач и средства ее программно-алгоритмической поддержки». Этой группой ученых предложено и решено много интересных задач различной направленности. Однако, проблема М'-полноты распределительной задачи по-прежнему не решена. Существующие точные алгоритмы решения РЗ, гарантирующие нахождение оптимума по заданному критерию, не обеспечивают решение многих за-дачза приемлемое время при их высокой размерности или неблагоприятном сочетании размеров заданий. Для решения таких РЗ используют быстрые приближенные алгоритмы, которые не гарантируют оптимум, но позволяют находить приемлемые по точности решения. Часто оценка у этих решений лучше, чем у решений, полученных точными алгоритмами за ограниченное время. Решения РЗ, найденные приближенными ал-

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

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

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

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

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

2. Разработать точный алгоритм решения ОРЗ с существенно повышенными по сравнению с алгоритмом Романовского (АР) ресурсно-временными характеристиками.

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

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

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

Основные научные результаты и положения, выносимые на защиту, и их научная новизна:

1. Разработан, концептуально обоснован и экспериментально проверен с использованием специально разработанного программного средства комбинационно модифицированный АР (КМАР), содержащий новый для АР механизм обеспечения комбинационной уникальности загрузки исполнителя при обходе ветвей дерева вариантов решений, что существенно повышает его быстродействие (в среднем в 5600 раз) с сохранением свойств точного оптимизационного алгоритма (с. 69-79). Например, в диапазоне от 4 до 8 исполнителей, и до 50 заданий выигрыш по времени решения составляет от 10- до 15000-кратного (с. 87-99), а при 3-х исполнителях может достигать 200000-кратного (с. 83-87).

2. Разработан, концептуально обоснован и экспериментально проверен структурно-модифицированный приближенный вариант КМАР - СМАР, новизна которого состоит во включении в АР алгоритмов формирования максимальной загрузки исполнителей во время перебора заданий и глубокого отката к первому исполнителю с целью дополнительного сокращения рассматриваемых вариантов решения задачи (с. 102-117). Это позволило получить ресурсно-временную результативность на 1-2 порядка выше, а в некоторых частных случаях и на 5 порядков выше, чем у КМАР при незначительном ухудшении точности решения ОРЗ (с. 117-153). Так, для задач с 2 исполнителями СМАР обеспечивает оптимум решения в 100% случаев, для 3-8 исполнителей и 12-31 распределяемых заданий - в основном от 75 до 100%, а в среднем в -98% случаев, при этом ошибка у неоптимальных решений оказывается в пределах 0,5 - 4% от значения оптимума (с. 117-128, с. 143-153). Для 3-5 исполнителей и 31-51 распределяемых заданий по имеющимся данным СМАР обеспечивает оптимум решения в 100% случаев (с. 128-143).

3. Разработаны, программно реализованы и экспериментально исследованы варианты селективно-перестановочных алгоритмов, новизна которых заключается во введении в известный алгоритм одинарных перестановок групповых мульти- и эквиперестановок (с. 166-174 и 186-190), существенно улучшающих точность решений ресурсно-ограниченных и приближенных алгоритмов. Они обеспечивают улучшение результатов СМАР по проценту оптимальных и приближенных к оптимальным решений от —47% до 100% в зависимости от конкретной размерности и структуры ОРЗ (с. 190-198).

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

Теоретическая значимость диссертационной работы:

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

2. Разработанная модификация КМАР - СМАР, понижающая его статус до приближенного, существенно расширяет область применения метода ветвей и границ в ОРЗ за счет повышения его быстродействия при возможности решать задачи теории расписаний и подобные им задачи дискретной оптимизации с высокой, достигающей 0,98, вероятностью получения оптимального решения.

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

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

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

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

1. Ресурсно-временная результативность точного решения ОРЗ повышена в среднем в 5600 раз (для некоторых частных задач до 200000), что на порядки уменьшает время решения как производственных, так и научно-исследовательских ОРЗ.

2. Обеспечена ресурсно-временная результативность решения ОРЗ на 1-2 порядка выше (в частных случаях на 5), чем у КМАР при ухудшении его точности не более 4% от оптимума, что обеспечивает уменьшение еще на несколько порядков времени решения практических задач, не требующих абсолютного оптимума.

3. Повышена точность работы селективно-перестановочного алгоритма приближенного решения ОРЗ введением мульти- и эквипереста-новок в среднем на 15%, а для некоторых частных случаев в ~2 раза, что повышает вероятность получения оптимальных и приближенных к ним быстрых решений ОРЗ.

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

5. Практическая проверка программного комплекса и разработанных

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

6. На основе разработанных в диссертационной работе алгоритмов решения ОРЗ построены программные средства, на которые получены свидетельства о государственной регистрации № 2013616055, № 2013616060, № 2013615965 и № 2013616088, ссылки на которые помещены в раздел "Основные публикации по теме диссертации". Их можно использовать для решения ОРЗ внешними программами. Программное обеспечение «Автоматизированная система экспериментальных исследований однородных распределительных задач теории расписаний «Autoscheduler» (свидетельство № 2013616055), позволяет сократить трудозатраты при проведении вычислительных исследований в области ОРЗ и повысить точность их приближенных решений.

Реализация результатов работы. Разработанные в диссертационной работе алгоритмы решения задач теории расписаний большой размерности были реализованы в ЗАО "СКБ "Орион" (г. Санкт-Петербург) на этапе эскизного проектирования системы мониторинга состояния сложных технических объектов в реальном масштабе времени и позволили обоснованно подойти к процедурам диспетчеризации вычислительных процессов, а также рационального распределения ограниченных информационнь1х ресурсов. Кроме того, полученные в диссертации научные и прикладные результаты нашли применение в научно-исследовательских разработках кй-федры программного обеспечения вычислительной техники и автоматизированных систем ДГТУ по направлению. «Технологии распределенных вычислений и систем», а также внедрены в учебный , процесс кафедры при изучении задач теории расписаний в рамках курсов «Исследование операций» и «Структуры и алгоритмы обработки данных».

Соответствие паспорту специальности. Область диссертационных исследований соответствует паспорту специальности 05.13.01 - «Системный анализ, управление и обработка информации (вычислительная техника и информатика)», пунктам: I - «Теоретические основы,и методы системного анализа, оптимизации, ... принятия решений и обработки информации»; 2 - «Формализация и постановка задач системного анализа, оптимизации, ... принятия решений и обработки информации»; 3 - «Разработка критериев и моделей описания и оценки эффективности решения задач системного анализа, оптимизации, ... принятия решений и обработки информации»; 4 - «Разработка методов и алгоритмов решения задач системного анализа, оптимизации, ... принятия решений и обработки информации»; 5 - «Разработка специального математического и алгоритмического обеспечения систем анализа, оптимизации, ... принятия решений и обработки информации».

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

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

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

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

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

Апробация результатов диссертационной работы. Основные результаты диссертационной работы докладывались и обсуждались на международных научных конференциях «Математические методы в технике и технологиях - ММТТ»: ММТТ-26 (НГТУ, Нижний Новгород, 27 - 30 мая 2013 г.), ММТТ-27 (ТГТУ, Тамбов, 3-5 июня 2014 г.); на международных научных семинарах (МНС): I МНС «Системный анализ, управление и обработка информации» (Дивноморское, 27-29 сентября 2010 г.), П МНС «Системный анализ, управление и обработка информации» (Дивноморское, 27 сентября - 2 октября 2011 г.), III МНС «Системный анализ, управление и обработка информации» (Дивноморское, 27 сентября - 2 октября 2012 г.), IV МНС «Системный анализ, управление и обработка информации» (Дивноморское, 29 сентября - 3 октября 2013 г.); на X международном научно-техническом форуме «Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012)» (ДГТУ, Ростов-на-Дону, 9-11 октября 2012 г.).

Промежуточные материалы диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета в 2012-2014 гг.

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

самостоятельные публикации. При этом 3 статьи опубликованы в ведущих изданиях, входящих в список ВАК РФ. Получено 4 свидетельства о государственной регистрации программ для ЭВМ.

В 15 совместных работах лично автором проведена алгоритмическая проработка, программная реализация и экспериментальные исследования комбинационной и структурной модификаций АР [1,2,16,21], вариантов СПА [3,9,10,12,13,17], комбинированного алгоритма «СМАР-СПА» [1,8]. В [5,15] автором разработана общая структура программного средства решения ОРЗ и осуществлена его программная реализация.

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

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

Кратко базовая математическая модель исследуемой задачи выглядит следующим образом. Рассматривается исполнительная система (ИС), состоящая из т идентичных, параллельно работающих исполнителей Е = {е},...,ет}. На вход ИС поступает множество п независимых заданий (работ) W = {w[,...,wn\, которые необходимо распределить между исполнителями. Известен размер каждого /-того задания rt, и он одинаков для любого /-того исполнителя вj, т.е. множеству W сопоставлено п-множество размеров R = {rl,...,rn}. Решением ОРЗ является множество

Dw = Wm}, в котором подмножества заданий Wj={wk \wkeW}

отвечают обязательному свойству

г , т

\/j,ke[\,m]->UWj=W-,Wjr\Wk=0. (i)

y=l j*k

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

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

Среди приближенных алгоритмов решения ОРЗ наиболее эффективными алгоритмами считаются широко известный эволюционно-генетический алгоритм (ЭГА) и еще недостаточно хорошо изученный селективно-перестановочный алгоритм (СПА). Эти алгоритмы позволяют с высокой вероятностью находить близкие к оптимуму решения ОРЗ, однако по представленным в литературе экспериментальным исследованиям точность нахождения ими именно оптимальных решений невысока. Например, для СПА для 3-х ИС вероятность получения оптимума не превышает 30%, а для ЭГА для 4-х ИС - нестабильно варьируется от 20 до 80%, а в среднем составляет -55%.

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

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

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

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

Проведенное с помощью специально разработанного программного средства экспериментальное исследование КМАР показало его высокие ресурсно-временные характеристики, позволяющие сократить время точного решения практически любой ОРЗ в диапазоне от 2 до 8 исполнителей, и от 10 до 50 заданий. Временной выигрыш от применения КМАР, исследованный на более чем 16000 задач, доходил до 200000-кратного. Средний же выигрыш по всей совокупности решенных задач составил 5600-кратный.

На диаграмме рисунка 1 представлены результаты одного из проведенных вычислительных экспериментов, иллюстрирующие высокую ресурсно-временную результативность КМАР. На этом рисунке представлены значения отношения среднего времени работы АР к среднему времени

КМАР Ралг = а?' / по основной совокупности оценок и по сово-

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

Количество заданий (л)

Рисунок 1 - Временной относительный выигрыш КМАР для 5-и исполнительной системы

Экспериментальные исследования КМАР также показали, что, во-первых, данная модификация позволяет не только сократить время решения ОРЗ по сравнению с базовым алгоритмом, но и значительно (в несколько раз по количеству распределяемых заданий) расширить диапазон доступных для решения за приемлемое время (до 70 мин) задач. Во-вторых, зависимость среднего времени решения КМАРом ОРЗ с узким диапазоном размеров распределяемых задач (А^„<10) от количества заданий имеет периодичный «пилообразный» характер с экспоненциальным ростом значений (рис. 2).

МС 5-Ю6 3106 1Ю6

8104 4,5-Ю4 1-10*

а','" > 70 лшн а

1600 1200 800

125 75 25

I \ I \ I

X

10

6

0,5 О

1 -- 1 и

[ — 1 \ 1 \ / =1 --4— 1 -

Количество заданий (л)

Рисунок 2 - Анализ временного ресурса КМАР для 5-и ИС

Таким образом, несмотря на то, что КМАР позволяет существенно снизить время и расширить диапазон оптимизационного решения ОРЗ, он остается Л^Р-полным алгоритмом. Поэтому исследования по созданию приближенных алгоритмов, обеспечивающих более быстрое решение ОРЗ, остаются актуальными. Данному исследованию посвящена следующая глава.

Третья глава посвящена структурной модификации КМАР (СМАР) для более быстрого нахождения по сравнению с исходным алгоритмом приближенного решения однородной РЗ.

Структурная модификация КМАР заключается в двух изменениях в структуре АР. Во-первых, в том, что в процессе поиска решения 2-задачи

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

a) Щ < 2,

b) К] = шах^ | $ ; Як с /?], (2)

где Лу" = ^^, е ^ ; К - множество размеров еще нераспределенных

на определенном шаге алгоритма заданий, /?сЛ.

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

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

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

В связи с ресурсно-временной ограниченностью КМАР, используемого как сравнительное средство решения ОРЗ, для оценки качества результатов решения СМАРом ОРЗ введены следующие основные понятия:

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

/ / / / /<'"> 30 мин/ / / / / / мс 1800000 / / /—г------—I-—I-----—^-«м1

1000000 200000

1000 т

800 +-I 1

31,5 21,5 11,5 1,5

о

О <>

ш аТк1 для кмар О а"'"1 для смар

0,9 0.6 0,3

о

^разл*

п т

---------

о и й й

35 35 35 35 20 5 5 5 5

31 31 51 51 41 31 53 31 51

5 3 3 5 4 5 3 3 5

Рисунок 3 - Среднее время работы а"ис! СМАР и КМАР по основной совокупности оценок

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

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

Проведенное с использованием введенных понятий и оценок качества результата решения ОРЗ исследование СМ АР продемонстрировало его высокие точностные показатели. По исследуемой в диссертации выборке в -20000 задач алгоритм в зависимости от условий задачи обеспечил нахождение оптимального решения в основном в 75-100%, а в среднем, в —98% случаев, при этом отклонение неоптимальных решений ог оптимума не превысило 4% от величины оптимума. В тех случаях, когда оптимальность для фактически полученных СМАР решений не удавалось определить, их оценка по ММК в большинстве случаев была лучше, чем у решений, полученных КМАР за ограниченное время.

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

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

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

Мультиперестановка представляет собой обмен непустых подмножеств заданий ,w[ ...je Wl и \\vJk ,w{ ...je Wj между et и ey исполнителями с улучшением критериальной оценки решения ОРЗ, т.е. удовлетворяющих условию

Rf-R]> !>;- 2W>0, (3)

p=k,s... q=k,s...

где r'p : w'p e , w's... j и г/ : wJq e \w{ , w{.. .J.

Эквиперестановкой называется обмен непустых подмножеств зада-

...1сЩ и , ...|сг 1¥/ между е{ и е] исполнителями с

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

НИИ Ц,

a)

b)

е

г' Ф г3 'р гя '

(4)

где г

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

Экспериментальное исследование результативности применения в СПА 1иульти- и эквиперестановок показало, что их использование позволяет существенно (в среднем на 15%, а в частных случаях в ~2 раза) повысить количество улучшенных до оптимального варианта с помощью СПА исходно приближенных решений по сравнению с применением в нем только одинарных перестановок. Кроме того, комбинированное применение «СПАО-СПАМ-СПАЭ» позволило в ~9 раз снизить количество полученных СМАР неоптимальных решений ОРЗ (рис. 4) и повысить процент найденных им оптимумов до крайне высокого значения - 99,8%.

СМАР СМАР-СПАО СМАР- СМАР-

СПАО+М СПАО+М+Э

Рисунок 4 - Улучшение результатов СМАР за счет поэтапного применения СПАО, СПАМ и СПАЭ

При этом ресурсно-временные затраты СПА на приближение к оптимуму полученных СМАР приближенных решений ОРЗ были небольшими и для исследованной в диссертационной работе выборки задач не превысили 150 мс.

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

ЗАКЛЮЧЕНИЕ

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

2. Системное изучение проблемы повышения эффективности решения ОРЗ позволило выделить ее наиболее перспективные направления:

• усовершенствование алгоритма Романовского по ресурсно-временной результативности, и с сохранением его свойства точного алгоритма, и при условии минимальной потери им точности решения;

• применение селективно-перестановочного алгоритма (СПА) для достаточно быстрого повышения точности приближенных решений.

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

4. Системное исследование КМАР показало его высокие ресурсно-временные характеристики, обеспечивающие сокращение времени решения большинства ОРЗ, экспериментально доказанное на более чем 16000 задач, в диапазоне до 8 исполнителей, и до 50 заданий с временным выигрышем относительно АР, доходящим до -200000-кратного, при среднем -5600-кратном выигрыше по всей совокупности.

5. Детальный анализ КМАР позволил разработать его структурную модификацию, названную СМАР, основанную на максимальной загрузке каждого исполнителей и глубоком откате к первому исполнителю, что сокращает количество рассматриваемых вариантов, повышая скорость алгоритма в среднем на 1-2 порядка, а иногда и на 5 порядков.

6. Исследование СМАР на почти 20000 опытах показало незначительное ухудшение точности по сравнению с КМАР: для ОРЗ с 2 исполнителям» он обеспечивает 100% оптимизацию решения, для 3-8 исполнителей и 10-30 распределяемых заданий - от 75 до 100% оптимумов, а в среднем обеспечивает ~98 % оптимальных решений. При этом наблюдается отклонение от оптимума приближенных решений от 0,5 до 4%, а для 3-5 исполнителей и 30-50 распределяемых заданий СМАР обеспечивает оптимум в 100% случаев.

7. Высокая ресурсно-временная результативность СМАР при обслуживании относительно ресурсоемких для КМАР ОРЗ делает целесообразным последовательное решение задачи с использованием КМАР, а, при задержке в работе - СМАР, что значительно сокращает время решения ОРЗ, сохраняя высокую вероятность оптимального решения.

8. Аналогично для улучшения результатов работы СМАР эффективен селективно-перестановочный алгоритм и его развитие использованием мульти- и эквиперестановок, что позволило существенно улучшить результаты решения ОРЗ с вероятностью получения оптимальных решений до -99,8 %. Возникающее увеличение времени решения ОРЗ незначительны, т.к. среднее время работы СПА для исследованной выборки задач составило 0,95 мс против 0,22 мс у СМАР.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

1. Жикулин, A.A. Комбинированное решение однородных распределительных задач на основе модифицированного алгоритма Романовского и селективно-перестановочного алгоритма / P.A. Нейдорф, A.A. Жикулин //Вести. Донск. гос. техн. ун-та.— 2012.-№ 5(66).— С. 50-54.

2. Жикулин, A.A. Модифицированный алгоритм Романовского быстрого нахождения приближенного решения однородной распределительной задачи / P.A. Нейдорф, A.A. Жикулин // Вестн. Донск. гос. техн. ун-та. -2012.-№6(67).-С. 87-92.

3. Жикулин, A.A. Селективно-перестановочный метод приближенного решения однородной распределительной задачи. Комбинационные перестановки / P.A. Нейдорф, A.A. Жикулин // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2013. - № 7(144). - С. 167-172.

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

4. Жикулин, A.A. Возможности и перспективы применения методов отжига в задачах поисковой оптимизации / A.A. Жикулин // Системный анализ, управление и обработка информации: тр. 1-го Межцунар. семинара студентов, аспирантов и ученых. - Ростов н/Д: ИЦ ДГТУ, 2010. - С. 223-228.

5. Жикулин, A.A. Исследование свойств многоэкстремальности решения распределительных задач / P.A. Нейдорф, A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 2-го Мелсдунар. науч. семинара. - Ростов н/Д: ИЦ ДГТУ, 2011. - С. 377-380.

6. Жикулин, A.A. Программное средство для исследования свойств многоэкстремальности решения однородных распределительных задач / A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 2-го Междунар. науч. семинара. - Ростов н/Д: ИЦ ДГТУ, 2011. - С. 245-248.

7. Жикулин, A.A. Алгоритм быстрого поиска решения распределительной задачи высокой степени приближения на основе алгоритма Романовского / A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара. - Ростов н/Д: ИЦ ДГТУ,2012.-С. 68-75.

8. Жикулин, A.A. Селективно-перестановочная модификация алгоритма Романовского и перспективы ее использования / P.A. Нейдорф, A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара. -Ростов н/Д: ИЦ ДГТУ, 2012. - С. 115-120.

9. Жикулин, A.A. Исследование селективно-перестановочного метода решения однородной распределительной задачи с использованием муль-типерестановок / P.A. Нейдорф, A.A. Жикулин // Системный анализ, управление и обработка информации: сб. тр. 3-го Междунар. науч. семинара. - Ростов н/Д: ИЦ ДГТУ, 2012. - С. 57-68.

10. Жикулин, A.A. Исследование вариантов модификации приближенных алгоритмов решения однородных распределительных задач, повышающих их эффективность / P.A. Нейдорф, A.A. Жикулин // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): Тр. X Междунар. науч.-техн. форума. - Ростов н/Д: ИЦ ДГТУ, 2012. - С. 370-375.

11. Жикулин, A.A. Метод повышения эффективности работы селективно-перестановочного алгоритма решения распределительных задач на основе эквивалентных перестановок / A.A. Жикулин // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): Тр. X Междунар. науч.-техн. форума. - Ростов н/Д: ИЦ ДГТУ, 2012. - С. 376-381.

12. Жикулин, A.A. Результаты исследования мультиперестановочного подхода при решении распределительных задач / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях - ММТТ-26: сб. тр. X3CVI Междунар. науч. конф.: в 10 т. Т. 9. Секция 11. - Нижний Новгород: НГТУ, 2013. - С. 332-335.

13. Жикулин, A.A. Эквиперестановочный подход к решению распределительных задач. Возможности и перспективы / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях — ММТТ-26: сб. тр. XXVI Междунар. науч. конф.: в 10 т. Т. 9. Секция И. - Нижний Новгород: НГТУ, 2013. - С. 305-308.

14. Жикулин, A.A. Двукритериальная стратегия элитизма эволюцион-но-генетического алгоритма многоэкстремальной оптимизации / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях -ММТГ-26: сб. тр. XXVI Междунар. науч. конф.: в 10 т. Т. 9. Секция 11.-Нижний Новгород: НГТУ, 2013. - С. 290-294.

15. Автоматизированная система экспериментальных исследований однородных распределительных задач теории расписаний «Autoscheduler»: свидетельство о государственной регистрации программы дпя ЭВМ № 2013616055 / P.A. Нейдорф, A.A. Жикулин. - № 2013616055; заявл. 2013613628; зарег. 26.06.2013.

16. Модификация алгоритма Романовского методом глубокого отката и максимальной загрузки для приближенного решения распределительных задач «Deep Rollback and Full Loading» (DR&FL): свидетельство о государственной регистрации программы для ЭВМ № 2013615965 / P.A. Ней-дорф, A.A. Жикулин. - № 2013615965; заявл. 2013613627; зарег. 25.06.2013.

17. Автоматизированное средство решения распределительных задач селективно-перестановочным методом «Selective-Permutational Scheduler»: свидетельство о государственной регистрации программы для ЭВМ № 2013616088 / P.A. Нейдорф, A.A. Жикулин. - № 2013616088; заявл. 2013613626; зарег. 26.06.2013.

18. Автоматизированное средство решения распределительных задач эволюционно-генетическим алгоритмом с использованием структурно-дифференцируемого элитизма «Structure-Differentiable Elitism»: свидетельство о государственной регистрации программы для ЭВМ № 2013616060 / P.A. Нейдорф, A.A. Жикулин. - № 2013616060; заявл. 2013613632; зарег. 26.06.2013.

19. Жикулин, A.A. Исследование ресурсно-временных возможностей алгоритма полного перебора при решении однородных распределительных задач / A.A. Жикулин // Системный анализ, управление и обработка информации: Тр. 4-го Междунар. семинара. - Ростов н/Д: ДГТУ, 2013. - С. 17-22.

20. Жикулин, A.A. Структурная модификация алгоритма Романовского с улучшением ресурсно-временных характеристик решения однородных распределительных задач / A.A. Жикулин // Системный анализ, управление и обработка информации: Тр. 4-го Междунар. семинара. — Ростов н/Д: ДГТУ, 2013. - С. 187-192.

21. Жикулин, A.A. Повышение ресурсной эффективности алгоритма точного решения однородной распределительной задачи / P.A. Нейдорф, A.A. Жикулин // Математические методы в технике и технологиях -ММТТ-27: сб. тр. XXVII Междунар. науч. конф.: в 12 т. Т. 3. Секции 6, 7, 8. - Тамбов: ТГТУ, 2014. - С. 42-46.

В набор 28.07.2014 г. В печать . О Ц.

Объем 1,0 усл.п.л., 1,0 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ Тираж 10.0

Издательский центр ДГТУ Адрес университета и полиграфического предприятия: 344000, г. Ростов-на-Дону, пл. Гагарина, I.