资讯详情

这是一篇关于MSTC网及调度算法小探的毕业论文提纲，欢迎浏览借鉴！

1引言

工作流是一类能够完全或者部分自动执行的经营过程，它根据一系列过程规则、文档、信息或任务能够在不同的执行者之间进行传递与执行，工作流管理系统是一个软件系统，它完成工作流的定义和管理，并按照在计算机中预先定义好的工作流逻辑推进工作流实例的执行。工作流引擎是整个工作流管理系统的基础，其功能直接决定了工作流管理系统的应用范围和对变化的适应能力。工作流引擎的核心是工作流过程模型和流程的调度算法，工作流过程模型是对业务流程的抽象表示，而调度算法则是流程执行的控制规则，两者共同实现了业务流程的自动执行。

工作流过程模型方面，有向图模型最早被用来建立工作流模型，如流程图、状态图等、活动网络图、EPCM模型（Event-drivenProcessChain，事件过程链模型）等。H.A.Reijers等学者将Event-drivenProcessChains扩展提出AggregateEPC(aEPC)模型，用一个统一的模型来描述一系列相似的业务流程。Petri网技术也是工作流建模的常用方法之一，如VanderAalst在Petri网的基础上提出了工作流网WF-net，并进一步研究提出了一种新的工作流建模语言YAWL，KeesVanHee等学者基于工作流网提出了一个过程模型和数据模型的融合方法。JanHidders等学者基于Petri网和嵌套关系演算理论提出了一个新的数据流语言。

也有人通过把已有的建模方法（如E-R图、面向对象方法）与有向图模型相结合，以更有针对性地面向某些领域进行过程建模，如ThomasAllweyer把EPCM与面向对象的UML相结合，用于面向对象的业务过程建模。除了有向图模型外，其它领域的工作流模型研究也取得了不少成果。如Kacmar、Carey和Alexaander等人提出了基于活动树（ActivityTree）的模型；范玉顺、吴澄等提出一种基于协调理论和反馈机制的工作流建模方法，该方法扩展了传统活动网络模型；AndreasGeppert等提出了代理/服务模型；Winograd和Flores在语言行为理论的基础上提出了一种基于对话的工作流模型等。

工作流引擎任务调度方面，当前的研究主要集中在调度策略和调度算法两个方面。调度策略分为静态调度和动态调度两种。静态调度是在工作流建模时就绑定相应的资源，缺点是资源效率较低。动态调度在建模时只绑定资源的描述，因此在调度时能根据实际情况来利用合适的资源来执行任务，资源效率较高，缺点是存在资源竞争问题。Tretola等人还提出了一些考虑子任务内并行性的预调度策略来加快工作流的执行。

本文首先介绍了一种新的工作流过程模型——多步任务协同网（MSTCnets），一个由角色(Role，R)，任务(Task，T)，工作(Work，W)和转发(Deliver，D)构成的网络，R表示流程的参与者，而T则描述了流程的业务活动，W表示角色在任务中的分工，而D用于表示业务流程的流转方向（可以是有条件的），一个任务可以由多个角色共同完成，这种区别不仅使其更贴近于实际的业务流程，还使其获得了更为强大的业务流程描述能力和更为丰富的信息加工能力。同时，由于W表示角色在任务中的分工，改善了模型对角色及其和任务的交互关系的处理能力（例如可更好地处理由角色引起的异常）。为了更好的描述MSTC网的动态运行状态，在其基础上增加了转发条件、起始工作、分组和循环的描述，构成MSTC网系统。针对MSTC网系统的特点，我们研究了并给出了其8个调度算法，并进行详细分析。

本文第一节给出MSTC网的定义和相关概念，形式化的数学语义描述为进一步的深入研究提供基础，直观的图形化描述为过程建模提供良好的图形表示方法。第二节在建立了MSTC网中各建模元素的状态集合的基础上，对MSTC网的调度方法进行了深入研究。第三节通过案例解析详细解释了调度方法的调度过程。最后是小结。

2MSTC网的定义和相关概念

2.1MSTC网

定义1（MSTC网，Multi-stepTaskCollaborativeNets）一个四元组N＝（R，T；W，D）是一个MSTC网的充分必要条件是：

T≠φ；

（3）R∩T=φ；

（4）W?R×T；

（5）D?T×R；

（6）dom(W)∪cod(W)=R∪T。

其中，dom(W)={x|?y：(x，y)∈W}，cod(W)={y|?x：(x，y)∈W}.

MSTC网的定义中，R和T是基本成分，W和D是由R和T构造出来的，所以在定义中将R、T和W、D用分号‘；’隔开。R和T是两类不同的概念，所以R∩T=φ。R≠φ和T≠φ表示在MSTC网中至少要有1个角色和1个任务。dom(W)∪cod(W)=R∪T表示在MSTC网中不能有孤立的R或孤立的T。显然，MSTC网中至少要有1个W。

MSTC网是一个由角色（Role，R）、任务（Task，T）、工作（Work，W）和转发（Deliver，D）构成的网络。其中，R是一个有限的角色集合，表示参与业务流程的人；T是一个有限的任务集合，表示网中的逻辑工作单元，必须完整执行，如申请、审核、会签、投票等；W是一个有限的工作集合，表示角色在事务中的分工，如阅文、填表、批示等；D是一个有限的转发集合，表示任务完成后业务的流转方向。

在一个MSTC网中，R和T是基本成分，称为节点（Node），W和D是由R和T构造出来的有向弧，称为连接（Connection）。

2.2多MSTC网

定义2（多MSTC网）一个六元组M＝（R，T；W，D；CN；DN）是一个多MSTC网，如果M满足以下的条件：

（1）N＝（R，T；W，D）是一个MSTC网，称为M的基网（Basic-net）；

（2）CN是一个有限的MSTC网集合；

（3）CN={N1，N2，…，Nm}，Ni是一个MSTC网，m为正整数且m≥1；

（4）DN是N和CN之间的转发的集合；

（5）DN?(T×Nk)∪(Nl×R)，1≤k≤m1≤l≤m；

（6）()domDN∪cod(DN)=R∪T∪N1∪N2∪.....∪Nm=R∪T∪CN。

其中，(){()}domDN=x|?y：x，y∈DN，(){()}codDN=y|?x：x，y∈DN。

根据定义可知，N和Ni（1≤i≤m）都是M的子网。DN?(T×Nk)∪(Nl×R)表明DN是N和CN之间的转发，称为网间转发（Net-deliver）。网间转发只能从N的T元素转发到Nk（即T×Nk，也称为网间转出），或从Nl转发到N的R元素（即Nl×R，也称为网间转入）。()domDN∪cod(DN)=R∪T∪N1∪N2∪.....∪Nm=R∪T∪CN表示在多MSTC网中不能有孤立的子网。

2.3多MSTC网统

MSTC网的定义描述了网的静态结构特征，为了更好的描述网的动态运行状态，需要对网的状态加以描述，下面首先介绍几个基本概念。

概念1（起始工作StartWork）不依赖于任何转发的结果就可以开始运行的工作称为起始工作。MSTC网的运行必须从起始工作开始。一个MSTC网可能有多个起始工作，并且可以从任意一个或多个起始工作开始运行。

概念2（转发条件DeliverCondition）MSTC网中的转发可能是无条件的，也可能是有条件的。有条件的转发必须在条件计算结果为真值的前提下，才能执行转发。转发所依赖的条件称为转发条件。中国代写论文网为您代写硕士论文。

概念3（分组Group）角色可异步地接收不同的转发和办理不同的工作，然而这些工作和转发之间可能存在依赖关系。为了描述这种依赖关系，必须对这些转发和工作进行区分，将有依赖关系的转发和工作归并在一起，称为分组。

概念4（路径Route）设N＝（R，T；W，D）是一个MSTC网，路径P是从节点n1到节点nk的序列，其中，∈W∪D，1≤i≤k-1。

概念5（循环Loop）循环是可被反复执行的，并只保留最后一次执行信息的环形路径。

概念6（关联工作Relate-work，关联转发Relate-deliver、关联任务Relate-task、关联角色Relate-role）若N＝（R，T；W，D）是一个MSTC网，设r是N中的任一角色，t是N中的任一任务，则我们称：

（1）rw(t)={w|?r:(rt)∈W}为t的关联工作，t为rw(t)的关联任务；

（2）rd(t)={d|?r:(tr)∈D}为t的关联转发，t为rd(t)的关联任务；

（3）rw(r)={w|?t:(rt)∈W}为r的关联工作，r为rw(r)的关联角色；

（4）rd(r)={d|?t:(tr)∈D}为r的关联转发，r为rd(r)的关联角色。

定义3（MSTC网系统）一个十元组Σ＝（R，T；W，D；CN；DN；CD，W0，G，L）构成MSTC网系统的充分必要条件是：

（1）M＝（R，T；W，D；CN；DN）是一个多MSTC网；

（2）CD是转发条件的集合；

（3）W0是起始工作的集合；

（4）G是分组的集合；

（5）L是循环的集合。

MSTC网系统比多MSTC网的定义增加了转发条件、起始工作、分组和循环，能更好地描述真实系统。在不特殊说明的情况下，本文所说的MSTC网就是指MSTC网系统。

2.4MSTC网系统的图形表示

任务的图符用一个矩形表示；工作的图符为一个带箭头的直线，方向从角色指向任务，起始工作用带空心箭头的直线表示，而其他工作则为实心箭头；转发的图符为也为一个带箭头的直线，方向从任务指向角色，条件转发用带空心箭头的直线表示，而其他转发则为实心箭头；分组用标在直线上靠近角色端的数字表示；循环用双箭头表示（仅循环用为空心）。

3MSTC网系统的调度方法研究

在一个具体的案例中，可能存在多个并行执行的任务，并且这些任务的执行时间和顺序是完全依赖于多步任务协同网的拓扑结构及相关的转发条件，因此需要工作流引擎对这些任务的执行进行调度。下面将详细说明多步任务协同网中多任务的调度方法通常构建并运行一个多步任务协同网的步骤为:

(1)构建多步任务协同网N＝（R，T；W，D）;

(2)构建多步任务协同网系统Σ＝（R，T；W，D；CN；DN；CD，W0，G，L）;

(3)构建调度所需的状态集合包括五个状态集合:

案例的状态集合：Si={Sir，Siw，Sif}，案例是多步任务协同网的一次执行，一个多步任务协同网系统可以被多次执行，每次执行都对应一个不同的案例.其中Sir就绪状态表示案例等待执行的状态;Siw在办状态：案例正在执行的状态;Sif完成状态：案例已经结束的状态.

工作的状态集合：Sw={Swr，Sww，Swn，Swf}其中Swr就绪状态：工作等待角色办理的状态;Sww在办状态：工作正在被角色办理的状态;Swn否定状态：工作因条件不满足不能被角色办理的状态;Swf完成状态：工作已经结束的状态.

任务的状态集合：St={Str，Stw，Stn，Stf}，其中Str就绪状态：任务等待角色办理的状态;Stw在办状态：任务正在被角色办理的状态;Stn否定状态：任务因条件不满足不能或不需要被角色办理的状态;Stf完成状态：任务已经结束的状态.

转发的状态集合：Sd={Sdr，Sdw，Sdn，Sdf}，其中Sdr就绪状态：转发等待被执行的状态;Sdw待签状态：转发等待被角色签收的状态;Sdn否定状态：转发因条件不满足不能或不需要被角色签收的状态;Sdf完成状态：转发已经结束的状态.

循环的状态集合：Sl={S1r，S1w，Slf}，其中S1r就绪状态：循环等待被执行的状态;S1w工作状态：循环正在被执行的状态;Slf完成状态：循环已经结束的状态.

(4)构建调度所需的调度方法

多步任务协同网系统中的调度方法包括启动案例、终止案例、角色签办任务、角色退回任务、多步任务办理、多步任务重办、启动循环和终止循环八个调度方法.在多任务调度之前，案例和所有的工作、任务、转发、循环都被初始化为就绪状态。启动案例是第一个被执行的调度，角色签办任务、角色退回任务、多步任务办理、多步任务重办、启动循环和终止循环是根据多步任务协同网系统的流向，包括正向和逆向，由角色进行执行的，终止案例的调度是根据工作和转发的状态由系统自动执行的.令：SetStatus(x)表示设置对象x的状态，x可以为案例、任务、工作、转发或循环；GetStatus(x)表示获得对象x的状态，x为案例、任务、工作、转发或循环；SetRole(x)表示设置对象所属角色，x为工作或转发；GetRole(x)表示获得对象所属角色，x可以为工作或转发；PreCondition(x)表示条件计算，结果为ture或false，x为转发；Count(x)表示集合中对象的数目，x为一个对象集合。

3.1启动案例的调度方法

一个多步任务协同网系统可以被多次执行，每次执行都对应一个不同的案例。

执行该调度方法之后，多步任务协同网系统就进入到运行状态，此后各个元素将逐一转变状态直至案例结束。

3.2终止案例的调度方法

该调度算法有多步任务协同网系统自动执行，即系统会根据需要执行该方法以检查案例是否可以结束。

3.3角色签办任务的调度方法

当角色的某组关联转发全部为否定或待签且至少有一个为待签时，该角色才能签办改组转发以及相关的任务，同时同组的工作也会转到在办状态。

3.4角色退回任务的调度方法

当角色办理工作时发现之前的工作存在问题时可以要求前驱角色重新办理任务，此时该角色的工作将退回到就绪状态，关联转发也会退回到就绪状态，所需重办的工作和任务则转变为在办状态。

3.5多步任务办理的调度方法

当所有工作完成或否定且至少有一个完成的话，任务就办理完成了。此时，关联转发根据设定的条件转变为待签或者否定。

3.6任务重办的调度方法

当工作未完成或者工作完成但还没有签收时，角色可以要求前驱角色重办与之相关的工作，即退回已经签办的工作。

3.7启动循环的调度方法

3.8终止循环的调度方法

4案例简析

设所示案例i中有6个角色（r1、r2、r3、r4、r5和r6）和7个任务（t1、t2、t3、t4、t5、t6、t7），其中任务t1、t5和t7是多步任务（由多个角色协同完成），工作w1_1、w1_2和w_5是启动工作，转发d1_1和d1_2是条件转发，在r6上定义了2个分组，d2和w6_2为分组g1，d1_2和w6_1为分组g2，其它所有没有定义分组的客户机默认为同一个分组，w2_1、d4、w3_1和d3是一个循环l。

4.1案例i的正向调度示例

(1)当案例i启动后，S(i)=Siw，S(w1_1)=Sww，S(w1_2)=Sww，S(w5)=Sww，S(t1)=Stw，S(t2)=Stw；

(2)由图14中可以看出，t1由r1和r5同时负责，对应工作w1_1和w5，t2由r1负责，对应工作w1_2；

(3)当w1_1和w5办理完毕后，即S(w1_1)=Swf，S(w5)=Swf，则t1完成，即S(t1)=Stf，由于d1_1和d1_2是条件转发，需要根据条件设置进行条件判断，这里假设P(d1_1)=true，P(d1_2)=false，则S(d1_1)=Sdw，S(d1_2)=Sdn；

(4)当w1_2办理完毕后，S(w1_2)=Swf，S(t2)=Stf，S(d2)=Sdw；

(5)r2没有定义分组，默认所有转发和工作为同一分组。由于d3为仅循环用（启动循环运行时才有效），这里假设不启动循环，所以r2可以签办任务t1，签办后，S(d1_1)=Sdf，S(w2_1)=Sww，S(w2_2)=Sww，S(t4)=Stw，S(t5)=Stw；

(6)r6上定义了2个分组，d2和w6_2为分组g1，d1_2和w6_1为分组g2。对于g1，r6签办任务t2后，S(d2)=Sdf，S(w6_2)=Sww，S(t6)=Stw。对于g2，由于S(d1_2)=Sdn，所以S(w6_1)=Swn；

(7)当w2_1办理完毕后，S(w2_1)=Swf，S(t4)=Stf，S(d4)=Sdw；

(8)当w2_2办理完毕后，S(w2_2)=Swf，由于S(w6_1)=Swn，所以S(t5)=Stf，S(d5_1)=Sdw，S(d5_2)=Sdw；

(9)当w6_2办理完毕后，S(w6_2)=Swf，S(t6)=Stf；

(10)r3没有定义分组，默认所有转发和工作为同一分组。由于w3_1为仅循环用，这里假设不启动循环，所以r3签办任务t4和t5后，S(d4)=Sdf，S(d5_1)=Sdf，S(w3_2)=Sww；

(11)r4没有定义分组，默认所有转发和工作为同一分组。r4签办任务t5后，S(d5_2)=Sdf，S(w4)=Sww；

(12)当w3_2和w4办理完毕后，S(w3_2)=Swf，S(w4)=Swf，S(t7)=Stf，由于i中没有任何一个w处于待办状态且没有一个d处于待签状态，所以案例i结束，即S(i)=Sif。

4.2案例的逆向调度过程示例

(1)角色重办任务

设案例i正向调度到第（4）步，由于S(d1_1)=Sdw，S(d1_2)=Sdn，所以r5可以重办t1，r1可以重办t1和t2。这里设r1重办t1，重办后，S(d1_1)=Sdr，S(d1_2)=Sdr，S(t1)=Stw，S(w1_1)=Sww。

(2)角色退回任务

设案例i正向调度到第（6）步，由于S(w2_1)=Sww，S(w2_2)=Sww，S(w6_1)=Swn，S(w6_2)=Sww，S(t4)=Stw，S(t5)=Stw，S(t6)=Stw，所以r2和r6都可以退回任务。这里设r6退回分组g1的签办的任务t2，则S(w6_2)=Swr，S(d2)=Sdw。可以看出，当r6退回签办的t2后，r1还可以重办w1_2，从而连续实现多步任务调度过程中的逆向。

4.3案例的循环调度过程示例

设案例i正向调度到第（10）步，r3启动循环l，则S(l)=Slw，S(w3_1)=Sww，S(t3)=Stw；当w3_1办理完毕后，S(w3_1)=Swf，S(t3)=Stf，S(d3)=Sdw；这时，r2可以签办任务t3，由于循环将路径中工作、任务和转发统一按照就绪状态处理，而w2_2不在循环中，所以签办后S(d3)=Sdf，S(w2_1)=Sww，S(t4)=Stw；当w2_1办理完毕后，S(w2_1)=Swf，S(t4)=Stf，S(d4)=Sdw；此时r3如果终止循环，则S(l)=Slf，循环结束，如果不终止循环，r3可以接着办理w3_1，则S(w3_1)=Sww，S(t3)=Stw，如此反复执行直至循环终止。

5结束语

本文以工作流过程模型MSTC网系统为基础研究了其主要的调度方法最后以案例简析来展示算法的有效性.MSTC网系统的建模元素主要有角色(R)、任务(T)、工作(W)、转发(D)，这些建模元素拥有不同的状态集合，在运行时通过不断的改变他们所处的状态最终实现预定的业务流程功能。MSTC网系统的调度算法是案例执行的规则，工作流引擎就是按照不同的调度算法对业务流程中的不同元素进行协同调度，从而实现业务流程的流转运行。在现实工作流的执行过程中任务的执行时间和顺序是完全依赖于MSTC网的拓扑结构及相关的转发条件，所以严密的调度逻辑对流程的正确执行至关重要。而本文所介绍的8个调度方法可以全面的控制多步任务协同网的执行。从案例简析中可以看到，MSTC网系统的调度算法不仅可以实现流程的正向调度，即正常的角色签办任务，还可以实现流程的逆向调度，如角色退回任务，并且可以很好的支持循环。

同时，由于多步任务协同网本身的演化，本文所介绍的调度算法可能还会进一步支持一些高级的结构，如子网，多实例等等。