(19)国家知识产权局 (12)发明 专利 (10)授权公告 号 (45)授权公告日 (21)申请 号 202210481654.5 (22)申请日 2022.05.05 (65)同一申请的已公布的文献号 申请公布号 CN 114581223 A (43)申请公布日 2022.06.03 (73)专利权人 支付宝 （杭州） 信息技 术有限公司 地址 310000 浙江省杭州市西湖区西溪路 556号8层B段801-1 1 (72)发明人 简道红　鲍阳　 (74)专利代理 机构 北京博思佳知识产权代理有 限公司 1 1415 专利代理师 李威 (51)Int.Cl. G06Q 40/02(2012.01) G06Q 10/06(2012.01) G06F 17/11(2006.01) (56)对比文件 CN 111742335 A,2020.10.02 CN 107370802 A,2017.1 1.21 CN 112861357 A,2021.0 5.28 CN 113890023 A,202 2.01.04CN 112188502 A,2021.01.0 5 CN 112136111 A,2020.12.25 US 2013018517 A1,2013.01.17 CN 110336298 A,2019.10.15 CN 110460036 A,2019.1 1.15 杨青润.基 于交替方向乘子法的电力系. .. 完全分布式动态经济调度方法. 《控制理论与应 用》 .2018,第3 5卷(第5期), 周任军等.基于改进矩不确定分布鲁棒优化 算法的多机调频比例决策. 《电力自动化设备》 .2019,(第0 6期), 徐薇等.基 于交替方向乘子法的大规模 线性 多商品流问题求 解算法. 《计算数 学》 .2018,(第 04期), 李婷等.基 于交替方向乘子法的源网协同多 适应规划. 《电力建 设》 .2017,(第1 1期), Euhanna Ghadimi.Optimal Parameter Selection for the Alternati ng Directi on Method of Multipl iers (ADM M) Quadratic Problems. 《IEEE Transacti ons on Automatic Control》 .2015,第6 0卷(第3期), 审查员 王婉君 (54)发明名称 分配任务处理方法、 设备、 分布式计算系统 及存储介质 (57)摘要 本说明书一个或多个实施例提供一种分配 任务处理方法、 设备、 分布式计算系统及存储介 质。 所述方法包括： 基于用户建模界面中的输入 数据， 确定分配任务的原始优化模型和约束条 件； 引入与所述约束条件相关的对偶变量； 根据 所述原始优化模型、 所述约束条件、 若干历史分 配任务对应的历史数据集合、 所述历史分配任务 的决策变量以及引入的所述对偶变量， 构建无约 束的目标优化模 型； 利用交替方向乘子法迭代求 解所述目标优化模型， 直到最后一轮迭代的约束 误差满足预设误差； 其中， 迭代后的对偶变量作为对偶系数用于实时处理在 线分配任务。 本实施 例有利于提高在线分配任务的处理效率并保证 其稳定进行。 权利要求书3页 说明书14页 附图4页 CN 114581223 B 2022.07.29 CN 114581223 B 1.一种分配任务处理方法， 所述分配任务用于从多个资源中确定向目标对象分配的目 标资源； 所述方法包括： 基于用户建模界面中的输入数据， 确定分配任务的原始优化模型和约束条件； 所述约 束条件包括约束所述分配任务的决策变量的约束系数和约束向量； 引入与所述约束条件相关的对偶变量； 根据所述原始优化模型、 所述约束条件、 若干历史分配任务对应的历史数据集合、 所述 历史分配任务的决策变量以及引入的所述对偶变量， 构建无约束的目标优化模型； 利用交替方向乘子法迭代求解所述目标优化模型， 直到最后 一轮迭代的约束误差满足 预设误差； 其中， 迭代后的对偶变量作为对偶系数用于实时处 理在线分配任务； 其中， 所述历史数据集合能够被划分为多个数据分片， 每个数据分片包括部分历史分 配任务的任务数据； 在将所述历史数据集合划分成多个数据分片的情况下， 所述方法应用 于分布式计算系统， 所述分布式计算系统包括控制节点以及若干个工作节点； 每个所述工作节点获取利用其中一个所述数据分片构建的无约束的目标优化子模型； 以及， 在每轮迭代过程中， 从所述控制节点中获取所述对偶变量经上一轮迭代更新的值， 根 据所述对偶变量的值求解所述目标优化子模型中的决策变量， 并将根据所述决策变量的求 解结果和所述决策变量的约束系 数确定的约束值发送给所述控制节点； 其中， 在首轮迭代 过程中， 所述控制节点将所述对偶变量的值初始化 为预设值； 所述控制节点在每轮迭代过程中， 接收各个所述工作节点发送的所述约束值， 基于各 个所述工作节点的约束值的累加结果和所述决策变量的约束向量之间的差异确定约束误 差； 在所述约束误差不满足预设误差的情况下， 根据所述约束误差更新所述对偶变量的值 并发送给 各个所述工作节点。 2.根据权利要求1所述的方法， 所述分配任务包括的决策变量的数量根据所述资源的 数量确定； 所述分配任务的决策变量 为： 各个资源分配给目标对象所能获取的收益； 所述原始优化模型的优化目标为： 最大化所述收益； 所述分配任务的处理结果为： 将所述收益最大的资源作为分配给所述目标对象的目标 资源。 3.根据权利要求1或2所述的方法， 所述原始优化模型包括影响所述分配任务的决策变 量的目标系数； 所述约束条件 包括约束所述分配任务的决策变量的约束系数和约束向量； 所述根据所述原始优化模型、 所述约束条件、 若干历史分配任务对应的历史数据集合、 所述历史分配任务的决策变量以及引入的所述对偶变量， 构建无约束的目标优化模型， 包 括： 根据所述目标系数、 所述约束系数和所述约束向量分别从所述历史数据集合中， 提取 若干历史分配任务的决策变量对应的目标系数矩阵、 约束系数矩阵和约束向量矩阵； 根据所述目标系数矩阵、 所述约束系数矩阵、 所述约束向量矩阵、 所述原始优化模型、 所述约束条件、 所述若干历史分配任务的决策变量以及引入的对偶变量， 构建无约束的目 标优化模型。 4.根据权利要求3所述的方法， 所述目标优化模型包括原 始优化模型项和约束 项； 所述原始优化模型项根据所述原始优化模型、 所述若干历史分配任务的决策变量和所权　利　要　求　书 1/3 页 2 CN 114581223 B 2述目标系数矩阵生成； 所述约束项根据所述约束条件、 所述若干历史分配任务的决策变量、 所述约束系数矩 阵、 所述约束向量矩阵和所述对偶变量生成； 其中， 所述约束项包括有等式约束项和/或不 等式约束 项。 5.根据权利要求1所述的方法， 在所述历史数据集合中， 各个历史分配任务的目标对象 所属类型相同； 所述方法还 包括： 针对于所述目标对象所属类型不同的多个历史数据集合， 分别执行构建无约束的目标 优化模型以及利用交替方向乘子法迭代求解所述目标优化模型的步骤， 获取不同类型的目 标对象分别对应的对偶系 数； 其中， 不同类型 的目标对 象分别对应的对偶系 数用于实时处 理具有对应 类型目标对象的在线分配任务。 6.根据权利要求1所述的方法， 所述控制节点包括主节点和算子节点； 所述方法还 包括： 所述算子节点在每轮迭代过程中， 将确定的所述约束误差发送给所述主节点， 并在接 收到所述主节点 发送的指示迭代未终止的指示信息时， 根据所述约束误差更新所述对偶变 量的值并发送给 各个所述工作节点； 所述主节点接收所述算子节点发送的约束误差， 在所述约束误差不满足预设误差的情 况下向所述 算子节点发送指示迭代未终止的指示信息 。 7.根据权利要求1所述的方法， 所述原始优化模型包括影响所述分配任务的决策变量 的目标系数； 所述约束条件 包括约束所述分配任务的决策变量的约束系数和约束向量； 所述方法还 包括： 根据所述原始优化模型、 所述约束条件和所述迭代后的对偶变量的求解结果， 生成数 据模板； 所述数据模板指示有处理分配任务所需的系数； 所述系数包括目标系数、 约束系数 以及对偶系 数； 所述数据模板还包括所述对偶系 数的系数值； 所述数据模板用于获取在线 分配任务相关的处 理数据。 8.根据权利要求7 所述的方法， 还 包括： 响应于在线分配任务的处理请求， 根据所述数据模板读取所述在线分配任务中每个资 源对应的系数值； 根据预先确定的评估规则和所述每个资源对应的系数值， 确定每个资源的评估结果； 其中， 所述评估规则基于所述原始优化模型对应的对偶模型确定； 所述评估结果指示将所 述资源分配给目标对象所能获得的收益； 基于每个所述资源的评估结果， 从所述多个资源中确定分配给所述目标对象的目标资 源。 9.根据权利要求1所述的方法， 所述用户建模 界面包括有决策变量输入组件、 优化目标 输入组件以及约束条件输入组件； 所述输入数据包括： 从所述决策变量输入组件获取的描述决策变量的信息、 从所述、 优 化目标输入组件获取的描述优化目标的信息、 以及从所述及约束 条件输入组件获取的描述 约束条件的信息； 所述分配任务的原始优化模型基于所述描述决策变量的信息和所述描述优化目标的权　利　要　求　书 2/3 页 3