Оптимизация решения задач теории расписаний на основе эволюционно-генетической модели распределения заданий

Задачи теории расписаний имеют не только важное теоретическое значение, как относящееся в основном к классу NP-полных задач, но и получили широкое практическое распространение во множестве инженерных и управленческих задач [41,46,46,67]. Везде, где требуется упорядочить и распределить какие либо ресурсы между агентами (исполнителями), возникает вопрос эффективного планирования. Оптимальность планирования в значительной степени определяет технико-экономические показатели производственных и бизнес процессов. Построение оптимального плана распределения может занять даже на современных многопроцессорных системах многие месяцы и годы, при использовании точных методов решения, например, ветвей и границ (МВГ). С другой стороны, сейчас применяемые для таких задач быстрые, но приближенные списочные методы, такие, как метод критического пути (МКП), могут давать большую погрешность, приближающуюся к 30%[46]. Такое отклонение от оптимума в большинстве случаев является неприемлемым. Возникает необходимость в методах, характеризующихся сочетанием противоречивых свойств: полиноминальной зависимостью времени счета от размерности задачи и точностью близкой к оптимальной (по крайне мере значительно лучшей, чем у МКП). К такому классу методов относятся эволюционно-генетические алгоритмы (ЭГА), которые являются на сегодняшний момент наиболее гибкими и эффективными из всех известных приближенных алгоритмов[26].

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

Цель и основные задачи диссертационной работы.

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

1. разработка, обоснование и исследование эволюционно-генетической модели (ЭГМ) распределительной задачи (РЗ) теории расписаний;

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

3. исследование возможности применения ЭГА в качестве метода оценки фактического значения оптимума для РЗ большой размерности;

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

Существенные научные результаты, полученные в диссертации:

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

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

3. найденная по этой методике область эффективных значений параметров системы «РЗ-ЭГА», обеспечивающих максимальную доверительную вероятность получения оптимального решения в диапазоне параметров РЗ: п = Ъ (число исполнителей) и m = 17 — 25 (число работ), (п = 4 и т-1 -19), а также п = 5и т = 17 *;

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

5. найденные по этой методике доверительные значения количества параллельных опытов по оценке с помощью ЭГА величины оптимума решения РЗ, обеспечивающих заданную вероятность достоверности результата** в диапазоне параметров РЗ: п = 3 (число исполнителей) и т = П-25 (число работ), {п = 4и т-1 -19), а также п = 5и т = 17 .

Так, для параметров РЗ п = 3 и т = 11 получена оценка нижней границы точности р = 0,76 при следующих параметрах модели ЭГА: Pmut = 0,4,Pmutbjt = 0,07, crossover = 1' -^lim = 1050, Nchr = 50.

Иными словами, для заданных параметров РЗ п и т может быть получено необходимое количество параллельных опытов z, результат применения которых к данной РЗ даст оценку значения ее оптимального решения Q" p' с заданной вероятностью Р (например, 0,99 или 0,99 999).

Научная новизна существенных результатов диссертации определяется следующими отличительными признаками:

1. побитовая структура эволюционно генетической модели обеспечивает эффективную реализацию этапов эволюционно генетического алгоритма (ЭГА) при решении задач теории расписаний с предъявлением разумных требований к вычислительным ресурсам;

2. параметры области настроечных значений ЭГА, обеспечивающих максимальную доверительную вероятность нахождения оптимального решения РЗ, значительно отличаются от рекомендованных в литературе теории и практике применения ГА, так вероятность мутации особи составила Pmut- 0,41 вместо рекомендуемых Pmut = 0,1, вероятность мутации бита в гене Pmutbit = 0,07 вместо рекомендуемых Pmutbit = 0,1, вероятность участии особи в кроссовере Pcrossover= 1 вместо рекомендуемых Pcrossover = 0,9 (при этом для параметров РЗ п = 3 и т = 17 выигрыш по нижней оценке точности составил ропт1 Рхуд = 13);

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

4. разработанная методика оценки оптимального решения с наперед заданной доверительной вероятностью обеспечивает возможность применении ЭГА в качестве эталонного метода при работе с задачами большой размерности, что дает большой выигрыш по ресурсам решения сравнительных задач, так исследования показали, что для получения оптимального решения, с доверительной вероятностью Рдов= 0,9999 (при числе исполнителейя = з, числе работт = 17) необходим запуск всего z = 1 параллельных ЭГА.

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

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

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

2. разработанный и апробированный метод параметрической оптимизации позволяет определить близкую к оптимальным область параметров модели ЭГА, гарантирующую эффективное решение РЗ в диапазоне ее важнейших параметров (в работе исследовались области: п = Ъ (число исполнителей) и т = 17−25 (число работ), (п = 4и т = 17 -19), а также п = 5 и т = 17);

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

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

5. разработанное программное средство «ProjectSheduler» показало себя эффективным инструментом решения и исследования РЗ и подтвердило возможность эффективной реализации предложенной ЭГМ на современном аппаратно-программном комплексе;

6. «ProjectSheduler» позволяет производить оценку ЭГМ при различных параметрах системы «РЗ-ЭГА», обеспечивает легкую расширяемость функциональных возможностей, позволяет добавление новых модификаций моделей ЭГА или других методов.

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Первая глава диссертации посвящена обзору существующих методов решения РЗ теории расписаний. Методы классифицированы по свойственным им точностным и временным характеристикам. Показано, что для решения задач реальной размерности необходимо применение приближенных методов, наиболее гибкими из которых являются методы класса ЭГА. Для диссертационного исследования из всех задач теории расписаний выделен класс однородных задач (в англоязычных изданиях open shop"), в которых нет ограничений на порядок выполнения работ, и каждая работа состоит только из одной операции.

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

1. на основе ГА разработать эффективную эволюционно-генетическую модель (ЭГМ) решения задачи теории расписаний;

2. исследовать взаимосвязь точностных и временных эксплуатационных характеристик ЭГМ в зависимости от параметров системы «РЗ-ЭГА»;

3. разработать механизм статистического анализа точностных и временных характеристик модели и с помощью него провести параметрическую оптимизацию модели;

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

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

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

X = {G={pni}>G2={pn2}, G3={pn3},., Gm ={рпт}}, (3) где G — ген, рппорядковый номер исполнителя, на который назначена работа, номер исполнителя кодирован числом размером w6ит.

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

Третья глава посвящена статистическому анализу и параметрической оптимизации характеристик системы «РЗ-ЭГА».

При решении РЗ с фиксированными параметрами ЭГА дает довольно большой разброс значений оценок оптимума. Поэтому для анализа его точностных характеристик введена величина p3=vonm/v, где vonm — число опытов с полученным точным решением, v — общее число опытов, которая представляет собой частоту наступления положительных событийнахождений оптимума. Она является экспериментальной оценкой вероятности правильной оценки оптимума р для исследуемой системы «РЗ-ЭГА». При этом в пределах ограниченной по размерам выборки испытуемых РЗ, для каждой из этих выборок может быть получено различное значение оценки рэ. Для повышения надежности количественной оценки свойств «РЗ-ЭГА» в работе принято решение об оценке вероятности р по нижней границе значений рэ — pmin.

С помощью поэтапной оптимизации исследуемой системы «РЗ-ЭГА» значение нижней границы было существенно улучшено и составило р = 0,78 (вместо pmin = 0,06 до оптимизации) при значениях параметров ЭГА значительно отличающегося от рекомендуемых в литературе (например уровень мутации особи составила Pmut = 0,41 вместо рекомендуемых Pmut = 0,1, а вероятность мутации бита в гене осталась близкой к рекомендуемому Pmutbit = 0,1 и составила = 0,07, несколько сместилась также вероятность кроссовера Pcrossover =1 вместо Pcrossover = 0,9).

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

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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