MSTC 网及调度算法小探

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

1 引言

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

工作流过程模型方面，有向图模型最早被用来建立工作流模型，如流程图、状态图等、活动网络图、epcm 模型（event-driven process chain，事件过程链模型）等。h.a. reijers等学者将event-driven process chains 扩展提出aggregate epc (aepc)模型，用一个统一的模型来描述一系列相似的业务流程。petri 网技术也是工作流建模的常用方法之一，如van deraalst 在petri 网的基础上提出了工作流网wf-net，并进一步研究提出了一种新的工作流建模语言yawl，kees van hee 等学者基于工作流网提出了一个过程模型和数据模型的融合方法。jan hidders 等学者基于petri 网和嵌套关系演算理论提出了一个新的数据流语言。

也有人通过把已有的建模方法（如e-r 图、面向对象方法）与有向图模型相结合，以更有针对性地面向某些领域进行过程建模，如thomas allweyer 把epcm 与面向对象的uml 相结合，用于面向对象的业务过程建模。除了有向图模型外，其它领域的工作流模型研究也取得了不少成果。如kacmar、carey 和alexaander 等人提出了基于活动树（activity tree）的模型；范玉顺、吴澄等提出一种基于协调理论和反馈机制的工作流建模方法，该方法扩展了传统活动网络模型；andreas geppert 等提出了代理/服务（broker/services）模型；winograd 和flores 在语言行为理论的基础上提出了一种基于对话的工作流模型等。

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

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

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

2 mstc 网的定义和相关概念

2.1 mstc 网

定义 1（mstc 网，multi-step task collaborative nets）一个四元组n＝（r，t；w，d）是一个mstc 网的充分必要条件是：

（1）r ≠φ ；

（2）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≤m, 1≤l≤m；

（6） ( )dom dn ∪ cod(dn ) = r ∪t ∪ n1 ∪ n2 ∪.....∪ nm = r ∪t ∪cn 。

其中， ( ) { ( ) } dom dn = x | ?y：x，y ∈dn ， ( ) { ( ) } cod dn = 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，也称为网间转入）。( )dom dn ∪cod(dn ) = r ∪t ∪ n1 ∪ n2 ∪.....∪ nm = r ∪t ∪cn表示在多mstc网中不能有孤立的子网。

2.3 多mstc 网统

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

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

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

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

概念4（路径 route）设n＝（r，t；w，d）是一个mstc 网，路径p 是从节点n1 到节点nk 的序列<n1, n2, …,nk>，其中，<ni，ni+1>∈ 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 : (r,t)∈w}为t的关联工作，t为rw(t)的关联任务；

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

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

（4）rd(r) = {d | ?t : (t,r)∈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.4 mstc 网系统的图形表示

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

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

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

(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 网系统的调度算法不仅可以实现流程的正向调度，即正常的角色签办任务，还可以实现流程的逆向调度，如角色退回任务，并且可以很好的支持循环。

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