ISSN 
-
现代业务的工作流技术是在网络流的基础上以服务为基本元素进行架构，使多个服务相互协作来完成整个业务。工作流系统将业务流程抽象化，划分为诸多工序，并结合工序中的服务属性，确定最佳完工路径。然而，目前企业的项目流程，往往因为一个或者几个工序出现问题而影响整体，如追求效率而忽略了服务质量或者追求服务质量而拖延了完工时间，使得整个项目的完工时间和完工质量失衡。为此，应该使用更合理的方法，在业务流程规定的截止期内，选择一条能够有效提升复杂项目准确率的路径，达到既能充分利用资源，又能使效率和准确率实现平衡的目的[1]。
本文提出了一种加工型产品工作流在限定完工时间内，保证工序完工质量最高的算法，即实现了完工路径质量的串归约优化。
HTML
-
工作流模型包含任务和服务两大要点，服务在工作流模型中承载着时间、费用和服务质量等属性，合理搭配服务之间的联系对优化任务的顺利进行起着关键性作用[2-3]。随着工作流结构的不断拓展，工作流的优化不再以时间为根本，而是对其完工时间和完工质量有了更高的要求。文献[4]结合时间启发函数和遗传算法的优点，提出一种混合式算法，通过实验证明了该策略的优化效果；文献[5]针对资源配置可能存在的不确定性弊端，提出了一种截止驱动调度算法，有效地降低了成本并保证了完工时间；文献[6]在混合式工作流的基础上提出了类似VM的并行任务处理方案，有效地降低了执行成本；文献[7]利用任务在进程中的灵活性并结合工作流的健壮性，提出了一种任务动态重排的方法，能够有效降低前驱任务对后续任务的影响，以达到资源合理分配的目标。
基于在约束时间下降低成本的问题，国内也开展了相应的研究。文献[8-9]都是在混合式复杂工作流上约束时间进而优化成本，分别利用逆向分层策略和串归约策略对每个活动结点划分活动区间，以局部选择最优服务来达到全局的优化。文献[10]采用优先级因子技术来优化复杂工作流的时间和成本的算法，并对不同的算法进行了比较分析。文献[11]对粒子进行初始化并进行了筛选，在此基础上提出了基于粒子群算法的优化调度策略，同时减少搜索时间。可见，现代工作流技术大部分追求的是时间和成本的平衡，而在约束时间下有效优化准确率也是一个研究热点。
-
工作流建模是对业务过程的一个合理安排，能够有效地将服务安排到对应任务的服务集合中[12]，并将加工型产品生产工序组成一个有向无环图。
定义1 任务池。是指在给定业务的流程中，将所有任务构成一个集合，若用P表示，则P=(p1, p2, …, pi, …, pn)。
定义2 服务池。指对于任务集合P中的任意一个任务pi，所对应的所有服务构成的集合。用Si=(s1, s2, …, sj, …, sm)表示。
定义3 服务池的秩。指对于任务集合P中的任意一个任务p，其服务集合Sp中服务的数目，用rp表示。
定义4 工作流图。即是网格环境下的有向无环图DAG与任务池P、服务池S相结合用来清楚描述业务流程的图，表示为G={spk, E}，p∈P，0＜k≤rp。其中，spk表示任务p用服务集合Sp中的第k个服务完成；E为有向边，表示每层的服务之间存在着顺序关系。工作流图中，没有前驱的结点为开始结点，记为结点Start，用ps表示虚拟的任务，Ss表示虚拟的服务集合，并指向Start结点；没有后继的结点为完成结点End，用pe表示虚拟的任务，用Se表示虚拟的服务集合，并指向End结点。
定义5 服务属性。是指工作流图G中服务spk带有的属性参数，表示为ptpk=(tpk, apk)，tpk表示使用服务池Sp中的第k个服务完成任务p的时间，apk表示达到的准确率。
-
定义6 完工时间。指产品的生产从开始到结束耗费的时间，记为T。
定义7 完工准确率。指产品的生产从开始到结束达到的准确率，记为A。
定义8 截止期。指产品的生产约束限定时间，记为ψ。
对于建立的工作模型，此时需要有规定的约束策略，对流程的形式化为：
即表示一条能够完成加工型产品路径的准确率。当执行一个任务时，只能选择一个服务来完成该任务，即：
完成加工型产品所用的时间必须低于或等于截止时间，即；
式中，lpk是一个变量，即：
在截止期ψ下，以式(1)为启发目标函数，在式(2)~式(4)的约束条件下，求得能够完成加工型产品路径的准确率，此时采用不同的算法策略求得对应路径的准确率。
2.1. 工作流模型的相关定义
2.2. 约束定义
-
一个加工型产品的生产工序，承载着完工时间和完工准确率的属性，传统单向目标的算法策略是指在生产过程中，仅仅保证了完工时间最小或者仅保证了完工准确率最大。
-
选择每个工序完成时间最小的服务组成工作序列，即：
式中，Tmin为限定条件，即时间最小化；在限定条件Tmin下可求得完工准确率A。
-
选择每个工序完成准确率最大的服务组成工作序列，即：
式中，Amax为限定条件，即达到完工准确率最大化；在限定条件Amax下可求得完工时间T。
3.1. 最小时间的单向目标优化算法(TMG)
3.2. 最大准确率的单向目标优化算法(AMG)
-
定义9 任务自由度WFp。即工作流模型中给定的任务的活动区间[STp，ENp]，p∈P，这里的STp即该任务最早开始时间，ENp是该任务最晚开始时间。WFp的STp和ENp由式(7)求得：
-
串归约优化算法是在每层任务的活动区间内选择合适的服务，实现复杂产品的完工时间和准确率平衡的目标。由于在活动区间内的服务存在不能充分利用时间的问题，因此会产生一些时间碎片。串归约算法充分利用在截止期范围内的时间，把时间碎片集中起来，产生一个局部最优解。本文以任务的自由度为基础，对于任务集合P中的每个任务p，都有一个WFp=[STp, ENp]，采用动态规划的方式，以后继活动不同时间点开始时达到的局部最优解求得当前活动不同时间点开始时达到的最优解，通过比较完工的准确率确定最佳路径。
针对含有n个任务的工作流图，用f(p, t)表示工作流图中的第p个任务在时间t开始时达到的最大准确率，其中t∈[STp, ENp]。以最后一个活动为起点，迭代求出前驱活动相应的值，最后一个活动的f由式(8)求得：
对已经求解每个活动自由度的业务流程，以活动p的相关值f(p, tp)，求解前驱活动p'对应的f(p', tp')，该迭代过程由式(9)求得：
通过层层迭代，当遍历到初始任务时，最大准确率的服务组合即为业务流程最佳路径。
基于串归约的时间-准确率优化算法SRO伪代码如下：
Input：P, Sp
Output：最佳路径。
Val n=P.length();
For(int p=1; p≤n; p++) {
Figure WFp by Formula (7)); }
Figure f(n, t) by Formula (8);
For(p=n-1; p＞0; p--){
Figure f(p, t) by Formula (9)};
if(p=1){
Search max(f(p, t)); }
经分析：SRO算法对应的时间复杂度为O(mn)。
4.1. 相关定义
4.2. 算法描述
-
组装工艺的一般过程分为备料、形成坯件、零部件加工、部件组合、总组合和表面涂饰6个环节，存在虚拟的开始任务和结束任务，分别为申请和竣工，则该业务流程可抽象化表示p1, p2, p3, p4, p5, p6, ps, pe。此时每个环节对应一个服务池Sp，对应的服务带有一定的属性参数，数据如表 1所示。
任务池(R) 服务池(S) p1 s11(3, 0.92); s12(4, 0.94); s13(5, 0.97); p2 s21(2, 0.96); s22(3, 0.98); p3 s31(2, 0.94); s32(4, 0.96); s33(5, 0.98); p4 s41(5, 0.95); s42(7, 0.97); p5 s51(3, 0.96); s52(5, 0.97); s53(6, 0.98); p6 s61(3, 0.96); s62(5, 0.97); -
由以上的任务和服务列表，建立如图 1所示的工作流图。
基于图 1的工作流图，规定本业务流程的截止期ψ=21，采用本文的传统单向目标算法和基于串归约的时间-准确率优化算法进行计算。
-
1) TMG算法。调用式(5)求得对应的工作流程为s11-＞s21-＞s31-＞s41-＞s51-＞s61，此时对应的限定条件Tmin=t11+t21+t31+t41+t51+t61=16，则可求得对应工作流程的准确率A=a11a21a31a41a51a61=0.727;
2) AMG算法。调用式(6)求得对应的工作流程为s13-＞s22-＞s33-＞s42-＞s53-＞s62，此时对应的限定条件Amax=a13a22a33a42a53a62=0.859，则对应工作流程的完工时间T= t13+ t22+t33+t42+t53+t62=31。
-
结合业务流程的任务及其对应的服务属性，调用算法SRO可得：任务p1自由度为[0, 3]，任务p2自由度为[3, 6]，任务p3自由度为[5, 8]，任务p4自由度为[7, 10]，任务p5自由度为[12, 15]，任务p6自由度为[15, 18]，并可求出各个任务在相应的任务自由度内，不同时间开始执行取得的最大准确率，其计算过程及结果如表 2所示：
任务 不同任务在不同时刻达到的准确率 p6 f(6, 15)=max{0.96, 0.97}=0.97；f(6, 16)=max{0.96, 097}=0.97;
f(6, 17)=max{0.96}=0.96; f(6, 18)=max{0.96}=0.96;p5 f(5, 12)=max{f(6, 15)*0.96, f(6, 17)*0.97, f(6, 18)*0.98}=0.941;
f(5, 13)=max{f(6, 16)*0.96, f(6, 18)*0.97}=0.931;
f(5, 14)=max{f(6, 17)*0.96}=0.922;
f(5, 15)=max{f(6, 18)*0.96}=0.922;p4 f(4, 7)=max{f(5, 12)*0.95, f(5, 14)*0.97}=0.894;
f(4, 8)=max{f(5, 13)*0.95, f(5, 15)*0, 97}=0.894;
f(4, 9)=max{f(5, 14)*0.95}=0.876;
f(4, 10)=max{f(5, 15)*0.95}=0.876;p3 f(3, 5)=max{f(4, 7)*0.94, f(4, 9)*0.96, f(4, 10)*0.98}=0.858;
f(3, 6)=max{f(4, 8)*0.94, f(4, 10)*0.96}=0.841;
f(3, 7)=max{f(4, 9)*0.94}=0.823;
f(3, 8)=max{f(4, 10)*0.94}=0.823;p2 f(2, 3)=max{f(3, 5)*0.96, f(3, 6)*0.98}=0.824;
f(2, 4)=max{f(3, 6)*0.96, f(3, 7)*0.98}=0.807;
f(2, 5)=max{f(3, 7)*0.94, f(3, 8)*0.98}=0.807;
f(2, 6)=max{f(3, 8)*0.94}=0.774;p1 f(1, 0)=max{f(2, 3)*0.92, f(2, 4)*0.94, f(2, 5)*0.97}=0.783;
f(1, 1)=max{f(2, 4)*0.92, f(2, 5)*0.94, f(2, 6)*0.97}=0.759;
f(1, 2)=max{f(2, 5)*0.92, f(2, 6)*0.94}=0.742;
f(1, 3)=max{f(2, 6)*0.92}=0.712;由f(1, 0)=0.783可知，此时的完工准确率最大，则可明确基于串归约算法的最佳路径为：任务p1从0时开始，用对应的s13服务，所用时间为5；任务p2从5时开始，用对应的s22服务，所用时间为3；任务p3从8时开始，用对应的s31服务，所用时间为2；任务p4从10时开始，用对应的s41服务，所用时间为5；任务p5从15时开始，用对应的s51服务，所用时间为3；任务p6从18时开始，用对应的s61服务，所用时间为3。
-
结合上述不同算法求得的完工结果，可求出每种算法在不同时刻达到的准确率及所用时间，如图 2a所示；并能得到不同的完工路径，如图 2b所示。
从图 2a中可知，对应业务进行到任务p6时的准确率即完工准确率A，此时可看出AMG算法的完工准确率最大，但由于出现完工时间高于截止期的情况，因此该策略不能被执行。TMG算法和SRO算法的完工时间满足约束条件，因此利用完工准确率A1=0.783、A2=0.727，可计算SRO算法相对于TMG算法的优化率K=7.7%。因此，SRO算法具有一定优化调度优势。图 2b可知，SRO算法从开始到完成，其服务选择为s13-＞s22-＞s31-＞s41-＞s51-＞s61。
5.1. 案例设计
5.2. 算法分析
5.2.1. 传统单向目标算法策略
5.2.2. SRO算法
5.3. 算法比较
-
截止期ψ是工作流的最晚完工时间，随着截止期的增大，业务流程的总体准确率也会得到优化。本文采用的基于串归约的时间-准确率优化算法主要是建立在时间约束的基础上，因此通过增大截止期，某些任务的自由度也会变大，可以选择更佳的服务来执行。实验选择任务数为10和15的业务流图，并以区间[2, 4]的随机值作为服务池大小，每个任务具有服务及其对应的属性等特性。以Tmin作为每个业务流图的最小完工时间，并在此基础上增加10%、15%、20%、25%、30%作为业务流图的不同截止期，业务流图在不同截止期下达到的最大完工准确率A如图 3所示：
通过图 3可得出，当截止期为Tmin时，即基于时间最小化策略。不同的业务流程，随着截止时间的增大，相对于以时间最小化为目标的算法，串归约优化算法的准确率越来越大，算法性能得到了优化。因此，在实际的业务过程中，可适当用大点截止期，串归约算法的优化作用将会越来越明显。
-
工作流中的某条路径的准确率是通过该路径上所有服务准确率的乘积而来，随着任务数目的增多，对整体的完工准确率A及SRO算法的优化效果均会产生不同的影响。实验选择集合{5, 10, 15, 20}中的值为任务数，并以区间[2, 4]的随机值作为服务池大小，每个任务具有服务及其对应的属性等特性，生成不同的业务流图。以Tmin作为每个业务流图的最小完工时间，并在此基础上增加20%作为不同流图的截止期，不同业务流图在不同算法策略下达到的完工准确率A如图 4所示。
从图 4的数据可以得出，随着任务数目的增多，每个环节都存在着偏差，总体的完工准确率会随着降低，但串归约优化算法的优化效果更加明显，算法提高率分别为7.26%、11.4%、16.8%、25.2%。
6.1. 截止期ψ大小产生的影响
6.2. 任务的数目对性能的影响
-
针对工作流截止期约束下的准确率优化问题，本文采用了任务、服务与有向无环图DAG相结合的方式，生成工作流模型。在此基础上，提出了在截止期约束下的串归约优化算法，通过对工序的每个环节进行时间约束，以逆向迭代的方式，求得每层任务在不同时刻开始时的最大准确率，所有任务都完成时以最大完工准确率确定优化路径。实验数据表明，相比于传统的单向目标算法，串归约优化算法的优化率达到了7.7%。与此同时，本文还对影响优化效果的因素即截止期的范围和业务流程的任务量进行了分析。但还存在没能将业务流程的运作成本考虑进去的问题，在此还需要进一步研究讨论，充分考虑在业务流程中服务的相关属性，真正找出一条具有效率化、准确化并能充分降低成本费用的最佳路径，以后的研究会进一步地改进并加以完善。
DownLoad: