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

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

Оглавление
ВВЕДЕНИЕ

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

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

1.2 Математические модели и методы решения задач распределения ресурсов и упорядочения работ

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

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

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

ВЫВОДЫ ПО ГЛАВЕ 1.

ГЛАВА 2. МАТЕМАТИЧЕСКИЕ МОДЕЛИ И ПОСТАНОВКИ ОПТИМИЗАЦИОННЫХ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ В СЕТЕВЫХ КАНОНИЧЕСКИХ СТРУКТУРАХ

2.1 Общая математическая модель распределения ресурсов и упорядочения работ.

2.2 Исследование математической модели
2.3 Постановки оптимизационных задач
Выводы по главе 2.
ГЛАВА 3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ.
3.1 Взаимно однозначное соответствие между множеством допустимых решений задачи упорядочения и множеством решений
задачи о назначениях
3.1.1 Установление взаимно однозначного соответствия.
3.1.2Построение множества всех решений задачи о назначениях
3.2. Алгоритмы решения задач распределения ресурсов и упорядочения работ с помощью биекции множеств
3.3. Перестановочные процедуры решения задач распределения
ресурсов и упорядочения работ.
Выводы по главе 3.
ГЛАВА 4. ДИАЛОГОВЫЕ ПРОГРАММНЫЕ СРЕДСТВА ПРИНЯТИЯ РЕШЕНИЙ ДЛЯ ЗАДАЧ РАСПРЕДЕЛЕНИЯ РЕСУРСОВ И УПОРЯДОЧЕНИЯ РАБОТ.
4.1. Архитектура диалоговой системы.
4.2. Типовые сценарии.
4.3. Составление план графиков работы подразделений
4.4 Планирование сборочных операций консолыюфрезерных
станков узловая и генеральная сборка.
Выводы по главе 4
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


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