Альтернативное распределение ресурсов в сетевых канонических структурах с интервальными характеристиками

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

ВВЕДЕНИЕ

ГЛАВА 1. ЗАДАЧИ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ КАК ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ.

1.1. Место задач распределения ресурсов в классе задач

МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

1.1.1. Место задач теории расписаний в классе задач математического программирования.,

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

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

структурах.

1.2.1. Классификация по способу задания параметров

1.2.2. Классификация по типу ресурса

1.2.3. Интервальная арифметика

1.3. Задачи альтернативного распределения ресурсов в сетевых канонических структурах с интервальными значениями параметров
ВЫВОДЫ ПО ГЛАВЕ 1.
ГЛАВА 2. ОБЩАЯ МАТЕМАТИЧЕСКАЯ МОДЕЛЬ АЛЬТЕРНАТИВНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЕВЫХ КАНОНИЧЕСКИХ СТРУКТУРАХ С ИНТЕРВАЛЬНЫМИ ХАРАКТЕРИСТИКАМИ.
2.1. Общая математическая модель.
2.1.1. Исходные параметры модели
2.1.2. Варьируемые параметры модели.
2.1.3. Ограничения математической модели
2.2. Исследование общей математической модели
2.2.1. ИРполнота проблемы существования решения
2.2.2. Линеаризация общей математической модели.
2.3. Частные подмодели и условия их разрешимости
2.3.1. Модель с технологическими ограничениями
2.3.2. Модель с технологическими и организационными ограничениями .
2.3.3. Модель с технологическими и ресурсными ограничениями
Выводы по главе
ГЛАВА 3. ПОСТАНОВКИ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ АЛЬТЕРНАТИВНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЕВЫХ КАНОНИЧЕСКИХ СТРУКТУРАХ С ИНТЕРВАЛЬНЫМИ ХАРАКТЕРИСТИКАМИ.
3.1. Многокритериальные задачи альтернативного распределения ресурсов.
3.1.1. Задача типа Апоиска эффективных технологически и организационно допустимых расписаний
3.1.2. Задача типа Впоиска эффективных технологически и ресурсно допустимых расписаний.
3.1.3. Задача типа Споиска эффективных технологически допустимых расписаний.
3.2. Схемы компромиссов для постановок задач альтернативного распределения ресурсов с интервальными характеристиками
3.2.1. Задача типа А поиска оптимального технологически и организационно допустимого расписания.
3.2.2. Задача типа В поиска оптимального технологически и ресурсно допустимого расписания
3.2.3. Задача типа С поиска эффективного технологически допустимого расписания
Выводы ПО ГЛАВЕ
ГЛАВА 4. АЛГОРИТМЫ РЕШЕНИЯ ЗАДАЧ АЛЬТЕРНАТИВНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ В СЕТЕВЫХ КАНОНИЧЕСКИХ СТРУКТУРАХ С ИНТЕРВАЛЬНЫМИ ХАРАКТЕРИСТИКАМИ
4.1. Интервальный подход к решению задач распределения ресурсов
4.2. Алгоритм построения Адопустимых расписаний.
4.2.1. Алгоритм А1 построения интервального расписания.
4.2.2. Алгоритм А2 уточнения расписания
4.2.3. Алгоритм АЗ выбора ресурсов.
4.2.4. Алгоритм А4 определения оптимального значения штрафа
4.2.5. Алгоритм А5 расчета интенсивностей потребления ресурсов
4.2.6. Алгоритм А6 уточнения интенсивностей потребления ресурсов .
4.2.7. Аалгоритм построения расписаний.
4.3. Алгоритм построения Вдопустимых расписаний.
4.3.1. Алгоритм В1 построения интервального расписания
4.3.2. Алгоритм В2 построения реализации интервального расписания .
4.3.3. Валгоритм построения расписаний.
ВЫВОДЫ ПО ГЛАВЕ 4.
ГЛАВА 5. ДИАЛОГОВАЯ ПРОГРАММНАЯ СИСТЕМА РЕШЕНИЯ ЗАДАЧ ПОСТРОЕНИЯ ИНТЕРВАЛЬНЫХ РАСПИСАНИЙ
5.1. Архитектура диалоговой программной системы.
5.2. Типовые сценарии решения задач интервального распределения ресурсов
5.3. Решение задачи оптимизации планграфиков для инструментального производства при изготовлении прессформ 3 Выводы ПО ГЛАВЕ 5.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


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