Теория расписаний, целочисленная оптимизация, методы агрегирования и декомпозиции

Преподаватели: 
Программа курса: 

Тема 1. Постановка задач теории расписаний. Критерии оценки расписаний.

Проблемы упорядочения работ. Основные понятия и определения. Постановка задач теории расписаний. Исходные данные для построения расписаний. Искомые величины при составлении расписаний. Критерии оптимальности расписаний. Формы представления расписаний. Упорядочение конечного числа работ для одной машины. Переналадки оборудования. Задача коммивояжера.

Тема 2. Задача Джонсона. Условия оптимальности для задачи Джонсона.

Постановка задачи Джонсона. Условия оптимальности для задачи Джонсона. Доказательство теоремы Джонсона. Алгоритм ее решения на основе условий оптимальности Джонсона и алгоритм Беллмана. Задача Джексона. Алгоритм ее решения.

Тема 3. Общая задача построения расписаний.

Основные виды задач теории расписаний. Линейная оптимизационная модель решения задач линейного программирования. Основные методы и подходы к решению задач теории расписаний. Методы локальных вариаций. Схема решения задач теории расписаний с использованием решающих правил. Простые и комбинированные решающие правила. Примеры решающих правил.

Тема 4. Задачи многокритериальной оптимизации.

Проблемы решения задач многокритериальной оптимизации. Основные методы решения задач многокритериальной оптимизации. Линейная свертка критериев. Метод контрольных показателей. Метод выделения основного критерия. Метод введения метрики в пространстве целевых функций. Метод последовательных уступок. Компромиссы Парето. Множества Парето.

Тема 5. Задачи целочисленного и смешанного линейного программирования.

Постановка задач целочисленного и смешанного линейного программирования. Особенности этих задач. Общие сведения об основных методах решения этих задач. Основные прикладные задачи, описываемые моделями целочисленного и смешанного линейного программирования. Задача о назначениях. Задача о коммивояжере. Задача о походном ранце. Целочисленные многогранные множества.

Тема 6. Алгоритмы отсекающей плоскости для задач целочисленного и смешанного линейного программирования.

Первый алгоритм Гомори. Схема метода и условия сходимости. Пример решения задачи. Второй алгоритм Гомори. Схема метода и условия сходимости. Пример решения задачи. Лексикографическое упорядочение.

Тема 7. Метод ветвей и границ.

Схема метода ветвей и границ и условия сходимости. Использование метода ветвей и границ для решения задачи Джонсона. Метод ветвей и границ для решения задач теории расписаний общего вида. Метод Ленд и Дойг для решения задач целочисленного и смешенного линейного программирования. Использование метода ветвей и границ для решения задачи коммивояжера.
Использование метода ветвей и границ для решения задачи о походном ранце. Стратегии ветвления в методе ветвей и границ.

Тема 8. Метод динамического программирования.

Принцип оптимальности Беллмана. Основное уравнение динамического программирования. Использование динамического программирования для решения задачи коммивояжера. Использование метода динамического программирования для решения задачи о походном ранце. Использование метода динамического программирования для решения задач дискретного программирования. Достоинства и недостатки метода динамического программирования. Сравнение с методом ветвей и границ.

Тема 9. Методы декомпозиции в задачах линейного программирования.

Методы декомпозиции. Сущность методов. Метод декомпозиции Данцига-Вулфа. Схема декомпозиции Корнаи-Липтака. Схема метода распределенного моделирования.

Тема 10. Методы агрегирования.

Методы агрегирования. Агрегирование в задачах планирования работ производств. Модель планирования производства с постоянным фондом рабочей силы. Модель планирования производства с переменным фондом рабочей силы. Модель планирования производства с переналадками. Использование методов агрегирования в задачах построения расписаний работ на уровне предприятий.

Тема 11. Задачи управления дискретными процессами.

Основные постановки задач управления дискретными процессами. Условия оптимальности для задач управления дискретными процессами. Основные методы решения задач управления дискретными процессами.

Тема 12. Математические методы моделирования сложных систем.

Сложные системы. Проблемы моделирования систем. Классификация методов моделирования сложных систем. Физическое моделирование. Математическое моделирование. Основные этапы моделирования систем. Методы имитационного моделирования сложных систем. Выбор инструментальных средств для моделирования систем. Методы обработки результатов моделирования. Методы принятия решений в задачах синтеза сложных систем.

Список литературы: 

Основная литература:
1. Зак Ю.А. Прикладные задачи теории расписаний и маршрутизации перевозок. М.: Книжный дом «Либроком», 2011.
2. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. М.: Наука, Главная редакция физико-математической литературы. 1975, 359 стр.
3. Пападимитру Х., Стайглиц К.. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985, 510 стр.
4. Сигал И.Х., Иванова А.П.. Введение в прикладное дискретное программирование. М.: ФИЗМАТЛИТ, 2007.
5. Шикин Е.В., Шикина Г.Е. Исследование операций. М.: «Издательство Проспект», 2008.
6. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969.
7.2 Дополнительная литература
7. Pinedo M.L. Planning and Scheduling in Manufacturing and Services. Springer Dordrecht Heidelberg London New York, 2009, 536 pp.
8. Pinedo M.L. Scheduling. Theory, Algorithms, and Systems. Springer Dordrecht Heidelberg London New York, 2008, 665 pp/
9. Хоботов Е.Н. О некоторых моделях и методах решения задач планирования в дискретных производственных системах // АиТ. - 2007. - № 12. - С. 85-100.
10. Сидоренко А.М., Хоботов Е.Н. Агрегирование при планировании работ на машиностроительных предприятиях // Теория и системы управления. – 2013. – № 5. C. 132-144.

Учебно-методическая литература:
11. Куняев М.С., Сидоренко А.М., Фирсов А.С., Хоботов Е.Н. Методы построения расписаний работ в производственных системах. Изд-во МГТУ им. Н.Э. Баумана, 2009, 31 стр.

Перечень ресурсов сети интернет:
1. http://lib.mipt.ru/ – электронная библиотека Физтеха
2. http://www.edu.ru – федеральный портал «Российское образование».
3. http://benran.ru –библиотека по естественным наукам Российской академии наук.