三层虚拟工作流模型的非线性制造工艺多目标优化算法研究

罗智勇 王静远 谢志强 孙广路 杨 旭

伴随着第四次工业革命的步伐,中国的制造业已经进入供给侧改革和产业升级的关键时期.产品的制造由传统的简单线性工艺粗加工逐渐向现代的复杂非线性即反馈工艺细加工转变,其制造过程更具复杂性、多变性和高效性等特点[1].复杂产品的非线性细加工涉及生产车间、工艺设计及调度等多部门的协同控制,其过程具有反复性,必将产生大量的动态信息,若不能及时优化这些信息势必会降低产品的竞争力.提高产品的竞争力,其核心是解决制造工艺的多目标动态优化问题.生产时间、产品质量和费用成本是制造工艺的重要参数,如何动态平衡这些参数使其最优本身就是一个NP (Non-deterministic polynomial)难题[2],若增加工艺的多次反馈,即非线性等因素,则其优化过程将变得更加困难.“中国制造2025”和“新一代人工智能”为复杂产品非线性工艺多目标优化带来了机遇和指明了方向.智能制造[3]只有在充分融合非线性生产工艺的特点和多目标要求的约束下,将人工智能、云计算、建模仿真和优化控制等信息处理技术与具体的生产资源相结合,开发出有效的智能优化调度算法,才可能使制造业实现跨越式的发展,满足时代的要求.科学工作流以其具备建模仿真能力强、资源参数量化准确、智能算法及优化调度易开发等特点,使其在智能制造领域中具有独特的优势.因此,研究如何利用科学工作流实现非线性制造工艺的多目标优化调度具有非常重要的理论和现实意义.

近些年,将工作流技术应用在线性生产工艺的多目标优化调度,国内外学者进行了一定的研究.Arabnejad 等[4]面向服务计算,使用服务质量(Quality of service,QoS)付费的量化约束,提出了一种异构预算约束调度算法,该算法可以保证在用户指定的预算范围内执行成本,并最大限度地缩短用户应用程序的执行时间,从而较好地完成了制造工艺异构系统的多目标任务优化调度;Lv 等[5]在分析了产品制造工艺流程的制约关系后,提出了一种工作流优化模型,该模型可进一步缩短制造工期,使工艺达到最优,从而提高了产品竞争力;Mollajafari 等[6]为解决云制造时间成本最优问题,利用云计算和遗传算法等技术提出了一种新的基因型到表型映射的工作流调度算法,该算法利用设定的资源调度代价函数有效地解决了限定时间下成本最优的问题,随后验证了该算法的收敛速度等性能;Koch 等[7]为解决医用模型制造工艺中的磨削精度和可靠性等问题,通过分析铣削的铸造数据集与主参考数据集的映射变化规律,提出了一种数字工作流铣削模型,统计分析发现该模型可有效地解决医用模型制造的多目标动态调度问题;Kianpisheh 等[8]将约束工作流与蚁群算法相结合,通过定义工期和成本因素变量完成了对云制造工艺的优化调度;Chirkin 等[9]为解决工作流执行时间估计中的常见问题,提出了一种考虑工作流组件及其运行复杂性和随机方面的解决方案,该方案将制造工艺参数进行双重随机表示,并使用特性/分布函数简化了工作流图,提高了多目标平衡算法的性能和优化效果;Roberts 等[10]为动态平衡危险复合无菌产品的生产时间、员工安全感和工作满意度等参数,提出一种基于质量约束的辅助工作流系统模型,该模型限定生产质量,并根据员工匿名的在线调查动态修改模型参数使其达到最优,从而有效地解决了生产工艺多目标平衡问题;Lucas 等[11]通过工序上下层之间的关系建立了基于事件的工艺工作流模型,通过所提出的相关公式完成了对制造系统的优化调度问题;Stender 等[12]为解决不同条件下制造工艺质量提升的问题,提出了一种有限元分析工作流模型,该模型可完成热条件影响下制造工艺时间质量的优化调度问题;敬石开等[13]为解决云制造工艺多服务平衡可靠性等问题,提出了一种离散粒子群智能优化工作流多目标调度算法,该算法通过不断优化云制造工艺参数,并根据智能算法的语义分析实现多服务匹配,从而确保了云制造多服务选择的可靠性问题;张玺等[14]采用人工智能理论提出了一种模糊Petri 网工作流模型,对制造车间在不确定环境下的制造工艺进行了资源重调度优化,实现了时间和成本的动态平衡;张萌等[15]为更好地解决制造工艺服务级别优选难的问题,提出了基于工作流的限定区间多目标优化调度算法,该算法将制造工艺区分成若干个区间,根据各区间的特点使用非支配排序改进型遗传算法对其进行局部优化,通过处处选取局部最优解完成整体优化,从而实现多目标调度的目的.

上述研究成果对于优化线性生产工艺的多目标动态平衡具有一定的先进性.然而,生产工艺错综复杂,尤其是某些工艺具有非线性特点,即反馈生产工艺.对于非线性工艺进行多目标多因素的优化调度,现有的研究成果无法完成.另一方面,非线性制造工艺在生产企业中普遍存在,企业急需对这类工艺进行优化调度.本文正是为解决非线性工艺优化调度问题而展开研究的,并在以往研究[16-17]的基础上,结合非线性制造工艺特点,考虑制造时间、质量和费用成本这些参数的制约关系,采用虚拟技术提出一种三层虚拟工作流模型Three-VMG (Threevirtual model graph)及其优化调度算法Three-OVMG(Three-optimal virtual model graph).该模型和算法的主要思想是首先建立非线性生产工艺的抽象结点层、虚拟工作流模型层和同构转换层,其次采用分段优化同构转换层的工艺参数,并由顶层向底层逐级传递优化解,最终实现工艺资源的动态平衡,为制造企业提供科学的决策依据和改进方案.由于模型采用虚拟技术,将工艺中的反馈工序结点虚拟为单个结点,从而将非线性工艺改造为虚拟线性工艺,实现了其多目标的优化调度.因此,该模型可用于解决非线性即反馈制造工艺的多目标优化调度问题.此外,该模型的三层结构,即底层工艺资源抽象层、中层结点工艺偏序层和顶层虚拟组合层,每层分别代表制造企业的不同关注面,先由下而上进行抽象优化形成决策,再由上而下传达决策修改配置参数.因此,这种三层模型较其他优化模型更具有建模清晰、高效快捷和简单明了等优势,值得推广.

1 问题描述

1.1 非线性制造工艺优化相关定义

非线性制造工艺虚拟工作流技术是根据非线性即反馈制约制造工艺特点将工作流与虚拟调度技术相结合为解决非线性制造工艺多目标动态平衡的一种综合优化调度技术.因此,其相关定义应体现虚拟、工作流和非线性制造工艺优化调度等技术的特性.

定义 1.制造工艺原始工作流.该工作流可定义为M(Pet,H,C,W),式中,M为工作流名称;Pet为其所继承的原始Petri 网名称,可定义为:Pet(B0,E0,P,T,L,Q),式中,B0为Petri 网开始状态结点;E0为Petri 网终止状态结点;P为工位结点抽象集,表示为P=(p0,p1,···,pn);T为迁移结点抽象集,表示为T=(t0,t1,···,tm);L为关系有向边抽象集,表示为L=(l0,l1,···,ly);Q为Petri 网中各结点间变换条件的权重值抽象集,表示为Q=(q0,q1,···,qz);H为各结点被加工所消耗的时间抽象集,表示为H=(h1,h2,···,hi,···,hn);C为各结点被加工所需费用的抽象集,表示为C=(c1,c2,···,ci,···,cn);W为各结点所加工产品的质量抽象集,表示为W=(w1,w2,···,wi,···,wn).

定义 2.虚拟结点s′.表示对多个结点进行组合,进而看作整体,成为一个虚拟结点,记为前者表示结点si至结点sj之间多结点的组合,后者表示结点si,sj两结点的组合,由多个虚拟结点s′构成的集合称为虚拟结点集合S′,其中,结点s可以是工位结点p也可以是迁移结点t,若结点s=p,则虚拟结点s′记为p′,若结点s=t,则虚拟结点s′记为t′.采用虚拟结点技术对非线性制造工艺进行处理,使其变为虚拟线性制造工艺的过程称之为虚拟技术.

定义 3.制造工艺虚拟工作流.该工作流可定义为VM(M,CP,P′,T′,Id,Od),式中,VM为虚拟工作流名称;M为制造工艺虚拟化前的原始工作流;CP是非线性制造工艺中所设置质量检测结点抽象集,表示为CP=(cp1,cp2,···,cpi,···,cpk),k为检测部门数,cpi表示工作流VM变换到检测部门i时,该部门对其直接前驱工位结点pj加工产品的累积生产质量Fw(pj,hj)和累积加工费用Fc(pj,hj)进行检测,当满足Fw(pj,hj)≥此处要求的质量δiw并且Fc(pj,hj)≤此处要求的费用δic时,工作流VM继续进行变换,执行该部门的直接后继工位结点pq继续加工,否则工位结点pj加工的产品未通过检测,需反馈至结点pj的某个前驱工位结点pj-x处进行精修,直到工作流VM重新变换至工位结点pj且满足检测点cpi的检测要求,整个过程的加工时间累积,因此检测点cpi=(δiw,δic),δiw和δic的值由具体加工部门确定;P′为非线性工艺中进行虚拟重构后工位结点抽象集,表示为T′为工艺重构后的虚拟迁移结点抽象集,表示为Id为工作流VM中各结点入度值的抽象集,表示为Id=(id1,id2,···,idi,···,idz);Od为工作流VM中各结点出度值的抽象集,表示为Od=(od1,od2,···,odi,···,odz).

定义4.制造工艺虚拟工作流图.该工作流图可定义为VG(V M,E),式中,VG为名称;VM为虚拟工作流名称;E为图中所有有向边的抽象集,表示为E=(e1,e2,···,ei,···,en),集合E反映VM中所有结点的工序.

定义5.制造工艺三层虚拟工作流,是指由制造资源集合和模型VM及虚拟工作流图VG所构成的决策优化调度过程图,可定义为Three-V MG(Re,Map,V M,V G),式中,Three-VMG是制造工艺三层虚拟工作流名称;Re是制造资源集合由集合P和集合T构成;VM是制造工艺虚拟工作流模型;VG是制造工艺虚拟工作流图;Map是制造资源集合向模型VM映射关系的集合,可表示为Map=(map1,map2,···,mapi,···,mapn+m).

定义6.合同矢量V,是指工艺所交付的产品应满足所签订合同的各项指标,本文设定为V=(vh,vc,vw),式中,vh是时间限定,vc是费用限定,vw是质量限定,要求交付产品的时间和费用不能超过vh和vc,质量不能低于vw.

1.2 非线性制造工艺Three-VMG 模型优化规则定义

由于三层虚拟工作流Three-VMG 模型具有一定的反馈制约等特性,为更好的识别其静态数据关联及生产过程中的动态转换关系,为此本文设定了一系列Three-VMG 模型应遵循的优化规则和约束条件,具体如下:

1)工作流VM的虚拟工位结点集P′识别重构.在工作流VM中,若多个工位结点构成一个完整的非线性即反馈制约关系,则这些结点可进行重构,记为虚拟工位结点,标记为表示由相邻的工位结点pi和pj重构后的虚拟工位结点;表示由工位结点pi开始至工位结点pj结束所包含若干工位结点重构后的虚拟工位结点.由所有重构后的虚拟工位结点所构成的集合,记为虚拟工位结点集P′.

2)工作流图VG的工位结点pi的优选域识别.工位结点优选域是指该结点可选择最优加工过程的时间范围域,可定义为OSDi[SrTi,EdTi],式中,OSDi为优选域名称,SrTi为工位结点pi可选加工过程的最早开始时间,EdTi为工位结点pi可选加工过程的最迟开始时间,优选域OSDi中的参数可由式(1)进行计算:

式(1)中,SrTpq和EdTpp为pi的直接前驱和后继工位结点pq的最早和最迟开始时间.

3)工作流图VG的加工域识别.重构后的工作流图VG中,令集合N′是结点集N(N=P∪P′)的子集,则由集合N′中各结点所构成的局部工作流所确定的最小和最大合同矢量V.vhmin和V.vhmax值区间,识别为该结点集的加工域,记为τ=[V.vhmin,V.vhmax].集合N′加工域τ的参数可由式(2)进行计算:

4)工作流图VG的虚拟歧途径识别.虚拟歧途径是指VG中,若存在某结点ni可与结点nj进行重构形成新的虚拟结点,但结点ni的部分出度边又可与结点nk进行重构形成另外新的虚拟结点,则由结点ni和nk构成的途径标记为歧途径,用VWRni表示,其中,ni,nj和nk互不相同.例如:某虚拟工作流图W,其结构如图1 所示.经分析,该工作流图共有4 个加工域分别进行标注.在加工域1 中,工位结点n15和n16可进行重构形成新的虚拟结点.在加工域2 中,工位结点n18和n19可进行重构形成新的虚拟结点.由于结点n16存在2 条出度边,其中一条可与n18进行重构虚拟,另外一条则不能进行重构虚拟,因此由结点n16,n18和n19所组成的途径为虚拟歧途径VWPn16.

图1 虚拟歧途径的识别过程Fig.1 The process of virtual wrong route recognition

5)工作流图VG的生产参数标识规则.虚拟工作流图VG中,令AHq,ACq和AW q为工作流图进行到结点nq时的累积生产时间、累积生产费用和累积生产质量,AHp和ACp为其直接前驱结点np的累积生产时间和累积生产费用,则AHq,ACq和AW q的值可通过式(3)进行计算.若nq=nE0,则AHE0,ACE0和AW E0表示工作流图VG执行完毕后所达到的最终生产时间、生产费用和生产质量.

式(3) 中,lij表示工作流图VG转换至工位结点ni时,选用迁移结点tj来进行后续转换,由于选择具有互斥性,因此lij=0 或1;N′表示工作流VG换至工位结点nq时,已经执行完毕的工位结点集.

本文要求所建立的三层虚拟工作流Three-VMG 模型在满足合同矢量V约束的前提下,利用规则1)～ 4)实现规则5)的各项参数最优.

1.3 非线性制造工艺三层虚拟工作流调度建模算法Three-MVMA

汲取部分以往研究成果并遵循第2.2 节中的相关规则和约束后,设计非线性制造工艺三层虚拟工作流调度建模算法Three-MVMA 如下:

步骤 1.分析非线性制造工艺,统计生产工位形成工位结点集P,分析各工位结点的转换状态形成迁移结点集T,将工艺中各检测数据汇总形成检测结点集CP;

步骤 2.结合工位结点集P和迁移结点集T的偏序关系构建原始工作流模型M;

步骤 3.根据非线性制造工艺,按序将cpi(cpi ∈CP,i=1,2,···,k)插入到原始工作流模型M中,调整有向边集合L,形成新的偏序关系;

步骤 4.输入合同矢量V,利用式(1)计算模型M各工位结点的优选域OSD;

步骤 5.从工位结点B0开始广度优先遍历模型M的工位结点集P,统计集合P中出度od和入度id不为1 的工位结点,将其插入至队列List中,其中反馈前置结构中各工位结点不入队;

步骤 6.出队List中的队首出度od不为1 的工位结点pj,寻找与其最近的反馈入度工位结点pi,重构结点pi流经结点pj之间的所有工位结点,将其标注为虚拟工位结点将结点暂时保存至虚拟工位结点集P′中,将此过程中所涉及迁移结点重构为虚拟迁移结点并保存至虚拟迁移结点集T′中;

步骤 7.重复步骤6 直至队列List为空;

步骤 8.按序移出集合P′和T′中的虚拟工位结点和虚拟迁移结点,使用规则4)进行判断,检查它们是否构成虚拟歧途径,若不构成VWR则正式进行虚拟重构并修改模型M且更新模型VM,若构成VWR则不能进行重构,删除该虚拟工位结点和虚拟迁移结点并恢复构成虚拟结点的工位结点和迁移结点;

步骤 9.若集合P′或T′不为空,则循环执行步骤8,否则标记模型VM并输出;

步骤 10.利用式(2)并遍历虚拟工位结点集P′,计算各工位结点的加工域τ,将其标注至模型M中;

步骤 11.遍历模型VM,统计相邻工位结点pi至pj(pi≠pj)的全部途径,将其建立有向边ejk,其中k=1,2,···,idpj,计算有向边ejk的参数hjk,cjk和wjk,标记这些参数形成虚拟工作流图VG;

步骤 12.重复步骤11 直至工作流趋于稳定,形成工作流图VG;

步骤 13.将制造资源集合Re、映射集合Map、虚拟工作流模型VM和虚拟工作流图VG进行组合,形成三层虚拟工作流Three-VMG,将其输出.

根据上述策略,给出建模算法Three-MVMA的伪代码如下:

算法1.Three -MVMA 算法

输入.集合P,集合T,集合Q,集合H,集合C,集合W,集合Id,集合Od,集合CP,合同矢量V;

输出.虚拟工作流模型VM,虚拟工作流图VG,三层虚拟工作流Three-VMG;

1.4 非线性制造工艺三层虚拟工作流决策模型实例验证

某公司汽车制造冲压工艺质量控制流程如图2所示,经分析该工艺流程呈现非线性的特点,可用三层虚拟工作流决策模型对其完工时间、生产质量和费用等参数进行多目标优化调度.

图2 汽车制造冲压加工工艺Fig.2 Stamping process of automobile manufacturing

根据一般统计发现,该公司进行冲压加工所需原材料常用供应商共计3 个,其供应号设定为:B1,B2和B3;采购部门共计设立2 个质检组,其编号设定为:C1和C2;冲压工艺形成的中间件进行质量抽查组共计有2 个,其编号设定为:S1和S2;冲压件在进入库存前的质量检测组共计有3 个,其编号设定为:D1,D2和D3.为便于研究,忽略该工艺流程的某些次要矛盾,将其主要矛盾进行非线性工作流分解,得出相应的结点记为:工位结点集合P和迁移结点集合T,各集合的情况如表1 所示.

表1 冲压工艺质量检测结点集合P 和TTable 1 Node set P and T of stamping process quality inspection

将集合P和集合T的各元素输入至Three-MVMG 算法后,形成非线性冲压工艺质量检测的三层虚拟工作流如图3 所示.

图3 冲压工艺质量检测三层虚拟工作流Fig.3 Three-tier virtual workflow for stamping process quality inspection

2 非线性制造工艺三层虚拟工作流调度模型优化算法Three-OVMG

定义7.三层虚拟工作流调度输出途径VRoute.该途径是指非线性制造工艺经优化调度算法处理后给出的最佳调度途径,由相关虚拟结点、有向边和生产参数组成,可定义为VRoute(P′,E,A),式中,VRoute是最优输出途径名;P′是组成该途径的虚拟工位结点集;E是偏序有向边集合;A是该途径各虚拟工位结点的累积参数集,表示为A=(a1,a2,···,ai,···,am),式中,ai为结点pi(pi ∈P′) 的累积参数,表示为ai=(aiH,aiC,aiW),m为集合P′的结点数.

假设函数ƒw(pi,hpi)和ƒc(pi,hpi)表示虚拟工作流Three-VMG在时刻hpi处,工位结点pi在其优选域OSDpi[SrTpi,EdTpi]内所选中的最高生产质量和最低费用,则该时刻下可使用式(4)计算工位结点pi的ƒw(pi,hpi)和ƒc(pi,hpi):

虚拟工作流Three-VMG中,任意两工位结点pi-1和pi(pi-1∈P′,pi ∈P′),若pi-1是pi的前驱结点,则可使用式(5)来计算结点pi-1的累积生产质量和费用:

式(5)可由后向前完成对工作流Three-VMG的优化求解,然后通过这些解完成非线性制造工艺资源的正向调度.由此,可设计三层虚拟工作流优化算法Three-OVMG.

步骤1.调用建模算法Three-MVMG 处理非线性制造工艺各参数,形成三层虚拟工作流Three-VMG 模型;

步骤2.结合合同矢量V由后向前将模型Three-VMG 分层,利用式(1)分析并计算每层形成各工位结点pi的优选域OSDpi[SrTpi,EdTpi];

步骤3.利用式(4)计算并标记结束层的工位结点E0在其优选域OSDE0内,各时刻的ƒw(E0,hE0)和ƒc(E0,hE0);

步骤4.全面处理模型Three-VMG,若工位结点不存在虚拟歧途径VWR,则使用逆向串规约且利用式(4)计算并标记各工位结点pi在其优选域OSDpi内,每个时刻的ƒw(pi,hpi)和ƒc(pi,hpi);

步骤5.若工位结点在虚拟歧途径VWR中,则首先利用式(2)计算VWR的加工域τ,然后利用式(4)串行计算并标记该域τ下的各工位结点pi不同时刻的ƒw(pi,hpi)和ƒc(pi,hpi);

步骤6.利用式(3)并遵循合同矢量V的约束,全面处理标记后的模型Three-VMG 的工位结点P集合,确定并输出最优调度途径VRoute.

算法Three-OVMG 其所对应的伪代码如下:

算法2.Three -OVMG 算法

3 非线性制造工艺Three-VMG 模型优化案例分析

为验证上述建模及优化调度算法,这里仍选用某公司汽车制造冲压工艺质量控制流程进行分析.实验所用服务器操作系统为Windows Server2016,内存配置至少8 GB,采用Java语言开发建模算法Three-MVMG 和优化调度算法Three-OVMG 的代码,设定合同矢量V为:V.h=111 天,V.w=0.98×100%,V.c=20 万元.

3.1 非线性冲压工艺Three-VMG 模型优化过程

为验证模型Three-VMG 的优化调度过程,这里仍选用第2.4 节所述工艺,该工艺在忽略突发事件及其他附情况的前提下,加工某批工件的质量控制数据如表2 所示.

将图3 所示的该工艺模型输入算法Three-OVMG 后,代入表2 中的数据并遵循合同矢量V的约束,形成最优的虚拟调度途径VRoute,其过程如图4 所示.

根据该工艺特点将图4 的调度过程分为两个优化段.由于合同矢量V.h=111 天,因此将第1 个优化段的原材料采购质量控制非线性工艺的合同约束时间定为V.h1=60 天,将第2 个优化段的冲压质量控制非线性工艺的合同约束时间定为V.h2=51天.根据工艺要求,在第1 个段中,采购部质检抽查组设置的检测点cp1=0.950,无费用约束,当工作流转换到该检测点时,若此时的fw(pi,hpi) ＜ 0.950时,则需要反馈至前向工位结点进行质量缺陷修改,生产时间延误5 天,费用增加5 万;在第2 个段中,车间质检抽查组设置的检测点cp2=0.975,无费用约束,当工作流转换到该检测点时,若此时的fw(pi,hpi)＜ 0.975时,则需要反馈至前向工位结点进行质量缺陷修改,生产时间延误3 天,费用增加1 万.两个段之间采用累积传递的策略进行衔接,利用式(1)～ (5)及表2 中的数据,可完成对图4 工艺各工位结点ƒw(pi,hpi) 和ƒc(pi,hpi) 的计算,过程如下:

图4 工作流Three-VMG 的调度过程Fig.4 Process of workflow Three-VMG

表2 各部门服务的时间、质量和费用Table 2 Time,quality and cost of departmental services

1)经计算,工位结点p1,p2和p3的优选域分别为:OSD1=[0,7],OSD2=[20,27]和OSD3=[35,42].它们符合虚拟重构要求且不存在VWR,故将其重构为虚拟工位结点的加工域:τ1=[35,35].

2)根据τ1和OSD1、OSD2、OSD3的值,计算第一阶段各工位结点pi的ƒw及ƒc如下:

工位结点p3的计算过程为:

工位结点p2的计算过程:

工位结点p1的计算过程:

由上述过程可知,第1 阶段由后至前累积到p1的ƒw(p1,0),ƒw(p1,1),ƒw(p1,2),ƒw(p1,3)和ƒw(p1,4)值所用生产时间分别为:60 天、59 天、58 天、57 天和56 天,但这些路径的累积生产质量fw＜ 0.950,不满足检测点cp1要求需返回前至修改.它们修改一次后的累积生产时间变为:65 天、64 天、63 天、62 天和61 天,这些生产时间不满足合同矢量V.h1=60 天的要求,因此不能沿用这些路径进行工艺的优化调度,及时淘汰.

由累积到p1的ƒw(p1,5),ƒw(p1,6)和ƒw(p1,7)值所用生产时间分别为:55 天、54 天和53 天,同样这些路径的累积生产质量fw＜ 0.950,不满足检测点cp1要求需返回前至修改.它们修改一次后的累积生产时间变为:60 天、59 天和58 天,这些生产时间小于合同矢量V.h1=60 天,满足时间约束要求.因此,工艺修改正后它们的累积ƒw分别为:(p1,5)=0.912+(1 -0.912) × 0.912=0.992,(p1,6)=0.912+(1 -0.912) × 0.912=0.992,(p1,7)=0.912+(1 -0.912) × 0.912=0.992;修改后的累积ƒc分别为:(p1,5)=5+11.25=16.25 万元,(p1,6)=5+11.25=16.25 万元,(p1,7)=5+11.25=16.25 万元.优选生产时间最短且累积ƒw最高者,即(p1,7)=0.992.此段工艺将沿此途径进行资源优化,即:VRoute1=B0→p1/t1B3→p2/t2→p3/t3C2.

3)由于第2 阶段为第1 阶段的后续工艺且合同矢量V.h2=51 天,因此此阶段的初始生产质量ƒw=0.992.经计算,工位结点p4、p5、p6和p7的优选域分别为:OSD4=[0,4],OSD5=[1,5],OSD6=[21,25]和OSD7=[28,32].它们符合虚拟重构要求且不存在VWR,故将其重构为虚拟工位结点的加工域:τ2=[28,28].

4)根据τ2和OSD4、OSD5、OSD6、OSD7的值,计算第2 阶段各工位结点pi的ƒw及ƒc如下:

a) 工位结点p7的计算过程为

b) 工位结点p6的计算过程为

c) 工位结点p5的计算过程为

d) 工位结点p4的计算过程为

e) 此段工艺被加工一次后工位结点p4的ƒw(p4,h0-4) 和ƒc(p4,h0-4) 为

由上述过程可知,第2 阶段由后至前累积到p4的ƒw(p4,0),ƒw(p4,1)和ƒw(p4,2)值所用生产时间分别为:50 天、49 天和48 天,但这些路径的累积生产质量ƒw＜ 0.975,不满足检测点cp2要求需返回前至修改.它们修改一次后的累积生产时间变为:53 天、52 天和51 天.若沿此途径继续转换至工位结点E0,则累积生产时间变为:54 天、53 天和52 天,均大于合同矢量V.h2=51 天,不满足时间要求.因此,不能沿用这些路径进行工艺的优化调度,及时淘汰.

由累积到p4的ƒw(p4,3)和ƒw(p4,4) 值所用生产时间分别为:47 天和46 天,同样这些路径的累积生产质量ƒw＜ 0.975,不满足检测点cp2要求需返回前至修改.它们修改一次后的累积生产时间变为:50天和49 天.若沿此途径继续转换至工位结点E0,则累积生产时间分别为:51 天和50 天,均小于合同矢量V.h2=51 天,满足时间要求.因此,工艺修改正后它们的累积ƒw分别为:(p4,3)=0.918+(1-0.918) × 0.925=0.994 和(p4,4)=0.910+(1-0.910) × 0.917=0.993;修改后的累积ƒc分别为:(p4,3)=1+17.81=18.81 万元和(p4,4)=1+17.79=18.79 万元.优选累积ƒw最高者,即(p4,3)=0.994.此段工艺将沿此途径进行资源优化,即:VRoute2=p4/t4→p5/t5S1→p6/t6→p7/t7D3.

5)将第1 阶段和第2 阶段工艺采用段间累积的方法进行整合,整合后此工艺的最终累积ƒw=0.999 ×0.994=0.993,累积ƒc=0.04+18.81=18.85 万元,累积ƒh=1+50+58=109 天.由于最终累积ƒh＜合同矢量V.h,满足要求,因此最终输出的优化调度虚拟途径VRoute=VRoute1+VRoute2=B0→p1/t1B3→p2/t2→p3/t3C2→p4/t4→p5/t5S1→p6/t6→p7/t7D3→E0.

3.2 Three-VMG 模型虚拟重构及算法比较

图5 给出了模型Three-VMG 被算法Three-OVMG 处理后,各工位结点的虚拟重构归约优化过程.

图5 虚拟结点重构过程Fig.5 Virtual node reconfiguration process

算法Three-OVMG 扫描模型Three-VMG 的工位结点集P,按规则将工位结点p1、p2、p3进行重构形成虚拟工位结点将工位结点p4、p5、p6、p7进行重构形成虚拟工位结点虚拟工位结点均不存在虚拟歧途径VWR,因此整个工艺优化后的最终ƒh2、ƒw2和ƒc2分别为:109 天、0.993 和18.85 万元.

将该工艺和表1、表2 的数据分别输入时间最小化优化调度算法[18]和算法Three-OVMG 中,设定合同矢量V.h=111 天,得出两条资源调度途径VRoute,如图6 所示.

图6 调度途径VRoute 输出对比Fig.6 Comparison of scheduling routes Vroute output

图6 所示工艺经时间最小化优化调度算法处理后被分为两个优化段,第一段被优化后的累积ƒ1h1,ƒ1w1和ƒ1c1分别为:58 天、0.990 和16.25 万元;第二段被优化后的累积ƒ2h1,ƒ2w1和ƒ2c1分别为:47 天、0.992 和2.04 万元.因此,整个工艺被优化后最终的ƒh1,ƒw1和ƒc1分别为:106 天、0.991 和18.33 万元.

比对最终的累积ƒw值发现:相对于时间最小化优化调度算法,算法Three-OVMG 最终优化的生产质量提升0.202%,即:Δ=(fw2-fw1)/fw1×100%.该结果表明:在有限范围内相同合同矢量V约束下,算法Three-OVMG 的优化效果要好于时间最小化优化调度算法.

3.3 算法Three-OVMG 的性能分析

影响算法Three-OVMG 执行性能的因素众多,本文只研究了算法在有限范围内不同合同矢量V.h和不同工位结点数集合P因素下执行性能的受影响情况.

1) 有限范围内不同合同矢量V.h对算法的影响

限定工位结点集P中数目为10 和15 个,各工位结点pi的迁移结点集T中数目为集合{2,3,4,5}的随机数,按5%、10%、15%、20%、25%的比例增加合同矢量V.h,调用算法Three-OVMG 执行,得出有限范围内不同合同矢量V.h对算法的影响,如图7 所示.

图7 合同矢量V 对性能的影响Fig.7 Effect of contract vector V on Performance

图7 指出,在有限范围内合同矢量V.h的值跟算法Three-OVMG 优化调度后工艺最终的ƒw值成正比关系.

2) 有限范围内不同工位结点数P集合对算法的影响

限定增加20%的合同矢量V.h后,将工艺的工位结点集P中数目分别设定为5、10、15 和20 后,各工位结点pi的迁移结点集T中数目为集合{2,3,4,5}的随机数,调用算法Three-OVMG 执行,得出有限范围内不同工位结点数P集合对算法的影响,如图8 所示.

图8 指出,在有限范围内工位结点集P中数目跟算法Three-OVMG 优化调度后工艺最终的ƒw值成反比关系.然而,同时间最小化调度算法相比,算法Three-OVMG 优化调度后工艺最终的ƒw值有所增加,其增加比为:1.58%,3.68%,11.13%,15.45%.

图8 工位结点数对性能的影响Fig.8 Effect of workplace node numbers on performance

4 结束语

制造工艺的多目标优化调度具有一定的难度,尤其是当工艺呈现出非线性即反馈制约时,现有的研究成果无法实现优化调度,本文针对这一不足提出了三层虚拟工作流决策模型及其优化调度算法.该模型汲取了虚拟技术的部分思想,并根据反馈制约工艺建立反馈工作流.随后,结合所提出的虚拟工作流调度模型识别规则对其扫描,重构工艺的虚拟结点,构建三层虚拟工作流模型.通过对模型进行逐级分段,段内采用虚拟串归约技术进行多目标动态优化,段间采用多目标优化结果累积传递和虚拟正向调度策略从而实现了对整个模型的优化调度.经验证,这种三层虚拟工作流优化调度方法具备虚拟特点,简化了非线性制造工艺流程,增强了对这些反馈制约工艺的描述,有效地完成了多目标优化调度.此外,该模型调度方法具备一定的启发性,值得进一步研究.