(机械设计及理论专业论文)双边装配线平衡问题的蚁群算法研究.pdf_第1页
(机械设计及理论专业论文)双边装配线平衡问题的蚁群算法研究.pdf_第2页
(机械设计及理论专业论文)双边装配线平衡问题的蚁群算法研究.pdf_第3页
(机械设计及理论专业论文)双边装配线平衡问题的蚁群算法研究.pdf_第4页
(机械设计及理论专业论文)双边装配线平衡问题的蚁群算法研究.pdf_第5页
已阅读5页,还剩64页未读, 继续免费阅读

(机械设计及理论专业论文)双边装配线平衡问题的蚁群算法研究.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

西南交通大学硕士研究生学位论文第1 页 捅要 双边装配线在大型复杂机械产品中应用广泛,较单边装配线而言,具有能缩短装 配线长度,提高工装、夹具等利用率和工人的工作效率等优点,具有重要的研究意义 与实用价值。但双边装配线中任务的操作方位约束与任务优先关系约束,决定其设计 复杂度比单边装配线复杂很多。 在总结双边装配线的研究现状基础上,分析了目前双边装配线研究的不足之处, 并以此制定了本文的几个研究方向。在研究双边装配线问题特征的基础上,提出了双 边装配线的数学模型,在此基础上,分别对双边装配线第一类平衡问题、随机型双边 装配线第一类平衡问题、双边装配线第二类平衡问题、附带复杂区域约束条件的双边 装配线第一类平衡问题进行了深入研究。 针对双边装配线第一类平衡问题,本文首先对三种常见的启发式算法进行了分析, 三种启发式算法分别采用了不同单一启发式搜索规则。通过对三种启发式算法的分析, 下一步研究工作中可借鉴采用优良的启发式规则。针对随机型双边装配线第一类平衡 问题,提出了两种综合启发式算法,两种综合启发式算法均通过综合集成不同的启发 式规则而成,通过算例分析比较了两种方法的优劣性。 提出了一种解决双边装配线第一类平衡问题的一种蚁群算法,算法采用先用蚁群 搜索选择任务,后调用启发式分配规则产生双边装配线具体工位分配方案。对于附带 复杂区域约束条件的双边装配线第一类平衡问题,本文采用禁忌集合满足区域约束中 的排斥性约束,采用优先集合满足区域约束中的相容性约束,并对现有算法进行了对 比分析,具有更优的求解性能。为提高算法的实用性,增加了优化结果的甘特图显示 模块。 对于双边装配线第二类平衡问题,本文同样提出了_ 种蚁群算法,此算法借鉴了 本文所提出的求解含区域约束条件装配线问题蚁群算法的解的构造策略,并采用蚁群 整体搜索规划策略对最小节拍时间进行搜索。并通过一个实例,验证了算法的求解性 能。 最终,通过调研国内某大型汽车厂商的双边装配线,并综合运用本文提出的多种 算法,提出了较优的双边装配线的优化设计方案,表明了本文所做工作的实际意义。 本文得到了高等学校博士学科点专项科研基金资助课题( 2 0 0 8 0 6 1 3 1 0 1 4 ) 的资助。 关键词:双边装配线;随机型;启发式算法;蚁群算法 西南交通大学硕士研究生学位论文第1 1 页 a b s t r a c t t w o s i d e da s s e m b l yl i n e sa g ew i d e l yu s e di nl a r g ea n dc o m p l e xm e c h a n i c a lp r o d u c t s a s s e m b l yl i n e s t h et w o s i d e da s s e m b l yl i n ec a ns h o r t e nt h el e n g t ho ft h ea s s e m b l yl i n ea n d a tt h es a m et i m ei n e a s et h ee f f i c i e n c yo fw o r k e r sa n df i x t u r e sc o m p a r e dt ot h es a m p l e a s s e m b l yl i n e a st h es p e c i a ls t r u c t u r eo ft h et w o - s i d e da s s e m b l yl i n e , s u c h 嬲t h er e s t r i c t i o n o fe a c ht a s k so p e r a t i o nd i r e c t i o n sa n do p e r a t i n gc o n s t r a i n t so ft h es e q u e n c eo ft a s k s ,i ti s m o r ec o m p l e x i t yt od e s i g nat w o - s i d e da s s e m b l yl i n et h a nas a m p l ea s s e m b l yl i n e t h i sa r t i c l ea n a l y s i st h es t a t u sq u oo ft w o s i d e da s s e m b l yl i n e ,t h e nf i n do u tt h e r e s e a r c h i n gd e f e c t si nt o d a y sr e s e a r c hw o r ka n df o r m u l a t et h er e s e a r c hf i e l d a r e rs t u d yt h e c h a r a c t e r i s t i c so ft h et w o - s i d e da s s e m b l yl i n e ,p r o p o s e dan e wm a t h e m a t i c a lm o d e l t h e n m a k eai n - d e p t h s t u d yi nt h ef o l l o w i n gp r o b l e m s :t w o s i d e da s s e m b l yl i n eb a l a n c i n g p r o b l e mo ft y p e - i ,s t o c h a s t i ct w o - s i d e da s s e m b l yl i n eb a l a n c i n gp r o b l e mo ft y p e i , t w o - s i d e da s s e m b l yl i n eb a l a n c i n gp r o b l e mo ft y p e - i i ,t w o s i d e da s s e m b l yl i n eb a l a n c i n g p r o b l e mo ft y p e i 、 ,i n lz o n i n gc o n s t r a i n t s t h i sa r t i c l ef i r s ta n a l y s i sa n a l y s i st h r e eb a s i ch e u r i s t i ca l g o r i t h m sw h i c ha r eb a s e do n o n l yo n ed i f f e r e n th e u r i s t i cr u l ef o rt w o - s i d e da s s e m b l yl i n eb a l a n c i n gp r o b l e mo ft y p e ii n o r d e rt os e l e c tt h ee x c e l l e n th e u r i s t i cm l e sf o rr e f e r e n c ei nt h ef u t u r ew o r k a f t e rt h i sw o r k , p r o p o s e dt w oh y b 硼h e u r i s t i ca l g o r i t h m sf o rs t o c h a s t i ct w o - s i d e da s s e m b l yl i n eb a l a n c i n g p r o b l e mo ft y p e i ,t h e na n a l y s i st h ep e r f o r m a n c eo ft h e s et w oa l g o r i t h m s t h e np r o p o s e da na n t c o l o n ya l g o r i t h m t h a tf o r m u l a t e st h et a s ks e q u e n c eb e f o r e g e n e r a t e sa na n s w e rb yu s i n gt h et a s ka s s i g n m e n tr u l e a f t e rt h a tr e s e a r c h ,d e v e l o p e d a n o t h e ra n tc o l o n yb a s e da l g o r i t h mt os o l v et w o s i d e da s s e m b l yl i n eb a l a n c i n gp r o b l e m 、析t h z o n i n gc o n s t r a i n t s i nt h i ss t u d y , a ni m p r o v e da n t - c o l o n y - b a s e dh e u r i s t i ca l g o r i t h mi s p r o p o s e df o rs o l v i n gt h i sp r o b l e m ai m p r o v e dh y b r i da n t - b a s e ds e a r c hr u l ea n dah e u r i s t i c t a s kd i s t r i b u t i o nr u l ew e r eu s e di no r d e rt oe s t a b l i s haf e a s i b l es o l u t i o nw h i c hi sa l s oi n a c c o r d a n c ew i t ht h ez o n i n gc o n s t r a i n t s t h i sa l g o r i t h mh a sb e t t e rp e r f o r m a n c ec o m p a r e d w i t hv a r i e sa l g o r i t h m sp r o p o s e db yo t h e rr e s e a r c h e r s a n dt h eg a n t tc h a r td i s p l a ym o d u l e w a sa d d e di no r d e rt oe n h a n c ei t s p r a c t i c a b i l i t y t h e n ,t h i sp a p e rp r o p o s e da na n tc o l o n yb a s e da l g o r i t h mf o rt w o - s i d e da s s e m b l yl i n e b a l a n c i n gp r o b l e mo ft y p e - i i ,t h i sa l g o r i t h mi sf o r m u l a t e di nt h ef o u n d a t i o nw o r ko fe a r l i e r p e r i o dr e s e a r c hi nt h i sa r t i c l ea n da l s oc o n t a i n e do t h e rr e s e a r c h e r sv i e w p o i n tw h i c hp l a y s i n f l u e n t i a lr o l ei nf i n d i n gt h eo p t i m i z a t i o nc y c l et i m e t h ea l g o r i t h mi sc o d e di n t oa p r o g r a m b ym a t l a ba n dt h eu s a b l i t yi si n d i c a t e db yap r a c t i c a le x a m p l e f i n a l l y , t h i sp a p e ri n v o l v e sar e a lt w o s i d e da s s e m b l yl i n ei no n eo ft h el a r g e s tc a r m a n u f a c t u r e r si nc h i n a b yu s i n gt h ea l g o r i t h m sp r o p o s e di nt h i sa r t i c l e ,g e n e r a t i n gs e v e r a l i m p r o v i n gp r o p o s a l sa n dt h eu s a b l i t ya r ei n d i c a t e d t h i sr e s e a r c hi ss u p p o r t e db yn a t i o n a lu n i v e r s i t ys p e c i a l i z e dr e s e a r c hf u n df o rt h e d o c t o r a lr e s e a r c ht o p i c s ( 2 0 0 8 0 6 1 3 1 0 1 4 ) k e y w o r d s :t w o 。s i d e da s s e m b l yl i n e :s t o c h a s t i c :h e u r i s t i cm e t h o d :a n tc o l o n ya l g o r i t h m 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 课题的研究意义 装配线线平衡问题是工业工程研究领域的一个重要研究方向,装配线工位的设计、 节拍时间的确定、装配线布局形式的确定是生产线平衡问题中的要点。为工业产品设 计合理的生产线是企业生产制造管理中的重要内容:合理的生产节拍有利于企业对市 场情况的快速响应;合理的工位设计能使企业节约生产资料投入,改善制造系统内物 流状况:合理的装配线整体任务分配能在一定范围内提高生产制造系统可靠性;混合 装配线的应用更能使企业减少固定设施投入,采用同样的装配线生产属于同一产品族 的任一款产品,极大地提高了企业的市场响应能力与制造系统的柔性。 双边装配线平衡问题是生产线平衡问题中的一个分支,双边生产线在大型、复杂 机械产品中广泛运用,如汽车产业、工程机械产业、军工产业。均为关系国家经济命 脉乃至国家安危的重要产业。如何合理的设计布局双边装配线,研究性能优良、能考 虑实际复杂约束条件的双边生产线平衡优化算法是双边生产线研究的核心内容。这不 仅能在和平时期为国家经济产业高效生产、高创外汇服务,有效地为提高国家的整体 经济实力、应付国际竞争服务,更能为保证战争时期高效地生产军工产品、保障高效 率的武器提供潜在支持。 1 2 国内外现状分析 1 2 1 装配线平衡问题及总体研究现状概述 装配线平衡问题按布局形式可分为单边装配线平衡问题( 或称为简单装配线平衡 问题) 、u 型装配线平衡问题以及双边装配线平衡问题三大类。自从世界上第一条装配 线诞生以来,装配线的发展十分迅猛,各种形式的装配线相继而生,装配线的应用形 式也趋向多样化。由于装配线平衡问题属于n p h a r d 型问题,其中,n p 指非确定性多 项式( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 。在n p 型问题中,若此问题能完全转化为一个图论 问题,则该问题可称为n p 困难问题,即n p h a r d 型问题。 较为著名的n p - h a r d 型问题有:旅行商问题:假设一个推销员需要从杭州出发, 经过上海、南京、苏州、镇江、无锡、金华,等刀个长三角城市,最后返回杭州。 任意两个长三角城市之间都有动车通行,票价与所用时间不等,问是否存在一种推销 路线方案,能经过所有的长三角城市,并且所用的旅行总费用最少,或者旅行所用的 总时间最少。在所有刀个长三角城市组成的所有旅行方案中找出一个最优方案,是十 西南交通大学硕士研究生学位论文第2 页 分困难的。若做最坏的打算,则需要将所有可能地旅行路线都核算一遍,将耗费很多 精力与时间。到目前为止,此类问题还未有一个有效算法,特别是当此类问题的规模 增大时,其计算复杂度将及几何倍数增加,若采用精确解法求解,难以在合理时间内 得出较优方案。因此,往往采用启发式求解算法或者目前流行的融入生物智能技术的 亚启发式算法。 装配线平衡问题较旅行商问题更为复杂,由于装配任务之间的任务优先关系约束, 是一个有向的图论问题,而且装配任务只能且必须出现一次,使得每当生成一组可行 方案时将耗费更多的时间;而且,在一条装配线中,分为若干个工作站( - r 位) ,由于产 品的投产节拍时间限制,每个工作站( 7 - 位) 的总累积操作时间不得超过产品的生产节拍 时间,使得在可行解的生成过程中增加了更多的条件判断过程,更增加了问题的求解 复杂性。 装配线平衡问题起源于对单边型或称简单型装配线平衡问题的研究。装配线平衡 的目的在于使各个工位( 工作站) 的累积操作时间趋向相等,以避免工位( 工作站) 之间的 累积操作时间的差异造成某些工位在制品堆积,而某些工位却出现等待加工的现象, 当平衡各个工位的累计操作时间后,整个装配线的设备利用率,人员安排合理性将显 著增加,从而提高生产率和人员的使用效率。单边装配线的研究目前主要集中于以下 几个领域: 1 ) 单边装配线第一类平衡问题的研究,即确定生产节拍,求最小化开启位置数目; 2 ) 单边装配线第二类平衡问题研究,即确定开启位置数目,求最小化节拍时间; 3 ) 随机单边装配线平衡问题的研究,即假设操作时间为随机变量,综合考虑单边 装配线可靠性、平衡率等因素的,并进行优化研究; 4 ) 多种复杂约束条件下的单边装配线平衡问题研究,l i p 3 n 入了区域约束条件( 任务 之间的相关性约束) 、疲劳作业因素( 考虑工位内部的工人操作强度) ,使得优化 结果更能贴近生产实际情况; 5 ) 混合型单边装配线平衡问题的研究,通过对产品族中各产品的任务优先关系约 束的归一化,从整体上考虑整个生产装配线的平衡效果。 单边装配线优化问题的求解途径目前有以下几种【1 】: 1 ) 精确解法:早期对单边装配线平衡问题的优化方法研究中,曾尝试使用精确解 法来求解,如线性规划( 1 i n e a rp r o g r a m m i n g ) 【2 。】、整数规划( i n t e g e r p r o g r a m m i n g ) t 4 1 、动态规翅j ( d y n a m i cp r o g r a m m i n g ) t 5 7 】和分枝定界法( b r a n c ha n d b o u n d ) t s q o 等。线性规划在各种优化问题中应用广泛,它采用线性方程组和线性 不等式来描述优化问题的约束条件。但对于装配线平衡问题这种非确定性多项 式难题,解决问题的难度随着问题的规模呈几何性的爆炸增长,难以在合理时 间内得出精确最优解。分枝定界法的求解效果与所采用的启发式评价函数及截 西南交通大学硕士研究生学位论文第3 页 枝规则有关,通常首先界定问题的最优解判定标准,判定标准的准确性对问题 的求解时间影响较大,同时,求解时间也受着问题规模的较大影响,受着“组合 爆炸”问题的困扰。 2 ) 启发式算法:根据t a l b o t u l 】对启发式方法的分类,启发式方法分为以下类别: 简单规则( 只采用单一规则进行决策) 、复合规则( 采用多个规则进行综合决策) 、 回溯决策规则( 前序决策对当前决策具有影响) 、以及寻优决策规则( 一种整体的 搜索规划策略) ,并据此细分出1 3 条简单启发式规则。s c h o l l 在其基础之上进一 步研究,总结细分出了1 6 条静态优先规则【1 2 1 。在实际问题求解中,应用较为广 泛的启发式算法有凯尔布里奇和韦斯特方法( k i l b r i d g ca n d w e s t e rh e u r i s t i c ) 1 3 】、 霍夫曼提出的矩阵法( h o f f r n a np r e c e d e n c em a t r i xm e t h o d ) t 1 4 1 、m o o d i e - y o u n g 提 出的两阶段启发式方法习、以及赫尔森和伯尼的位置权重法( p o s i t i o n a lw e i g h t m e t h o d ) t 1 6 】和分级指派法( r a n l 【a n da s s i g nh e u r i s t i c ) 1 7 】等。启发式方法求解较为 快速便捷,但不存在具备普适性的启发式规则。对于简单的优化问题,能较快 得到优化结果,但是对于附加各种约束条件的复杂问题求解时,往往无能为力, 更主要的是,往往难以找到最优解。 3 ) 亚启发式算法( 智能优化算法) :许多学者通过观察自然界中的物理、生物现象, 提出了一批新颖的优化算法,如遗传算法( g e n e t i ca l g o r i t h m ,g a ) b s 】、模拟退 火算法( s i m u l a t e da n n e a l i n g ,s a ) 【1 9 1 、禁忌搜索算法( t a b us e a r c h ,t s ) 2 0 】、蚁群 优化算法( a n tc o l o n yo p t i m i z a t i o n ,a c o ) 2 1 】、粒子群优化算法( p a r t i c l es w a r m o p t i m i z a t i o n ,p s o ) 2 2 】等。这些优化算法通过模仿自然界中的一些内在机制和客 观规律,并应用于优化问题的求解过程中,以期求得较优解或最优解。但是, 应用这些优化算法解决具体问题时,一般须考虑实际问题的本身特征,根据具 体问题的内在机理制定相应合理的搜索机制与问题描述机制,以保证所得优化 结果的可行性。 单边装配线平衡问题的研究一直较为热门,相对于单边装配线平衡问题,双边装 配线问题受到的关注较少。目前,由于我国大型复杂机械产品的生产装配线渐渐增多, 双边装配线开始受到越来越多的关注。许多针对双边装配线的研究思路均来自单边装 配线的研究经验和研究路线。目前,对双边装配线问题的研究主要集中于以下几个领 域: 1 ) 双边装配线第一类平衡问题的研究,即确定生产节拍,求最小化开启位置数目; 2 ) 双边装配线第二类平衡问题研究,即确定开启位置数目,求最小化节拍时间; 3 ) 随机双边装配线平衡问题的研究,即假设操作时间为随机变量,以此进行优化 研究,得到综合考虑双边装配线可靠性、平衡率等因素的优化结果: 4 ) 多种复杂约束条件下的双边装配线平衡问题研究,即加入了区域约束条件、成 西南交通大学硕士研究生学位论文第4 页 对组合操作条件等任务之间的相关性约束,使得优化结果更能贴近生产实际情 况,得到可直接应用的双边装配线优化方案: 5 ) 混合模型双边装配线的研究,即考虑以生产同一产品系列的双边装配线为研究 目标,等。 目前对此问题的研究多采用启发式方法和多种亚启发式方法,研究的模型从只考 虑操作方位约束、任务优先关系约束等基本约束双边数学模型拓宽到同时考虑任务相 关性约束、操作随机性约束等附加约束条件的复杂数学模型上来。 1 2 2 国内外研究现状 1 9 9 3 年,b a r t h o l d i 2 3 】首次提出了双边装配线平衡问题的概念,在其论文中阐述了 双边装配线相对于单边装配线的优点,同时分析了双边装配线任务分配时的复杂性。 并提出一种基于f i r s tf i tr u l e ( f f r ) 启发式规则算法,帮助车间调度计划人员进行装配 任务的生产组织与规划。 2 0 0 0 年,k i m 2 4 的团队提出了一种基于“工位”编码方式的双边装配线遗传算法, 用于解决双边装配线第一类平衡问题。此算法采用基于“工位”的编码方式,采用改进 的位置权重法( r a n k e dp o s i t i o n a lw e i g h t , r p w ) 的“关键阶位权法”( c r i t i c a l l yr a n k e d p o s i t i o n a lw 萌g h t ,c r y w ) 的来对染色体进行解码工作,并调用重分配策略调整遗传过 程中某些染色体中出现的违反任务优先关系约束的现象。 2 0 0 1 年,l e e 等【2 5 】以提高双边装配线中任务操作中的连续性和降低左右工位之间 所分配任务的关联性为优化目标,提出了一种基于a g r a w a l 的“最大集规则”( l a r g e s t s o t r u l e ,l s r ) 的任务归组分配规则,以提高任务之间的操作连续性;同时采用多个启发式 规则,降低左右工位任务之间的相关度。实验表明,此算法往往会增加双边装配线的 所需开启工位数量。 2 0 0 5 年,秦杏敏掣2 6 】将经典的位置权l _ 法( r a n k o dp o s i t i o n a lw 西g h t ,r p w ) 算法应 用到双边装配线第一类问题的求解当中,提出了双边装配线的位置权重算法( r a n k e d p o s i t i o n a lw e i g h tf o rt w o - s i d e da s s e m b l yl i n eb a l a n c i n g ,t r p w ) 在任务的分配过程中,作 者考虑了平衡双边所分配任务操作时间均衡的思想,以期望得到降低可开启工位数量 的目的。 2 0 0 7 年,吴尔飞掣2 7 】提出一种基于任务排列序列的遗传算法求解双边装配线第一 类平衡问题,并提出了相应的解码策略,为保证经过交叉变异过程之后,仍能生成满 足任务优先关系约束条件的染色体,提出了重分配策略。经过多组算例实验,此算法 具有比t r p w 算法和f f r 算法更优的求解性能。 同年,吴尔飞等【2 剐提出一种求解双边装配线第一类平衡问题的启发式算法,采用 最大化e 型任务的调节作用的启发式规则来进行双边装配线任务在工位中的分配。此 西南交通大学硕士研究生学位论文第5 页 算法具有优于多种常见启发式算法的求解性能。 同时,在2 0 0 7 年,吴尔飞等【2 9 1 提出了求解双边装配线第一类平衡问题的一种分枝 定界精确解法。提出了一种求解最小开启工位数目的方法,来界定搜索过程中得到的 解是否已经达到最优解标准,以期望缩短搜索时间。采用多种启发式规则来进行分枝 过程中的搜索方向选择,以期望更快的得到最优解。 2 0 0 8 年,b a y k a s o g l u 和d e r e l i t 3 0 1 首次将蚁群搜索算法应用到双边装配线第一类平 衡问题的求解当中。并同时首次引入了区域约束条件,针对双边装配线任务分配的特 征,同时考虑了复杂的区域约束。全面的考虑了不同任务操作之间的相关性条件与排 斥性条件,使得所得优化结果能更加贴近生产实际情况。为双边装配线平衡问题的研 究开辟了新的分支。 同年,侯东亮【3 l 】针对某实际双边装配线改善问题,采用工业工程“5 w l h ”分析方法 并运用“e c r s ”四大操作方法对瓶颈工位进行改进,通过对比改进前后双边装配线的实 际效率,说明了改进途径的可行性。 可见,在之前的研究当中,较多地采用遗传算法与传统的启发式算法,但遗传算 法需经过交叉、变异等过程,算法的复杂度高;而传统的启发式算法求解性能一般。 同时发现,具备优良求解性能的蚁群算法开始被引入到双边装配线平衡问题的求解当 中。进入2 0 0 9 年之后,双边装配线的研究进展开始加速,许多学者借鉴单边装配线的 研究思路,产生许多新的想法,同时提出并引入了更多的启发式和亚启发式算法到双 边装配线的研究领域中: 2 0 0 9 年,u g u r6 z e a n 等【3 2 】将禁忌搜索算法( t s a ) 引入到双边装配线第一类平衡问 题的优化中,并同时考虑了生产线的平衡率指标和平滑系数指标。此算法采用基于选 择权值的方式来决定任务的分配优先权,同时,采用交换任务之间选择权值的方式来 产生一个领域解。 同年,u g u r6 z c a n 等【3 3 】开始研究双边装配线平衡问题的多目标优化方法,提出了 双边装配线的完整的数学模型,建立了多目标优化目标函数。并采用成熟的线性规划 算法来求解此类问题,对考虑区域约束条件的双边装配线多目标优化问题进行了首次 研究。 同年,u g u r6 z c 觚等【蚓开始研究混合型双边装配线的第一类平衡问题,在提出完 整的数学模型的基础上,提出了混合型双边装配线的多目标优化评价函数。采用基于 选择权值的禁忌搜索算法求解问题,开辟了双边装配线平衡问题研究的新方向。 2 0 0 9 年,s i m a r i a 等【3 5 】提出一种采用两队蚂蚁共同构造可行解的蚁群算法求解双边 装配线第一类平衡问题,但仅仅考虑了区域约束条件中的相斥性约束条件,对比l e e 的启发式算法,具有相对较优的求解效果。 同年,k i m 3 6 】的研究团队再次采用基于“工位”编码方式的遗传算法运用于求解双边 西南交通大学硕士研究生学位论文第6 页 装配线平衡问题,在未考虑区域约束条件的情况下,同时采用单种群和多种群遗传算 法来求解双边装配线第二类平衡问题,对比传统的f f r 启发式算法,具有较好的性能。 2 0 1 0 年,u g u r6 z e a n 掣了7 】开始对随机型双边装配线平衡问题进行开创性研究,在 首次建立随机型双边装配线平衡问题数学模型的基础上,分别提出了数学规划方法和 模拟退火算法来求解此类问题,提出的模拟退火算法采用基于任务选择权值的交换策 略来产生领域解。通过算例对比,表明模拟退火算法具有更优的求解性能。 2 0 1 0 年,l a l eo z b a k i r 与p i n a rt a p k a n 3 8 】首次采用蜜蜂搜索算法来求解多目标双边 装配线平衡问题,通过多组算例实验,具有较好的求解效果。 可见在2 0 0 9 年以后,在双边装配线的研究当中,开始了混合型、多目标、随机型 双边装配线平衡问题的研究,但求解问题的方法多采用传统但性能稳定的算法。性能 优良的蚁群算法还未在以上问题求解过程中广泛应用。 综上所述,目前国内外双边装配线研究领域中,对于第一类平衡问题的研究较多, 对第二类平衡问题的研究较少;对单一品种双边装配线的研究较多,对混合品种装配 线的研究较少;对任务操作时间为确定的双边装配线平衡问题研究较多,对任务操作 时间为随机型的双边装配线平衡问题研究较少;对仅含双边装配线基本约束条件的平 衡问题研究较多,对包含复杂区域约束条件的双边装配线平衡问题研究较少。解决问 题的算法也多为传统的启发式算法与线性规划方法、性能稳定但算法复杂度高的遗传 算法等亚启发式算法,性能优良的蚁群算法随也有涉及,但从求解性能来看,并未充 分发挥出蚁群算法的优势。 针对当前双边装配线平衡问题研究领域的以上问题,本文将对随机型双边装配线 平衡问题、双边装配线第二类平衡问题、包含复杂区域约束条件的双边装配线平衡问 题分别进行进一步研究。 针对目前双边装配线平衡问题研究中,还未有涉及优化结果的图像界面显示这一 现状,本文引入生产调度研究领域中的甘特图生成显示技术,简明直白地显示优化解 所隐含的双边装配线中各个任务在其工位中的操作时间先后进度。能为生产实际提供 有利的参考。 1 3 课题研究目标、研究内容、解决的关键问题 1 ) 课题研究目标 ( 1 ) 首先研究双边装配线问题的机理,提出相应的数学模型。针对双边装配线第一 类平衡问题实现并验证三种启发式算法。在此基础上进行启发式规则的综合运用,针 对随机双边装配线第一类平衡问题提出有效的综合启发式算法。 ( 2 ) 对双边装配线第一类平衡问题提出一种性能较高的蚁群算法,并考虑解决附带 区域约束条件的双边装配线第一类平衡问题,提出一种改进蚁群算法。 西南交通大学硕士研究生学位论文第7 页 。皇奠皇墨鼍量皇量舅邑曼曼曼曼量曼曼皇量量量鲁皇皇曼量鼍量量曼皇皇曼曼曼曼皇鼍皇曼曼曼量量曼曼量皇舅舅量曩_ 量量量量量曼量皇量鲁鼍鼍曼皇皇量曼皇皇_ ( 3 ) 针对双边装配线第二类平衡问题提出有效的蚁群算法。 2 ) 研究内容 ( 1 ) 研究双边装配线第一类平衡问题的启发式算法。通过对单边装配线研究领域常 用启发式算法的归类总结,提出并且实现了三种常见的双边装配线启发式算法,分析 了三种算法的性能。 ( 2 ) 研究双边装配线第一类平衡问题的蚁群算法。在对三种启发式算法进行研究的 基础上,将性能稳定的位置权重规则引入蚁群综合搜索规则,提出一种性能优良的蚁 群算法。 ( 3 ) 研究随机双边装配线第一类平衡问题的启发式算法。在研究操作时间为确定型 的双边装配线第一类平衡问题的基础上,同时考虑随机性双边装配线的特征,提出两 种采用多种启发式规则相结合的综合启发式算法。 ( 4 ) 研究双边装配线第二类平衡问题的蚁群算法。研究双边装配线第二类平衡问题 的问题特征基础上,将适用于第一类平衡问题的蚁群算法进行改进,引入蚁群综合搜 索规划策略,以适应第二类平衡问题的特性,并采用某实例进行验证。 ( 5 ) 研究双边装配线第一类平衡问题附加区域约束条件的蚁群算法。结合附加区域 约束条件的双边装配线第一类平衡问题的问题特征,对原蚁群算法进行分析,确定蚁 群信息素搜索过程作为改进目标,以保证生成同时满足区域约束条件的可行解。 3 ) 解决的关键问题 ( 1 ) 引入目前装配线平衡问题研究中常见的三种启发式规则,提出三种针对双边装 配线第一类平衡问题的启发式算法。在算法的制定过程中,启发式规则体现于对可选 任务集合中任务的选择过程:对于位置权重启发式规则,须计算可选任务集合中每个 任务的位置权重系数,而位置权重系数的计算需采用树的遍历搜索技术,同时考虑最 多后续任务及后续任务的操作时间以及任务之间的优先顺序关系,是一个较为复杂的 算法过程;对于最早开始加工时间优先规则,须计算可选任务集合中每个任务的最早 可开始操作时间,而任务最早可开始操作时间的计算受紧前任务的分配以及任务本身 操作方位属性约束,其算法制定过程也较为复杂;最大加工时间优先规则的任务选择 过程则相对简单,但三种启发式算法的任务分配过程都较单边装配线平衡问题更为复 杂,因此,还须同时提出合适的任务分配规则。 ( 2 ) 针对目前随机型双边装配线的研究现状,提出两种新的综合启发式求解算法。 两种综合搜索算法均同时采用多种启发式规则,在对可选任务集合进行任务筛选时, 先后采用多种规则,每种规则的应用都须对候选集合中的任务重新计算选择权值。因 此,对于两种综合启发式算法,均须制定一个不同启发式规则的选用流程与算法细则, 之后采用任务分配规则形成具体的双边工位任务分配方案。 ( 3 ) 针对双边装配线第一类平衡问题,提出一种蚁群信息素搜索与任务分配过程相 西南交通大学硕士研究生学位论文第8 页 结合的蚁群算法。在考虑双边装配线平衡问题任务分配过程的复杂性基础上,针对任 务选择过程制定蚁群综合信息素搜索方法,并同时考虑局部信息素更新与全局信息素 更新,在任务分配过程中,采用多种启发式规则生成可行的任务分配方案。在此算法 基础上,针对同时考虑区域约束条件的双边装配线第一类平衡问题,对原算法的蚁群 信息素搜索过程进行改进,提出一种能有效解决区域约束条件的蚁群算法。针对目前 双边装配线研究中较少涉及的第二类平衡问题,提出一种蚁群搜索算法,采用一个实 例验证了此算法的有效性。并同时加入了分配方案的甘特图显示模块。 1 4 采取的研究方法、技术路线 1 ) 研究方法: 本文主要采用智能搜索算法求解双边装配线平衡问题,通过对装配线平衡问题不 同分枝的问题特性,主要采用蚁群算法来求解。 针对双边装配线第一类平衡问题,首先分析比较了三种常见的启发式算法的求解 性能,为下一步选择合适的启发式规则提供参考。针对目前研究较少的随机型双边装 配线第一类平衡问题,采用两种综合启发式算法求解,两种启发式算法均采用较为合 理的启发式规则综合而成。 对于双边装配线第一类平衡问题,本文重点研究了蚁群算法,提出了一种蚁群搜 索与任务分配过程相结合的蚁群算法。对考虑区域约束条件的第一类平衡问题,对原 蚁群算法进行改进,提出一种改进蚁群算法。 针对双边装配线第二类平衡问题,通过借鉴之前本文提出的求解附带区域约束双 边装配线第一类平衡问题蚁群算法的解的构造策略,并采用可行的蚁群整体搜索规划 策略,提出了一种改进蚁群算法。 通过研究了优化结果的甘特图显示技术,为程序增加了甘特图的显示模块,增加 了算法的适用性能。 2 ) 技术路线: 本文通过从研究相对简单的双边装配线平衡问题的启发式算法入手,步步深入, 进一步研究采用综合启发式规则的启发式算法。 之后针对双边装配线第一类平衡问题,提出了一种求解效率较高的蚁群算法,在 下一步求解附带区域约束问题双边装配线平衡问题中,一种改进后的蚁群算法来满足 问题的条件。并寻求加入甘特图的显示模块。 针对双边装配线第二类平衡问题,提出了一种蚁群算法。图1 1 为本文研究的技 术路线图。 西南交通大学硕士研究生学位论文第9 页 :三种单一规则启发式算法 两种综合规则启发式算法 。、位置权重优先启发式算法: 最早开始时间优先启发式算法 最大加工时间优先启发式算法 最早开始时间主要规则启发式算 图1 1 本文的研究技术路线图 1 5 创新性 本课题具有以下创新点: 1 ) 研究双边装配线的问题特征基础上,提出一种新的数学模型。在此基础上,针 对随机型双边装配线第一类平衡问题,提出了两种新的综合启发式求解算法。 2 ) 针对双边装配线第一类平衡问题,提出一种求解性能高效的蚁群算法。对考虑 区域约束条件的双边装配线平衡问题,提出了一种新型的蚁群算法。并首次将甘特图 显示模块引入装配线平衡研究领域,使得优化结果更易于投入生产实际。 3 ) 采用蚁群算法解决双边装配线第二类平衡问题。 1 6 论文结构和主要内容 论文的整体研究思路为,首先明确所研究课题的意义,制定研究目标,然后首先 提出所研究问题的数学模型,之后的研究路线为: 1 ) 所解决的问题从基本的双边装配线第一类平衡问题_ 基本的随机型双边装配 西南交通大学硕士研究生学位论文第1 0 页 线第一类平衡问题_ 带复杂约束条件的双边装配线第一类平衡问题一基本的双边装配 线第二类平衡问题。 2 ) 所采用的解决算法:从基本的单一规则的启发式算法一综合规则的启发式求解 算法一亚启发式求解算法( 人工智能算法) 。在解决的具体问题时,同时引入其他学者提 出的其他智能优化算法求解效果进行对比。 本文的主要研究结构如图1 2 所示,图中并未表明第一章和第二章的内容。 研究问题解决途径 论文章节 图1 2 论文主要研究结构 西南交通大学硕士研究生学位论文第1 1 页 第2 章双边装配线的概念和数学模型 2 1 双边装配线的概念 2 1 1 双边装配线问题的定义 双边装配线的左右两边都可进行装配任务,在整条装配线中,按节拍时间的限制将 整条装配线分割成p 个开启的位置,每个位置由两个相对的工位组成。在双边装配线 中,在同一个位置的两个工位之间,某些无优先关系约束的装配任务可同时进行装配。 被装配产品以节拍时间为时间间隔进入在装配线,并依次完成各个位置的所有装配任 务,装配线末端位置也以节拍时间为时间间隔移出完工产品。 双边装配线的简化模型如图2 1 所示,在一条传送装置中,含有p 个位置及2 物个 工位;属于同一位置的两个工位称为成对工位( m a t e - s t a t i o n ) ,其中一个工位可称为另一 个工位的伴随工位( c o m p a n i o n ) 。 工位1工位3 。 i 工位( 2 p - 3 ) i 工位( 2 p 一1 ) l 位置1 日位置2 传送装置位置( p 1 ) 固位置p 工位2 l 工位4 l l 工位2 p - 1 ) l 工位印i 图2 - 1 双边装配线 在一个基本的双边装配线问题定义中,包含以下基本要素: 1 ) 作业任务( t a s k ) ,或称作业元素、任务。作业任务是双边装配线平衡问题研究的 最小单元,不同任务之间的组合构成双边问题的一个可行解。每个任务可由一个或多 个动作组合而成,以完成一项具体装配工作。 2 ) 任务时间( t a s k t i m e ) 。任务时间指完成一项任务所需要的标准时间,对于人工装 配线,可采用动作时间分析法测定,对于自动化装配线,为定值。 3 ) 操作方位约束( o p e r a t i n g d i r e c t i o nc o n s t r a i n t ) 。在双边装配线中,每个任务都具 有一个操作方位约束,为左边) 、右边( 尺) 、或两边。操作方位约束为三型的任务 必须分配到某一位置的左边工位中;同理,r 型任务必须处于右边工位:而e 型任务 可分配到任意一边工位。 4 ) 位置( p o s i t i o n ) ;工位,或称工作站( s t a t i o n ) 。在双边装配线中,两个相对的工位 组成一个位置,在一个位置的两边放置着完成属于此位置内装配任务的相关设备、工 具、零件等。产品在此位置中停止移动,依次完成相关装配任务;或者产品在此位置 内缓慢移动,依次经过完成各装配任务的设备,并进入下一个位置。 西南交通大学硕士研究生学位论文第1 2 页 5 ) 生产节拍( c y c l et i m e ) 。生产节拍为相邻两个产品进入装配线的时间间隔。生产 节拍并不等同于产品的总加工时间,若将产品在装配线中的等待与空闲时间也包括在 内,则产品的生产时间可视为产品从进入装配线到移出装配线所经历的总时间。在装 配线中,生产节拍一般稍大于此装配线的瓶颈位置所需总时间。 6 ) 工位操作时间( s t a t i o

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论