公平性指派问题及其进化求解算法

摘要

针对任务指派中指派结果可能存在工作负荷分布极不平衡的问题,建立了公平性指派问题优化模型,并设计了求解模型的进化算法。以指派后代理的工作负荷与负荷均值的差值大小度量工作负荷的不均衡状况,将上述差值的平方和作为工作负荷的公平性指标。基于经典线性指派问题,构建了公平指派问题的优化模型。将相关问题按是否具有固定均值分为两类,并对两类问题的特征和求解策略加以分析。为提高计算效率,针对第二类指派问题的模型特征,设计了一种可求解过程中保持解的可行性的改进遗传算法。通过多个算例计算,并与Lingo软件求解结果对比,验证了模型和算法的合理性和有效性。研究表明:1) 一般情况下,公平性指派问题是一类具有NP-hard特征的三次指派问题;2) 追求公平的指派结果可能导致整体的工作负荷量增加;3) 所设计的遗传算法可高效求解各种规模的公平指派问题,但往往只能给出局部最优解;4) 变异系数对求解结果有显著影响,过大或过小的变异系数值均不利于算法求得最佳解。