第27卷第4期 哈 尔 滨 工 程 大 学 学 报 Vol.27№.42006

年8月 JournalofHarbinEngineeringUniversity Aug.2006
基于活动的工作流关键路径算法
曹 瀚1,刘大昕1,富 锐2
(1.哈尔滨工程大学计算机科学与技术学院,黑龙江哈尔滨150001;2.哈尔滨工程大学经济管理学院,黑龙江哈尔滨150001)
摘 要:计算关键路径是研究工作流时间问题的重要步骤,现有算法大多是基于工作流控制结构的规约与化简的,对工作流模型要求较高,不能计算控制结构的“部分覆盖”,限制了其应用.首先给出一个描述活动延迟的工作流模型,然后将工作流网看作一个M/M/1队列网,讨论工作流活动在各种结构中的到达率与时间延迟,提出一种基于活动的关键路径算法.算法降低了对工作流模型结构的要求,解决了控制结构“部分覆盖”的计算问题,提高了算法的实用性.
关键词:工作流模型;关键路径;控制结构;队列网
中图分类号:TP311 文献标识码:A 文章编号:100627043(2006)0420551205
WorkflowcriticalpathCAO112
(1.CollegeofScienceand,,Harbin150001,China;2.CollegeofEconomicsandManagement,Harbin150001,China)
Abstract:Criticalinaworkflowisthebasisofworkflowtimemanagement.However,mostexistingresearchintheareaisbasedonreducingworkflowcontrolblocks,whichcannotresolvethe“partcover”ofacontrolstructure.Here,aworkflowmodelwasdevelopedtoincludethedelaydataofactivi2ties.ThenworkflownetismodeledasaM/M/1queuingnetwork.Theaveragedelayofactivitiesindiffer2entcontrolstructureswasalsodiscussed.Analgorithmbasedonactivitiesisproposedthatdeterminesthecriticalpathundertheworkflowmodel.Thisalgorithmresolvesthe“partcover”ofcontrolstructureandrequiresfewerlimitsonaworkflowmodel.
Keywords:workflowmodel;criticalpath;controlstructure;queennet
近年来随着工作流系统应用,人们逐渐认识到对工作流的时间属性的管理往往是工作流系统实施与应用的关键[1].工作流模型的关键路径的确定与计算是工作流时间研究工作的基本问题.Duk2Ho等[2]提出一种以控制结构为基础的关键路径算法ICSF.林闯等[3]讨论了计算基于Petri网的工作流系统的顺序、并行、选择、循环4种结构的性能等价公式,并指出利用这些公式来计算工作流的性能参数的方法.这些算法对工作流模型要求较高,不能出现控制结构的“部分覆盖”,限制了其应用.图1的工
收稿日期:2005205220.作者简介:曹 瀚(1973-),男,博士研究生,E2mial:caohan602@si2
na.com;
刘大昕(1941-),男,教授,博士生导师.
作流模型是正确的,但存在控制结构的“部分覆盖。”
(Wellstruc2这样的模型结构很难进行“良好结构”
tured)[4]的等价变换,即很难消除模型中的“部分覆盖”问题.则ICSF算法不适用.
石威等[5]提出一种根据活动最早可能开始时间EPST来计算任务图的关键路径.Eder等[6-7]提出
图1 一个工作流模型例子
Fig11 Anexampleofworkflowmodel
根据活动网络图中的AOE网来展示工作流模型,把对AOE网的关键路径的求解算法应用到工作流的关键路径的求解...更多>>工作流建模是工作流管理系统的重要组成部分,工作...
最后利用关键路径识别算法对结果进行对比分析,验证方法的有效性。 关键词:工作流...在工作流系统中,关键路径指从初始活动到结束活动平均执行时间最长的路径〔2〕。...
基于资源有效度的网格工作流任务调度算法_专业资料。针对执行时间限制严格的DAG...在DAG中的关键路径上资源系统有效度满足用户要求的一定信任水平,选择执行费用相对...
基于相对效费比的网格工作流调度算法_工学_高等教育_教育专区。算法...工 作流完工时间就是关键路径的运行时间,工作流总 费用是所有活动花费之和。图...
基于时间关键路径的工作流... 5页 1财富值 多...种基本结构的逗留时间分布与在每一活动的逗留时间分..., 本文分类讨论 4 种基 本结构的等价排队算法 。...
针对工作流 系 统中活动节 点的分配问题 , 设计模 型求解算法, 现了实 ...关键词: 活动网络 节点 路径 均衡 模型 当前 ,工作流 技术 成为实现企 业业...
关键词:服务发现 工作流 兼容 该付费资源由维普网提供 中国最大最早的...而在工作流中,这些问题同样是影响服务选择的主要因素。本文提出一种服务选择算法...
关键词:遗传算法粒子群算法网格工作流 该付费资源由维普网提供 中国最大最早的专业内容网站 机构整体评分:3.8 在售版权资源:7828836份 近七天成交量:13636份...
该算法先基于事件类型定义任务间序关系; 然后依据...关键词:事件类型;事件日志;工作流挖掘;结构化工作...定义3(事件路径,事件日志) 设E=Tx{Start,Complete...
热门文档