А.В. Катаев Т.М. Катаева
Управление проектами на базе динамической сети партнеров. Монография.

3.4. Оптимальное назначение исполнителей с ограничениями на предшествование работ

Приведенные в предыдущих пунктах модели не учитывали зависимость во времени между выполняемыми работами, которая характерна для управления проектами. Большинство математических моделей управления проектом строятся, исходя из известных (вероятных или предполагаемых) временных характеристик работ и отношений предшествования между работами.
Рассмотрим одну из задач выбора исполнителей работ проекта с учетом ограничений на предшествование работ.
Постановка задачи. Пусть имеется некий проект, состоящий из m взаимосвязанных работ. Взаимосвязь работ представлена в виде сетевой модели. На выполнение работ претендуют n различных исполнителей, каждый из которых обязуется в полном объеме выполнить отдельные работы за определенное им время t и со стоимостью с. Требуется назначить исполнителей на работы таким образом, чтобы минимизировать суммарную стоимость выполнения проекта и уложиться в выделенный на проект срок T.
В данной задаче, кроме подбора комбинаций расстановки исполнителей на работы, требуется учесть ограничение на время выполнения всего проекта с учетом ограничений предшествования. Далее приведены основные подходы к математическому моделированию и  решению данной задачи.

Сетевая модель и критический путь
Как известно, сетевая модель в терминах сетевого планирования и управления (СПУ) представляет  собой ориентированный граф, где дугами отображаются работы сети, а вершины показывают события,  когда завершаются одни работы и (или) начинаются другие[1]. Некоторые работы в проекте могут выполняться одновременно, из чего следует, что в данной выше постановке задачи предполагается нахождение такого распределения исполнителей по работам, при котором длительность критического пути  в сетевой модели будет минимальна и будут соблюдены ресурсные ограничения.
Критический путь (КП), представляющий собой самую продолжительную по времени непрерывную последовательность работ и событий от начального до конечного события проекта,  может изменяться и по длительности, и по составу работ в зависимости от назначаемых исполнителей. Следовательно, для нахождения, расчета и минимизации КП необходимо описать математически взаимосвязи работ и событий проекта, т.е. учесть конфигурацию (топологию) сетевой модели.
Далее будем использовать метод критического пути (Critical Path Method, CPM)[2], используемый также в системах PERT-Time и PERT-Cost, и обозначим основные временные параметры сетевой модели на примере сетевого графика условного проекта (рис.3.3).

Рис.3.3.Пример сетевого графика

На рис. 3.3 введены следующие обозначения:
- Ts – ранний срок наступления события s. Это время, которое необходимо для выполнения всех работ, предшествующих данному событию. Tрs равняется наибольшей из продолжительности путей, предшествующих данному событию.
- T’s – поздний срок наступления события s. Это такое время наступления события s, превышение которого вызовет аналогичную задержку наступления завершающего события сети.
- Rs – резерв времени наступления события s. Это такой промежуток времени, на который может быть отсрочено наступление события s без нарушения сроков завершения проекта в целом. Rs = T’s – Ts.
- Рk,g – работа (k, g), где k – номер начального события работы, а g – номер конечного.
- tk,g – время выполнения работы Рk,g.
К важным временным параметрам работ относятся резервы времени:
- Rсk,g – свободный резерв работы, показывающий максимальное время, на которое можно увеличить продолжительность работы (k, g) или отсрочить ее начало, не меняя сроки начала последующих работ. Использование свободного резерва одной из работ не меняет величины свободных резервов остальных работ сети: Rсk,g = Tg – Tk – tk,g.
- Rпk,g – полный резерв работы показывает максимальное время, на которое может быть увеличена продолжительность работы (k, g) или отсрочено ее начало, чтобы продолжительность проходящего через нее максимального пути не превысила продолжительности критического пути: Rпk,g = T’g – Tk – tk,g.
При расчете временных параметров работ и событий предполагается, что работы начинаются сразу после окончания всех предыдущих работ, т.е. расчет происходит только на основе известных длительностей tk,g и последовательности работ. В этом случае, выразив tk,g через ранний срок наступления событий и свободный резерв, можно описать зависимости работ и событий через систему уравнений следующего вида:
Tg – Tk – Rсk,g = tk,g,  j=1,…,m,                       (3.41)
где j – порядковый номер работы Рk,g; m - количество работ в проекте.
Используя (3.41), строим следующую линейную модель математического программирования:

Целевой функцией в (3.42) является ранний срок наступления конечного события проекта, который равен длительности КП при T1 равным нулю, а неизвестными являются ранние сроки наступления событий и свободные резервы работ.
В модели (3.42)  и каждая из этих неизвестных входит только в одно уравнение вида (3.41), следовательно, при постановке задачи линейного программирования их можно исключить из модели, заменить систему уравнений (3.41) на систему неравенств:
.                     (3.44)
В (3.42) изначально T1 (время наступления начального события проекта) приравнивается нулю, однако это условие можно опустить при отсутствии дополнительных ограничений, так как по условию все значения временных параметров неотрицательные и минимизируется Th (время наступления конечного события), зависимого от T1 через систему уравнений. Другими словами, при оптимальном решении задачи в постановке (3.42) T1 и все  работ КП станут равны нулю.
Далее рассмотрим вариант модели, когда на выполнение каждой из работ претендуют разные исполнители, которые обязуются выполнить отдельные работы за различное время и стоимость. Причем на каждую работу должен быть назначен только один исполнитель, но один исполнитель может выполнять сразу несколько работ.

Математическая модель назначения исполнителей с оптимизацией проекта по стоимости и ограничением на срок окончания проекта формулируется следующим образом:
 
где неизвестными являются все , т.е. все ранние сроки наступления событий проекта, и все xi,j – выбор (назначение) исполнителя на работу (1 – назначается, 0 – нет);
- целевая функция (3.45)  – суммарная стоимость выполняемых работ;
- и  – ранние сроки наступления начального и конечного события работы соответственно;
-  – ранний срок наступления конечного (последнего) события всей сети, а h – номер этого события;
- каждой работе поставлен в соответствие индекс j, где  а m – количество работ;
-  – время выполнения j-й работы i-м исполнителем, где  а n – количество исполнителей.
-  – стоимость выполнения j-й работы i-м исполнителем;
- T – время, к которому все работы проекта должны завершиться.
Группа ограничений (3.46) в соответствии с методом критического пути (Critical Path Method[3]) задает порядок выполнения работ, точнее, временную зависимость событий и работ. В отличие от моделей, где время выполнения каждой работы  известно заранее,  в модели (3.45) – (3.50) длительность выполнения работы зависит от назначаемого исполнителя при выполнении условий (3.47):

Еще одним критерием оптимальности может служить количество задействованных в проекте исполнителей. При этом в зависимости от установок менеджера проводится как минимизация, так и максимизация числа участвующих в проекте исполнителей. Формально в модели (3.45) – (3.50) количество назначенных на работы участников можно получить следующим образом:
.                          (3.53)
Использование же выражения (3.53) в качестве целевой функции не позволяет найти оптимальное решение методами линейного программирования, однако можно линеаризовать модель, введя дополнительные переменные и ограничения (см. п.3.3).
При многокритериальной оптимизации  можно применить ряд методов, включая:
- ранжирование множества критериев и последовательная оптимизация по каждому из них;
- оптимизация одного критерия, а остальные критерии выступают в роли дополнительных ограничений;
- сведение многих критериев к одному путем введения весовых коэффициентов важности для каждого критерия и нормализации векторного критерия;
- минимизация максимальных отклонений от наилучших значений по всем критериям.
К примеру, модель с минимизацией по двум критериям, в качестве которых выступают  стоимость  (матрица С) и время выполнения работы  (матрица T), можно решить, сведя  два критерия к одному  суперкритерию . Для этого требуется значения критериев привести к безразмерному виду (удельные значения) и произвести свертку с учетом важности каждого критерия (взвешенные значения). В итоге получим матрицу (Y) суперкритериев , которые можно получить, например, с помощью аддитивной взвешенной модели по формуле
 
В данном случае при отсутствии ограничений максимальный бюджет или длительность проекта алгоритм поиска оптимального решения сводится к нахождению минимальных  по каждой работе без применения методов линейного программирования. Если же названные ограничения присутствуют, то следует пользоваться другими алгоритмами.
Расширенные постановки задачи могут включать ряд дополнительных условий:
1) доступный период времени, когда исполнитель готов выполнить работу;
2) запреты назначения того или иного исполнителя на конкретную работу, выдвигаемые со стороны менеджера проекта;
3) предпочтение выбора определенного исполнителя для выполнения конкретных работ;
4) «связка» работ при назначении, когда требуется отдать несколько определенных работ «в одни руки»;
5) невозможность параллельного выполнения работ исполнителем;
6) ограничения по компетенции и надежности исполнителей;
7) учет конфликтов между потенциальными партнерами;
8) учет прежнего опыта сотрудничества партнеров друг с другом.
Ниже подробней описана сущность перечисленных выше условий и приведены математические формулировки.
1. Доступный период времени.
В ряде случаев исполнители могут начать и закончить работы только в определенные периоды времени, когда у них имеются требуемые для этого ресурсы. Для учета этого ограничения необходима информация от каждого исполнителя по возможным срокам начала  и окончания  работы, т.е. период времени, когда исполнитель готов выполнить работу. Тогда ограничения по каждой j-й работе имеют вид

Если у какого-либо исполнителя таких периодов несколько, тогда рекомендуется добавлять «новых» исполнителей под каждый интервал, что позволит учесть и возможно разные ti,j и ci,j для разных периодов времени. Если же конкретный исполнитель не выдвигает ограничений на период времени, тогда следует bi,j задать нулевое значение, а ei,j – заведомо большое значение. Ограничения (3.56) и (3.57) не описывают случай, когда требуется при назначении исполнителя учесть использование в будущем возможных свободных или полных резервов времени у работ[5].
2.Запреты назначения. В случаях, когда исполнитель не претендует на выполнение отдельных работ или есть запрет назначения со стороны менеджера проекта, указывается, что xi,j = 0. Запреты могут быть поставлены и путем присвоения ti,j заведомо больших значений (больше T). Для уменьшения же размерности запреты (переменные) могут быть просто исключены из модели.
3. Предпочтение выбора. В модель прямым образом могут быть добавлены предпочтения выполнения работ i-м исполнителем j-й работы, т.е. для отдельных работ можно указать, что xi,j = 1. Таким способом работа закрепляется сразу за определенным исполнителем. Это требуется в случаях, когда на некоторые работы проекта уже выбран исполнитель или работа уже выполнена, однако требуется провести частичную (фрагментарную) оптимизацию проекта.
4. «Связка» работ. Предположим в проекте есть работы, которые требуется отдать «в одни руки». Например, есть две работы «разработка технического задания…» и «контроль результата и тестирование продукта…». Менеджер проекта считает, что обе работы должен выполнять исключительно один исполнитель, а не разные. При этом если одна работа начинается сразу после окончания другой, а связывающее их событие не имеет других дуг, то существует возможность объединения их в сетевой модели в виде одной работы. В противном случае назначения должны быть попарно равны для каждого исполнителя, что может быть отражено в модели системой уравнений следующего вида:
                             (3.58)
где w и u – номера работ, которые должны быть отданы «в одни руки».
5. Невозможность параллельного выполнения работ исполнителем. Существует определенная трудность учета в линейной модели случаев, когда одна работа не должна пересекаться по времени с другой, что было отмечено исследователями еще в период осуществления попыток описать классическую задачу теории расписаний – задачу Беллмана-Джонсона о станках[6] в виде модели линейного программирования.
Основная проблема здесь заключается в том, что требуется задать альтернативное ограничение: либо работа A начинается после окончания B, либо B – после A. Один из успешных приемов обработки альтернативных условий заключается в следующем[7]: для каждой пары работ A и B вводится целочисленная переменная , принимающая значение 1, когда A предшествует B, или 0, когда B предшествует A. Тогда альтернативное условие записывается в виде двух неравенств:

где D – номер исполнителя, выдвигающего условие на не пересечение во времени работ A и B при его назначении на обе работы.
Ограничения вида (3.61) корректны и в случае, когда исполнитель D не назначается на работы A и (или) B.
6. Ограничения по компетенции и надежности исполнителей. В ряде случаев требуется произвести назначения таким образом, чтобы максимизировать минимальную компетенцию среди назначаемой группы исполнителей (см. «задача о назначениях в узких местах» в п.3.2). Другими словами, на практике требуется избежать ситуации, связанной с назначением на выполнение некоторых работ исполнителей с низкими значениями названных показателей.
Одним из способов решения данной проблемы является исключение на этапе формирования математической модели исполнителей с определенным уровнем компетенции, который ниже заданного минимального порогового значения. Другой способ заключается в постепенном увеличении ограничения на минимальную компетенцию. В этом случае после нахождения решения без ограничений на компетентность ищется минимальная компетенция из назначений «исполнитель-работа», после чего устанавливаются определенные запреты (или исключаются соответствующие неизвестные) для всех пар «исполнитель-работа», где компетенции ниже или равны найденной минимальной. После успешного нахождения новых решений о назначениях данную процедуру можно повторять многократно, до получения удовлетворяющего менеджера  результата.
7. Учет конфликтов между потенциальными партнерами. В ряде случаев, чтобы избежать множества проблем при реализации проекта, требуется не допустить вхождения в одну группу (команду проекта) конфликтующих агентов (например, прямых конкурентов на определенных рынках). Способы задания подобных ограничений приведены п.3.1.
8. Учет прежнего опыта сотрудничества партнеров друг с другом. Подбор в команду проекта агентов, которые имели положительный опыт сотрудничества друг с другом, может способствовать эффективному выполнению проекта в целом. К примеру, целевой функцией может выступать количество «связанных пар» партнеров (см. п.3.1).