基于工作流的关键路径分析

摘要：通过了解利用工作流建模，确定活动网络图中的关键路径的相关知识，对现有的方法进行分析、总结，在前人的基础上，提出将数据挖掘技术引入工作流模型，实时动态的分析活动网络图中的关键路径，实现对关键路径实时优化的方法。

关键词：工作流、关键路径、动态

中图分类号：G254文献标识码： A

1.工作流及关键路径概述

工作流就是工作流程的计算模型，即将工作流程中的工作，前后组织在一起的逻辑和规则在计算机中以恰当的模型进行表示并对其实施计算。工作流建模把现实世界的业务流程抽象化，建立计算机可识别和处理的信息模型，实现业务流程的全部或部分自动化，使得文档、信息或任务能够在不同的执行者之间进行传递与执行[1]。

关键路径是网络终端元素的序列，该序列具有最长的总工期，决定了整个项目的最短完成时间。任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间，因此，对关键路径的控制，是对整个项目能否按时完成的关键[2]。

2.分析工作流模型确定关键路径

（1）网络图中活动之间关系

网络图中活动之间的关系包括：顺序、并发、选择、循环、与、或等多种关系[3]。工作流系统对不同的关系进行处理，分析每个活动的处理时间及等待时间。确定从起点，到终点的所有路径，再分别计算每条路径上的所有活动的处理时间及等待时间，对比分析网络图中的关键路径。

（2）网络图的简化

Aalst定义了最基本的7种结构[4]，包括基本构件块、顺序结构、分叉结构、合并结构、循环结构、与结构。

袁崇义老师，在其《Petri网原理》一书中给出了28种基本结构[5]。基本结构应用于活动网络图的化简，主要使用选择结构、循环结构和与结构，用于简化活动网络图中的选择结构、循环结构、与结构和或结构。将这些结构化简，计算每个结构的时间，使网络图变得更清晰，便于优化分析。

3.关键路径调优

受现有的一些基于工作流模型确定关键路径的方法的启发，从网络图中活动时间参数的分析计算，结合数据库、数据挖掘技术的资源分析，实时在各个阶段动态确定关键路径。

第一步：网络图中活动时间参数分析

将活动的最早开始时间、最早结束时间、最迟开始时间、最迟结束时间的概念，及活动总时差、自由时差的计算方法，引入到工作流模型中，根据每个活动的最早开始时间、最早结束时间、最迟开始时间、最迟结束时间，计算每个活动的总时差和自由时差，通过对每个活动的总时差和自由时差的分析，确定整个网络的优化空间及节点。

第二步：通过资源分析，确定活动的处理时间

在确定网络图中每个活动的处理资源时，利用数据库及数据挖掘技术，对每个资源的能力、效率进行分析，结合历史的经验数据，估算每个活动的处理时间，并将时间直接输送到工作流模型。

第三步：初步确定关键路径

通过现有的方法，对活动网络图进行化简，将第二步的每个活动的处理时间的分析结果导入工作流模型，确定关键路径。

第四步：关键路径优化

利用工作流模型，确定了活动网络图的关键路径后，需要结合每个活动的总时差及自由时差，处理活动的资源对每个活动的处理时间，分析网络图中的所有路径，对活动网络图的关键路径进行优化。对于那些总时差及自由时差比较大的活动，在保证活动延时不影响后续活动的前提下，调整资源，将优秀的资源放在关键路径上，协调非关键路径上的资源，支持关键路径的活动，缩短关键路径的时间。通过资源的调整，降低整个活动网络图的完成时间。

第五步：关键路径动态调整

确定关键路径，并对关键路径进行优化后，在工作流转进行过程中，活动网络图的关键路径，可能会因为这样、那样的原因发生变化。关键路径的变化，也会使得工作的重点，关注的焦点发生改变。这就需要实时的监测、分析各个活动的执行情况、完成情况，是否按计划进行。对于当前时间后续需要完成的工作，根据当前的实际情况，重新进行分析，确定当前状态下的关键路径，并对当前状态下的关键路径进行优化。

通过以上几步的操作，从任务开始处理，到最后任务处理完成，在整个过程中都进行这样的操作，可以有效的保证关键路径的正确性，指导各个阶段的工作。

4.结束语

本文通过对网络图及其基本结构的分析，总结现有的研究成果，从网络图中活动时间参数的分析计算，结合数据库、数据挖掘技术的资源分析，提出了一种针对关键路径优化的方法，同时提出了实时动态分析关键路径的方法。通过该方法，可以动态的确定项目当前的关键路径是什么，当前的问题以及需要资源投入的方向，可以有效控制项目更好的实施。

参考文献：

[1] Guozhong Tian,Chuangbai xiao,Xiao Xu,ChaoQin Gao,Nuslati,Mardan.Grid Workflow Scheduling Based on Time Prediction of Queuing Theory.IEEE 2010.

[2] Zeki Karaca,Turgay Onargan The Application of Critical Path Method(CPM) in Workflow Schema of Marble Processing Plants Materials and Manufacturing Processes 2007

[3] 陶泽，谢里阳，袁锋 受时间约束的工作流关键路径的确定 计算机工程与应用 2004

[4] Aalst Workflow management:Models,Methods,and Systems 2002

[5] 袁崇义 Petri网原理 电子工业出版社 1998