PCB板组装工艺中多机流水生产线贴片机负荷均衡优化方法

摘要

本发明公开了一种PCB板组装工艺中多机流水生产线贴片机负荷均衡优化方法，首先描述和分析PCB板组装生产线的优化问题，再根据优化问题的描述和分析建立其负荷均衡的数学模型，再针对数学模型的求解特点设计算法获得各贴片机负荷均衡的元器件贴装顺序，最后应用于生产线控制系统，对生产线各贴片机按最优调度方式进行元器件贴装，所述算法采用布谷鸟搜索算法和粒子群算法结合的智能优化算法。本发明采用改进布谷鸟搜索算法求解生产线上各贴片机负荷均衡的优化调度数学模型，获得全局最优的元器件贴装调度方案,从而使各台贴片机的负荷达到均衡，提高生产线的效率。

说明书

技术领域

本发明涉及一种用于PCB板(印刷电路板)组装生产线的智能调度优化方法,属于生产系统智能优化调度与控制技术领域。

背景技术

表面组装生产过程作为我国电子信息制造业的关键工序，国际上在该方面的核心研究成果也很少公开，国内对其中的关键共性理论问题和实现技术的探索才刚刚起步，这些都成为制约我国电子信息产业赶超国际先进制造水平的瓶颈。

印刷电路板(PCB板)组装是表面组装生产线的核心工艺过程，是将电子元件组装在印刷电路板上，从而实现电子元器件的互联，其用的关键设备是贴片机。电子制造技术在电子信息产业中的地位越来越重要，而印刷电路板组装又是电子信息产业的基础工业，也是其支柱产业。

印刷电路组装生产线必须适应多用户、多任务、多品种的生产要求，以最低的成本和最小的废品率在最短的时间内获得最大的产出。满足这一问题的有效途径是全过程最优控制。

贴片机是表面组装生产线中最关键的设备，其工作效率的高低会制约着整条生产线生产能力的发挥。因此，为了更好地满足电子装备制造过程中的多品种、变批量、短周期、低成本、高质量的要求，研究表面组装生产线及其“瓶颈”设备——贴片机优化运行的理论和实际应用问题，寻求提高生产线和设备生产效率的有效方法，分析生产线上各贴片机负荷均衡优化问题，成为近年来国内外相关学者研究的热点之一。同时，这些问题的研究和实践,，将不仅推动国产表面组装技术的革新和升级，还能有效提高现有表面组装过程中贴片设备的优化管理与控制水平，解决传统生产线上存在的生产调度优化问题,并将产生重大、直接的经济效益和社会效益。

表面组装生产线调度问题是车间调度问题和并行机调度问题的综合与推广，是强NP-hard问题，其特征是某些难解性以及多目标性更能反映实际生产过程，其理论和方法具有更高的应用价值。国内外许多学者曾用蚁群算法(ACO)、遗传算法(GA)、禁忌搜索算法(TS)、粒子群算法(PSO)等求解流水作业车间调度问题，取得了很好的效果。目前国内对多机流水生产线负荷均衡优化算法的研究相对较少，遗传算法具有大范围的全局搜索能力，但对反馈信息利用不足，当解到一定程度时往往做大量无用的冗余迭代；蚁群算法具有反馈机制但收敛速度慢；PSO算法收敛速度快，但不能保证得到最优解,布谷鸟搜索算法是近几年提出的一种新型的智能算法,具有参数设置少、收敛速度快、全局寻优能力强等优点；但是该算法存在局部寻优能力不强、搜索速度较慢的缺点。

发明内容

本发明的目的在于针对现有技术的不足，提供了一种基于改进布谷鸟算法的表面组装生产线贴片机负荷均衡优化的调度优化方法，解决PCB板组装生产线元器件贴装路径规划的优化问题,获取负荷均衡优化的元器件贴装调度方案,为各台贴片机确定一种最佳的生产负荷方案；使得各贴片机的加工时间相等且最小，从而使各台贴片机的负荷达到均衡，提高生产线的效率。

本发明的目的通过以下技术方案来具体实现：

一种PCB板组装工艺中多机流水生产线贴片机负荷均衡优化方法，首先描述和分析PCB板组装生产线的优化问题，再根据优化问题的描述和分析建立其负荷均衡的数学模型，再针对数学模型的求解特点设计算法获得各贴片机负荷均衡的元器件贴装顺序，最后应用于生产线控制系统，对生产线各贴片机按最优调度方式进行元器件贴装，所述算法采用布谷鸟搜索算法和粒子群算法结合的智能优化算法。

作为优选方案，上述的PCB板组装工艺中多机流水生产线贴片机负荷均衡优化方法，其特征在于：包括如下步骤：

1)数学模型的建立

从PCB板组装的多机流水生产线的实际出发，描述PCB板的多机流水生产线负荷均衡问题，再根据问题的描述建立带约束条件的生产线各贴片机负荷均衡的优化调度数学模型；

2)求解

根据步骤1)中的建立的PCB板的多机流水生产线元器件贴装调度的数学模型,采用将布谷鸟搜索算法和粒子群算法相结合的优化方法对其进行求解，以求得使各个贴片机的加工时间相等且达到最小的最优解；

3)控制贴装

对步骤2)得到的元器件贴装调度最优解分别提供给生产线贴装控制子系统和智能送料分配子系统，使整个生产线的每台贴片机按最优调度方式进行元器件贴装化。

优选的，所述步骤1)中，所述数学模型的建立方法如下：

a.先针对该流水线生产的实际特征，对PCB板的多机流水生产线负荷均衡问题进行描述，描述方法如下：

设PCB板上有c种元件将在m台贴片机上加工，为了便于描述和解析问题，所有贴片机及PCB板的元件类型分别用数学编号表示如下：

贴片机集合为：M＝{1,2,…,m}；PCB板的类型集合为：C＝{1,2,…,c}；加工需求集合为：W＝{w₁,w₂,…,w_k,…,w_c}，其求w_k为类型为k(k<C)的PCB板的数量。设类型为k的PCB板在编号为i∈M的贴片机上加工或组装时间为t_ik，T_i为编号为i∈M的贴片机完成其所分配的任务所需的时间。引入如下0—1决策变量：

b.针对步骤a对于问题的描述，建立负荷均衡优化调度问题用数学模型，数学模型表示如下：

目标函数：

$>\min f=\underset{i\in M}{\min }\left({\mathrm{maxT}}_i\right)$>

其中，

$>T_i=\underset{k\in C}{\Sigma }{w}_k{t}_{ik}{x}_{ik}$>

约束条件：

i＝1，...，m；k＝1，...，C，表明任何一类元件只能分配给一个贴片机；

i＝1，...，m；k＝1，...，C，表明任何一台贴片机至少组装一类以上元件；

x_ik∈(0，1)，i＝1，...，m；k＝1，...，C，表明该变量为0-1变量约束。

优选的，所述步骤2)中，所述采用布谷鸟搜索算法和粒子群算法相结合的优化方法为：利用粒子群算法对布谷鸟算法中的位置进行不断的更新，具体的，使布谷鸟按照LevyFlight机制随机游走，又使其在后期按照粒子群算法更新路径，以提高了布谷鸟搜索算法在局部的寻优能力。

进一步优选的，所述步骤2)中，所述采用布谷鸟搜索算法和粒子群算法相结合的优化方法，具体包括如下步骤：

步骤a：初始化基本参数

布谷鸟选择的鸟窝数目N，发现概率P_a，最大种群粒子数h，学习因子c₁、c₂，最大迭代次数maxgeneration；

步骤b：布谷鸟随机选择鸟窝的位置

随机产生并择优选取n个序列，将X_i(i＝1,2,…,N)，作为初始鸟巢，基于最小位置值规则的随机键编码将鸟窝位置换为PCB板元器件帖装工序的排列，根据鸟窝的位置计算评价各鸟窝的调度目标值，初选得到目前最优鸟窝X_best，记录当前最优帖装排序和调度目标值，迭代次数置为1；

步骤c：分析各种位置解的优劣性，分别建立劣解种群集和优解种群集；

步骤d：对于优解种群，转步骤f；对于劣解种群，顺序执行；

步骤e：根据标准布谷鸟搜索算法中的更新方式一，具体如式Ⅰ，对鸟巢位置进行搜索并与原位置进行对比，择优选择进行位置更新鸟窝，同时更新对应的帖装排序和调度目标值，转步骤g，

式Ⅰ：$>X_i^{(t+1)}=X_i^{\left(t\right)}+\alpha \otimes L\left(\lambda \right)$>

其中，表示第t+1代第i个鸟窝的候选位置；表示第t代第i个鸟窝的位置；α为控制步长；为点对点乘法；L(λ)为服从Levy分布的随机搜索路径，转步骤g；

步骤f：根据粒子群算法，具体如式Ⅱ，对其他鸟巢位置进行搜索并与原位置进行对比，择优选择进行位置更新鸟窝，同时更新对应的帖装排序和调度目标值，

式Ⅱ：$>v_i^{(t+1)}=w\times v_i^{\left(t\right)}+c_1\times random\left(\right)\times (p_i-x_i^{\left(t\right)})+c_2\times random\left(\right)\times (g-x_i^{\left(t\right)})$>

$>x_i^{(t+1)}=x_i^{\left(t\right)}+v_i^{\left(t\right)}$>

其中，表示位置；表示速度；random()为[0,1]之间的随机数；c₁、c₂为学习因子，是非负常数；w为惯性系数；P_i表示个体最优粒子；g表示全局最优粒子；

步骤g：对每个更新鸟巢生成随机数random()，与发现外来鸟蛋的概率P_a进行比较，若random()＜Pa，则宿主放弃更新鸟巢并随机新建鸟巢，从而得到一组新的鸟巢，然后用新的鸟巢位置与更新鸟巢进行对比，若更好，则用其作为现有鸟巢，同时更新对应的帖装排序和调度目标值；

步骤h：评估全部鸟窝的目标调度值，若更新之后鸟窝目标调度值更优，则在更新后的鸟窝中产卵，并找出其对应的最优鸟窝位置，保留最优鸟窝，并更新对应的帖装排序和调度目标值，

步骤i：保留最优帖装工序排列和调度目标值，迭代次数增加1，若达到最大迭代次数，转步骤j，否则转步骤c，进行下一轮寻优；

步骤j：输出最优值和最后的生产调度方案。

本发明原理：

本发明步骤1)，针对PCB板的组装生产线是多贴片机同时工作的并行流水生产线(具体想详见图1和图2)的特点，假定各类PCB板在不同贴片机上的加工时间是已知的，以整体组装时间最小化为优化目标，旨在构造确定PCB板的组装顺序和加工任务分配方案的智能优化方法。从流水生产和连续批量生产的特点可知，加工时间最长的贴片机决定了整个加工工序的完成时间。如果能使流水线上各贴片机的加工时间相等且达到最小，则整个生产线就完成负荷均衡，可以获得最高的生产效率。故，建立带约束条件的生产线各贴片机负荷均衡的优化调度数学模型，以求得使各个贴片机的加工时间相等且达到最小的最优解。

本发明步骤2)采用改进布谷鸟搜索算法，先基于最小位置值规则的随机键编码方式实现布谷鸟选择宿主鸟巢的连续位置向量和各种PCB板的元器件帖装顺序之间的相互转换；再用粒子群算法(PSO)对布谷鸟搜索算法进行改进，使布谷鸟按照LevyFlight机制随机游走基础上，使其在后期按照PSO算法更新路径，这样既保持了布谷鸟搜索算法的全局寻优能力，又大幅提高了其在局部的寻优能力，从而达到对生产线负荷均衡的优化调度数学模型进行全局最优求解，获得负荷均衡最优的调度方案所对应的各种PCB板的全部元器件的帖装顺序。

本发明的有益效果：

本发明在现有技术中各算法的优缺点的基础上，为了使各种算法取长补短，提高算法寻优的效率，结合贴片机生产的实际，提出了将布谷鸟搜索算法和粒子群算法进行融合，并将其应用于解决PCB板组装的多机流水生产线负荷均衡优化问题的求解。本发明根据表面组装流水生产线的工作过程和特点，建立了生产线上各种PCB板的元器件帖装顺序优化调度数学模型，通过对各贴片机的优化调度，实现生产线上各贴片机的的帖装时间相等且最小，采用改进布谷鸟搜索算法求解生产线上各贴片机负荷均衡的优化调度数学模型，获得全局最优的元器件贴装调度方案,从而使各台贴片机的负荷达到均衡，提高生产线的效率。

附图说明

图1是本发明中PCB板组装生产线的流水线特征示意图；

图2是本发明中PCB板组装生产线的并行特征示意图；

图3是本发明中改进布谷鸟搜索算法的框图。

具体实施方式

实施例1：

如附图1，1为PCB板、21为元件1、22为元件2、23为元件3、、24为元件4、25为元件5、26为元件6、27为元件7、28为元件8、29为元件9，在本发明所述基于改进布谷鸟算法的表面组装生产线贴片机负荷均衡优化的调度优化方法中,该流水生产线的特点为：PCB板的分配是按类型进行的，同一类型的PCB板通常在一台贴片机上完成加工；每个部件的组装任务由生产线上所有贴片机共同完成，每台贴片机的加工任务完全不同；

如附图2，3为输送带，在本发明所述基于改进布谷鸟算法的表面组装生产线贴片机负荷均衡优化的调度优化方法中,该流水生产线的特点为：多台贴片机并行布置，各类PCB板被分配到不同的贴片机上完成加工组装，一台贴片机对某类PCB板(由若干元件构成)进行执行加工的同时，其它贴片机对其它部件也执行加工操作；

基于改进布谷鸟算法的表面组装生产线贴片机负荷均衡优化的调度优化方法，其具体过程如下：

步骤一：针对该流水线生产的实际特征，PCB板的多机流水生产线负荷均衡问题的描述如下：设PCB板上有c种元件将在m台贴片机上加工，为了便于描述和解析问题，所有贴片机及PCB板的元件类型分别用数学编号表示如下：

贴片机集合为：M＝{1,2,…,m}；PCB板的类型集合为：C＝{1,2,…,c}；加工需求集合为：W＝{w₁,w₂,…,w_k,…,w_c}，其求w_k为类型为k(k<C)的PCB板的数量。设类型为k的PCB板在编号为i∈M的贴片机上加工或组装时间为t_ik，T_i为编号为i∈M的贴片机完成其所分配的任务所需的时间。引入如下0—1决策变量：

步骤二：针对步骤一对于问题的描述，贴片机优化调度的思路是为各台贴片机确定一种最佳的生产负荷方案；使得各台贴片机的加工时间相等且最小，从而使生产线的效率最优，所以，负荷均衡优化调度问题用数学模型表示如下：

目标函数：

$>\min f=\underset{i\in M}{\min }\left({\mathrm{maxT}}_i\right)$>

其中，

$>T_i=\underset{k\in C}{\Sigma }{w}_k{t}_{ik}{x}_{ik}$>

约束条件：

i＝1，...，m；k＝1，...，C，表明任何一类元件只能分配给一个贴片机；

i＝1，...，m；k＝1，...，C，表明任何一台贴片机至少组装一类以上元件；

x_ik∈(0，1)，i＝1，...，m；k＝1，...，C，表明该变量为0-1变量约束；

步骤三：如附图3，根据步骤二中的建立的生产线元器件贴装调度的数学模型,采用将布谷鸟搜索算法和粒子群算法(PSO)进行结合的优化方法对其进行求解，对布谷鸟搜索算法进行改进，将PSO算法融入其中，一方面，使布谷鸟按照LevyFlight机制随机游走，又使其在后期按照PSO算法更新路径，这样既保持了布谷鸟搜索算法的全局寻优能力，又大幅提高了其在局部的寻优能力；所以，利用PSO算法对布谷鸟算法中的位置更新方式进行优化调整，是该优化方法的关键创新点；具体实现步骤如下:

步骤a：初始化基本参数

布谷鸟选择的鸟窝数目N，发现概率P_a，最大种群粒子数h，学习因子c₁、c₂，最大迭代次数maxgeneration；

步骤b：布谷鸟随机选择鸟窝的位置

随机产生并择优选取n个序列，将X_i(i＝1,2,…,N)，作为初始鸟巢，基于最小位置值规则的随机键编码将鸟窝位置换为PCB板元器件帖装工序的排列，根据鸟窝的位置计算评价各鸟窝的调度目标值，初选得到目前最优鸟窝X_best，记录当前最优帖装排序和调度目标值，迭代次数置为1；

步骤c：分析各种位置解的优劣性，分别建立劣解种群集和优解种群集；

步骤d：对于优解种群，转步骤f；对于劣解种群，顺序执行；

步骤e：根据标准布谷鸟搜索算法中的更新方式一，具体如式Ⅰ，对鸟巢位置进行搜索并与原位置进行对比，择优选择进行位置更新鸟窝，同时更新对应的帖装排序和调度目标值，转步骤g，

式Ⅰ：$>X_i^{(t+1)}=X_i^{\left(t\right)}+\alpha \otimes L\left(\lambda \right)$>

其中，表示第t+1代第i个鸟窝的候选位置；表示第t代第i个鸟窝的位置；α为控制步长；为点对点乘法；L(λ)为服从Levy分布的随机搜索路径，转步骤g；

步骤f：根据粒子群算法，具体如式Ⅱ，对其他鸟巢位置进行搜索并与原位置进行对比，择优选择进行位置更新鸟窝，同时更新对应的帖装排序和调度目标值，

式Ⅱ：$>v_i^{(t+1)}=w\times v_i^{\left(t\right)}+c_1\times random\left(\right)\times (p_i-x_i^{\left(t\right)})+c_2\times random\left(\right)\times (g-x_i^{\left(t\right)})$>

$>x_i^{(t+1)}=x_i^{\left(t\right)}+v_i^{\left(t\right)}$>

其中，表示位置；表示速度；random()为[0,1]之间的随机数；c₁、c₂为学习因子，是非负常数；w为惯性系数；P_i表示个体最优粒子；g表示全局最优粒子；

步骤g：对每个更新鸟巢生成随机数random()，与发现外来鸟蛋的概率P_a进行比较，若random()＜Pa，则宿主放弃更新鸟巢并随机新建鸟巢，从而得到一组新的鸟巢，然后用新的鸟巢位置与更新鸟巢进行对比，若更好，则用其作为现有鸟巢，同时更新对应的帖装排序和调度目标值；

步骤h：评估全部鸟窝的目标调度值，若更新之后鸟窝目标调度值更优，则在更新后的鸟窝中产卵，并找出其对应的最优鸟窝位置，保留最优鸟窝，并更新对应的帖装排序和调度目标值，

步骤i：保留最优帖装工序排列和调度目标值，迭代次数增加1，若达到最大迭代次数，转步骤j，否则转步骤c，进行下一轮寻优；

步骤j：输出最优值和最后的生产调度方案。

步骤四：对步骤三得到的一组生产线各贴片机贴装调度最优解提供给PCB板表面组装生产线控制系统,实现对贴片机贴装元器件的最优控制,保证整个生产线的每台贴片机按最优调度方式进行元器件贴装，达到了各贴片机的负荷均衡优化，提高了生产效率。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。