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

DEMAND/ACTIVITY NETWORKS SCHEDULING TECHNIQUES

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. The second, in the multi-project scheduling problem, multiple projects must be scheduled. 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 project scheduling 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 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 multi-project scheduling is given.
multi-project scheduling
aggregate project
demand
activity
greedy algorithm
resource allocation
root-mean-square deviation
multi-criteria ranking
1. Barkalov P.S., Burkova I.V., Glagolev A.V. et al. Zadachi raspredelenja resursov v upravlenji proectami. М.: IPU RAN, 2002, 65 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. Оbrazovatelnuje resursy i tehnologiji, М., 2014, no. 2 (5), pp. 9–21.
4. Klevansky N.N., Krasnikov A.A. Fundamentalnue issledovanija, М.: 2016, no. 2–3, pp. 482–486.
5. Klevansky N.N., Krasnikov A.A. VSPU-2014, М.: 2014, pp. 8051–8059.
6. Klevansky N.N., Mihajlova M.M. Dokladi akademiji voennih nauk, Saratov.:. 2012, no. 5(54), pp. 77–82.
7. Коchetov J.А.. Stoljar А.А. Diskretnyj analiz i issledovanije operacij, Novosibirsk. 2005. Serija 2. tom 12, no. 1, pp. 12–36.
8. Lazarev А.А., Gafarov E.R. Teorija raspisanij. Zadachi l algoritmy. М., Fizicheskij facultet MGU, 2011. 222 p.
9. Podinovskij V.V. Izvestija RAN. Teorija i sistemy upravlenija. 2008, no. 2, pp. 64–68.
10. Safronov V.V., Vedernikov J.V. Informacionnyje technologii, 2007, no. S11, pp. 17–21.
11. 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.
12. Kolish R., Sprecher A. PSPLIB A project scheduling library // European Journal of Operational Research. 1996. Vol. 96. рр. 205–216.

Мультипроектное планирование решает взаимосвязанные проблемы – формирование календарного графика [2] и распределение ресурсов [1, 11]. Календарные графики мультипроектного планирования являются расписаниями иерархических или сетевых структур действий [3, 5, 6]. Проекты могут быть технологически независимыми, но объединенными по потребляемым ресурсам. Для описания комплекса работ проекта необходимо наличие описание каждой работы. Трудоемкость (продолжительность) работ измеряется в тактах планирования. Потребности отдельных работ в ресурсах измеряются условными единицами на такт планирования. Работы проектов выполняются с постоянной интенсивностью [1]. Каждый тип ресурса однороден.

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

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

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

Предполагается, что агрегации всех проектов мультипроекта известны [4].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

rm,j,i, klevansk08.wmf klevansk09.wmf klevansk10.wmf – объем ресурса типа km, требуемый работе ej,i проекта pi во время ее выполнения на j-м такте планирования;

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

Int – интервал расписания – длительность календарного графика в тактах планирования.

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

npi, klevansk13.wmf – количество путей графа сети проекта pi;

klevansk14.wmf – множество путей графа сети проекта pi;

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

nepj,i, klevansk16.wmf klevansk17.wmf – количество работ пути pi,j графа сети проекта pi;

klevansk18.wmf klevansk19.wmf – множество работ пути ptj,i графа сети проекта pi;

Di – длительность (трудоемкость) выполнения проекта pi в тактах планирования. В предлагаемом решении принято Di = Cpi, klevansk20.wmf.

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

ni, klevansk21.wmf – количество: включенных в начальный календарный график проектов; оптимизированных (переставленных) проектов в календарном графике;

nr, klevansk22.wmf – количество: не включенных в начальный календарный график проектов; не оптимизированных проектов в календарном графике;

Rmaxm, klevansk23.wmf – максимальная величина тактового потребления ресурса типа km в календарном графике;

TIi – начальный такт планирования для выполнения проекта pi в календарном графике;

TFi = TIi + Di – финальный такт планирования проекта pi в календарном графике;

rpm,j,i, klevansk24.wmf klevansk25.wmf klevansk26.wmf – объем ресурса типа km, потребляемый проектом pi на j-м такте интервала расписания;

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

klevansk29.wmf klevansk30.wmf klevansk31.wmf klevansk32.wmf – средний объем ресурса типа km, потребляемый проектами календарного графика на каждом такте интервала расписания;

RPm,j,i, klevansk33.wmf klevansk34.wmf klevansk35.wmf – оценка равномерности j-го такта проекта pi по ресурсу типа km;

klevansk36.wmf klevansk37.wmf – среднеквадратичное отклонение потребления ресурса типа km от среднего значения в интервале расписания.

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

min(Rmax1, Rmax2, ..., Rmaxu), (1)

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

klevansk39.wmf

klevansk40.wmf (2)

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

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

klevansk41.wmf klevansk42.wmf

klevansk43.wmf klevansk44.wmf (3)

Чем больше величина оценки (3), тем более соответствующая работа ej,i проекта pi загружена по ресурсу типа km. Оценки (3) формируют множество векторов (критериев загруженности) работ на очередном шаге формирования начального календарного графика

klevansk45.wmf (4)

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

klevansk46.wmf (5)

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

klevansk47.wmf (6)

Обратное многокритериальное ранжирование векторов (6) порождает множество рангов критериев загруженности путей графов сетей проектов

klevansk48.wmf (7)

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

klevansk49.wmf (8)

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

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

klevansk50.wmf (9)

Прямое многокритериальное ранжирование векторов (9) определяет доминирующий вектор, индекс j которого определяет искомое начальное время включения проекта pni+1 в начальный календарный график TIni+1 = j. Если nr > 0, то переход к следующему шагу формирования начального календарного графика.

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

min(σ1, σ2, ..., σu), (10)

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

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

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

klevansk53.wmf klevansk54.wmf

klevansk55.wmf klevansk56.wmf (11)

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

klevansk57.wmf

klevansk58.wmf (12)

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

klevansk59.wmf klevansk60.wmf (13)

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

klevansk61.wmf (14)

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

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

klevansk62.wmf (15)

pic_18.tif

Рис. 1. Начальный календарный график

pic_19.tif

Рис. 2. Оптимизированный календарный график

Прямое многокритериальное ранжирование векторов (15) определяет доминирующий вектор, индекс j которого определяет начальное время TIni+1 = j для перестановки проекта pni+1 в календарном графике. Если nr > 0, то переход к следующему шагу оптимизации.

Результаты исследования и их обсуждение

Для численных экспериментов использовалось тестовое задание, включающее I = 15 проектов, случайно выбранных из библиотеки тестовых задач PSPLib [12]. Проекты включают по klevansk63.wmf работ, и им требуется 4 типа ресурсов (u = 4).

На рис. 1 представлены результаты формирования начального календарного графика мультипроектного планирования при принятых агрегациях проектов [4]. В верхней части рисунка представлена диаграмма Гантта для 15 проектов тестового задания при принятом интервале расписания в 100 тактов планирования. В нижней части показаны диаграммы потребления (синий цвет) и выделения (голубой цвет) каждого из четырех ресурсов на каждом такте планирования. Цифрами в диаграммах ресурсов представлены максимальные значения тактового потребления и выделения ресурса. Третья цифра показывает среднеквадратичное отклонение от среднего значения в процентах.

Анализ начального (рис. 1) и оптимизированного (рис. 2) календарных графиков:

1) уменьшение значений среднеквадратичных отклонений в оптимизированном календарном графике;

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

3) повышение уровня потребления ресурсов у границ интервала расписания и, как следствие, смещение большинства проектов (рис. 2) к границам интервала расписания.

Таким образом, представлены следующие результаты:

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