Введение
1 Задачииалгоритмывтеории расписаний 21
1.1 Классификация ресурсов 21
1.2 Классификация задач теории расписаний 23
1.2.1 Конфигурации машин 24
1.2.2 Характеристики работ 25
1.2.3 Целевые функции 26
1.2.4 Задачи теории расписаний с ограничениями на ресурсы 27
1.2.5 Система обозначений 27
1.3 Вычислительная сложность 29
1.4 Приближенные алгоритмы 31
1.5 История и основные этапы развития теории расписаний 32
2 Задачи теории расписаний с воспроизводимым ресурсом 37
2.1 Одна машина. Минимизация взвешенной суммы моментов окончания работ 39
2.1.1 NP-трудность 39
2.1.2 Приближенный алгоритм 48
2.2 Параллельные машины. Минимизация длины
расписания. Сложность задач и свойства допустимых расписаний 52
2.2.1 Зеркальный пример и зеркальное расписание 52
2.2.2 Задачи с воспроизводимым ресурсом и задача об упаковке в контейнеры 54
2.2.3 Две машины. Одинаковые длительности 55
2.2.4 Неограниченное число машин. Единичные длительности и положительная прибыль всех работ. Неаппроксимируемость 60
2.3 Параллельные машины. Минимизация длины расписания. Приближенные алгоритмы 62
2.3.1 Приближенные алгоритмы для задач с единичными длительностями 62
2.3.2 Приближенные алгоритмы для задач с произвольными длительностями 71
3 Энергетически эффективные расписания
3.1 Минимизация расхода энергии: от расписаний с прерываниями к расписаниям без прерываний
3.1.1 Одна машина. Свойства оптимальных расписаний на одной машине с прерываниями
3.1.2 Одна машина. Приближенный алгоритм
3.1.3 Параллельные машины. Согласованные времена поступления и директивные сроки
3.1.4 Параллельные машины.
Произвольные времена поступления и директивные сроки
3.2 Минимизация расхода энергии: линейное программирование и вероятностное округление 3.2.1 Вспомогательные утверждения
3.2.2 Неоднородная задача на параллельных машинах с прерываниями без переноса работ
3.2.3 Задача на одной машине без прерываний работ
3.2.4 Неоднородная задача на параллельных машинах с прерываниями и перемещениями работ 3.2.5 Цеховая задача рабочего типа с прерываниями операций .
4 Задачи построения расписаний с задержками передачи данных
4.1 Одновременная минимизация длины расписания и взвешенной суммы моментов окончания работ
4.1.1 Неограниченное число машин
4.1.2 Одновременная минимизация длины расписания и взвешенной суммы моментов окончания работ с доставками
4.1.3 Верхние оценки на существование (а,/3)-приближенных распи
4.1.4 Ограниченное число машин
4.2 Задачи с задержками в иерархической коммуникационной системе .
4.2.1 Линейное программирование
4.2.2 Нижняя оценка
4.2.3 Построение допустимого решения
4.2.4 Анализ точности
5 Маршрутизация машин в цеховых задачах открытого типа
Произвольное число машин. O(m)-Приближенный алгоритм
5.1.1 Приближенный алгоритм 5.1.2 Анализ точности алгоритма
5.3 Произвольное число машин. O(logm)-приближенный алгоритм Две машины, произвольная сеть
5.3.1 Приближенный алгоритм
5.3.2 Анализ точности алгоритма
5.7 5.4 Две машины, легкий пример задачи коммивояжера
5.4.1 Приближенный алгоритм
5.4.2 Свойства и точность алгоритма
5.9 5.5 Две машины, две вершины
5.5.1 Основные обозначения и предварительные результаты Достаточные условия для полиномиальной разрешимости зада чи R02V = 21 Cmax
5.5.3 Точный алгоритм и приближенная схема
5.5.4 Конфигурации оптимальных расписаний в трудных примерах
5.5.5 Построение оптимальной перестановки внутри идентичных бло 5.5.6 Алгоритм динамического программирования
5.5.7 Вполне приближенная полиномиальная схема Заключение
Литература
