(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210816561.3 (22)申请日 2022.07.12 (71)申请人 苏州大学 地址 215000 江苏省苏州市吴中区石湖西 路188号 (72)发明人 梁合兰　李煌　李凡长　 (74)专利代理 机构 苏州市中南伟业知识产权代 理事务所(普通 合伙) 32257 专利代理师 陈华红子 (51)Int.Cl. G06F 9/50(2006.01) G06F 30/20(2020.01) G06F 111/04(2020.01) G06F 111/06(2020.01) (54)发明名称 混合云环境下带多时序约束的工作流调度 方法 (57)摘要 本发明涉及一种混合云环境下带多时序约 束的工作流调度方法， 包括： 建立包括模型的决 策变量、 模 型约束和模型目标的混合云多时序约 束工作流调度问题的形式化模型， 在混合云多时 序约束工作流调度问题的形式化模型下建立多 时序约束分解策略、 启发式任务 分配策略和考虑 计费周期的成本优化策略， 使用多时序约束分解 策略、 启发 式任务分配策略和考虑计费周期的成 本优化策略得到混合云中具有时序约束的工作 流调度的最佳方案。 本发明可以提高最优解生成 的有效性， 在复杂流程结构、 多时序约束、 混合云 资源等复杂环境制定成本更低的调度解。 权利要求书6页 说明书17页 附图1页 CN 115237593 A 2022.10.25 CN 115237593 A 1.一种混合云环境下 带多时序约束的工作流调度方法， 其特 征在于， 包括以下步骤： S1： 建立混合云多时序约束工作流调度问题 的形式化模型， 所述混合云多时序约束工 作流调度问题的形式化模型包括模型的决策变量、 模型约束和模型目标； S2： 在所述混合云多时序约束工作流调度问题 的形式化模型下， 建立多时序约束分解 策略、 启发式任务分配策略和考虑计费周期的成本优化策略； S3： 使用所述多时序约束分解策略、 启发式任务分配策略和考虑计费周期的成本优化 策略得到混合云中具有时序约束的工作流调度的最佳 方案。 2.根据权利要求1所述的混合云环境下带多时序约束的工作流调度方法， 其特征在于： 所述混合云多时序约束工作流调度问题的形式化模型， 具体为： S1‑1： 设置混合云多时序约束工作流调度问题的形式化模型中的参数： 将私有云表示为pc1， 公有云资源提供商表示为EC＝{ ec1,…,ecm}， 其中每个ecm代表一 个公有云服务提供商， 每个云提供商都提供了不同机器配置和定价模型 的虚拟机类型； 将 虚拟机类型表示为VMTi＝{vmti1,…,vmtij,…,vmtik}， 其中vmtij表示第i个云提供的第j个 虚拟机类型； 工作流集合定义为WP＝{wp1,…,wpi,…,wpm}， 其中， 每个工作流基于P etri网模型进行 形式化定义， 表 示为wpi＝<TSi， Pi， Ai>， TSi是第i个工作流中的任务集合， Pi是任务的状态集 合， Ai是连接任务的有向弧集 合； 定义柔性时序约束集合TCN＝{tcn1,…,tcnu,…,tcnn}， 其中每个柔性时序约束tcnu＝< swpu,eu,du,pau>， 其中swpu是第u个时序约束子流程， 存储了第u个时序约束所 涉及的任务及数据序列； eu是第u个时序约束理想执行时间 限制， du是截止时间， pau是损失 补偿； 如果在调度计划中， 执行swpu的结束时间与开始时间之差小于理想执行时间eu， 则表 明该调度 计划完全满足时序约束要求； 如 果执行swpu的结束时间与开始时间之差超过截止 时间du， 则调度计划完全违反时序约束， 表明计划不可行； 如果执行swpu的结束时间与开始 时间之差在eu和du之间， 表明该调度计划局部满足了约束， 对于超过eu的每个时间单位需额 外增加单位惩罚成本pau； S1‑2： 根据混合云多时序约束工作流调度问题的形式化模型中的参数设置模型的决策 变量： 设置决策变量xijkvq， 用于回答每个任务安排到哪个虚拟机； xijkvq为0‑1变量， 若xijkvq＝ 1表示任务tij由第k个云提供商的第v个类型的虚拟机实例q执行， tij为第i个工作流的第j 个任务； 将公有云中每种类型的虚拟机数量设置为任务数量| TS|， xijkvq的表达式为： 设置决策变量stij和ftij， stij用于回答每个任务调用虚拟机的开始时间， ftij用于回答 每个任务调用虚拟机的结束时间； S1‑3： 设置模型约束： S1‑3‑1： 设置任务的开始时间stij的约束为： 其中， pred(tij)为任务tij的紧前任务集合， adb(tij)为任务tij所安排的资源上当前已权　利　要　求　书 1/6 页 2 CN 115237593 A 2安排的任务集合， tiu表示tij的任意一个紧前任务， thp表示任务tij所安排的资源上 当前已安 排的任意 一个任务， ftiu表示任务tiu的结束时间， fthp表示任务thp的结束时间； 设置每个任务调用虚拟机的结束时间ftij等于开始时间加上 执行时间： 其中， 表示任务tij在第k个云提供商提供的第v种虚拟机类型 下的执行时间； S1‑3‑2： 根据柔 性时序约束得到时序约束公式： 其中， 为第u个时序约束子流程swpu的结束时间， 为第u个时序约束子流程 swpu的开始时间， du是第u个时序约束的截止时间， tcnu表示第u个柔性时序约束， TCN表示柔 性时序约束集 合； S1‑3‑3： 设置限制每 个任务只能安 排到一个虚拟机： S1‑3‑4： 设置限制每 个虚拟机在同一时间只能执 行一个任务： 其中， 为0‑1变量， 用于标记任务tij是否在时刻s执行； 若ztijs＝1表明任务tij在时 刻s执行； S1‑3‑5： 设置限制私有云的资源约束： 其中， vcpuv表示私有云的虚拟机类型v所需的CPU数量， v memv表示私有 云的虚拟机类型 v所需的内存数量， Ccpu表示私有云的资源池最大CPU数量， Cmem表示私有云的资源池最大内 存数量； xij1vq为0‑1变量， 若xij1vq＝1表示任务tij由私有云提供商的第v个类型的虚拟机实 例q执行； S1‑4： 设置模型目标： min TotalCost＝Proc Cost+TranCost+TemPen             (10)； 其中TotalCost为调度模型的总成本， Proc Cost为资源执 行成本， 具体为：权　利　要　求　书 2/6 页 3 CN 115237593 A 3