一种基于工作流图的时间资源分配策略

第２６卷第９期　计算机应用　Ｖｏ１．２６　Ｎｏ．９　２００６年９月　Ｃｏｍｐｕｔｅｒ　Ａｐｐｌｉｃａｔｉｏｎｓ　Ｓｅｐｔ．２００６　文章编号：１００１—９０８１（２００６）０９—２１６６—３　一种基于工作流图的时间资源分配策略　刘丹妮，陈秀寓　（东北大学东软信息学院，辽宁大连１１６０２３）　（１ｉｕｄａｎｎｉ＠ｎｅｕｓｏｆｔ．ｅｄｕ．ａｎ）　摘要：研究了工作流中时间分配问题。在具体活动基础上增加标记活动，以记录所在路由分支　的资源使用情况；将时间看作一种不可更新资源，并将时间资源分为私有资源、公有资源和双重资源　三类；提出了一种路由结构的时间资源分析方法和分配算法，根据不同路由分支的特点及初始分配　资源在实际执行过程中的使用情况，通过裂变与聚合进行时间资源再分配，保证整个工作流的顺利完　成。通过实例说明工作流图中时间资源分配过程。　关键词：工作流；时间资源；松弛时间　中图分类号：ＴＰ３０２　文献标识码：Ａ　Ａ　ｓｔｒａｔｅｇｙ　ｆｏｒ　ｔｉｍｅ　ｒｅｓｏｕｒｃｅ　ａｌｌｏｃａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　ｗｏｒｋｆｌｏｗ　ｇｒａｐｈ　ＬＩＵ　Ｄａｎ—ｎｉ．ＣＨＥＮ　Ｘｉｕ一１Ｉｒｕ　（／Ｖｅｕ，ｏ￣Ｉｎｆｏｒｍａｔｉｏｎ　Ｉｎｓｔｉｔｕｔｅ，Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｗｅｍｉｔｙ，Ｄａｌｉａｎ　Ｌｉａｏｎｉｎｇ　１１６０２３，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｉｍｅ　ａｌｌｏｃａｔｉｏｎ　ｉｎ　ｗｏｒｌｄｌｏｗ　ｗａｓ　ｓｔｕｄｉｅｄ．Ｆｉｍｆｌｙ，ｌａｂｅｌｄｅ　ａｃｔｉｖｉｔｉｅｓ　ｗｅｒｅ　ａｄｄｅｄ　ｉｎ　ｏｒｄｅｒ　ｔｏ　ｍａｋｅ　ｒｅｃｏｒｄｓ　ｏｆ　ｔｈｅ　ｒｅｓｏｕｒｃｅｓ　ｕｓａｇｅ　ｏｎ　ｅａｃｈ　ｒｏｕｔｅ　ｏｒｉｇｉｎ．Ｓｅｃｏｎｄｌｙ，ｔｉｍｅ　ｗａｓ　ｒｅｇａｒｄｅｄ　ａｓ　ａ　ｋｉｎｄ　ｏｆ　ｎｏｎ—ｅｒｎｅｗａｂｌｅ　ｒｅｓｏｕｒｃｅｓ，ａｎｄ　ＷａＳ　ｃｌａＳｓｉｉｆｅｄ　ｉｎｔｏ　ｔｈｒｅｅ　ｔｙｐｅｓ：ｐｒｉｖａｔｅ，ｐｕｂｌｉｃ　ａｎｄ　ｍｉｘｅｄ．Ｔｈｉｒｄｌｙ，ａｎ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｔｉｍｅ　ｒｅｓｏｕｒｃｅ　ａｎａｌｙｓｉｓ　ａｎｄ　ａｌｌｃｏａｔｉｏｎ　ＷａＳ　ｐｒｏｐｏｓｅｄ．Ｉｎ　ｔｈｅ　ｅｂｇｉｎｎｉｎｇ，ｔｉｍｅ　ｒｅｓｏｕｒｃｅ　ＷａＳ　ｐｒｅ—ａｌｌｏｃａｔｅｄ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｃｈａｒａｃｔｅｒｉｓｔｉｃｓ　ｏｆ　ｄｉｆｅｒｅｎｔ　ｒｏｕｔｉｎｇ，ｔｈｅｎ　ｄｕｒｉｎｇ　ｈｔｅ　ｐｒｏｃｅｓｓ　ｏｆ　ａｃｔｕａｌ　ｏｐｅｒａｔｉｏｎ，ｔｉｍｅ　ｒｅｓｏｕｒｃｅ　ｗａＳ　ｒｅａｌｌｏｃａｔｄｅ　ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｉｍｅ　ｃｏｎｓｕｍｉｎｇ　ｓｉｔｕａｔｉｏｎ　ｂｙ　ｔｈｅ　ｍｅｔｈｏｄ　ｏｆ　ｓｐｌｉｔｔｉｎｇ　ａｎｄ　ｃｏｎｖｅｒｉｇｎｇ．Ｆｉｎａｌｌｙ，ａ　ｅａＳｅ　ｓｔｕｄｙ　ｉｌｌｕｓｔｒａｔｄｅ　ｔｈｅ　ｔｉｍｅ　ｒｅｓｏｕｒｃｅ　ａｌｌｃｏａｉｔｏｎ　ｐｒｏｃｅｓｓ　ｉｎ　ｗｏｒｋｆｌｏｗ　ｇｒａｐｈ．　Ｋｅｙ　ｗｏｒｄｓ：ｗｏｒｌｄｌｏｗ；ＴＲ（ｔｉｍｅ　ｅｒｓｏｕｒｃｅ）；ＴＳｌａｅｋ（ｔｉｍｅ　ｓｌａｃｋ）　０　引言　动不紧急，则将这些资源和相应时间的权限一同对该活动开　放。时间起到对其他资源权限的开放和关闭作用。　近年来，在科学研究和实践中，工程的时序安排越来越多　本文基于文献［７，８］的工作流模型，给出标记活动和具　地受到学者关注。Ｂｒｕｅｋｅｒ对资源环境、活动特征和客观功能　体活动的概念，通过对时间资源的特性分析，将时间资源分为　等进行分类，对资源约束的单一模式和多重模式应用启发式算　私有资源、公有资源和双重资源三类。对四种结构中的活动　法进行了活动执行序列的讨论　Ｊ。Ｓｅｎｋｕｌ提出了模拟资源消　和路由分支进行时间资源与松弛时间的界值确定。依据以上　耗和资源分配信息的语言，含有约束解决方案的进度表模型将　分析，给出时间资源的分配算法，详细描述了时间资源分配策　得到的工作流描述转换成约束语言，生成满足资源分配约束的　略，以及松弛时间的裂变和聚合。最后通过实例演示了算法　时刻表　。Ｈｏｎｇｅｈｅｎ将时间工作流进行扩展，对工作流描述　的分配过程。　的资源一致性进行验证的同时考虑了时间约束条件∞Ｊ。依据　业务实例在工作流四种路由结构的逗留时间分布，给出以资源　１　工作流模型　单位时间消耗成本最小化为目标的求解最优资源数量的方　在实际的工作流中，常有可跨越活动和可替换路径，对可　法　。目前很多文献将时间作为约束条件分析资源模型中人　跨越活动适当取舍和可替换路径适当选择，会提高工作流的　员、设备、软件等资源的分配和调度情况¨刮，但是将时间作为　执行效率。以文献［７，８］的工作流模型为基础，把时间纳入　不可更新资源纳入资源范畴，与其他资源统一分配和回收，取　资源范畴，对活动、分支和路由结构进行时间资源分配。　消模型外部时间约束的分配策略几乎未见报道。本文将研究　，Ｉ和ｏｕｔ分别表示工作流的入口和出口。活动节点形式化　时间作为资源在四种路由结构中的分配情况，以及工作流图中　地描述为：ｎｏｄｅ（　）＝（ＤＵＲ，Ｅ，Ｌ，ｏｐｔ．）；这里，Ｅ＝（Ｅ　，Ｅｂｓ，　活动、各种路由分支的时间分配策略。　Ｅｗｆ，Ｅｗｓ），Ｌ＝（　，Ｌｂｓ，Ｌｗｆ，Ｌｗｓ）。ｏｐｔ．∈｛０，１｝，ｏｐｔ．＝１表示　工作流的过程模型由资源模型、组织模型、功能映射模型　ｉ是可跨越活动，ｏｐｔ．＝０时表示ｉ不是可跨越活动。ＤＵＲ是建　和约束规则组成。约束规则中时间约束是首要约束，如能将　模阶段活动的执行延迟；ｏｐｔ．标记可跨越活动；ＥｌＬ表示此活　时间作为资源，并入资源模型，可减少约束规则描述的内容，　动的最早／最迟结束时间；ｂ／ｗ表示若出现条件分支，则选择　简化工作流模型的建模过程。将活动需要的时间、人员、设备　最优／最差分支运行；　表示跨过／保留所有可跨越活动，　等资源分配给某活动，当时间资源耗尽时，其他资源的权限立　并且，选择最优／最差可替换路径。　即被回收。如果这些非时间资源闲置或其他需要此资源的活　文中对该模型进行扩展，在并发结构和选择结构的分又　收稿日期：２００６—０１—２２；修订日期：２００６—０４—０３　作者简介：刘丹妮（１９７５一），女，黑龙江哈尔滨人，讲师，硕士，主要研究方向：工作流建模技术、工作流可达性分析方法、工作流资源分配策　略；　陈秀寓（１９７７一），女，讲师，硕士，主要研究方向：工作流模型建立方法、工作流静态验证与动态验证技术．　维普资讯 http://www.cqvip.com

第９期　刘丹妮等：一种基于工作流图的时间资源分配策略　２１６７　汇合处以及各分支末尾处分别增加活动以标记时间资源。　ＴＳｌａｃＪ｝（　）＝豫（　）一∑ＤＵＲ（　）　２）并发结构　２　时间资源分配策略　２．１　基本概念　并发结构中存在多个并发分支，各分支分配相同的资源，　由于活动实例不同，各分支的松弛时间会有不同（如图１），每　个分支的豫和ＴＳｌｃｋ记录在该分支末尾的标记活动上。以　ａ分支为例，资源分配情况如下：　豫　（　）＝Ｅｂｆ（ｊ）一Ｅｂｆ（　）一ＤＵＲ（ｊ）；　豫～（　）＝Ｅｗｓ（ｊ）一Ｅｂｆ（　）一ＤＵＲ（ｊ）；　对文献［８］的工作流图进行扩展，在具有实际含义的具　体活动基础上增加标记活动。　定义１　标记活动：是一种只起到标记作用且没有实际　含义的活动，它不被执行，只记录它所在分支的时间分配情　况。例如：并发结构和条件结构的分叉点（ａｎｄ＿ｓｐｌｉｔ，ｏｒ＿ｓｐｌｉｔ）、　汇合点（ａｎｄｊｏｉｎ，ｏｒｊｏｉｎ）以及顺序结构的末尾节点。　定义２　具体活动：工作流图中有实际含义，可被执行的　活动称为具体活动（ａｃｔｉｖｉｔｙ，简称ａｃｔ）。　资源分为可更新资源、不可更新资源和双重约束资源。时　间的不可再生性决定了时间属于不可更新资源。作为一种资　源，时间有其特殊性：　１）可消耗性。时间也有折旧，例如有ＤＵＲ（ｔ）＝６，则分配　给事件ｔ的时间资源ｓ为６，当ｔ执行结束的时间为ｈ＝６，则ｔ　的执行使得ｓ的折旧率达到了１００％；否则，（６一ｈ）作为ｔ的　松弛时间，并入ｔ所在分支。　２）可裂变。时间具有非原子性。活动、分支或路由结构执　行未结束时出现资源耗尽，可向上一级申请资源支持，上级结　构将松弛时间出一部分分配给请求者的过程称为裂变。　３）可聚合。活动、分支或路由结构执行结束时，剩余资源　的权限提交给上一级并与上级资源合并的过程称为聚合。　时间资源分为三种：私有资源、公有资源和双重资源。　定义３　私有资源：私有资源用来描述路由结构、分支或　活动ｋ的独有资源，记为ＴＲ（ｋ）。该资源一旦分配给ｋ，就被ｋ　独占，ｋ执行结束时的松弛时间记为ＴＳｌｃａｋ（Ｊ｝），可按照资源　分配策略进行聚合。　定义４公有资源：公有资源用来描述工作流实例别　的　松弛时间，记为ＴＳｌａｃｋ（ＷＦ）。所有活动实例或结构分支在资　源不足时，都有权限按照裂变规则请求裂变ＴＳｌａｃｋ（ＷＦ）。　定义５　双重资源：双重资源用来描述路由结构中任一　分支　的松弛时间，记为ＴＳｌｃａｋ（　）。它具有私有资源和公有　资源的双重特征。　中的任一活动ｋ未结束时出现ＴＲ（ｋ）耗　尽，可申请裂变ＴＳｌｃａｋ（　）。同时，只有理中的活动有权申请裂　变ＴＳｌａｃｋ（　），　分支执行结束时，ＴＳｌａｃｋ（　）剩余资源失效或　者聚合，具体情况依据　所在路由结构和资源分配策略而定。　结束时的剩余资源记在该分支的标记活动ｋ上，记为　ＴＳｌａｃｋ（ｋ）。　ＴＲ（ｋ）∈［豫　（ｋ），豫～（ｋ）］，ｋ为活动或分支。　豫　（ｋ）＝ＤＵＲ～（ｋ），豫～（ｋ）：ＤＵＲ．￣（ｋ）。ＴＳｌａｃｋ（ｋ）　∈［ＴＳｌａｃｋ　（ｋ），ＴＳｌａｃｋ．￣（ｋ）］。　任意分支　的标记活动－『描述为（豫～（　），豫～（　），　ＴＳｌｃａｋ．￣（卢），ＴＳｌａｃｋ．￣，（　））。　２．２　各种路由结构时间资源分析　１）顺序结构　顺序结构中只有一个分支　，按活动　（　∈（　，…，　，））的执行时间分配私有资源ＴＲ（　），活动执行时出现资源　不足时，请求裂变上层资源。因为ＤＵＲ．￣（ｋ）：Ｄ　～（ｋ）＝　ＤＵＲ（ｋ），所以有下述关系存在：　ｒＲ（　）＝ＤＵＲ（　）；　ＴＳｌａｃｋ　（　）：豫　（　）一∑ＤＵＲ（＾　ｌ　ａ＾）；　ｆ∞Ｊ｝～（　）＝豫～（口）一∑ＤＵＲ（ａ＾）；　＝＝嚣扭　图１并发结构　＝＝嚣参　图２条件结构　３）条件结构　条件结构中存在多个分支，各分支资源分配情况由活动　决定，松弛时间不尽相同。如图２。　豫～（　）＝Ｅ　ａ　）一Ｅ　ａ。）＋ＤＵＲ（ａ１）；　豫～（　）＝Ｅｗ３（ａ　）一Ｅｂｆ（ａ１）＋ＤＵＲ（ａＩ）；　＾　ＴＳｌａｃｋ　（　）＝豫～（　）一∑ＤＵＲ（＾＝ｌ　ａ＾）；　＾　ＴＳｌｃａｋ．￣，（　）＝豫～（　）一∑ＤＵＲ（口＾）；　４）循环结构　循环分支　的最少执行次数为０，最大执行次数由该分支　的最大概率循环次数Ａ决定，Ａ根据经验确定。　豫　（　）＝０；豫～（　）：Ａ　ＤＵＲ（　＾）；　＾＝１　ＴＳｌａｃｋ￣（　）＝０；ＴＳｌｃａｋ．￣，（　）＝０　２．３　工作流图的时间分配策略　从工作流入口开始，依次访问每一个节点，按活动执行时间　为其分配资源。遇到并发结构、选择结构或循环结构的分叉点时，　找到相应的汇合点，分别依据各分支的特点，按照顺序结构分配　时间资源。活动执行过程中资源不足或剩余，可向所在分支申请　裂变或聚合双重资源。结构分支执行过程中资源缺乏或过剩，向　上一层结构请求裂变或聚合双重资源和公有资源。　Ｂｒａｎｃｈ（ｏｒ＿ｓｐｌｉｔ）是条件结构中ｏｒ＿ｓｐｌｉｔ节点后继分支的集　合，令Ｂｒａｎｃｈ（ｏｒ＿ｓｐｌｉｔ）＝｛田，　｝；Ｂｒａｎｃｈ（ａｎｄ＿ｓｐｌｉｔ）是并发结　构中ａｎｄ＿ｓｐｌｉｔ节点后继分支的集合，令Ｂｒａｎｃｈ（ａｎｄ＿ｓｐｌｉｔ）：　｛　，ｃｃ，｝。时间资源分配算法详细描述如下：　依次遍历每一个活动节点ｋ，　ＩＦ（ｋ＝＝ａｃｔ）ＴＨＥＮ　按照顺序结构的分配策略为ｋ分配ＴＲ（　），　在执行过　程中不断消耗ＴＲ（ｋ），　当ＴＲ（ｋ）＝０时，ｋ未执行完，则请求裂变ｋ所在分支　的ＴＳｌａｃｋ（　），令ＴＳｌａｃｋ（　）＝ＴＳｌａｃｋ（　）一　维普资讯 http://www.cqvip.com

２１６８　计算机应用　２００６盎　豫　（ｋ），ＴＲ　（ｋ）是根据实际情况确定的ｋ所需要的后　续资源。　执行活动Ｃ（进入库房点货），否则与客户沟通延期发货（活　动Ｄ），并告知销售部经理（活动Ｅ）、告知销售小组组长（活　动Ｆ）、通知生产部门经理（活动Ｇ）和生产小组组长（活动　当ｋ执行结束时，ＴＲ（ｋ）＞０，则将剩余资源ＴＳｌａｃｋ（ｋ）　与ｋ所在分支ｏｔ的ＴＳｌａｃｋ（ｏｔ）聚合，令ＴＳｌａｃｋ（ｏｔ）＝　ＴＳｌａｃｋ（ｏｔ）＋ＴＳｌａｃｋ（ｋ）。　ＥＮＤ　ＩＦ　Ｈ），然后组织生产（活动Ｉ），其中Ｅ和Ｈ是可跨越的。两条　件分支汇合后为客户开出发货单（活动Ｊ），告知客户准备发　货（Ｋ）与货物装箱（Ｌ）并发执行，填写销售登记表（Ｍ）后选　择空运（Ｎ）、陆运（Ｏ）或海运（Ｐ）方式运输，最后与客户结账　ＩＦ（ｋ＝＝ｏｒ＿ｓｐｌｉｔ）ＴＨＥＮ　找到与其对应的汇合点ｏｒ＿ｊｏｉｎ；　对于任意ｏｔ∈Ｂｒａｎｃｈ（ｏｒ＿ｓｐｌｉｔ），按照条件结构的分配　（Ｑ）。ｏｒｌ，ｏｒ２，ａｎｄｌ，ａｎｄ２，ａｌｔｌ，ａｈ２和ａｈ３分别是各分支标记　节点。ｏｒ＿ｓｐｌｉｔ，ｏｒ＿ｊｏｉｎ，ａｎｄ—ｓｐｌｉｔ，ａｎｄ－ｊｏｉｎ，ａｌｔｅｒｎａｔｉｖｅ—ｓｐｌｉｔ和　规则，找到各分支的豫　（ｏｔ）和豫～（ｏｔ）。　豫（田）＝ＴＲ（　）＝Ｍａｘ（豫～（田），豫～（　））；　ＴＲ（妒）＝Ｍａｘ（豫～（田），豫～（　））；　ＴＳｌａｃｋ（田）＝ＴＤ（田）一豫～（田）；　ＴＳｌａｃｋ（妒）＝ＴＤ（　）一豫～（　）　ｏｔ分支一旦执行，其他非ｏｔ分支的豫和ＴＳｌａｃｋ资源消　亡。　ｏｔ分支执行结束时，剩余资源的权限作为该分支所在　结构的剩余资源向上一层路由结构聚合，　ＴＳｌａｃｋ（ｏｒ＿ｊｏｉｎ）＝ＴＳｌａｃｋ（ｏｒ１），０ｒ１是ｏｔ分支的标记　Ａ　Ｂ　Ｃ　Ｄ　Ｅ　Ｆ　Ｇ　Ｈ活动。　ＥＮＤ　ＩＦ　ＩＦ（ｋ＝＝ａｎｄ＿ｓｐｌｉｔ）ＴＨＥＮ　找到相对应的汇合点ａｎｄ＿ｊｏｉｎ，对于任意ｏｔ∈　Ｂｒａｎｃｈ（ａｎｄ＿ｓｐｌｉｔ），按照并发结构的分配规则，找到各　分支的豫～（ｏｔ）和豫～（ｏｔ）　ＴＲ（　）＝ＴＲ（０９）＝Ｍａｘ（豫～（　），豫～（０９））；　ＴＲ（０９）＝Ｍａｘ（豫～（　），豫～（０９））；　ＴＳｌａｃｋ（　）＝ＴＤ（　）一豫～（　）；　ＴＳｌａｃｋ（０９）＝ＴＤ（０９）一豫～（０９）。　并发结构各分支均执行结束时，ＴＳｌａｃｋ（ａｎｄ＿ｊｏｉｎ）＝　ＭＡＸ（ＴＳｌａｃｋ（ａｎｄ１），ＴＳｌａｃｋ（ａｎｄ２）），ａｎｄｌ和ａｎｄ２分　别是　和０９的标记活动。ＴＳｌａｃｋ（ａｎｄ＿ｊｏｉｎ）作为并发结　构的松弛资源向上层路由结构聚合。　ＥＮＤ　ＩＦ　ＩＦ（ｋ＝＝ｃｉｒｃｌｅ）ＴＨＥＮ　根据实际情况确定循环分支ｏ／的最大概率执行次数　Ａ，依据循环结构的分配规则，令ＴＲ（ｏｔ）＝豫～（ｏｔ），　ＴＳｌａｃｋ（ｏｔ）＝０。　ＥＮＤ　ＩＦ　３　实例分析　图３一个生产销售实例　如图３，Ａ表示销售部接到客户订单，Ｂ表示销售部查看　库存量，根据库存量选择不同的分支，能够满足客户需求时，　ａｌｔｅｒｎａｔｉｖｅ＿ｊｏｉｎ分别是各路由结构的分叉和汇合节点。对具　体活动的时间描述如表１所示。　表１活动节点的时间描述　ｎｏｄｅ　活动的时间描述　（１，（１，１，１，１），（１，１，１，１），０）　（２，（３，３，３，３），（３，３，３，３），０）　（２，（５，５，５，５），（５，５，８，１１），０）　（１，（４，４，４，４），（１，一２，４，４），０）　（２，（４，６，４，６），（１，０，４，６），１）　●Ｊ　Ｋ　Ｌ　Ｍ　Ｎ　０　Ｐ　Ｑ　（１，（５，７，５，７），（２，１，５，７），０）　（１，（６，８，６，８），（３，２，６，８），０）　（１，（６，９，６，９），（３，３，６，９），１）　（２，（８，１１，８，１１），（５，５，８，１１），０）　（１，（６，６，９，１２），（６，６，９，１２），０）　（１，（７，７，１Ｏ，１３），（８，８，１１，１４），０）　（２，（８，８，１１，１４），（８，８，１１，１４），０）　（１，（９，９，１２，１５），（９，９，１２，１５），０）　（１，（１Ｏ，１Ｏ，１３，１６），（１Ｏ，１２，１３，１８），０）　（２，（１１，１１，１４，１７），（１０，１２，１３，１８），０）　（３，（１２，１２，１５，１８），（１Ｏ，１２，１３，１８），０）　（３，（１４，１６，１７，２２），（１４，１６，１７，２２），０）　从ｉｎ开始遍历每一个活动，依据活动执行时间为具体活　动分配时间资源：ＴＲ（Ａ）＝１，ＴＲ（Ｂ）＝２，…。下面重点讨论　各路由结构分配情况：　访问到ｏｒ＿ｓｐｌｉｔ节点，找到与其对应的ｏｒ＿ｊｏｉｎ，用标记活　动ｏｒ１和ｏｒ２分别标记该条件结构中的两个分支　和Ｂ；访　问到ａｎｄ—ｓｐｈｔ活动，找到对应的ａｎｄ－ｊｏｉｎ，用ａｎｄｌ和ａｎｄ２分　别标记并发分支　和８；访问到ａｌｔｅｒｎａｔｉｖｅ—ｓｐｌｉｔ节点，找到对　应的ａｈｅｒｎａｔｉｖｅ＿ｊｏｉｎ，用ａｌｔｌ，ａｈ２和ａｈ３分别标记各替换分支　０，－ｉ１和　。标记活动记录所在分支可能分配拥有的最小资　源、最大资源、实际分配的时间资源和松弛时间。标记活动分　别描述如下：　ｏｒｌ：（５，８，８，ｏ）；ｏｒ２：（２，２，　６）；ａｎｄｌ：（１，１，１，１）；ａｎｄ２：（２，２，　ｏ）；　ａｌｔｌ：（１，１，１，２）；ａｌｔ２：（２，２，２，１）；ａｌｔ３：（３，３，３，ｏ）；ｃｉｃｌｅ：（３，４，４＇ｏ）　在实际执行过程中，根据资源消耗情况可对双重资源或　公有资源裂变和聚合。执行到ｏｒ＿ｓｐｌｉｔ节点时，假设经过条件　判断进入Ｂ分支。ｃ活动分配的资源是２，由于突发事件，２　单位时间消耗完时，ｃ未执行结束。因为ＴＳｌａｃｋ（Ｂ）＝６，所以　可向Ｂ分支申请裂变一定量的资源。申请数量如果大于６，　多余部分要向ＴＳｌａｃｋ（ｗＦ）申请。如果ｃ活动执行完毕只消　耗１单位，剩余的１单位松弛时间与ＴＳｌａｃｋ（Ｂ）聚合，此时ｏｒ２　标记的ＴＳｌａｃｋ（Ｂ）＝７，Ｂ分支结束时，ＴＳｌａｃｋ（Ｂ）向上与　ＴＳｌａｃｋ（ｏｒ＿ｊｏｉｎ）聚合，最后与ＴＳｌａｃｋ（ｗＦ）聚合。　（下转第２１７１页）　维普资讯 http://www.cqvip.com

第９期　王德志等：基于多克隆策略的应用层组播路由算法　２１７ｌ　州，按照变异概率取代抗体上原有的值，从而生成新抗体群　Ｄ（ｔ）。若产生的解不满足组播树条件，则重新进行克隆变异　操作。　（６）克隆选择　对父代抗体群Ａ（ｔ）和变异后的克隆抗体群Ｄ（ｔ）进行克　的抗体群规模　），且每次计算开始时遗传算法的初始群由　克隆算法的初始抗体群复制得到，以使三种算法的初始数量　和分布上处在同一水平上。遗传算法的突变概率为０．０５，交　叉概率为０．９。　仿真结果图２为采用免疫克隆算法得到的应用层组播　树。通过进行２００次仿真取平均值，得到三种算法的性能比　较，如表１所示。从表中可以看出基于免疫多克隆策略的组　播路由算法比遗传算法具有更快的收敛速度，并且解的性能　隆选择操作，利用亲和度函数　）选出亲和度最高且互不相　同的Ⅳ个抗体组成新抗体群Ａ（ｔ＋１）。　（７）结束条件　在最优个体，则算法终止；否则转到（２）继续操作。　根据文献［６］证明，免疫多克隆策略算法的种群序列　｛Ａ（ａ），ｎ≥０｝是有限齐次马尔可夫链，并且该算法是以概　率１收敛的。　计算Ａ（ｔ＋１）中每个抗体的亲和度，若新一代抗体中存　要比其他两种算法高。　表１算法性能比较　ｃ（５ｏ）Ｇ（１００）Ｇ（１５０）ｃ（２ｏｏ）Ｇ（２５０）Ｇ（３００）Ｇ（３５０）　本文算法　３３　改进ＧＡ　３５　２９　３２　２５　２８　２３　２５　１９　２Ｏ　１７　１８　１７　１８　该算法的时间复杂度与抗体群规模Ⅳ，免疫克隆规模　，　标准ＧＡ　３６　３３　２９　２７　２４　２　２１　２０　３　４　５　６　算法的迭代次数ｔ有关，所以算法的复杂度为０（　ｔ）。　４仿真实验及结果分析　本文采用Ｍａｆｌａｂ　７．０作为仿真工具，分别采用文献［３］　５　结语　应用层组播是目前网络研究领域的研究热点。本文对基　于树的应用层组播路由算法进行了研究，建立了网络模型，提　提出的改进遗传算法、标准遗传算法以及本文提出的基于免　疫多克隆策略的路由算法。为了验证仿真结果，随机生成完　出基于免疫多克隆策略的带度约束的应用层组播路由问题。　本算法克服了遗传算法中的“早熟”现象，取得比遗传算法更　好的结果，同时，该算法具有更快的收敛速度。实验结果证　全图的网络拓扑Ｇ，节点数为８个，网络边的延迟代价为一个　范围的随机整数，并且每个节点的度约束指定为［２，ｎ／２］之　间的一个随机整数，网络拓扑如图１所示。　明，本算法具有较好的性能。　参考文献：　【１】ＤＥ　ＣＡＡＴＲＯ　ＬＮ，ＶＯＮ　ＺＵＢＥＮ　ＦＪ．Ｌｅａｒｎｉｎｇ　ａｎｄ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｕ—　ｓｉｎｇ　ｔｈｅ　ｄｏｎａｌ　ｓｅｌｅｃｔｉｏｎ　ｐｒｉｎｃｉｐｌｅ【Ｊ】．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｅｖｏｌｕ－　ｔｉｏｎａｒｙ　ｃｏｍｐｕｔａｔｉｏｎ，２００２，６（３）：２３９—２５１．　ＺＨＵ　Ｙ，ＷＵ　ＭＹ．ＳＨＵ　Ｗ．Ｃｏｍｐａｒｉｓｏｎ　ｓｔｕａｙ　ａｎｄ　ｅｖａｌｔｌａｔｉｏｎ　ｏｆ　ｏ＿　ｖｅｒｌａｙ　ｍｕｌｔｉｃａｓｔ　ｎｅ￣ｏｒｋｓ『Ａ１．Ｍｕｌｔｌｍｅｄｉａ　ａｎｄ　Ｅｘｐｏ．２００３．ＩＣＭＥ＇０３　【Ｃ】，２０ｏ３，（３）：４９３—４９６．　徐磊，章兢．广义最小生成树的遗传算法求解及其应用【Ｊ】．系　统工程与电子技术，２００４，２６（３）：３９０—３９２．　潘耘，余镇危，王励成．求解应用层组播路由问题的遗传算法　【Ｊ】．小型微型计算机系统，２００５，２６（１）：５５—５８．　余波，王东．基于加权选择函数的应用层组播路由算法【Ｊ】．计　算机工程，２０ｏ５，３１（１８）：１０５—１０７．　刘若辰，杜害峰，焦李成．免疫多克隆策略【Ｊ】．计算机研究与发　展，２００４，４１（４）：５７１－５７６．　（上接第２１６８页）　２００５，３０（５）：３９９—４２２．　４　结语　本文将时间纳入资源范畴，定为不可更新资源。通过对　路由结构的分析，提出时间资源分配算法，在建模阶段进行资　源分配，在执行过程中实现资源的动态裂变与聚合。时间是　种特殊资源，供活动消耗，同时决定着其他资源权限的开放　一【３】Ｕ　Ｈ，ＹＡＮＧ　Ｙ，ＣＨＥＮ　ＴＹ．Ｒｅ￣ｕｍｅ　ｃｏｎｓｌｒａｌｎｔｓ　ａｎａｌｙｓｉｓ　ｏｆｗｏｒｋ—　ｌｆｏｗ　ｓｐｅｃｉｉｆｃａｔｉｏｎｓ【Ｊ】．Ｔｈｅ　Ｊｏｕｒｎａｌ　ｏｆ　Ｓｙｓｔｅｍｓ　ａｎｄ　Ｓｏｆｔｗａｒｅ，２ＯＯ４，　７３（２）：２７１—２８５．　【４】　刘胜，范玉顺，尹朝万．基于工作流模型的资源配置优化方法　【Ｊ】．计算机集成制造系统，２００５，ｌ１（９）：１２７２—１２７８．　【５】　李伟平，范玉顺．基于工作流的资源受限项目调度研究【Ｊ】．清　华大学学报（自然科学版），２００４，１０（４４）：１３８４—１３８８．　【６】　綦方中，王正肖，孙永军．虚拟企业运营过程中项目调度和执行　与关闭。　参考文献：　【１】　ＢＲＵＣＫＥＲ　Ｐ，ＤＲＥＸＬ　Ａ，ＭＯＨ￣ＮＧ　Ｒ，ｅｔ　ａＬ　Ｒｅ￣ｕｍｅ—ｃｏｎ—　ｓｔｒａｉｎｅｄ　ｐｍｊｅｃｔ　ｓｃｈｅｄｕｌｉｎｇ：Ｎｏｔａｔｉｏｎ，ｃｌａｓｓｉｉｆｃａｔｉｏｎ，ｍｏｄｅｌ，ａｎｄ　ｍｅｔｈｏｄｓ［Ｊ】．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９９，１　１２　（３）：３—４１．　策略【Ｊ】．计算机工程，２００２，５（２８）：７０—７２．　【７】　ＥＤＥＲ　Ｊ．ＰＡＮＡＧＯＳ　Ｅ，ＰＯＺＥＷＡＵＮＩＮＧ　Ｈ，ｅｔ　ａＬ　Ｔｉｍｅ　ｍａｎａｇｅ－　ｍｅｒｉｔ　ｉｎ　ｗｏｒｋｆ］ｏｗ　ｓｙｓｔｅｍｓ［Ａ】．ＡＢＲＡＭＯＷＩＣＺ　Ｗ，ＯＲＬＤＷＳＫＡ　ＭＥ，ｅｄ．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｂｕｓｉｎｅｓｓ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍｓ【Ｃ】．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ—Ｖｅｒｌａｇ，１９９９．２６５—２８０．　【２】　ＳＥＮＫＵＬ　Ｐ，ＴＯＲＯＳＬＵ　１Ｈ．Ａｎ　ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　ｗｏｒｋｆｌｏｗ　ｓｃｈｅｄｕｌｉｎｇ　ｕｎｄｅｒ　ｒｅｓ０ｕｒｃｅ　ａｌｌｏｃａｔｉｏｎ　ｃｏｎｓｔｒａｉｎｔｓ【Ｊ】．Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｙｓｔｅｍ，　【８】　唐达，刘丹妮．一种工作流时间截止期限的动态验证方法ｆＪ】．　计算机集成制造系统——ＣＩＭＳ，２００４，９（１０）：１　１５４—１　１５９．