《成批处理工作流动态分组调度优化方法》由会员分享，可在线阅读，更多相关《成批处理工作流动态分组调度优化方法（23页珍藏版）》请在装配图网上搜索。
1、成批处理工作流动态分组调度优化方法中南大学 信息科学与工程学院陈志刚陈志刚()Outline动态分组调度优化模型动态分组调度优化模型2问题的提出问题的提出1基于改进基于改进PSO的调度优化算法的调度优化算法3仿真实验仿真实验4问题的提出问题的提出1问题的提出问题的提出12问题的提出：研究背景问题的提出：研究背景q成批处理工作流成批处理工作流m一类包含成批处理区的特殊业务过程m成批处理区中同一类型工作流活动的多个活动实例可进行合并处理m原本分别执行的多个活动实例可成组合并执行q例：某公司处理共享租车的工作流例：某公司处理共享租车的工作流 m活动A提出租车申请；活动B审批租车申请；若租车申请未被审
2、批通过，则选择活动G发送拒绝通知 m反之，活动C安排出租车；活动D为通知司机；活动E为通知乘车人；活动F为乘车人缴费 现有成批处理工作流调度机制现有成批处理工作流调度机制q相关研究工作已设计了一个基于事件驱动机制的成批相关研究工作已设计了一个基于事件驱动机制的成批处理调度引擎处理调度引擎(DBP)现有调度机制的优缺点现有调度机制的优缺点优点：优点：qDBP采用事件触发机制来组织成批处理工作流的执行采用事件触发机制来组织成批处理工作流的执行过程过程qECA规则解释器对事件队列中的新到事件进行处理，规则解释器对事件队列中的新到事件进行处理，当某条当某条ECA规则满足，则其被解释执行规则满足，则其被
3、解释执行缺点：缺点：q未考虑活动实例对执行者的执行能力等需求以及执行未考虑活动实例对执行者的执行能力等需求以及执行者间的执行时间、开销等差异，这在一定程度上影响者间的执行时间、开销等差异，这在一定程度上影响了算法的实用性；了算法的实用性；q未考虑在通过分组合并降低活动执行开销时，尽量减未考虑在通过分组合并降低活动执行开销时，尽量减少活动实例的平均停留时间，而这有利于提高客户对少活动实例的平均停留时间，而这有利于提高客户对业务过程处理的满意程度。业务过程处理的满意程度。本文的研究思路本文的研究思路q通过对执行者与活动实例进行定量描述，建立活动实通过对执行者与活动实例进行定量描述，建立活动实例动态
4、分组调度优化模型例动态分组调度优化模型 q提出一种基于改进微粒群算法的动态分组调度优化实提出一种基于改进微粒群算法的动态分组调度优化实现算法（现算法（Dynamic Grouping and Scheduling Optimization,简称简称DGSO）m考虑活动实例对执行者的执行能力需求等约束，以最小化活动实例的停留时间总和与执行开销总和为目标，以有效产生一组满足约束条件的Pareto优化调度方案。m在实际应用中系统可根据该算法对活动实例动态分组并统一安排执行者与执行顺序，以符合成批处理工作流的实际应用需求 Outline动态分组调度优化模型动态分组调度优化模型2问题的提出问题的提出1基
5、于改进基于改进PSO的调度优化算法的调度优化算法3仿真实验仿真实验4问题的提出问题的提出1问题的提出问题的提出12相关概念的形式化描述相关概念的形式化描述 相关概念的形式化描述（继相关概念的形式化描述（继1）相关概念的形式化描述（继相关概念的形式化描述（继2）动态分组调度优化问题描述动态分组调度优化问题描述q根据上述定义，根据上述定义，本文研究的活动实例动态分组调度优化问本文研究的活动实例动态分组调度优化问题可描述如下：题可描述如下：m支持成批处理的工作流系统中存在M个待调度的同一类型可成批处理工作流活动的活动实例，其在分组特征项上的取值相同；同时存在N个执行者可为其服务m需要将这些活动实例合
6、理划分为若干个活动实例分组，并在执行者在满足活动实例分组的执行能力需求的前提下，为这些分组分配执行者及安排同一执行者上各个分组的执行顺序m使执行者的执行开销总和最小，同时活动实例的停留时间总使执行者的执行开销总和最小，同时活动实例的停留时间总和最小和最小q为方便求解，本文假设：为方便求解，本文假设：m各个分组的执行均只需一个执行者资源（需要多个执行者资源的情况将另行讨论）m且执行者每次执行的服务时间与执行开销固定，同时假设活动实例的停留时间为其排队等待时间，服务等待时间与服务时间总和。数学模型数学模型q根据上述假设，该问题可形式化描述如下：根据上述假设，该问题可形式化描述如下：Outline动
7、态分组调度优化模型动态分组调度优化模型2问题的提出问题的提出1基于改进基于改进PSO的调度优化算法的调度优化算法3仿真实验仿真实验4问题的提出问题的提出1问题的提出问题的提出12算法思想算法思想 qPSO算法算法 m由Kennedy博士和Eberhart博士于1995年提出m具有收敛速度快、计算简便和参数较少等优点，且受问题维数的影响也很小，能有效解决复杂优化问题 m近年来已成功应用于解决多个不同领域的调度与资源分配等问题。m但是，对于工作流调度优化问题，尤其离散域上带约束多目标调度优化问题方面的研究还很少 q基于改进基于改进PSO的动态分组调度优化实现算法的动态分组调度优化实现算法DGSO
8、m将活动实例分组与执行者分配方案编码为一个微粒m从带约束多目标优化的角度搜索可行解与非可行解m最终产生满足约束条件的Pareto优化动态分组调度方案 算法过程描述算法过程描述 qDGSO算法主要包括初始化与迭代搜索两个阶段算法主要包括初始化与迭代搜索两个阶段 微粒编码策略微粒编码策略 qDGSO算法采用整数编码方式算法采用整数编码方式 储备集更新策略储备集更新策略 qDGSO算法在更新储备集时将搜索时找到的精英个体均予以算法在更新储备集时将搜索时找到的精英个体均予以保留以维护解的多样性保留以维护解的多样性 微粒全局最优点的选择微粒全局最优点的选择 pDGSO算法采用动态分配策略与聚类分析相结合
9、的方法来选算法采用动态分配策略与聚类分析相结合的方法来选择微粒全局最优点择微粒全局最优点 微粒位置的更新微粒位置的更新 qDGSO算法采用类似遗传算法的交叉、变异、选择操作等算法采用类似遗传算法的交叉、变异、选择操作等方法更新各微粒的位置方法更新各微粒的位置 Outline动态分组调度优化模型动态分组调度优化模型2问题的提出问题的提出1基于改进基于改进PSO的调度优化算法的调度优化算法3仿真实验仿真实验4问题的提出问题的提出1问题的提出问题的提出12实验背景实验背景q某快递公司的包裹投送业务某快递公司的包裹投送业务 m活动A为发件人提交包裹，活动B为业务人员将包裹登记为“航空快递”或“普通快递
10、”型，然后，活动C、D分别运输、投送“航空快递”包裹，活动E、F则分别运输、投送“普通快递”包裹，活动G为收件人确认接收包裹，活动G为通知发件人 m为支持该过程高效执行并降低物流成本，我们结合前期成批处理工作流研究及正在承担的项目，已初步开发了一个工作流支持的智能物流系统 实验结果实验结果q采用采用Zitzler提出的提出的GD（Generational Distance,世代距世代距离）度量及算法运算时间作为算法性能的评价标准离）度量及算法运算时间作为算法性能的评价标准mGD反映了解集与实际Pareto最优解集的逼近程度，若GD=0，则算法获得的解均属于Pareto最优解集 Thank you！Q&A
成批处理工作流动态分组调度优化方法
