创新点1：一类NP-hard问题的四次多项式时间复杂度精确求解算法

        创新点2：提出了一类具有广泛应用性的指数分配问题

公平性指派问题及均值逼近求解算法

何胜学

(上海理工大学 管理学院，上海 200093)

摘要: 为了平衡任务指派后代理之间的工作负荷，建立了公平性指派优化模型，并给出了一种求解问题全局最优解的数值方法。将指派后各代理工作负荷与平均负荷的差的平方和作为工作负荷公平性的度量指标，结合经典指派问题约束建立了公平性指派模型。以工作负荷矩阵是否可以分解为两个特殊矩阵之和对问题进行了分类，指出了一般情况下公平性指派问题属于一类特殊的三次指派问题。通过有规律遍历工作负荷的可行取值范围，将问题求解转化为一维搜索内嵌求解系列经典线性指派问题。从理论上证明了均值逼近算法的合理性，同时指出算法的时间复杂度为问题规模的四次多项式时间。通过与商业优化软件Lingo的计算结果比较，证实新方法不仅可以得到问题的全局最优解，而且所需的计算时间很短。

关键词：整数规划；NP-hard问题；逼近算法；组合优化；指派问题

中图分类号：O221, F224

Fair Assignment Problem and its Average Approximation Algorithm

He Shengxue

(Business School, University of Shanghai for Science and Technology, Shanghai 200093, China)

Abstract：To balance the assigned working loads among agents, this paper formulated a fair assignment optimization model and proposed a numerical method for obtaining the global optimal solution. By defining the sum of squares of differences between assigned working loads of agents and the average load as the index of measuring the fairness of working load, this paper constructed the fair assignment model combining the constraints of the classic assignment problem. This study classified the problem according to whether the working load matrix could be decomposed into two special matrices and pointed out that a fair assignment problem is in general a type of cubic assignment problem. By regularly going through the feasible range of working load, this paper transformed the solution process into a one-dimensional search process that needs to solve a series of classic linear assignment problems. This study proved theoretically the soundness of the average approximation algorithm and pointed out the quartic polynomial time complexity concerning the scale of the problem. By comparing with the results of commercial optimization software-Lingo, the comparison verified that the new method obtains the global optimal solution and needs very low computational time.

Key words: integer programming; NP-hard problem; approximation algorithm; combinational optimization; assignment problem

引用格式： 何胜学．公平性指派问题及均值逼近求解算法[J/OL]．系统科学与数学.

https://kns.cnki.net/kcms/detail/11.2019.O1.20220620.1418.011.html

详见附件：

公平性指派问题及均值逼近求解算法_何胜学.pdf