可复用资源的在线派单不再只看匹配分：LAG 把机会成本算进索引，在同行评审数据上比贪心最多高 12.3%
核心概要
可复用资源（评审人、坐席、服务器）的在线派单长期依赖贪心：每次把当前匹配分最高的资源派出去，却不计它被占用后未来任务失去的价值。LAG 把问题写成上下文 restless 多臂老虎机，用占用测度线性规划的上界及其对偶，为每个任务类型与资源对算出一个闭式索引，等于匹配分减去保留该资源的机会成本。在同行评审数据与结构化合成实例上，LAG 达到该线性规划上界的 83%–99%，相对贪心在期刊数据上最多提升 12.3%，在合成实例上最多提升 36%。
深度剖析
在线派单的决策依据从单一匹配分变成匹配分减去机会成本，资源因此会被留给后续更需要的任务。 此前的做法是贪心：按匹配分把当前可用的资源排个序，取最高的派出去，不考虑未来需求；自动评审人分配和呼叫中心路由都采用这种形式。 在同行评审数据与结构化合成实例上，LAG 达到占用测度线性规划上界的 83%–99%，相对贪心在期刊数据上最多提升 12.3%，在合成实例上最多提升 36%。
每个任务类型与资源对得到一个标量索引，到达的任务按索引从高到低占用空闲资源。 索引由占用测度线性规划的对偶解给出：该规划的对偶把全局派单问题拆成每个资源一个子问题，每个子问题由一个阈值策略求解。 索引中的价格项是服务一个该类型任务的影子价格，另一项是让资源保持忙碌的每步成本；在负载扫描中，每个负载点求解一次该规划并据此算出索引。
在每类资源的副本数与每步到达数一起增长的缩放机制下，LAG 被证明渐近最优。 经典的仅放大资源数的缩放每步仍只有一个随机到达，流体系统不会收敛到确定性不动点；同时放大到达数的批式缩放又让资源能在一批任务中挑最好的，改变了原问题。 新缩放把每类资源随机划分成若干组、每组只面对一个到达，使每个资源每步仍只看到一个上下文；在该机制下 LAG 的归一化奖励收敛到线性规划上界，且阻塞概率趋于零。
启示与展望
演示范围是可复用资源、任务即时派单、服务时长有界且只依赖任务类型的离散时间系统；评估覆盖两个真实同行评审数据集、两个合成呼叫中心实例和两个解析实例，负载从 0.1 扫到 0.9。渐近最优性只在严格欠载假设下、且每类资源副本数与每步到达数同步增长的新缩放机制中成立。
渐近最优性的证明依赖流体动力学存在唯一全局吸引不动点这一假设，该性质通常难以解析验证，一般靠数值证据建立。有限规模下阻塞概率没有闭式表达，需数值计算，文中以 Erlang 损失网络的表达式作为参考值。