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

Программа курса: 

 

п/п

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

Содержание

 
 

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.  Сложность задач дискретной оптимизации. Классы P и NP.

4.  NP-сложные и NP-трудные задачи.

5.  Характеризация задачи о ранце, как задачи дискретной оптимизации.

6.  Точные методы решения задач дискретной оптимизации. Перебор, динамическое программирование, графический метод, метод ветвей и границ.

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

8.  Метод дихотомического программирования. Теорема Колмогорова-Арнольда о дихотомическом представлении функций.

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

10.  Алгоритм дихотомического программирования для задачи о ранце.

11.  Сетевое программирование и двойственные задачи.

12.  Задача выбора оптимального портфеля проектов. Точные и приближенные методы решения.

13.  Решение задачи выбора варианта реализации программы методом дихотомического программирования.

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

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

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

17.  Задача Джонсона и алгоритм Джонсона.

18.  Сравнение задач упаковки в полосу и LSPP (like stripe packing problem).

19.  Сравнение задач упаковки в палеты и UPT (unit per time).

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

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

22.  Анализ эвристики распределения ресурсов по критичности работ

23.  Анализ эвристики распределения ресурсов по позднему времени окончания,

24.  Анализ эвристики распределения ресурсов на работы с минимальной длительностью.

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

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

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

28.  Задачи управления стоимостью проекта. Общий алгоритм решения задачи сокращения продолжительности проекта для целочисленной продолжительности работ.

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

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

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

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

  4. Введение в дихотомическое и сетевое программирование (видеопрезентация)

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

  6. Задачи планирования работ по проекту с учетом ограниченности ресурсов(видео,продолжениепрезентация)

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

 

Список литературы: 
  1. Алферов В.И., Баркалов С.А., Бурков В.Н. и др. Прикладные задачи управления строительными проектами. Воронеж: ОАО «Центрально-черноземное книжное издательство», 2008.
  2. Буркова И.В. Метод дихотомического программирования в задачах управления проектами. Воронеж: ВГАСУ, 2004.
  3. Лазарев А.А., Гафаров Е.Р. Теория расписаний: задачи и алгоритмы. М: МГУ, 2011.
  4. Бурков В.Н., Буркова И.В. Метод сетевого программирования (готовится к печати). 2013.

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

  1. Матвеев А.А., Новиков Д.А., Цветков А.В. Модели и методы управления портфелями проектов. М.:   ПМСОФТ, 2005.
  2. Бурков В.Н., Заложнев А.Ю., Новиков Д.А. Теория графов в управлении организационными системами. М.: Синтег, 2001.Баркалов С.А., Бурков В.Н. Минимизация упущенной выгоды в задачах управления проектами. М.: ИПУ РАН, 2001.
  3. Баркалов С.А., Буркова И.В., Колпачев В.Н., Потапенко А.М. Модели и методы распределения ресурсов в управлении проектами. М.: ИПУ РАН, 2004.
  4. Лазарев А.А. Теория расписаний. Оценки абсолютной погрешности и схема прибли­жённого решения задач теории расписаний./ / Учебное пособие. М.: МФТИ, 2008.