Задача минимимизации количества исполнителей работ в проекте: математическая модель и алгоритм решения

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

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

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

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

Из постановки задачи следует, что целевой функцией является именно количество задействованных в проекте партнеров. В качестве ограничений выступает выделенный на выполнение работ бюджет и условие выполнения одной работы одним исполнителем. Неизвестные – булевы переменные, показывающие факт назначения i-го исполнителя на j-ю работу (1 – назначается, 0 – нет). Оптимальное же решение задачи представляет собой удовлетворяющий всем ограничениям план распределения работ по партнерам, при котором значение целевой функции будет минимально.

Очевидно, что без ограничения на бюджет оптимальным решением задачи является выполнение всех работ только одним (любым) исполнителем. Следовательно, лучшим значением целевой функции является 1 (нижняя граница), когда задействован только один исполнитель на всех работах, а худшим - n (верхняя граница), если потребовалось привлечь всех партнеров для выполнения работ с выделенным общим объемом финансирования. Таким образом, значение целевой функции дискретно и лежит в интервале ¹ n ] .

Задача может не иметь решения в том случае, если не существует удовлетворяющего ограничению по бюджету варианта расстановки исполнителей по работам. Условие наличия решения можно выразить следующим выражением:

m

X min ci.j - S .

J = 1     ⁱ

где:

• -    i - порядковый номер исполнителя, i 1,ⁿ ;

• -    j - порядковый номер работы, ^J = ¹ m ;

• -    m – количество работ, а n – количество исполнителей;

• -    S – бюджет;

• -    c i . ^J - стоимость выполнения j -ой работы i -ым исполнителем.

Условие (1) отражает то, что в том случае, если сумма минимальных по стоимости вариантов выполнения работ будет меньше либо равна бюджету, тогда существует хотя бы один допустимый план распределения задач по партнерам.

Математическая постановка оптимизационной задачи в виде модели целочисленного математического программирования:

n

^ min

L = X max Xi. j i=1   J nm

X i.J e { 0.1 } . i = 1. n , J = 1. m

^L                                                             (2)

где: x

• -    i . ^J - искомые неизвестные, показывающие факт назначения г -го

исполнителя на j -ю работу (1 – назначается, 0 – нет).

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

Частным случаем данной модели является задача, когда ^{c i , j} – возможность выполнения j -ой работы i -ым исполнителем (0 – может выполнить, 1 – не может выполнить), S = 0. Описанный ниже алгоритм применим и для данного случая.

Пошаговый алгоритм поиска оптимального решения

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

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

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

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

Для успешной реализации приведенного ниже алгоритма целесообразным является представление исходных данных решаемой нами задачи в виде матрицы затрат С размерностью n на m, где столбцы – основные проектные работы, строки – возможные исполнители, ^{c i , j} – затраты на выполнение j -ой работы i -ым исполнителем.

Пошаговый эвристический алгоритм нахождения оптимального решения:

Шаг 1. Основные действия:

c

• 1.    Находим сумму всех ^{i , j} по каждой строке – Di .

• 2.    Если имеются ⁱ , тогда решение найдено и на выполнение всех работ назначается исполнитель с минимальным значением ^{D i} . В противном случае переходим к действию 1.3.

• 3.    Находим значения минимальных элементов ^{i , j} по каждому столбцу и обозначим их как ^Mj . Пометим в каждом столбце все равные ^Mj элементы.

• 4.    Считаем количество помеченных элементов в каждой строке ( Ki ) и сумму этих элементов ( Zi ).

• 5.    Выбираем строку с максимальным Ki . Если таких строк несколько, то выбираем из них любую с максимальным Zi . Фиксируем назначение выбранного i -го сотрудника на работы с помеченными в i -ой же строке элементами, строку помечаем.

• 6.    Вычеркиваем столбцы, соответствующие зафиксированным назначениям. Уменьшаем бюджет на Zi . Переходим к следующему шагу.

D ≤ S

c

Шаг 2. На данном шаге аналогично предыдущему производятся те же действия только с оставшимися столбцами и уменьшенным бюджетом. Действие 3 можно опустить – его результат получен на первом шаге и не изменится в дальнейшем.

Шаг 3. Аналогичен второму шагу. Основное отличие состоит в том, что при выполнении действия 2 предпочтение отдается ^{D i} в уже помеченных строках. Другими словами, сначала ищутся минимальные значения ^{D i} меньшие либо равные остаточному бюджету среди уже назначенных ранее исполнителей, а в случае неудачного поиска – среди остальных.

Шаг 4 и далее. Аналогично шагу 3 до нахождения подходящего по бюджету значения. Максимальное количество шагов составляет ( m -1).

Численный пример постановки задачи и ее решения

Согласно приведенной выше постановке задачи имеется четыре исполнителя и пять работ, матрица затрат С приведена в таблице 1, затраты на оплату работ по проекту определены в тысячах рублей. Ограничение на бюджет S составляет 14 тыс.руб. Требуется найти минимальное количество исполнителей, задействовав которые можно выполнить все работы и уложиться в бюджет.

Таблица 1

Матрица стоимости затрат на выполнение основных работ по проекту возможными исполнителями

Возможные исполнители	Стоимость выполнения основных работ по проекту ( Pi ), тыс. руб.
	Р1	Р2	Р3	Р4	Р5
И1	5	7	9	2	2
И2	2	3	3	8	3
И3	2	6	5	5	1

И4

4

1

4

6

3

Ниже представлено решение в табличной форме по предложенному выше алгоритму.

Шаг №1

Результаты, полученные на первом шаге алгоритма, приведены в таблице 2.

Таблица 2

Вспомогательная таблица для проведения расчетов

Возможные исполнители	Стоимость выполнения основных работ по проекту ( Pi ), тыс. руб.					D, тыс. руб.	K, ед.	Z, тыс. руб.
	Р1	Р2	Р3	Р4	Р5
И1	5	7	9	2	2	25	1	2
И2	2	3	3	8	3	19	2	5
И3	2	6	5	5	1	19	2	3
И4	4	1	4	6	3	18	1	1
M, тыс. руб.	2	1	3	2	1

В таблицу 1, кроме непосредственно значений стоимости выполнения работ исполнителем, добавлены следующие столбцы:

• -    суммы элементов по каждой строке (столбец D);

• -    найденные минимальные значения элементов по каждому столбцу исходной матрицы (строка M), а соответствующие этим значениям элементы подчеркнуты;

• -    количество отмеченных подчеркиванием элементов по каждой строке (столбец K) и сумма значений этих элементов (столбец Z).

Как видно все Di > S, однако, большее количество минимальных по величине значений (К=2) имеют строки И2 и И3, при этом Z2 > Z3, в связи с чем целесообразным является для дальнейшего нахождения решения выбрать строку И2, назначив на выполнение работ Р1 и Р3 исполнителя И2.

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

Шаг №2

На данном шаге аналогично предыдущему производятся те же действия только с новой матрицей, полученной путем исключения столбцов Р1 и Р3, и с бюджетом, уменьшенным на сумму выбранных назначений (S2 = 14 – 5 = 9 тыс. руб.). Результат представлен в таблице 3.

Отметим, что в столбце D серым цветом выделены ячейки, соответствующие исполнителям, которые уже раннее были назначены нами на выполнение некоторых из основных работ по проекту.

Таблица 3

Вспомогательная таблица для проведения расчетов в рамках первой итерации

Возможные исполнители	Стоимость выполнения основных работ по проекту ( Pi ), тыс. руб.			D, тыс. руб.	K, ед.	Z, тыс. руб.
	Р2	Р4	Р5
И1	7	2	2	11	1	2
И2	3	8	3	14	0	0
И3	6	5	1	12	1	1
И4	1	6	3	10	1	1
M, тыс. руб.	1	2	1

В результате проведенных действий нами было закреплено выполнение работы Р4 за исполнителем И1. При этом сумма оставшегося после предыдущего назначения бюджета уменьшилась на величину, равную стоимости указанной работы, то есть на 2 тыс. руб.

Шаг №3

Повторяем аналогичную шагу №2 итерацию с учетом оставшегося бюджета (S3) в 7 тыс. руб.

Таблица 4

Вспомогательная таблица для проведения расчетов в рамках второй итерации

Возможные исполнители	Стоимость основных работ по проекту ( Pi ), тыс. руб.		D, тыс. руб.	K, ед.	Z, тыс. руб.
	Р2	Р5
И1	7	2	9	0	0
И2	3	3	6	0	0
И3	6	1	7	1	1
И4	1	3	4	1	1
M, тыс. руб.	1	1

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

Таким образом, в результате проведенных действий мы получили план распределения задач по партнерам (таблица 5) с двумя исполнителями, суммарными затраты на выполнение в размере 13 тыс. рублей и экономией бюджета (1 тыс. рублей). Следует заметить, что полученное решение можно улучшить по критерию минимизации затрат, перераспределив выбранных партнеров по задачам – на Р5 назначить И1, уменьшив тем самым затраты на

• 1    тыс. рублей.

Таблица 5

План распределения основных работ по проекту между возможными исполнителями

Возможные исполнители	Стоимость выполнения основных работ по проекту ( Pi ), тыс. руб.
	Р1	Р2	Р3	Р4	Р5
И1	5	7	9	2	2
И2	2	3	3	8	3
И3	2	6	5	5	1
И4	4	1	4	6	3

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

В предложенную модель в случае необходимости могут быть включены ограничения по компетенциям и надежности исполнителей. Вариант многокритериальной оптимизации проекта, учитывающий данные ограничения был подробно рассмотрен нами в раннее изданных публикациях [1, 2]. Математические модели минимизации времени выполнения проекта за счет оптимального выбора и назначения исполнителей проектных работ подробно описаны в источниках [3, 4].