Теория расписаний. Задачи и алгоритмы.

Description

Титульный лист Выходные данные Оглавление Предисловие редактора Введение 1 Общие сведения о теории расписаний 1.1 Предмет теории расписаний 1.1.1 Возникновение и этапы развития теории расписаний 1.1.2 Способы представления расписаний 1.2 Классификация задач ТР 1.2.1 Дополнительные условия в задачах ТР 1.2.2 Целевые функции в задачах ТР 1.2.3 Построение расписания для проекта. Project scheduling (PS) 1.2.4 Построение расписания для приборов. Machine scheduling (MS) 1.2.5 Система обозначений для задач Machine Scheduling 1.2.6 Составление временных таблиц (Time Tabling) Библиографическая справка 2 Методы решения задач комбинаторной оптимизации 2.1 Классические задачи дискретной оптимизации 2.2 Некоторые сведения о сложности (трудоемкости) задач комбинаторной оптимизации 2.2.1 Трудоемкость алгоритмов и полиномиально разрешимые задачи 2.2.2 Класс NP и труднорешаемые задачи 2.2.3 Классификация алгоритмов решения 2.3 Методы решения задач дискретной оптимизации 2.3.1 Эвристические алгоритмы 2.3.2 Мета эвристические методы 2.3.3 Метод динамического программирования 2.3.4 Графический метод 2.3.5 Алгоритм динамического программирования для задачи о двух конвейерах 2.3.6 Метод Ветвей и Границ 2.4 Задача о назначениях 2.5 Некоторые сведения из теории графов Библиографическая справка 3 Одноприборные задачи ТР 3.1 Одноприборные задачи 1 | r_j, p_j = 1, pmtn | Σ f_j 3.2 Минимизация числа запаздывающих требований 1 || Σ U_j 3.3 Минимизация взвешенного числа запаздывающих требований 1 || Σ w_j U_j 3.3.1 Графический алгоритм для задачи 1 || Σ w_j U_j 3.4 Минимизация суммарного запаздывания 1 || Σ T_j 3.4.1 Точный алгоритм решения задачи 1 || ΣT_j 3.4.2 Аппроксимационный алгоритм 3.4.3 Алгоритм Муравьиные Колонии 3.4.4 Гибридный алгоритм решения 3.4.5 Эффективность алгоритмов для тестовых примеров Поттса и ван Вассенхова 3.5 Минимизация обобщенной функции запаздывания 3.6 Одноприборные задачи с обратными критериями оптимизации 3.6.1 Доказательство NP-трудности задачи 1(nd) || max Σ w_j T_j 3.6.2 Псевдополиномиальный алгоритм решения задачи 1(nd) || max Σ T_j 3.6.3 Графический алгоритм решения задачи 1(nd) || max Σ T_j 3.7 Задачи с одним невозобновимым ресурсом Библиографическая справка 4 Задачи цеха (Shop problems) 4.1 Задачи F || C_max Библиографическая справка 5 Построение расписания для проекта 5.1 Практическая задача составления расписания проекта 5.2 Алгоритм диспетчеризации для задачи RCPSP 5.3 Задача RCPSP с прерываниями обслуживания требований 5.4 Нижние оценки для задачи RCPSP 5.4.1 Нижняя оценка Mingozzi 5.5 Соотношение оптимальных значений для задачи RCPSP с прерываниями и без прерываний 5.6 Алгоритмы вычисления верхних оценок для задачи RCPSP 5.7 Алгоритм Муравьиные Колонии для задачи RCPSP 5.8 Частные случаи задачи RCPSP c одним ресурсом 5.8.1 Частный случай LSPP 5.8.2 Частный случай UPT 5.8.3 Частный случай PMS 5.9 Сложности приближенного решения задачи RCPSP 5.10 Планарность сетевого графика для задач RCPSP и PMS Библиографическая справка 6 Приложения Доказательство NP-трудности задачи 1 || Σ T_j Таблица терминов и обозначений Кто есть кто в Теории Расписаний Литература