Свойства оптимальных расписаний и эффективные алгоритмы решения некоторых NP - трудных задач теории расписаний для одного прибора

Содержание
Введение
1 Свойства оптимальных расписаний задачи минимизации максимального временного смещения
1.1 Постановка задачи
1.2 Свойства оптимальных расписаний общего случая задачи
1 гЬтах.
1.3 Свойства оптимальных расписаний частных случаев задачи 1гуЬтах
2 Эффективные алгоритмы решения задачи минимизации максимального временного смещения
2.1 Процедура построения приближенного расписания для задачи 1г с1Ь1тх. Оценка абсолютной погрешности
2.2 Процедура построения допустимого расписания для задачи 1г Ьпи1Х.
2.3 Алгоритм решения задачи 1г1 г у, с1г ЛуЬ7Пах .
2.4 Полиномиальные алгоритмы решения частных случаев
задачи 1г, Гу, Ьпмх бб
2.5 Приближенный алгоритм решения общего случая задачи.
Оценка абсолютной погрешности.
3 Задача минимизации суммарного запаздывания
3.1 Постановка задачи и некоторые ее свойства.
3.2 Свойства оптимальных расписаний частного случая задачи
3.3 Полиномиальный алгоритм решения частного случая задачи .
Заключение
Список литературы