Организация вычислительного процесса решения одного класса задач теории расписаний методом дискретного динамического программирования (на примере энергетического производства)

• Автор: Калиновский, Яков Александрович
• Шифр специальности: 05.13.13, 05.14.02
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 253 c. : ил

ВВЕДЕНИЕ
ГЛАВА I. ТЕОРЕТИЧЕСКИЕ И ПРАКТИЧЕСКИЕ АСПЕКТЫ ОРГАНИЗАЦИИ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА РЕШЕНИЯ ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ

1.1. Характеристики и особенности задач теории расписаний.

1.2. Выявление областей практического применения задач теории расписаний

1.3. Анализ основных методов оптимизации графи

ков остановок

1.4Постановка задач дальнейших исследований.

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

2.1. Математическая формулировка задачи.

2.2. Принцип оптимальности

2.3. Выявление параметров, характеризующих систему на стадии динамического программирования
2.4. Система уравнений Беллмана.
2.5. Численное решение системы уравнений Беллмана.
ГЛАВА 3. МЕТОДЫ УЛУЧШЕНИЯ ВРЕМЕННЫХ ХАРАКТЕРИСТИК ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА РЕШЕНИЯ ЗАДАЧ ПЛАНИРОВАНИЯ ОПТИМАЛЬНЫХ ГРАФИКОВ ОСТАНОВОК.
3.1. Декомпозиция задачи.
Стр.
3.2. Методы перебора состояний ьи
3.3. Приведение целевой функции к сепарабельному
3.4. Распараллеливание вычислительного процесса.
3.5. Разработка квазиоптимальных графиков. ЮО
ГЛАВА 4. РАЗРАБОТКА ОДНОЙ ПРАКТИЧЕСКОЙ МОДЕЛИ ПЛАНИРОВАНИЯ ГРАФИКА ОСТАНОВОК
4.1. Исследование модели. ЮЗ
4.2. Структура целевой функции и декомпозиции задачи
4.3. Организация вычислений экономических показателей модели
4.4. Организация вычислений надежностных показателей модели
ГЛАВА 5. ОСОБЕННОСТИ ОРГАНИЗАЦИИ И ПРОГРАММНОЙ РЕАЛИ. ЗАЦИИ ВЫЧИСЛИТЕЛЬНЫ ПРОЦЕССОВ ОПТИМИЗАЦИИ ГРАФИКОВ РЕМОНТОВ ОСНОВНОГО ОБОРУДОВАНИЯ ЭНЕРГОСИСТЕМ.
5.1. Формулировка задачи оптимизации графиков ремонтов основного оборудования энергосистем .
5.2. Особенности организации вычислительного процесса оптимизации графиков ремонтов основного оборудования энергосистем.
5.3. Приведение топливной составляющей к сепарабельному виду.
5.4. Особенности программной реализации вычислительных процессов оптимизации графиков ремонтов основного оборудования
ВЫВОДЫ .
ЛИТЕРАТУРА


Функциональное уравнение 1. Идея решения заключается в следующем. Решение начинается с конца процесса. Намечаются всевозможные входы 1-й стадии, как показано на рис. Переходу в Ці из любого хА соответствует ДОХОД /? Х1 , то решение только одно и оно оптимально. На рис. Из каждого входа второй стадии X^ можно попасть на выход одним? Для ХІ , например, это будут: ХХ) х'хх;Л) . Из этих путей в соответствии с 1. Таким образом, зная любой из входов второй стадии, можно построить оптимальную последовательность решений на двух последних стадиях. Рассматривая таким образом все стадии от конечной до начальной, получим одну или более траекторий, выходящих из начального входа и приносящих максимальный доход. Если траектории несколько, то им соответствет одинаковый доход. Пример такого построения для более сложной задачи показан на рис. Для решения уравнения 1. С увеличением числа возможных входов объем вычислений резко возрастает. Для разрешения противоречия между требованиями к точности и объемом вычислений можно применить метод измельчений сеток. Он основан на предварительном решении задачи при небольшом числе входов и нахождении приблизительных границ, в которых проходит оптимальная траектория, с последующим уточнением решения, когда входв выбираются в определенных ранее границах так, что интервал между ними будет значительно меньше. Принцип оптимальности применим к задачам и с непрерывным "временем", если под "временем" подразумевать ту величину, по которой можно расчленить задачу на стадии. Рис. Построение оптимальной траектории (отмечена штриховой линией). Рис. К геометрической интерпретации зада'/и. Как показано в [-/5] , применение принципа оптимальности к задаче (1. V = у. Решение (1. Однако, даже численное решение уравнений типа (1. Поэтому целесообразен переход к оптимизации дискретного аналога интеграла (1. XI = Х(с? Уравнение (1. Интеграл (1. FCx,})d. HF(xLjyc')(li. О ^ Ц; ^ ОС; (1. Сс) = max d zL tCxi, у-1). Сс} = max Ld*:(c,v)+fu. H?&(c,v))], П. FC с if) (1. Система (1. Алгоритмы решения дискретных аналогов . ЭВМ. Объем вычислений возрастает приблизительно линейно с числом стадий задачи, а не экспоненциально, как обычно. Метод динамического программирования позволяет заметно сократить объем вычислений по сравнению с полным перебором. Например, . К /. А/ раз. При наличии ограничений, исключающих возможность применения некоторых вариантов, ото соотношение изменяется в пользу динамического программирования. Важным свойством метода динамического программирования является то, что он дает глобальный оптимум для весьма широкого класса задач. Рассмотрим некоторую производственную систему 5 > состоящую из множества машин [, работающих параллельно, то-есть потребляющих однородное сырьё и производящих однородную продукцию. Каждая из машин характеризуется экономической и надежностной характеристиками. Г системы Б в течение всего интервала времени должны быть минимальными. И=1. Издержки /ГО , состоящие из экономических и надежностных компонентов, зависят как от плана выпуска продукции ^'ГО, так и от состава работающих машин Mj в момент времени I , который, в свою очередь, является непостоянным по с л едующим причинам. В процессе эксплуатации экономические и надежностные характеристики машин ухудшаются вследствии износа. Поэтому машины нуждаются в периодических остановках,периодичность и длительность которых определяется системой планово-предупредительных ремонтов (ППР), основным принципом которой является предотвращение аварий, а не устранение их. Длительность остановки машины не является постоянной величиной, а зависит от расхода ремонтных ресурсов (наличия рабочей силы, материалов, запчастей и пр), общее количество которых ограничено. Изменение длительностей остановок также влияет на издержки производства. Как видно из вышеизложенного, остановки машин необходимо планировать заранее. При этом необходимо определить как срок начала каждой остановки, так и её длительность. Совокупность этих величин в дальнейшем будем называть графиком остановок.