М.: Московский государственный университет им. М.В. Ломоносова
(МГУ), 2011. — 222 с.
В данном учебном пособии приводятся базовые сведения о специальном
разделе дискретной математики - Теории расписаний. Описаны этапы
становления теории, свойства и классификации задач теории
расписаний, методы их решения. На примерах классических задач
представлены приемы доказательства их трудоемкости и алгоритмы
решения.
Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, сталкивающихся с задачами объемно-календарного планирования. Содержание:
Общие сведения о теории расписаний.
Предмет теории расписаний.
Возникновение и этапы развития теории расписаний.
Способы представления расписаний.
Классификация задач ТР.
Дополнительные условия в задачах ТР.
Целевые функции в задачах ТР.
Построение расписания для проекта Project scheduling (PS).
Построение расписания для приборов Machine scheduling (MS).
Система обозначений для задач Machine Scheduling.
Составление временных таблиц (Time Tabling).
Методы решения задач комбинаторной оптимизации.
Классические задачи дискретной оптимизации.
Некоторые сведения о сложности (трудоемкости) задач комбинаторной оптимизации.
Трудоемкость алгоритмов и полиномиально разрешимые задачи.
Класс NP и труднорешаемые задачи.
Классификация алгоритмов решения.
Методы решения задач дискретной оптимизации.
Эвристические алгоритмы.
Метаэвристические методы.
Метод динамического программирования.
Графический метод.
Алгоритм динамического программирования для задачи о двух конвейерах.
Метод ветвей и границ.
Задача о назначениях.
Некоторые сведения из теории графов.
Одноприборные задачи ТР.
Одноприборные задачи.
Минимизация числа запаздывающих требований.
Минимизация взвешенного числа запаздывающих требований.
Графический алгоритм.
Минимизация суммарного запаздывания.
Точный алгоритм решения задачи 1|| Σ Tj.
Аппроксимационный алгоритм.
Алгоритм Муравьиные колонии.
Гибридный алгоритм решения.
Эффективность алгоритмов для тестовых примеров Поттса и ван Вассенхова.
Минимизация обобщенной функции запаздывания.
Одноприборные задачи с обратными критериями оптимизации.
Доказательство NP-трудности задачи 1(nd)|| max Σ Tj.
Псевдополиномиальный алгоритм решения задачи 1(nd)|| max Σ Tj.
Графический алгоритм решения задачи 1(nd)|| max Σ Tj.
Задачи с одним невозобновимым ресурсом.
Задачи цеха (Shop problems)
Задачи F||Cmax.
Построение расписания для проекта
Практическая задача составления расписания проекта.
Алгоритм диспетчеризации для задачи RCPSP.
Задача RCPSP с прерываниями обслуживания требований.
Нижние оценки для задачи RCPSP.
Нижняя оценка Mingozzi.
Соотношение оптимальных значений для задачи RCPSP с прерываниями и без прерываний.
Алгоритмы вычисления верхних оценок для задачи RCPSP.
Алгоритм Муравьиные колонии для задачи RCPSP.
Частные случаи задачи RCPSP c одним ресурсом.
Частный случай LSPP.
Частный случай UPT.
Частный случай PMS.
Сложности приближенного решения за дачи RCPSP.
Планарность сетевого графика для задач RCPSP и PMS.
Доказательство NP-трудности задачи 1|| Σ Tj.
Таблица терминов и обозначений.
Кто есть кто в Теории расписаний.
Учебное пособие основано на курсе лекций, читаемых в МФТИ, МГУ и ВШЭ, и предназначено для студентов и преподавателей вузов математических специальностей, специалистов в области управления и практиков, сталкивающихся с задачами объемно-календарного планирования. Содержание:
Общие сведения о теории расписаний.
Предмет теории расписаний.
Возникновение и этапы развития теории расписаний.
Способы представления расписаний.
Классификация задач ТР.
Дополнительные условия в задачах ТР.
Целевые функции в задачах ТР.
Построение расписания для проекта Project scheduling (PS).
Построение расписания для приборов Machine scheduling (MS).
Система обозначений для задач Machine Scheduling.
Составление временных таблиц (Time Tabling).
Методы решения задач комбинаторной оптимизации.
Классические задачи дискретной оптимизации.
Некоторые сведения о сложности (трудоемкости) задач комбинаторной оптимизации.
Трудоемкость алгоритмов и полиномиально разрешимые задачи.
Класс NP и труднорешаемые задачи.
Классификация алгоритмов решения.
Методы решения задач дискретной оптимизации.
Эвристические алгоритмы.
Метаэвристические методы.
Метод динамического программирования.
Графический метод.
Алгоритм динамического программирования для задачи о двух конвейерах.
Метод ветвей и границ.
Задача о назначениях.
Некоторые сведения из теории графов.
Одноприборные задачи ТР.
Одноприборные задачи.
Минимизация числа запаздывающих требований.
Минимизация взвешенного числа запаздывающих требований.
Графический алгоритм.
Минимизация суммарного запаздывания.
Точный алгоритм решения задачи 1|| Σ Tj.
Аппроксимационный алгоритм.
Алгоритм Муравьиные колонии.
Гибридный алгоритм решения.
Эффективность алгоритмов для тестовых примеров Поттса и ван Вассенхова.
Минимизация обобщенной функции запаздывания.
Одноприборные задачи с обратными критериями оптимизации.
Доказательство NP-трудности задачи 1(nd)|| max Σ Tj.
Псевдополиномиальный алгоритм решения задачи 1(nd)|| max Σ Tj.
Графический алгоритм решения задачи 1(nd)|| max Σ Tj.
Задачи с одним невозобновимым ресурсом.
Задачи цеха (Shop problems)
Задачи F||Cmax.
Построение расписания для проекта
Практическая задача составления расписания проекта.
Алгоритм диспетчеризации для задачи RCPSP.
Задача RCPSP с прерываниями обслуживания требований.
Нижние оценки для задачи RCPSP.
Нижняя оценка Mingozzi.
Соотношение оптимальных значений для задачи RCPSP с прерываниями и без прерываний.
Алгоритмы вычисления верхних оценок для задачи RCPSP.
Алгоритм Муравьиные колонии для задачи RCPSP.
Частные случаи задачи RCPSP c одним ресурсом.
Частный случай LSPP.
Частный случай UPT.
Частный случай PMS.
Сложности приближенного решения за дачи RCPSP.
Планарность сетевого графика для задач RCPSP и PMS.
Доказательство NP-трудности задачи 1|| Σ Tj.
Таблица терминов и обозначений.
Кто есть кто в Теории расписаний.