Теория расписаний
Преподаватели:
Программа курса:
Лекция 1. Введение в Теорию расписаний. Классификация задач. Определения, обозначения. История
Лекция 2. Задачи дискретной оптимизации. Задача разбиения. Задача о ранце. Задача коммивояжера. Задачи Теории графов
Лекция 3. Вычислительная сложность и методы решений задач. Классы P и NP, трудоемкость решения, полиномиальные и псевдополиномиальные алгоритмы, эвристические и метаэвристические методы.
Лекция 4. Одноприборные задачи. Классические задачи. Задачи с ресурсными ограничениями.
Лекция 5. Задачи с параллельными приборами. Взаимозаменяемые приборы.
Лекция 6. Задачи цеха. Многостадийные системы. Задачи open- , job- , flow-shop
Лекция 7. Задачи с отношениями предшествования. Одноприборные задачи. Задачи автопилота.
Лекция 8. Задачи с одинаковой продолжительностью обслуживания требований. Одно приборные и двух приборные задачи.
Лекция 9. Задачи балансировки производственной линии. Одно и двусторонняя линия. Задача мастера и подмастерья.
Лекция 10. Задача построения календарного плана проекта с учетом ограничения на ресурсы. Алгоритм диспетчеризации. Алгоритм ветвей и границ. Верхние и нижние оценки. Частные случаи. Программные продукты. Задача о распределении ресурсов по работам календарного плана.
Лекция 11. Стохастические задачи. Модели и методы решения.
Лекция 12. Типовые подходы к доказательству NP-трудности. На примерах одноприборных задач
Лекция 13. Метод динамического программирования для решения задачи Теории расписаний. На примерах решения задачи с двумя станциями, задачи с двумя приборами.
Лекция 14. Метод ветвей и границ для решения задачи Теории расписаний. На примере задачи RCPSP.
Лекция 15. Методы приближенного решения задач Теории расписаний. Эвристические и метаэвристические алгоритмы. Класс APX.
Список литературы:
Основная литература:
1. Уилсон Р.Дж. Введение в Теорию графов. - М.: Мир, 1977.
2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир. – 1982.
3. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование// М.: Физматлит, 2002.– 240 с.
4. Танаев В.С., Шкурба В.В. Введение в Теорию расписаний.// М.: Наука. Гл. ред. физ.-мат. лит., 1975.– 256 с.
5. Танаев В.С., Гордон В.С., Шафранский Я.М. Теория расписаний. Одностадийные системы// М.: Наука. Гл. ред. физ.-мат. лит., 1989.– 384 с.
6. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы// М.: Наука, Гл. ред. физ.-мат. лит., 1989.– 328 с.
7. Танаев В.С., Ковалёв М.Я., Шафранский Я.М. Теория расписаний. Групповые технологии. // Минск: Институт технической кибернетики НАН Беларуси, 1998. – 290 с.
8. Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема приближённого решения задач Теории расписаний. // Учебное пособие. – М.: МФТИ, 2008. – 222 С.
9. Лазарев А.А., Садыков Р.Р. Теория расписаний. Минимизация максимального временного смещения и суммарного взвешенного числа запаздывающих требований.// Научное издание. Вычислительный центр им. А.А. Дородницына РАН – 2007. – 135 С.
10. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Исследование задач с отношениями предшествования и ресурсными ограничениями.// Научное издание. Вычислительный центр им. А.А. Дородницына РАН – 2007. – 80 С.
11. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Минимизация суммарного запаздывания для одного прибора.// Научное издание. Вычислительный центр им. А.А. Дородницына РАН – 2006. – 134 С.
12. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. М.: МГУ, 2011. – 224 с.
13. Peter Brucker, Scheduling Algorithms, 2007, Springer Verlag