基于改进遗传算法的PCB多级组装线调度*

黄 毅，胡 悦，杨宏兵

(苏州大学机电工程学院，苏州 215137)

0 引言

随着信息时代的到来，电子产品得到了极大的发展，而印制电路板PCB(printed circuit board)是电子产品的重要部件之一。随着PCB板广泛应用于手机、计算机、智能手表等电子设备，近些年来PCB板的需求得到了极大的提升，因此如何提高PCB组装线的生产效率成为了制造企业的重要问题。

PCB组装线调度问题是SMT(surface mounted technology)生产线调度问题的扩展，PCB组装线中往往包含了多条SMT生产线，对于PCB组装线调度问题国内外学者已进行了大量的研究。SAWIK等[1]详述了SMT车间各类流水线的基本运作方式并提出了相应的混合整数规划模型。HE等[2]提出了一种确定性的多层启发式方法减少了SMT生产线的加工时间。KOSKINEN等[3]考虑了PCB 组装作业分配到生产线、机器负载平衡以及作业调度的联合任务。黄夏宝等[4]将整个PCB组装过程分为订单批量分批和子批排程两个阶段，并设计了一种模拟遗传算法进行求解。杜轩等[5]基于多色集合理论，建立了PCB组装工艺规划和调度集成优化约束模型。杨霁轩[6]根据印制电路板生产的特点，基于流水车间和柔性流水车间环境，分别设计了两种启发式算法。李小龙等[7]考虑了PCB装配调度中单生产线多板型情况，并将其转化为带顺序相关切换时间的单机延期模型。郭姝娟等[8]对由多台贴片机组成的SMT生产线负荷均衡问题进行了建模，并采用了遗传算法进行求解，通过实际现场的模拟验证了模型及算法的有效性。

综上所述,以往的PCB组装线调度问题往往将该问题视为流水线式车间调度问题，每个订单仅由单一的物料组成，但在实际生产过程中，每个订单往往由多个物料组成并进行加工，是多级零件制造组成的更加复杂的装配过程。因此本文考虑了具有物料BOM表结构的PCB多级组装线调度问题，建立了混合整数规划模型，提出了一种改进的遗传算法求解该模型，在编码和解码环节采用了3层编码机制以及主动解码策略，增大了解空间并改善了解质量，对3层编码进行多级交叉变换，并采用了独立于种群的精英解保留策略，最后通过多个算例验证了其有效性。

1 问题描述与数学建模

PCB组装通常包含多个加工阶段，主要分为前段加工和后段加工，前段加工通常为SMT段加工，一般包括了A面加工和B面加工。后段加工一般分为测试、分板、焊接、涂覆和组装5个工艺段。其中测试有ICT测试、FCT测试等；分板有VCUT分板、铣刀式分板等；焊接有波峰焊、选择焊、焊接机器人焊等；涂覆有涂覆机涂覆、低压注塑机涂覆等；组装有点胶机组装，人工组装等。本文主要列举了6种某企业PCB加工的物料BOM表结构，如图1～图6所示，图7为PCB物料BOM表结构3的具体加工路线。

图1 物料BOM表结构1 图2 物料BOM表结构2

图3 物料BOM表结构3 图4 物料BOM表结构4

图5 物料BOM表结构5 图6 物料BOM表结构6

图7 PCB物料加工路线

PCB组装线调度问题描述如下：生产车间有m个加工中心处理i个订单，每个订单的PCB产品由j个物料组成，每个物料包含k道工艺段，每道工艺段能在可允许的加工中心上进行加工，且在不同的加工中心上进行加工的时间是不同的。本文的调度目标是最小化最大完工时间，主要满足的约束条件是物料之间存在的先后加工顺序以及物料各道工序的先后加工顺序。定义如下数学符号用于问题描述：

(3)目标函数及约束条件：

minz=max{Fi,i=1,2,…,I}

(1)

(2)

Fi,j=Fi,j,ONij,∀Ji,j

(3)

Fj=Fi,Gi,∀i

(4)

Ri,j,k≥Fi,j,k-1,∀Oi,j,k

(5)

Ri,j,1≥Fi,lJi,l,j,∀(Ji,j,Ji,l)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

式中，式(1)表示本文所求的目标函数即最小化最大完工时间；式(2)表示工艺段的完工时间；式(3)表示订单中物料的完工时间；式(4)表示订单的完工时间；式(5)表示工艺段的时间约束；式(6)表示订单中物料的时间约束；式(7)表示工艺段只能在可允许的加工中心上进行加工；式(8)表示某时刻同一个工艺段只能选择在一个加工中心上进行加工；式(9)和式(10)表示在同一个加工中心上每道工艺段只能有一道紧前工艺段和一道紧后工艺段；式(11)和式(12)表示任一加工中心同一时刻最多只能完成一道工艺段的加工。

2 改进的遗传算法

图8 遗传算法步骤图

遗传算法在求解车间调度问题时具有良好的全局搜索能力，收敛性快等特点，但局部搜索能力弱，容易产生早熟收敛的问题。文献[9-11]均对遗传算法进行了一些深入的研究与改进，本文为了提高传统遗传算法的效率，避免最优解的丢失，也提出了一些改进措施，采用了多种交叉方式，主动解码策略以及精英解保留策略。图8为遗传算法的基本流程。

2.1 编码

针对具有物料BOM表结构的多级PCB组装线调度问题，将该问题分为3个子问题，即订单之间的加工顺序排序，物料的工艺段加工顺序排序以及工艺段选择加工中心，故采用3层编码形式，第1层为订单层，以确定订单加工顺序；第2层为工艺段层，以确定物料工艺段加工顺序；第3层为加工中心层，以确定各工艺段选择的加工中心。图9为3层编码示意图，该图以物料BOM表结构1和结构2构成了订单1和订单2。ORS编码为第1层编码，假设该编码串为[1 1 2 2 1 2 2 1 1 1 2 2 1 1]，编码串上的每个基因都与相应订单号的OPS编码相对应，ORS编码串上的第1个1与OPS编码串上的订单1的第1个0相对应，代表了订单1的物料0的第1道工艺段，同理第2个1与OPS编码串上的订单1的第1个1相对应，代表了订单1的物料1的第1道工艺段，以此类推，每个工艺段的具体加工顺序详见图9。MS编码为第3层编码，MS编码串上的每个基因按照每个订单的初始工艺段加工顺序来进行加工中心的选择，MS编码串上订单1的第1个2表示订单1的物料0的第1道工艺段选择加工中心2进行加工，同理MS编码串上的订单1的第1个3表示订单1的物料0的第2道工艺段选择加工中心3进行加工，以此类推，每个工艺段的加工中心的选择如图9所示。

图9 3层编码示意图

2.2 解码

为了在解码过程中产生更好的解，本文采用一种主动调度策略以尽可能地缩短工艺段间的等待时间和最大完工时间，具体的主动调度策略方案如下：

(1)如果Oi,j,k在加工中心m上是第1道工艺段，同时Oi,j,k也是订单i的第1道工艺段时，那么Ri,j,k=0；

(3)如果Oi,j,k在加工中心m上是第1道工艺段，但是Oi,j,k根据工艺段加工顺序约束不能作为订单的第1道工艺段并且Oi,j,k是某个物料的非首道工艺段，那么Ri,j,k=Fi,j,k-1；

(4)如果Oi,j,k在加工中心m上是第1道工艺段，但是不能作为订单的第1道工艺段并且Oi,j,k是受物料加工先后顺序约束的某道工艺段时，那么对于所有的受Oi,j,k约束工艺段集合{Fi,j1,k,Fi,j2,k,…,Fi,jm,k}，Ri,j,k=max{Fi,j1,k,Fi,j2,k,…,Fi,jm,k}；

2.3 种群初始化

种群初始化方法对算法的求解速度和求解质量都有一定的影响，如果完全采用随机方法生成初始解，那么将大大增加计算时间，本文采用随机选择和调度规则相结合的方法来生成初始解，产生初始种群方法如下：

ORS初始解：随机生成；

OPS初始解：随机生成，针对OPS编码随机生成会产生不满足物料先后加工顺序的问题，采用二叉树中序遍历机制来对OPS初始解进行修复；

MS初始解：①随机生成：种群数量占40%；②按加工时间最短优先(shortest process time，SPT)调度规则半随机生成：种群数量占60%，产生0～1之间的随机数，如果该值小于0.8，该工艺段选择加工时间最短的加工中心加工，否则该工艺段随机选择加工中心进行加工。

2.4 遗传算子

在选择算子方面，采用轮盘赌选择策略，各个个体被选择中的概率与其适应度大小成正比，并且为了防止当前群体的最优解在下一代发生丢失，采用精英解保留策略，把每一代的最优解不进行选择、交叉、变异操作直接保留至下一代，替换下一代中适应度值最低的解。

在交叉算子方面，针对三段式编码采用多级交叉方式，对每一段编码都进行交叉操作以尽可能地扩大解空间。对ORS编码采用传统的POX交叉方式[12]，如图10所示，将所有订单随机分成两段非空子集G1,G2，将父代1和父代2中含有G1和G2订单号的工艺段基因分别按原编码位置保留至子代1和子代2中，然后将父代2中含有G2订单号的工艺段基因按顺序依次填入子代1中空白位置处，将父代1中含有G1订单号的工艺段基因按顺序依次填入子代2中空白位置处。同理对于OPS编码也采用POX交叉方式，针对交叉后可能产生的不满足物料先后加工顺序的问题，采用二叉树中序遍历机制进行修复。对于MS编码采用多点交叉方式，如图11所示，随机选择若干个基因位置，父代1和父代2被选基因位的基因按照对应关系互相交换，其余基因位的基因保持不变从而得到子代1和子代2。

图10 POX交叉示意图 图11 MS编码多点 交叉示意图

在变异算子方面，对ORS编码和MS编码实现变异操作，针对ORS编码采用两点互换式变异方法，即随机选择两个基因点位，互换两点基因实现变异。针对MS编码采用定点变异方法，即随机生成2个基因位置，从这两个基因位的可选加工中心中随机选择一个不同的加工中心，替换原基因实现变异。

3 实验分析

为了验证采用改进的遗传算法求解PCB组装线调度问题的有效性，本文采用OR-tools求解器进行比较，由于没有标准算例可供测试，故以某PCB生产企业的实际生产为背景，生成10组规模大小不一的测试集来进行验证，测试集规模从10×20～80×30不等，其中10×20表示10个订单在20台加工中心上进行加工的调度问题算例，表1为某个订单的工艺段的部分可选加工中心的加工时间示例。

表1 工艺段加工时间表

图12 算法比较折线图

本文改进的遗传算法使用python编程实现，程序在Windows10系统，CPU为i7-9750H的个人电脑上运行，对于验证的10个案列，算法参数设置如下：种群数量为50，交叉概率为0.8，变异概率为0.05，最大迭代次数为200次。将算法运行10次取平均值与Google公司的OR-tools工具求解的结果进行比较，由于随着测试集规模的增大，OR-tools计算时间逐渐增加，当算例规模在40×20以上时，OR-tools计算时间已远超本文所提算法，故当算例规模在40×20以上时，OR-tools结果以本文所提算法的计算时间×1.2显示，即在基本相同的计算资源下比较两者的结果，具体结果见如表2和图12所示。采用相对偏差来表示两者之间的差距，表达式如下：

(13)

表2 算法比较结果

图13为本文算法得出的10×20算例的甘特图。 横坐标为加工时间，纵坐标为加工中心号，图中以短横线连接的3个数字分别代表订单编号、物料编号、工艺段编号，以7-3-1为例，代表订单7的物料3的第1道工艺段。

图13 10×20甘特图

4 结论

本文针对具有物料BOM表结构的PCB组装线调度问题，以最小化最大完工时间为目标构建了混合整数规划模型，并提出了改进的遗传算法求解该模型。该算法采用了3层编码机制以及主动调度策略，减少了最大完工时间以及工艺段之间的等待时间，种群初始化采用了随机选择和调度规则相结合的方法提升了初始解的质量，减少了算法收敛时间，选择操作采用了精英解保留策略避免了群体最优解的丢失，交叉操作采用了多级交叉算子，提高了算法的全局搜索能力。最后通过实验证明，在相同的计算资源下所提出的算法在大规模问题上的求解质量优于OR-tools求解器求解。