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

АЛГОРИТМЫ ФОРМИРОВАНИЯ РАСПИСАНИЙ ДЛЯ СЕТЕВЫХ СТРУКТУР ЗАЯВОК/РАБОТ

Клеванский Н.Н. 1 Красников А.А. 1
1 ФГБОУ ВО «Саратовский государственный аграрный университет имени Н.И. Вавилова»
Представлены методы решения второй задачи мультипроектного планирования – формирования календарных графиков. Двухэтапный вычислительный процесс реализован в среде СУБД и включает формирование начального календарного плана на первом этапе и его последующую оптимизацию на втором этапе. Каждый этап цикличен, так как содержит две «жадные» эвристики. В каждом шаге цикла результат работы первой эвристики используется второй эвристикой. Каждая эвристика осуществляет выбор наиболее приемлемого критерия загруженности или равномерности с принятием некоторых решений. В операциях выбора использованы различные методы ранжирования теории принятия решений. В формировании календарных графиков использованы «жадные» алгоритмы и концепции равномерности и загруженности. Осуществлены формализация и постановка задач обоих этапов. Представлены алгоритмы решения задач обоих этапов. Рассмотрен численный пример формирования календарного графика мультипроектного планирования.
мультипроектное планирование
агрегация проекта
заявка
действие
«жадный» алгоритм
распределение ресурсов
среднеквадратичное отклонение
многокритериальное ранжирование
1. Баркалов П.С., Буркова И.В., Глаголев А.В. и др. Задачи распределения ресурсов в управлении проектами. – М.: ИПУ РАН, 2002. – 65 с.
2. Бурков В.Н., Квон О.Ф., Цитович Л.А. Модели и методы мультипроектного управления. – М.: (Препринт / ИПУ РАН), 1997. – 62 с.
3. Клеванский Н.Н. Основные концепции реализации задач формирования расписаний // Вестник Московского университета имени С.Ю. Витте. Образовательные ресурсы и технологии. – М.: 2014. – № 2 (5). С. 9–21.
4. Клеванский Н.Н., Красников А.А. Алгоритмы агрегирования проектов // Фундаментальные исследования. – 2016. – № 2–3. С. 482–486.
5. Клеванский Н.Н., Красников А.А. Формирование календарных графиков мультипроектного планирования // Труды XII Всероссийского совещания по проблемам управления – ВСПУ-2014. Москва 16–19 июня 2014 г. – С. 8051–8059.
6. Клеванский Н.Н., Михайлова М.М. Подходы к формированию расписаний для иерархий заявок // Доклады Академии Военных наук. – 2012. – № 5(54). – С. 77–82.
7. Кочетов Ю.А.. Столяр А.А. Новые жадные эвристики для задачи календарного планирования с ограниченными ресурсами // Дискретный анализ и исследование операций. – Новосибирск, 2005. – Серия 2. Т. 12, № 1. – С. 12–36.
8. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. – М.: Физический факультет МГУ, 2011. – 222 с.
9. Подиновский В.В. Анализ задач многокритериального выбора методами теории важности критериев при помощи компьютерных систем поддержки принятия решений // Известия РАН. Теория и системы управления. – 2008. – № 2. – С. 64–68.
10. Сафронов В.В., Ведерников Ю.В. Характеристика метода «жесткого» ранжирования // Информационные технологии. – 2007. – № S11. – С. 17–21.
11. 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.
12. Kolish R., Sprecher A. PSPLIB – A project scheduling library // European Journal of Operational Research. – 1996. – Vol. 96. – P. 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) к границам интервала расписания.

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

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

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

Клеванский Н.Н., Красников А.А. АЛГОРИТМЫ ФОРМИРОВАНИЯ РАСПИСАНИЙ ДЛЯ СЕТЕВЫХ СТРУКТУР ЗАЯВОК/РАБОТ // Фундаментальные исследования. – 2016. – № 4-3. – С. 495-500;
URL: http://fundamental-research.ru/ru/article/view?id=40204 (дата обращения: 07.05.2021).

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

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