工作流资源配置禁忌搜索算法优化课件

我们的团队研究三位老师，近30个研究生感兴趣的研究传统工作流技术。包括时态工作流模型，资源配置优化，过程调度优化，引擎集群技术；面向服务工作流技术。服务组合优化，人工服务管理，过程协作中社会因素的影响。近五年成果2项国家基金，20多项省市支持项目。近10项横向应用主要应用电信，YWAL的应用，增强集群和并发支持能力物流，服务组合、伙伴协同、虚拟组织、信任与信誉电子商务，供应链协作优化、信任与信誉服务外包，ITIL在路灯管理、能源外包中的应用我们的团队研究三位老师，近30个研究生1大纲背景与动机相关工作问题定义工作流配置问题仿真优化框架禁忌搜索算法与启发规则实验结果与评价结束语大纲背景与动机2工作流资源配置问题的复杂性业务流程结构的多样性Aalst等从2005年就整理并了四十多种工作流基本结构模式现实业务中大多数流程可以用顺序、与、或、循环、并行等常用结构表示流程优化资源限制与优化目标的多样性优化目标：平均排队时间最优，占用资源最少，平均执行成本最低，最大执行时间最短资源限制：总成本，资源总数，执行时间，排队时间任务到达、执行时间分布的不确定性易于数学公式描述和处理的分布。例如，泊松分布、均匀分布、指数分布不易于数学描述和处理的分布。例如，三角分布，突发实例流工作流资源配置问题的复杂性业务流程结构的多样性3现有的一些方法基于排队理论的数学方法结构上化简：顺序、与、或、循环实例到达分布近似：均匀分布、泊松分布、指数分布单一约束与目标：资源总量不变下平均执行时间最短、资源总量不变下执行总成本最小优化方法：主要是线性规划基于进化算法优化方法引入并行结构。复合约束条件下单目标优化。例如：资源总量不变+最大执行时间约束下平均执行时间最短基于仿真优化技术方法更一般的工作流网络接近真实的任务到达流，如多种分布的组合复杂的约束条件和多目标把业务流程看成黑盒的、动态的复杂系统现有的一些方法基于排队理论的数学方法4不同方法的对比排队理论进化算法仿真优化结构上顺序，与、或，循环+并行一般任务输入均匀、泊松、指数分布无特别要求无特别要求约束条件单一多多优化目标单一单一多分析与建模白盒白盒黑盒求解效率高一般一般求解质量精确较差，可能是局部最优解较差，可能是局部最优解参数率定难较少很少不同方法的对比排队理论进化算法仿真优化结构上顺序，与、或，循5我们的工作运用仿真优化方法研究工作流的资源配置问题问题求解的一般框架对复杂业务流程的支持能力。主要考虑结构多样性和任务输入分布的复杂性定义成本约束、平均响应时间最短条件下的资源配置问题研究特定问题解空间的特征，提出适用于禁忌搜索算法的启发规则，并实验验证了这些规则的作用与有效性。禁忌搜索算法的初始解，短、中、长期启发规则分别验证不同规则的作用与有效性分析了求解效率、解质量我们的工作运用仿真优化方法研究工作流的资源配置问题6问题的定义问题描述：业务流程P，包含循序、分支、循环和并行结构。n个任务节点组成，令为t1，t2，…，tn。每个任务ti都对应一个可以执行它的角色ri，ri的单个资源的成本为ci。约束与目标：计算每个任务ti需要配置的资源数目xi，且总成本不超过一个上限C，业务流程案例的平均执行时间最短。（x1,x2,…,xn）即是该流程的配置向量x。问题的定义问题描述：7配置问题仿真优化求解框架配置问题仿真优化求解框架8解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务到达为泊松分布时，解配置问题空间。1、2、单调性。当其他资源数量不变，增加一种资源都有助于降低执行时间。当引入并行结构后？解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务9解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务到达为泊松分布时，解配置问题空间。1、2、单调性。当其他资源数量不变，增加一种资源都有助于降低执行时间。当引入并行结构上述两点都不成立。由于资源竞争，解空间变小，排队会形成局部拥堵。如堵车一样，在高成本节点拥堵会形成总体成本上升。直观的思路：用上述公式预估初始解。监控排队成本，作为禁忌算法的中期策略。解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务10基本禁忌搜索算法与要素禁忌搜索算法须确定以下几个要素：初始解产生规则，邻域的采样规则，短期记忆和藐视准则，以及中期和长期记忆。基本禁忌搜索算法与要素禁忌搜索算法须确定以下几个要素：初始解11初始解的产生算法以随机的方式产生初始解，但是费用接近而不超过

。显然，如果选择离在上边界太近，算法易陷入局部最优，太远则效率不高。初始解产生算法见算法2。初始解的产生算法以随机的方式产生初始解，但是费用接近而不超过12配置向量的邻域与采样x的邻域一维（左右两点）二维（上下左右四点）三维（8点）K维（2N个相邻的点）采样，确定下一解搜索的方向由于每个配置仿真一次，需要耗费大量时间，因此减少采样点非常重要。（1）优先搜索排队成本高的节点，资源增加的方向（2）选择合理的采样量配置向量的邻域与采样x的邻域13短期记忆短期记忆，即禁忌表，用于避免搜索回到一个已经搜索过的解。短期记忆短期记忆，即禁忌表，用于避免搜索回到一个已经搜索过的14中期记忆中期记忆用于将搜索过程引向一个有希望找到好的解的区域。直观就是倾向于为拥堵严重的地方添加资源中期记忆中期记忆用于将搜索过程引向一个有希望找到好的解的区域15长期记忆长期记忆的作用是将搜索引导到从未搜索过的区域。采用一种基于频率的方法：对于每个任务，记录它的每一个可能的资源数目在搜索过程中被使用过的次数。在生成新一轮迭代的初始解时，尽可能地为每个任务选择前一轮搜索中取值的次数较低的资源数目组合成新的初始解长期记忆长期记忆的作用是将搜索引导到从未搜索过的区域。16实验数据流程结构多种任务到达率的组合，各任务执行时间分布（见论文）实验数据流程结构17

实验A

与标准禁忌算法和爬山算法比较解的质量好，平均案例执行时间短。本文算法明显优于基本禁忌算法，绝大多数情况下优于爬山算法。这体现了进化算法的随机性和局部最优解的特征。求解的效率高，仿真次数少。本文算法与基本禁忌算法比提高了近10倍，是爬山法的2倍。爬山法总是在梯度最大方向搜索，效率较高但易于陷入局部最优解；禁忌算法搜索范围广，但效率低。添加了合适的启发算法后，效率问题得到了本质的改善。验证了本文所提出的启发式规则作为一个整体的有效性。

实验A

与标准禁忌算法和爬山算法比较解的质量好，平均案例执18实验B

不同规则在禁忌算法中作用分析四种实验场景基本禁忌搜索算法；基本禁忌搜索算法+初始解的产生规则；基本禁忌搜索算法+初始解的产生规则+短期记忆规则带启发式所有规则的禁忌搜索算法（本文算法）。实验结果实验B

不同规则在禁忌算法中作用分析四种实验场景19实验B

不同规则在禁忌算法中作用分析（1）初始解的合理选择，将极大改善算法的收敛速度。进一步验证了效率提高10倍的效果。（2）添加了邻域结构和采样规则算法后，效率进一步提升，解的质量有了进一步提高。（3）添加了中长期策略，虽然对效率提升不大，平均仅节约11次仿真。但由于一次防真都需要大量时间，这个节约也是有价值的。更重要的是，中长期策略扩大了解空间搜索范围，对提高解的质量有明显的帮助。实验B

不同规则在禁忌算法中作用分析（1）初始解的合理选择，20结束语基于仿真优化技术应用于工作流配置优化适应于更复杂，更一般的应用场景更一般的计算框架，不需要进行流程分析与建模针对特定优化问题，建立合适启发规则，能有效提高进化算法解的质量和求解的效率不足与进一步的工作结束语基于仿真优化技术应用于工作流配置优化21Thanks！Thanks！22我们的团队研究三位老师，近30个研究生感兴趣的研究传统工作流技术。包括时态工作流模型，资源配置优化，过程调度优化，引擎集群技术；面向服务工作流技术。服务组合优化，人工服务管理，过程协作中社会因素的影响。近五年成果2项国家基金，20多项省市支持项目。近10项横向应用主要应用电信，YWAL的应用，增强集群和并发支持能力物流，服务组合、伙伴协同、虚拟组织、信任与信誉电子商务，供应链协作优化、信任与信誉服务外包，ITIL在路灯管理、能源外包中的应用我们的团队研究三位老师，近30个研究生23大纲背景与动机相关工作问题定义工作流配置问题仿真优化框架禁忌搜索算法与启发规则实验结果与评价结束语大纲背景与动机24工作流资源配置问题的复杂性业务流程结构的多样性Aalst等从2005年就整理并了四十多种工作流基本结构模式现实业务中大多数流程可以用顺序、与、或、循环、并行等常用结构表示流程优化资源限制与优化目标的多样性优化目标：平均排队时间最优，占用资源最少，平均执行成本最低，最大执行时间最短资源限制：总成本，资源总数，执行时间，排队时间任务到达、执行时间分布的不确定性易于数学公式描述和处理的分布。例如，泊松分布、均匀分布、指数分布不易于数学描述和处理的分布。例如，三角分布，突发实例流工作流资源配置问题的复杂性业务流程结构的多样性25现有的一些方法基于排队理论的数学方法结构上化简：顺序、与、或、循环实例到达分布近似：均匀分布、泊松分布、指数分布单一约束与目标：资源总量不变下平均执行时间最短、资源总量不变下执行总成本最小优化方法：主要是线性规划基于进化算法优化方法引入并行结构。复合约束条件下单目标优化。例如：资源总量不变+最大执行时间约束下平均执行时间最短基于仿真优化技术方法更一般的工作流网络接近真实的任务到达流，如多种分布的组合复杂的约束条件和多目标把业务流程看成黑盒的、动态的复杂系统现有的一些方法基于排队理论的数学方法26不同方法的对比排队理论进化算法仿真优化结构上顺序，与、或，循环+并行一般任务输入均匀、泊松、指数分布无特别要求无特别要求约束条件单一多多优化目标单一单一多分析与建模白盒白盒黑盒求解效率高一般一般求解质量精确较差，可能是局部最优解较差，可能是局部最优解参数率定难较少很少不同方法的对比排队理论进化算法仿真优化结构上顺序，与、或，循27我们的工作运用仿真优化方法研究工作流的资源配置问题问题求解的一般框架对复杂业务流程的支持能力。主要考虑结构多样性和任务输入分布的复杂性定义成本约束、平均响应时间最短条件下的资源配置问题研究特定问题解空间的特征，提出适用于禁忌搜索算法的启发规则，并实验验证了这些规则的作用与有效性。禁忌搜索算法的初始解，短、中、长期启发规则分别验证不同规则的作用与有效性分析了求解效率、解质量我们的工作运用仿真优化方法研究工作流的资源配置问题28问题的定义问题描述：业务流程P，包含循序、分支、循环和并行结构。n个任务节点组成，令为t1，t2，…，tn。每个任务ti都对应一个可以执行它的角色ri，ri的单个资源的成本为ci。约束与目标：计算每个任务ti需要配置的资源数目xi，且总成本不超过一个上限C，业务流程案例的平均执行时间最短。（x1,x2,…,xn）即是该流程的配置向量x。问题的定义问题描述：29配置问题仿真优化求解框架配置问题仿真优化求解框架30解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务到达为泊松分布时，解配置问题空间。1、2、单调性。当其他资源数量不变，增加一种资源都有助于降低执行时间。当引入并行结构后？解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务31解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务到达为泊松分布时，解配置问题空间。1、2、单调性。当其他资源数量不变，增加一种资源都有助于降低执行时间。当引入并行结构上述两点都不成立。由于资源竞争，解空间变小，排队会形成局部拥堵。如堵车一样，在高成本节点拥堵会形成总体成本上升。直观的思路：用上述公式预估初始解。监控排队成本，作为禁忌算法的中期策略。解空间的特征由顺序、与、或、循环四种结构组成的排队网络，任务32基本禁忌搜索算法与要素禁忌搜索算法须确定以下几个要素：初始解产生规则，邻域的采样规则，短期记忆和藐视准则，以及中期和长期记忆。基本禁忌搜索算法与要素禁忌搜索算法须确定以下几个要素：初始解33初始解的产生算法以随机的方式产生初始解，但是费用接近而不超过

。显然，如果选择离在上边界太近，算法易陷入局部最优，太远则效率不高。初始解产生算法见算法2。初始解的产生算法以随机的方式产生初始解，但是费用接近而不超过34配置向量的邻域与采样x的邻域一维（左右两点）二维（上下左右四点）三维（8点）K维（2N个相邻的点）采样，确定下一解搜索的方向由于每个配置仿真一次，需要耗费大量时间，因此减少采样点非常重要。（1）优先搜索排队成本高的节点，资源增加的方向（2）选择合理的采样量配置向量的邻域与采样x的邻域35短期记忆短期记忆，即禁忌表，用于避免搜索回到一个已经搜索过的解。短期记忆短期记忆，即禁忌表，用于避免搜索回到一个已经搜索过的36中期记忆中期记忆用于将搜索过程引向一个有希望找到好的解的区域。直观就是倾向于为拥堵严重的地方添加资源中期记忆中期记忆用于将搜索过程引向一个有希望找到好的解的区域37长期记忆长期记忆的作用是将搜索引导到从未搜索过的区域。采用一种基于频率的方法：对于每个任务，记录它的每一个可能的资源数目在搜索过程中被使用过的次数。在生成新一轮迭代的初始解时，尽可能地为每个任务选择前一轮搜索中取值的次数较低的资源数目组合成新的初始解长期记忆长期记忆的作用是将搜索引导到从未搜索过的区域。38实验数据流程结构多种任务到达率的组合，各任务执行时间分布（见论文）实验数据流程结构39

实验A

与标准禁忌算法和爬山算法比较解的质量好，平均案例执行时间短。本文算法明显优于基本禁忌算法，绝大多数情况下优于爬山算法。这体现了进化算法的随机性和局部最优解的特征。求解的效率高，仿真次数少。本文算法与