Resource-constrained project scheduling problem under uncertainty of cash flows.pdf Введение Календарное планирование как метод управления проектами возник сравнительно недавно. Потребность в планировании этапов работ, объемов необходимых ресурсов и сроков строительства существовала с древнейших времен. Однако подходы к решению этих задач сформировались только в ХХ в. Одной из первых форм описания проектных работ с привязкой ко времени выполнения считают диаграммы Ганта, появившиеся в 1910-х гг. [1]. Предложенные инженером Генри Гантом ленточные графики первоначально использовались при разработке крупномасштабных военных и инфраструктурных проектов в США. Появление удобного метода визуализации привело к тому, что этап расстановки проектных работ во времени, получивший название календарного планирования, стал неотъемлемой частью инвестиционного проектирования. В 1930-е гг. в СССР разрабатывались методы поточного выполнения строительных работ. Были созданы новые инструменты визуализации, приспособленные для проектов высокой сложности. Начало активного использования математических моделей календарного планирования пришлось на 1950-е гг. Это было связано с потребностью планирования и управления сложными проектами, состоящими из большого числа взаимосвязанных работ. Такие проекты требовали объединения усилий многих исполнителей и значительных ресурсов. В этот период укрепилось понимание важности календарного планирования и оперативного управления в обеспечении высокого качества принимаемых решений. Моделирование позволяло также уменьшить сроки выработки решения и обеспечить возможность его корректировки в изменяющихся условиях. Подходы к календарному планированию, существовавшие в тот период времени, не соответствовали сложности решаемых задач. Это привело к возникновению и развитию математического аппарата, а также активному применению вычислительной техники. В этот период появились такие формы представления календарных планов, как CRM (Critical Path Method) и PERT (Project Evaluation and Review Technique). Вместе с новыми формами записи были разработаны и методы решения задач календарного планирования, например метод критического пути. Разнообразие рассматриваемых ситуаций привело к тому, что изучение задач календарного планирования (ЗКП) велось в рамках различных научных дисциплин. В теории сетевого планирования, например, решались задачи оптимального распределения ресурсов при выполнении комплекса работ. Теория расписаний рассматривала процессы обработки изделий и транспортировки продукции, в которых задействованы ресурсы оборудования и других видов основных средств. Кроме того, задачи планирования деятельности по оказанию услуг, а также распределения поступающих клиентских заявок изучались в рамках теории массового обслуживания. Календарное планирование играет важную роль в процессах организации и управления инвестиционным проектом. Календарный план - это проектно-технологический документ, определяющий порядок работ, их продолжительность и объем задействованных в каждый момент производственных ресурсов разных видов [2]. Качество календарного плана определяется также полнотой учета технологических особенностей конкретного проекта. Основная цель календарного планирования состоит в составлении таких расписаний выполнения работ, которые удовлетворяют всем технологическим ограничениям, а также обеспечивают рациональное использование производственных ресурсов. Критерий оптимальности расписания должен отражать наиболее существенную характеристику плана (например, длительность реализации проекта, совокупные затраты, прибыль, эффективность использования ресурсов, экологичность производства). Кроме того, могут быть использованы и комплексные критерии. В практике численного решения из-за сложности учета большого числа факторов обычно рассматриваются задачи с укрупненными параметрами и единственным критерием оптимальности. Постановка задачи Рассмотрим инвестиционный проект, предполагающий выполнение заданного количества работ за определенный промежуток времени. Каждая из работ характеризуется длительностью её выполнения, затратами ресурсов и доходами, которые она генерирует. Кроме того, известны технологические и организационные взаимосвязи между работами. Это, в частности, может выражаться в необходимости завершения одной работы до выполнения другой. Источниками финансирования проекта являются собственные средства организации, а также доходы, полученные в процессе его реализации. Для простоты будем считать, что все ресурсы проекта могут быть сведены к денежным. Бюджет проекта известен заранее. Будем считать, что в отсутствие достаточного объема средств на выполнение любой из работ проект должен быть остановлен. Планирование бюджета, а также доходов и расходов по проекту будем вести по годам. Для оценки результатов реализации проекта воспользуемся показателем чистой приведенной стоимости (NPV). Данный показатель представляет собой стоимость прибыли от всех запланированных работ, дисконтированную к моменту начала инвестирования. Таким образом, рассматриваемая нами задача календарного планирования инвестиционного проекта заключается в нахождении оптимального времени начала для каждой из работ, при котором выполняются ограничения на достаточность средств, взаимосвязь работ и обеспечивается максимум NPV. Основными проявлениями факторов неопределенности, действующих в процессе реализации проекта, будут недополучение запланированных доходов и рост издержек реализации проекта. Таким образом, возникает необходимость рассматривать затраты и доходы по проекту в качестве случайных величин, а их прогноз осуществлять, делая предположения о характеристиках распределений этих случайных величин. Сформулируем математическую постановку описанной оптимизационной задачи. Пусть V = {1, 2, N} - множество запланированных работ, связанных друг с другом отношением частичного порядка E. Каждая из работ характеризуется сроками Q = (q1, q2, ..., qN), необходимыми для ее выполнения. Обозначим через с(т) случайные величины поступлений от j-й работы в момент времени т. Для отрицательных значений cj(i) речь будет идти о расходах на выполнение работы. Бюджет проекта в момент t обозначим через K(t), а ставку дисконтирования - через r0. Кроме того, обозначим через Nt множество работ, выполняемых в интервале [t; t+1). Будем искать оптимальные сроки начала каждой из работ, которые образуют расписание выполнения проекта S = (s1, s2, ., sN). Чистый приведенный доход от j-й работы рассчитывается по формуле NPV = У С (ТУ . (1) j & (1 + Г )т Ниже представлен итоговый вид оптимизационной модели. NPVj NPV (SУ = max У S |_ j^V (1 + Го) si + q, sj, (Л j)e E, i-rK^t+iуСгт*°-''=1-2-T-1. t=0 (1 + Г0 ) t=0 jeNt (1 + Г0 ) (2) _1_ (3) (4) Рассматриваемая модель предложена Е.А. Казаковцевой и В.В. Серва-хом [3, 4]. Очевидно, что целевая функция модели представляет собой случайную величину, распределение которой зависит от распределений случайных характеристик работ. Отметим также, что при заданном допустимом расписании S целевая функция NPV(S) есть линейная комбинация величин поступлений от каждой из работ: N qj NpV (S ) = iia,(r)-c,(r), (5) j =1т=0 где aj (т) = (1 + г0 )s У. Подходы к оценке рисков проекта Даже самое упрощенное описание инвестиционного проекта будет содержать параметры, значения которых могут со временем измениться. В особенности это касается долгосрочных проектов со сложной внутренней структурой. Планирование таких проектов и прогнозирование целевых показателей ведутся в условиях неопределенности. Под неопределенностью в проектном анализе принято понимать неполноту и неточность информации об условиях реализации проекта. С неопределенностью тесно связано понятие инвестиционного риска. В разных источниках риск определяется по-разному. Наиболее существенным отличием нам представляется учет «знака» последствий. Так, например, в рекомендациях по стандартизации менеджмента риска [5] он определяется как следствие влияния неопределенности на достижение поставленных целей. Под влиянием понимается положительное или отрицательное отклонение от ожидаемого результата или события. Характеризуя риск, как правило, описывают возможные события или их результаты. Другие авторы при характеристике риска делают акцент на ухудшении положения. Например, П.Л. Виленский называет риском возможность возникновения таких условий, которые приведут к негативным последствиям для всех или некоторых участников проекта [6]. При этом автор замечает, что, в отличие от неопределенности, понятие риска субъективно. Разные участники проекта могут видеть в одних и тех же событиях как угрозы, так и возможности для себя. В предложенной нами постановке ЗКП единственными параметрами, выражающими неопределенность условий реализации проекта, выступают компоненты потока платежей. Далее будем считать, что временные характеристики проекта, а также запасы собственных средств компании не подвержены колебаниям. Рассмотрим, как могут быть адаптированы популярные на практике методы количественной оценки рисков к сформулированной модели. Если при реализации проекта могут возникнуть условия, существенным образом влияющие на основные его характеристики, имеет смысл оценивать изменения параметров в совокупности. Для каждого сценария развития событий мы будем иметь дело с набором фиксированных характеристик проекта. Такой подход, в частности, позволяет учитывать взаимное влияние параметров. Как правило, число рассматриваемых сценариев невелико. Не нарушая общности подхода, можно остановиться на трёх сценариях: пессимистическом, оптимистическом и нейтральном, которым соответствуют потоки платежей С-, С+ и С0. Поскольку все параметры модели для каждого из сценариев известны, могут быть найдены расписания S , V и S0, обеспечивающие максимум NPV. При описании сценариев оцениваются также вероятности развития событий по каждому из них: p-, p+ и p0. По этим данным может быть оценено среднее значение прибыли для выбранного расписания. Например, для нейтрального сценария имеем NPV(S°) = p-NPV(S°, С-) + p0 NT\\\\S, С0) + p ■ NPV(S°, C). При проведении экспертной оценки вариантов развития проекта неопределенные параметры часто задаются в виде дискретных случайных величин. Ввиду сложности прогнозирования обычно рассматривается небольшое число исходов. Например, компоненты потока платежей для j-й работы в каждый момент времени т могут быть представлены следующим образом: с-,(т) с вероятностью p-/т); с°,(т) с вероятностью р0,(т); с 7(т) с вероятностью p+j(r). Тот или иной исход создает новые условия для последующих работ по проекту. При этом последовательности исходов, позволяющие завершить проект, могут отличаться значением целевой функции. Кроме того, часть реализаций приведет к приостановке проекта раньше срока по причине недостаточности средств. Визуальной моделью такого развития событий может служить дерево исходов. Двигаясь вдоль ветвей такого дерева, можно построить все возможные векторы параметров проекта. Для каждого из этих векторов и любого из расписаний, соответствующих условиям частичного порядка, можно проверить выполнение бюджетных ограничений. Если ограничения выполняются, можно определить значение NPV. В противном случае можно определить вероятность того, что проект не будет реализован. Если компоненты потока платежей характеризуются непрерывными случайными величинами или же имеют значительное число дискретных исходов, применение сценарных методов затруднено. В такой ситуации оценку рисков можно производить, моделируя распределение NPV методом Монте-Карло. Тип и характеристики распределения NPV в некоторых случаях можно получить аналитически. Пусть, например, все компоненты потока платежей представляют собой независимые случайные величины, которые подчиняются нормальному закону распределения с7(т)еЛ(ц7(т), с}(т)). Тогда для каждого допустимого расписания S верно, что NPV(S)eN (h(S), o(S)), где N qj N qj h(s)=j (т) • н j (т), а °(S)=А ZZ(r (т) • %2 (т). j=1 т=0 У j=1 т=0 Устойчивостью относительно композиции случайных величин обладают, например, биномиальное распределение и распределение Пуассона [7, 8]. Эти свойства позволяют анализировать свойства закона распределения NPV(S) для выбранного допустимого расписания без моделирования распределения в ходе испытаний. Для сравнения расписаний можно использовать такие характеристики распределений, как среднее значение NPV, дисперсия и коэффициент вариации прибыли [9]. Две последние характеристики часто используют для сравнения риска проектов. Однако рассмотренные ранее определения риска показывают, что отклонения целевого показателя в большую сторону с полным основанием могут не считаться риском. В этом случае характеристики колеблемости случайной величины для оценки риска подходят плохо. В качестве альтернативы предлагается оценивать вероятность получения прибыли не ниже заданного уровня и по этой характеристике сравнивать уровень риска расписаний [10]. При расчете характеристик распределения NPV(S) возникает необходимость учитывать также риск того, что при определенных сочетаниях случайных характеристик проект не будет реализован. Чтобы иметь возможность продолжить работы по проекту, можно привлечь заёмные средства. В каждый момент времени, когда ограничение на достаточность средств не выполняется, мы будем компенсировать разницу за счет кредита, плата за пользование которым взимается по ставке r*. Расходы на привлечение кредитных ресурсов будут уменьшать размер NPV. Случай дискретного распределения параметров проекта Продемонстрируем применение описанных выше метрик риска к задаче календарного планирования. Рассмотрим условный проект, состоящий из 6 работ. На рис. 1 приведен сетевой график проекта. Стрелками на графике соединены работы, связанные отношениями частичного порядка. Для j-й работы на графике приведено значение параметра qj - число лет реализации. Работы с номерами (0) и (7) представляют собой моменты начала и конца проекта и имеют длительность 0. Предельный срок реализации проекта составляет 8 лет. Будем считать размер бюджета проекта постоянным и равным 5 единицам на начало каждого года. Примем ставку дисконтирования r0 равной 10 % годовых. Рассмотрим несколько вариантов представления случайных характеристик проекта. Для случая дискретного распределения компонентов потока платежей зададим для каждой величины jr) два возможных значения {с-,(т), cjr)}, которые будем считать равновероятными. Указанные величины приведены в табл. 1. Таблица 1. Дискретные параметры потока платежей j т 0 1 2 3 1 {-5,5, -4,4} {-2,2, -1,76} 2 {-5,5, -4,4} {-1,65, -1,32} {4,5, 5,4} 3 {-1,65, -1,32} {9, 10,8} 4 {-5,5, -4,4} {-5,5, -4,4} {1,8, 2,16} {7,2, 8,64} 5 {4,95, 5,94} {5,4, 6,48} {4,05, 4,86} {1,8, 2,16} 6 {-5,5, -4,4} {-2,2, -1,76} {-3,3, -2,64} {7,2, 8,64} Учитывая, что общее число параметров работ равно 19, число ветвей дерева исходов равно 219 = 524288. Для моделирования распределений NPV в зависимости от расписания проведем 10000 вычислительных экспериментов. В ходе каждого эксперимента будем случайно выбирать вариант потока платежей и находить оптимальное расписание и значение NPV. Поиск оптимальных расписаний выполнялся с помощью ранее разработанного авторами генетического алгоритма [11]. В зависимости от случайной реализации потока платежей оптимальным оказывалось одно из четырёх расписаний (табл. 2). Среднее значение максимума NPV свидетельствует о предпочтительности расписания (1, 0, 2, 2, 2, 5) перед другими в ситуации, когда это расписание допустимо. Однако необходимо учитывать также риск невозможности завершить проект без привлечения дополнительных средств. Этот риск можно определить как долю числа экспериментов, для которых выбранное расписание оказывалось недопустимым из-за ограниченности бюджета проекта. Таким образом, для наиболее выгодного расписания мы сталкиваемся с наибольшим риском остановки проекта. Таблица 2. Оптимальные расписания проекта (дискретный случай) Расписание Число экспери ментов Среднее значение NPV Доля случаев недопустимости (1, 3, 2, 2, 5, 5) 4867 6,904 0 (1, 0, 2, 2, 2, 5) 2434 12,166 0,756 (0, 2, 1, 2, 4, 5) 2561 8,811 0,5 (1, 2, 4, 2, 4, 5) 138 8,596 0,251 Если для какого-либо эксперимента расписание оказывается недопустимым, мы можем рассчитать скорректированную величину NPVD по формуле NPVd(S) = NPV(S) - D(S) ■ (1+r*), где D(S) - размер суммарного дефицита средств. NPVD показывает текущую стоимость прибыли с учетом затрат на привлечение заёмных средств. Для распределения NPVD могут быть найдены характеристики, по которым можно сравнивать уровень риска для различных расписаний. На рис. 2 приведены графики плотности распределения NPVD для различных расписаний при r* = 0. Рис. 2. Плотности распределения NPVD В табл. 3 представлены величины скорректированной прибыли, а также оценки риска выбора каждого из расписаний. Таблица 3. Характеристики прибыли и риска проекта (дискретный случай) Расписание Средняя NPVD Стандартное отклонение Коэффициент вариации Вероятность того, что NPVD < 8 (1, 3, 2, 2, 5, 5) 7,644 2,234 0,292 0,561 (1, 0, 2, 2, 2, 5) 9,720 2,893 0,298 0,277 (0, 2, 1, 2, 4, 5) 8,399 2,467 0,294 0,436 (1, 2, 4, 2, 4, 5) 6,279 2,920 0,465 0,706 Расписание (1, 0, 2, 2, 2, 5) характеризуется наибольшим риском по стандартному отклонению и коэффициенту вариации, но даже с учетом затрат на ликвидацию дефицита средств позволяет получить наибольшую среднюю прибыль. Среднее значение NPVD для всех расписаний, кроме расписания (1, 3, 2, 2, 5, 5), зависит от размера r*. На рис. 3 графически представлены указанные зависимости для тех расписаний, относительно которых нельзя сделать однозначный выбор по характеристикам дохода и риска. Таким образом, при r < 2,133 наибольшую среднюю прибыль обеспечивает расписание (1, 0, 2, 2, 2, 5), при 2,133 < r < 3,016 - расписание (0, 2, 1, 2, 4, 5), а при r > 3,016 - расписание (1, 3, 2, 2, 5, 5), для которого риск нехватки средств отсутствует. Случай непрерывного распределения параметров проекта Пусть теперь компоненты потоков платежей будут распределены по нормальному закону с параметрами с_,(т)еЛ(ц7(т),ст,(т)). Для расчёта параметров распределений воспользуемся формулами: компоненты которых приведены в табл. 1. В непрерывном случае число различных векторов параметров является бесконечно большим, однако мы можем получить представление о распределении NPV, проведя вычислительные эксперименты. В табл. 4 приведены результаты экспериментов. В отличие от дискретного случая, когда крайние значения параметров потока платежей выбирались с вероятность 0,5, при нормальном распределении С](т) большинство исходов соответствует середине интервала. Число оптимальных расписаний уменьшилось до трёх, а расписание с наибольшей средней NPV имеет очень высокий риск дефицита средств. Таблица 4. Оптимальные расписания проекта (непрерывный случай) Расписание Число экспериментов Среднее значение NPV Доля случаев недопустимости (1, 3, 2, 2, 5, 5) 1502 7,332 0 (1, 0, 2, 2, 2, 5) 82 11,683 0,992 (0, 2, 1, 2, 4, 5) 8416 8,737 0,150 В табл. 5 приведены характеристики риска и скорректированной прибыли для случая r* = 0. В данном случае расписание (0, 2, 1, 2, 4, 5) лучше расписания (1, 3, 2, 2, 5, 5) и по среднему значению прибыли, и по уровню риска. На рис. 4 представлены графики плотности распределения NPVD для различных расписаний. Таблица 5. Характеристики прибыли и риска проекта (непрерывный случай) Расписание Средняя NPVD Стандартное отклонение Коэффициент вариации Вероятность того, что NPVD < 8 (1, 3, 2, 2, 5, 5) 7,671 0,738 0,096 0,671 (1, 0, 2, 2, 2, 5) 9,913 1,000 0,101 0,028 (0, 2, 1, 2, 4, 5) 8,659 0,799 0,092 0,207 Рис. 5. Зависимость средней NPVD от стоимости кредита Для непрерывного случая также могут быть найдены интервалы r*, на которых какое-либо из расписаний обеспечивает максимум средней NPVD. Соответствующие графики приведены на рис. 5. При r < 1,571 наибольшую среднюю прибыль обеспечивает расписание (1, 0, 2, 2, 2, 5), при 1,571 < г* < 49,471 - расписание (0, 2, 1, 2, 4, 5), а при г* > 49,471 - расписание (1, 3, 2, 2, 5, 5), реализуемое без привлечения кредита во всех случаях. Заключение Рассмотренная задача календарного планирования инвестиционного проекта представляет важную проблему в сфере управления производством. Определение оптимальных сроков начала работ позволяет обеспечить более высокий уровень прибыли от проекта. Решение задачи осложняется неопределенностью отдельных характеристик проекта. К числу таких характеристик относятся потоки платежей для отдельных работ. Способ учета неопределенности параметров проекта влияет на выбор подхода к оценке рисков. Проведенный анализ демонстрирует способы выбора расписаний на основе вычислительных экспериментов. Для нахождения оптимальных расписаний использовался предложенный авторами генетический алгоритм. Для случаев дискретного и непрерывного распределения были рассчитаны оценки рисков и сделаны выводы о выборе расписания. В работе рассматривался случай независимости случайных параметров проекта друг от друга. В ходе дальнейшего исследования предполагается рассмотрение задачи многокритериальной оптимизации, а также учет взаимного влияния случайных параметров проекта.

Скачать электронную версию публикации