改进遗传算法在混合装配线平衡问题中的应用

改进遗传算法在混合装配线平衡问题中的应用

［摘要］为满足顾客对产品个性化的需要,越来越多的企业采用多种小批量的生产模式,逐步设计和建立起了混合装配生产线,而如何确保混装线负荷平衡是一个十分重要的问题。对此,本文提出了一种基于自适应遗传算法的解决方法,能够很好地解决简单遗传算法易早熟的问题,为混合装配线的设计和优化改进提供有效依据。
［关键词］遗传算法；混合装配线；负荷平衡
［中图分类号］TP278；TH165［文献标识码］A［文章编号］1005-6432（2012）2-0046-02
1引言
装配线的平衡问题是指在作业先后顺序的约束下,将作业任务分派到工作站中,以使得各个工作站内负荷尽量接近节拍（即处于繁忙状态）,且各个工作站间负荷尽量均衡,从而确保整条装配线的总闲置时间最少。装配线平衡问题实质上就是组合优化问题,其受到由产品设计工艺和制造过程技术所决定的作业任务之间先后关系的约束而变得异常复杂。实际中,装配线的负荷平衡有着特别重要的意义：一方面,装配生产线的平衡程度不仅直接反映了装配生产线的效率,而且影响到产品的质量,如果各工位负荷不均衡,劳动强度大的工人就有可能为了赶上装配线的运行节拍而匆忙操作,常常忽视了产品质量。另一方面,一条负荷不均衡的装配线会给工人不公平的感觉,易生厌烦和抵触情绪,进而影响整个装配线的生产效率。
混合装配线能够连续且同时在一条装配线上组装结构相似、工艺接近的不同品种产品,与单一装配线相比,其生产过程中产品种类多,工序复杂。对此本文提出将混装线上不同产品利用虚作业任务整合为一种产品,即将混装线平衡问题转化成单一装配线平衡优化问题,之后采用自适应遗传算法进行基于作业任务的平衡优化。
2问题分析与数学模型建立
3遗传算法设计
3.1编码与解码
本文根据混合装配线平衡问题的特点,设计了实数编码的方法。首先,按照装配的先后顺序将各个工序连接成一个实数串,构成一个染色体。如按规则编码后的一种染色体基因型为142378569。表示先完成操作1,再完成操作4,依此类推。染色体的基因型表示了加工顺序,但不反映工位划分的情况。之后,需要对染色体进行工序分割,将各个工序划分到相应的工位。其操作方法是,按照染色体基因型上操作的排列顺序,依次逐个将操作分配到工位中,当安排某操作至某工位内时,该工位分配的工序总加工时间超过节拍时间,则将此工序连同后面的工序安排至下一工位,保证各工位内操作时间总和不超过节拍,依此类推，直至将所有工序分配到相应工位中。
3.2初始种群的产生
初始种群的产生要保证其随机性,但同时还需要满足装配先后顺序的约束。首先,依据工序优先关系产生可选工序集合,之后,在可选工序集合中随机选定一个工序,排入染色体基因位,如此重复,产生一条染色体。
3.3选择算子
采用最优保存策略的方法,首先,将父代中的最优个体直接复制到下一代,对于其他个体,采用锦标赛选择法,设定锦标赛规模为2,从父代中随机地选择两个个体,比较其适应度值,将较优的个体复制为新代个体,如此重复，直至新代个体数目达到种群数量。
3.4交叉算子
为保证交叉操作后工序先后顺序不被打乱,采用如下方法：随机从种群中选出两个染色体作为父代双亲,在其中一条染色体上随机地选取一段基因,其子代在这段基因里的作业按照另一父代染色体的顺序排列,其余部分的排列顺序不变,组成两个新子代染色体。因为双亲都是可行解,故通过这样的方法产生的子代也必然是可行解。
3.5变异算子
变异操作采用移位变异法：在父代中任意选择一个染色体,随机选择一个基因位进行变异。先找出其满足约束关系的可行区间,然后将变异基因插入可行区间中任意一个位置。
3.6适应度函数设计
平衡度较好的装配线既要满足各个工位间负荷尽量均衡,又要满足工位内负荷饱满,节拍内空闲时间接近于零。以此为目标设计适应度函数,数学表达式为：
通过以上实例分析，算法在进行到第16代以后，收敛于最优结果,将所有工序划为8个工作站。计算结果与理论最小工作站数相一致。
5总结
混合装配线平衡问题是一个NP-hard问题,本文通过对不同产品作业任务的整合,将混合装配线平衡问题转化为单一装配线平衡问题,进而采用了自适应技术改进遗传算法,使得交叉概率和变异概率在运算过程中动态调整,使得算法在运算初期增强了搜索能力,能够有效避免过早收敛和陷入局部最优解。而运算后期能够很大程度保存最优解,加快收敛速度。算例结果显示,算法取得了很好的优化结果,有效解决了工序分配的问题,能够为装配线平衡优化提供有力支持。
参考文献：
［1］肖中华.基于改进遗传算法的汽车装配线平衡问题研究［D］.武汉：武汉科技大学,2010.
［2］凌文曙.基于遗传算法的混流装配线工作站平衡研究［J］.合肥工业大学学报,2008，31.
［3］曹振新,朱云龙.多目标遗传算法在混流装配线排序中的应用［J］.计算机工程,2005.

［基金项目］首都经济贸易大学研究生科技创新项目,北京科技计划面上项目,项目号CUEB2010012。
［作者简介］郝金鹏（1985―）,男,河北张家口人,首都经济贸易大学研究生,研究方向：生产计划与控制。