Методы дискретной оптимизации в управлении проектами
№ п/п |
Разделы и темы лекционных занятий |
Содержание |
|
1 |
Введение в исследование операций. Задачи дискретной оптимизации и их сложность |
Проблематика исследования операций. Классификация задач и подходов. Общая постановка задачи дискретной оптимизации. Сложность задач дискретной оптимизации. Классы P и NP. Решение задачи дискретной оптимизации. Задача о ранце, как пример задачи дискретной оптимизации. |
|
2 |
Точные методы решения задач дискретной оптимизации |
Классификация точных методов решения задач дискретной оптимизации. Перебор. Метод динамического программирования. Графический метод. Нижние оценки и неявный перебор – метод ветвей и границ |
|
3 |
Приближенные методы решения задач дискретной оптимизации: эвристики и метаэвристики |
Приближенные методы решения задач дискретной оптимизации: эвристики и метаэвристики. Пример простейших эвристик – метод «затраты-эффект». Локальная оптимизация. Генетические алгоритмы. Понятие о метаэвристиках |
|
4 |
Основы дихотомического программирования |
Дихотомическое представление функций и ограничений. Линейная задача дискретного программирования. Решение задачи о ранце методом дихотомического программирования. Сетевое программирование и двойственные задачи |
|
5 |
Задачи мультипроектного управления: выбор варианта реализации программы |
Задача о ранце, как формализация задачи выбора оптимального портфеля проектов. Одномерная и многомерная задачи о ранце. Задача выбора варианта реализации программы и ее решение методом дихотомического программирования |
|
6 |
Задачи мультипроектного управления: оптимизация последовательности выполнения проектов |
Сетевые графики с рекомендательными зависимостями работ. Задача оптимизации последовательности выполнения проектов |
|
7 |
Задача определения продолжительности проекта, расчет критического пути |
Задача определения продолжительности проекта. Расчет критического пути. Метод PERT (Program Evaluation and Review Technique) |
|
8 |
Классификация задач распределения ресурсов между задачами проекта |
Классификация задач распределения ресурсов между задачами проекта. Задача Джонсона. Задача упаковки в полосу и задача LSPP. Задача упаковки в палеты и задача UPT. Другие частные случаи |
|
9 |
Алгоритм диспетчеризации и точные алгоритмы решения задачи распределения ресурсов |
Алгоритм диспетчеризации для задачи распределения ресурса. Нижние оценки для задачи распределения ресурсов и ее частных случаев. Точный алгоритм решения задачи распределения ресурсов методом ветвей и границ. |
|
10 |
Эвристические алгоритмы решения задачи распределения ресурсов |
Эвристические алгоритмы решения задачи распределения ресурсов: распределение по критичности, по позднему времени окончания, на работы с минимальной длительностью. Оценки сравнительной эффективности эвристик. Алгоритм муравьиных колоний |
|
11 |
Методы агрегирования работ и задачи распределения ресурсов |
Методы агрегирования работ и задачи распределения ресурсов. Агрегируемые сетевые графики и эффективный алгоритм решения задачи распределения ресурса |
|
12 |
Задачи оперативного управления проектом. Сокращение продолжительности проекта |
Задачи управления стоимостью проекта. Задача сокращения продолжительности проекта. Частные случаи и общий алгоритм. |
|
13 |
Задачи оперативного управления проектом. Управление потоком ресурсов проекта |
Задачи определения последовательности выполнения работ с учетом времени перемещения бригад. Двойная сетевая модель. |
|
Презентации и видео
- Введение в исследование операций
- Задачи дискретной оптимизации и их сложность
- Алгоритмические методы решения задач дискретной оптимизации
- Методы дихотомического и сетевого программирования
-
Задачи мультипроектного управления
Видео отсутствует
- Задачи распределения ресурсов между задачами проекта
- Другие задачи планирования проекта
Перечень контрольных вопросов
- Основные разделы науки исследования операций. Классификация задач исследования операций [3, глава 1]. Презентация 1.
- Задача принятия решения при неопределенности. Виды неопределенности и методы ее устранения. [3, параграф 5], Презентация 1.
- Общая постановка и этапы решения задач дискретной оптимизации. [5, глава 1], [4, глава 2].
- Сложность задач дискретной оптимизации. Задачи распознавания. Недетерминированные вычисления Классы P и NP. [4, раздел 2.2], также настоятельно рекомендуется [10, части 1, 2].
- Сводимость задач дискретной оптимизации. NP-полные и NP-трудные задачи. [4, раздел 2.2], [6, раздел 15.4], также настоятельно рекомендуется [10, часть 2].
- Характеризация задачи о ранце, как задачи дискретной оптимизации. [5, раздел 2.2].
- Теорема Кука: формулировка и основная идея доказательства. Сводимость задач дискретной оптимизации [6, раздел 15.5; 10, разделы 2.5, 2.6].
- Точные методы решения задач дискретной оптимизации. Перебор, метод ветвей и границ. [4, раздел 2.3.6], [5, раздел 3.1], [2, раздел 2.1], для углубленного изучения [6, глава 18].
- Точные методы решения задач дискретной оптимизации. Динамическое программирование, графический метод. [4, разделы 2.3.3 и 2.3.4], [5, глава 4], [2, раздел 2.1], для углубленного изучения [6, раздел 18.6].
- Приближенные методы решения задач дискретной оптимизации: локальная оптимизация (локальный поиск), жадные алгоритмы [5, разделы 1.3.3 и 5.7.1], [4, раздел 2.3.1], презентация 3, [2, раздел 2.1], дополнительно [6, глава 19].
- Метаэвристики: генетические алгоритмы. [4, раздел 2.3.2]
- Метаэвристики: алгоритм муравьиных колоний. [4, раздел 2.3.2]
- Метод дихотомического программирования. Теорема Колмогорова-Арнольда о дихотомическом представлении функций. [2, раздел 2.2].
- Метод дихотомического программирования и дихотомическое представление линейной задачи дискретного программирования. [2, раздел 2.5].
- Алгоритм дихотомического программирования для задачи о ранце. [2, раздел 2.5].
- Задача выбора оптимального портфеля проектов (задача о ранце). Точные и приближенные методы решения. [5, раздел 2.2], [2, раздел 2.5].
- Решение задачи выбора варианта реализации программы методом дихотомического программирования. [2, раздел 3.3].
- Сетевые графики с рекомендательными зависимостями работ. Оптимизация последовательности выполнения проектов методом дихотомического программирования. [2, раздел 3.1], презентация 5.
- Сетевые графики с рекомендательными зависимостями работ. Сведение к задаче линейного упорядочения (linear ordering). Оптимизация последовательности выполнения проектов с помощью лагранжевой релаксации. [7], презентация 5.
- Методы расчета критического пути. Задачи определения продолжительности проекта. Основные этапы метода PERT (Program Evaluation and Review Technique). Wiki, Презентация 6.
- Характеристика задачи распределения ресурсов между задачами проекта как задачи дискретной оптимизации [4, раздел 5.1].
- Задача Джонсона и алгоритм Джонсона [4, раздел 4.1].
- Частный случай LSPP. Сравнение задач упаковки в полосу и LSPP (like stripe packing problem) [4, раздел 5.8.1].
- Частный случай UPT (unit per time) [4, раздел 5.8.2].
- Частный случай PMS (parallel machine scheduling) [4, раздел 5.8.3].
- Алгоритм диспетчеризации (list scheduling) для задачи распределения ресурса и его свойства. [4, раздел 5.2].
- Нижние оценки для задачи распределения ресурсов проекта. [4, раздел 5.4].
- Нижняя оценка Буркова-Mingozzi для задачи распределения ресурсов. Ее вычисление методом (отложенной) генерации столбцов. [4, раздел 5.4.1], Презентация 6, [12].
- Правила диспетчеризации, основанные на параметрах требований и необходимых ресурсах. [4, раздел 5.6].
- Правила диспетчеризации, основанные на отношениях предшествования. [4, раздел 5.6].
- Правила диспетчеризации, основанные на информации о критическом пути. [4, раздел 5.6].
- Алгоритм муравьиных колоний для задачи распределения ресурсов проекта. [4, раздел 5.7].
- Агрегируемые сетевые графики. Вычисление эквивалентного объема агрегированной операции [8, раздел 1.3].
- Задача сокращения продолжительности проекта. Цепочка работ, произвольный сетевой график для целочисленной продолжительности работ. Задача о максимальном потоке. [9], Презентация 7.
- Распределение ресурсов по работам для линейной зависимости интенсивности от ресурса. Правила приоритетов. Оптимальность LST в частных случаях [1, глава 12].
Введение в исследование операций (видео, продолжение презентация)
-
Задачи дискретной оптимизации и их сложность (видео, презентация)
-
Алгоритмические методы решения задач дискретной оптимизации (видео, продолжение, презентация)
-
Введение в дихотомическое и сетевое программирование (видео, презентация)
-
Задачи мультипроектного управления (презентация)
-
Задачи планирования работ по проекту с учетом ограниченности ресурсов(видео, продолжение, презентация)
-
Другие задачи планирования проекта (видео, презентация)
Основная литература
- Алферов В.И., Баркалов С.А., Бурков В.Н., Курочка П.Н., Хорохордина Н.В., Шипилов В.Н. Прикладные задачи управления строительными проектами / Воронеж. гос. арх. – строит. ун-т. 2008. – 766 с.
- Буркова И.В. Метод дихотомического программирования в задачах управления проектами. Воронеж: ВГАСУ, 2004.
- Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, Главная редакция физико-математической литературы, 1980.
- Лазарев А.А., Гафаров Е.Р. Теория расписаний: задачи и алгоритмы. М: МГУ, 2011.
- Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. М.: Физматлит, 2003.
- Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.
- 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.
- Баркалов С.А., Бурков В.Н., Гилязов Н.М. Методы агрегирования в управлении проектами. М.: ИПУ РАН, 1999 – 55 с.
Дополнительная литература
- Баркалов П.С., Буркова И.В., Глаголев А.В., Колпачев В.Н. Задачи распределения ресурсов в управлении проектами. Москва: ИПУ РАН, 2002. – 65 с.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Пер. с англ. М.: Мир, 1982. 416 с.
- Нестеров Ю.Е. Введение в выпуклую оптимизацию. - М.: МЦНМО, 2010.
- 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.