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

Fair Assignment Problem and Its Average Approximation Algorithm

作　　者：何胜学[1] HE Shengxue(Business School,University of Shanghai for Science and Technology,Shanghai 20093)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《系统科学与数学》2022年第9期2399-2411,共13页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金资助项目(71801153,71871144);上海市自然科学基金项目(18ZR1426200)资助课题。

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

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

分 类 号：O221.4[理学—运筹学与控制论]