Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,074

AGGREGATE PROJECT ALGORITHMS

Klevanskiy N.N. 1 Krasnikov А.А. 1
1 Saratov State Agrarian University named after N.I. Vavilov
Представлены методы решения задач агрегирования проектов – первой задачи мультипроектного планирования. Двухэтапный вычислительный процесс реализован в среде СУБД и включает формирование начальной агрегации на первом этапе и ее последующую оптимизацию на втором этапе. Каждый этап цикличен, так как содержит две «жадные» эвристики. В каждом шаге цикла результат работы первой эвристики используется второй эвристикой. Каждая эвристика осуществляет выбор наиболее приемлемого критерия загруженности или равномерности с принятием некоторых решений. В операциях выбора использованы различные методы ранжирования теории принятия решений. В агрегировании проектов использованы «жадные» алгоритмы и концепции равномерности и загруженности. Осуществлены формализация и постановка задач обоих этапов. Представлены алгоритмы решения задач обоих этапов. Рассмотрен численный пример агрегации проекта.
This paper is demonstrate how multi-project scheduling problems can be solved efficiently by two procedures. The first, in the multi-project scheduling problem, multiple projects, each having a number of activities, must be aggregated. A set of local and global resources are available for carrying out the activities of the projects. The basic criteria for choice operations are demanded – criterion of activity workload and criterion of resource equability. The aggregate project procedure use of two-stage algorithm developed in database system. The solutions obtained by the first stage algorithm with the best resource allocation rule are used as a baseline to compare those obtained by the latter. Each stage consists of two heuristic solution-finding procedures based on greedy ideology. The greedy algorithms use multi-criteria and multi-vectorial ranking of decision support theory. The algorithm introduces the concept of an adjustable resource allocation factor which can be used to produce schedules. A numerical example of aggregate project is given.
multi-project scheduling
aggregate project
demand
activity
greedy algorithm
multi-vectorial ranking
1. Barkalov S.A., Burkov V.N., Giljazov N.M. Metody agregirovanja v upravlenji proectami. М.: (Priprint / IPU RAN), 1999 55 p.
2. Burkov V.N., Kvon O.F., Citovitch L.A. Моdeli i metody multiproectnogo upravlenija. М.: (Priprint / IPU RAN), 1997. 62 p.
3. Klevansky N.N. Оsnovnyje concepciji realizaciji zadach formirovanija raspisanij // Оbrazovatelnuje resursy i tehnologiji, М., 2014. no. 2 (5). рр. 9 21.
4. Коchetov J.А.. Stoljar А.А. Novyje zhadnyje evristiki dlja zadachi kalendarnogo planirovanija s ogranichennymi resursami // Diskretnyj analiz i issledovanije operacij. Novosibirsk. 2005. Serija 2. tom 12, no. 1. рр. 12–36.
5. Lazarev А.А., Gafarov E.R. Teorija raspisanij. Zadachi l algoritmy. М., Fizicheskij facultet MGU, 2011. 222 p.
6. Podinovskij V.V. Аnaliz zadach mnogokriteralnogo vybora metodami teorii vazhnosti kriteriev pri pomoshchi kompjuternych system podderhzhki prinjatija reshenij // Izvestija RAN. Teorija i sistemy upravlenija. 2008. no. 2. рр. 64–68.
7. Safronov V.V., Vedernikov J.V. Characteristika metoda «zhestkogo» ranzhirovanija // Informacionnyje technologii. 2007. no. S11. рр. 17–21.
8. Kane H., Tissier A. A resource allocation model for multi-project management // Proc. of MOSIM12 9e conference internationale de modelisation, optimisation et simulation. Bordeau, France, 2012. 8 p.

Мультипроектное планирование решает взаимосвязанные проблемы – формирование календарного графика [2] и распределение ресурсов [8]. Один из подходов к решению этих проблем использует агрегированные представления проектов [1, 2].

Календарные графики мультипроектного планирования относятся к расписаниям иерархических или сетевых структур действий [3]. Формирование расписания – это определение времен начала выполнения всех действий или их совокупностей в интервале расписания [5]. Для мультипроектного планирования необходимо решение двух задач:

1) агрегирование заявок проекта – определение относительных начальных времен выполнения каждой работы в пределах интервала расписания проекта (длительности критического пути графа проекта или задаваемой/переопределяемой длительности);

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

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

Общие подходы

Агрегирование является задачей управления одним проектом, но в отличие от [4] необходимы допущения. На данном этапе исследования интервал расписания агрегации принят равным критическому пути графа проекта. В получаемых решениях разрешено превышение потребляемых ресурсов на отдельных тактах планирования по сравнению с уровнями выделяемых проекту ресурсов. В последующем мультипроектном планировании эти превышения будут удовлетворяться совместно используемыми выделяемыми ресурсами. Интервалы, в пределах которых могут «мигрировать» работы, не находящиеся на критическом пути, позволяют осуществить варьирование агрегаций.

Алгоритмизация и разработка программного обеспечения агрегирования проектов использовали следующие концепции [3]: программное решение задачи в рамках СУБД; двухэтапный процесс решения; идеология жадного алгоритма; концепции загруженности и равномерности; использование методов ранжирования теории принятия решений.

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

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

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

Операции выбора в представляемых алгоритмах являются многокритериальными [6], и для их реализации привлечен аппарат методов ранжирования. В представляемых алгоритмах использованы методы, в основе которых лежит метод «жесткого» ранжирования [7]. В дальнейшем под термином многокритериальное ранжирование будет пониматься «жесткое» ранжирование. Будут различаться прямое (по «возрастанию») и обратное (по «убыванию») многокритериальное ранжирование.

Постановка и формализация задачи

Введем необходимые в дальнейшем обозначения.

Исходные данные задачи:

I – количество проектов мультипроектного планирования;

klevans01.wmf – множество проектов мультипроекта;

nei – количество работ проекта pi;

klevans02.wmf – множество работ проекта pi (j = 1 – источник, j = nei – сток);

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

epj,i – количество непосредственных предшественников работы ej,i;

EPj,i – множество непосредственных предшественников работы ej,i, EPj,i ∈ Ei;

efj,i – количество непосредственных последователей работы ej,i;

EFj,i – множество непосредственных последователей работы ej,i, EFj,i ∈ Ei;

u – количество типов возобновляемых ресурсов;

klevans04.wmf – множество типов возобновляемых ресурсов;

Rm,i, klevans05.wmf klevans06.wmf – объем ресурса типа km, выделяемый проекту pi во время его выполнения на каждом такте планирования;

rm,j,i, klevans07.wmf klevans08.wmf klevans09.wmf – объем ресурса типа km, требуемый работе ej,i проекта pi во время ее выполнения на каждом такте планирования;

dj,i, klevans10.wmf klevans11.wmf – длительность (трудоемкость) выполнения работы ej,i проекта pi, такты планирования.

Исходные расчетные данные задачи:

Cpi, klevans12.wmf – критический путь проекта pi, такты планирования;

Di – трудоемкость проекта pi. В предлагаемом решении Di = Cpi = Int, klevans13.wmf.

Переменные задачи:

ni, klevans14.wmf – количество: включенных в начальную агрегацию работ проекта pi; переставленных работ проекта pi в календарном графике агрегации;

nr, klevans15.wmf – количество: не включенных в начальную агрегацию заявок проекта pi; не оптимизированных работ проекта pi в календарном графике агрегации;

на любом шаге формирования и оптимизации начальной агрегации ni + nr ≡ nei;

tij,i – минимально возможный такт включения работы ej,i в агрегацию проекта pi:

tfj,i – максимально возможный такт включения работы ej,i в агрегацию проекта pi:

tj,i – начальный такт выполнения работы ej,i проекта pi в календарном графике агрегации;

Rmaxm, klevans16.wmf – максимальный тактовый объем потребляемого ресурса типа km в календарном графике агрегации;

klevans17.wmf klevans18.wmf klevans19.wmf – средний объем ресурса типа km, потребляемый работами проекта pi в интервале расписания;

RSm,j, klevans20.wmf klevans21.wmf – объем ресурса типа km, потребляемый календарным графиком агрегации на j-м такте интервала расписания;

klevans22.wmf klevans23.wmf – среднеквадратичное отклонение потребления ресурса типа km на всех тактах интервала расписания от среднего значения потребления этого ресурса в расписании.

Задача формирования начальной агрегации проекта pi состоит в цикличном выборе очередной, не находящейся на критическом пути, заявки проекта и формировании расписания klevans24.wmf, которое минимизирует вектор максимальных тактовых объемов потребляемых ресурсов внутри критического пути (интервала расписания)

klevans25.wmf (1)

при обязательных ограничениях

klevans26.wmf klevans27.wmf;

klevans28.wmf klevans29.wmf (2)

klevans30.wmf klevans31.wmf;

klevans32.wmf klevans33.wmf (3)

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

Интервалы включения заявок ej,i в календарный график агрегации определяются следующими выражениями:

klevans34.wmf (4)

klevans35.wmf (5)

Минимально возможные такты включения (4) определяются для всех заявок от источника до стока, для непосредственных последователей источника tik,i = 0. Максимально возможные такты включения (5) определяются в обратном порядке – от стока до источника. Для непосредственных предшественников стока tfk,i = Cpi.

Оценки загруженности cj,m,i заявки ej,i проекта pi на очередном шаге формирования начальной агрегации определяется объемом требуемого ресурса

klevans36.wmf klevans37.wmf

klevans38.wmf klevans39.wmf. (6)

Оценки загруженности (6) формируют множество векторов (критериев загруженности) заявок на очередном шаге формирования календарного графика начальной агрегации:

klevans40.wmf (7)

Обратное многокритериальное ранжирование векторов (7) порождает множество рангов заявок

klevans41.wmf (8)

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

Для определения времени включения tni+1,i работа eni+1,i последовательно, по одному такту перемещается с учетом ограничений (2), (3) внутри интервала [tini+1,i, tfni+1,i], формируя множество векторов:

klevans42.wmf (9)

Прямое многокритериальное ранжирование векторов (9) определяет доминирующий вектор, индекс j которого определяет искомое начальное время включения работы eni+1,i в календарный график начальной агрегации tni+1,i = j.

Очередной шаг формирования начальной агрегации завершается переопределением tfj,i для работ, предшествующих от источника. Для работ, непосредственно предшествующих eni+1,i, в выражениях (5) применяется tni+1,i. Также осуществляется переопределение tij,i для работ, следующих от eni+1,i до стока. Для работ, непосредственно следующих от eni+1,i, в выражениях (4) применяются tik,i = tni+1,i и dk,i = dni+1,i. Если nr > 0, то переход к следующему шагу формирования начальной агрегации.

Задача оптимизации начальной агрегации проекта pi состоит в изменении начальной агрегации для формировании расписания klevans43.wmf, которое минимизирует вектор среднеквадратичных отклонений потребления ресурсов klevans44.wmf на всех тактах интервала расписания от средних значений потребления ресурсов расписания

klevans45.wmf (10)

при обязательных ограничениях (2), (3).

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

Оценка равномерности n-го такта работы ej,i проекта pi по ресурсу km на очередном шаге оптимизации начального календарного графика агрегации определяется следующим выражением:

klevans46.wmf klevans47.wmf

klevans48.wmf klevans49.wmf klevans50.wmf (11)

Значения тактовых оценок равномерности находятся в интервале [0, 1]. Чем больше величина оценки (11), тем неравномернее соответствующая работа проекта на данном такте интервала расписания по данному ресурсу. Оценки равномерности проектов (11) формируют u множеств векторов (критериев равномерности) работ проекта по каждому ресурсу.

klevans51.wmf

klevans52.wmf (12)

Прямое многокритериальное ранжирование векторов (12) проектов расписания порождает множества рангов векторов работ проекта по каждому ресурсу

klevans53.wmf klevans54.wmf (13)

Ранги векторов (13) формируют множество векторов (критериев равномерности) неоптимизированных работ проекта

klevans55.wmf (14)

Старшая по рангу работа проекта, полученная прямым многокритериальным ранжированием векторов (14), является самой неравномерной среди неоптимизированных при принятых оценках и критериях равномерности. Она становится очередным кандидатом eni+1,i на перестановку в календарном графике агрегации.

Для определения начального времени TIni+1 перестановки работа eni+1,i проекта pi последовательно, по одному такту перемещается с учетом ограничений (2), (3) внутри интервала расписания, формируя множество векторов:

klevans56.wmf (15)

Прямое многокритериальное ранжирование векторов (15) определяет доминирующий вектор, индекс j которого определяет искомое начальное время для перестановки работы eni+1,i проекта pi в календарном графике tni+1,i = j. Очередной шаг оптимизации завершается переопределением tfj,i и tij,i, и если nr > 0, то переход к следующему шагу.

Реализация и численные результаты

Для численных экспериментов использовались случайно выбранные из библиотеки тестовых задач PSPLib проекты. Проекты включают по 30 работ и для своего выполнения им необходимо 4 типа ресурсов.

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

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

На рис. 2 представлена оптимизированная агрегация этого же проекта.

pic_16.tif

Рис. 1. Начальная агрегация проекта

pic_17.tif

Рис. 2. Оптимизированная агрегация проекта

Заключение

Авторы считают, что новыми являются следующие положения и результаты:

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