close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
УДК 519.854.3
ЗАДАЧА ВЫБОРА ОПТИМАЛЬНОГО ПОРТФЕЛЯ ВЗАИМОЗАВИСИМЫХ
ПРОЕКТОВ С ОГРАНИЧЕНИЕМ ПО ВРЕМЕНИ
В.В. Зубарев
Рассматриваются задачи формирования и планирования процесса реализации портфеля взаимосвязанных проектов с одним типом ограничений. Приводятся соответствующие алгоритмы решения
Ключевые слова: дискретная оптимизация, управление портфелем проектов, управление проектами
Введение
Среди задач оптимизации в области управления проектами определенный интерес представляют задачи управления портфелем проектов′.
Портфелем проектов называется группа проектов,
объединенных с целью достижения максимальной
эффективности управления. Часто в портфель объединяются проекты, находящиеся в компетенции
одного центра ответственности и/или выполняющиеся на общем пуле ресурсов [2, с. 93]. В связи с
этим целесообразно выделить класс задач управления портфелем взаимозависимых проектов, что
предполагает наличие зависимостей между проектами портфеля. Под зависимостью будем понимать
требование начать выполнение определенного проекта после завершения другого. Такого типа зависимости назовем жесткими [1, с. 336], т.к. они
должны выполняться обязательно. На практике
возможны ситуации, когда эти зависимости носят
рекомендательный характер. Т.е. они могут нарушаться, но их нарушение ведет к определенным потерям. Например, выполнение проекта строительства здания целесообразно начинать после завершения проекта создания инфраструктуры. Выполнение этих проектов в другом порядке может потребовать дополнительные затраты. Без нарушения
общности можно считать, что любые зависимости
носят рекомендательный характер. В случае жестких зависимостей достаточно ввести бесконечные
(или достаточно большие) потери при их нарушении. В статье рассматривается задачи планирования процесса реализации и формирования портфеля
взаимосвязанных проектов. Также предлагаются
алгоритмы их решения.
Задача планирования процесса реализации
Пусть имеется портфель из N проектов,
рекомендательные зависимости между которыми
описаны сетевым графиком. Вершины сетевого
графика соответствуют проектам портфеля. Для
каждого проекта задана его базовая продолжительность ti . Дуги соответствуют рекомендательным
зависимостям между проектами. Для каждой дуги
задан параметр aij > 0 , который определяет увелиЗубарев Виктор Владиславович – ИПУ РАН, канд. техн.
наук, доцент, тел. (495) 334-79-00
чение продолжительности проекта j , если зависи-
мость (i, j ) нарушается, т.е. если проект j начат
до окончания проекта i . Требуется определить календарный план с минимальной общей продолжительностью.
Алгоритм 1.
Шаг 1. Присваиваем всем проектам на-
чальные индексы λi = ti , i = 1, N .
Общий шаг. Рассматриваем каждый проект
i . Обозначим через Qi – множество проектов,
предшествующих проекту i , т.е. в сетевом графике
существует дуга ( j, i ) для j ∈ Qi . Обозначим через
mi – число дуг, заходящих в вершину i (число
элементов множества Qi ). Рассмотрим все подмножества из mi элементов (их число равно 2 mi ).
Для каждого подмножества, содержащего вершины
Ri ⊂ Qi , вычисляем
τ i (Ri ) = ti + max λ j + ∑ a ji .
j ∈ Ri
j∉ Ri
Определяем новый индекс вершины
λi = min τ i (Ri ) .
i
Ri
Алгоритм заканчивается, когда все индексы установятся. Конечность алгоритма следует из
того, что последовательность индексов для каждого
i является возрастающей. С другой стороны, индексы λi ограничены сверху величиной
λi ≤ τ i + ∑ a ji ,
j∈Qi
а минимальное приращение – снизу величиной
⎛
⎞
min⎜ min λ j , min aij ⎟ .
,
j
i
j
⎝
⎠
Теорема 1. Установившиеся значения индексов λi определяют минимальные ранние сроки
завершения проектов.
Заметим, что величины индексов, получаемые на каждом шаге, являются нижними оценками
моментов окончания соответствующих проектов.
После того, как индексы установились, учтенные
зависимости можно считать обязательными (жесткими [1]). Также можно построить сетевой график
выполнения работ с учетом только жестких зависимостей. Очевидно, что этот сетевой график не
имеет контуров. Рассчитывая его известными алгоритмами (с учетом того, что зависимости, которые
не выполняются, приводят к увеличению продолжительностей проектов) мы получим те же самые
установившиеся индексы. Это доказывает теорему.
Задача формирования портфеля
Пусть имеется N проектов, для каждого из
которых заданы параметры ri > 0 (эффект) и ti > 0
(базовое время выполнения). Также задан набор рекомендательных зависимостей между проектами
{(i, j )} с параметрами aij > 0 . aij определяет увеличение продолжительности проекта j , если зави-
симость (i, j ) нарушается. Эти условия могут быть
описаны сетевым графиком (пример – рис. 1, обозначения – рис. 2).
( )
∀G ∗ ⊂ G : T G ∗ < T (G ) G ∗ ⊂ G \ pν
,
где
ν : λν = max λi .
i: p i ∈G
Определим операции с сетевым графиком
G , уменьшающие минимальное время завершения
всех проектов. Рассмотрим pν : λν = max λi . Очечто T (G ) = λν .
i : p i ∈G
видно,
Обозначим через Qν множество индексов вершин, предшествующих вершине
pν , т.е. ∀j ∈ Qν ∃ ( j ,ν ) ∈ G . Заметим, что исключение вершин из Qν не может уменьшить величину
λν , т.к. в противном случае алгоритм 1 определил
бы меньшее время завершения для pν , чем λν .
Следовательно, величину λν могло бы уменьшить
только уменьшение некоторых λ j , для j ∈ Qν . Далее последовательно применим аналогичные рассуждения ко всем p j : j ∈ Qν , а также к вершинам,
им предшествующим. Т.к. в исходном сетевом графике отсутствуют контуры, на определенном шаге
будут рассматриваться такие вершины pi (i ∈ I )
для которых Qi = Ø, т.о. исключение этих вершин
также не может уменьшить λν . Следовательно, утверждение 1 доказано.
Для решения задачи можно использовать
следующий алгоритм.
Алгоритм 2.
Шаг i :
Рис. 1
(a )
ri , t i
ij
rj , t j
( )
Рис. 2
j : p j ∈ G i . Если T G i ≤ T , то вершины, входящие
Требуется определить набор проектов с
максимальной суммой эффектов, при условии, что
общее время их выполнения не превышает T . Т.о.
задача имеет следующий вид:
N
∑ xi ∗ ri → max,
i =1
max xi ∗ τ i ≤ T ,
i =1, N
τ j = t j + max xi ∗ y ij ∗ τ i ,
i =1, N
N
(
)
t j = t j + ∑ 1 − xi ∗ y ij ∗ aij ,
i =1
Рассматривается сетевой график G i . С помощью алгоритма 1 определяются λ j , где
xi = {0; 1}, i = 1, N ,
yij = {0; 1}, i = 1, N , j = 1, N ,
ai ≥ 0, i = 1, N ,
ri > 0, t i > 0, i = 1, N .
Утверждение 1. Пусть условия задачи задаются сетевым графиком G , в котором отсутствуют контуры. Для всех его вершин pi ∈ G, i = 1, N
алгоритмом 1 определены минимальные сроки завершения λi . T (•) обозначает минимальное время
завершения всех проектов сетевого графика. Тогда
в G i , – решение задачи. Иначе: G i +1 = G i \ pν (i ) , где
ν (i ) : λν (i ) = max λ j .
j : p j ∈G i
Утверждение 2.
Алгоритм 2 дает оптимальное решение задачи в случае, если связи между проектами заданы
сетевым графиком без контуров.
Справедливость утверждения следует из
того, что алгоритм 2 представляет собой последовательное исключение из исходного сетевого графика вершин, не входящих в оптимальное решение
задачи. Отсутствие в оптимальном решении задачи
вершин pν (i ) следует из определения pν (i ) и утверждения 1.
Пример
Рассмотрим задачу, условие которой описывается сетевым графиком без контуров, изображенном на рис. 1 с ограничением T = 13 . В случае
отсутствия контуров в рассматриваемом графе число шагов алгоритма 1 можно сократить, если рассматривать вершины по порядку, предварительно
перенумеровав их таким образом, чтобы для любой
дуги (i, j ) выполнялось бы i < j . Соответствую-
щим образом перенумерованный граф изображен
на рис. 3.
Рис. 3
Результат вычислений минимальных ранних сроков завершения проектов по алгоритму 1
приводится в таблице.
Таким образом, минимальное время завершения всех проектов равно 21 (нарушаются две зависимости: (2,3) и (6,8) ), это превышает ограничение T = 13 . Далее по алгоритму 2 необходимо исключить те проекты, которые не входят в оптимальное решение задачи. Такими проектами являются проекты 6, 7 и 8 с минимальными временами
завершения 15, 21 и 14 соответственно.
На рис. 4 изображен план-график выполнения всех проектов с минимальными сроками завершения. Пунктиром отделены проекты, не входящие в оптимальное решение.
Рис. 4
Сумма эффектов оставшихся проектов равна 21. Это является максимумом целевой функции
при указанном ограничении.
Заключение
В работе рассмотрены задачи формирования и планирования процесса реализации портфеля
взаимосвязанных проектов. Описанные модели
предполагают наличие только одного типа ограничений. При решении практических задач приходится иметь дело с различными проектными ограничениями. В современной литературе часто выделяют
4 их типа (т.н. «пирамидальное ограничение») [2] –
качество, время, стоимость, стратегия. Задачи, учитывающие несколько типов ограничений, являются
более сложными и требуют других методов решения. Например, в [1] описывается способ решения
задачи построения календарного плана проекта с
учетом стоимости работ и времени их выполнения
на основе метода дихотомического программирования.
Литература
1. Баркалов С.А., Воропаев В.И., Секлетова
Г.И. и др. Под ред. В.Н. Буркова. Математические основы управления проектами: учеб. пособие. – М.: Высш.
шк., 2005. – 423 с.
2. Ципес Г.Л., Товб А.С. Проекты и управление проектами в современной компании: учеб. пособие
[Под общей редакцией А.С. Товба, Г.Л. Ципеса]. – М.:
ЗАО «Олимп-Бизнес», 2009. – 480 с.
Институт проблем управления им. В.А. Трапезникова РАН (г. Москва)
PROBLEM OF THE CHOICE OF THE OPTIMUM PORTFOLIO OF INTERDEPENDENT
PROJECTS WITH RESTRICTION ON TIME
V.V. Zubarev
Problems of formation and planning of process of realization of a portfolio of the interconnected projects with one
type of restrictions are considered. Corresponding algorithms of the decision are resulted
Key words: discrete optimization, management of a portfolio of projects, management of projects
Документ
Категория
Без категории
Просмотров
5
Размер файла
375 Кб
Теги
времени, оптимальное, проектов, выбор, ограничений, взаимозависимое, задачи, портфель
1/--страниц
Пожаловаться на содержимое документа