(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210922011.X (22)申请日 2022.08.02 (71)申请人 西南交通大 学 地址 610031 四川省成 都市二环路北一段 (72)发明人 邱小平　吴燕姣　游彬慈　杨科　 (74)专利代理 机构 北京正华智诚专利代理事务 所(普通合伙) 11870 专利代理师 陈航 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) G06Q 10/10(2012.01) G06N 7/00(2006.01) (54)发明名称 一种基于随机时间Petri网的工作流执行优 化方法 (57)摘要 本发明公开了一种基于随机时间Petri网的 工作流执行优化方法， 包括S1、 构建服务时间模 型， 计算不同结构下活动总平均服务时间， 并对 当前负载进行更新， 以计算得到工作流服务时间 最小的目标函数； S2、 根据负载均衡服务时间最 小的目标模 型， 将执行者能力和其已分配的实际 任务数量转换为执行者负载进行遍历循环， 以寻 找得到最优的候选执行者； S3、 构建等待时间模 型， 并基于工作流服务时间最小的目标函数， 计 算工作流执行时间最小的目标函数； S4、 根据工 作流执行时间最小的目标函数， 进行随机时间 Petri网执行时间的优化。 本发明构建了基于随 机时间Petri网的工作流执行时间模型， 用于分 析、 计算并减少工作流过程执 行时间。 权利要求书4页 说明书12页 附图3页 CN 115239008 A 2022.10.25 CN 115239008 A 1.一种基于随机时间Pet ri网的工作流执 行优化方法， 其特 征在于， 包括以下步骤： S1、 构建服务时间模型， 计算不同结构下活动总平均服务时间， 并对当前负载进行更 新， 以计算得到 工作流服务时间最小的目标函数； S2、 根据负载均衡服务时间最小的目标模型， 将执行者能力和其已分配的实际任务数 量转换为执 行者负载进行遍历循环， 以寻找得到最优的候选执 行者； S3、 构建等待时间模型， 并基于工作流服务 时间最小的目标函数， 计算工作流执行时间 最小的目标函数； S4、 根据工作流执 行时间最小的目标函数， 进行随机时间Pet ri网执行时间的优化。 2.根据权利要求1所述的基于随机时间Petri网的工作流执行优化方法， 其特征在于， 所述步骤S1具体包括： S1.1、 根据随机时间Petri网 的模型构 建， 对多维动态工作 流运行过程产生的执行时间 进行分析， 将执 行时间划分为 服务时间和等待时间， 并分别构建工作流时间优化模型； S1.2、 计算 不同结构下活动总平均服 务时间； S1.3、 对执 行者负载进行 更新， 并计算 求解工作流 服务时间最小的目标函数。 3.根据权利要求2所述的基于随机时间Petri网的工作流执行优化方法， 其特征在于， 所述步骤S1.2中计算 不同结构下活动总平均服 务时间， 包括： 计算顺序结构活动总平均服 务时间： 其中， Si为活动Ti上的平均 服务时间； n为工作 流活动的总数， ei为每个工作 流活动上执 行者人数， uij为工作流每个 活动中的候选执行者； tij为执行者uij完成活动Ti所需的平均服 务时间； Q(uij)为在活动Ti上执行者uij处理实例的平均排队时间； 工作流的活动集为{Ti}(1 ≤i≤n)； 计算并行 结构活动总平均服 务时间： 其中， a为并行 结构分支 节点开始序号， g为并行 结构分支 节点结束序号； 计算选择 结构活动总平均服 务时间： 其中， v为选择 结构分支 节点结束序号； 计算循环结构活动总平均服 务时间： 其中， f为循环集 N分支节点结束序号， z为循环结构结束循环 节点序号。权　利　要　求　书 1/4 页 2 CN 115239008 A 24.根据权利要求3所述的基于随机时间Petri网的工作流执行优化方法， 其特征在于， 所述S1.3中对执 行者负载进行 更新， 并计算 求解工作流 服务时间最小的目标函数， 包括： 根据最小预测负载对服 务时间模型新任务进行分配， 其中， 负载 更新包括： 执行者进行新任务分配时更新当前负载， 其预测负载的值和当前负载的更新 为： Lpred(uij)＝Lcur(uij)+tij， j∈(1,ei) Lcur(uik)＝Lpred(uik) 其中， uik为预测负载最小的执行者； Lpred(uij)为执行者uij的预测负载； Lcur(uij)为执行 者uij的当前负载； Lcur(uik)为执行者uik的当前负载； Lpred(uik)为执行者uik的预测负载； 在每个时刻需要更新当前负载： Lcur(uij)＝max(0,Lcur(uij)‑Δt) 其中， Δt为时间步长； 在动态的工作流系统中， 若每个实例所有活动上服务时间最短， 在分配任务时选择负 载最小的执 行者， 其工作流 服务时间最小的目标函数为： min(Lpred(uij))， s.t Aki≠0,1≤Aki≤ei且为整数； 其中， 约束条件Aki≠0表示实例在活动中产生的任务都应被分配给对应活动上的执行 者。 5.根据权利要求4所述的基于随机时间Petri网的工作流执行优化方法， 其特征在于， 所述步骤S2包括： 以时间为主线， 通过一个时间变量tcur的循环累加模拟一个真实的工作流环境， 求得时 间线上执行者的当前负载， 确定当前时刻实例的到 达数量； 以及， 以单个实例分配为主 线， 确定在当前时刻单个实例上 可以进行分配的活动。 6.根据权利要求5所述的基于随机时间Petri网的工作流执行优化方法， 其特征在于， 所述步骤S3具体包括： S3.1、 在工作流不同活动两个相同执行者的交互过程中， 因交互次数的增加存在学习 效应， 执行者重复交互工作从而积累经验， 使得双方后续交互产生的工作流等待时间减少， 采用两阶段交互曲线表示交互学习效应， 即第x次交互时执行者ui‑1,k与执行者uiv产生的等 待时间为： 执行者ui‑1,k与执行者uiv之间所产生的平均等待时间为： 其中， M为交互过程中的不可压缩因子， 即无法降低重复交互的等待时间； B为执行者交 互过程中存在的先前经验因素； b为交互学习指数； X<ui‑1,k,uiv>为执行者ui‑1,k与执行者uiv 达到交互稳定时间的交互次数； 为执行者ui‑1,k执行活动Ti‑1与执行者uiv执行活 动Ti之间所产生的平均等待时间； c<ui‑1,k,uiv>为执行者ui‑1,k与执行者uiv的交互次数； tx<权　利　要　求　书 2/4 页 3 CN 115239008 A 3