Упорядочение работ и распределение ресурсов в канонических системах "конвейер-сеть"

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

Введение
Глава 1. Оптимизационные задачи упорядочения работ и распределения ресурсов в сетевых канонических структурах
1.1. Задачи упорядочения работ и распределения ресурсов как задачи математического программирования.
1.1.1. Место задач теории расписаний в классе задач математического программирования.

1.1.1.1. Задачи планирования перевозок.

1.1.1.2. Задачи размещения и специализации.

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

1.1.1.4. Задачи распределения вычислительной памяти

1.1.1.5. Задачи синтеза логических сетей.

1.1.1.6. Задачи нахождения маршрутов перевозки груза.

1.1.2. Классификация задач теории расписаний

1.1.2.1. Сетевое представление.
1.1.2.2. Иерархическое представление.
1.1.2.3. Задачи упорядочения работ.
1.1.2.4. Задачи согласования.
1.1.2.5. Задачи распределения
1.2. Упорядочение работ и распределение ресурсов при заданных отношениях предшествования
1.2.1. Общее описание задачи упорядочения работ и распределения ресурсов при заданных отношениях предшествования
1.2.2. Классификация моделей по учету внешних воздействий.
1.2.2.1. Детерминированные модели
1.2.2.2. Вероятностные стохастические модели.
1.2.2.3. Статистические модели.
1.3. Содержательная постановка задач упорядочения и распределения ресурсов в канонических структурах типа комвейсрсеть.
1.3.1. Оптимальное планирование и управление процессом производства изделий м и крозлектро I и к и
1.3.1.1. Производство больших интегральных схем БИС
1.3.1.2. Производство гибридных интегральных схем ГИС
1.3.2. Задача планирования опытного производства изделий машиностроения.
1.3.3. Задача планирования процесса изготовления прессформ в инструментальном производстве.
1.3.4. Общие особенности задачи планирования производства микроэлектронных изделий и задачи опытного производства изделий
машиностроения
1.3.5. Содержательное описание объекта
Выводы по главе
Глава 2. Математические модели упорядочения работ и распределения ресурсов в
канонических системах
2.1. Общая математическая модель упорядочения работ и распределения ресурсов для канонических систем
2.1.1. Исходные параметры математической модели.
2.1.2. Варьируемые параметры математической модели
2.1.3.Ограничения математической модели.
2.1.4. Исследование общей математической модели.
2.2. Математическая модель упорядочения работ для систем с конвейерными
технологиями
2.2.1. Математическая модель и ее исследование
2.3. Математическая модель распределения ресурсов для систем с сетевыми
технологиями
2.3.1. Математическая модель
2.3.2. Исследование математической модели.
Выводы но главе 2.
Глава 3. Постановки оптимизационных задач упорядочения работ и распределения
ресурсов и алгоритмы их решения
3.1. Постановка оптимизационных задач упорядочения работ и распределения ресурсов
3.1.1. Критерии оптимизационных задач.
3.1.2. Постановка оптимизационной задачи для систем конвейерного
3.1.3. Постановка оптимизационной задачи для систем конвейерссть
3.2. Метод ветвей и границ построения расписаний для систем типа конвейерсеть
3.2.1. Описание основных процедур метода ветвей и границ
3.2.2. Алгоритмы определения граничных значений метода ветвей и границ для
систем типа конвейерсеть.
3.3. Стохастические и детерминированные алгоритмы решения задачи упорядочения работ и распределения ресурсов
3.3.1. Алгоритмпостроитель расписания.
3.3.1.1. Алгоритмпостроитель допустимого расписания.
3.3.2. Стохастические алгоритмы
3.3.2.1 .Алгоритм Метрополией i i
3.3.2.2.Муравьиный алгоритм i.
3.3.2.3.Генетический алгоритм
3.3.3. Детерминированные алгоритмы.
3.3.3.1 .Фронтальный алгоритм
3.3.3.2.Алгоритм решения задачи о назначениях
3.3.4.Метод комбинирования алгоритмов.
Выводы по главе
Глава 4. Диалоговые программные средства решения оптимизационных задач упорядочения работ и распределения ресурсов в канонических системах типа конвейерсеть
4.1. Описание структуры и возможностей диалоговой системы.
4.1.1. Модель работы с каноническими системами типа конвейерсеть
4.1.2. Архитектура диалоговой программной системы.
4.1.3. Алгоритмический блок программной системы.
4.1.4. Функциональный блок программной системы
4.1.5. Системные требования.
4.2. Результаты вычислительных экспериментов для анализа эффективности применения разработанных алгоритмов
4.3. Решение задач упорядочения работ и распределения ресурсов.
4.3.1. Решение задач упорядочения работ и распределения ресурсов в микроэлектронном производстве.
4.3.1.1. Общее описание программного комплекса
4.3.1.2. Решение задач планирования в программном комплексе Кристалл
4.3.2. Построение расписания изготовления прессформ в инструментальном
Выводы по главе 4.
Заключение
Список литературы


Я., Бурков В. Н. , Гордон , Кульба В. В., Мироносецкий Н. Б., Михалевич , Норенков И. П., Подчасова Т. П., Танаев , Шкурба В. В., Шор Н. З. и многие другие. Из зарубежных ученых это Конвой Р. Джонсон Б. Максвелл У. Гиффлер Б. Томпсон Ж. И другие. Следует отметить школу нижегородского университета и ученых Батищева Д. И., Прилуцкого М. Х., Когана Д. И., Федосенко Ю. С., которые рассматривали подобные проблемы. В настоящее время системы сетевого планирования и управления используются как инструмент для решения задач планирования, возникающих в различных областях деятельности человека. Актуальность исследования. В настоящее время задачи управления изготовлением сложных изделий включают в себя несколько стадий, каждую из которых можно отнести либо к классу последовательного выполнения работ конвейерные технолог ии, либо к классу распределения ресурсов в сетевых структурах. В результате их анализа, в диссертационной работе представлена модель системы типа конвейерсеть, включающая в себя последовательность данных технологий. Выделение данного класса систем позволило не только более естественно описывать в рамках поставленной модели многие инженерные и технические задачи, но и существенно сократило время их решения, используемые аппаратные ресурсы, а также оптимизировало поиск расписаний. Для решения задач, относящихся к системам типа конвейерсеть, выделен метод, соединяющий в себе подход, связанный как с упрощением исходной задачи, а, следовательно, со снижением ее математической сложности, так и с применением различных комбинаций конфигурируемых эвристических алгоритмов. Ключевая идея подобного подхода состоит в том, что размерность задачи сокращается путем ее разбиения, для полученных таким образом задач меньшей размерности производится поиск решения, после чего происходит оценка решения исходной задачи объединением полученных решений. Другим способом сокращения вычислительной сложности решающих алгоритмов служит введение элементов стохастики. Однако практический интерес к ним не ослабевает, а наоборот, усиливается. Объяснить это можно тем обстоятельством, что эти методы позволяют исследовать и находить приемлемые решения таких задач, решение которых при помощи традиционных методов оказывается затруднительным, а в некоторых случаях и просто невозможным. Кроме того тот факт, что набор перестановок, полученных в результате работы одного из алгоритмов, может быть использован как начальное решение для другого алгоритма, позволяет комбинировать алгоритмы различным образом и настраивать их для поиска решения конкретной задачи. Комбинирование же точных и эвристических алгоритмов позволило находить оптимальное решение для задач небольшой размерности, а для большеразмерных систем принимать лучшее из найденных значений рекорд за эвристическую оценку искомого расписания. Целью диссертационной работы является исследование задач распределения ресурсов и упорядочения работ в канонических системах типа конвейерсеть, построение математических моделей и их исследование, постановка оптимизационных задач, разработка алгоритмов их решения и создание на их основе диалоговой программной системы. Выделен новый класс канонических систем конвейерсеть, описывающий многостадийные производственные процессы чередование стадий конвейерных и сетевых технологий, где конвейерные технологии связаны с упорядочиванием работ, а сетевые с распределением ресурсов. Построены математические модели канонических систем с конвейерными и сетевыми технологиями. Проведено их исследование. В рамках построенных математических моделей поставлены оптимизационные задачи упорядочения работ и распределения ресурсов по критерию быс тродействия. Предложены алгоритмы решения поставленных задач, в основу которых заложены основные вычислительные процедуры метода ветвей и границ с использованием комбинирования точных и эвристических алгоритмов для получения оценок эффективности полученных решений. Создана диалоговая программная система решения задач, относящихся к классу задач конвейерсегь.