Задача «А»: составление расписания запуска инновационных проектов в портфеле

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

Пусть имеется п проектов в составе портфеля инновационных проектов U = {a₁,a₂, — , в котором еще не учитывается взаимное влияние проектов.

Предполагается, что все проекты выполняются без прерываний.

Обозначим через Т= {1,2, ...,τ} множество пронумерованных допустимых для расписания квантов времени (номера событий), в которых может осуществляться выполнение ограничений. Тогда длительность τ - желаемая или предельная продолжительность выполнения всех проектов в портфеле, !- предлагаемая алгоритмом продолжительность. Время выполнения t? каждого проекта a?∈ U может определяться в днях, неделях, месяцах в зависимости от масштаба проектов, і = 1,2, —, п.

Каждый проект характеризуется такими параметрами, как s? - номер начального события проекта а? , /? - номер конечного события проекта а? , при этом номера s?,/? ∈Т.

В портфеле экспертным методом выявляются группы зависимых проектов по невещественным ресурсам. Согласно следствию (п. 2.2) множество таких групп обозначим как Z⊆ U, где:

- группы зависимых проектов не пересекаются: Z_fe ∩ Z_y∙ = 0, к≠ j, к, у = 1,2, —, ζ, к и j - порядковые номера групп зависимых проектов, ζ - количество групп зависимых проектов, 1 ≤ ζ ≤ п/2;

- группа Z_feсостоит из проектов: Z_fe = {z_fel, ...,z_fem, ...,z_feε}, m- порядковый номер зависимого проекта, m = 1,2, —, ε, ε- количество зависимых проектов в группе, 1 < ε ≤ п.

Для каждой пары, состоящей из подгруппы проектов Z_ij,выбранном диапазоне начал s = s?— s_j∙рассчитывается коэффициент взаимовлияния a?j(s), a_ij(s) > 0.

Пусть R = {r₁,r₂,... ,r_p} - множество видов вещественных ресурсов,

необходимых для выполнения проектов и имеющих прямое влияние на последовательность запуска их в портфеле. Тогда Vj(t)- располагаемый в определенный момент времени фонд ресурса вида r_j∙∈R, D_ij-(t)- потребность в ресурсе η ∈ Rдля выполнения проекта и?.

В портфеле Uмогут находиться также и независимые по невещественным ресурсам проекты: Y⊂ U - множество независимых проектов, Y = {y₁, ...y_γ}, 0 ≤ γ ≤ п.

Сумма зависимых и независимых проектов равна числу всех проектов в портфеле п.

Обозначим через - эффект от реализации независимого проекта y_iи - эффект от реализации зависимого проекта z_i. Эффект от реализации взаимосвязанных проектов зависит от коэффициента взаимовлияния проектов:

Вектор O = (k₁, s₂, ..., s_n)называется расписанием выполнения проектов в портфеле. Расписание O называется допустимым, если:

- в каждый момент времени t ∈Т потребность в ресурсах для выполнения

проектов будет удовлетворена дляпри этом

в ограничениях учитываются все виды вещественных ресурсов;

- суммарный эффект от зависимых проектов будет выше или равен допустимому

- проект и_? может быть начат в период не позже, чем разница между количеством доступных периодов т и длительностью проекта t_?плюс один период, т. к. отсчет начинается с единицы:

Целевая функция равна:

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

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

Решение задачи

Проиллюстрируем поставленную задачу «А» в виде схемы в соответствии с рисунком 3.4.

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

Поставленная дискретная задача в условиях заданных ограничений на ресурсы является NP-трудной [198-200]. В силу сложности данных задач целесообразно использовать малотрудоемкие алгоритмы, такие как приближенные методы [201­203],базирующиеся на приоритетных правилах, лагранжевых релаксациях, идеях эволюции, локальном поиске и др. Приближенные методы активно применяются при решении задачи составления расписания портфелей проектов [204-206].

В настоящее время на рынке программного обеспечения представлен ряд инструментов, позволяющих решить поставленную задачу составления расписаний. Такими инструментами могут выступать расширение «Поиск решения» в Excel (Microsoft), пакет Optimization в Maple (Waterloo Maple Inc.), пакет Optimization в MatLab (The MathWorks) и др.

В рамках данного исследования для верификации поставленных задач был выбран широко доступный инструмент «Поиск решения» приложения Microsoft Excel. Был использован эволюционный метод, основанный на генетическом алгоритме и локальном поиске, внедренный в данный инструмент «Поиск решения» [207]. Генетический алгоритм - эвристический алгоритм поиска, напоминающий биологическую эволюцию. В таком алгоритме генерируется и используется одновременно не одно, а несколько допустимых решений. Итеративно на основе комбинации лучших свойств этих нескольких решений создаются новые более эффективные расписания, которые заменяют полученные на более ранних итерациях алгоритма и используются на дальнейших этапах решения. Особенностью метода локального поиска является то, что на каждой итерации процесса выбор нового решения производится не детерминировано, а в результате реализации некоторого случайного процесса [200, 203].

Верификации поставленной задачи «А» проводились как на тестовых данных, так и на реальных портфелях инновационных проектов. Пример решения задачи приведен в параграфе 4.3.

3.4