可复用资源的在线派单不再只看匹配分:LAG 把机会成本算进索引,在同行评审数据上比贪心最多高 12.3%
可复用资源(评审人、坐席、服务器)的在线派单长期依赖贪心:每次把当前匹配分最高的资源派出去,却不计它被占用后未来任务失去的价值。LAG 把问题写成上下文 restless 多臂老虎机,用占用测度线性规划的上界及其对偶,为每个任务类型与资源对算出一个闭式索引,等于匹配分减去保留该资源的机会成本。在同行评审数据与结构化合成实例上,LAG 达到该线性规划上界的 83%–99%,相对贪心在期刊数据上最多提升 12.3%,在合成实例上最多提升 36%。