带约束的多对一任务分配问题是否属于NP-hard问题？

你描述的这个带约束任务分配问题不是NP-hard问题，存在多项式时间的确定性全局最优解法。

问题约束拆解 #

先把题设的规则和约束理清楚，避免歧义：

• 基础匹配规则
  • 共N项任务、M名人员，属于多对一匹配：每名人员可以承接多项任务，每项任务只能分配给1名人员
  • 任务i分配给人员j时，获得收益为P_ij，目标是找到总收益最高的分配方案
• 附加约束
  • 全体任务被划分为m个互不重叠的子集T₁,T₂,…,T_m，对应给定正整数n₁,n₂,…,n_m
  • 要求：对任意任务分组T_i，分配到该组内任务的不同人员总数不超过n_i
    （注：如果按字面意思理解为“分配给Ti内单任务的人员数≤ni”，那由于单任务本身仅能分配给1人，只要ni≥1约束就自动成立，问题求解更简单）

多项式时间求解方法 #

你可以直接通过构造最小费用最大流模型求解，整个建模和求解过程都不涉及指数级复杂度的枚举：

1. 构造流网络的节点层级：源点 → 任务分组节点 → 人员节点 → 任务节点 → 汇点
2. 各边的容量和费用设置：
   • 源点到第k个任务分组节点的边：容量设为n_k，费用为0，这一步直接锁死每个任务组最多可用n_k个不同人员承接组内任务，完全满足约束
   • 每个任务分组节点向所有人员节点连边：容量设为不小于对应组内任务总数的数值（直接取N即可），费用为0，代表组内名额没用完时，任意人员都可以被选来承接组内任务
   • 每个人员节点向所有任务节点连边：如果任务属于该人员连通的分组，边容量设为1，费用设为-P_ij（最小费用流默认求最小值，收益取负即可转换为最小费用目标）
   • 每个任务节点向汇点连边：容量为1，费用为0，保证每个任务恰好被分配一次
3. 计算该网络从源点到汇点的最小费用最大流，流的走向对应的分配方案就是全局最优解。

整个网络的节点数、边数都随N、M、m的规模多项式增长，用常规的最小费用流算法就可以在多项式时间内算出结果，不需要遍历所有可能的分配组合。

补充：如果后续给问题加上其他约束，比如每名人员有固定的任务承接上限、同组任务分配给同一人存在额外互斥规则，问题复杂度可能变化，但仅按题设给出的条件，这个问题不属于NP-hard范畴。

内容的提问来源于stack exchange，提问作者Oscar