Анализ и алгоритмы решения бикритериальных задач управления обслуживанием стационарных объектов mobile-процессорами

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

1.2.1. Схемы компромисса между критериями.

1.2.2. Концепция Парето.

1.3. Вычислительная сложность задач и алгоритмов

1.4. Модели обслуживания объектов в системах транспортного типа.

Выводы по главе 1.

ГЛАВА 2. МОДЕЛИ, ЗАДАЧИ И АЛГОРИТМЫ СИНТЕЗА СТРАТЕГИЙ

ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ

ОБЪЕКТОВ В ОДНОМЕРНОЙ РАБОЧЕЙ ЗОНЕ.

2.1. Однопроцессорное обслуживание объектов в одномерной зоне.

2.1.1. Математическая модель i 1

2.1.2. Постановка оптимизационных задач.

2.1.3. Исследование вычислительной сложности задач i ,x,
i ,, i 1x,x.
2.2. Синтез совокупности эффективных оценок на основе идеологии динамического программирования
2.2.1. Построение рекуррентных соотношений динамического программирования.
2.2.2. Примеры реализации синтеза стратегий обслуживания
2.3. Синтез совокупности эффективных оценок на основе метода ветвей и границ
2.3.1. Описание метода
Выводы по главе 2.
ГЛАВА 3. МОДЕЛИ, ЗАДАЧИ И АЛГОРИТМЫ СИНТЕЗА СТРАТЕГИЙ ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ ОБЪЕКТОВ В ОДНОМЕРНОЙ РАБОЧЕЙ ЗОНЕ ДВУХ ОБСЛУЖИВАЮЩИХ
ПРОЦЕССОРОВ
3.1. Обслуживание объектов в рабочей зоне двух попутных процессоров
3.1.1. Математическая модель i2.
3.1.2. Постановка оптимизационных задач.
3.1.3. Построение рекуррентных соотношений динамического программирования.
3.1.4. Примеры реализации синтеза стратегий обслуживания
3.2. Обслуживание объектов в рабочей зоне двух встречных процессоров
3.2.1. Математическая модель i2 и постановка оптимизационных задач
3.2.2. Построение рекуррентных соотношений динамического программирования.
3.2.3 Примеры реализации синтеза стратегий обслуживания.
Выводы по главе 3.
ГЛАВА 4. МОДЕЛИ, ЗАДАЧИ И АЛГОРИТМЫ СИНТЕЗА СТРАТЕГИЙ
ОДНОПРОЦЕССОРНОГО ОБСЛУЖИВАНИЯ СТАЦИОНАРНЫХ
ОБЪЕКТОВ В РАБОЧЕЙ ЗОНЕ ГРАФОВОЙ СТРУКТУРЫ
4.1. Обслуживание объектов в рабочей зоне графовой структуры.
4.1.1. Математическая модель .
4.1.2.1 Остановка оптимизационных задач.
4.1.3. Исследование вычислительной сложности задач ,x,
, и I,.
4.2. Синтез совокупности эффективных опенок на основе идеологии динамического программирования.
4.2.1. Построение рекуррентных соотношений динамического программирования
4.3. Обобщение модели обслуживания на случай наличия ограничений на порядок обслуживания объектов
4.3.1. Концепция расписаний и постановка оптимизационных задач.
4.3.2. Построение рекуррентных соотношений динамического программирования .
Выводы по главе 4
ГЛАВА 5. АЛГОРИТМЫ СИНТЕЗА СУБОПТИМАЛЬНЫХ СТРАТЕГИЙ
ОБСЛУЖИВАНИЯ.
5.1. О сравнении двух множеств оценок
5.2. Алгоритмы мягких вычислений для задач i, x, i,, ix,x
5.2.1. Синтез субоптимальных стратегий обслуживания на основе эволюционногенетического подхода
5.2.2. Синтез субоптимальных стратегий обслуживания на основе метода поиска с запретами
5.2.3. Синтез субоптимальных стратегий обслуживания на основе метода имитации отжига
5.2.4. Результаты вычислительных экспериментов.
5.3. Алгоритмы мягких вычислений для задач i2,x, i2,, i2x,x, i2,x, i2,, i2x,x
5.3.1. Синтез субоптимальных стратегий обслуживания на основе эволюционногенетического подхода
5.3.2. Синтез субоптимальных стратегий обслуживания на основе метода поиска с запретами
5.3.3. Синтез субоптимальных стратегий обслуживания на основе метода имитации отжига
5.3.4. Результаты вычислительных экспериментов.
5.4. Алгоритмы мягких вычислений для задач , x, I, I,
x, x, 1,Г.
5.4.1. Синтез субоптимальных стратегий обслуживания на основе концепции расписаний
5.4.2. Синтез субоптимальных стратегий обслуживания методом муравьиной колонии.
5.4.3. Синтез совокупности субоптимальных стратегий на основе эволюционногенетического подхода.
5.4.4. Синтез субоптимальных стратегий обслуживания на основе метода поиска с запретами
5.4.5. Синтез субоптимальных стратегий обслуживания на основе метода имитации отжига
5.4.6. Комбинированный подход для синтеза субоптимальных стратегий обслуживания
5.4.7. Результаты вычислительных экспериментов.
Выводы по главе 5.
ГЛАВА 6. ПРОГРАММНЫЙ КОМПЛЕКС ПОДДЕРЖКИ УПРАВЛЕНИЯ СНАБЖЕНИЕМ ПЛАВУЧИХ ДОБЫВАЮЩИХ КОМПЛЕКСОВ
ДИЗЕЛЬНЫМ ТОПЛИВОМ
6.1. Проблема оперативного управления снабжением дизельным топливом
группировки плавучих добывающих комплексов.
6.2. Программный комплекс поддержки оперативного управления обслуживанием группировки плавучих добывающих комплексов
6.2.1. Назначение и функциональные возможности.
6.2.2. Интерфейс пользователя
6.2.3. Описание типового сценария работы с комплексом
6.2.4. Описание архитектуры программного комплекса.
Выводы по главе 6
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Во второй главе Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в одномерной рабочей зоне , , , , , выполняется построение математической модели, формулируются оптимизационные задачи, исследуются вопросы их вычислительной сложности, разрабатываются алгоритмы синтеза совокупности паретооптимальных стратегий обслуживания и приводятся примеры их численной реализации. Ставятся оптимизационные задачи i , x, i 1X,I, i 1Г,x,x. Доказываются теоремы об трудности и о числе возможных эффективных оценок. Выводятся рекуррентные соотношения, приводятся примеры численной реализации. Доказывается, что данный алгоритм имеет псевдополиномиальную оценку трудоемкости. В третьей главе Модели, задачи и алгоритмы синтеза стратегий обслуживания стационарных объектов в одномерной рабочей зоне двух обслуживающих iпроцессоров , , , рассматривается расширение модели, описанной в главе 2, на случай двух обслуживающих процессоров. При этом 3. В четвертой главе Модели, задачи и алгоритмы синтеза стратегий однопроцессорного обслуживания стационарных объектов в рабочей зоне графовой структуры , , , , , 0 рассматривается общая модель однопроцессорного обслуживания , в которой объекты совокупности находятся в вершинах неориентированного односвязного фафа. X, X, x, x и X,Г. Доказываются теоремы об трудности в сильном смысле задач, в которых хотя бы один критерий аддитивный. Поставлены оптимизационные задачи, разработаны решающие алгоритмы, основанные на многокритериальном расширении метода динамического программирования, доказана их псевдополиномиальность. Пятая глава Алгоритмы синтеза субоптимальных стратегий обслуживания , , , , ,, , посвящена разработке решающих алгоритмов на основе концепции мягких вычислений, реализованной с использованием следующих метаэвристик муравьиная колония, поиск с запретами, имитация отжига, эволюционногенетическая парадигма. Построен также итеративный алгоритм синтеза субоптимальных стратегий обслуживания на основе концепции брасписаний . В 5. Для указанных задач разработаны алгоритмы, основанные на идеологии поиска с запретами, имитации отжига и эволюционногенетической парадигме. Приводятся и анализируются результаты вычислительных экспериментов, формулируются рекомендации но применению алгоритмов. В дополнение к рассмотренным в 5. В шестой главе Программный комплекс поддержки управления снабжением плавучих добывающих комплексов дизельным топливом , , , , рассматриваются прикладные задачи для построенных в главах моделей обслуживания стационарных объектов тоЫ1епроцессорами. Описывается разработанный программный комплекс, предназначенный для синтеза оптимальных и субоптимальных стратегий управления обслуживанием. В заключении изложены основные научные и практические результаты диссертационной работы. Приложение содержит документы о внедрении и использовании результатов диссертационной работы. ГЛАВА 1. Проводится обзор вопросов, изучаемых в теории расписаний. Излагаются методы решения дискретных многокритериальных задач. Приводятся базовые понятия и определения из теории вычислительной сложности задач и алгоритмов. Формулируется общая модель обслуживания стационарных объектов перемещающимися процессорами. К середине прошлого века сформировался устойчивый интерес к математическим исследованиям задач планирования и управления производственными процессами. Та часть таких задач, которая описывалась в рамках дискретного формализма, со временем сформировалась в самостоятельную научную дисциплину, получившую название теория расписаний. В рамках теории расписаний изучаются вопросы, связанные с оптимальным распределением и упорядочением конечного множества обтектов работ, требований, заявок в системе с одним или несколькими обслуживающими процессорами приборами, машинами при различных предположениях о характере обслуживания . Например, в качестве работ могут выступать производственные операции, взлеты и посадки самолетов, исполнение программ для ЭВМ. Под термином процессор подразумеваются станки, взлетнопосадочные полосы, вычислительные машины и т. Считается, что интерес к вопросам теории расписаний появился, начиная с работы 2. Однако прошло немало времени, прежде чем появились первые публикации в литературе по исследованию операций и организации производства. С появлением статьи .