（计算机应用技术专业论文）分布式工作流管理系统myworkflow的研究与设计.pdf

第一章绪论 1 1 引言 随着i n t e r n e t 的普及，计算机开始转向支持商务过程，最初的应用软件 是基于在操作系统平台上开发的，这大大限制了企业的更深远的发展。所以， 随着应用规模的不断扩大，常规的应用软件对企业的发展起到瓶颈作用，因 而有必要引入工作流管理系统( w o r k f l o wm a n a g e m e n ts y s t e m ，w f m s ) 。 1 2 工作流技术的发展概况 工作流管理技术到目前为止大致经历了三个发展： 第一个阶段( 1 9 8 9 一1 9 9 2 ) ：在这个阶段是工作流技术思想的萌芽阶段。 第二阶段( 1 9 9 2 一1 9 9 5 ) ：在这个阶段是工作流技术的初步发展阶段。 9 0 年代一至今是工作流技术发展的第三个阶段，即对工作流技术讲行系统地 研究和大发展的阶段。 综上所述，工作流技术仍然不是一门十分成熟的技术学科，它有着广阔 的发展研究空间，是一门充满活力的新兴技术学科。 1 3 工作流管理系统的现状 从广义上讲，工作流管理系统分为四种：计算机支持协同工作( c s c w ) 商用工作流管理系统、商用事务管理系统和事务性工作流管理系统 1 基于 成熟产品的工作流管理系统；智能工作流管理系统( i n t e n i g dc r e l t e ( ) ： p u b l i cv o i dd e s t r o y ( ) 创建一个项目 撤消这个项目 x 1 4 工作流管理系统的基本概念介绍 工作流管理的最大优点是将应用逻辑与过程逻辑分离，工作流技术为企 业更好地实现经营目标提供了先进的手段 1 l ，1 2 ，1 3 1 9 9 3 年，国际上专门成立了工作流管理联盟( w f m c ) 以对工作流管理标 准化，进而推动工作流技术快速发展。工作流管理联盟成员包括开发商、用 户、系统分析员和科研人员等。该组织统一了工作流管理系统的相关术语 1 4 ，制订了工作流参考模型 1 5 ，以及工作流应用编程接口( a p i ) 说明等 1 6 1 7 。通过这些规范来使工作流产品实现标准化。 1 4 1 基本概念 按照工作流管理联盟的建议 1 8 。这里给出如下定义： 定义1 1 工作流( w o r k f l o w ) ：工作流是指整个或部分业务过程在计算机 支持下的全自动或半自动化执行。 定义1 2 工作流管理系统( w f 淞 x 第二章m y l r o r k f l 呷工作流模型和模型执行算法 工作流模型是对工作流的抽象表示，也就是对经营过程的抽象表示。 本章分析了当前流行的工作流建模方法，给出了m y w o r k f l o w 所采用的 建模方法网络活动状态图( n a s d ) 与l y w o r k f l o w 模型的体系结构，最后在 m y w o r k f l o w 模型的基础上，设计了m y w o r k f l o w 工作流实例的执行算法。 2 1 工作流建模方法研究 在工作流建模方法方面，人们从各自的研究背景和应用需求出发，分别 提出了许多有价值的方法。目前，主要的建模方法有以下几种： 基于用图形化的建模方法、基于p e t r i 网的建模方法、基于对话模型的 建模方法 2 3 等。 活动网络图是可读性最好的一种。对于非专业人员是最直观、最自然的 过程表示方式。在以下的小节中，我们将详细讨论m y w o r k f l o w 工作流模型。 2 2m o r k f l o 霄过程建模体系结构 本章提出的m y w o r k f l o w 过程建模体系结构是由组织模型维，数据信息 模型维，资源模型维，过程模型维组成的四维结构。 下面对各个模型维进行具体的介绍。 2 2 1 组织模型维 组织模型用于建立企业的组织模型，描述企业组织的层次结构，与一个 企业业务流程所涉及到的所有组织对象( 一个单个的人员、一个小组也可 以是一台机器等任何处理实体。 一个组织o r ( o r g a n i z a t i o n ) 可有若干个部门( d e p a r t m e n t ) 或者团队 ( t e a m ) 每个部门又可细分为多个下级部门这样就形成了组织的层次树结 构。 组织0 r 通常为五元关系 其中： 1 0 o r g i d 表示组织编号； o r g n a m e 表示组织名称； t y p e 为组织类型1 表示部门；2 表示团队l a y e 缉圣毓琴禽蹦鬏 枯5 爹# 目t s l 姚豁鞠坦蠢辚辫辅篮脞垡斜华在； 副豢塞嵩澎世芏缫燃- - - 裂藉莉需赫赫 强靠n 礁姑。裕瓣 ，r i 。； g ! 藕；i 毒盔喃z j ；5 i ；演湍j 瑚啧! 墓l 霉憔一渤m 懈隋；学蕾锲搿曼熏善 意薪巅彰昏豪翩蓟舒蕃执 行也可能会带 来不正确的执行结果，产生丢失修改、不可重复读和读脏数据三种数据不一 致问题 3 3 ，因此必须提供有效的调度技术来控制工作流的并发执行，以保 证工作流执行的正确性和高效性。 3 2 调度类型 工作流系统中的实例调度大致可以分为两种： 1 ) 多个过程实例调度： 2 ) 单过程实例调度。 对于同一个过程实例内部的多个分支上分别存在n ( n 2 ) 个活动参与可 更新资源的竞争：或者不同的过程实例中分别有多个活动实例参与可更新资 源竞争的问题，这时可以利用多个过程实例调度的加锁的策略进行调度，由 于属于单执行模式资源受限项目调度问题( s r c p s p ) 3 4 ，所以也可按照遗传 一蚂蚁混合任务调度算法来解决。 一个过程实例有两个并行的分支淌道辛礁霾械姆种 x 数据存储对象等信息。 2 2 4 过程模型维 在m y w o r k f l o w 模型中，过程模型维是核心模型维( 为了描述方便，以 下章节中，将过程模型维简称过程模型) 。 在建立过程时，可根据具体情况对过程中的某个活动即复杂活动逐层分 解，由于企业过程很多，所建立的过程模型同样很多，这就形成了许多过程 树组成的“过程森林”。而模型的过程视图，也正是这个“过程森林”。 2 3m y w o r k f l o w 过程模型的形式化描述 下面给出m y w o r k f l o w 过程模型的形式化定义。 定义2 3 1 工作流过程w 工作流过程w 是对某个产品开发流程的静态特性的数学描述，将其形式化 为一个多元组( n ，v ，v 。，r ，p js ，e ) ，其中 n 是过程的标识： v = f a ii = l ，2 ，n ) 表示工作流程中所有活动a 构成的集合： v 。= r u 。ii = 1 ，2 ，n ) 表示工作流程中所有活动间的跃迁路由集合： r 为过程的负责人： p 工作版本w o r k ed i t i o n ，释放版本r e l e a s e ed i t i o n ，它表示工 作流过程在设计过程中的设计状态。s ，e 均为布尔表达式，分别表示过程的 开始条件和结束条件。过程的开始条件是指过程执行所需要的外部条件。 定义2 3 2 任务活动a 任务活动a 是对工作流过程中的一个工作步骤的静态特性的数学描述， 它对应过程模型中的一个节点。它可以是实际工作的个任务，也可以是过 程中的一个逻辑节点。它可被形式化成多元组( i d ，t ，s c ，e c ，a r ，o ， r s ，d ，t ，m ) ，其中i d 表示活动标识：t 表示活动类型，在m y w o r k f l o w 中活动可 以分为以下几类； 1 根据任务的复杂程度将任务按复杂程度分成简单任务和复合任务。 简单任务活动是功能单一，是不可再分的独立的工作单位。 复合任务活动是完成某一工作目标的独立工作单位，但它可以分为多个 简单任务或功能相对简单的复合任务。 条件结构表示选定所有的分支。有条件结构一般用于选路。 图2 3 3 分支结构 汇聚结构。如图2 3 4 ，它分为两种基本汇聚结构：与( a n d ) 结构、或 ( o r ) 结构，也称为a n d 一汇聚、或o r 一汇聚。a n d 一汇聚结构表示t i 全部提交 后，t 开始启动，如果t i 中有一个废弃，整个汇聚结构废弃。0 r - 一聚结构表 示t i 中有一个提交后，t 开始启动，如果t i 都废弃，整个汇聚结构废弃。 图2 3 4 汇聚结构 循环结构。图2 3 5 指的是一种w h i l e 型的循环结构，在实际中还可有 r e p e a t u n t i l 型的循环结构，但这晕只列出一种。对图2 3 5 的结构，如果 条件为t r ue t 1 开始启动，t 1 提交后，然后t 2 开始启动，以此类推到t n 循 环结构一直运行到条件变成f a l s e 或任务t i 被废弃。 图2 3 5 循环结构 1 9 6 ) 补偿反做结构。图2 3 6 中t 表示任务t 的补偿或反做任务。补偿结 构的形式语义为：c o m p e n s a t i o n = ( a b o r t l i s t ( t l ，t 2 ，t n ) t ，) ，它表 示一旦( t l ，t 2 ，t n ) 中有一个任务废弃时，补偿任务t 启动。反做结构的 形式语义为：u n d o 可，它表示任务t 失败时，反做任务t 启动。 图2 3 6 补偿反做结构 定义2 3 4 活动实例a 活动实例a 表示过程执行中的一个步骤，活动a 和活动实例a 分别是对过 程中活动的静态和动态描述。a 需要从a 中继承分量，同时又要增加反映活动 动态特性的分量。a 可以被形式化为多元组( i ，1 ，n ，u ，t s ，t e ，s t ，a no ， e s ，e e ，r s ，d ，t ，m ) ，其中i 为活动实例标识：i 为活动实例所属的过程实例的 标识：n 为此活动实例相应的活动名称： v 一= p 1i n ) 表示活动实例a 的参加者集，其中p ；的r 分量构成的集合，记 为v 旷 r i i i n ，v p r 满足下列条件： v p _ 。口a r ： 其中a 。表示活动实例a 的角色集。该条件表示活动实例a 的参加者的角色 应该符合与活动的角色定义。 t s ，t e 表示活动开始和结束时间 s t f 初始态( i na c t i v e ) ，就绪态( r e a d y ) ，执行态( e xe c u t i n g ) ， 休眠态( s l e e p i n g ) ，完成态( f i n i s h e d ) ，挂起态( s u s p e n d e d ) ，废弃态 ( a b a n d o n e d ) ，它表示活动的运行状态，其中初始态表示活动实例创建后的 最初状态。活动实例的状态转换图如图3 一1 4 所示。 a 。o ，e s ，e e ，r s d ，t ，m 都是活动实例a 从活动a 中继承的分量。 定义2 3 5 工作流过程实例w 工作流过程实例w 表示一个工作流的一次执行过程，工作流过程实例w 和 工作流过程w 的区别在于它们分别是对过程的动态和静态的描述。w 需要继承 w 中的分量，同时又要增加反映过程动态特性的分量。w 可以被形式化为多元 组 i ，w ，b ，e ，t w ，v a ，vr l ，s ，r ，p ) ，其中 i 为工作流实例的名称： w 为工作流实例引用的工作流过程的名称： b ，e 分别为工作流实例的开始和结束时： t w 初始态( i n a c t i v e ) ，就绪态( r e a d y ) ，执行态( e x e c u t i n g ) ，完成 态( f i n i s h e d ) ，休眠态( s l e e p i n g ) ，挂起态( s u s p e n d e d ) ，废弃态 ( a b a n d o n e d ) ，与活动实例a 中t 不同的是，t w 表示整个过程的运行状态， 它的状态转换关系与活动实例的状态转换关系类似，需要说明的是，过程从 初始态( i n a c t i v e ) 向就绪态( r e a d y ) 的变迁条件是过程开始条件s 为真。 v 产( a 、! i = l ，2 ，3 ，n 表示过程执行中所有活动实例的集合。 。s ，r ，p 是继承工作流过程w 的分量。 定义2 3 6 工作项i 工作项i 表示的是需要某个参加者处理的一项任务，它可以形式化为四 元组 n ，w ，a ，d ) ，其中n 表示参加者的名称，w 表示相应的工作流实例的名 称，a 表示此工作流实例中的活动实例名称，d 为该工作项的任务描述。 定义2 3 7 工作项列表l 工作项列表l 记录了在产品开发工作流管理系统中的用户需要处理的 所有工作项的集合，它可以形式化为二元组 n v 。) ，其中n 表示参加者的名 称：v i = i = l ，2 ，3 ，n ) 表示工作项的集合，其中v ，中每个元素i 的n 分量 等于l 中的n 分量。 工作项列表l 记录了在产品开发工作流管理系统中的用户需要处理的所 有工作项的集合，它可以形式化为二元组f n v 。) ，其中n 表示参加者的名 称：v ，= i ； j = l ，2 ，3 ，n 表示工作项的集合，其中v 中每个元素i 的n 分量等于1 中的n 分量。 2 4m y w o r k f l o w 工作流模型的执行算法 下面本文以m y w o r k f l o w 为基础，给出工作流实例执行的相关算法。该算 法可以分为两个部分，即工作流实例的启动和工作流实例的执行。 ( 1 ) 工作流实例的启动算法 从工作流管理系统中，选择指定的、待启动的工作流过程w ： 根据该工作流过程w 与指定的工作流实例名称n a m e ，创建并初始化 新的工作流实例w 和w 中的所有活动实例v a ，使得： w i = n a l i i e ： 初始化工作流实例名 w b = 系统当前时间：初始化工作流实例的开始时间 w = w n ： 初始化工作流实例引用的工作流过 程的名称 w r = w r ： 初始化工作流实例的负责人 w p = w p ：初始化工作流实例的版本 w t w = i n a c t i v e ： 初始化工作流实例的状态 w v a t = i n a c t i v e ； 初始化工作流实例的活动集的状态 判断工作流实例w 的开始条件s ，若满足。则： w t w = r e a d y： 根据坩的起始活动a ，使能工作流实例w 中的起始活动实例a ：使： a 1 = w i ： a n = a n ： 初始化活动实例标识 a v p = 参加者：初始化活动实例的参加者集 a t s = 系统当前时间： 初始化活动实例的开始时间 a s t = r e a d y ：初始化活动实例的状态为就绪状态 a d 。= 待处理的数据：初始化活动实例的输入数据 a s = a s ： 初始化活动实例的开始条件 a e = a e ：初始化活动实例的结束条件 a r s = a r s ：初始化活动实例所需要使用的资源集， a k = a k ：初始化活动实例所使用的资源类型 建立一个工作项j ：使： i w = w i ：初始化工作项中的工作流实例的名称为相对应 工作流实例的名称 i a ：a i ：初始化工作项中的话动实例名称为相对应的工作流实例 中的活实例名称 i n = 参加者u ：初始化工作项中的参加者的名称 将工作项加入到参加者u 的工作项列表中。使： v 。l h 。v i l ! 。ui ( 2 ) 工作流过程实例w 的运行算法 1 判断活动实例a 的类型，若为原子活动，则转至第2 步，记录过程实例的 状态，进入子过程的开始结点，至第2 步。 判断起始活动实例a 的开始条件s ，与执行模式m ，若都满足，则： a t t s = 系统当前时间：将活动实例的开始执行设置成系统当前时 间。 a s t = e x e c u t i n g ： 将活动实例的状态设置成执行状态。 w t w = e x e c u t i n g ；将工作流过程实例设置成执行状态。 并执行工作项的相关任务。 当完成对此工作项的处理后，提交处理结果。即： a s t = s l e e p i n g ： 这时仅表明工作项规定的任务执行完成，不表明 该活动实例的结束。 只有当活动实例的结束条件e 满足 时，才能执行下一步： a s t = f i n i s h e d ：a t t e = 系统当前时间：这时表明该活动实例a 执行 结束。 建立一个工作项i ：使： i w = w i ：i a = a i e 接，：i n = 参加者u ： 将工作项加入到参加者u 的工作项列表中。使： v ；r 镕。= v 后缍邗u i 转步骤，直到所有活动实例执行结束： 工作流过程实例w 结束，w t w = f i n i s h e d设置工作流过程实例状态 为完成状态 2 5 本章小结 本章给出了基于网络活动状态图( n e t a c t i v i t y s t a t ed i a g r a m ，n a s d ) 的m y w o r k f l o w 工作流模型，该模型由组织模型维、数据信息模型维、资源模 型维、过程模型维组成，其中过程模型维是该模型的核心。最后给出了基于 该工作流模型的执行算法。 两个并行执行的过程实例 图3 2 可按规则进行调度的两种情况 3 3 工作流调度实例获取方法与服则 3 3 1 工作流调度实例获取方法 工作流调度实例获取可按如下方法进行：确定需要调度的资源，然后在 所有工作流实例中寻找含有该资源的实例，并通过具体的时间计算和预测， 找到存在冲突的工作流实例，然后从中获取调度实例，具体步骤如下所示： 1 ) 根据需要调度的资源在相关工作流实例中按照活动实例来搜索，找到 需要使用相关资源的过程实例。 2 ) 若资源只在一个过程内部，考虑下面三种情况： 若是“顺序结构”只选择一条分支执行，则不必进行调度，因为这些活 动不可能同时执行。 若是“或”分叉且只选择条分支执行，则不必进行调度，因为这些分 支上的活动不可能同时执行。 如果可能存在资源竞争的活动处于过程中不同的分支上，且这些分支 并行执行时( “与”分叉或者多个“或”分叉并发) 则计算使用该资源的时间 距离，若时间重叠则需要调度，否则不需要调度。因为一个过程内部各个活动 之间的紧前关系已经确定，此时可直接从工作流模型中抽取调度模型。 3 ) 若资源在多个过程内，则计算使用该资源的时间距离，看不同活动实 例占用资源的时间是否冲突，若不冲突则结束：若冲突，则从工作流模型中抽 取模型。 时间距离的计算我们采用方法文献 3 5 所提出的方法 3 3 2 工作流调度实例获取原则 找到存在执行时间重叠过程实例( 包括资源冲突的过程实例与资源非冲 突的过程实例后) ，需要先从这些过程中将相关活动抽取出来。这些被抽取 出来的活动组成了需要调度的“总过程”，即项目调度的有向图模型。从过 程实例中抽取模型所遵循的原则： 1 ) 周期性：判断执行情况并获取项目调度模型需按照一定的周期进行， 不必实时进行。 2 ) 瞬时性原则：如果工作流中各个分支之间是并发关系，对于参与资源 竞争的活动可直接抽取出来组成新的过程。 3 ) 完整性原则：按照活动之间的逻辑关系，把从相关工作流实例中当前 正在执行的活动开始到最后一个需要调度的活动( 占用资源的活动) 之间的 所有活动都抽取出来。 4 ) 对于一个分支上其它不参与资源竞争的活动，把它们的资源需求量定 为o ，在调度时只考虑它们与需要资源竞争的活动之间的紧前关系约束。 5 ) 从工作流模型中获取每个活动的时间、资源约束( 组织约束可作为人 力资源处理) ，构成项目调度的有向网络图。 如果占用资源的活动只在某一个工作流实例内出现，则可以直接根据过 程模型来抽取出需要调度的模型。 3 4 基于规则的调度策略 对于第一种情况，调度问题可以看成是单机调度问题，分为两种情况。 3 4 1 考虑活动本身的调度策略 1 ) 先来先服务( f i f o ) 按照任务到达的时间排队，并按照先来先服务的原 则来依次执行队列中的任务。 2 ) 最短作业优先( s p t ) 为了使工作流实例总的平均流程时间最小，采用 最短作业优先规则。 3 ) 最高响应比规则h r n ( h i g h e s tr e s p o n s e r a t i o n e x t ) 最高响应比方法 ( h r n ) 是对s p t 和f i f o 方法一种综合平衡。h r n 策略同时考虑每个任务的等待 时间和执行时间，从中选择响应比最高的活动执行。响应比定义为： r = ( w + t ) t = l + w t( 4 ) 其中：t 为活动的计划执行时间，w 为活动实例在队列中的实际等待时间。 在调度时，首先计算每个活实例的响应比r ，选择r 最大的调度执行。这样，即 使是执行时间很长的活动，随着等待时间的增加w t 也就随着增加，也就有机 会被调度执行。 3 4 2 考虑过程全局的调度策略 从过程的角度来考虑问题，进行全局优化，可采用的规则有： 1 ) 过程最早到期时考虑过程全局的调度策略间规则。 2 ) 最短后继活动执行时间规则s s t ( s h o r t e s t su c c e s s o r t i m e ) 。 3 4 3 基于封锁的调度策略 采用冲突任务提出请求，工作流调度系统按一定顺序实施封锁，即在冲 突类实例集中只有时问戳最小的任务才可以申请封锁( 共享锁，排它锁) 。 封锁具体过程为：当工作流实例执行到冲突的任务时，它首先到对应的 冲突类实例集中判断其是否是时间戳最小的。如果是，该任务实例可以申请 封锁其冲突数据对象。如果不是，任务挂起，并在一定的时间间隔后再进行 这样的判断。当申请锁完成后，在冲突类实例集中删除该实例，只有封锁成 功，任务才可以执行 3 3 。 3 5 基于遗传一蚂蚁混合任务调度算法 对于同一个过程实例内部的多个分支上分别存在多个活动参与可更新 资源竞争的情况，或者不同的过程实例中分别有多个活动实例参与可更新资 源竞争的情况，可建立如下概念性数学模型： m i nt 。， ( 5 ) s t t 。一t 。d 。 ， j p 。 ( 6 ) 懂群，f = 1 ，2 ，毛；= 坛，彪( 7 ) j e 其中s ，为工作的开始时间，肜为可更新资源的可用量，a t 为在( t 一1 ，t 时间段内进行的工作集合。 式( 5 ) 为目标函数，代表项目工期最短：式( 6 ) 为紧前关系约束：式( 7 ) 保 证在每一阶段使用的可更新资源量不能大于它的可用量。 对于该问题，本文采用遗传一蚂蚁混合任务调度算法，其基本思想是汲取 两种算法的优点，克服各自的缺陷，优势互补在时间效率上优于蚂蚁算法， 在求精解效率上优于遗传算法，是时间效率和求解效率都比较好的一种新的 启发式方法 下面介绍此算法中所涉及到的遗传算法，蚂蚁算法，最后是遗传一蚂蚁 混合任务调度算法。 3 5 1 遗传算法 遗传算法( g a s ) 是2 0 世纪发展起来的一种优化方法。 遗传算法的基本定理和大量的数学证明可以在h 0 1 l a n d l9 7 5 年出版的 a d a p t i o ni nn a t r u a la n da r t i f i c i a ls y s t e m s 一书中找到，该书是遗 传算法的经典之作 3 6 ，掀起了遗传算法研究与应用的第一次浪潮。 g 0 1 d b e r g1 9 8 9 年在g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n d m a c h i n el e a r n i n g 一书对遗传算法的方法，理论和应用全面系统的总结， 掀起了遗传算法研究与应用的第二次浪潮 3 7 现在遗传算法被认为是解决复杂高维空间问题的一种新方法，已广泛地 应用到各种优化问题中 3 8 。如函数优化、自动控制、机器学习 3 7 、人工 神经网络 3 9 、优化调度 3 7 等领域。 与传统方法相比。遗传算法的主要特点是【4 0 ：g a s 使用参数的编码集， 而不是参数本身进行操作；g a s 是在点群中而不是在一个单点上进行寻优：g a 仅使用问题本身所具有的目标函数进行工作，而不需要其它任何先决条件或 辅助信息：g a s 使用随机转换规则而不是确定性规则来工作 4 1 。 下面给出遗传算法的基本概念。 编码：将问题的潜在解用一些参数表示，这些参数( 基因) 排列在一起形 成一个特定的编码( 染色体) ，代表一个个体，每一个个体通过对应的解码策 略与问题的一个实际解相对应。 适值函数：根据求解空间特性定义的反应个体对问题环境适应能力和优 劣程度的函数。 复制：复制又称选择，指按照个体的适值进行，适值高的个体拥有更多 经则被选中的机会，因而拥有更大的存活概率，并将其优良特性遗传给后代。 常使用的复制方法是轮盘赌方法。 设种群规模为n ，个体i ；，适值为f ( i ；) ，个体i 。被复制的概率为 加卜哉 交叉：设个体染色体长度为l ，随机产生一个交叉位置，即 1 ，l i 上的一个 整数，作为交叉点。在交叉点将参与运算的两个个体的染色体分别分成两段， 两个后代个体从两个父代个体各继承一段染色体，形成新一代的个体。根据 问题的不同，遗传算法中还采用其它形式的交叉方法。 变异：根据一定的变异概率随机地改变染色体中的一个或多个基因的位 置和基因值的过程。通过变异可以保持种群的多样性。 终止准则：遗传算法是一个迭代算法，一般给定一个固定的迭代 示活动的执行模式：手动执行或自动执行。 定义2 3 3 跃迁路由l 目| 优个体数r ： 2 生成初始种群p o p o ，计算初始种群的个体适值： 3n = 0 ： 4d o w h i l en g e n e r a t i o n 比例复制p o p s i z e 个个体并两两匹配： 利用变异算子对p o p 。进行操作，生成p o p ： 计算p o p 。每个个体的适值： 从p o p 中选择r 个最优个体，从p o p 中选择p o p s i z e r 个最优个体形成 p o p 。+ t ： n = n + l ： e n d d 0 5 输出最优个体。 编码：算法采用紧前关系相容链表作为个体的编码。 适值函数：s r c p s p 的目标函授为工程的工期最短，属于极小化问题，因此遗 传算法中个体i 的适值函数为：f ( i ) = d s t j ，d 为最近几代中所有个体对 应的最大工期，s t 。为对个体i 解码所得调度计划中工作j 的开始时间，也就是 哥标函数值。 初始种群的产生：初始种群的个体由两部分组成，一部分随机产生，一 部分基于优先规则产生。由于算法为最优保存遗传算法，所以能够保证最后 得到的解至少与基于规则所产生的解具有同样的目标函数值，而随机产生的 个体则保证了初始个体的多样性。 基于优先规则产生紧前关系相容链表的过程与串行调度方案的产生 过程类似，但不考虑资源约束。 复制：复制采用轮盘赌的复制方法。记种群规模为p o p s i z e ，个体i ，的 适值为“l l 则个体l ，被复制的概率为r p 。芝尝美景 交叉算子：记参与交叉运算的两个个体为父亲f 和母亲睢，选择一随机整 数p ，i v a l u e 、，并计算这类工作项对用户i 而言的 工作负载w l t ：为该用户s c 次成功执行花费时间的平均值a v e r = 圭妻们心， ( 其中：w 砖表示参与者i 成功完成一次第k 项任务的负载) ， 步骤5 结束。 4 3 2 2 。w 钟的计算 假定有m 个工作流参与者参与当前工作流任务的执行。用w 时表示工作 流参与者i ( 1 i m ) 的第k 个待执行任务的工作负载，且该用户已经分配到 t 个待执行任务则用。w f f ? = w f 寸表示参与者i 当前工作负载总和。 t l l 3 2 3 。w 畔的计算 针对m 个工作流参与者，其负载总量计算算法如下所示： 1 置i = 1 ： 2 由算法2 1 2 1 计算w f f j ，五 3 i f 五= ct h e n1 0 a d s u m = w l t 。e l s el o a d s u 珂= k w 钟 4 p ，f = 五( w p + 1 0 a d s u m ) 5 置i = i 十1 ，循环执行s t e p 2 ，s t e p 3 ，s t e p 4 ，直到i = m 为止： 6 对所有的硼( i = l ，2 ，m ) 求和，伽= 。叫 l i 7 结束 4 3 2 3 参与者负载得分 我们参照shen minx in 等的论文 5 5 ，即工作负载重的员工应 该得到较低的描述合适程度分数，并用下列等式描述： e 一。( u ) = ( 。w 肿一。w 酢) ( ，( 肚w 蝉一。w 畔) ) 4 3 3 任务紧急程度确定 任务紧急程度是一个模糊概念，因此我们以模糊集理论来描述任务的 紧急程度。紧急程度的原予单词有大、中、小，加上适当的语气算予 7 0 后， 构成难度语言变量值集合 很小，小，中，大，很大 ，对应的模糊数为 ( ( o ，0 ，0 ) ，( o 。o 1 5 ，o 3 5 ) ，( 0 1 5 。o 3 5 ，o 5 5 ) ，( o 3 5 ，o 5 5 。0 7 5 ) ，( 0 5 5 ，o 7 5 ，1 0 ) 。对每一语言值给定一三角模糊数r 我们以e 。( 塔) 表示待分配任务集合t s 。中任务i 的紧急程度， 4 3 5 任务之间的关系 s ( kkc 。) ：丝型掣丛鲨学生剑( 1 ) 一，p 口0 ，【w ( ，g ) n w ( 厶w ，a ) 】 ( 1 ) 式评估了待分配任务j 。和员工u 的工作列表中第j 项任务在技能ct 上的相似性结果是定值。 s ( j mj 。) 2 ：。s ( ， 一，g ) ( 2 ) ( 2 ) 式得到了j ；，和j ，之间的相似性，结果是定值。 e s w ( u ) = 吉：s ( 西， m ) ( 3 ) ( 3 ) 式决定了j 。和已经分配给员工u 的所有任务之间的相似性结果是一 个模糊数。 4 3 6 员工对任务感兴趣程度 6 4 用，( u ，巧) 表示员工ui 对任务jj 的感兴趣程度，如果员工的感兴趣程 度越高，相应地他就会得到更高的适合该任务的分数。下式可以得到员工对 任务的感必趣程度 e 肿( u ) = 【( ) 一二：，( u ，西) 弘( 4 ) 肌面 员工对任务的感兴趣程度，公式( 4 ) 中t 表示可以分配的任务种类的个 数： 为调整系数， 越大，兴趣对任务分配的影响就越大对 进行调节，就 可以轻松地对员工的兴趣对任务分配影响的程度进行调节当公司希望多样 化地分配任务时，就可以增大 ，让员工多样化地选择工作如果公司不希望 多样化分配的时候，可以使 = 0 ，这样就可以按照任务的相似性来分配任务 了将员工的感兴趣程度分为5 个等级：不感兴趣、不太感兴趣、一般、比较 感兴趣和非常感兴趣，对应的模糊数为 ( 0 ，o ，o 1 ) ，( o ，o 3 ，o 5 ) ，( o 3 ，o 5 ，0 7 ) ，( 0 5 ，o 7 。o 9 ) ，( o 7 ，o 9 ，1 0 ) 员工需要事先定义好自己在目前这些种类的任务的感兴趣程度，在工作 流管理系统执行过程中，当需要对这些任务进行分配的时候就会将这些程度 作为考虑的因素之一，最终做出考虑到了员工意愿的任务分配，更好地体现 了系统的人性化的一面如果员工不定义自己对任务的感兴趣程度，系统将 会使用默认值。即对任何任务都是一般感兴趣，使用( o 3 ，o 5 jo 7 ) 为员工的 平均感兴趣度 1f p ( = ，( u ，o ) j = l 如果员工对多个任务都十分有兴趣，那么，他的这一项分值会比较高，相 反则会较低返在某种程度上可以反映该员工对工作的态度。 4 3 7 社会关系 5 4 等式e 触= 者o 。e n ( 翰，醵) 表示团队社会关系的总分数，式中f 表 u 2 示团队成员的个数，c ，= ，( 厂一1 ) 2 表示团队成员的关系数，f n ( 坼，阴) 表 示团队中，员工u 。与u 。社会关系的得分。将员工的社会关系分为5 个等级：最 差，较差，一般，较好。最好( w o r s t ，p o o r ，f a ir ，g o o d ，a n db e s t ，) ， 与之对应的模糊数为 ( o ，o ，o 1 5 ) ，( 0 ，o 3 5 ，o 5 5 ) ，( 0 3 5 ，0 5 5 ，o 7 5 ) ，( 0 5 5 ，o 7 5 ，0 9 5 ) ，( o 7 5 ， 0 9 5 。1 0 ) 等式e c w o = ? e ，”d ( u j ) 表示有m 个成员组成团队的合适程度 等中凸v d ( u ) 表示员工执行任务j 的适合程度。 一 z h d ( u ) 2e d p ( c ，) oe m ，( u ，) 0e d ( ) 0e 加( u ，) oe n ( u ) 等式删= e d m o e m 表示一个候选团队在加入了社会关系对任务分 配策略的影响之后的合适程度。 4 4 工作流任务分配算法 下面假设待分配任务集合t s 共有疗项任务，完成任一个待分配任务所需 的人员数相等，即完成待分配任务的候选团队的人数都为m 个。 4 8 配给改团队。 步骤8 将待分配任务集合中刚分配的任务移到已分配任务集合中，将刚分 配到任务的人员从候选人员集合中删除，将刚建立起来并分配到任 务的团队放到老的团队集合之中，并修改修改该团队的工作负载。 步骤9 重复步骤l 一步骤8 ，直到任务分配完毕。 4 5 小结 本章所设计的m y w o r k f l o w 的用户型任务分配策略对 5 5 等文献所提 出任务分配策略进行了改进，并且任务分配策略中增加了任务紧急程度与员 工对任务的感兴趣程度两个因素，改进后的分配策略由五个因素( 能力、社 会关系、任务之间的关系、员工对任务的感兴趣程度和任务紧急程度) 决定 任务分配