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

• Автор: Попов, Денис Валериевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Нижний Новгород
• Количество страниц: 122 с. : ил.

Оглавление
Введение.

Глава 1. Задачи распределения ресурсов и упорядочения работ в сетевых структурах.

1.1 Задачи распределения и упорядочения в сетевых канонических

СТруКТУраХ ммииииитииммммм.

1.1.1. Классификация задач распределения и упорядочения

1.1.2 Задачи распределения ресурсов

1.1.3. Задачи сетевого планирования

1.1.4. Задачи упорядочения.

1.2 Задачи распределения и упорядочения в многостадийных системах

Нечеткие временные и стоимостные характеристики в задачах распределения ресурсов и упорядочения работ.
1.3.1 Нечеткие множества.
1.3.2. Нечеткие числа
1.3.3. Операции над нечеткими числами
1.3.4. Операции сравнения нечетких чисел.
1.3.5. Определение нечетких бинарных отношений ,, на множестве нечетких чисел
1.3.6. Применение нечетких временных и стоимостных характеристик для описания реальных производственных систем.
Выводы по главе 1
Глава 2. Многостадийные задачи распределения ресурсов и упорядочения работ.
2.1. Общая математическая модель распределения ресурсов и упорядочения работ в многостадийных системах
2.1.1. Исходные параметры математической модели
2.1.2. Варьируемые параметры математической модели.
2.1.3. Ограничения математической модели.
. Исследование общей математической модели я
. Постановки оптимизационных задач распределения ресурсов и упорядочения работ в многостадийных системах
2.3.1. Частные критерии оптимальности.
2.3.2. Постановка классических задач дискретной оптимизации в рамках построенной
математической модели
Выводы по главе 2
Глава 3. Алгоритмы решения оптимизационных задач распределения ресурсов и упорядочения работ в многостадийных системах с нечеткими характеристиками
3.1. Жадные алгоритмы решения задач распределения и упорядочения.
3.2. Детерминированные алгоритмы ограниченного перебора
3.2.1. Алгоритм построитель расписания АР.
3.2.2 А Алгоритм поиска перестановки Р с глубиной И
3.2.3 Аз Метод локального улучшения расписания
3.2.4 А, Алгоритм критического пути
Стохастические алгоритмы решения задач распределения и упорядочения
мнамннннтнмиамммнаммммммммиапиммм4мнмамнмнв1мимммн
3.3.1. А2 Алгоритмы Метрополиса i i.
3.3.3 Управление процессом решения задачи путем взаимозависимого применения
различных алгоритмов.
3.3.4. Реализация нечетких расписаний при организации производственного процесса
Выводы по главе 3
Глава 4. Программные средства решения задач распределения ресурсов и упорядочения работ в многостадийных системах с нечеткими характеристиками .
4.1. Процедуры интерактивного взаимодействия
4.2. Реализация механизма построений различных отображений задачи
4.2.1. Сравнение различных схем отображений результатов решения задачи.
4.2.2. Математическая модель интерфейса с использованием аппарата нечетких множеств.
4.3. Реализация механизма сравнения различных отображений задачи
4.4. Решение прикладных задач распределения и упорядочения мммммиим
4.4.1 Численный эксперимент для оценки производительности групп жадных алгоритмов для построения расписания в многостадийных системах
4.4.2 Построение расписания изготовления прессформ в инструментальном цехе
Выводы по главе 4 4ЙИИМИИИМННМММНМММИМММЦИММММЧХИМнммми
Заключение
Литература


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