Алгоритмы решения многоресурсных задач теории расписаний и их применение

• Автор: Ильницкий, Александр Леонидович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Киев
• Количество страниц: 136 c. : ил

1. ПОСТАНОВКА ОБОБЩЕННОЙ ЗАДАЧИ ТЕОРИИ РАСПИСАНИЙ
1.1. Основные понятия
1.2. Решение вспомогательной задачи теории расписаний
1.3. Другие постановки задач теории расписаний и вычислительная сложность обобщенной многоресурсной задай теории расписаний
2. ДВОЙСТВЕННАЯ ОБОБЩЕННАЯ ЗАДАЧА ТЕОРИИ РАСПИСАНИЙ
2.1. Методы негладкой оптимизации при решении дискретных задач математического программирования
2.2. Промежуточная двойственная задача теории расписаний. Аддитивная целевая функция
2.3. Промежуточная двойственная задача теории расписаний. Минимизация общего времени выполнения системы работ
3. АЛГОРИТМИЧЕСКАЯ И ПРОГРАММНАЯ РЕАЛИЗАЦИЯ МЕТОДОВ РЕШЕНИЯ РЯДА ЗАДАЧ ТЕОРИИ РАСПИСАНИЙ
3.1. Задача определения очередности выполнения работ на одной машине
3.2. Динамическая задача выполнения VI работ с помощью М/ машин
3.3. Экспериментальное исследование эффективности алгоритмов

4. ЗАДАЧА ПЕРСПЕКТИВНОГО КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ СТРОИТЕЛЬНО-МОНТАЖНЫХ РАБОТ ДОМОСТРОИТЕЛЬНОГО КСМЕИНАТА
4.1. Описание и постановка
4.2. Алгоришы решения
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ I
ПРИЛОЖЕНИЕ 2

Во всей системе народнохозяйственного планирования СССР важное место занимает календарное и объемно-календарное планирование, оперативное управление. Задачи календарного планирования (КП) входят в состав, как определяющая часть, многих АСУ.
Постоянное усложнение постановок, увеличение объемов информации (при нынешнем высоком уровне концентрации сил и средств, росте основных фондов, номенклатуры используемых ресурсов) уже давно сделали невозможным решать задачи КП без широкого внедрения сов -ременных математических методов, средств автоматизации и вычислительной техники.
Предметом исследования задач КП, их математической природы является зародившаяся недавно теория расписаний. Дальнейшее развитие теория расписаний и календарное планирование в нашей стране получили благодаря работам Михалевича B.C., Танаева B.C., Шкур -бы В.В., Подчасовой Т.П., Гордона B.C., Шафранского Я.М., Кук -сы А.И., Мироносецкого Н.Б., Португала В.М. и др. [48,52,62,63,
69,71J . Известны и зарубежные публикации [31,64,79,80]
Кроме КП существуют многие другие сферы применения ТР. К задачам ТР относят распараллеливание алгоритмов на множестве элементарных операторов [4,5] , планирование работы вычислительной системы в мультипрограммном режиме [5,40 j и т.п.
При решении задач ТР нашли применение различные методы [7,31, 42,62,63,69,7о] . Задачи ТР сводились к линейным и линейным целочисленным задачам. Для некоторых из постановок был использован аппарат динамического программирования. Большое распространение по-лучил подход определения точных решений методом последовательного конструирования, анализа и отсеивания вариантов и его частным слу-

и зафиксируем оптимальное решение для первой операции работы
Рс : а»* ~<кс<&<| С&ь^НьСзъС'и)))}
С%С“>{ ^ Ц-1 НьСщМ)}}
$< кУ'! ~ {у е 5# I &Й, ((?£*/“■) = Н? )
Очевидно, составлять всю таблицу 6^ нет смысла. Запомним только значения 0^ , £ч> 60, 4% Ы), (аг^О«-))'
П-й этап - восстановление оптимальной траектории. Этап состоит в покомпонентном восстановлении оптимальных векторов ,
у у
? 4; . Для этого воспользуемся (последовательно по возрастанию ^ ) содержанием каждой из таблиц (5^
1-й шаг ( % е ) :
Ж5-М={%р,и)|р=
«у (-«■) = ?о-К Я?/-“) + ©ГО));
^■(0 = & + ©£б')).
Общий шаг С 0^ Ф <2(? , :
^'(^)={%(Р;^) | Р= 3£гЫ+ ©«-О
4н=?.}■ («, «5-н а ■>
-£|-«) = -бу гО)")'
По результатам второго этапа определяется обобщенный градиент (см.§2.1), необходимый для перехода к следующей итерации метода ОГС или *£ -алгоритма.
2.3. Промежуточная двойственная задача теории расписаний. Минимизация общего времени выполнения систем работ
Не теряя общности, для упрощения изложения допустим, что
Д*= Т4 » , &%(¥■)= 6$&), У€еЦ , 4 6 А, •
Тогда функции потребления ресурсов Чс^ ^ , % к.
(см.§1.1) зависят только от 3! - вектора начал операций.