基于DNA遗传算法的表面贴装生产线的平衡研究 0830(共7页)

1、基于(jy)DNA遗传算法的表面(biomin)贴装生产线的负荷均衡研究摘要(zhiyo) 本文以实际SMT生产现场为背景，在DNA遗传算法的基础上，构建出了表面贴装生产线的负荷均衡模型。在生产节拍给定以及满足一些约束条件下，目的是使得所研究的不同贴片机负荷均衡，让生产线平衡得以优化。相关数值实验证实了数学模型与算法的有效性，适当处理后可作为实际生产现场的现有软件, 用于日常生产安排。关键字 SMT DNA遗传算法 负荷均衡 生产线平衡;1引言表面组装技术( Surface Mount Technology, SMT)是将不同元器件( 无引脚或短引脚的元器件) 贴、焊到印制电路板( Print

2、ed Circuit Board, PCB) 规定位置上的电子贴装技术。SMT技术作为新兴电子行业中的核心技术，在电子工业中得到越来越广泛的应用，特别是在笔记本电脑、智能手机等电子生产企业中,SMT技术正成为影响产品质量、公司效率最重要的因素。SMT生产线一般会由不同种类型的贴片机组成，其中贴片机是整个SMT生产线的核心设备，其生产效率的高低直接决定整条生产线的效率。由于贴片机是全自动设备，技术含量高，其工作原理和贴片工艺较复杂，如若不能很好的进行贴片机之间的负荷均衡，会降低整条生产线的效率以及设备的利用率。因此，研究表面贴片机负荷均衡对于提高SMT生产线的生产效率具有十分重要的意义。2 研究

3、背景本文以国内某大型电脑代加工企业SMT生产车间为背景，以松下公司目前最新研发的NPM-D高速贴片机为研究对象，分别是可以超高速贴装微小元件的16吸嘴贴装头高速贴片机、可以高速贴装微小元件到中型元件的8吸嘴贴装头高速贴片机、可以贴装各种异形元件的2吸嘴贴装头泛用贴片机。本文主要研究的是多台贴片机之间的负荷均衡优化,即不同种类元件在不同贴片机之间的负荷均衡问题，目的是使不同型号的贴片机作业时间近乎相同，接近于已知的Cycle Time，从而使SMT生产装配线的平衡率达到最优。遗传算法虽然作为目前最广泛使用且被认同的解决最优化问题的方法，但是(dnsh)有其自身的缺点，其局部搜索能力差，容易过早收

4、敛，而且基于0与1的二进制的编码方式存在明显的不足，对于一些繁复的表达方式，会出现编码长度(chngd)过长、编码方式复杂且混乱的情况。从DNA生物学的生物进化过程(guchng)受到启发，将遗传算法与DNA机理相结合，组成DNA遗传算法。DNA遗传算法同时具有遗传算法与生物学DNA的诸多优点，可使编码方式实现更灵活的表达，并且能使遗传算法的过程变得更加容易，很好的解决了单一遗传算法过早收敛以及编码方式欠佳等不足的缺点。3 表面贴装生产线负荷均衡数学模型的建立设一条表面贴装生产线由台贴片机组成，有个独立的元件分配到台机器中去，其中一台贴片机可以吸取个原件。每个工作站的实际工作时间应尽可能地接近

5、给定的生产线节拍时间，这样可使得台贴片机作业时间近乎相同，使得各台机器负荷均衡，从而提升设备利用率。设每一台机器的时间为，求解目标是寻求一种最优方案，在节拍给定以及满足实际生产现场下的一些约束条件下，使得整条生产线平衡达到最优。满足上述条件的数学模型如下：表示贴片机编号，为整数，且，其中机器编号1-7为NPM-D 16Nozzle型号,机器编号8为NPM-D 8Nozzle型号，机器编号9-10为NPM-D 2Nozzle型号。表示每台机器的实际工作时间，表示产线生产节拍（已知，由公司每日生产排程给定），表示元件的种类, 为所有的集合，其中表示为机器贴装元件种类的集合，表示种元件在基板PCB上

6、的数量，即基板PCB需要多少个种元件，表示(biosh)机器(j q)贴片一个元件的时间(shjin)，参数是由贴片机厂商提供，其中=0.051s/chip（=1,2,3.7），=0.090s/chip，=0.360s/chip，表示元件，即基板上所有点的元件，为所有的集合，表示吸嘴的种类，为所有的集合，表示第台机器的供料槽（，公司实际贴片机料槽最多可放取17个），表示种元件所占的供料槽，表示若元件种类在编号为1-7的贴片机上使用吸嘴，则其值为1，否则为0，表示若元件种类在编号为8的贴片机上使用吸嘴，则其值为1，否则为0，表示若元件种类在编号为9-10的贴片机上使用吸嘴，则其值为1，否则为0，

7、如果元件安排在工作台上，则其值为1，否则为0.其目标函数为， (1)其中， , (2) ， (3), (4), (5), （6）, （7）4 基于DNA遗传算法的负荷均衡模型的编码计算DNA-GA（DNA遗传算法）从初始化出发，通过一代一代的进化与选择，从而得到优秀的群体与个体(gt)，进而找到问题的最优化解决方法。4.1 编码(bin m)方式(fngsh)DNA遗传算法最重要的步骤是采取何种方式进行编码，在初始化时，待解决问题的参数设计是通过4个字符集来编码以形成染色体，即DNA链. DNA-GA以染色体的形式为基本单位进行二进制编码，即A(00)、T(01)、C(10)、D(11),然后

8、每次从K颗元件随机取出4颗元件，编码为元件种类和机器工作台吸嘴一一对应的关系，并组成DNA汤。4.2 计算适应度因为目标函数是求最小化的问题，选取适应度函数为式中，c为常数，为目标函数的保守估计值。则目标函数值越小，其所对应的适应度越大，4.3 选择按照一定的概率从DNA汤中选取m个DNA链个体，作为双亲用于繁殖后代，产生新的个体加入到下一代。4.4 交叉 DNA链中的交叉位置是随机选取的。在标准交叉中，其后代的个体是基于一个随机产生的特征码（交叉特征码为0和1）对父代进行操作而得到的。如下所示，若某一位置上交叉特征码为0，则其后代的碱基不变；若某一位置上交叉特征码为1，则其后代的碱基由双亲互

9、换得到。4.5 倒位以一定(ydng)的概率从DNA汤中随机(su j)选取若干个DNA链个体(gt)，在选中的DNA链个体中，随机将某两个位置碱基顺序进行倒位。倒位互换的目的是试图找到更好的进化性的基因顺序。4.6 终止条件经过上述过程，将产生的新一代DNA汤反馈回算法流程的第2步（即计算适应度），再进行评价、选择、交叉和倒位操作，如此循环往复，使得适应度不断提高，直到适应度提高到某一极限值，则算法结束。5.数值实验5.1 数据来源本文以实际生产现场中一款PCB板的S面（PCB板有两面，分为S面和C面，是公司人为称呼，以示区分）为研究对象，此PCB板S面总共需要贴装的元件有512颗。其中贴装

10、机有10台，编号为1-7的为16Nozzle的NPM-D的高速机，编号为8的是8Nozzle的NPM-D的高速机，编号为9-10的为2Nozzle的NPM-D的泛用机。吸嘴的选择因元器件种类和贴片机类型而异, 不同种类的元器件需要采用不同的吸嘴进行吸取, 被安排到高速机上或泛用机上的同一种元器件可以选择不同的吸嘴进行操作。在本文所研究的模型中，通过笔者在公司实践获得的相关数据可得，本文所研究的PCB基板所需元件种类总共有16种，元件种类以及对应的种类数量如表1所示，元件种类0802080412041208160816122412241632123220322444124424442844365

11、624编号12345678910111213141516种类数量24615925732311111121211表1 元件种类以及对应的种类数量一览表吸嘴型号L有7种，不同机型的机器对应元件种类以及吸嘴种类如表2所示，机型型号吸嘴种类16 Nozzle2302358 Nozzle1402352402 Nozzle10021003100424215443544610061192元件种类16 Nozzle080208048 Nozzle08041208161224122 Nozzle161224124412160824163212322032244424442844365624表2 不同(b tn)

12、机型的机器对应(duyng)元件种类以及(yj)吸嘴种类一览表由表1、表2可知，在选取元件时我们首先要考虑元件种类的特殊性以及贴装的优先关系，有些元件只能在特定的机型工作台上贴装，如编号为0802的元件只能在16Nozzle的机型上贴装，1608的元件只能在2Nozzle的机型上贴装；有些元件可以在16Nozzle、8Nozzle的机型上贴装，如编号为0804的元件；有些元件可以在8Nozzle、2Nozzle的机型上贴装，如1612、2412的元件。由于所吸取的元件种类不同，高速机和泛用机吸取一颗元件所需要的时间不同，表3为贴片机在理想状态下吸取一颗元件所需要的时间。机型NPM-D 16No

13、zzleNPM-D 8NozzleNPM-D 2Nozzle时间（s/chip）0.0510.0900.360表3 贴片机理想状态下吸取一颗元件所需时间5.2 数据结果说明 由公司自带软件编入相应程序，通过秒表测量，获得贴片机测量时间如下表4所示，机台编号12345678910机型16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle8Nozzle2Nozzle2Nozzle时间（s）9.02258.87759.343759.38259.18759.226259.2259.23259.819.5825表4计算得=5.21，其平衡率为。通

14、过(tnggu)导入DNA遗传算法，模拟(mn)建模流程，经编码、选择(xunz)、交叉、倒位等计算方式，计算适应度，然后再重复上述步骤，重新计算适应度，直至找到最优解。仿真程序用Matlab6.0编写，算法中使用的参数为交叉概率,变异概率,种群规模N=100，选取最大遗传代数为300.平衡预算结果如表5所示，机台编号12345678910机型16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle8Nozzle2Nozzle2Nozzle时间(s)9.3459.2349.4329.4729.2439.4679.5529.5439.2439.367表5由目标公式 可得=1.622，其平衡率为。由上述比较可得，通过DNA遗传算法对不同元件重新进行调度分配，使得每台贴片机之间的设备负荷得到很大的改善，平衡率也达到98.30%，6 结束语本文基于DNA遗传算法，对多台贴片机组成的SMT生产线的负荷均衡问题进行了理论数学建模和算法仿真，通过对生产