基于串归约的时间约束下工作流精确率优化算法

罗智勇　朱梓豪　尤波　苗世迪

摘要：复杂产品的业务调度依赖于完工时间和精确率等属性，追求单一的目标不能保证这两个方面的平衡。传统的算法经常是以花费时间最小或者保证完工质量最佳为目标，这样会导致产品质量过低或者完成产品所用的时间过多。针对这种弊端，提出了约束时间下精确率串归约优化算法SRA，通过约束任务得到活动区间来进行优化路径。最后在典型案例中，分别利用了传统的单向目标算法和串归约算法求解对应的路径，并对算法SRA优化效果的其他参数进行了研究。研究表明，这种算法具有简单、高效、方便执行等优点。

关键词：

工作流调度；时间一致性；准确率优化；截止期

DOI：10.15938/j.jhust.2018.05.012

中图分类号： TP393

文献标志码： A

文章编号： 1007-2683（2018）05-0068-07

Abstract：Complex business scheduling depends on the completion of the time and accuracy and other attributes， the pursuit of a single goal cannot guarantee the balance of the aspects Traditional algorithms often take the least time or the best quality as goal， it leads to the low quality low or the more time taken to complete the product Aiming at this drawback， the SRA of the exact rate with string reduction optimization under the constraint time proposed， and obtains the active interval by the constraint task Finally， in the typical case， the traditional oneway target algorithm and the string reduction algorithm are used to solve the corresponding path respectively， and analyzed the other parameters that affect the performance of SRA The research shows that this algorithm has the advantages of simple， efficient and convenient implementation

Keywords：workflow scheduling； time consistent； accuracy optimization； deadline

0引言

复杂产品工作流是以网络流为基础，结合调度技术，并以服务为基本构成单位的一种架构技术[1-2]，主要用于表征多服务相互协调工作来完成整个产品加工的过程。工作流将业务流程抽象化，划分为诸多工序，结合工序中服务属性，确定最佳完工路径。在工作流中，每个任务中服务的选择极为重要，它决定着整个业务的效率及完工质量。能否合理地选择任务中对应的服务，对整个业务流程的有效执行起着重要的影响。

目前企业在复杂项目的实施过程中，工作流模型所需要的资源类型在模型的构建中就已经确定了，在实际的项目下发后，企业也能够及时地分配好任务，并利用对应的服务展开工作。但是项目流程作为一个整体，并被分成几个工序，往往因为一个或者几个工序存在问题，诸如追求效率从而忽略了服務质量或者追求服务质量而拖延了完工时间，使得整个项目的完工时间和完工质量失衡。因此单方面地追求效率，将会导致准确率过低，相反单方面追求服务准确率，反而影响复杂产品的完工时间。为此，应该使用更合理的方法，在业务流程规定的截止期内，选择一条能够有效提升复杂项目准确率的路径，达到既能充分利用资源，又能使效率和准确率实现平衡的目的[3]。本文提出了一种在限定完工时间内，通过串归约算法（serial reduction algorithm， SRA）来优化生产精确率的解决办法，达到时间和生产精确率的相对平衡。

1相关工作

工作流模型主要由任务和服务组成，其中任务代表了加工工序，而服务则代表了完成该任务所用的成本、工期和生产精度等属性[4]，合理平衡服务中的各属性参数对优化工作流模型中的任务调度具有关键性作用[5-6]。随着工作流技术的不断完善，已不再以单纯的优化工期为研究目的，而是向着动态平衡工期和生产精度等更深层次优化提出了严格的要求。文[7]提出在时间限制条件下优化成本的问题实际上是一种NPhard问题；文[8]基于时间约束下提出了3种降低成本的启发式算法；文[9]对截止期约束下的优化成本问题提出了正向分层的策略，在每个环节的约束时间内选择费用最小的服务；文[10]提出了串行和并行的实例集合，在网络模型的基础上进行建模；文[11]在业务的网络图中，将整个业务分解为多个环节，对每个分量做出了时间约束并进行优化；文[12]中Pawel通过对工作流程中成本与时间的分析，对每个任务选择合适的服务，优化了工作流的线性组合；文[13]通过AMPL模型实现了约束时间下成本的最小化；文[14]通过并行方式进行资源整合，降低了成本并且提高了质量。

基于在约束时间下降低成本的问题，国内也开展了相应的研究。文[15]采用动态资源选择策略，在相对较小的完工时间范围内，实现业务成本的最小化。文[16]运用了基于Markov链技术实现了工作流成本最小化。可见在工作流模型的服务属性中，确实存在着时间、成本和服务质量问题，如何保证在业务流程约束时间下对完工质量进行优化也是一个研究热点[17]。

2问题描述

21相关定义

定义1工作流模型。若用M表示模型，则M可形式化为二元组M=（R，Wr），其中R为任务池，由工序所涉及到的所有工作任务构成的集合，可表示为R=（r1，r2rirn），n为任务数；Wr为任务ri的服务池，是由完成该任务可选用的服务构成的集合，可表示为Wi=（w1，w2wjwm），m为服务数；在具体的业务过程中，任务ri与任务rj之间（i≠j）存在顺序关系，且每个任务r对应着服务池Wr，通过每个任务对应服务的合理搭配，实现整个工作流；任务池r中任意任务r所对应的Wr中的数目称为服务池的秩，可表示为zr。

定义2工作流图F。是一个有向无环图DAG，且F={wrk，rhrk，L}，其中：wrk代表任意任务r选择服务池Wr中第k个服务来加工；rhrk为服务属性且rhrk=（hrk，erk），代表着服务wrk全部的属性参数，hrk表示选择Wr中第k个服务w来加工任务r所用的时间参数，erk则表示生产精确率；L为有向边集合，代表各服务wi之间的偏序关系，且只有前驱层服务完成相关的任务ri后才允许开始后继层任务rj；r∈R，0

定义3任务自由度。指模型M中任务r的活动工作区间，表示为FDr=[IMr，ALr]，其中：IMr为任务r的最早启动时间，ALr为任务r的最晚启动时间，可由式（1）求得：

IMr=∑r-1i=1min（hik），0

ALr=DL-∑ri=nmin（hik），0

定理1工作流图F中，任意任务r其自由度FDr有且只有一个。

证明：存在FDr=[IMr，ALr]，有任务结点r，r′，并满足顺序关系，即r′在r之前执。

1）证明最早开始时间IMr′有且只有一个：此时假设任务r′的第k个服务的运行时间最短，即hr′k，则任务r最早开始时间IMr=IMr′+hr′k，依次递推，即每个任务的最早开始时间，则任务r的最早开始时间有且只有一个。

2）证明最晚开始时间ALr有且只有一个：反证法假设第r′的任务的最迟开始时间为ALr′，假设存在AL′r′ALr′ ，则AL′r′+hrk>DL，此时完工时间超过截止期，因此假设不成立。

综上所述，任务r的最早开始时间和最晚开始时间有且只有一个，所以任务自由度FDr也有且只有一个。

22工作流图生成算法

工作流图能有效地模拟出业务流程中的任务及对应服务，对管理人员详细掌握所有工作路径有着至关重要的作用。本文在以往的研究基础上[18-19]，结合工作流特点，给出生成工作流图的步骤如下：

1）划分业务流程的任务集合R，对R中所有任务r安排顺序，并对任务r规划出能够完成该任务的服务Wr；

2）在结点Begin处开始，添加任务层，将第一个任务的服务放到同一层中；

3）查询下一个任务，并将其对应的所有服务添加到同一层中，与前一层的所有任务形成顺序关系；

4）重复步骤3），直至没有任务为止，此时将最后一层服务集合连接到最终状态Final；

5）对所有的服务wrk添加属性rhrk；

6）工作流图完成。

根据上述的策略，可设计的工作流图生成算法WGGA的伪代码如下：

输入：参数wrk；rhrk；Begin；Final；len；zr；// len为集合R中的任务数目

输出：工作流图F

算法WGGA

Service_queue=NULL，F=NULL，len=Rlength；

For（intr=1；r<=len；i++）{ For（intk=1；k<=zr；k++）{Insert（Service_queue，wrk）}}；

r=1；For（k=1；k<=zr；k++）{Delete（Service_queue，wrk）；} //把任务1的服务出队

ADD wrk TO F； //把服务加入工作流程图F中；

Contact（Begin，wrk）；} //连接开始结点Begin和任务1的所有服务

For（r=2；r<=len；r++） {For（k=1；k<=zr；k++）{Delete（Service_queue，wrk）；}}

ADD wrkTOF； //把对应的服务加入到F中

Contact（wr-1k，wrk）；} //把前一层的任务的所有服务连接到下一层的所有服务

Contact（wrk，Final）； //把最后一层服务连接到结束结点Final

ADDrhrk TO wrk； //把服务属性添加进去

Return F。

该算法的时间复杂度为O（mn）。

23工作流图生成算法WGGA举例

假设工作流模型M的任务集合R为{α，β，γ，δ}，且每个任务都有对应的服务池Wα，Wβ，Wγ，Wδ，利用工作流图生成算法WGGA，输入基本参数后，生成该实例的工作流图F及相应参数如图1所示。

24工作流图F所满足的约束

工作流图F中各任务加工需满足一定的约束条件才能达到工业需求，式（2）为工作流图F用于计算截止期下生产精确率的公式及遵循的约束条件：

E=∏crkerk，H=∑crkhrk<=DL

st∑zrk=1crk=1，r∈R，crk∈{0，1}，0

式中：E为生产精确率，指沿着某路径所经过的不同任务r选择对应的服务wrk加工产品所得到的精确率；H为加工时间，指沿着某路径加工产品所花费的时间；DL为截止期，指加工产品的最晚完工时间；crk为互斥变量取值为1或0。

复杂产品的加工要求在不超过截止期DL内，以式（2）为目标函数，计算各工作流调度策略的加工时间H和精确率E，比较优化效果和性能指标。

3单指标优传统化调度算法[20]

31基于单指标H的传统优化调度策略ODSH

以优化最小完工时间Hmin为目标的传统工作流调度策略可节省更多的加工时间，这种策略在工作流图F中每次选择最小的加工时间h来进行调度，式（3）为在这种调度策略下求得的生产精确率E：

Hmin=∑min（hrk）

E=∏erk，0

32基于单指标E的传统优化调度策略ODSE

以优化最大加工精确率Emax为目标的传统工作流调度策略可获得最高的加工精确率，这种策略在工作流图F中每次选择最大的加工精确率erk来进行调度，式（4）为在这种调度策略下求得的完工时间H：

Emax=∏max（erk）

H=∑hrk，0

分析以上两种单指标优化调度策略发现其存在如下弊端：①实现完工时间Hmin最小化，则该路径完工精确率E可能会降低；②实现完工精确率Emax最大化，则该路径所用时间可能超过截止期DL，不能满足工业需求。

4基于串归约的时间-精确率优化策略SRA

串归约分层技术的核心思想是充分考虑业务流程的完工时间和完工精确率，即在截止期DL范围内，对每层任务划分活动区间，在其中寻找最优的服务，将复杂产品的生产工序转变为局部结点的执行，通过迭代的方式，找到一条完工时间和完工精确率平衡的路径。

若某工作流模型中的加工任务数为n，则令函数Φ（r，h）代表任务r从时刻hr开始在其活动区间[IMr，ALr]内所能达到的最大生产精确率。函数Φ（r，h）的值可通过式（5）进行计算：

φ（r，hr）=max{erk}，r=n，0

hr∈[IMr，ALr]，hr+hrk<=DL（5）

假設任务r的前驱为r′，则工作流模型整体被归约后，可通过先计算最后层任务的精确率反向求得前层任务的各自最大精确率，最终求得整个业务的最佳路径，此过程可通过式（6）来进行计算：

φ（r′，hr′）=max{φ（r，hr′+hr′k）×er′k}

hr′∈[IMr′，ALr′]（6）

综上所述，基于串归约的时间-精确率优化算法SRA如下：

1）调用算法WGGA生成工作流图F；

2）利用业务截止期并结合式（1）求得每个任务的自由度FDr；

3）调用式（5）求得在最后一层任务的自由度内，在不同时刻开始达到的最大精确率；

4）调用式（6），采用迭代的方式，求出每个服务在不同时间开始能达到的最大精确率；

5）比较最终的精确率，达到最大精确率的路径即为最佳路径。

5案例描述及算法应用

51案例描述

经调研某卡车装配的组装业务的流程分为车架总成、总装配流水线、布设电线、安装零件、加注油料、安装轮胎、膨胀水箱、调试下线等8个环节，经分析可将申请和竣工环节当作虚拟任务，作为开始与结束，则该业务环节构成了工作流里面的任务集合R，可抽象化表示为r1， r2， r3， r4， r5， r6， r7， r8，虚拟的申请、竣工环节为rB、rF；每个任务环节r对应一个服务池Wr。已知各服务集合中的任一元素的属性rhrk，结合服务可表示为wrk（hrk，erk），如w11（3，095）表示审批环节r1用该服务集合W1中的第一个服务w11来完成需要的时间为3，达到的准确率为095。其他任务对应的服务及其工作时间和准确率如表1所示。

52算法分析

若规定业务流程的截止期DL=30，则图2所示工作流图在不同优化算法下的调度过程如下：

分析图3可见，使用算法ODSE进行优化得到的完工准确率最大，但由于加工所用时间大于截止期DL而不能采用；采用算法ODSH和算法SRA进行优化，最终的完工时间均未超过截止期DL，因此可以采用且所得最大完工准确率为E1=0622、E2=0670。对于算法ODSH，算法SRA的优化提高率IR=（E2-E1）/E1×100%=771%。因此，算法SRA较传统单项目标优化算法具有更好的优化效果。

6不同截止期DL对算法性能的影响

截止期DL是加工任务必须遵守的完工限定时间，是工作流中重要的参数。一般情况下，截止期的变大使得最佳路径的完工准确率有所提高。算法SRA正是基于此参数的约束前提下，对各生产任务进行的优化。若改变DL值，则工作流中各加工任务r的自由度FDr也将进行改变，这使得自由度变大的任务可以选择准确率更高的服务，相反，自由度变小的任务由于不能超过最晚完工时间只能选择准确率较小的服务。对于案例所述工作流模型，不同截止期DL对算法性能影响的数据如表2所示。

分析表2可知，增大DL值，相对以时间最小化和以准确率最大化为目标的算法，算法SRA的提高率随之增大。因此，可通过适当增加工程要求的截止期，来达到增加算法SRA优化性能的目的。

7结语

针对时间约束下工作流生产精确率难于优化等问题，本文提出了一种串归约的时间-精确率优化算法SRA。该算法采用分层的思想并由后向前循环迭代，求得每层任务的自由度。在每个任务的自由度范围内，算法选择最佳服务，从而达到优化整体加工准确率的目的。案例分析表明，先对于传统优化算法ODSH和ODSE，算法SRA的性能提高了771%。未来的工作将围绕时间、精确率和成本等三方面以上因素来优化工作流调度。

参 考 文 献：

[1]I FOSTER C KESSELMAN，J M Nick， et al Grid Service for Distributed System Integration [J]. IEEE Computer，2002，35（6）：37-46

[2]DEELMANL E， BLYTHEL J Mapping Abstract Complex Workflows onto Grid Environments[J]. Journal of Grid Computing，2003，1（1）：25-39

[3]EDMONDS J，KARPR M Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems[J]. Journal of the ACM，2002，19（2）：248-264

[4]ALONSO G， CASATIF， KUNO H， et al Web Service Concepts， Architectures and Applications[M].Berlin： Springer，2004

[5]DUSTDAR S，SCHREINER W A Survey on Web Services Compositions[J]. International Journal of Web and Grid Services， 2005， 1（1）：1-30

[6]CHELLAMMAL S， GOPINATH G， MANIKANDAN S R An Approach for Selecting Best Available Services Through a New Method of Decomposing QoSconstraints[J]. Service Oriented Computing and Applications，2015，9（2）：107-138

[7]DE P， DUNNER E J， GHOSH J B， Wells C E Complexity of the Discrete Timecost Tradeoff Problem for Project Networks[J]. Operations Research， 1997， 45（2）： 302- 306

[8]BUYYA R， DAVID ABRAMSON， JONATHAN GIDDY， et al Economic Models for Resource Management and Scheduling in Grid Computing Concurrency and computation[J]. Practice and Experience Journal， Special Issue on Grid Computing Environment， 2002，14（13/15）： 1507-1542

[9]ABRAMSON D，BUYYA R，GIDDY J A Computational Economy for Gird Computing and Its Implementation in the NimrodG Resource Broker[J]. Future Generation Computer Systems（FGCS） Journal，2002，18（8）：1061-1074

[10]ADNENE G，FRANCOIS C Multiple Instantiation in a Dynamic Workflow Environment[C]//Proceedings of 16th International Conference on Advanced Information Systems Engineering，2004：175-188

[11]AKKAN C， DREX I A， KIMMS A Network Decompositionbased Bench Mark Results for the Discrete Timecost Tradeoff Problem[J].European Journal of Operational Research，2005， 165（2）： 339-358

[12]PAWEL CZAMUL Modeling， Runtime Optimization and Execution of Distributed Workflow Applications in the JEEbased BeesyClusterenvironment[J]. The Journal of Supercomputing， 2013， 63（1）：46-71

[13]MACIEJ M， KAMIL F， MARIAN B， et al Cost Optimization of Execution of Multilevel DeadlineConstrained Scientific Workflows on Clouds[C]// Parallel Processing and Applied Mathematics，2014，8384： 251-260

[14]WOOJOONG K， DONGKI K， SEONGHWAN K， et al Cost adaptive VM Management for Scientific Workflow Application in Mobile Cloud[C]// Mobile Networks and Application， 2015，20（3）： 328-336

[15]張伟，秦臻，苑迎春 网格环境下工作流的费用-时间调度算法[J].计算机工程，2006，32（16）：97-99

[16]武星，卓少剑，张武成本最优化工作流技术驱动的研发协同软件即服务应用[J].计算机集成制造系统， 2013， 19 （8）： 1748- 1754

[17]陈成，薛恒新，张庆民 基于本体与多Agent的可靠供应链网络设计模型[J].计算机集成制造系统， 2011，17（1）： 142-150

[18]罗智勇，孙广路，刘嘉辉，等 攻击图算法在入侵防御系统中的应用[J].云南大学学报， 2012，34（3），271-275

[19]罗智勇，尤波，许家忠，等 基于三层攻击图的入侵意图自动识别模型[J].吉林大学学报， 2014， 44（5）：1392-1397

[20]苑迎春，李小平，王茜，等 基于逆向分层的网格工作流调度算法[J].计算机学报，2008， 31（2）： 282-290

（编辑：温泽宇）