-
现代业务的工作流技术是在网络流的基础上以服务为基本元素进行架构,使多个服务相互协作来完成整个业务。工作流系统将业务流程抽象化,划分为诸多工序,并结合工序中的服务属性,确定最佳完工路径。然而,目前企业的项目流程,往往因为一个或者几个工序出现问题而影响整体,如追求效率而忽略了服务质量或者追求服务质量而拖延了完工时间,使得整个项目的完工时间和完工质量失衡。为此,应该使用更合理的方法,在业务流程规定的截止期内,选择一条能够有效提升复杂项目准确率的路径,达到既能充分利用资源,又能使效率和准确率实现平衡的目的[1]。
本文提出了一种加工型产品工作流在限定完工时间内,保证工序完工质量最高的算法,即实现了完工路径质量的串归约优化。
-
工作流建模是对业务过程的一个合理安排,能够有效地将服务安排到对应任务的服务集合中[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 截止期。指产品的生产约束限定时间,记为ψ。
对于建立的工作模型,此时需要有规定的约束策略,对流程的形式化为:
$$ A=\prod{{{l}_{pk}}{{a}_{pk}}}\;\;\;p\in P, 0<k\le {{r}_{p}} $$ (1) 即表示一条能够完成加工型产品路径的准确率。当执行一个任务时,只能选择一个服务来完成该任务,即:
$$ s.t.\sum\limits_{k = 1}^{{r_p}} {{l_{pk}} = 1\;\;p \in P} $$ (2) 完成加工型产品所用的时间必须低于或等于截止时间,即;
$$ T = \sum\limits_{}^{} {{l_{pk}}{t_{pk}}} \le \psi \;\;p \in P, 0 < k \le {r_p} $$ (3) 式中,lpk是一个变量,即:
$$ {l_{pk}} \in \{ 0, 1\} \;\;p \in P{\rm{, }}0 < k \le {r_p} $$ (4) 在截止期ψ下,以式(1)为启发目标函数,在式(2)~式(4)的约束条件下,求得能够完成加工型产品路径的准确率,此时采用不同的算法策略求得对应路径的准确率。
-
一个加工型产品的生产工序,承载着完工时间和完工准确率的属性,传统单向目标的算法策略是指在生产过程中,仅仅保证了完工时间最小或者仅保证了完工准确率最大。
-
选择每个工序完成时间最小的服务组成工作序列,即:
$$ \left\{ \begin{array}{l} {T_{\min }} = \sum {\min ({t_{pk}})} \\ A = \prod {{a_{pk}}\;\;\;\;0 < k \le {r_p}} \end{array} \right.p \in P $$ (5) 式中,Tmin为限定条件,即时间最小化;在限定条件Tmin下可求得完工准确率A。
-
选择每个工序完成准确率最大的服务组成工作序列,即:
$$ \left\{ \begin{array}{l} {A_{\max }} = \prod {\max ({a_{pk}})} \\ T = \sum {{t_{pk}}} \;\;\;\;0 < k \le {r_p} \end{array} \right.p \in P $$ (6) 式中,Amax为限定条件,即达到完工准确率最大化;在限定条件Amax下可求得完工时间T。
-
定义9 任务自由度WFp。即工作流模型中给定的任务的活动区间[STp,ENp],p∈P,这里的STp即该任务最早开始时间,ENp是该任务最晚开始时间。WFp的STp和ENp由式(7)求得:
$$ \left\{ \begin{array}{l} {\rm{S}}{{\rm{T}}_p} = \sum\limits_{i = 1}^{p-1} {\min ({t_{ik}})\;\;{\rm{S}}{{\rm{T}}_1} = 0} \\ {\rm{E}}{{\rm{N}}_p} = \psi-\sum\limits_{i = n}^p {\min ({t_{ik}})} \end{array} \right.0 < k \le {r_p} $$ (7) -
串归约优化算法是在每层任务的活动区间内选择合适的服务,实现复杂产品的完工时间和准确率平衡的目标。由于在活动区间内的服务存在不能充分利用时间的问题,因此会产生一些时间碎片。串归约算法充分利用在截止期范围内的时间,把时间碎片集中起来,产生一个局部最优解。本文以任务的自由度为基础,对于任务集合P中的每个任务p,都有一个WFp=[STp, ENp],采用动态规划的方式,以后继活动不同时间点开始时达到的局部最优解求得当前活动不同时间点开始时达到的最优解,通过比较完工的准确率确定最佳路径。
针对含有n个任务的工作流图,用f(p, t)表示工作流图中的第p个任务在时间t开始时达到的最大准确率,其中t∈[STp, ENp]。以最后一个活动为起点,迭代求出前驱活动相应的值,最后一个活动的f由式(8)求得:
$$ \left\{ \begin{array}{l} f(p, {t_p}) = \max \{ {a_{pk}}\} \;\;\;\;{\rm{ }}p = n, 0 < k \le {r_p}\\ {t_p} \in [{\rm{S}}{{\rm{T}}_p}, {\rm{E}}{{\rm{N}}_p}]\;\;\;\;{t_p} + {t_{pk}} \le \psi \end{array} \right. $$ (8) 对已经求解每个活动自由度的业务流程,以活动p的相关值f(p, tp),求解前驱活动p'对应的f(p', tp'),该迭代过程由式(9)求得:
$$ \left\{ \begin{array}{l} f(p', {t_{p'}}) = \max \{ f(p, {t_{p'}} + {t_{p'k}}) * {a_{p'k}}\} \\ {t_{p'}} \in [{\rm{S}}{{\rm{T}}_{p'}}, {\rm{E}}{{\rm{N}}_{p'}}] \end{array} \right. $$ (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)。
-
组装工艺的一般过程分为备料、形成坯件、零部件加工、部件组合、总组合和表面涂饰6个环节,存在虚拟的开始任务和结束任务,分别为申请和竣工,则该业务流程可抽象化表示p1, p2, p3, p4, p5, p6, ps, pe。此时每个环节对应一个服务池Sp,对应的服务带有一定的属性参数,数据如表 1所示。
表 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所示:
表 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。
Research on Serial Reduction Algorithm for Accuracy of Processing Products under Time Constraints
-
摘要: 完工时间和准确率是生产调度的两个重要属性,然而单属性优化算法只能完成单个属性的优化,无法动态平衡这些属性。针对此问题,提出了基于有向无环图的串归约优化算法。算法通过约束每个任务的活动区间并采用逆向迭代进行归约,达到每层选择最优服务的目的,从而实现了这两个属性的优化。实验表明,该算法可准确地得到一条完工时间和准确率相互平衡的优化路径,但其优化效率受限于完工截止期和任务数。最后,研究结论对生产调度多属性的优化提供了一定的参考。Abstract: Completion time and accuracy are the most important attributes of processing products' business, however, single attribute optimization algorithm only can optimize one attribute, let alone balancing these two attributes dynamically. In order to fix this problem, a serial reduction algorithm based on directed acyclic graph is proposed. The algorithm constraints each tasks' activity section by using backwards iterative eduction to choose appropriate service for achieving the optimization of these two attributes. Statistical data shows that serial reduction algorithm does get an optimized path with time and accuracy balance, but its optimization efficiency is limited by the completion deadline and the number of tasks. The research conclusion provides a certain theoretical reference for the optimization of production scheduling.
-
Key words:
- accuracy optimization /
- deadline /
- temporal consistency /
- workflow schedule
-
表 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); 表 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; -
[1] DE P, DUNNE E J, GHOSH J B, et al. Complexity of the discrete time-cost tradeoff problem for project networks[J]. Operations Research, 1997, 45(2):302-306. doi: 10.1287/opre.45.2.302 [2] BUYYA R, GIDDY J, ABRAMSON D. An evaluation of economy-based resource trading and scheduling on computational power grids for parameter sweep applications[C]//Active Middleware Services.[S.l.]:Springer, 2000:221-230. doi: 10.1007/978-1-4419-8648-1_19 [3] BUYYA R, ABRAMSON D, JONAT H G, et al. Economic models for resource management and scheduling in grid computing[J]. Concurrency & Computation:Practice & Experience, 2002, 14(13-15):1507-1542. doi: 10.1002/cpe.690/full [4] NASONOV D, VISHERATIN A, BUTAKOV N, et al. Hybrid evolutionary workflow scheduling algorithm for dynamic heterogeneous distributed computational environment[J]. Journal of Applied Logic, 2016, 299:83-92. doi: 10.1007/978-3-319-07995-0_9 [5] MA Z, CAO J, QIAN S. DDS:a deadline driven workflow scheduling algorithm for hybrid amazon instances[M].[S.l.]:Advances in Services Computing, 2015. [6] YOON D, KIM S H, KANG D K, et al. Hybrid workflow management in cloud broker system[C]//Cloud Computing.[S.l.]:Springer, 2015:145-155. doi: 10.1007/978-3-319-38904-2_15 [7] CHEN W, LEE Y C, FEKETE A, et al. Adaptive multipleworkflow scheduling with task rearrangement[J]. Journal of Supercomputing, 2015, 71(4):1297-1317. doi: 10.1007/s11227-014-1361-0 [8] 苑迎春, 李小平, 王茜, 等.基于逆向分层的网格工作流调度算法[J].计算机学报, 2008, 31(2):282-290. http://www.cqvip.com/QK/87339A/201003/33825133.html YUAN Yin-chun, LI Xiao-ping, WANG Qian, et al. Bottom level based heuristic for workflow scheduling in grids[J]. Chinese Journal of Computers, 2008, 31(2):282-290. http://www.cqvip.com/QK/87339A/201003/33825133.html [9] 苑迎春, 李小平, 王茜.基于串归约的网格工作流费用优化方法[J].计算机研究与发展, 2008, 45(2):246-253. http://edu.wanfangdata.com.cn/Periodical/Detail/jsjyjyfz201506016 YUAN Yin-chun, LI Xiao-ping, WANG Qian. Cost optimization heuristics for grid workflows scheduling based on serial reduction[J]. Journal of Computer Research and Development, 2008, 45(2):246-253. http://edu.wanfangdata.com.cn/Periodical/Detail/jsjyjyfz201506016 [10] 刘灿灿, 张卫民, 骆志刚.基于逆向分层的工作流时间-费用优化方法[J].国防科技大学学报, 2013, 35(3):61-66. http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201206022.htm LIU Can-can, ZHANG Wei-min, LUO Zhi-gang. Time and cost trade-off heuristics for workflow scheduling based on bottom level[J]. Journal of National University of Defense Technology, 2013, 35(3):61-66. http://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ201206022.htm [11] 曹斌, 王小统, 熊丽荣, 等.时间约束云工作流调度的粒子群搜索方法[J].计算机集成制造系统, 2016, 22(2):372-380. http://www.oalib.com/paper/5220383 CAO Bin, WANG Xiao-tong, XIONG Li-rong, et al. Searching method for particle swarm optimization of cloud workflow scheduling with time constraint[J]. Computer Integrated Manufacturing Systems, 2016, 22(2):372-380. http://www.oalib.com/paper/5220383 [12] 武星, 卓少剑, 张武.成本最优化工作流技术驱动的研发协同软件即服务应用[J].计算机集成制造系统, 2013, 19(8):1748-1754. http://www.oalib.com/paper/4718312 WU Xing, ZHUO Shao-jian, ZHANG Wu. Cost optimization workflow-driven SssS for collaborative research and development[J]. Computer Integrated Manufacturing Systems, 2013, 19(8):1748-1754. http://www.oalib.com/paper/4718312