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

В течение нескольких последних десятилетий сформировалась новая область науки и знаний — управление проектами (ProjectManagement). Под термином «проект» понимают ограниченное во времени целенаправленное предприятие, имеющее требования к привлекаемым ресурсам и качеству конечных результатов и предназначенное для создания уникальных продуктов, услуг или результатов. Таким образом, управление проектами — это приложение знаний, опыта, инструментов и методов к операциям проекта для удовлетворения требований, предъявляемых к проекту .

Управление проектами сегодня — это важнейший инструмент управления не только созданием новых продуктов и услуг, но и осуществлением целенаправленных изменений в рамках отдельных организаций, предприятий, а также целых социально-экономических и организационных систем. Сложно найти такую область деятельности человечества, где не использовались бы проекты. В частности управление проектами широко используется при создании и внедрении автоматизированных информационных систем управления ресурсами предприятия (в том числе управлением финансово-хозяйственной деятельностью и технологическими процессами).

Любой проект имеет определенную структуру — набор задач (операций/работ) или подпроектов, взаимоувязанных между собой, выполнение которых обеспечивает получение требуемого результата проекта.

Управление проектами ставит перед исследователями и руководителями проектов ряд нетривиальных задач, решение которых в общем случае не всегда оптимально или отсутствует вовсе. Таким образом, среди них можно выделить задачи ресурсного планирования, оптимального распределения ресурсов, минимизации упущенной выгоды, оптимизации проектов по стоимости и пр. Руководители проектов, сталкиваясь с подобными задачами в своей практике, зачастую действуют на основе своего опыта или по наитию.

На сегодняшний день теория управления проектами является бурно развивающимся разделом теории управления социально-экономическими системами. Можно выделить несколько различных направлений в управлении проектами.

Во-первых, это — модели календарно-сетевого планирования и управления (КСПУ), с появления которых и зародилось управление проектами.

Во-вторых, это — «качественный» подход к управлению проектами, близкий по своей методологии к менеджменту организаций и развиваемый, в основном, зарубежными учеными.

И, наконец, в-третьих, это — «количественный» подход, основывающийся на анализе и синтезе математических моделей механизмов управления проектами (процедурах принятия управленческих решений) и развиваемый, в основном, отечественными учеными. Настоящая статья исследует аспекты количественного подхода.

Развитие общества, экономики, организации, да и жизни отдельного человека можно представить себе как совокупность дискретных процессов с заданными конечными целями, протекающими в условиях ограниченного времени и ограниченных ресурсов. Человеку удобно делить процесс своей деятельности на локальные процессы, которые требуют для своей реализации специальных методов управления. В основу методов управления проектами заложено представление проекта в виде сетевого графика, отражающего зависимость между различными операциями проекта. Сложностью решения дискретных задач управления проектами (задач дискретной оптимизации) заключается в том, что число допустимых решений экспоненциально растет с ростом размерности задачи n. Поэтому простой перебор всех решений невозможен при больших n. В то же время эти задачи относятся, как правило, к классу NP-полных задач, для которых не существует методов их точного решения, отличных от перебора.

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

Данную задачу целесообразно решать методом динамического программирования, дающим точное решение. В основе метода динамического программирования лежит сведение задачи оптимизации к задаче определения экстремальной траектории (минимальной или максимальной длины) в некотором специальным образом построенном семействе возможных траекторий. В соответствии с принципом оптимальности Беллмана: любой участок оптимальной траектории оптимален. В случае дискретных задач метод динамического программирования сводится к определению пути максимальной или минимальной длины в специальным образом построенной сети .

В качестве примера рассмотрим комплекс независимых работ проекта, с заданным временем выполнения каждой работы t-_i и полезностью u_i. Под полезностью работы будем понимать число работ, связанных с данной работой, которые становятся доступными для выполнения после завершения текущей работы.

Требуется выбрать подмножество работ M так, чтобы их суммарная полезность.

была максимальной при ограничении на общее время выполнения T:

динамический программирование беллман Способ построения сети рассмотрим на примере из пяти работ, данные о полезности и времени которых приведены в таблице 1.

Таблица 1 — Данные примера.

Положим T = 10. Строим на плоскости систему координат, ось которой соответствует работам, а вторая — времени их выполнения. По оси работ отмечаем номера работ 1.5 (рис. 1). Из начала координат проводим две дуги: одна — горизонтальная в точку (1, 0), а другая — наклонная в точку (1, 3), где 3 — время выполнения первой работы. Первая дуга соответствует случаю, когда первая работа не выполняется, а вторая — когда выполняется. Из каждой полученной точки (1, 0) и (1, 3) проводим также по две дуги для второй работы. Получаем четыре точки (2, 0), (2, 4), (2, 3) и (2, 7), соответствующие четырем возможным вариантам для двух работ. Продолжая таким образом, получим сеть, приведенную на рис. 1, содержащую множество D всех возможных решений задачи.

Рисунок 1. Метод динамического программирования.

Очевидно, что любой путь в сети, из начальной вершины 0 в одну из конечных вершин соответствует некоторому набору работ. И наоборот, любому набору работ, с общим временем выполнения не более 10 однозначно соответствует путь в сети, соединяющей начальную вершину с одной из конечных. Значение координаты по второй оси равно суммарному времени выполнения работ. Примем длины горизонтальных дуг равными 0, а длины наклонных равными полезности соответствующей работы. В этом случае длина пути, соединяющего начальную вершину с одной из конечных, равна суммарной полезности соответствующего набора работ. Таким образом, задача свелась к определению пути, имеющего максимальную длину. Путь максимальной длины выделен на рис. 1 жирными дугами; суммарная полезность U равна 14.

При решении данной задачи методом динамического программирования число допустимых решений равно 2ⁿ. Таким образом, для данного примера число путей в сети равно 32, а при большом n перебор всех возможных вариантов решений становится весьма трудоемким.

Возможное улучшение метода — использование комбинации эвристического алгоритма и метода динамического программирования, которая выглядит следующим образом:

Шаг 1. Введем понятие коэффициента полезности работы K^u_-, определяемого следующим образом:

(3).

Вычислим K^u_- для каждой работы и ранжируем работы по убыванию K^u_-. Из получившейся последовательности выбираем первые kработ, сумма t_i которых удовлетворяет формуле (2). Таким образом, множество D возможных решений разбивается на два подмножества: одно D₁ — в котором, одновременно не используются работы, не попавшие в набор из k работ; второе подмножество D₂ содержит все остальные варианты решений.

Очевидно, что полученный набор из k работ (табл. 2) является оптимальным решением в D₁ и локально-оптимальным решением в D, а с некоторой долей вероятности — оптимальным в D (в данном примере полученное локально-оптимальное решение из 2-й и 4-й работ с суммарной полезностью равной 14 по случайности является оптимальным, в чем можно убедиться, отыскав его на рис. 1).

Таблица 2 — Локально-оптимальное решение.

Шаг 2. Предположим, что в отброшенных работах есть комбинации, которые дают более оптимальное решение, чем решение в D₁. Рассмотрим подмножество решений D₂, применяя метод динамического программирования для всех комбинаций, где работы 1, 5 и 3 не исключаются одновременно (рис. 2). Для наглядности работы 1, 5 и 3 были перемещены в начало оси работ.

Рисунок 2. Улучшенный метод динамического программирования.

Оптимальные решения множества D₂ выделены жирными дугами на рис. 2; при этом полезность оптимальных решений равна 13, что меньше полезности оптимального решения множества D₁. Следовательно, набор из 2-й и 4-й работ является оптимальным решением задачи. При этом стоит отметить, что число допустимых решений множества D₂ на 2^k меньше, чем число решений в D. Таким образом, использование метода динамического программирования в комбинации с вышеизложенным эвристическим алгоритмом позволяет:

• · во-первых, без использования рутинных операций по перебору сразу получить как минимум локально-оптимальное решение задачи;
• · во-вторых, сократить количество переборов до 2ⁿ-2^k при поиске оптимального решения.

В заключении перечислим основные полученные результаты:

• 1. Показано применение метода динамического программирования Беллмана к решению задачи о выборе приоритетных работ.
• 2. Предложен новый метод решения задач дискретной оптимизации, заключающийся в улучшении метода динамического программирования за счет использования эвристических алгоритмов.
• 3. Дана оценка сокращения количества комбинаций для перебора при поиске точного решения за счет использования эвристических алгоритмов в методе динамического программирования.