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

Fair Assignment Problem and Its Genetic Algorithm

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

Abstract: In order to solve the highly unbalanced working load distribution possibly shown after assignment, this paper formulated the optimization model of fair assignment problem and designed a genetic algorithm to solve this model. In view that the difference between the working load of an agents and the average of working load reflects the unbalance state of working load, the sum of the square of the above differences was defined as the index of fairness of working load. Based on the classic linear assignment problem, this paper constructed the optimization model of fair assignment problem. The paper grouped the related problems into two categories according to whether the average is a constant and analyzed the properties and solution strategies of the two categories. To improve the efficiency of solving the problem in the second category, this paper designed a modified genetic algorithm that remains the feasibility of solutions obtained during the iterations. Through computing several examples and comparing the results with that of Lingo software, this paper verified the rationality and effectiveness of the new model and algorithm. This study shows the following: 1) In general, fair assignment problem is a type of cubic assignment problem with NP-hard property. 2) Pursuing a fair assignment result may lead to an increased total working load. 3) The designed genetic algorithm can solve various scales of fair assignment problem, but usually only give a local optimal solution. 4) The mutation coefficient has a noticeable impact on the final solution and a too big or too small mutation coefficient has negative influence on searching a better solution.