资源描述:
《基于可行作业序列的遗传算法求解第二类装配线平衡问题》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、第39卷第7期上海交通大学学报Vol.39No.72005年7月JOURNALOFSHANGHAIJIAOTONGUNIVERSITYJul.2005文章编号:1006-2467(2005)07-1123-05基于可行作业序列的遗传算法求解第二类装配线平衡问题皮兴忠,范秀敏,严隽琪(上海交通大学计算机集成制造研究所,上海200030)摘要:从作业顺序图出发,定义了作业的序关系.以此为基础,分析了工位数固定时作业序列与最小节拍的对应关系,并针对第二类装配线平衡问题,提出一种基于可行作业序列的遗传算法.该算法直接依据作业顺序
2、图生成初始群体,并构造交叉和变异算子;初始群体和交叉变异的结果都是可行解,从而保证只在可行作业序列子空间中进行最优解搜索,效率较高;在染色体的适应值定义中还考虑了最小节拍时间和工位工时标准差的综合影响,可用来比较最小节拍时间相同的不同作业分配方案间优劣,提高了解的可信度.应用该算法,对一实例进行了多种工位数的验证,结果较优.关键词:装配线平衡;遗传算法;单元作业;可行作业序列中图分类号:TH391.9文献标识码:AApplyingtheGeneticAlgorithmBasedonFeasibleTaskSequence
3、toALB2PIXing-zhong,FANXiu-min,YANJun-qi(Inst.ofComputerIntegratedManufacturing,ShanghaiJiaotongUniv.,Shanghai200030,China)Abstract:Accordingtotasksequencediagram,thispaperdefinedsequenceoperationsbetweendifferenttasks.Andtherelationshipbetweenthetasksequenceandth
4、eminimalcycletimewaspresentedwhileworkplacenumberisgiven.Thenageneticalgorithmbasedonfeasibletasksequencewasdevelopedforthesecondtypeofassemblylinebalancing(ALB2)problem.Theinitialpopulation,crossoveroperatorandmutationoperatorinthealgorithmareallconstructedfromt
5、hetasksequencediagram.Allsolutionsintheinitialpopulationorresultsofcrossoverandmutationoperationsarefeasible.Forthealgorithmonlyhuntstheoptimalsolutioninthesubspaceoffeasiblesolutions,itishighefficient.Atthesametime,ittookintoaccountthemixedeffectofminimalcycleti
6、meandthestandarddeviationofworkplaces'timetocomparedifferenttaskdistributionsolutions,eveniftheirminimalcycletimeisequal.Sotheresultwillbemorecredible.Atlastacasestudywasgivenforthealgorithm,andtheresultissatisfactory.Keywords:assemblylinebalancing(ALB);genetical
7、gorithm(GA);elementtask;feasibletasksequence对装配线,决定如何将单元作业分配到工位的相等,以减少总的闲置时间,提高整条装配线的效过程就是装配线平衡(AssemblyLineBalancing,率.ALB问题由于其求解目标不同,可分为两类.第ALB).ALB的目的就是尽量使各工位的作业时间一类(ALB1)是给定节拍时间(CycleTime,CT),求收稿日期:2004-07-11作者简介:皮兴忠(1974-),男,博士生,主要研究方向为虚拟制造、虚拟现实.范秀敏(联系人),女,教
8、授,博士生导师,电话(Tel.):021-62933777;E-mail:xmfan@sjtu.edu.cn.1124上海交通大学学报第39卷最小工位数;第二类(ALB2)是给定工位数,求最小节拍时间.由于产品种类数不同,又可分为单品种ALB和混合ALB.本文主要讨论单品种ALB2.ALB是一个组合优化问题.它是典型