автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.10, диссертация на тему:Сетевые методы формирования оптимального портфеля проектов при наличии зависимостей рекомендательного типа

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ ИМ. В.А. ТРАПЕЗНИКОВА

УДК 338.24

На правах рукописи

НЕДОВЕСОВ Максим Васильевич

СЕТЕВЫЕ МЕТОДЫ ФОРМИРОВАНИЯ ОПТИМАЛЬНОГО ПОРТФЕЛЯ ПРОЕКТОВ ПРИ НАЛИЧИИ ЗАВИСИМОСТЕЙ РЕКОМЕНДАТЕЛЬНОГО ТИПА

Специальность: 05.13.10 -управление в социальных и экономических системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 Я НОЯ 2013

005540079

Москва 2013

005540079

Работа выполнена в Федеральном научном бюджетном учреждении Институте проблем управления им. В.А. Трапезникова Российской академии наук РАН (ИПУ РАН)

Научный руководитель: Буркова Ирина Владимировна, доктор технических наук, с.н.с. лаборатории №57 ИПУ РАН

Официальные оппоненты: Цвиркун Анатолий Данилович, доктор технических наук, профессор, зав. Лабораторией №33 ИПУ РАН

Колосова Елена Валерьевна,

кандидат технических наук, директор по развитию, ООО «К4»

Ведущая организация: Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)»

Защита состоится «_»_ 20_г. в_часов на заседании

Диссертационного Совета Д 002.226.02 Федерального научного бюджетного учреждения Института проблем управления им. В.А. Трапезникова Российской академии наук РАН: 117997, М., ул. Профсоюзная, 65. Телефон Совета (495)334-8901

С диссертацией можно ознакомиться в библиотеке ИПУ РАН

Автореферат разослан «_»_ 20_

Ученый секретарь Диссертационного Совета кандидат физико-математических наук

А.А. Галяев

Общая характеристика работы

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

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

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

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

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

- показать эффективность предложенных методов

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

Научная новизна и значимость результатов диссертационной работы

состоит в следующем:

- проведена адаптация модели проектного управления с рекомендательными зависимостями между работами для задачи формирования оптимального портфеля проектов

- описан метод решения ряда частных случаев задачи формирования оптимального портфеля взаимозависимых проектов с определенным видом сетевого графика, основанный на методе динамического программирования

- доказано утверждение об оптимальном решении задачи формирования оптимального портфеля взаимозависимых проектов с ограничениями по времени

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

- доказано утверждение о вогнутости целевой функции обобщенной двойственной задачи к задаче формирования оптимального плана реализации проекта

- разработан алгоритм решения задачи формирования оптимального портфеля проектов с рекомендательными зависимостями между проектами с использованием методов динамического и сетевого программирования

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

- проведены вычислительные эксперименты, подтверждающие эффективность предложенных методов и моделей

Достоверность и обоснованность научных результатов,

сформулированных в диссертации, определяется строгостью доказательств и

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

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

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

Апробация результатов исследования. Результаты диссертационного исследования докладывались на семинарах Института проблем управления им. В.А. Трапезникова РАН, также автор участвовал в следующих конференциях:

- 53-я научная конференция МФТИ «Современные проблемы фундаментальных и прикладных наук» (Москва, 2010)

- 7-я международная научно-практическая конференция «Управление проектами: состояние и перспективы» (Николаев, 2011)

- Международная научно-техническая конференция «Современные сложные системы управления X НТС8'2012» (Старый Оскол, 2012)

Публикации. По результатам работы имеется 4 публикации общим объемом 1.3 п.л. в журналах, входящих в список ВАК.

Структура и содержание диссертации. Работа состоит из введения, четырех глав, заключения и списка литературы из 81 наименования. Объем текста диссертации - 103 страницы, включая 19 иллюстраций и 19 таблиц.

Во введении дана общая характеристика работы, сформулирована ее цель, поставлены основные задачи исследования, обоснованы научная новизна и практическая значимость результатов.

Первая глава носит обзорный характер. В разделе 1.1 рассмотрена история развития методов управления проектами и обоснована актуальность разработки новых подходов к задаче формирования портфеля проектов. В разделе 1.2 описаны проблемы управления портфелем проектов, дан краткий обзор рассматриваемых задач. В разделе 1.3 описаны методы дискретной оптимизации, используемые в ходе диссертационного исследования. В разделе 1.4 приведена классификация существующих сетевых моделей, используемых для решения задач управления проектами на основании трех классификационных признаков: типов элементов сети, параметров элементов сети, а также уровня альтернативности сетевой модели.

Вторая глава посвящена разработке алгоритмов решения задач управления портфелем проектов. В разделе 2.1 описано применение сетевой модели с рекомендательными зависимостями к задачам управления портфелем проектов. В рамках данного подхода рассматривается набор Р = {р, | / = 1,«} возможных проектов, для каждого из которых заданы параметры:

1) эффект от реализации г: >0,1 = 1, п

2) базовые затраты с, > 0,; = 1 ,п

3) базовое время выполнения /, >0,/ = 1 ,п

Также задан набор л}2 рекомендательных зависимостей, каждая

из которых (¡,}) характеризуется параметрами > 0 и с/, > 0 - соответственно увеличением продолжительности и затрат проекта рр если зависимость (¡, ]) нарушается, то есть выполнение проекта j начинается до завершения проекта /. Как и в случае классической сетевой модели с рекомендательными зависимостями, эти условия могут быть описаны сетевым графиком, в котором проекты изображаются в виде вершин сети, а зависимости между ними - в виде дут. Без нарушения общности можно считать, что жесткие (обязательные) зависимости между проектами отсутствуют, так как иначе они сводятся к рекомендательным с бесконечно большими значениями щ и Ъу. Однако на практике не всегда можно вводить большое число такого рода зависимостей,

6

поскольку это ведет к существенному росту вычислительной сложности решаемых задач.

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

В качестве характера зависимостей рассматриваются рекомендательные зависимости, которые могут иметь один из четырех видов: «окончание-начало», «окончание-окончание», «начало-начало», «начало-окончание», а также совместные зависимости, подразумевающие изменение параметров объектов при условии их одновременного включения в решение задачи. В качестве типов целевой функции, зависимостей или ограничений могут выступать такие параметры, как эффект, затраты или длительность работ. В таблице 1 в соответствии с данной классификацией отражены рассмотренные в диссертации задачи. Для некоторых из них в работе дана содержательная постановка. Основная задача формирования оптимального портфеля взаимозависимых проектов формулируется следующим образом: Задача формирования оптимального портфеля. Пусть заданы оба параметра Ц-и Су. Среди таких подмножеств (портфелей) множества Р, для которых существуют календарные планы выполнения всех проектов с общим временем выполнения и затратами, не превышающими Г и С соответственно, требуется определить подмножество с максимальной суммой эффектов (г¡) входящих в него проектов.

Таблица 1

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

I. Объекты переменных

вершины v v v v

дуги v v v

II. Характер зависимостей

1. Рекомендательные

"окончание-начало" v v v v v v

"окончание-окончание"

начало-начало"

"начало-окончание"

2. Совместные зависимости v

III. Тип целевой функции

эффект v v v

стоимость v v v

длительность v

IV. Тип зависимостей

эффект v

стоимость v v v v

длительность v v v v

V. Тип ограничений

эффект v

стоимость v v

длительность v v v

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

В разделе 2.3 рассмотрены задача формирования оптимального портфеля взаимозависимых проектов и задача оптимизации такого портфеля по времени, которые возникают при разделении исходной задачи на подзадачи и часто встречается на практике вследствие разграничения процессов формирования портфеля проектов и его оперативного управления. На первом этапе опускаются ограничения на время и решается задача минимизации затрат при

заданном уровне эффекта. На втором этапе вводятся временные ограничения, рекомендательные зависимости по времени, и решается задача построения оптимального календарного плана реализации всех проектов сформированного на предыдущем этапе портфеля.

Для описания взаимосвязей между проектами вводится п х/i матрица взаимозависимости [dj. Значение элемента djj > 0 показывает дополнительный эффект, который получает проект i от успешной реализации проекта j. Если d,j = 0, то реализация проекта / не зависит от успешной реализации проекта j. Диагональные элементы dtj, i = j, определяют минимальный эффект, получаемый от реализации проекта / (независимо от выполнения остальных проектов). Таким образом, эффект от реализации проекта i равен , где Р -

множество всех реализованных проектов.

Задача формирования портфеля проектов представляется в следующем

Ее решение может быть получено при помощи метода сетевого программирования. Когда оптимальный портфель сформирован, вводятся рекомендательные зависимости и решается известная задача оптимального формирования календарного плана выполнения проекта с рекомендательными зависимостями. В разделе 2.2 приведен один из алгоритмов ее решения и доказано утверждение о конечном числе его шагов.

В разделе 2.4 рассмотрена задача формирования оптимального портфеля взаимозависимых проектов с ограничением по времени. Данная задача является разновидностью задачи формирования оптимального портфеля проектов с зависимостями рекомендательного характера в предположении, что ¥р, е Р, с,

виде:

-> min,

і=і

X, є

{О; і}, і = 1, п.

= 0, V(i,j) є Р, сij = 0.

Вводятся переменные:

1, зависимость (і, ^ не нарушается, О, - ішаче.

Таким образом, формально задача имеет вид:

[1, проект і выполняется, [О, - иначе;

У*, *г, —»шах,

шах х,*т,< Т,

І-1, N

т, =/. + пах *у„ *т„

* 1 1=1, V '

х. = {О; і}, і = ЇЛ,

yIJ={0■Лi = ÏNJ = ÏN.

г, >0,1, >0,І = ГЛ'.

(1)

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

В разделе 2.5 рассмотрена задача построения оптимального календарного плана реализации проекта с рекомендательными зависимостями между работами. Рассматривается проект, состоящий из множества работ IV = \н>,\1 = 1, и}, для каждой из которых заданы параметры: и с, - базовые время выполнения и затраты соответственно. Кроме этого задано множество зависимостей ..., и}2 между парами работ, с параметрами и с у. Для

формальной постановки водятся дополнительные переменные Ху.

1, если зависимость (і, $ не нарушается,

О - иначе.

Общая длительность работы Wj составляет

¡(мМ

затраты на ее

выполнение - с1 + . Условие задачи имеет вид:

С ('.УМ

E(1-Jc.yK -^min,

max т, < T,

г, = t, + max x, г.,

y j /:«.уМ " ' (2)

cO'.yM

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

На каждом шаге / работы алгоритма рассматривается вершина, соответствующая работе w,. Обозначим через I, — множество индексов "входящих" вершин, то есть h={j | 3(j, i) е А}, а через О, - множество индексов "исходящих": 0,={/ | 3(i, j) е А}. Определим множество обобщенных переменных G, = {(Ti, Cj, Fj)}, где Т, соответствует времени завершения работы w„ С; - сумме дополнительных затрат, связанных с выполнением уже рассмотренных работ (включая w,), a F, — минимально возможному времени завершения этих работ. Идея алгоритма заключается в последовательном вычислении обобщенных переменных (то есть G, =G,({c, lv' = l, / — l}), i > 1) с последующим решением задачи минимизации общих дополнительных затрат, связанных с вершинами с нулевой степенью исхода (такими w„ что |/,| = 0). Однако если число исходящих из i вершин больше 1, то вычисление переменных {Cj | (i, j) е А} осложнено возможностью неоднократного учета дополнительных затрат С,. Для исключения такой неопределенности для вершин с \Oi\ > 0 введем коэффициенты разделения s,pj е О,:

(3)

Таким образом, если у вершины i \1,\ = 0, множество обобщенных переменных состоит из одного набора: G, = {(!,, О, tj}\ если |/,| > 0 для каждого возможного

набора значений переменных хш ((к, i) е А, хи е {0, 1}) и каждого набора значений обобщенных переменных из множеств обобщенных переменных {Gk} к е /, во множество G, добавляются наборы обобщенных переменных (Т„ CJ, вычисленные по следующим правилам:

Т^тахГ^+Х'Л'^-К^

1 /е/,

С, С, + С,-(

Jel,

F, = max Г..

Мл '

Поскольку каждый набор значений обобщенных переменных соответствует некоторому плану реализации рассматриваемого проекта, из множества G/ можно исключить те наборы (Т„ С,), которые не соответствуют допустимому плану реализации (Т, > Т).

На последнем шаге (п+1), рассматриваются все вершины, у которых нет исходящих дуг, т.е. \0,\ = 0, и методом динамического программирования решается следующая задача оптимизации: ->min,

/:|О,|=0

max F, < Т, (4)

<:| 0,|=0 '

В работе показано, что для любых значений коэффициентов разделения, задаваемых условием (3), решение (г*($),С*(4 Ff*(s)), i: \0,\ = 0 задачи (4) является оценкой снизу для задачи (2). Обозначим Ф(ьj значение целевой функции задачи (4) в своем оптимальном решении, где s = {si} | (i,j) e А}. Для улучшения качества оценки сформулирована следующая задача:

<J>(s) -> max,

(5)

Jto,

Приведено доказательство утверждения о вогнутости целевой функции задачи (5).

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

Для краткого описания метода ветвей и границ, используемого для точного решения задачи (2), вводятся следующие обозначения: X = {х} -множество допустимых значений переменных Хф (i, j) е A, R = {X* \ X сХ} — такое множество его подмножеств, что = 0 и (J X' = X (на первом шаге

X'eil

R = {X}), d(X') - нижняя оценка задачи (2), полученная, как решение задачи (4) на подмножестве X\ На каждом шаге ветвления из R выбирается разветвляемое подмножество X'=argmin d(X'). Если оценка d(X') является достижимой, то

ЛГ'еК

есть найдется набор значений переменных х, порождающий по правилам оптимальное решение (4), то х является оптимальным решением (2), иначе подмножество X' разбивается на два подмножества X,1 и Хг'. Такое разделение можно произвести различными способами. В частности, в работе использован следующий эмпирический подход: выбирается (i, j) е А, для которой среди оптимального решения (4) найдутся такие обобщенные переменные С/ и Сь что их оптимальные значения выражаются, как С] =С,и С'к=СкДалее

полагается,

Х1'={х\хеХ',х = {хтр | (т, р) е А, хц =1}}, X2,= {x\xeX\x = {xmp\(»i,p)eA,x,,=()}}. Алгоритм ветвления продолжается до получения точного решения задачи (2).

В разделе 2.6 рассмотрена задача формирования оптимального портфеля проектов с зависимостями рекомендательного типа. Формальное условие задачи имеет вид

х1 -> шах,

(=1

щах х * т. < Т,

ы.ы

т, = I, + шах х, * у *г,,

(6)

¡=1 ^ м )

х, = {0; 1}, » = Гп, у9 = {0; 1}, / = =

> 0, с, > 0, /' = 1, л,

> 0, С(у >0,1 = 1, я, у = 1, п.

Для ее решения описан алгоритм, отчасти повторяющий действия алгоритма решения задачи построения оптимального плана реализации проекта. Здесь вводятся следующие множества обобщенных переменных Gi = /7?,, Т„ С/, Р,}, где

- Л, - сумма эффектов выбранных проектов, скорректированная с учетом коэффициентов разделения

- Г, — минимальное время завершения проекта /

- С, - ресурсы, требуемые для реализации выбранных проектов, скорректированные с учетом коэффициентов разделения

- - минимальное время завершения выбранных проектов. Определенный таким образом набор обобщенных переменных % е О, должен соответствовать параметрам проекта /?, е Р в некотором плане реализации определенного портфеля, составленного из рассматриваемых проектов. Следовательно, расчет множества обобщенных переменных должен производиться следующим образом:

для проектов, не имеющих входящих дуг, то есть р,: |/,| = 0, множество обобщенных переменных Gj состоит из двух наборов обобщенных переменных: в, = {(0, 0, 0, 0), (п, и, си т для остальных проектов во множество обобщенных переменных включаются следующие пары наборов обобщенных переменных:

14

V/, ={У, Ф, 1}I О, О ¿А}

л! ¿¿У Ьр,

_о'"' г, -таху- Г, +( (]->Л)(1-^(Г,))+/„

с, = IX С, - Xе, ^

: л Л 1 у«Л

Е, = тах .Р „ (

¡¡ч!, Р. = тах|

тах Е., Т. .

У: Уе/, ' ')

\У

После построения всех множеств обобщенных переменных С,: г' = 1,л, на шаге (п+1), рассматриваются все вершины, у которых нет исходящих дуг, то есть \0,\ = 0, и решается задача оптимизации: ^ Л, тах,

<:|О,|=0

тах Е < Т, /:|0,|-0

Т,С,<С,

Доказано утверждение о том, что для любых значений коэффициентов разделения, заданных выражением (3), решение задачи (7) является оценкой сверху для задачи (6).

Задача (7) принадлежит к классу линейных задач дискретного программирования с двумя ограничениями. Для решения может быть применен метод динамического программирования, заключающийся в определении оптимальной траектории в специальном семействе возможных траекторий. Однако, подход к построению такого рода траекторий, предложенный не учитывает возможность исключения траекторий, содержащих значения переменных, не являющиеся Парето-оптимальными. Таким образом, для решения задачи (7) возможно применение метода сетевого программирования. Структура сетевого представления для данной задачи изображена на рис. 1.

Слой 2

я\) .............................-................... (у (к!,,) (#!,) Слой 1

Рис. 1. — Структура сетевого представления

Здесь обозначает обобщенную переменную /, находящуюся на слое у сетевого представления.

В вершине , j > 1 решается задача

+ ** )тах>

та

С,+С2 <С,

где Т<Т, а С<С.

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

Обозначая теперь через Г(з) оптимальное решение Л* задачи (7). 5 = /я,у | (г,/) е А} задаются условием (3), задача улучшения верхних оценок формально можно записать следующим образом: Г(в) -» шш,

В работе доказано утверждение о выпуклости функции Г(я).

Итак, для получения точного решения задачи (6) возможно применение следующих действий:

1) улучшение оценки решением обобщенной двойственной задачи (8)

2) использование полученной оценки в методе ветвей и границ

В третьей главе отражены прикладные аспекты разработанных методов. Раздел 3.1 содержит описание примеров решения рассмотренных задач. В разделе 3.2 приведены результаты вычислительных экспериментов, подтверждающие эффективность разработанных методов. Для проведения вычислительных экспериментов все рассматриваемые алгоритмы были реализованы на языке С++, а вычисления производились на платформе с процессором Intel Core ¡5 М460 2.53Ghz. Ниже приведены результаты наиболее репрезентативных вычислительных экспериментов.

Эксперимент 1. Рассматривается решение задачи (1) алгоритмом, основанным на методе динамического программирования. В ходе вычислительного эксперимента рассматривались случайным образом сформированные цепочки проектов различной длины. Значения всех параметров были заданы целыми числами. Эффекты всех проектов принимались равными 1, а значения остальных параметров задавались случайным образом из следующих диапазонов: t, е [1, 10], с, е [1, 10], а, е [1, 2], b, е [1,2].

Поскольку, как указано в объем вычислений алгоритма решения зависит от размерности задачи, а также от величины ее ограничений, были рассмотрены 3 варианта ограничений: сильные (С=Т=1.25п, где п - количество проектов), средние {С=Т=2.5п) и слабые (С=Т=3.75п) ограничения.

Для каждого рассматриваемого числа проектов было сформировано 100 цепочек проектов, а время работы алгоритма усреднялось по всем задачам одной размерности. В таблице 2 приведено среднее время работы алгоритма на одной задаче, условия которой определяются описанными выше ограничениями, в миллисекундах

Таблица 2 - Результаты эксперимента 1

Количество проектов Сильн. огр. Средн. огр. Сл. огр.

10 2,32 31,03 82,58

20 77,6 560,8 1377,4

30 544,8 2982,8 7783,5

40 1505 11104 30172

50 4632 29042 87779

В работе приведено сравнение разработанного алгоритма с методом полного перебора на задачах относительно небольшой размерности. Для сравнения алгоритм полного перебора решает задачу размерности 10 в среднем за 62 миллисекунды.

Эксперимент 2. Рассматривается решение задачи (1) алгоритмом, основанным на методе ветвей и границ, с получением оценок методом сетевого программирования и решением задачи (3) методом динамического программирования.

В ходе данного эксперимента задавались случайным образом сформированные ациклические графы, а также соответствующие им целочисленные параметры. Каждый граф был сформирован таким образом, что количество ребер (рекомендательных зависимостей) составляло 40-60% от максимально возможного числа ребер в ациклическом графе. Параметры ц, Су принимали целочисленные значения из следующих интервалов: е [1, 20], /у е [1, 5], с у е [1, 5]. Поскольку время работы предлагаемого алгоритма, зависит от величины ограничения Т, были рассмотрены три типа ограничений: сильные Тешь„=0.1 {Тшп + Ттах), средние Тсреди = 0.25 (Ттш + Ттах) и слабые Тсл = 0.5 (Гт,„ + Ттах). где Ттт - время завершения проекта в случае, если ни одна зависимость не выполняется, а Ттах - если все зависимости выполняются. В 2 приведено среднее время работы алгоритма (в миллисекундах) на задачах с различным числом рекомендательных зависимостей по каждому из указанных типов

ограничений. Время усреднялось по результатам решения от 10 до 100 задач для каждого числа рекомендательных зависимостей.

Таблица 3 - Результаты эксперимента 2

Тсильн Т среди Тел

7 0,024 0,093 0,47

10 0,10 6,15 26.0

15 0,026 1,59 56,7

20 0,032 76,1 4403

25 0,032 142 2275

30 0,048 519 53927

35 0,089 2665 456133

40 0,12 1422 5592570

45 0,13 9257 8057067

50 0,18 14503 -

Для сравнения решение задачи размерности 30 с использованием полного перебора на тех же входных данных в среднем может быть получено за 700 секунд. На практике число рекомендательных зависимостей может быть относительно невелико, что позволит эффективно применять предложенных алгоритм к задачам большей размерности.

Эксперимент 3. Рассматривается решение задачи (5) алгоритмом, основанным на методе ветвей и границ, с получением оценок методом сетевого программирования и решением задачи (6) методом сетевого программирования.

В ходе данного эксперимента в качестве условий задачи (5) случайным образом формировались ациклические графы, а также соответствующие им целочисленные параметры. Для каждого рассматриваемого числа вершин в графе рассматривалось три варианта числа рекомендательных зависимостей: 10%, 20% и 30% от максимально возможного числа связей в ациклическом графе. Целочисленные параметры 4 с„ Су задавались случайными значениями из следующих интервалов: и е [1, 15], с, е [1, 15], ц е [1, 5], с,у е [1, 5]. Как показывают результаты предыдущего вычислительного эксперимента, время работы рассматриваемого алгоритма в существенной степени зависит от величины ограничений. Для целей данного эксперимента

были выбраны достаточно нежесткие ограничения, а именно Т = 0.75 Т0, С = 0.75 Со, где Т0 и Со - время и затраты на выполнение всех проектов рассматриваемого множества при условии, что все рекомендательные зависимости выполняются. В таблице 4 приведены результаты вычислительных экспериментов — среднее время работы рассматриваемого алгоритма в миллисекундах по результатам решения десяти случайных задач.

Таблица 4 - Результаты эксперимента 3

10% 20% 30%

5 6,53 1,94 2,24

10 6,80 49,5 979,72

15 135 25443 906088

20 5169 1068415 -

25 52960 - -

30 2063602 - -

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

Четвертая глава посвящена практическим приложениям разработанных методов в сфере планирования социально-экономического развития муниципальных образований. В разделе 4.1 приведен анализ аспектов стратегического планирования социально-экономического развития муниципальных образований. Описаны существующие подходы к разработке целостных систем управления развитием территории. В разделе 4.2 приведена схема оценки потенциала развития экономического субъекта посредством анализа альтернативных стратегических инициатив. Дается иллюстрация

применения разработанных моделей и методов на содержательном примере.

20

В заключении диссертации приведены основные результаты и выводы работы.

На защиту выносятся следующие результаты, полученные в диссертационной работе при исследовании задач управление портфелем проектов:

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

2. Постановка и классификация задач формирования оптимального портфеля с рекомендательными зависимостями между проектами

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

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

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

Основные результаты диссертации опубликованы в следующих работах: Публикации в изданиях, рекомендованных ВАК РФ

[1] Недовесов М.В. Задача выбора оптимального портфеля взаимозависимых проектов с ограничением по времени // Системы управления и информационные технологии, 2011, №3.2(45). - Воронеж: Научная книга, 2011, с. 301-303.

[2] Бабкин В.Ф., Колпачев В.Н., Баринов В.Н., Недовесов М.В. Модель формирования оптимального портфеля взаимозависимых строительных проектов с ограничением по времени // Научный вестник ВГАСУ. Строительство и архитектура, 2012, №2. - Воронеж: ВГАСУ, 2012, с. 85-89.

[3] Гуреева Е.В., Недовесов М.В. Управление проектами. Стратегическое планирование // Системы управления и информационные технологии, 2012, №2(48). - Воронеж: Научная книга, 2012, с. 95-98.

[4] Недовесов М.В., Руденко З.Г. Формирование оптимального портфеля взаимозависимых проектов и его оптимизация по времени // Проблемы управления, 2012 №4. - Москва, 2012, с.26-31. Статьи и материалы конференций

- Недовесов М.В., Руденко З.Г. Выбор оптимального портфеля взаимозависимых проектов и его оптимизация по времени // Труды 53-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук». Часть I. Радиотехника и кибернетика. Том 2. — М.: МФТИ, 2010, с. 42-43.

- Недовесов М.В. Сетевые модели в задачах управления портфелем взаимозависимых проектов // Управление проектами: состояние и перспективы: Материалы 7-й Международной научно-практической конференции. — Николаев: НУК, 2011, с. 224-226.

- Недовесов М.В. Задача формирования оптимального портфеля проектов с зависимостями рекомендательного типа // Современные сложные системы управления X НТС8'2012: материалы Международной научно-технической конференции. — Старый Оскол: ТНТ, 2012

Личный вклад автора в совместные работы. В работе [2] — формальная постановка и метод решения задачи формирования оптимального портфеля взаимозависимых проектов с ограничением по времени. В работе [3] -обоснование применимости методов управления портфелем проектов к процессу стратегического управления организацией. Формальная постановка и метод решения задачи формирования оптимального портфеля проектов с зависимостями рекомендательного типа. В работе [4] — обзор моделей, использующихся в процессе управления портфелем проектов. Формальная постановка задачи оптимизации портфеля проектов по времени. Доказательство о конечном числе шагов алгоритма решения, и оценка его вычислительной сложности.

Подписано в печать 17.09.2013 Заказ № 11373 Тираж 100 экз. Объем 1 п.л. Отпечатано: ООО «ВП24» г. Москва, ул. Трубная, д. 21 Телефон 651-64-48 www.vp24.ru

УЧРЕЖДЕНИЕ РОССИЙСКОЙ АКАДЕМИИ НАУК ИНСТИТУТ ПРОБЛЕМ УПРАВЛЕНИЯ ИМ. В.А. ТРАПЕЗНИКОВА

338.24

На правах рукописи

СЕТЕВЫЕ МЕТОДЫ ФОРМИРОВАНИЯ ОПТИМАЛЬНОГО ПОРТФЕЛЯ ПРОЕКТОВ ПРИ НАЛИЧИИ ЗАВИСИМОСТЕЙ РЕКОМЕНДАТЕЛЬНОГО ТИПА

Специальность: 05.13.10 - управление в социальных и экономических системах

Диссертация

на соискание ученой степени кандидата технических наук

Научный руководитель -д.т.н. Буркова И.В.

Москва 2013

Оглавление

Введение.......................................................................................................................3

Глава 1. Управление проектами и портфелями проектов.......................................7

1.1 Обзор истории развития управления проектами............................................7

1.2 Проблемы управления портфелями проектов..............................................12

1.3 Обзор используемых методов дискретной оптимизации............................18

1.4 Обзор сетевых моделей, используемых в задачах управления проектами 23 Глава 2 Сетевая модель управления проектами с зависимостями рекомендательного типа...........................................................................................29

2.1 Описание модели.............................................................................................29

2.2 Метод динамического программирования для частных случаев задачи формирования оптимального портфеля взаимозависимых проектов..............33

2.3 Формирование оптимального портфеля взаимозависимых проектов и его оптимизация по времени.......................................................................................42

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

2.5 Метод решения задачи определения оптимального календарного плана реализации проекта с рекомендательными зависимостями между работами 47

2.6 Метод решения задачи формирования оптимального портфеля взаимозависимых проектов с зависимостями рекомендательного типа.........53

Глава 3. Примеры. Вычислительные эксперименты.............................................60

3.1 Примеры решения задач.................................................................................60

3.2 Результаты вычислительных экспериментов...............................................74

Глава 4. Применение разработанных подходов к задачам разработки стратегий социально-экономического развития муниципальных образований..................83

4.1 Анализ аспектов стратегического планирования социально экономического развития муниципальных образований..................................83

4.2 Оценка потенциала развития..........................................................................87

Заключение................................................................................................................95

Список использованных источников......................................................................97

Введение

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

Современные исследования показывают, что сегодня для достижения конкурентных преимуществ уже недостаточно успешного выполнения отдельно взятых проектов [34, 20]. В настоящее время экономическая ситуация такова, что необходимо успешно выполнять комплексы проектов. Тем не менее, сегодня состояние этой дисциплины таково, что большинство подходов и методов описывают только верхний уровень предметной области, ограничиваясь описанием терминов, основных процессов и компетенций участников. На сегодняшний день методы управления портфелем проектов требуют дальнейшей проработки экономико-математической составляющей. Тем не менее, существует широкий ряд работ в этом направлении. Необходимо отметить достаточно большой вклад следующих исследователей: M.W. Dickinson, A.C. Thornton, S. Graves, D. Verma, K.K. Sinha, Баркалова С.A., Буркова B.H., Бурковой И.В., ВоропаеваВ.И., Зубарева В.В., E.H. Шомовой [30, 31,32,33] и др.

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

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

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

- показать эффективность предложенных методов

Научная новизна и значимость результатов диссертационной работы состоит в следующем:

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

- описан метод решения ряда частных случаев задачи формирования оптимального портфеля взаимозависимых проектов с определенным видом сетевого графика, основанный на методе динамического программирования

- доказано утверждение об оптимальном решении задачи формирования оптимального портфеля взаимозависимых проектов с ограничениями по времени

- описан метод решения широкого класса задач управления проектами и портфелями проектов на основе методов динамического, дихотомического и сетевого программирования.

- указанный метод применен для решения следующих задач:

- формирование оптимального плана реализации проекта

- формирование оптимального портфеля взаимозависимых проектов

- доказано утверждение о вогнутости целевой функции обобщенной двойственной задачи к задаче формирования оптимального плана реализации проекта

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

- проведены вычислительные эксперименты, подтверждающие эффективность предложенных методов.

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

Практическая значимость результатов работы состоит в возможности их непосредственного применения для решения задач формирования оптимального портфеля взаимозависимых проектов и построения его плана реализации. Результаты исследования могут быть использованы для оценки потенциала посредством анализа множества альтернативных проектов. Помимо этого разработанные методы могут быть использованы при создании комплекса программных средств по управлению портфелями проектов, практическая значимость которого рассматривается в разделе 2.2 диссертации.

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

Апробация результатов исследования. Результаты диссертационного исследования докладывались на семинарах Института проблем управления им. В.А. Трапезникова РАН, также автор участвовал в следующих конференциях:

53-я научная конференция МФТИ «Современные проблемы фундаментальных и прикладных наук» (Москва, 2010)

7-я международная научно-практическая конференция «Управление проектами: состояние и перспективы» (Николаев, 2011)

Международная научно-техническая конференция «Современные сложные системы управления X НТС8'2012» (Старый Оскол, 2012)

Также основные положения диссертации отражены в четырех статьях общим объемом 21 п.л. в журналах, входящих в перечень ВАК.

В 2011 году автор в составе рабочей группы принимал участие в разработке стратегий социально-экономического развития муниципальных образований, где для оценки потенциала социально-экономического развития применялись методы портфельного управления.

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

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

Во второй главе описана сетевая модель проектного / портфельного управления с рекомендательными зависимостями между работами / проектами, сформулированы ее достоинства и недостатки. Также во второй главе дается описание разработанных автором методов решения прикладных задач на основе данной модели.

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

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

В заключении перечисляются основные результаты работы.

Глава 1. Управление проектами и портфелями проектов

1.1 Обзор истории развития управления проектами

Первые исследования в этом направлении связывают с выполнением ряда крупных технологических проектов в США [1]. Начало работ по обобщению и систематизации знаний в области управления относят к первой половине XX века. Одной из первых работ в этом направлении является книга Г. Файоля «Общее и промышленное управление», в которой автор представил 14 принципов - правил построения успешной системы управления. Продолжая развивать идеи Г. Файоля, JI. Гьюлик и JI. Урвик в 1937 г. впервые предложили матричную организацию для организации проектной деятельности [2]. Впервые комплексное применение этой модели было осуществлено в 50х гг. в ряде военных подразделений в США. Результатом применения этой технологии стало существенное повышение показателей качества. Вследствие этого сложилась практика управления проектами, заключающаяся в выделении специальной роли руководителя проекта, обязанностями которого стало детальное планирование работ в соответствии с заранее определенными требованиями [3]. Данная практика дала основу для будущей разработки технических методов и средств управления проектами.

В 1957 г. в ходе совместной деятельности по разработке методов

управления проектами компаний Du Pont de Nemours Со и Remington, а также

исследовательского центра UNIVAC был разработан и реализован

программными средствами метод критического пути (СРМ), - эффективного

инструмента планирования расписания и управления сроками проекта [4]. С тех

пор данный метод не претерпел принципиальных изменений, и сегодня

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

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

сетевом графике таких путей, на которых выполнение всех операций возможно

лишь в наиболее поздний допустимый срок. Вначале этот метод использовали

7

для контроля межремонтного срока службы оборудования, где он позволил сократить продолжительность профилактического ремонта на 40% [5]. Преимущества метода критического пути позволили продолжить исследования в этом направлении и в январе 1958 г. отделом специальных проектов управления вооружением ВМС США была разработана система сетевого планирования PERT [7]. Данная система представляет собой способ анализа календарного плана выполнения проекта или программы и сводится к выполнению следующих действий: определение ключевых задач и вех проекта или программы, определение последовательности выполнения задач, построение сетевой диаграммы, оценка времени выполнения каждой задачи и определение критического пути [6]. В 1959 г. П. Геддис в своей статье обобщил концептуальные основы управления проектами, подчеркнул значимость роли проектного менеджера, а также обозначил перспективы развития дисциплины в целом [8].

В 1960-е годы основные исследования в области управления проектами были направлены на расширение границ применимости средств PERT и СРМ. Были предложены методы планирования и распределения ресурсов RPSM и RAMPS, подход PERT/COST, основанный на идее измерения освоенного объема [9]. Компанией IBM был разработан комплекс средств управления проектами PMS [1]. Впервые был применен метод графической оценки и анализа - стохастический метод сетевого планирования, основанный на использовании сетей GERT [10]. В это же время появляются работы по сетевым методам в СССР. Их авторами стали Г.С. Поспелов, А.И. Тейман [21], Ю.А. Авдеев [22].

В 1970-е методы сетевого планирования получили законодательную

поддержку в США [1], что привлекло существенный интерес со стороны

разработчиков программных средств. Также в этот период активно развивались

междисциплинарные направления, связанные с экономическими,

экологическими и общественными факторами [1]. Появились новые области

знаний: управление конфликтами [12], организационные структуры управления

8

проектами [11]. В 1970e годы также был разработан новый, класс сетевых моделей, который позволил существенно расширить границы применимости сетевых методов - обобщенные сетевые модели [23, 24]. Согласно [25] принципиальными отличиями такого рода моделей от уже существующих стали отказ от требований ацикличности сети, расширение интерпретации событий и введение ограничений сроков на работы или их части. В этот же период был разработан ряд стохастических моделей, позволяющих учесть вероятностные факторы моделируемой среды [1, 26, 27]. Научной школой В.Н. Буркова было разработано такое направление, как теория активных систем [28], также

В 1980-х проводились работы по интеграции дисциплин, связанных с управлением проектами. Появились такие дисциплины, как управление изменениями [14], управление рисками [13]. Также был проведен ряд работ по разработке методов оценки эффективности управления проектами [15]. Получают распространение альтернативные сетевые модели [18]. Вследствие развития новых информационных технологий расширились возможности эффективного использования таких методов и средств управления проектами, как планирование, составление графиков работ, контроль и анализ времени, стоимости и ресурсов. В 1987 г. был впервые опубликован свод знаний по управлению проектами - коллективная работа института PMI, в которой, как считается, определены место, роль и структура методов и средств управления проектами [1, с. 96].

В 1990-х появилась концепция управления хозяйственной деятельностью

посредством проектов, вследствие чего появилось понятие проектно-

ориентированных компаний [16]. Начинают изучаться вопросы, связанные со

стратегическим управлением такого рода компаний. В 1991 г. в Германии

национальной ассоциацией по управлению проектами было опубликовано

практическое руководство, в котором были отражены национальные и мировые

достижения в этой области [1, 17]. Более глубоко рассматриваются

стохастические модели [19]. Также в этот период продолжилось развитие

9

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

К началу XXI в. широкое распространение получила концепция, которая заключается в идее создания организаций, деятельность которых может быть представлена в виде совокупности различных проектов, обеспечивающих достижения стратегических целей [20]. Актуальность исследований данного направления вызвана, тем, что в современных условиях для получения конкурентных преимуществ становится недостаточно обеспечить качество выполнения отдельных проектов. В первую очередь это связано с тем, что многим компаниям удалось существенно повысить уровень зрелости процессов в данной области, и для осуществления успешной конкуренции им необходимо решать более сложные задачи, в том числе анализ соответствия проектов стратегическим целям, определение ключевых показателей контроля проектов, анализ структуры финансирования проектов, формирование сбалансированных портфелей и максимизация полезности портфеля проектов [20, 29]. Современное состояние управления портфелем проектами таково, что большинство подходов и методов описывают только верхний уровень предметной области, ограничиваясь описанием терминов, основных процессов и компетенций участников. На сегодняшний день методы управления портфелем проектов требуют дальнейшей проработки экономико-математической составляющей. Тем не менее, существует широкий ряд работ, посвященных исследованиям данной области. Необходимо отметить существенный вклад следующих исследователей: M.W. Dickinson, A.C. Thornton, S. Graves, D. Verma, K.K. Sinha, Баркалова C.A., Буркова B.H., Бурковой И.В., ВоропаеваВ.И., Зубарева В.В., E.H. Шомовой [30, 31, 32, 33] и др.

Сегодня управление портфелем проектов уже стало самостоятельной

дисциплиной в рамках управления проектами. Процесс управления портфелем

можно разделить на четыре этапа [20, 29]: определение перечня проектов, их

10

анализ, оптимизация портфеля и его реализаци