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

基于DNA遗传算法的表面贴装生产线的负荷均衡研究摘要本文以实际SMT生产现场为背景，在DNA遗传算法的基础上，构建出了表面贴装生产线的负荷均衡模型。在生产节拍给定以及满足一些约束条件下，目的是使得所研究的不同贴片机负荷均衡，让生产线平衡得以优化。相关数值实验证实了数学模型与算法的有效性，适当处理后可作为实际生产现场的现有软件,用于日常生产安排。关键字SMTDNA遗传算法负荷均衡生产线平衡;1引言表面组装技术(SurfaceMountTechnology,SMT)是将不同元器件(无引脚或短引脚的元器件)贴、焊到印制电路板(PrintedCircuitBoard,PCB)规定位置上的电子贴装技术。SMT技术作为新兴电子行业中的核心技术，在电子工业中得到越来越广泛的应用，特别是在笔记本电脑、智能手机等电子生产企业中,SMT技术正成为影响产品质量、公司效率最重要的因素。SMT生产线一般会由不同种类型的贴片机组成，其中贴片机是整个SMT生产线的核心设备，其生产效率的高低直接决定整条生产线的效率。由于贴片机是全自动设备，技术含量高，其工作原理和贴片工艺较复杂，如若不能很好的进行贴片机之间的负荷均衡，会降低整条生产线的效率以及设备的利用率。因此，研究表面贴片机负荷均衡对于提高SMT生产线的生产效率具有十分重要的意义。2研究背景本文以国内某大型电脑代加工企业SMT生产车间为背景，以松下公司目前最新研发的NPM-D高速贴片机为研究对象，分别是可以超高速贴装微小元件的「16吸嘴贴装头」高速贴片机、可以高速贴装微小元件到中型元件的「8吸嘴贴装头」高速贴片机、可以贴装各种异形元件的「2吸嘴贴装头」泛用贴片机。本文主要研究的是多台贴片机之间的负荷均衡优化,即不同种类元件在不同贴片机之间的负荷均衡问题，目的是使不同型号的贴片机作业时间近乎相同，接近于已知的CycleTime，从而使SMT生产装配线的平衡率达到最优。遗传算法虽然作为目前最广泛使用且被认同的解决最优化问题的方法，但是有其自身的缺点，其局部搜索能力差，容易过早收敛，而且基于0与1的二进制的编码方式存在明显的不足，对于一些繁复的表达方式，会出现编码长度过长、编码方式复杂且混乱的情况。从DNA生物学的生物进化过程受到启发，将遗传算法与DNA机理相结合，组成DNA遗传算法。DNA遗传算法同时具有遗传算法与生物学DNA的诸多优点，可使编码方式实现更灵活的表达，并且能使遗传算法的过程变得更加容易，很好的解决了单一遗传算法过早收敛以及编码方式欠佳等不足的缺点。3表面贴装生产线负荷均衡数学模型的建立设一条表面贴装生产线由m台贴片机组成，有n个独立的元件分配到m台机器中去，其中一台贴片机可以吸取ik个原件。每个工作站的实际工作时间it应尽可能地接近给定的生产线节拍时间Tt，这样可使得m台贴片机作业时间近乎相同，使得各台机器负荷均衡，从而提升设备利用率。设每一台机器的时间为it，求解目标是寻求一种最优方案，在节拍Tt给定以及满足实际生产现场下的一些约束条件下，使得整条生产线平衡达到最优。满足上述条件的数学模型如下：i表示贴片机编号，i为整数，且110i，其中机器编号1-7为NPM-D16Nozzle型号,机器编号8为NPM-D8Nozzle型号，机器编号9-10为NPM-D2Nozzle型号。it表示每台机器的实际工作时间，Tt表示产线生产节拍（Tt已知，由公司每日生产排程给定），j表示元件的种类,J为所有j的集合，jJ，其中iJ表示为机器i贴装元件种类j的集合，jD表示j种元件在基板PCB上的数量，即基板PCB需要多少个j种元件，iw表示i机器贴片一个元件的时间，iw参数是由贴片机厂商提供，其中iw=0.051s/chip（i=1,2,3...7），8w=0.090s/chip，9w=10w=0.360s/chip，k表示元件，即基板上所有点的元件，K为所有k的集合，l表示吸嘴的种类，L为所有l的集合，im表示第i台机器的供料槽（017im，公司实际贴片机料槽最多可放取17个），jS表示j种元件所占的供料槽，1ljb表示若元件种类j在编号为1-7的贴片机上使用吸嘴l，则其值为1，否则为0，2ljb表示若元件种类j在编号为8的贴片机上使用吸嘴l，则其值为1，否则为0，3ljb表示若元件种类j在编号为9-10的贴片机上使用吸嘴l，则其值为1，否则为0，ijz如果元件j安排在工作台i上，则其值为1，否则为0.其目标函数为，101infmaxiiiMitt(1)其中，iiijijjJtwDz,110i(2)..stijijijJszm，110i(3)1011ijiZ,jJ(4)11ljlLb,jJ(5)21ljlLb,jJ（6）31ljlLb,jJ（7）4基于DNA遗传算法的负荷均衡模型的编码计算DNA-GA（DNA遗传算法）从初始化出发，通过一代一代的进化与选择，从而得到优秀的群体与个体，进而找到问题的最优化解决方法。4.1编码方式DNA遗传算法最重要的步骤是采取何种方式进行编码，在初始化时，待解决问题的参数设计是通过4个字符集,,,ATCG来编码以形成染色体，即DNA链.DNA-GA以染色体的形式,,,ATCG为基本单位进行二进制编码，即A(00)、T(01)、C(10)、D(11),然后每次从K颗元件随机取出4颗元件，编码为元件种类和机器工作台吸嘴一一对应的关系，并组成DNA汤pt。4.2计算适应度因为目标函数是求最小化的问题，选取适应度函数为11Fitfxcfx式中101infmaxiiifxMitt，c为常数，为目标函数的保守估计值。则目标函数值越小，其所对应的适应度越大，4.3选择按照一定的概率ip从DNA汤pt中选取m个DNA链个体，作为双亲用于繁殖后代，产生新的个体加入到下一代1pt。4.4交叉DNA链中的交叉位置是随机选取的。在标准交叉中，其后代的个体是基于一个随机产生的特征码（交叉特征码为0和1）对父代进行操作而得到的。如下所示，若某一位置上交叉特征码为0，则其后代的碱基不变；若某一位置上交叉特征码为1，则其后代的碱基由双亲互换得到。......ATTCGCTAACTGCATCCTAG......TCCGACTGCTATCGTTCGAC01101010110110110101......ACCCACTGCTTTCATTCGAC......TTTGGCTAACAGCGTCCTAG4.5倒位以一定的概率ip从DNA汤1pt中随机选取若干个DNA链个体，在选中的DNA链个体中，随机将某两个位置碱基顺序进行倒位。倒位互换的目的是试图找到更好的进化性的基因顺序。4.6终止条件经过上述过程，将产生的新一代DNA汤反馈回算法流程的第2步（即计算适应度），再进行评价、选择、交叉和倒位操作，如此循环往复，使得适应度不断提高，直到适应度提高到某一极限值，则算法结束。5.数值实验5.1数据来源本文以实际生产现场中一款PCB板的S面（PCB板有两面，分为S面和C面，是公司人为称呼，以示区分）为研究对象，此PCB板S面总共需要贴装的元件有512颗。其中贴装机有10台，编号为1-7的为16Nozzle的NPM-D的高速机，编号为8的是8Nozzle的NPM-D的高速机，编号为9-10的为2Nozzle的NPM-D的泛用机。吸嘴的选择因元器件种类和贴片机类型而异,不同种类的元器件需要采用不同的吸嘴进行吸取,被安排到高速机上或泛用机上的同一种元器件可以选择不同的吸嘴进行操作。在本文所研究的模型中，通过笔者在公司实践获得的相关数据可得，本文所研究的PCB基板所需元件种类J总共有16种，元件种类j以及对应的种类数量jD如表1所示，元件种类0802080412041208160816122412241632123220322444124424442844365624编号12345678910111213141516种类数量24615925732311111121211表1元件种类j以及对应的种类数量jD一览表吸嘴型号L有7种，不同机型的机器对应元件种类j以及吸嘴种类l如表2所示，机型型号吸嘴种类l16Nozzle2302358Nozzle1402352402Nozzle10021003100424215443544610061192元件种类j16Nozzle080208048Nozzle08041208161224122Nozzle161224124412160824163212322032244424442844365624表2不同机型的机器i对应元件种类j以及吸嘴种类l一览表由表1、表2可知，在选取元件时我们首先要考虑元件种类的特殊性以及贴装的优先关系，有些元件只能在特定的机型工作台上贴装，如编号为0802的元件只能在16Nozzle的机型上贴装，1608的元件只能在2Nozzle的机型上贴装；有些元件可以在16Nozzle、8Nozzle的机型上贴装，如编号为0804的元件；有些元件可以在8Nozzle、2Nozzle的机型上贴装，如1612、2412的元件。由于所吸取的元件种类不同，高速机和泛用机吸取一颗元件所需要的时间不同，表3为贴片机在理想状态下吸取一颗元件所需要的时间。机型NPM-D16NozzleNPM-D8NozzleNPM-D2Nozzle时间（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计算得1infmaxmiiiMitt=5.21，其平衡率为1=100%94.69%maxmiiitmtω。通过导入DNA遗传算法，模拟建模流程，经编码、选择、交叉、倒位等计算方式，计算适应度，然后再重复上述步骤，重新计算适应度，直至找到最优解。仿真程序用Matlab6.0编写，算法中使用的参数为交叉概率0.95cp,变异概率0.30mp,种群规模N=100，选取最大遗传代数为300.平衡预算结果如表5所示，机台编号12345678910机型16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle16Nozzle8Nozzle2Nozzle2Nozzle时间(s)9.3459.2349.4329.4729.2439.4679.5529.5439.2439.367表5由目标公式1infmaxmiiiMitt可得infMi=1.622，其平衡率为1=100%98.30%maxmiiitmtω。由上述比较可得，通过DNA遗传算法对不同元件重新进行调度分配，使得每台贴片机之间的设备负荷得到很大的改善，平衡率也达到98.30%，6结束语本文基于DNA遗传算法，对多台贴片机组成的SMT生产线的负荷均衡问题进行了理论数学建模和算法仿真，通过对生产现场的实际数据模拟证实了模型及算法的适用性和可行性。因此，对于提高生产现场SMT生产线的平衡率有很好的指导和借鉴意义，通过相关编程可以作为生产现场的优化平衡软件，提高生产效率。