Научный журнал
Фундаментальные исследования
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

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

Клеванский Н.Н. 1 Красников А.А. 1
1 ФГБОУ ВО «Саратовский государственный аграрный университет имени Н.И. Вавилова»
Представлены методы решения задач агрегирования проектов – первой задачи мультипроектного планирования. Двухэтапный вычислительный процесс реализован в среде СУБД и включает формирование начальной агрегации на первом этапе и ее последующую оптимизацию на втором этапе. Каждый этап цикличен, так как содержит две «жадные» эвристики. В каждом шаге цикла результат работы первой эвристики используется второй эвристикой. Каждая эвристика осуществляет выбор наиболее приемлемого критерия загруженности или равномерности с принятием некоторых решений. В операциях выбора использованы различные методы ранжирования теории принятия решений. В агрегировании проектов использованы «жадные» алгоритмы и концепции равномерности и загруженности. Осуществлены формализация и постановка задач обоих этапов. Представлены алгоритмы решения задач обоих этапов. Рассмотрен численный пример агрегации проекта.
мультипроектное планирование
агрегация проекта
заявка
действие
«жадный» алгоритм
многовекторное ранжирование
1. Баркалов С.А., Бурков В.Н., Гилязов Н.М. Методы агрегирования в управлении проектами. – М.: (Препринт / ИПУ РАН), 1999. – 55 с.
2. Бурков В.Н., Квон О.Ф., Цитович Л.А. Модели и методы мультипроектного управления. – М.: (Препринт / ИПУ РАН), 1997. – 62 с.
3. Клеванский Н.Н. Основные концепции реализации задач формирования расписаний // Образовательные ресурсы и технологии. –М., 2014. – № 2 (5). – С. 9–21.
4. Кочетов Ю.А.. Столяр А.А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. – Новосибирск, 2005. – Серия 2. т. 12, № 1. – С. 12–36.
5. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. – М.: Физический факультет МГУ, 2011. – 222 с.
6. Подиновский В.В. Анализ задач многокритериального выбора методами теории важности критериев при помощи компьютерных систем поддержки принятия решений // Известия РАН. Теория и системы управления. – 2008. – № 2. – С. 64–68.
7. Сафронов В.В., Ведерников Ю.В. Характеристика метода «жесткого» ранжирования // Информационные технологии. – 2007. – № S11. – С. 17–21.
8. Kane H., Tissier A. A resource allocation model for multi-project management // Proc. of MOSIM’12 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. Оптимизированная агрегация проекта

Заключение

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

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

Библиографическая ссылка

Клеванский Н.Н., Красников А.А. АЛГОРИТМЫ АГРЕГИРОВАНИЯ ПРОЕКТОВ // Фундаментальные исследования. – 2016. – № 2-3. – С. 482-486;
URL: https://fundamental-research.ru/ru/article/view?id=39960 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674