最小化工人方差分配问题：相关研究与高效求解算法咨询

问题研究现状 #

你描述的问题属于带约束的负载均衡型指派问题，是经典指派问题的扩展，已有较为充分的研究：

• 理论上，该问题被证明是NP-hard——即使去掉任务只能分配给工人子集的约束，单纯的均匀任务指派问题（最小化工人负载方差/极差）已经属于NP-hard问题，加上子集约束后复杂度只增不减。
• 现有研究覆盖了从理论复杂度分析到各类求解算法的设计，包括精确求解、启发式近似、元启发式等多个方向。

高效求解算法 #

精确算法（适合小规模/中等规模实例） #

• 商用ILP求解器优化：你已经将问题转化为整数线性规划模型，直接使用Gurobi、CPLEX等商用求解器即可，它们内置了针对这类负载均衡问题的分支定界、割平面等优化策略，比手动实现的基础ILP求解效率高得多。
• 约束规划（CP）：针对任务-工人的子集约束，约束规划可以通过定义负载均衡的全局约束（如自定义负载差异约束），结合智能回溯剪枝，在部分场景下比ILP更快收敛到最优解，适合处理约束复杂的实例。

近似算法（适合大规模实例） #

• 贪心启发式：
  • 按任务耗时从大到小排序，依次将每个任务分配给当前总耗时最小的、且属于该任务允许子集的工人。该方法实现简单，且对于负载均衡类问题有稳定的近似效果，理论上针对最小化最大负载的场景有2 - 1/m的近似比（m为工人数），对最小化方差也能得到较优的近似解。
  • 基于效率的贪心：计算每个任务分配给不同工人后对整体方差的降低幅度，优先选择降低幅度最大的任务-工人对进行分配。
• 局部搜索类算法：
  • 从贪心得到的初始解出发，通过邻域交换（如将一个工人的任务转移给另一个允许的工人）、模拟退火、遗传算法等方式迭代优化，直到无法进一步降低方差。这类算法适合大规模实例，能在合理时间内得到高质量的近似解。
• LP松弛+舍入：
  • 先求解ILP模型的线性规划松弛问题，得到分数指派解后，通过随机舍入或确定性舍入策略得到整数解。这种方法有严格的理论近似比保证，适合对近似质量有明确要求的场景。

补充说明 #

最小化工人耗时方差的目标，和最小化负载极差（最大耗时-最小耗时）、最小化最大负载等目标高度相关——很多针对这类目标的算法可以直接适配到方差最小化的场景，或者通过调整目标函数的权重进行转换。

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