Методы дискретной оптимизации в управлении проектами

Преподаватели: 
Губко М. В. (ИПУ РАН, Лаборатория 11) НЕАКТУАЛЬНАЯ ЗАПИСЬ
Программа курса: 

 

№

п/п

Разделы и темы лекционных занятий

Содержание

  
 

1

Введение в исследование операций. Задачи дискретной оптимизации и их сложность

Проблематика исследования операций. Классификация задач и подходов. Общая постановка задачи дискретной оптимизации. Сложность задач дискретной оптимизации. Классы P и NP. Решение задачи дискретной оптимизации. Задача о ранце, как пример задачи дискретной оптимизации.

 

2

Точные методы решения задач дискретной оптимизации

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

 

3

Приближенные методы решения задач дискретной оптимизации: эвристики и метаэвристики

Приближенные методы решения задач дискретной оптимизации: эвристики и метаэвристики. Пример простейших эвристик – метод «затраты-эффект». Локальная оптимизация. Генетические алгоритмы. Понятие о метаэвристиках

 

4

Основы дихотомического программирования

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

 

5

Задачи мультипроектного управления: выбор варианта реализации программы

Задача о ранце, как формализация задачи выбора оптимального портфеля проектов. Одномерная и многомерная задачи о ранце. Задача выбора варианта реализации программы и ее решение методом дихотомического программирования

 

6

Задачи мультипроектного управления: оптимизация последовательности выполнения проектов

Сетевые графики с рекомендательными  зависимостями работ. Задача оптимизации последовательности выполнения проектов

 

7

Задача определения продолжительности проекта, расчет критического пути

Задача определения продолжительности проекта. Расчет критического пути. Метод PERT (Program Evaluation and Review Technique)

 

8

Классификация задач распределения ресурсов между задачами проекта

Классификация задач распределения ресурсов между задачами проекта. Задача Джонсона. Задача упаковки в полосу и задача LSPP. Задача упаковки в палеты и задача UPT. Другие частные случаи

 

9

Алгоритм диспетчеризации и точные алгоритмы решения задачи распределения ресурсов

Алгоритм диспетчеризации для задачи распределения ресурса. Нижние оценки для задачи распределения ресурсов и ее частных случаев. Точный алгоритм решения задачи распределения ресурсов методом ветвей и границ.

 

10

Эвристические алгоритмы решения задачи распределения ресурсов

Эвристические алгоритмы решения задачи распределения ресурсов: распределение по критичности, по позднему времени окончания, на работы с минимальной длительностью. Оценки сравнительной эффективности эвристик. Алгоритм муравьиных колоний

 

11

Методы агрегирования работ и задачи распределения ресурсов

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

 

12

Задачи оперативного управления проектом. Сокращение продолжительности проекта

Задачи управления стоимостью проекта. Задача сокращения продолжительности проекта. Частные случаи и общий алгоритм.

 

13

Задачи оперативного управления проектом. Управление потоком ресурсов проекта

Задачи определения последовательности выполнения работ с учетом времени перемещения бригад. Двойная сетевая модель.

 
 

Презентации и видео

  1. Введение в исследование операций

  2. Задачи дискретной оптимизации и их сложность

  3. Алгоритмические методы решения задач дискретной оптимизации

  4. Методы дихотомического и сетевого программирования

  5. Задачи мультипроектного управления

    Видео отсутствует

  6. Задачи распределения ресурсов между задачами проекта

  7. Другие задачи планирования проекта

Перечень контрольных вопросов

  1. Основные разделы науки исследования операций. Классификация задач исследования операций [3, глава 1]. Презентация 1.
  2. Задача принятия решения при неопределенности. Виды неопределенности и методы ее устранения. [3, параграф 5], Презентация 1.
  3. Общая постановка и этапы решения задач дискретной оптимизации. [5, глава 1], [4, глава 2].
  4. Сложность задач дискретной оптимизации. Задачи распознавания. Недетерминированные вычисления Классы P и NP. [4, раздел 2.2], также настоятельно рекомендуется [10, части 1, 2].
  5. Сводимость задач дискретной оптимизации. NP-полные и NP-трудные задачи. [4, раздел 2.2], [6, раздел 15.4], также настоятельно рекомендуется [10, часть 2].
  6. Характеризация задачи о ранце, как задачи дискретной оптимизации. [5, раздел 2.2].
  7. Теорема Кука: формулировка и основная идея доказательства. Сводимость задач дискретной оптимизации [6, раздел 15.5; 10, разделы 2.5, 2.6].
  8. Точные методы решения задач дискретной оптимизации. Перебор, метод ветвей и границ. [4, раздел 2.3.6], [5, раздел 3.1], [2, раздел 2.1], для углубленного изучения [6, глава 18].
  9. Точные методы решения задач дискретной оптимизации. Динамическое программирование, графический метод. [4, разделы 2.3.3 и 2.3.4], [5, глава 4], [2, раздел 2.1], для углубленного изучения [6, раздел 18.6].
  10. Приближенные методы решения задач дискретной оптимизации: локальная оптимизация (локальный поиск), жадные алгоритмы [5, разделы 1.3.3 и 5.7.1], [4, раздел 2.3.1], презентация 3, [2, раздел 2.1], дополнительно [6, глава 19].
  11. Метаэвристики: генетические алгоритмы. [4, раздел 2.3.2]
  12. Метаэвристики: алгоритм муравьиных колоний. [4, раздел 2.3.2]
  13. Метод дихотомического программирования. Теорема Колмогорова-Арнольда о дихотомическом представлении функций. [2, раздел 2.2].
  14. Метод дихотомического программирования и дихотомическое представление линейной задачи дискретного программирования. [2, раздел 2.5].
  15. Алгоритм дихотомического программирования для задачи о ранце. [2, раздел 2.5].
  16. Задача выбора оптимального портфеля проектов (задача о ранце). Точные и приближенные методы решения. [5, раздел 2.2], [2, раздел 2.5].
  17. Решение задачи выбора варианта реализации программы методом дихотомического программирования. [2, раздел 3.3].
  18. Сетевые графики с рекомендательными  зависимостями работ. Оптимизация последовательности выполнения проектов методом дихотомического программирования. [2, раздел 3.1], презентация 5.
  19. Сетевые графики с рекомендательными  зависимостями работ. Сведение к задаче линейного упорядочения (linear ordering). Оптимизация последовательности выполнения проектов с помощью лагранжевой релаксации. [7], презентация 5.
  20. Методы расчета критического пути. Задачи определения продолжительности проекта. Основные этапы метода PERT (Program Evaluation and Review Technique). Wiki, Презентация 6.
  21. Характеристика задачи распределения ресурсов между задачами проекта как задачи дискретной оптимизации [4, раздел 5.1].
  22. Задача Джонсона и алгоритм Джонсона [4, раздел 4.1].
  23. Частный случай LSPP. Сравнение задач упаковки в полосу и LSPP (like stripe packing problem) [4, раздел 5.8.1].
  24. Частный случай UPT (unit per time) [4, раздел 5.8.2].
  25. Частный случай PMS (parallel machine scheduling) [4, раздел 5.8.3].
  26. Алгоритм диспетчеризации (list scheduling) для задачи распределения ресурса и его свойства. [4, раздел 5.2].
  27. Нижние оценки для задачи распределения ресурсов проекта. [4, раздел 5.4].
  28. Нижняя оценка Буркова-Mingozzi для задачи распределения ресурсов. Ее вычисление методом (отложенной) генерации столбцов. [4, раздел 5.4.1], Презентация 6, [12].
  29. Правила диспетчеризации, основанные на параметрах требований и необходимых ресурсах. [4, раздел 5.6].
  30. Правила диспетчеризации, основанные на отношениях предшествования. [4, раздел 5.6].
  31. Правила диспетчеризации, основанные на информации о критическом пути. [4, раздел 5.6].
  32. Алгоритм муравьиных колоний для задачи распределения ресурсов проекта. [4, раздел 5.7].
  33. Агрегируемые сетевые графики. Вычисление эквивалентного объема агрегированной операции [8, раздел 1.3].
  34. Задача сокращения продолжительности проекта. Цепочка работ, произвольный сетевой график для целочисленной продолжительности работ. Задача о максимальном потоке. [9], Презентация 7.
  35. Распределение ресурсов по работам для линейной зависимости интенсивности от ресурса. Правила приоритетов. Оптимальность LST в частных случаях [1, глава 12].
Видео лекций: 

Введение в исследование операций (видео, продолжение презентация)

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

Основная литература

  1. Алферов В.И., Баркалов С.А., Бурков В.Н., Курочка П.Н., Хорохордина Н.В., Шипилов В.Н. Прикладные задачи управления строительными проектами / Воронеж. гос. арх. – строит. ун-т. 2008. – 766 с.
  2. Буркова И.В. Метод дихотомического программирования в задачах управления проектами. Воронеж: ВГАСУ, 2004.
  3. Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, Главная редакция физико-математической литературы, 1980.
  4. Лазарев А.А., Гафаров Е.Р. Теория расписаний: задачи и алгоритмы. М: МГУ, 2011.
  5. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Физматлит, 2003.
  6. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.
  7. I. Charon, O. Hudry. A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments / Discrete Applied Mathematics 154 (2006) 2097 – 2116.
  8. Баркалов С.А., Бурков В.Н., Гилязов Н.М. Методы агрегирования в управлении проектами. М.: ИПУ РАН, 1999 – 55 с.

Дополнительная литература

  1. Баркалов П.С., Буркова И.В., Глаголев А.В., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами. Москва: ИПУ РАН, 2002. – 65 с.
  2. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М.: Мир, 1982. 416 с.
  3. Нестеров Ю.Е. Введение в выпуклую оптимизацию. - М.: МЦНМО, 2010.
  4. T. Baar, P. Brucker, S. Knust. Tabu Search Algorithms and Lower Bounds for the Resource-Constrained  Project Scheduling Problem. In “Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization”. Springer, 1999.
Вопросы для устного экзамена: 
Иконка PDF Вопросы к зачету.pdf