Двойственность в задаче о назначении исполнителей проекта

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

Математика

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

Как следует из формулировки проблемы, речь идёт о решении двухэтапной задачи – формирование и предварительная оценка списка потенциальных исполнителей и назначение конкретного исполнителя каждой работы. Решению этих подзадач посвящено достаточно много публикаций [5–14]. Обширный обзор соответствующих моделей и методов их решения представлен в монографии [5]. Для решения задачи первого этапа в последнее время приобрели популярность генетические алгоритмы [6–8]. Что касается решения задачи второго этапа, то предлагаются различные методы. Данная задача является обобщением классической задачи о назначениях и отличается от неё наличием дополнительных допущений и ограничений. Традиционный подход основан на сведении данной задачи к задаче смешанного целочисленного математического программирования [9], для решения которых в настоящее время существует широкий спектр программных средств, включая расширение Solver в MS Excel, LPSolve c IDE и CPLEX Optimizer. Недостаток такого подхода состоит в ограниченной размерности решаемых задач. Также предлагаются эвристические методы решения типа локального поиска и жадного алгоритма [10–13]. В [14] предложен алгоритм, основанный на сведении задачи второго этапа к обычной задаче о назначениях путём наложения системы штрафов за нарушения дополнительных ограничений.

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

Методы и материалы

Пусть сформирован сетевой план проекта в виде графа G = (V , E ), | V | = n , | E | = m , отражающего отношения взаимосвязи между работами. Каждая дуга e е E представляет собой определённую работу в рамках проекта. Пусть s – исток сети, f – ее сток.

Сделаем следующие допущения:

• –    каждая работа может быть выполнена каждым работником с сопоставимой эффективностью, иными словами, характер выполняемых работ более или менее однороден;

• –    не предполагается совмещение, т. е. выполнение нескольких работ одним исполнителем.

Обозначим:

• -    J = {1,2,..., m } - множество исполнителей; без ограничения общности можно считать, что число работ и исполнителей совпадает; в противном случае несложно провести дробление работ на более мелкие или ввести фиктивных исполнителей;

• –    T_ij – время, которое требуется j -му исполнителю для выполнения i -й работы; при фиксированном назначении T_ij можно интерпретировать как вес (длину) i -й дуги графа.

Варьируемыми параметрами математической модели являются величины Z ^ е {0,1} - распределение операций по исполнителям: Z j = 1, если i -я операция поручена j -му исполнителю, Z ij = 0 в противном случае. При этом должны выполняться следующие ограничения:

каждая работа выполняется лишь одним исполнителем:

X Z j = 1 V i е E ;                                     (1)

j е J каждому исполнителю поручается лишь одна работа:

X Z ij = 1 V j е J .                                       (2)

i е E

В публикациях [5–14] предложено достаточно много моделей реализации проекта с различными целевыми функциями и ограничениями. Наиболее распространенным способом синтеза оптимального управления, используемым в современных системах управления проектами, является Program (Project) Evaluation and Review Technique (сокращённо PERT) – метод оценки и ана-

Бугаев Ю.В., Калач А.В.,                                             Двойственность в задаче

Никитин Б.Е., Шурупова И.Ю.                             о назначении исполнителей проекта лиза проектов. Ключевой частью PERT является метод критического пути в сетевом графике (сетевой диаграмме PERT). Остановимся на постановке задачи с минимизацией критического пути, т. е. с минимизацией времени исполнения проекта.

Связь между длиной критического пути и введенными выше величинами можно описать следующим образом. Пусть Ek, k e{1,...,N} - множество дуг, составляющих к -й по порядку путь от источника к стоку. Если распределение работ зафиксировано в элементах матрицы Z , то длина k -го пути вычисляется по формуле dk = I I TjZj - ie Ek j e J

Введем вспомогательную переменную t , значение которой равно длине критического пути. В соответствии с определением t для нее должны выполняться условия

I I T j Z j <  t V к e {1,2,.., N } ,                          (3)

ie Ek j eJ t ^ min.                                      (4)

Поскольку Z j e {0,1}, а переменная t произвольна, задача определения исполнителей работ свелась к задаче частичного булевого программирования (1)–(4). Как известно, эти задачи в общем случае являются NP -трудными, поэтому нужно подобрать соответствующий метод решения.

Сложность решения модели (1)–(4) в частности состоит из необходимости перебора всех путей в сетевом графе. Их количество N сильно варьируется в разных задачах и в графах даже средней размерности может достигать весьма больших значений. Алгоритмически же задача не представляет сложности, наиболее простой метод её решения – алгоритм поиска с возвратом ( back-tracking ). Часто он реализуется в рекурсивной форме.

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

Произвольная оптимизационная задача сводится к двойственной следующим образом [15]. Пусть поставлена задача min(^(x)| x e S),(5)

hk (x) < 0, k e{1,..., N}.(6)

Функция Лагранжа для неё имеет следующий вид:

N

L(x, 2) = ^(x) +1Zkhk (x), x e S, 2k > 0.(7)

k = 1

По определению задача, двойственная к (5)–(6), записывается как max min L(x, 2) .(8)

• 2 > 0 x e S

Функцию

^(2) = min L(x, 2), 2k > 0 xeS называют двойственной функцией для задачи (5)–(6), и двойственную задачу (8) можно представить в виде max ®(2).

2 > 0

Конкретно для задачи (1)–(4) функция Лагранжа (7) выглядит так:

L ( Z , t , 2 ) = t + 1 2 k ( ll TZ — t k = 1 ^ i e E k j = 1              ) ’

Z e S , 2 _k >  0.

Область допустимых решений S определяется ограничениями (1)-(2) и условием Z j e {0,1}, t произвольно.

Математика

Преобразуем формулу (9). Для этого введём матрицу M размера (N х m), элементы которой зададим следующим образом: Mki = 1, если i -е ребро содержится в к -м пути, Mki = 0 в противном случае. Тогда длина k -го пути определится по формуле mm dk = Z Mki Z TijZij.

i=1

Подставим это выражение в формулу (9) на место первоначального выражения для d_k :

N   ( mm

A

— ^£

L(Z,£,2) = £ + Z^k ZMki ZTjZj k=1    I i=1

Поменяем порядок суммирования:

(   N^

L ( Z , £ , 2 ) = £ 1 - Z 2 k

\k

mNm

+ Z Z 2 k M ki Z T ij Z j .

i=1 k=1

Обозначим

В итоге получим:

L ( Z , £ , 2 ) = £

N

A- = Z2kMki • k=1

(    N   Л

¹ - Z ² k

<    k = 1    7

mm

+ Z Z A i T j Z j , i = 1 j = 1

( Z , £ ) e S , 2 k >  0.

Возможны три случая для значений 2k .

N

• 1-    Z 2 k >  1 • Поскольку £ не ограничено, то минимум L ( Z , £ , 2 ) при произвольном фиксиро- k = 1

ванном 2 достигается при £ = да . При этом ^ ( 2 ) = -да . Данное решение двойственной задачи, очевидно, не имеет практического значения, этот случай мы рассматривать не будем.

N

• 2-    Z 2 k <  1 • Аналогичная ситуация, только минимум L ( Z , £ , 2 ) достигается при £ = -да .

k = 1

N

• 3-    Z 2 k = 1- В этом случае значение функции (11) не зависит от £ и она примет вид k = 1

mmN

L(Z, a) = Z Z i! ' Z = Z2kdk , Z e S, 2 > 0,(12)

i =1 j=1

а k -я координата ее градиента равна mm g (2u) k =Z Mki Z TijZj - £ = dk - £- i =1

Выражение (12) представляет собой целевую функцию классической задачи о назначениях, ценовая матрица которой образована из матрицы T задачи (1)–(4) умножением каждой её i -й строки на весовой коэффициент a , определяемый по формуле (10) при условии

N

Z 2 k = 1-                                      (13)

k = 1

Известна тесная связь между прямой и двойственной задачами. Так, при определенных условиях [15], например, для задачи линейного программирования (ЛП), оптимальные значения целевых функций прямой и двойственной задач совпадают. При несовпадении говорят, что имеет место разрыв двойственности. Опыт решения тестовых примеров показал, что в общем случае для задачи (1)–(4) разрыв двойственности имеет место. Данный факт не позволяет использовать

Бугаев Ю.В., Калач А.В.,                                             Двойственность в задаче

Никитин Б.Е., Шурупова И.Ю.                             о назначении исполнителей проекта двойственный метод для поиска точного решения задачи. Однако он вполне пригоден для построения приближенного алгоритма.

Решение двойственной задачи сводится к непосредственному поиску максимума функции Лагранжа. К сожалению, по известному её свойству [15] разрыв двойственности влечёт отсутствие седловой точки, из чего, в свою очередь, следует недифференцируемость функции Лагранжа в оптимальной точке. Это означает, что для решения двойственной задачи следует привлекать специальные алгоритмы [15–22], приспособленные к оптимизации вогнутых (выпуклых вверх) функций, которые не всюду дифференцируемы. Помимо классических лагранжевых методов [15–17] можно отметить семейства субградиентных методов с растяжением пространства, которые известны как r-алгоритмы Н.З. Шора [21, 22]. Они имеют ускоренную сходимость при минимизации выпуклых функций с овражной структурой поверхностей уровня, а также хорошо зарекомендовали себя при минимизации негладких выпуклых функций. Тем не менее есть основания полагать, что алгоритмы, в основе которых положена идея движения по гребню минимизируемой негладкой функции, выдвинутая и обоснованная в монографии В.Ф. Демьянова и В.Л. Малоземова [23], вполне конкурентоспособна на фоне методов с переменной метрики.

В общем случае субградиентный алгоритм с ограничениями состоит из следующих шагов [15].

Обозначим Л с R N - множество весов ^, удовлетворяющих условию (13).

• 1.    Задать начальную точку Х0 , положить номер итерации и = 0 .

• 2.    На u -м шаге итерации мы находимся в точке λ ^u . Вычислить величину

• 3.    Вычислить вектор д(Х ^и ) - субградиент функции ® (Х) в точке Х ^и .

• 4.    Определить Х u ^{+ 1} равенством

• 5.    Если выполнен тест остановки, то СТОП. Иначе положить и = и + 1 и вернуться к пункту 2.

ш(Х^и ) = min L (х,Х ^и ) .

X G S

Х u ^{+ 1} = Pr Г Х u + p g(X u ) 1 ,                                  (14)

R + P| Л1-                 J где pu - шаг перемещения на и -й итерации.

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

В ходе поиска оптимума возможно получение точки разрыва градиента. В данном случае разрыв обусловлен тем, что задача о назначениях, а значит, и задача (3)–(4) может иметь несколько решений с одинаковыми значениями целевой функции, но с разными наборами протяженностей путей { d_k } , которые, в свою очередь, определяют векторы-градиенты функции (12). Отсюда возникают две подзадачи:

• –    поиск различных решений задачи (3)–(4), порождающих при фиксированном λ одинаковые значения функции Лагранжа;

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

Изложим способ нахождения соответствующего вектора p (λ ^u ) – проекции субградиента на множество R ⁺ П Л .

Пусть λ ^u – точка разрыва градиента и { Z (λ ^u )} – набор всех решений задачи минимизации функции Лагранжа (12), соответствующих Х u . Обозначим A - матрица ( m х t ), столбцами которой являются градиенты, образованные решениями из { Z (λ ^u )} . Потребуем, чтобы вектор

Математика

p(λu) образовывал максимально острый угол со всеми столбцами A . Точнее, чтобы выполнялось условие

τ → max, A^T p (λ ^u ) ≥ τ e_t .

Здесь e_t – столбец из t единиц.

Помимо этого, вектор p (λ ^u ) должен удовлетворять следующим условиям.

• 1.    Поскольку при достаточно малой величине шага ρ вдоль направления p (λ ^u ) элементы матрицы Z не изменятся, а условие (13) для новых значений λ ^{u + 1} должно остаться в силе, то для его соблюдения необходимо, чтобы сумма элементов p ( λ ^u ) была равна 0. Для этого введем произвольную матрицу H , ( m × ( m - 1)) ранга m - 1 , сумма элементов каждого столбца которой равна 0. Сделаем замену переменных, положив p = Hx , где x – вектор с m - 1 координатами, и вместо поиска p будем подбирать x . Нетрудно доказать, что при такой подстановке требуемое условие для p будет выполнено.

• 2.    В процессе поиска максимума L некоторые λ _k могут обратиться в 0. В этом случае соответствующие значения p_k должны быть неотрицательны. Обозначим множество номеров таких p_k через Q , | Q | = s . Введём матрицу D , ( m × s ) у которой в r -м столбце, r = 1, 2,..., s , отличен от нуля только элемент D_{k , r} , k ∈ Q . Тогда соответствующее условие можно записать как

D^TH x ≥ 0.

Кроме того, ограничим норму вектора x условием x^Tx ≤ 1 , чтобы не получить вектор бесконечной длины.

Окончательно получаем, что для обеспечения максимального локального роста функции Лагранжа необходимо решить задачу условной оптимизации

τ → max; A^THx ≥ τ e; x^Tx ≤ 1; D^THx ≥ 0.                      (15)

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

Можно предложить два варианта такой замены:

• x^T x → min; A^T Hx ≥ / e ; D^THx ≥ 0                       (16)

либо

• x^T x - )τ → min; A^THx ≥ τ e ; D^THx ≥ 0.                       (17)

Здесь у >  0– некоторое большое число.

Как было сказано выше, для определения направления поиска p ( λ ^u ) в точке разрыва градиента необходимо решить задачу поиска различных решений задачи (3)–(4), порождающих при фиксированном λ одинаковые значения функции Лагранжа. В общем случае это потребует определения всех возможных решений задачи о назначениях. Соответствующий метод предложен авторами в работе [24]. При этом использован комбинированный алгоритм, сочетающий ускоренный вариант модифицированного симплекс-метода и алгоритм поиска в ширину на графе.

Очевидно, что трудоемкость каждой итерации изложенного метода решения задачи (3)–(4) намного выше, чем, например, классического варианта алгоритма Утзавы [15], в котором направление поиска совпадает с направлением градиента. Однако такой вариант применим лишь при отсутствии разрыва градиента и выполнении условия λ _k >  0, k = 1,..., m , в противном случае траектория поиска становится зигзагообразной, сходной с траекторией оптимизации «овражных» функций, что, в конечном счете, может привести к зацикливанию. Соответствующие примеры приведены в [22].

Бугаев Ю.В., Калач А.В.,                                             Двойственность в задаче

Никитин Б.Е., Шурупова И.Ю.                             о назначении исполнителей проекта

Остается рассмотреть вопрос о выборе длины шага поиска р. Предлагается определять его из условия минимума функции Лагранжа в направлении p(λu) . Поскольку данная целевая функция кусочно-линейная, то весьма эффективным будет метод касательных. В [22] предложена формула для определения производной по направлению p в точке разрыва градиента целевой дL функции. Применительно к функции (12) формула имеет вид — = min qj, где q = AT p .

^д P    j=1t

В заключение рассмотрим пример. Пусть граф G имеет 4 вершины и 5 дуг. Элементы матрицы T и дуги графа заданы в таблице.

Дуги		Длительности работ
Начальная вершина	Конечная вершина
1	2	10	5	9	18	11
2	4	13	19	12	6	14
1	4	19	2	20	4	19
1	3	18	9	12	17	15
3	4	11	6	14	19	10

Данный граф имеет, очевидно, три пути из истока (вершина 1) к стоку (вершина 4): путь № 1: 1 – 2 – 4 (дуги 1 и 2); путь № 2: 1 – 4 (дуга 3); путь № 3: 1 – 3 – 4 (дуги 4 и 5).

Зададим начальные значения λ0

1 T

= 3 • (1,1, 1) . Тогда решением задачи минимизации L по Zij будут следующие назначения:

Z⁰⁾ =

( 1

0 ^

.

Кратко запишем данное назначение, указав порядковые номера исполнителей для 1-й, 2-й и т. д. задач в виде (1, 4, 2, 3, 5). Соответственно, длины путей составят (16, 2, 22). Отсюда

® ( 2⁰ ) = 13,3333.

Направление

поиска

определяется

вектором

p ( 2⁰ ) = (0,1837, - 0,7808, 0,5971) ^T .

Минимум ю ( 2 ) в направлении p ( 2 0 ) достигается при р ⁰ = 0,2767, следующее приближение 2¹ = (0,3842, 0,1173, 0,4985) ^T , ю ( 2¹ ) = 17,3489 .

Весовому вектору λ1 соответствуют два назначения (1, 4, 2, 3, 5) и (1, 4, 5, 3, 2) со значениями длин путей (16, 2, 22) и (16, 19, 18) соответственно. Следовательно,

' 16

16 ^

¹⁸ >

A Р) = ²

.

^ 22

Отсюда следующее направление p ( 2 1 ) = ( - 0,7689, 0,1465, 0,6224) ^T .

Новые значения весов будут Л² = (0,2632,0,1404,0,5965) ^T . Соответствующие назначения: (1, 4, 2, 3, 5) с длинами путей (16, 2, 22); (5, 1, 4, 3, 2) и (1, 5, 4, 3, 2) с одинаковыми длинами (24,

• 4,    18) и (1, 4, 5, 3, 2) с длинами (16, 19, 18). ® ( 2 1 ) = 17,6140 . Следовательно,

  Математика

  
  

( 16

A a²) = ²

V 22

24 16 '

4 19

18 18 J

Направление поиска p ( A ²) = ( - 0,5245, - 0,2796, 0,8042) T , ^ 3 = (0,0,1) T , L (Z⁽³⁾,^ 3 ) = 18. В точке

λ³ имеем 6 назначений, 5 различных возможных путей. Матрицы A (λ³) и D имеют вид:

(31  32  17  2416

A(^3) = 19  19  19  4  19 , v18  18  18  1818

v ⁰

0 3

oj

.

Задача (15) при таких данных имеет нулевое решение p (л3 ) = (0, 0, 0)T, следовательно, до- пустимых направлений нет, найдено оптимальное значение L = 18.

Наилучшие из полученных назначений – (1, 4, 5, 3, 2), (5, 4, 1, 3, 2) и (1, 4, 5, 3, 2) с протяженностью критического пути 19. Их можно приять за решение задачи. Разрыв двойственности составит А = 1.

Проверка полным перебором показала, что минимальная длина критического пути действительно 19 и существует еще одно оптимальное назначение (3, 4, 1, 2, 5).

Разработанный алгоритм был реализован нами в системе MATLAB для решения тестовых задач. Сравнение значения функции Лагранжа в найденных решениях с полученной длиной критического пути указывает на близость полученного решения к оптимальному. Для сравнения была предпринята попытка решить тестовые задачи посредством программы bintprog системы MATLAB и пакета «Поиск решения» системы Excel.

Соответствующая задача булевого программирования содержит m ² переменных и при m >  20 решение этим программным обеспечением уже не находилось.

Заключение

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

К недостаткам предложенного подхода следует отнести необходимость перебора всех путей в сетевом графе, что в общем случае приводит к задаче высокой вычислительной сложности. Однако в постановке задачи предполагали, что характер выполняемых работ более или менее однороден, а значит, их перечень не может быть слишком большим, поскольку в больших и сложных проектах виды работ обычно весьма разнообразны. Следовательно, не стоит опасаться, что в графах реальных проектов список путей будет неподъёмным.