遗传算法在装配线平衡中的应用

DOI:10.14018/j.cnki.cn13-1085/n.2010.02.004

ValueEngineering·253·

遗传算法在装配线平衡中的应用

TheApplicationsofGeneticAlgorithmsininAssemblyLineBalancing

肖中华①XiaoZhonghua;邓明星②DengMingxing;唐秋华①TangQiuhua

(①武汉科技大学机械自动化学院,武汉430081;武汉430081)②武汉科技大学汽车与交通工程学院,(①CollegeofMechanic-automation,WuhanUniversityofScienceandTechnology,Wuhan430081,China;

)②CollegeofAutomobileandTrafficEngineering,WuhanUniversityofScienceandTechnology,Wuhan430081,China

摘要:装配线平衡是混合装配生产线调度的重要基础,是面向订单装配(ATO)得以实施的技术瓶颈,对提高生产率和设备利用率也具有重要

意义。在工位数量给定的条件下,文章针对装配线平衡的数学模型,提出了一种面向装配线平衡的非标准遗传算法。该算法基于各操作之间的逻辑

优先关系产生可行操作序列而生成初始种群,保证解的可行性;在此基础上实现寻找最小节拍、选定较优序列进行遗传,并采用最优保存策略确保算法收敛到最优或近优解。最后通过实例验证了该算法的有效性和可行性。

Abstract:Thispaperpresentsanon-standardgeneticalgorithmtosolvethemathematicmodelforassemblelinebalancing,inwhichtheworkstationnumberisgiven.Initialpopulationofthegeneticalgorithmisbasedonthelogicrelationshipbetweenoperations,whichcanensurethefeasibilityofthesolution.Andthen,thesequence,whichhasbettertargetvalue,willbeselectedtodogeneticoperators,andtheminimumcycletimewillbefound.The

andthismethodcanhelpthealgorithmeasilyovercomethelocalsuperiorkeepingstrategyisusedtoprotectthebestoneinthepastsuperiorindividual,

restraintweaknessandgettheentireoptimalresult.Atlast,acasehaveprovedthisapproacheffectiveandfeasibletosolvethisproblem.

关键词:遗传算法;装配线平衡;可行序列Keywords:geneticalgorithm;assemblylinebalancing;feasiblesequence

中图分类号:TH16

文献标识码:A

文章编号:1006-4311(2010)02-0253-03

0引言

装配线平衡是将基本的作业元素分配到工作站,满足特定的目标和约束条件。从实质上看,装配线平衡问题就是组合优化问题,但这个问题由产品设计工艺和制造过程技术所决定的作业元素之间的先后关系而变得异常复杂。在实际生产中,由于装配线的柔性增加,很多情况都可能导致生产线不能顺畅的运行,从而造成暂时性不平衡现象发生,而且装配生产线的平衡程度不仅直接反应了装配生产线的效率,而且影响产品的质量,劳动强度大的工人为了赶上装配线的运行节拍,常常忽视了产品质量。据美国有关资料统计,即使在美国这样工业发达的国家,在工业装配生产中平均要有5%~10%的装

其平衡问题就配时间是浪费在平衡延迟中。从装配线产生之日起,

一直受到人们的重视[1]。现代关于此类问题的解决方案大致可以分为四类:包括线性规划,非线性规划,多目标规划,①数学规划方法,动态规划等;此类方法是给不同的操作根据潜在的②基于规则调度,

生产瓶颈分配不同的权重以达到优化目的。③启发式方法,如模拟退火发、遗传算法、禁忌搜索算法、噪声算法等;如④人工智能算法,

[2][3]

神经网络等。面对大规模的装配线平衡,解决此类问题专家系统、

的主要趋势是采用启发式。但一些启发式搜索方法在逼近最优解或次优解的搜索中,不断地有倒退过程,搜索效率低,还易产生“组合爆

现象[4]。鉴于此,本文主要采用改进的遗传算法来解决这个NP-炸”

hard问题。

1遗传算法遗传算法(GA)是J.Holland于1975年受生物进化论的启发而提出的。GA的提出一定程度上解决了传统的基于符号处理机制的

信息处理和解决组合爆炸等方面所遇到人工智能方法在知识表示、

的困难,其自组织、自适应、自学习和群体进化能力使其适合于大规模复杂优化问题。GA是一种通用的优化算法,它对优化设计的限制较少,由于它的进化特性,它在解的搜索中,不需要了解解的内在性质,可以处理任意形式的目标函数和约束,无论是线性的还是非线性的,离散的还是连续的,甚至是混合的搜索空间;它的另一个显著优点就是能够有效地进行概率意义下的全局搜索,而且能够以较大的概率求得全局最优解。

对于装配线平衡问题来说,标准的遗传算法的操作算子可能产

生早熟收敛或收敛缓慢等缺点,甚至由于算子的不可行而无法得出可行解。这也是遗传算法在实际应用遇到的最大障碍,鉴于此本文采取基于可行序列的非标准遗传算子,保证算子的可行性,并采取最有保留策略,避免最优解丢失或算法退化。

2装配线平衡的遗传算法设计装配线平衡问题的一般提法是:给定产品装配作业表(包括各项

作业时间及其先后关系)或者直接给出装配作业先后关系装配作业、

图,优化某一特定的目标函数。一般可以分以下几类:①生产节拍C给定,在满足生产线约束条件的前提下最小化工作站;②工作站数量给定,在满足生产线约束条件的前提下最小化生产节拍,使节拍与工

最大化分配同一工位的操作相作站负荷之差最小;③生产节拍给定,

关性。

2.1装配线平衡的数学模型

本文主要对上述提及的第二类装配线问题进行研究,即已知工作站数量,最小化生产节拍,使节拍与工作站负荷之差最小。目标值设定为负荷方差(WorkloadVariance),最小节拍CT等于最优方案中的最大工位时间。这类装配线平衡问题的数学模型如下:

minMV=

1N

式中:N为给定工位数量,Tj为分配在j工位的操作时间和,ti为第i个作业元素的操作时间。2.2装配线平衡的算法设计

改算法采用的是基于可行序列的遗传算法来求解装配线平衡问题,无论是初始种群的产生

初始化种群:随机产生

还是遗传算子的构造,都是P个可行作业序列直接从作业元素之间的顺

对种群中各个个序关系出发,从而保证它搜

体进行评价

索的所有作业序列以及相

Y结束并输出最佳应的作业分配方案都是可个体及统计

行的,并且所有的可行分配N

个体选择方案都可能被搜索到,效率

作业元

极高。如图1是该算法的交叉素之间流程图描述。的优先

变异

2.3编码约束编码就是将问题的解下一代种群用一种码来表示,从而将问图1遗传算法框图

Σ

j=1

N

ΣΣΣ

n

2

ti

Tj

i=1

———————————————————————

基金项目:国家自然科学“混装生产精准作业的多尺度智能元胞调度模型研

,项目编号:究”50875190/E051005。

作者简介:肖中华(1984-),男,硕士研究生,机械制造及其自动化专业,研究

方向为工业工程。

·254·

价值工程

题的状态空间与GA的码空间相对应,这很大程度上依赖于问题的I},如果CT′燮CT,则进入Step5,此分配方案为该CT′即为最小节拍,性质,并将影响遗传操作的设计。本文采取的基于可行序列的编码序列下的最优方案。否则转向Step2;方式:按作业元素分派至工作站的先后顺序,将作业元素排成一列,Step5:计算目标函数:

2

每个作业元素对应一个基因位,这种编码方式对目标函数和操作算n

N1ti子的适应性较好。图2是经过编码后的一染色体的图解。这个染色ΣWV=Σi=1Tj体说明了各个作业元素被分配的先后顺序,其中第一次分配作业元j=1

N

第二次分配作业元素2第三次分配作业元素4…第八次分配作素1,2.6选择业元素7,最后分配作业元素9。选择操作用于避免有效基因的损失,使高性能的个体得以更大

燮燮

12435

6679

图2编码后的染色体

2.4初始化

初始种群通常是随机产生的。鉴于保优GA的概率1收敛特性,

本文基于各操作之间的优先关系,随机产生一组的可行作业序列作为初始种群。

假设a(i)为完成操作i之后可行的操作集合。根据优先关系,操作j能进入可行操作集合a(i)的条件是它所有的前序操作都已经完成而本身未完成。因此,生成可行操作序列的具体步骤如下:

挑选没有前序操作或前序操作已分配的任务,形成可行Step1:

操作集合a(i);

判断终止条件,可选集合a(i)为空,则停止;否则进入Step2:

Step3;

从可行操作集合中随机选择一个任务,编入基因位;Step3:

更新可行操作集合a(i),即删除已选操作,并加入符合规Step4:

则的新操作;进入Step2。

2

1

3

5

8

6

9

4

7

图3优先关系图

以9个操作元素的工位分配问题为例,图3为其优先关系图。表

将此过程循环P次,则可得出1为其一染色体各个基因产生的过程。

即产生初试种群P(i)。P个可行序列,

表1个体基因选择过程

的概率生存,从而提高全局收敛性和计算效率。为避免最优解的丢

失,本文采取最优保存策略,即上代最优个体直接复制到新代种群。其他个体则采用锦标赛法。具体如下:

选择竞标赛规模K=2;Step1:

在当前种群中随机产生K个个体;Step2:

比较所选择个体的适应度值,将值较小的个体复制成为Step3:

新代个体;

重复step2、Step4:step3直至新代个体数目达到种群数量;

2.7交叉

从选择操作产生的新染色体种群中任取两个染色体。随机产生一个小于操作数的整数,确定交叉点(例如产生随机数7,则交叉点进在第7个基因和第8个基因之间)在这个交叉点上将这两个体成左右两部分。取出第一个染色体的左面部份,同时在第二个染色体中删除第一个染色体左边部份的基因,剩余的基因按照原来的顺序排列。以第一个染色体的左部和第二个染色体中按上述步骤处理得到的基因为右部,重组为一个新的染色体。把用于交叉操作的两个父代染色体从种群中删除。把产生的后代染色体加入新种群。

2.8变异

为了保证优先关系约束,文中采用移位变异法,任意选择一个个

先找出其满足约束关系体,任意选择一个基因(作业元素)进行变异。

的可行区间,然后将变异基因插入其中任意一个位置。

3实例分析

基于上述所提出的遗传算法,本文采用C++语言实现了相应的程序。下面以一个具有三十个装配操作的装配生产线为例。该装配线设计工位为9个。图4为其各个操作之间的优先关系图。图中的每个节点表示一个操作,有向边表示各操作之间的逻辑优先关系,节点上数值表示每个操作对应的操作时间。

9271

133154

225146

11788

[1**********]

[1**********]425

2017191620

[1**********]124

16262729

28

30

基因位123456789

已分配操作121,1,2,41,2,4,31,2,4,3,51,2,4,3,5,61,2,4,3,5,6,82,4,3,5,6,8,71,可选择作集合

12,33,43,75,6,76,7,87,879选择操作

124356879

2615

251618

图4装配操作优先关系图

将程序运行6次,其最优结果如表2。

表2装配线平衡

操作分配

工位1

工位2工位3工位4工位5工位6工位7工位8工位9

1,4,2,3,65,8,7,1110,913,1514,25,18,2012,1617,19,22,2123,24,2926,27,28,30

工位时间Tj

58

[**************]6

2.5解码及适应度计算

按照个体中的顺序将操作分配至工位,要满足每个工位的操作

因此在解码过程中首先必须求出每个可行序时间和不超过节拍CT,

列下的最小节拍CT′,具体步骤如下:

计算理论最小节拍Step1:

CT=Σti/N;

i=1N

以CT为节拍,按照可行序列将任务分配到工位,直至Step2:

(N-1)工位,剩余操作全部分配至N工位;

计算Tj(j=1,)和Tj′=Tj+tj+1(j=1,Step3:2…N2,3…N-1,tj+1为

分配至j+1工位的第一个操作对应时间);

计算CT′=max{Tj|j=l,Step4:2…N}andCT=min{Tj′|j=l,2…N-

根据程序运行结果,其节拍应设定为59,平衡延迟为:9×59-ΣTi

j=19

d=

=

531-517

=2.64%

ValueEngineering·255·

线性振动的神经网络建模

NeuralNetworkModelingofLinearVibration

李晔①LiYe;赵杨②ZhaoYang;杨诗婷②YangShiting

(①乌海职业技术学院,乌海016000;呼和浩特010051)②内蒙古工业大学理学院,

(①WuhaiVocationalTechnicalCollege,Wuhai016000,China;

②SchoolofScience,InnerMongoliaUniversityofTechnology,Hohhot010051,China)

摘要:本文利用人工神经网络对两自由度线性振动系统进行了神经网络建模,并通过所建立的神经网络模型对该系统进行了预测。分别利用

将一段时间内的激励力作为网络的输入参数,对应于该段时间内MATLAB和BP网络作为平台和训练工具。以两自由度悬臂梁的受迫振动为例,

由振动产生的挠度作为网络的输出参数,然后利用BP网络进行训练。将网络模型预测结果与精确解进行对比,误差甚小。该结果表明:所建立的神经网络模型合理、有效,可利用其对该类问题进行预测并应用于工程实践中。

Abstract:Usingartificialneuralnetworktogettwodegreeslinearvibrationsystemmodeling,theneuralnetworkbytheneuralnetworkmodelforthissystemisforecasted.MATLABandBPnetworkhaverespectivelybeenasplatformandtrainingtools.Forexample,withtwodegreesofthecantileverbeamforcedvibration,atimeofbasicwillbeasinputparametersandcorrespondingtothatperiodofdeflectionbyvibrationasnetworkoutputparameters,thenusingBPneuralnetworkwastrained.comparingthenetworkmodelpredictionresultswiththeexactsolutions,thereisaverysmallerror.Theresultsshowthat:theneuralnetworkmodelisreasonableandeffective,whichcanbeusedtopredicttheseproblemsandapplicationinengineeringpractice.

关键词:悬臂梁;神经网络;建模;振动

Keywords:cantilever;neural;networkmodeling;vibration

中图分类号:TH113.1

文献标识码:A

文章编号:1006-4311(2010)02-0255-02

0引言

随着重大工程结构(高层建筑,大坝,桥梁等)的兴建及旧有结构的老化,需要及时了解结构的健康状况,以便对结构进行安全加固处理,从而避免巨大的经济损失。随着工程技术的发展,机械振动问题

[6]

已成为各个工程领域内经常提出的重要问题。由于振动而引起工程结构的使用寿命缩短,甚至结构的破坏的例子也是很多。因此,对振动系统进行预测显得尤为重要。

近年来,国际上掀起了一股人工神经网络的研究热潮,人工神经网络独特的结构和处理信息的方法,使其在许多应用领域中取得了显著的成效,能够解决一些传统计算机方法难以解决的问题。因此,利用人工神经网络对振动系统进行建模并预测,为振动结构的健康诊断开辟了一条新路径,避免了以往在已知激励和动力响应条件下,求解结构系统参数的反问题中出现的不适定性。提取能够反映结构损伤的特征参数作为神经网络的输入才能保证预测结果的准确性。神经网络是20世纪80年代末期发展起来的一种实用的多学科交叉技术,已成为“智能控制的一个新分支,是自动控制领域的前沿学科之一。1943年建立的第一个神经模型-NP模型,为神经网络的研究与发展奠定了基础。至今,已经建立了多种神经元与网络的模型,取得了相当多的成果。

本文利用人工神经网络对两自由度的线性振动系统进行神经网络建模,并利用所建立的模型对该系统进行预测。首先将结构受迫振动某一时间段内的激励力作为BP网络的输入参数,对应这段时间内由激励力产生的挠度作为BP网络的输出参数,然后进行训练。

将训练结果与相对的精确解进行对比,误差很小,故该模型可以作为

线性振动系统的神经网络模型,并且可以利用该模型对线性振动系统进行预测。预测的含义分为两种:一种是已知一段时间内的挠度而对另一段等长时间内的挠度进行预测;另一种是已知某一激励力作用下的挠度而对其他任意激励力作用下的挠度进行预测。此种预测结果与真实结果相比误差甚小,故此预测结果可以代替真实结果应用到实际中。上述这些工作为类似问题的研究提供了一定的基础,同时也有力地推动了神经网络在振动系统中的应用。

1算例分析

以两自由度悬臂梁,受力与尺寸如图1所示。该悬臂梁的材料为

923

密度ρ=7800kg/m,长l=1m,梁的横截面积45号钢,E=200×10N/m,

为a×a=0.06×0.06m2的正方形。两钢求质量分别为m1=80kg,m2=

(w0t)与F())40kg。当m1和m2同时受到简谐激励力F(=F01sin=1t2t

(w0t)作用时,该系统发生线性振动,其中w0=rad/s,F02sinF01=0.8KN,F02=1KN且为无阻尼情况

2

———————————————————————

作者简介:李晔(1981-)内蒙古人,助教,力学专业。,女,

生产效率高达97.36%,文献[2]中用GAMS和CPlex求解该类问

题的MILP模型,在此案例的应用中,其运行结果各工位的时间分别为:生产58,57,59,61,60,53,54,52,63。计算其平衡延迟d1=8.81%,效率为91.18%。证明本文提出的方法在配置装配线工位可以降低平衡延迟,提高生产效率,但在计算效率上与文献[2]中的方法相比还需要改进。

4结论

本文给出了的初始种群方法及各种遗传算子的实现步骤,在寻求各工位负荷最平衡的同时,寻求最小生产节拍。并用实例证明该方法在对装配线平衡问题的求解,能得出理想的结果。

参考文献:

席忠民,陈平和,严运兵.混装线投产序列和工位任务的协同[1]唐秋华,

调度机理[J].工业工程,(1):2008,1119-24.

[2]QiuhuaTang,ChristodoulosA.Floudas2,JianyiKong,etcANovel

ApproachForSchedulingMixed-modelAutomobileAssemblyLineBasedOnMILP.WCGO-2009.

杨月新.装配生产线的平衡问题研究[J].机械设计与制造,[3]杜运普,

(2):2003,104-16.

王吉权,吴昌友等.实数遗传算法的改进研究[J].生物工程学[4]王福林,

报,(1):2006,21153-158.

[5]YeoKeunKim,YongJuKim,YeonghoKim,Geneticalgorithmsforassemblylinebalancingwithvariousobjectives.Computersind.1996.30:397-409.

[6]SerenOzmehmetTasan,Areviewofthecurrentapplicationsofgeneticalgorithmsinassemblylinebalancing.JIntellManuf,2008,19:49-69.

席忠民,陈平和,严运兵.面向高效精准柔性混装作业的智能[7]唐秋华,

元胞调度方法研究[J].武汉科技大学学报(自然科学版)(4):2007.30379-383.


相关范文

  1. 基于遗传算法的装配线平衡_宋华明

    第20卷第1期(总第109期) 系 统 工 程 Vol.20,No.1 2002年1月 SystemsEngineering Jan.,2002 文章编号:1001-4098(2002)01-0087-05 基于遗传算法的装配线平衡 宋华明,韩玉启 (南京理工大学经济管理学院,江苏南京 210094 ...

  2. 混合遗传算法在生产线工艺路线排序中的应用

    2005年10月 农 业机械学报 第36卷第10期 混合遗传算法在生产线工艺路线排序中的应用 王芸凤 于宝证 赵 韩 刘 琼 [摘要] 生产线工艺方案的确定是生产线设计的关键, 在一条生产线中工步.工位数比较多, 其顺序直接影响加工质量和生产效率.在分析生产线工步.工位排序原则的基础上, 基于设备负 ...

  3. 生产线平衡翻译初稿

    本科毕业论文外文翻译 外文译文题目: 对于E类型的简单生产线平衡问题的解决过程 学 院: 专 业: 学 号: 学生姓名: 指导教师: 日 期: 机械自动化 工业工程 20108 谭 李 二○一四年五月 A solution procedure for type E simple assembly l ...

  4. 飞轮储能关键技术及应用发展趋势_朱熀秋

    第1期 2017年1月 机械设计与制造 Machinery Design &Manufacture 265 飞轮储能关键技术及应用发展趋势 朱熀秋,汤延祺 江苏镇江212013)(江苏大学电气信息工程学院, 摘要:飞轮储能作为一种新型的电能储备技术正受到越来越多的关注,它具有储能密度大.充电 ...

  5. 飞机工装制造执行系统的设计与实现

    2121201011飞机工装制造执行系统的设计与实现 南京航空航天大学, 南京, 枣庄学院, 枣庄, 1. 210016 2. 277160 摘要:针对飞机工艺装备制造水平低下㊁ 信息化程度不高的问题, 设计开发了飞机工装制造执行系㊂ 详细介绍了M E 统(重点阐述了基于C M E S -A T ) ...

  6. 机电装配体拆卸序列的自动生成及组合优化探讨

    机电装配体拆卸序列的自动生成及组合优化探讨 [摘要]为深入研究机电装配体拆卸序列的自动生成和优化问题,本文首先建立了装配体的自由-干涉矩阵,并将其作为描述机电装配体结构的数学模型,并在此基础上提出了"拆卸楔"概念和具体算法,依照此法计算机电装配体上各个零件的拆卸序列和方向,最后基 ...

  7. 基于模糊认知图的动态系统的建模与控制

    基于模糊认知图的动态系统的建模与控制 [摘要]模糊认知图简单.直观的图形化表示和快捷的数值推理能力使其在医学.工业过程控制以及环境监测等领域得到了广泛的应用.模糊认知图是模糊逻辑和神经网络相结合的产物, 适用于基于动态数据的非线性系统的描述.预测与控制.由于受到人的经验.知识水平和认知能力的限制, ...

  8. 智能机器人及其发展

    智能机器人及其发展 史琪 (北京信息科技大学 机电工程学院 北京 ) 摘要:智能机器人是一个国家高科技发展水平的重要标志之一,具有广阔的应用前景.本文介绍了机器人的定义和发展阶段,阐述了智能机器人研究领域的关键技术,总结了国内外各类机器人的发展现状并给出相应实例,最后分析并展望了智能机器人今后的发展 ...

  9. 制麦生产车间布局建模方案

    制麦生产车间布局建模方案 摘要 随着经济全球化的发展,制造系统不断发展的同时也对生产线布局提出更高的要求:可重构性.可适应性和系统的不断升级.其布局的优劣对生产物流起到决定性的作用.传统的制麦生产车间布局方法是,利用简单的计算机辅助二维平面设计,或采用现场布置的方法,这样布局方法存在很大问题.而国内 ...