摘要：
第7卷第4期 哈 尔 滨 工 程 大 学 学 报 Vol.7№... 第 27 卷第 4 期 哈 尔 滨 工 程 大 学 学 报 Vol. 27 №. 42006 年 8 月 Journal of Harbin Engineering University Aug. 2006基于活动的工作流关键路径算法曹 瀚1,刘大昕1,富 锐2(1. 哈尔滨工程大学 计算机科学与技术学院 ,黑龙江 哈尔滨 150001 ;2. 哈尔滨工程大学 经济管理学院 ,黑龙江 哈尔滨150001)摘 要 :计算关键路径是研究工作流时间问题的重要步骤 ,现有算法大多是基于工作流控制结构的规约与化简的 ,对工作流模型要求较高 ,不能计算控制结构的 “部分覆盖” ,限制了 其应用. 首先给出一个描述活动延迟的工作流模型 ,然后将工作流网看作一个 M/ M/1 队列网 ,讨论工作流活动在各种结构中的到达率与时间延迟 ,提出一种基于活动的关键路径算法. 算法降低了对工作流模型结构的要求 ,解决了 控制结构 “部分覆盖”的计算问题 ,提高了 算法的实用性.关键词 :工作流模型 ;关键路径 ;控制结构 ;队列网中图分类号 : TP311 文献标识码 :A 文章编号 :100627043 (2006) 0420551205Workflow critical path algorithm based on activitiesCAO Han1,LIU Da2xin1,FU Rui2(1. College of Science and Technology , Harbin Engineering University , Harbin 150001 , China ; 2. College of Economics andManagement , Harbin Engineering University , Harbin 150001 ,China)Abstract :Critical path analysis in a workflow is the basis of workflow time management. However , mostexisting research in the area is based on reducing workflow control blocks , which cannot resolve the“partcover” of a control structure. Here , a workflow model was developed to include the delay data of activi2ties. Then workflow net is modeled as a M/ M/ 1 queuing network. The average delay of activities in differ2ent control structures was also discussed. An algorithm based on activities is proposed that determines thecritical path under the workflow model. This algorithm resolves the“part cover” of control structure andrequires fewer limits on a workflow model.Keywords :workflow model ; critical path ; control structure ; queen net收稿日期 :2005205220.作者简介 :曹 瀚(1973 - ) ,男 ,博士研究生 , E2mial :caohan602 @si2na. com;刘大昕(1941 - ) , 男 ,教授 ,博士生导师. 近年来随着工作流系统应用 ,人们逐渐认识到对工作流的时间属性的管理往往是工作流系统实施与应用的关键[1 ]. 工作流模型的关键路径的确定与计算是工作流时间研究工作的基本问题. Duk2 Ho等[2]提出一种以控制结构为基础的关键路径算法ICSF. 林闯等[3 ]讨论了 计算基于 Petri 网的工作流系统的顺序、并行、选择、循环 4 种结构的性能等价公式 ,并指出利用这些公式来计算工作流的性能参数的方法. 这些算法对工作流模型要求较高 ,不能出现控制结构的 “部分覆盖” ,限制了其应用. 图 1 的工作流模型是正确的 ,但存在控制结构的 “部分覆盖。
”这样的模型结构很难进行 “良好结构”(Well struc2tured)[4]的等价变换 ,即很难消除模型中的 “部分覆盖”问题. 则 ICSF 算法不适用.石威等[5 ]提出一种根据活动最早可能开始时间EPST 来计算任务图的关键路径. Eder 等[6 - 7 ]提出图 1 一个工作流模型例子Fig1 1 An example of workflow model
