两阶段混合算法求解集成工艺规划与调度问题

文笑雨 罗国富 李 浩 肖艳秋 乔东平

郑州轻工业学院河南省机械装备智能制造重点实验室，郑州，450002

0 引言

工艺规划和车间调度是制造系统中非常重要的子系统，对制造系统的产品加工能力、资源利用率以及生产效率有重要影响[1]。两者虽然相互独立，功能不同，但又相互制约。将工艺规划和车间调度视为独立的子系统单独进行研究，不利于提高制造系统的生产效率以及设备利用率。文献[2]指出，为了匹配车间的实时状态，必须对预先设定工艺路线的20%～30%进行重新规划。已有研究显示，将工艺规划和车间调度进行集成研究能够提高制造系统的效率[1]。

工艺规划和车间调度本身均为NP-complete问题，集成式工艺规划与车间调度(integrated process planning and scheduling,IPPS)问题更加复杂[3]。在制造企业中，工艺规划和车间调度往往是两个独立的部门，将两个部门完全进行整合并不现实。考虑到这一实际问题，工艺规划与车间调度的集成方法主要关注如何增加工艺规划与车间调度之间的信息交互,但是，工艺规划与车间调度关注点并不相同。工艺规划的主要任务是通过对工件加工特征、精度、材料等的分析，为工件选择合适的加工方法和加工参数。车间调度则需要在时序上确定多个工件的不同工序在不同机器上的开工时间。如果在工艺规划阶段仅仅考虑单个工件的工序顺序以及加工资源，极容易在车间调度过程中产生资源冲突问题，即工艺规划的结果对车间调度产生制约。IPPS问题存在着复杂的机器柔性、工序顺序柔性和加工路径柔性，使得问题解空间非常庞大，求解非常困难。

基于上述IPPS问题的复杂性和重要性，对IPPS问题的研究已经成为相关研究领域的难点和热点。自1984年CHRYSSOLOURIS等[4]首次提出将工艺规划与车间调度进行集成优化之后，涌现出了大量关于IPPS问题的研究[5-6]。在这些研究中，基于元启发式算法求解IPPS问题是近年来的研究热点，如遗传算法(genetic algorithm,GA)[7-9]、蚁群算法(ant colony optimization，ACO)[10-14]、帝国竞争算法(imperialist competitive algorithm,ICA)[15]、蜂群算法[3,16-17]等。由于IPPS问题求解困难，越来越多的学者将不同的算法进行优势互补，设计有效的混合算法[18-26]对IPPS问题进行求解。本文从工艺规划与车间调度两阶段优化目标冲突的角度出发，结合不同元启发式算法的优点，设计了一种两阶段混合算法对IPPS问题进行求解，并采用IPPS问题基准测试集对提出的算法进行验证。

1 IPPS问题描述

本文研究的IPPS问题可以被描述为：某加工任务共包含n个待加工工件，车间可供使用的机床共有m台。每一个待加工工件具有多道加工特征，不同的加工特征之间存在一定的先后顺序约束关系。每一道加工特征具有可选的加工工艺，不同的可选加工工艺包含的具体工序数目可能有所不同。每一道工序可以选择在若干台不同的加工机器上进行加工。IPPS需要解决如下三个问题：首先，确定每个工件的工序加工顺序；然后，为每一道工序挑选合适的加工机器；最后，根据确定的工序加工顺序以及工序加工机器，确定每一道工序的开工时间和完工时间，从而使得整个系统的某项性能指标最优。本文中，评价整个系统的性能指标为最小化工件最大完工时间(makespan)。

本文研究的IPPS问题中，生产调度的方式为作业车间调度问题(job shop scheduling problem,JSP)，并建立在如下假设条件下[3]：①在零时刻，所有的机器都可以被安排加工任务;②加工工序所需要的准备时间包含在每道工序的加工时间中;③不同工件具有相同的优先级，每台机器在同一时刻只能加工一个工件;④机器一旦开始加工一道工序，在该道工序加工完成之前，操作不允许被打断;⑤每个工件在同一时刻只能安排一道工序的加工任务;⑥不同工件的工序之间不存在加工顺序的约束关系;⑦暂不考虑工件在机器之间的传输时间。

表1 3个工件在5台机器上加工的IPPS问题

为了更具体地描述本文所研究的IPPS问题，接下来针对一项具体的加工任务对该问题进行详细描述。表1为3个工件在5台机器上加工的IPPS问题输入信息表。如表1所示，工件1具有6个加工特征，其中加工特征1必须在其他5个加工特征之前进行加工，加工特征4必须在加工特征6之前进行加工。加工特征1和加工特征4分别具有两种可选的加工工艺。加工特征1的第一种可选加工工艺只需要一道工序(O1)即可完成加工，第二种可选加工工艺则需要两道工序(O2—O3)才可以完成加工。每一道工序具有可选加工机器，如O1具有3台可选加工机器(M1,M2,M3)，决策者可根据不同的需求选择其中一台机器完成对该道工序的加工任务。从表1中可以明显看出，每一个工件具有许多可选的工艺路线，在求解IPPS问题时，首先需要确定每一个工件的工艺路线，然后依据确定的工艺路线，合理安排每道工序的开工时间，从而使得最大完工时间最小化。

2 基于两阶段混合算法的IPPS问题求解方法

2.1 算法总流程图

针对IPPS问题中存在的复杂机器柔性、工序顺序柔性和加工路径柔性，本文采取一种“分而治之，协同优化”的思路，设计了基于两阶段混合算法的IPPS问题求解方法：在工艺规划阶段，采用遗传算法为每一个工件生成近优的可选工艺路线集，动态地为作业车间调度阶段输入不同的工艺路线；在作业车间调度阶段，使用蜜蜂交配优化(honey bees mating optimization,HBMO)算法优化求解，获得最优调度方案。具体流程见图1。

图1 两阶段混合算法求解IPPS总流程Fig.1 Workflow of two-stage hybrid algorithm for IPPS

2.2 工艺规划阶段主要操作

本文中工艺规划阶段的目的并不是使用遗传算法为每个工件求得一条最优的工艺路线，而是为作业车间调度阶段提供尽可能多的近优工艺路线。采取的方法是，使用遗传算法对每个工件的工艺路线种群进行优化，获得每个工件的近优工艺路线集，然后随机从每个工件的近优工艺路线集当中挑选一条工艺路线输入作业车间调度阶段。以下详述使用遗传算法对工艺规划阶段进行优化的主要操作。

2.2.1编码与解码

遗传算法种群中每一条染色体代表零件的一条具体的工艺路线，本文采用文献[3]中的编码方法对染色体进行编码操作。每条染色体包含3段长度不同的序列。第一段为特征顺序序列，第二段为可选工艺序列，这两段序列的长度均等于工件的总特征数。第三段为可选机器序列，该序列的长度等于工件的总工序数。以表1中的工件1为例，一种可行的编码方案见图2。因为工件1一共包含6个加工特征，图2中特征顺序序列和可选工艺序列长度均为6。特征顺序序列代表的含义为该零件按照特征F1—F4—F6—F3—F2—F5的顺序进行加工。可选工艺序列的第i个位置的数字k，代表了工件的特征Fi选择第k种可选加工工艺进行加工，如图2中可选工艺序列中第一个位置为1，则代表特征1从它的可选工艺集{O1，O2—O3}中选择第1种加工工艺，即O1进行加工。可选机器序列代表的第i个位置的数字k，代表了零件的工序Oi从可选加工机器集当中选择第k个加工机器，如图2中可选机器序列第4个位置为3，则代表工序4从它的可选加工机器集{M2,M3,M4}中选择了第三台机器，即机器M4进行加工。

图2 工艺规划阶段染色体编码方案Fig.2 Chromosome encoding scheme in process planning stage

该编码方案在解码时比较简单，首先，特征顺序序列直接代表的就是特征的加工顺序，只需要直接从可选工艺序列中依次确定相应特征的加工工艺即可。图2所示的编码方案代表工件1工序的加工工序为O1—O8—O10—O5—O4—O9。然后，依据可选机器序列，依次确定选中工序的加工机器，即图2所示的编码方案所确定工件1的工艺路线为O1(M2)—O8(M5)—O10(M4)—O5(M1)—O4(M4)—O9(M5)。

2.2.2种群初始化

遗传算法种群中的每一条染色体代表工件的一条工艺路线。按照编码操作，每条染色体包含三段序列，均采用随机初始化的方法进行初始化操作。对特征顺序序列进行初始化时，首先随机生成零件加工特征的一种全排列序列，然后使用文献[23]中的约束调整方法对特征顺序序列进行调整，将不可行序列转换为可行序列。对可选工艺序列进行初始化时，如果零件第i个特征的可选工艺有k种，则随机生成1至k中的一个整数，存入可选工艺序列的第i个位置。对可选机器序列进行初始化时，如果零件第i道工序的可选机器有k台，则随机生成1至k中的一个整数，存入可选机器序列的第i个位置。这种初始化方法能够保证生成的可选工艺序列和可选机器序列均为可行的。

每条染色体按照上述方法进行编码操作之后，使用解码操作对其进行解码，获得具体该条染色体所对应的工艺路线，根据确定的工艺路线，计算该工艺路线下零件的加工时间，将加工时间作为染色体进化过程中的适应度值。

2.2.3遗传操作

遗传操作主要包括选择、交叉和变异操作。本文中采用的选择操作为最好个体保留和轮盘赌的选择操作。因为工艺规划的目的是为车间调度阶段提供近优的工艺路线，所以希望可以尽可能保留种群中比较好的个体。在进化过程中，生成新种群时，直接保存父代种群中最好的前PcopyPPsize(Pcopy为复制概率，PPsize为工艺规划阶段种群规模)个个体到子代种群中。在生成新种群挑选进行交叉的父代时，采用轮盘赌的选择操作从种群中选择父代个体，使得适应度值较好的个体能够以更大的概率参与生成新种群，从而保存种群中的优良基因。本文中工艺规划部分的编码操作采用了三段式编码操作，采用文献[3]中的操作分别对三段染色体进行交叉和变异操作。

2.3 作业车间调度阶段主要操作

作业车间调度阶段的目的是根据每个工件确定的工艺路线生成最终的可行调度方案，从而使得加工完成所有工件需要用的时间最短。本文在该阶段采用能够兼顾全局搜索和局部搜索的HBMO算法对作业车间调度阶段进行优化求解，下面详细描述算法的主要操作。

2.3.1编码、解码与初始化

本阶段采用基于工序的编码方法[3]对作业车间调度阶段种群中的个体进行编码。以表1中的问题为例，若在工艺规划阶段为车间调度阶段输入的工艺路线中，工件1包含6道工序，工件2包含5道工序，工件3包含4道工序，则一种可行的编码串为[3 1 1 1 3 2 2 3 1 3 1 1 2 2 2]，编码串的总长度为所有工件包含工序的总数，即15，编码串中1出现了6次，依次代表工件1的6道工序。采用文献[23]中的贪婪解码方法将编码方案解码为活动调度类型，依据解码获得的甘特图，计算出最大完工时间，将最大完工时间直接作为该编码串所对应的适应度值。采用上述编码、解码和适应度值计算的方法随机生成初始种群。

2.3.2蜂王婚飞阶段

HBMO算法的蜂王婚飞阶段主要能够保证算法的全局搜索能力。主要操作步骤如下[3]。

(1)从当前种群中挑选适应度值最好的个体作为蜂王，其他个体作为雄蜂。

(2)设定蜂王受精囊容量Ssize，蜂王受精囊中雄蜂基因型的个数Snum，幼蜂种群规模Bsize，蜂王速度和能量的衰减系数α(本文中设定为0.9)，蜂王婚飞时的能量阈值T，初始化蜂王的速度值S(t)和能量值E(t)，令t=0,Snum=0。

(4)使用衰减系数对蜂王的速度和能量进行更新，令t←t+1。

(5)如果蜂王的能量E(t)>T且Snum

(6)从蜂王的受精囊中随机挑选一个雄蜂的基因型，对蜂王和选择的基因型使用文献[27]中设计的交叉操作生成幼蜂，直到生成Bsize个幼蜂为止。

2.3.3工蜂培育幼蜂阶段

HBMO算法中的工蜂培育幼蜂阶段保证了算法的局部搜索能力。本文参考文献[28]中对JSP问题不同邻域结构寻优性能的评估，挑选了以下3种效果比较好的邻域结构作为工蜂培育幼蜂的局部搜索策略。

(1)N1为随机插入邻域。随机挑选幼蜂的2个不同位置的不同基因型，将其进行互换。

(2)N2为随机全邻域。随机选择幼蜂的3个不同位置的不同基因型，对其进行全排列生成5个新的个体，挑选其中最好的1个个体，取代原来的幼蜂。

(3)N3为N5邻域。对于关键路径上的关键块，首块只交换最后2个加工工序，相应的尾块只交换前2个加工工序，所有的中间块分别交换头2个加工工序和最后2个加工工序。

对于蜂王婚飞后生成的每个幼蜂，随机选择上述3种邻域结构中的1种对其进行改进，如果新生成的幼蜂适应度值更好，则取代以前的幼蜂，直到达到工蜂培育幼蜂的最大迭代次数。

2.4 两阶段混合算法求解IPPS问题的具体步骤

基于上述算法关键操作的描述，本文提出的两阶段混合算法求解IPPS问题的具体步骤如下。

(1)算法参数设定。工艺规划部分参数如下：算法最大迭代次数PPgen，种群规模PPsize，交叉概率Pcros，变异概率Pmuta，复制概率Pcopy。作业车间调度参数如下：蜂王的最大婚飞次数NMF，蜂王速度和能量的衰减系数α，蜂王婚飞时的能量阈值T，蜂群数目JPsize，蜂王受精囊的容量Ssize，幼蜂数目Bsize，工蜂数目Wsize，工蜂培育幼蜂迭代次数Inum。另外还需要设定两阶段混合算法整体最大迭代次数GIPPS。

(2)根据待求解IPPS问题的输入信息(表1所示即为IPPS问题的输入信息表)，采用2.2.2节描述的方法随机初始化n个工件的柔性工艺路线种群，作为每个工件的当前可选工艺路线集。

(3)设置算法终止准则为达到算法最大迭代次数PPgen，使用2.2.3节描述的遗传算法的操作(复制、选择、交叉、变异)，对n个工件的柔性工艺路线种群进行优化，更新每个工件的可选工艺路线集。

(4)根据每个工件当前的可选工艺路线集，随机从中选择一条可选工艺路线输入到作业车间调度阶段。依据每个工件确定的工艺路线，采用2.3.1节的操作，随机生成作业车间调度阶段的初始化种群。挑选种群中最好的个体作为蜂王，其他个体作为雄蜂。

(5)判断蜂王是否达到最大婚飞次数，如果蜂王已经达到了最大婚飞次数，则跳转到步骤(8)。如果没有达到，则采用2.3.2节的操作完成蜂王婚飞阶段，生成幼蜂种群。

(6)采用2.3.3节的操作完成工蜂对幼蜂的培育，使用新生成的幼蜂种群对蜂王和雄蜂进行更新。将幼蜂种群中的个体与蜂王进行对比，如果幼蜂的适应度值优于蜂王，则取代蜂王。如果幼蜂的适应度值优于已有雄蜂种群中的个体，则取代相应的雄蜂。

(7)更新蜂王的婚飞次数，跳转到步骤(5)。

(8)保存进化过程中生成的最优解(即蜂王对应的工艺路线方案及调度方案)。更新IPPS算法迭代次数，如果达到了最大迭代次数，则算法终止。如果没有达到最大迭代次数，则跳转到步骤(4)。

3 计算结果与分析

3.1 基准测试集计算结果

表2 两阶段混合算法求解IPPS主要参数

由于单个工件工艺路线的最优与最终IPPS希望达到的最优并不是一种线性的关系，而是一种复杂的非线性关系，因此，第一阶段的目的并不是提供每个工件的最优工艺路线，而是希望找到每个工件较优的工艺路线输入到第二阶段的车间调度环节。本文算法设计的初衷是希望保持一种探索两阶段优化非线性关系的趋势，因为并非每个工件最优的工艺路线都能够保证IPPS找到最优解。所以，本文中工艺规划阶段的算法对每个工件使用一样的参数，且迭代次数较少，目的是为第二阶段提供多样化的工艺路线，以此保证种群的多样性，实现找寻IPPS全局最优解的目的。

测试集共包含15台加工机器，18个不同的工件，根据工件的不同组合构成了24个不同规模的测试问题，具体数据参考文献[23]的附录部分。该测试集中每个工件均采用网络图进行表示，包含复杂的机器柔性、工艺顺序柔性和加工路径柔性，IPPS问题的计算结果应该包含有每个工件的工艺路线及具体的调度方案。THA的计算结果(包含运算时间)与已有文献中其他算法的结果对比见表3。使用本文算法获得问题24的最优解为511，该解所对应的每个工件具体的工艺路线见表4，该解所对应的甘特图见图3。甘特图方框中的数字(i,j)代表着第i个工件在确定的工艺路线中的第j道工序。如(18,1)代表的是工件18工艺路线中的第1道工序，通过查询表4可以获得该工序具体的工序号O7。

表3 THA计算结果及与其他算法的对比

表4 问题24最优解对应的18个工件的工艺路线

(续表)

工件工序数工艺路线413O1(M2)—O2(M12)—O3(M9)—O4(M5)—O13(M6)—O14(M10)—O7(M10)—O8(M6)—O9(M3)—O16(M7)—O10(M9)—O11(M7)—O12(M15)510O14(M8)—O1(M4)—O15(M5)—O10(M4)—O11(M14)—O12(M6)—O13(M14)—O16(M13)—O17(M3)—O18(M7)616O5(M6)—O1(M4)—O15(M14)—O17(M12)—O16(M5)—O2(M6)—O18(M10)—O6(M10)—O7(M9)—O10(M8)—O9(M11)—O14(M7)—O3(M5)—O19(M12)—O4(M5)—O20(M9)712O1(M7)—O7(M3)—O8(M5)—O9(M6)—O10(M12)—O11(M2)—O19(M2)—O20(M6)—O12(M1)—O13(M9)—O18(M13)—O21(M10)812O17(M10)—O1(M4)—O18(M7)—O20(M3)—O2(M15)—O3(M12)—O4(M4)—O5(M2)—O7(M3)—O8(M6)—O10(M5)—O11(M1)916O1(M12)—O2(M7)—O13(M2)—O16(M4)—O18(M2)—O19(M2)—O7(M13)—O14(M15)—O4(M3)—O5(M6)—O10(M14)—O6(M6)—O11(M15)—O12(M6)—O20(M4)—O15(M5)109O1(M4)—O3(M1)—O4(M13)—O5(M7)—O6(M5)—O9(M9)—O10(M3)—O2(M15)—O11(M14)119O1(M6)—O2(M14)—O3(M13)—O6(M10)—O8(M2)—O7(M1)—O4(M5)—O5(M6)—O9(M9)1216O8(M3)—O1(M11)—O13(M3)—O5(M15)—O2(M15)—O3(M5)—O6(M2)—O4(M12)—O14(M1)—O15(M9)—O9(M6)—O10(M4)—O11(M7)—O12(M10)—O18(M13)—O7(M11)138O17(M8)—O1(M11)—O12(M6)—O13(M10)—O14(M6)—O15(M4)—O16(M14)—O18(M2)1410O9(M12)—O12(M14)—O1(M9)—O10(M15)—O4(M3)—O5(M4)—O6(M4)—O8(M3)—O11(M4)—O13(M10)1513O7(M9)—O12(M7)—O1(M11)—O8(M8)—O9(M2)—O13(M1)—O3(M6)—O4(M7)—O5(M2)—O14(M9)—O6(M5)—O15(M1)—O11(M8)1613O18(M11)—O1(M11)—O20(M14)—O21(M14)—O6(M6)—O7(M5)—O8(M5)—O9(M10)—O10(M11)—O11(M8)—O15(M4)—O16(M9)—O17(M13)1714O18(M2)—O1(M11)—O13(M6)—O19(M1)—O20(M9)—O14(M3)—O2(M10)—O3(M4)—O4(M12)—O5(M7)—O7(M11)—O12(M8)—O22(M11)—O17(M2)1812O7(M3)—O8(M13)—O1(M3)—O4(M1)—O5(M9)—O12(M5)—O13(M9)—O10(M11)—O6(M5)—O16(M4)—O17(M10)—O11(M10)

图3 问题24最优解对应的甘特图Fig.3 Corresponding Gant chart for optimal solution of problem 24

3.2 结果分析

由表3可以看出，与已有文献中的6种不同的算法比较，本文提出的算法在19个问题上取得了更好(或相同)的结果。当问题规模变大时(问题22、23和24)，使用本文提出的算法获得的计算结果明显优于其他6个算法。这是因为本文提出的算法采取了“分而治之”的思想分别处理IPPS中的不同柔性问题，当工件数变多时，这种设计思路能够有效地提高寻优效率。有4个问题(问题13、14、18、21)的计算结果劣于已有文献中GATS算法的计算结果，优于其他对比算法。问题8的计算结果相对较差。这是因为，工艺规划阶段为车间调度动态输入工艺路线时存在一定的随机性，算法在运行时可能会受到已定工艺路线的限制，在下一步的研究工作中，可以考虑采用一些启发式规则，对工艺规划阶段为车间调度阶段输入工艺路线的过程进行一定的指导。

总体来说，通过基准测试集的测试，证明了本文提出的THA算法在求解IPPS问题时的有效性。本文提出的IPPS优化方法在工艺规划部分采用遗传算法为每个零件生成近优的可选工艺路线库，在这一阶段对IPPS问题存在的3种柔性进行了一定程度的预处理，在车间调度阶段采用HBMO算法进行优化，能够保证车间调度阶段的全局搜索和局部搜索。

究其本质，工艺规划的优化目标和车间调度优化目标之间存在非常复杂的非线性关系。在一定程度上，单个零件的加工时间越短，整体加工任务的完工时间相对较少。但是，如果大量零件被集中安排在瓶颈机器上进行加工，则必然会导致整体加工任务的延迟完工。本文提出的方法能够在一定程度上解决工艺规划和车间调度优化目标之间的矛盾冲突，从而实现了IPPS问题的整体优化求解。

4 结语

本文针对制造系统运行优化中亟需解决的IPPS问题进行了研究。针对IPPS问题中存在的机器柔性、工序顺序柔性和加工路径柔性，提出了一种两阶段混合算法进行求解。这一算法实现了IPPS问题的整体优化求解。

在今后的研究中，可以从问题建模和算法设计两个方面对IPPS问题进行更深入的研究。在问题建模方面，可以考虑如何处理实际生产环境中的动态不确定事件，研究动态事件的描述方法，设计动态不确定性评估指标，构建有效的动态不确定环境下IPPS问题建模方法；在算法设计方面，探讨更加科学的工艺规划和车间调度两阶段信息交互方式，进一步提高集成效率，使得研究成果能够更好地指导实际生产。另外，还可尝试从绿色制造角度开展绿色IPPS问题的研究。