Модели и алгоритмы управления ресурсами в однофазных системах обслуживания транспортного типа

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

Введение

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

сами в однофазных системах обслуживания транспортного типа

1.1. Место, роль и методы анализа процессов управления

ресурсами в задачах повышения эффективности функционирования сложных технических систем .

1.2. Специфика управления ресурсами в системах транспортного типа

1.3. Особенности математических моделей и алгоритмов,

реализующих новые информационные технологии оперативного управления ресурсами

1.4. Качественный подход к декомпозиции математических

моделей процессов управления ресурсами систем обслуживания транспортного типа

1.5. Основные результаты и выводы первой главы .

Глава 2. Построение общей динамической модели управления
ресурсами в однофазных системах обслуживания транспортного типа.
2.1. Дискретная формализация детерминированной системы
обслуживания
2.2. Моделирование динамики системы обслуживания при
наличии ограничений на объекты и процессы управле
ния .
2.3. Критерии оценки качества функционирования системы
обслуживания
2.4. Схема конструктивной декомпозиции многопроцессорной системы обслуживания .
2.5. Основные результаты и выводы второй главы .
Глава 3. Исследование вычислительной сложности экстремаль
ных задач управления дискретными ресурсами в однофазных системах обслуживания транспортного типа
3.1. Концепции оценки вычислительной сложности экстре
мальных переборных задач синтеза программ управления дискретными ресурсами .
3.2. Вычислительная сложность задачи синтеза оптималь
ного расписания для системы обслуживания с линейной функцией суммарного штрафа.
3.3. Полиномиальная разрешимость частных подклассов задачи синтеза оптимального расписания .
3.4. Бифуркационные свойства проблемы полиномиальной
разрешимости задачи синтеза оптимального расписания .
3.5. Полиномиальная разрешимость задачи синтеза опти
мального расписания обслуживания для потоков заявок, поступающих на ограниченном интервале времени
3.6. ИРтрудность типовой задачи диспетчеризации .
3.7. Основные результаты и выводы третьей главы
Глава 4. Моделирование типовых процессов обслуживания потока независимых заявок, разработка и исследование алгоритмов синтеза оптимальных однопроцессорных расписаний
4.1. Синтез оптимального расписания в базовой модели обслуживания потока заявок на основе схемы динамического программирования .
4.2. Полиномиальные алгоритмы синтеза оптимальных расписаний в базовой модели с ограничениями на структуру потока и дисциплину управления обслуживанием 0 4,3. Оптимальное обслуживание в базовой модели при наличии подмножества привилегированных заявок с жсткими директивными сроками завершения обслуживания .
4,4, Общая модель и алгоритмы синтеза расписаний обслуживания потока независимых заявок с нелинейными
штрафами.
4.5. Моделирование и оптимизация в однопроцессорных системах с закрытыми для обслуживания временными
интервалами
4.6. Основные результаты и выводы четвертой главы .
Глава 5. Моделирование и разработка алгоритмов синтеза оптимальных расписаний однопроцессорного обслуживания пакетов заявок.
5.1. Базовая модель и алгоритм минимизации суммарной
стоимости расписания обслуживания потока заявок в
пакетах фиксированной структуры
5.2. Базовая модель и алгоритм минимизации суммарной стоимости расписания обслуживания потока заявок в
пакетах с переменной структурой
5.3. Общая модель и алгоритм синтеза оптимальных расписаний обслуживания потока заявок в пакетах фиксированной структуры с нелинейными штрафами
5.4. Общая модель и алгоритм синтеза оптимальных расписаний обслуживания потока заявок в пакетах с переменной структурой с нелинейными штрафами .
5.5. Основные результаты и выводы пятой главы
Глава б. Разработка алгоритмов синтеза и оценка устойчивости рациональных расписаний для однопроцессорных моделей однофазного обслуживания .
6.1. Синтез субоптимальных расписаний на основе метода
ветвей и границ.
6.2. Скользящий алгоритм синтеза рациональных расписаний
6.3. Алгоритм последовательного зондирования для корректировки расписания обслуживания .
6.4. Оценка устойчивости оптимальных рациональных
расписаний
6.5. Синтез рациональных расписаний обслуживания с
учтом нескольких критериев
6.6. Основные результаты и выводы шестой главы .
Глава 7. Разработка моделей и алгоритмов синтеза расписаний однофазного обслуживания потока независимых заявок в многопроцессорных системах
7.1. Оптимальное обслуживание потока заявок в системе
параллельных процессоров
7.2. Построение рекуррентных соотношений для синтеза оптимального расписания обслуживания заявок в пространственно рассредоточенной системе ш независимых процессоров .
7.3. Построение и экспериментальное исследование вычислительной схемы поэтапного синтеза рационального распределения и упорядочения использования дискретных ресурсов .
7.4. Ситуационные модификации алгоритмов поэтапного
синтеза программ управления ресурсами
7.5. Основные результаты и выводы седьмой главы
Глава 8. Информационная технология оперативного управления ресурсами в крупномасштабном воднотранспортном комплексе
8.1. Описание крупномасштабного воднотранспортного комплекса и особенностей его функционирования как
однофазной системы обслуживания
8.2. Архитектура программной системы МУРАД для решения задач управления ресурсами крупномасштабного воднотранспортного комплекса в интерактивном режиме
на ПЭВМ типа ВМ РС
8.3. Оперативное управление использованием плавучих добывающих установок и подачей судов под обработку в крупномасштабном воднотранспортном комплексе с по
мощью программной системы МУРАД
8.4. Основные результаты и выводы восьмой главы .
Заключение.
Список литературы


К таковым относятся модификации, адекватно моделирующие потоки с ограниченным количеством типов заявок и относительно
разреженные потоки 4. В 4. На основе метода динамического программирования построены алгоритмы синтеза расписаний минимальной стоимости и получены оценки их вычислительной сложности. Показано, что наложение естественных для СТТ ограничений на плотность потоков и дисциплину управления обслуживанием позволяет строить полиномиальные алгоритмы синтеза. Синтез оптимальных расписаний обслуживания осуществляется путем отработки конструируемых в главе рекуррентных соотношений динамического программирования. Для их построения предложен универсальный прим моделирования простоев процессора, заключающийся в постановке на обслуживание определнным образом вводимых нулевых заявок количество нулевых заявок, находящихся у процессора в любой момент времени, не ограничивается, что позволяет единообразно формализовывать процессы обслуживания заявок потока. Каждый из разработанных параметрически настраиваемых алгоритмов, учитывая специфику внутренних свойств конкретных потоков, а также процессов управления ими, имеет свою область наиболее целесообразного применения. В 4. Содержательно такого рода ситуации соответствуют случаям, когда, например, расчт программы управления дискретными ресурсами осуществляется при известном графике выполнения с процессором регламентных работ или реализации на выделенных интервалах времени обслуживания заявок с абсолютными приоритетами. Наряду с базовыми рассмотрены обобщенные модели с нелинейными штрафами произвольного вида за время пребывания в системе обслуживания и нарушение мягких директивных сроков 5. На основе схемы динамического программирования разработаны алгоритмы синтеза расписаний минимальной стоимости и получены оценки их вычислительной сложности. Полученные результаты решают в практическом плане задачи расчта оптимальных программ группового управления дискретными ресурсами в однопроцессорных СТТ. Шестая глава Разработка алгоритмов синтеза и оценка устойчивости рациональных расписаний для однопроцессорных моделей однофазного обслуживания посвящена алгоритмам синтеза рациональных расписаний обслуживания и оценке устойчивости распи
саний. Рациональные расписания, не являясь оптимальными, характеризуются приемлемыми для приложений качеством и скоростью синтеза. Кроме этого, алгоритм формирования рационального расписания обслуживания, построенный в 6. А. и i А. Два других разрабатываемых в 6. Скользящий алгоритм отличается высокой скоростью отработки и, как показали тестовые расчты, формирует расписания с приемлемой для приложений точностью. Алгоритм последовательного зондирования, решая задачу оптимальной вставки в синтезированное решение дополнительной заявки, предназначен для оперативной корректировки расписания. Значительный интерес для приложений представляет проблема оценки устойчивости оптимальных рациональных расписаний. В 6. На основе метода продолжения по параметру предложена численная схема построения границ областей устойчивости по структуре оптимальных рациональных расписаний в пространстве изменяемых парамет
ров модели. Приведены примеры разбиения плоских сечений пространства параметров однопроцессорной модели обслуживания на области устойчивости структурно различных расписаний обслуживания потока заявок. В заключении главы 6. В седьмой главе Разработка моделей и алгоритмов синтеза расписаний однофазного обслуживания потока независимых заявок в многопроцессорных системах строятся рекуррентные соотношения динамического программирования для задачи оптимизации управления ресурсами в СТТ с шмерным пулом параллельных 7. В 7. СТТ разрабатывается вычислительная схема поэтапного синтеза рационального распределения и упорядочения использования ресурсов на основе решения специальным образом конструируемой рекуррентной последовательности задач о назначениях. Приводится описание методики и характерных результатов экспериментального исследования вычислительных алгоритмов, реализующих предлагаемую схему поэтапного синтеза.