基于遗传算法装配线平衡问题探究

《基于遗传算法装配线平衡问题探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于遗传算法装配线平衡问题探究摘要：文中针对装配线平衡问题，提出了一种基于可行作业序列的多种群遗传算法。该算法依据可行作业序列产生初始种群，并据此构造交叉、变异算子，以保证后代种群都是可行解；而且多种群的遗传算法，扩大了搜索的空间范围,所以可以有效的避免局部最优的情况发生，而且还能增强算法的运行效率。文章在最后，用实例进行了运行效果的验证。Abstract：Forassemblylinebalancingprobleminthetext,puttingforwardaviablejobsequence-basedmultiple-populationgeneticalg

2、orithm.Thealgorithmbasedonfeasibleoperatingsequencesproduceinitialpopulation,andthusconstructedcrossoverandmutationoperator,toensurefuturegenerationspopulationsareviablesolutions；Andmultiple-populationgeneticalgorithmbroadensthescopeofthesearchspace,soitcanavoidlocaloptimization,alsoenha

3、ncetheefficiencyofalgorithms・Finallyanillustrativeexampleisgiventotestifythevalidityofthisalgorithm.关键词：装配线平衡；改进遗传算法；约束矩阵Keywords：assemblylinebalance；improvedGA；constraintmatrix中图分类号:F273文献标识码：A文章编号:1006-4311(2013)05-0123-030引言自从装配线平衡(AssemblyLineBalancingALB)问题被提出后，就一直为研究热点。在装配线上，工件一次进入

4、各个工位进行加工，如何在满足生产线节拍以及作业之间优先顺序的情况下，组合并优化分配作业单元，使各个工作站的工时尽可能相等，从而避免因资源过于空闲或忙碌而产生不良后果，这就是装配线平衡问题(AssemblyLineBalancingProblem,ALBP问题)[1]o通常情况下，根据所要优化的目标不同，可将装配线生产平衡问题分为两类[2]。第一类是在给定生产节拍、装配作业时间和作业逻辑关系的情况下，求解最小工作站数；第二类是先给定工作站数目、装配线的作业时间和作业优先关系，来求出最小的生产节拍及列出每个工作站内的作业分配情况，本文主要针对第二类装配线问题进行研究。从实质

5、上说，装配线平衡问题就是在一定约束条件下的组合优化问题。现代用来解决此类问题的方法大致可分为如下四类：①数学规划方法；②基于规划调度的优化方法；③启发式算法，如模拟退火法和遗传算法等；④人工智能算法,如神经网络等。余晓光等提出了一种禁忌搜索遗传混合算法，提高了算法的运行效率［3］；蒋艳等引入小生环境的改进遗传算法，进行了协同优化设计；肖中华等提出一种非标准遗传算法，确保算法收敛到最有或近优解［4］。鉴于遗传算法在实验及应用中取得的显著效果，本文采用多种群该进行遗传算法来解决ALB问题。1装配线平衡问题描述装配线平衡中，用m表示工作站数，n个作业元素，用C表示生产节拍，作

6、业所用时间ti表示第i个作业元素的作业时间，工作站时间用T(Sk)表示，Sk表示所有分配给第k个工作站作业的集合，则分配给第k个工作站的作业时间为T(Sk)二工iWkti；总作业时间为T二工■■ti。在进行ALB规划，首先必须满足单元作业之间的先后顺序约束条件，即某些作业之间在技术上存在先后的执行顺序。采用矩阵来描述作业装配的优先关系，若装配线上有n个作业，其优先关系矩阵为nXn的方阵，为P=(pij)nXn,其中P«=l,若i为j的紧前作业元素0,否则(1)式中i,j为作业元素序号。在对装配线的平衡效果进行评价时，基本的评价指标包括：节拍、工位数、总空闲时间、平衡延迟

7、、平滑性指标、装配线利用率、装配线生产能力增长指标等等［5］。本文根据所研究问题采用平衡延迟和平滑系数来。平衡延迟：P二■X100%(2)平滑系数：SI=H(3)这两个指标越小，越接近零，说明平衡效果越理想。2装配线平衡的遗传算法设计2.1编码本文采用基于可行作业序列的原则来对GA进行有效编码。按照装配关系优先关系矩阵中的作业元素的先后顺序，将作业元素序号排成一列，每个作业元素对应一个基因位，从而保证所有作业分配方案都是可行的，并且所有可行的作业序列都有一定的概率被搜索到，在排成列的工序中，每个基因对应一个工序。这种编码方式对适应函数和算