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

Институт проблем управления РАН

Го од

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

) Г| !! Г ' 'ЛТ

Квон Олег Федорович

МОДЕЛИ И МЕТОДЫ МУЛЬТИПРОЕКТНОГО УПРАВЛЕНИЯ

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

системах"

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

Москва, 1997 г.

Работа выполнена в Институте проблем управяешя РАН.

Научный руководитель:

- доктор технических наук, профессор Бурков В.Н. Официальные оппоненты:

- доктор технических наук, профессор Цвиркун А.Д.

- кандидат технических наук Сочнев C.B.

Ведущая организация: Московский физико-технический институт

Защита состоится «__»_ 1997 г. в_часов на

заседании Совета Д. 002.68.03 Института проблем управления по адресу: •117806, Москва, ул. Профсоюзная, д.65.

С диссертацией можно ознакомиться в библиотеке Института проблем управления.

Автореферат разостлан «_»_^ 1997 г.

Ученый секретарь Специализированного

совета, к.rn.it Власов СА.

Развитее общества, экономики, предприятия, да и жизни отдельного человека можно представить себе как совокупность дискретных процессов с заданными конечными целями, протекающими в условиях ограниченного времени и ограниченных ресурсов. Человеку удобно делить процесс своей деятельности на локальные процессы. Проектами называются процессы изменений, то есть неповторяющиеся процессы, требующие для своей реализации специальных методов управления. Так Вы каждое утро делаете зарядку (должны делать). Это отработанный процесс, не требующий от Вас специальных усилий по организации. Это не проект. А вот освоение нового курса упражнений или новой системы занятий - это уйсе можно отнести к проектам. Ежедневный процесс выпуска продукции на предприятии тоже не называют проектом. А вот освоение новой продукции или технологии - проект. Конечно, не всегда различие столь очевидно. Так, например, строительство дома - это проект, а выпуск на комбинате типовых блочных домиков с установкой на месте не имеет смысла называть проектом.

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

В наши дни в России управление проектами переживает второе рождение. Создана Российская ассоциация управления проектами (СОВНЕТ), являющаяся членом Международной ассоциации управления

проектами (ИНТЕРНЕТ). Ведется работа по подготовке менеджеров по управлению проектами, готовится к изданию отечественное руководство по управлению проектами.

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

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

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

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

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

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

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

Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались на семинарах Института проблем управления; международном симпозиуме СОВНЕТ'97 «Управление проектами в переходной экономике: инвестиции, инновации, менеджмент», Москва - 1997; международной научно-практической конференции «Управление большими системами», Москва - 1997; четвертой международной конференции «Проблемы управлешм в чрезвычайных ситуациях», Москва -1997.

Публикации. По теме диссертационной работы автором опубликовано 4 печатных работы общим объемом 3 печатных листа.

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

Краткое содержание работы

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

Рассмотрим мультнпроект из п независимых проектов. Каждый проект в агрегированном виде описывается как операция двумя характеристиками - объем проекта Wj и зависимость скорости реализации проекта w,(t) = {¡(u£(t)) от количества ресурсов Uj(t) в момент t. Объем проекта, скорость и момент его завершения Т; связаны соотношением:

(1.)

о

Пусть задана величина ресурсов N(t) на реализацию мультипроскта. Задача заключается в распределении этих ресурсов по отдельным операциям так, чтобы мультнпроект был реализован за минимальное время T=maxTf. В случае, если N(t)=N в любой момент времени

(равномерное поступление ресурсов во времени) и fi(ui) - вогнутые функции Ui, задача распределения ресурсов детально исследована Бурковым В.Н. Показано, что оптимальное распределение ресурса имеет следующие свойства:

а) каждая операция выполняется при постоянном уровне ресурсов Ui(t) = 1ц, i = 1, н, te [О, Т], а значит с постоянной скоростью;

б) все операции заканчиваются одновременно.

Если Т - момент завершения всех операций, то Wj = W/Г постоянна скорость i-ой операции. Если обозначить через (pi(Wj) - функцию, обратную функции то ц = cp,(W/r) определяет количество ресурсов, требуемое для завершения операции i за время Т. Минимальное время Т определяется теперь из уравнения

Рассмотрим случай, когда N(t) - кусочно-постоянная функция времени, N(t) Nb t е [Ты, Tk), k = Ср, Т0 = 0. Обозначим wiq - скорость

операции > в интервале ^ И«, = ф^ууц). В работе показано, что в оптимальном решении имеет место

Ьц = Уч-Ьц, 1 = 1, п» я = 1, р, ( 2 )

где р - интервал, в котором завершается мультипроект, уч > 0 - скалярная величина. Таким образом вектор {Ьц} является в определенном смысле инвариантным во времени (его направление не меняется от интервала к интервалу, а меняется только длина).

Полученное свойство оптимального решения позволяет свести задачу распределения ресурсов к решению системы (п + р) нелинейных уравнений с (п + р) неизвестными ! = 1, п, {уч}, q = 2, р и Т. В работе описаны алгоритмы решения задачи для случая степенных и линейных зависимостей скоростей операций от количества ресурсов (уровня финансирования).

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

Опишем алгоритм выравнивания графика поступления ресурсов в к периодах при заданных величинах |ТЧ |, я = 1, к.

I шаг. Находим период р, начиная с которого количество ресурса уменьшается от периода к периоду до некоторого периода С, то есть

Определяем

= -г

• £ТЧ ч-р,

и полагаем Ы<1 = для всех я = р, ^. Все периоды с равными И,

объединяем в один. Для нового графика процедуру повторяем, если найдется участок с уменьшающимися уровнями

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

Пусть - произвольные, ограниченные, непрерывные справа

функции, такие что £<0) = 0. Определим множество У - пар (и, \у) -следующим образом:

У, «{(и,, *,)*<>: (3)

Заметим, что если £(и0 - вогнутая функция, то У; - выпуклое множество. В общем случае множество У^ не является выпуклым. Построим выпуклую ободочку этого множества, то есть выпуклое множество У1 такое, что любая его точка представима в виде выпуклой линейной комбинации точек множества У(. Граница этого множества, очевидно, является

вогнутой функцией. Рассмотрим задачу минимизации продолжительности мультипроекга, в котором скорости проектов определяются зависимостями Ц(ч,)}. Поскольку это вогнутые функции, то применяя методы, описанные в разделах 1 и 2, можно определить оптимальное распределение ресурсов {и/1} и минимальную продолжительность Тт мультипроекга.

Теорема 1.1. Минимальная продолжительность мультипроекта равна

Тт-

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

С-¿с,!,. (4)

1«!

Рассмотрим задачу распределения ресурсов по проектам таким образом, чтобы минимизировать (4), то есть упущенную выгоду.

Пусть мультипроект состоит из п проектов, объемы которых а скорости линейно зависят от количества ресурсов:

Гп,.«.*^

и, > а,

В работе предложено эвристическое правило, согласно которому приоритет отдается проектам, имеющим ббльшее отношение ф = с4ЛЛг|, Показано, что это правило дает оптимальное решение для случая двух проектов, и, как показали многочисленные примеры, во многих случаях дает близкие к оптимальным решения. Заметим, что если уровень финансирования постоянен, - N(1) = N и ¡^ = Н, I =1, п, то существует оптимальное распределение финансов, при котором каждый проект выполняется при максимальном уровне финансирования за время Т) = В этом случае получаем известную в теории расписания задачу определения оптимальной очередности операций на одном рабочем месте.

Решающее правило в этом случае естественно совпадает с известным решающим правилом - упорядочение по убыванию отношения Ы/т£.

Во второй главе рассматриваются методы построения агрегированных описаний проектов.

Под агрегированием понимается представление проекта в укрупненном виде с меньшим числом операций. Такое представление очень удобно при управлении большими проектами, когда сама система управления является многоуровневой (например, генеральный директор, директор отделения, руководитель мультипроекта, руководитель проекта). Ясно, что на каждом уровне управления нужна информация о проектах, представленная в виде, удобном для принятия решений. Чем выше уровень •управления, тем более укрупненной должна быть эта информация. Методы агрегирования проектов, ориентированные на такого рода иерархические системы управления рассматриваются в работах Воропаева В. и Любкина С., где предлагаются так называемые обобщенные сетевые модели (ОСМ), обладающие большими возможностями для описания проектов, чем обычные сетевые модели. Для рассматриваемых в работе задач финансирования мультипроекта удобным является представление каждого проекта в виде отдельной операции. Такой подход к агрегированию проекта был предложен Бурковым В. и Чеботаревым О. Дадим основные определения.

Определенно 2.1. Агрегированием проекта называется его описание в виде отдельной операции объема У/э и зависимостью Рэ(и(0) скорости агрегированной операции от количества ресурсов.

Пусть и Р,(и(1)) определены. Тогда для заданной функции N(0 поступления ресурсов на проект можно определить минимальное время его завершения Тю^М]- Для той же функции N0) можно определить

минимальное время завершения агрегированной операции T,[N(t)]. Разность

e[N(t)]= |TA[N(t)]-T,tN(t)]| опрелеляет ошибку агрегирования. Очевидно, что для разных зависимостей N(t) в общем случае будут поучаться разные оценки.

Обозначим через М семейство возможных зависимостей N(t). В этом случае ошибкой агрегирования называется

в = max efNftYj.

N(DeM 1 v

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

Определение 2.2, Агрегирование называется идеальным, если ошибка агрегирования равна нулю.

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

fi(ui) = aSl, i = !Tn. Действительно, в этом случае Бурковым В. доказано, что существует эквивалентный объем комплекса W3 и зависимость

F3(N) = Na,

такие, что для любого уровня ресурсов N(t) имеет место

т •

fF[N(t)]dt = W5. в

При этом, существует оптимальное распределение ресурсов {uj°(t)}, такое

что

а время выполнения комплекса равно Т„ш,.

Пусть N(1) = N при любом В этом случае распределение ресурсов {«¡°(0} имеет следующие интересные свойства:

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

2. Ресурсы {и*} образуют поток по сетевому графику.

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

Опишем алгоритм определения эквивалентного объема комплекса. Сначала определяем зависимость затрат Бу = от времени выполнения операции:

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

были минимальными.

Как известно, необходимым и достаточным для оптимальности является выполнение для любого события 1 сети (за исключением начального и конечного) следующих условий:

где Ъ® - моменты начала и окончания ¡-ой операции.

(5)

Однако, поскольку

—-----

1 ату а

то условно (6) эквивалентно условию потоков ости ресурсов в каждом собь<тии. А минимум стоимости при условии, что ресурсы образуют поток в сети, эквивалентен минимуму ресурсов N.

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

шаге происходит уменьшение величины (5). Когда в сети получено

- - »

решение, для которого (6)- выполняется во всех вершинах, величина стоимости (5) минимальна и, следовательно, минимальным является и уровень ресурсов N„031. Эквивалентный объем комплекса определяется выражением

= ТЫ* = Б^пш/Г'Л Опишем еще один метод оценки эквивалентного объема комплекса. В основе его лежит следующая теорема:

Теорема 2.1. Эквивалентный объем комплекса является выпуклой однородной функцией объемов операций V.

Доказательство. Бурковым В. доказано, что при N(1) = N Тщщ(^) является выпуклой функцией своих аргументов. Так как

= , то из условия выпуклости Т^) получаем для

W = aW1+(l-a)W^ 0£а<1,

+ (1 -а)\7г) £ ) + (1 - .

Дня /¡ н'..'п:пелылва однородности увеличим объем всех операций в

ц к * и одновременно увеличим продолжительности всех операций в ч раз. При 31 ом количество ресурсов, выполняющих каждую операцию, не изменится, а минимальная продолжительность комплекса увеличится в я раз. Так как V/, = ТтЬ •№ , то эквивалентный объем также увеличится в ц раз.

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

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

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

1-го этапа лр^-ом уровне финансирования, 1 = 1, п, 3 = 1, т.

/

Для агрегированного описания проекта необходимо определить агрегированную скорость проекта при каждом уровне финансирования, 3 = 1, т, и объем каждого этапа, 1 = 1, п. Определение объема каждого этапа необходимо в данном случае, так как изменение уровней финансирования допускается только при завершении этапа (каждый этап выполняется при постоянном уровне финансирования). Поэтому нам необходимо знать, какой объем выполнен при завершении каждого этапа. Обозначим щ - 1, если ¡-ый этап выполняется при ,)-ом уровне финансирования, щ ~ 0 в противиом случае. Тогда время завершения проекта составит

Т(х) = не-

определим время завершения агрегированной операции:

п

Обозначим 1 /у? ■ - Т = £ ■ Тогда (2.3.2) можно записать в виде 1 1=1

i.j

Ошибка агрегирования равна

Ф0 =

¡о'

Все возможные варианты реализации проекта определяются условием

М = |хч: Еху =1' "Ь

таким образом

е(х) = шах

хеМ

и

Поставим задачу оптимального агрегирования: определить У/, г О, 1 = 1, п такие, что е принимает максимальное значение. В работе показано, что эту задачу можно свести к задаче линейного программирования.

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

и 1 ;

Поставим задачу минимизации оценочной функции (7). Эта задача, как легко видеть, распадается на п независимых подзадач для каждого этапа: определить > 0, такое что

шах

шш.

1

Решение этой задачи сводится к решению уравнения с одним неизвестным

т$-е, . Тз+е, юах—— = гит —--

. J Т, I Т,

/

Рассмотрим линейную зависимость скоростей операций от количества ресурсов

= = ^.

Для этого случая также возможно идеальное агрегирование. При этом для »

агрегированной операции имеет место

¡=1

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

Ги15 вслии^а,,

если И| ^ а^ »

В этом случае идеальное агрегирование возможно не всегда.

Обозначим II - - минимальную продолжительность 1-ой

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

событий О, непосредственно следующих за ¡-ым, то поздний ыоиент «свершения ьго события определяется по формуле

, »Г-«§(»;-ч)-

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

= - т

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

Рассмотрим один пример идеального агрегирования для линейного случая. Пусть поступление финансовых ресурсов на мультипроект происходит равномерно, то есть N(0 = N. а потребность в ресурсах для каждого проекта удовлетворяет условию

где 8(Т) = 8(Т, Т) - объем финансовых ресурсов, необходимый для проекта. Смысл этого неравенства в том, что потребность в ресурсах ниже, чем равномерное их использование. В этом случае возможно идеальное агрегирование. Параметры агрегированной операции:

\Уэ = Й(Т), .

N. если N < А, 8(Т)

если>1 2: А.

В третьей главе описано применение разработанных методов для формирования плана ввода оборудования в НПО «ЗНОК и ППД».

Рассмотрим задачу формирования плана по вводу оборудования на 1997 год. Укрупненные мероприятия плана (проекты) приведены в таблице 1. ,;

Таблица 1.

№ Ввод оборудования Затраты (млн. руб.)

1 Клей-расплав 1500

2 2-хелойная термоустойчивая лента 1100

3 Цех сборки насосов 2700

4 Цех ТИТ 700

5 Сервис насосов 300

б Диагностика резервуаров и трубопроводов 700

7 Очистка и покрытие резервуаров 400

8 Автотранспортный участок 1600

9 Экспериментальное оборудование 1000

Каждый проект состоит из нескольких мероприятий (операций) ряд из которых технологически связаны. В то же время проекты технологически независимы. Таким образом мы имеем дело с мультипроектами.

Для каждого проекта была решена задача агрегирования.

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

Таблица 2.

№ Наименование проекта Затраты млн. руб. Мни. продшкс педель Коэф. упущен, выгоды млн. руб. Эффективность

1 Клей-расплав 1500 1 400 0,26

2 2-хслойная термоустойчивая лента 1100 1,5 • 300 ' 0,27

3 Цех сборки насосов 2700 . • 3 600 0,22

4 Цех ТИТ 700 3 300 0,43

5 Сервис насосов . 300 0,5 260 0,86

6 Диагностика резервуаров и трубопроводов 700 1 50 ■ 0,07

7 Очистка и покрытие резервуаров 400 1 130 0,33

8 Автотранспортный участок 1600 1 500 0,31

9 Экспериментальное оборудование 1000 1 200 0,2

Задача решалась по критерию упущенной выгоды с применением эвристического правила (упорядочение проектов по убыванию приоритетов с/УД). Было получено решение с величиной упущенной выгоды на 2 млрд. или на 20 , % меньше, чем в первоначально разработанном варианте плана.

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

1. Доказано свойство инвариашиости вектора Ьч во времени (направление вектора не меняется, меняется только его длина), которое позволяет свести задачу распределения ресурсов к решению системы нелинейных уравнений.

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

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

4. Дана постановка задачи минимизации упущенной выгоды И

предложен эвристический алгоритм для ее решения.

t

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

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

7. Предложенные методы цашли применение в НПО «ЗНОК и ППД» для формирования годового плана ввода оборудования. Экономический эффект от оптимизации плана составляет 2 млрд. руб. за 1997 год.

Основные публикации:

1.Kboh О.Ф. «Распределение ограниченных средств в условиях чрезвычайной ситуации» - Материалы четвертой международной конференции «Проблемы управления в чрезвычайных ситуациях». Москва, ИПУ РАН, 1997 г.

2. Квон О.Ф. «Задачи распределения ресурсов при управлении мультипроектами» - Сборник трудов международного семинара СОВНЕТ'97 «Управление проектами в переходной экономике: инвестиции, инновации, менеджмент». Москва, 1997 г.

3. Бурков В.Н., Квон О.Ф., Цитович J1.A. «Модели и методы мультнироектного управления». - Препринт. Москва, ИПУ, !997 г.