Задача распределения функций.
Начнем с транспортной задачи, в которой имеется граф, вершины которого разбиты на две группы - n агентов и m работ (функций).
Для агентов заданы количества времени, которые они могут затратить на работу в команде - ai, i = 1, n, для работ - продолжительности их реализации - bj, j = 1, m . Также известны
затраты Sj на выполнение 7-ым агентом j-ой работы в течение единицы времени .
nm
Пусть задача является замкнутой, то есть У at = У bj - сум-
7=1 j=1
марный временной ресурс агентов равен суммарной продолжи-тельности работ (вводя фиктивного агента или фиктивную работу любую незамкнутую задачу можно свести к замкнутой). Требуется определить распределение агентов по работам (функциям), минимизирующее суммарные затраты.
Формально транспортную задачу можно записать в виде:
n m
УУx7j s.. ® min
7=1 j=1 iX'j 1 m
У x, = a, i = 1, n,
j=1
txy = ь, j = 1m.
7=1
Условие (8) означает, что каждый агент «загружен» полностью, условие (9) - что все работы выполнены. Алгоритмы решения транспортной задачи описаны в [7, 9, 15].
Частным случаем транспортной задачи является задача о назначении (в узком смысле), заключающаяся в следующем: имеются n агентов, которые могут выполнять различные работы (реализо- вывать различные функции, занимать различные должности), число работ равно числу работников (введя фиктивные должности и/или фиктивных агентов, всегда можно незамкнутую задачу привести к рассматриваемой замкнутой форме). Известны затраты Sj на назначение i-го агента на j-ю должность (например, минимальная зарплата, за которую он согласится работать на этой должности).
Требуется найти назначение работников на должности (каждого работника на одну и только одну должность), минимизирующее суммарные затраты (если S, интерпретируется как эффективность от работы i-го работника на j-ой должности, то опти-мальное назначение должно максимизировать суммарную эффективность).
Формально задачу о назначении (см. также примеры в разделе 4) можно записать в виде (ср. с (7)-(9)):
n n
YYxii L ® min
? Xj = 1, i = 1Й,
1=1
X Xj = 1, j = 1n .
i =1
Методы решения задачи о назначении (10)-(12) описаны в [7, 9, 15]. Содержательной интерпретацией этой задачи в терминах менеджмента [52, 123] или управления проектами [12, 73] является нахождение оптимальной матрицы ответственности.
Транспортная задача и задача о назначении являются хресто-матийными задачами исследования операций и имеют множество обобщений (учет ограничений на совместимость работ, выполняемых одним агентом, ограничений на последовательность выполнения работ, многокритериальности и т.п. - см. обзоры в [15, 20, 82]), которые целесообразно использовать при решении задач распределения функций между членами команды. Кроме того, для таких задач может оказаться адекватным и аппарат теории массового обслуживания [36, 39], в случае, если набор функций, реализуемых командой, меняется во времени по известным (статистически описываемым) законам.