成批处理工作流动态分组调度优化方法.ppt

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