（机械工程专业论文）多目标拆卸线平衡问题的群集智能优化算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着生产者责任延伸制的推行、各国新的更多的环境立法的建立以及公众环境意 识的提高，制造商开始回收和再制造废旧的产品。此外，重新使用废旧产品所带来的 经济吸引力也从另一个层面推动了更多制造商的投入。拆卸是重新使用、制造、回收、 存储以及合理处理产品关键的第一步，拆卸线是实现大规模拆卸的最佳选择，因而有 效设计和平衡拆卸线对提高拆卸效率至关重要，因此研究拆卸线平衡问题具有重要的 理论和实际意义。 结合拆卸线的特点，提出了多目标拆卸线平衡问题的数学模型，其优化目标为最 小化工作站数、均衡各工作站空闲时间，并考虑拆卸产品部件的危害、需求以及方向。 在此基础上，采用两种群集智能优化算法一粒子群算法和蚁群算法研究了多目标拆卸 线平衡问题。 提出了一种目标基于优先排序的粒子群算法，该算法采用随机数生成粒子的位置 和速度，而位置和速度的更新则为对应随机数相加减，进而把位置的随机数作为选择 零件的权重，从而根据权重的大小来选择拆卸的零件。并通过具体的实例以及基准例 子验证了算法的有效性。 提出了一种基于p a r e t o 的粒子群算法来求解多目标拆卸线平衡问题，该算法采用 小生境技术选取多目标的全局最优解，采用p a r e t o 占优以及分散度作为个体评价以及 局部最优解选取，最后通过具体的实例以及基准例子验证了算法的有效性。 提出了一种目标基于优先排序的蚁群算法来求解多目标拆卸线平衡问题，该算法 考虑了以零件拆卸时间、危害以及需求三种规则的启发式信息，并综合考虑利用先验 知识、探索新路径、随机选择三种方式的混合搜索机制，有效的提高了算法的搜索效 率，并通过具体的实例以及基准例子验证了算法的有效性。 关键词：拆卸线平衡问题；多目标；蚁群算法；粒子群算法；p a r e t o 西南交通大学硕士研究生学位论文第| | 页 a b s t r a c t t h ee s t a b l i s h m e n to fe x t e n d e dm a n u f a c t u r e rr e s p o n s i b i l i t ya l o n g 、加也n e w , m o r er i g i d e n v i r o n m e n t a ll e g i s l a t i o na n di n c r e a s e dp u b l i ca w a r e n e s sh a sc a u s e da l li n c r e a s i n gn u m b e r o fm a n u f a c t u r e r st ob e g i nr e c y c l i n ga n dr e m a n u f a c t u r m gt h e i rp o s t - c o n s u m e dp r o d u c t s i n a d d i t i o n ，t h ee c o n o m i ca t t r a c t i v e n e s so fr e u s i n gp r o d u c t si n s t e a do fd i s p o s i n go ft h e mh a s f u r t h e rd r i v e dt h i se f f o r t t h ef i r s tk e ys t e po fp r o d u c tr e u s e ，r e c y c l i n g ，r e m a n u f a c t u r i n g ， s t o r a g ea n dr e a s o n a b l yp r o c e s s i n gp r o d u c ti sd i s a s s e m b l yd i s a s s e m b l yl i n ei st h eb e s t c h o i c ef o ra u t o m a t e dd i s a s s e m b l yo fr e t u r n e dp r o d u c t s ，i ti st h e r e f o r eo fi m p o r t a n c et h a ti t b ed e s i g n e da n db a l a n c e dt ow o r ke f f i c i e n t l y s or e s e a r c ho dd i s a s s e m b l yl i n eb a l a n c i n g p r o b l e mh a si m p o r t a n tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e c o m b i n i n gc h a r a c t e r i s t i c so fd i s a s s e m b l yl i n e ，am a t h e m a t i c a lm o d e lw a se s t a b l i s h w i t ho p t i m i z a t i o no b j e c t i v e so fm i n i m i z i n gt h en u m b e ro fw o r k s t a t i o n s ，m a k ef r e et i m e e q u a la sf a ra sp o s s i b l e ，a tt h es a m et i m ec o n s i d e r i n gt h eh a z a r d ，d e m a n da n dd i r e c t i o no f c o m p o n e n t so f r e t u r n e dp r o d u c t s ，t h e nt w ok i n d so fs w a r mi n t e l l i g e n to p t i m i z a t i o na l g o r i t h m ， p a r t i c l e s w a r l t l o p t i m i z a t i o na l g o r i t h m a n da n tc o l o n y a l g o r i t h m i su s e dt o s t u d yt h e m u l t i o b j e c t i v er e m o v el i n eb a l a n c ep r o b l e m a p a r t i c l e s w a r m a l g o r i t h m b a s e do n o b j e c t i v ep r i o r i t i z e w a s d e v e l o p e d f o r m u l t i o b j e c t i v ed i s a 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 ea l g o r i t h mg e n e r a t e dt h ep a r t i c l e s p o s i t i o na n ds p e e db a s e do nr a n d o mn u m b e r , a n dt h ep o s i t i o na n ds p e e di su p d a t e db y c o r r e s p o n d i n gr a n d o mn u m b e rt oa d da n ds u b t r a c t ，t h e nt h er a n d o mn u m b e ro ft h ep o s i t i o n a st h ew e i g h to fp a r t si su s e dt oc h o o s er e m o v ep a r t s f i n a l l y , e x a m p l ev e r i f i c a t i o ni sc a r r i e d o u t ，a n dw h i c hi n d i c a t e st h ev a l i d i t yo f t h ep r o p o s e da l g o r i t h m a p a r t i c l e s w a r ma l g o r i t h mb a s e do np a r e t ow a s d e v e l o p e d f o rm u l t i o b j e c t i v e d i s a s s e m b l yl i n eb a l a n c i n gp r o b l e m i nt h i sa l g o r i t h m n i c h et e c h n o l o g yw a su s e dt og u i d e a n tt os e a r c ht h eg l o b a lo p t i m a ls o l u t i o n p a r e t od o m i n a n ta n dd i s p e r s i o nd e g r e ew a sa p p l i e d t oe v a l u a t et h ea n ta n ds e l e c t i o no fl o c a lo p t i m u ms o l u t i o n f i n a l l y , e x a m p l ev e r i f i c a t i o ni s c a r r i e do u t ，a n dw h i c hi n d i c a t e st h ev a l i d i t yo ft h ep r o p o s e da l g o r i t h m a na n tc o l o n yo p t i m i z a t i o na l g o r i t h mb a s e do no b j e c t i v ep r i o r i t i z ew a sd e v e l o p e df o r m u l t i - o b j e c t i v ed i s a s s e m b l y l i n e b a l a n c i n gp r o b l e m t h e h e u r i s t i ci n f o r m a t i o n c o l l a b o r a t i v e l yc o n s i d e r st h er e m o v et i m e ，t h eh a r ma n dt h ed e m a n do fp a r t s ，ah y b r i ds e a r c h m e c h a n i s mb yc o n s i d e r i n gu t i l i z i n gp r i o rk n o w l e d g e ，e x p l o r i n gn e wp a t h ，r a n d o ms e l e c t i o n m o d e sc o m p r e h e n s i v e l yw a sc o n s t r u c t e d ，w h i c hi m p r o v e st h es e a r c he f f i c i e n c yo fa l g o r i t h m 西南交通大学硕士研究生学位论文第1 ii 页 f i n a l l y , e x a m p l ev e r i f i c a t i o ni sc a r r i e do u t ，a n dw h i c hi n d i c a t e st h ev a l i d i t yo ft h ep r o p o s e d a l g o r i t h m k e y w o r d s ：d i s a s s e m b l y l i n e b a l a n c i n gp r o b l e m ；m u l t i - o b j e c t i v e ；a n tc o l o n y o p t i m i z a t i o na l g o r i t h m ；p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ；p a r e t o 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 1 1 课题的研究意义 步入2 1 世纪，在享受科技进步以及经济快速发展给人类造就的辉煌的物质文明的 同时，全球资源存量日益锐减，环境破坏日趋严重，与此同时世界人口高速增长，资 源、环境、人口已经成为阻碍人类进步的三大障碍【1 】。 上世纪8 0 年代以来，生命终端产品由于各种原因急剧增加，加之拆卸回收技术的 落后，大量的终端产品成为了废弃物的主力军，成为了世界各国共同面临亟需解决的 难题之一。对待大量的废旧产品，若施以囤积或者垃圾焚烧等简单的处理方式，将造 成严重的环境破坏和资料浪费。因此各国纷纷制定新的、更多的环境立法，如中国实 行的“以旧换新”政策以及 等等，同时推行“谁生产，谁负责”的生产责任 延伸制，加之公众环境意识的增强，越来越多的生产商开始回收和再制造废旧产品。 并且由此带来的经济吸引力也从另一个层面推动了更多生产商的投入。 拆卸是重新使用、制造、回收、存储以及合理处理产品关键的第一步【2 ，拆卸线是 实现大规模拆卸的最佳选择，因而有效设计和平衡拆卸线对提高拆卸效率至关重要， 因此研究拆卸线平衡问题具有重要的理论和实际意义。 1 2 国内外现状分析 1 2 1 拆卸线平衡问题及总体研究现状概述 回收指从废物中分离有用物质的过程，再制造是通过物理或机械加工使旧的产品 重新焕发生命活力的过程。产品回收实现了材料的回收以及可用零件的再造，最小化 了废弃物的数量。产品的诸多属性加速了产品回收的过程，例如：容易拆卸、模块化， 而拆卸是实现产品回收重要的第一步，拆卸是指从废弃的产品中系统地分离有价值的 零件、组件、材料的过程，它是实现产品生命周期完整性与封闭性的必要环节。拆卸 由于在产品回收中的重要作用而引起了学术界和工业界的关注。 拆卸线平衡问题寻求找到一个可行的拆卸序列，最小化工作站数，均衡各工作站 空闲时间，以及考虑拆卸线关注的其它方面【2 j 。 拆卸系统面临着许多挑战，例如，对特定零件的需求与拆卸产量之间的矛盾会造 成严重的库存问题，与装配环境中“收敛”的流向相反( 许多零件被装配成一个产品) ，拆 卸环境中的流向是“发散”的( 一个产品被拆卸成许多零件) ，同时，由于事先无法知道回 收产品的情况，相应的零件的可靠度也将无法预知，从而造成回收产品在结构和质量 西南交通大学硕士研究生学位论文第2 页 方面的高度不确定性。其次，一些产品的零件可能会引起污染甚至危害，这些零件被 破坏的几率将增高，同时也将会影响到拆卸工作站的利用，因而需要一些特别的处理。 另外，各种需求资源也将会增加拆卸线的复杂性。下面详细说明拆卸线的一些影响因 素【3 5 1 。 1 ) 拆卸产品 拆卸产品特性的改变将会使拆卸线的运作复杂化，相应的将会引起拆卸线平衡的 复杂化，其次拆卸产品种类的改变将会破坏拆卸线的平衡，因此如何保持拆卸线的平 衡将会非常具有挑战性。 2 1 拆卸线 拆卸线有不同的布局方式，当拆卸产品的质量、种类发生变化时，如何选取合适 的布局方式，提高拆卸线的效率将至关重要。拆卸线的速度是一个非常重要的方面， 它能动态的变化，从而最小化拆卸线需求变化的影响。 3 1 拆卸零件的质量和数量 产品零件质量：回收产品及其构成部件具有高度的不确定性，它们有的存在物理 缺陷，有的存在功能缺陷，有的两者皆有，故当拆卸这类存在缺陷的零件时，一方面 将会耗费很长的时间，另一方面由于零件之间存在着先后约束关系，将会影响后续零 件的拆卸，甚至会导致后续零件无法拆卸，从而将极大的影响拆卸线的效率，故需对 存在缺陷的零件进行特别的处理。 产品零件数量：产品在使用的过程中，由于升级、改造、更换或者退化等原因， 特定零部件的数量及结构和预期将存在很大的差异，将造成零件的需求与产量之间极 大的差距，由此将引发严重的库存问题，故在拆卸零件之前，需考虑是否存在此类情 况，以便确定最适合的拆卸流程。 4 ) 拆卸时间 零件拆卸会因拆卸产品状况的不同以及拆卸线工作站的差异而发生改变，因此， 零件拆卸时间可能是确定的、随机的或者动态变化的，例如，工人在拆卸的过程中， 由于经验的累积以及动作的娴熟，拆卸零件的时间将逐渐减少。这种动态的学习过程 将会使零件的拆卸时间动态的变化。 5 1 拆卸零件的需求 在拆卸线中，对零部件的需求可分为三类：对某个零件的需求( 单个零件拆卸 线，部分拆卸的特例) ；对多个零件的需求( 部分拆卸) ；对所有零件的需求( 完全 拆卸) 。在拆卸的过程中，由于零部件存在物理或者功能缺陷以及零件优先关系的约束， 将会使拆卸线复杂化。 6 ) 零件分配 将零件分配到工作站时，不仅要考虑零件优先关系以及节拍约束，还需要考虑其 西南交通大学硕士研究生学位论文第3 页 它因素，如有些特定的零件需要特定工作站的机器和工具进行拆卸，比如有危害的零 件需在特定的专业化的工作站进行拆卸，以免对环境或其他工作站造成危害；又如某 些零件需在特定的温度、湿度、灯光等特定环境下进行拆卸。故某些零件需在特定的 工作站进行拆卸。 表1 1 基于操作及技术的装配线和拆卸线的比较 表1 1 从技术及操作方面比较了拆卸线及装配线的不同，从表中可以清晰的看出 有必要发展特定的技术以及改善现有的线平衡技术来提高拆卸线，同时，装配线平衡 问题的求解方法以及累积的经验可为拆卸线平衡问题提供指导。 拆卸线平衡问题求解途径目前有以下几种： ( 1 ) 精确解法：精确算法包含线性规划、整数规划、动态规划和分枝定界法等。目 西南交通大学硕士研究生学位论文第4 页 前应用于求解拆卸线平衡问题的有分支定界算法【6 】，但分枝定界法的求解效果与所采用 的启发式评价函数及截枝规则有关，通常首先界定问题的最优解判定标准，判定标准 的准确性对问题的求解时间影响较大，同时，求解时间也受着问题规模的较大影响。 ( 2 ) 启发式算法：启发式方法分为以下几类：简单规则( 只采用单一规则进行决策) 、 复合规则( 采用多个规则进行综合决策) 、回溯决策规则( 前序决策对当前决策具有影 响) 、以及寻优决策规则( 一种整体的搜索规划策略) 。启发式方法如2 o p t 算法【j 7 。引，贪 婪算法】、领域爬山算法【8 - 9 】。启发式方法求解较为快速便捷，但不存在具备普适性的 启发式规则。对于简单的优化问题，能较快得到优化结果，但是对于附加各种约束条 件的复杂问题求解时，往往无能为力，更主要的是，往往难以找到最优解。 ( 3 ) 亚启发式算法( 智能优化算法) ：许多学者通过观察自然界中的物理、生物现象， 提出了一批新颖的优化算法，如遗传算法( g e n e t i c a l g o r i t h m ，g a ) 1 0 】、h k 搜索算法【1 1 】、 蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 【1 2 】等。这些优化算法通过模仿自然界中 的一些内在机制和客观规律，并应用于优化问题的求解过程中，以期求得较优解或最 优解。但是，应用这些优化算法解决具体问题时，一般须考虑实际问题的本身特征， 根据具体问题的内在机理制定相应合理的搜索机制与问题描述机制，以保证所得优化 结果的可行性。 综上可知，用于求解拆卸线平衡问题的启发式方法居多，群集智能优化算法蚁群 算法较少使用，粒子群算法在拆卸线领域未见报道，故本文开展拆卸线平衡问题的群 集智能算法研究。 1 2 2 国内外研究现状 2 0 0 1 年，g u n g o r 等【13 j 首先提出了拆卸线平衡问题( d i s a s s e m b l yl i n eb a l a n c i n g p r o b l e m ，d l b p ) ，分析比较了与装配线平衡的异同，说明了拆卸线的复杂性，并结合拆 卸线的特点，提出了一种启发式方法，该启发式方法融合了空闲时间最小、尽可能早 的拆卸高需求的零件、后续任务数最多、尽可能早的拆卸有危害的零件以及最小化方 向改变5 种启发式规则，最后，通过实例验证了所提启发式方法的有效性。 同年，g u n g o r 和g u p t a 1 4 提出来一种求解存在缺陷任务的拆卸线平衡问题的方法。 同年，g u n g o r 和g u p t a 采用分支定界方法【6 】求解拆卸序列规划问题。 2 0 0 2 年，g u p t a 1 s 采用遗传算法来求解最佳的拆卸系列，并用实例验证了算法的有 效性。 2 0 0 3 年，m c g o v e m 和g u p t a 【7 j 融合了贪婪算法和2 - o p t 算法来求解拆卸线平衡问 题，它首先采用基于f i r s t f i td e c r e a s i n g 的贪婪算法在尽可能早的拆卸有危害和高需求 零件的情况下，最小化工作站数，从而得到一个接近最优解的方案，然后在此基础上， 利用2 - o p t 使各工作尽可能的相等，同时维持乃至改善有危险和需求的零件。 西南交通大学硕士研究生学位论文第5 页 2 0 0 4 年，g u p t a 和m c g o v e m n 利用基准例子，在工作站数、平衡、求解时间方面 对比分析了贪婪算法、领域爬山算法和2 - o p t 算法。 同年，m c g o v e r n 和g u p t a e 9 】针对拆卸线的特点，设计了蚁群算法、遗传算法、h k 亚启发式算和融合贪婪算法和领域爬山算法的启发式算法，并利用基准例子，对比分 析了4 种组合优化算法在工作站数、平衡、求解时间方面的性能。 同年， 灿t c k i l l 【l6 等采用改进的a n d o r 图规划拆卸线平衡方案，其目标最大化 回收利润。 2 0 0 5 年，m c g o v e r n 和g u p t a 1 0 证明了拆卸线平衡问题是n p 组合优化问题，问 题复杂度随任务数的增加而呈几何级数增长，难以在合理的时间完全解决问题，利用 穷举搜索算法说明了算法的求解时间随任务数的增加呈指数增长，之后采用遗传算法 来求解拆卸线多目标平衡问题，最小化工作站数，工作站的空闲时间尽可能相等，最 小化危害指数和需求指数，以及最小化了零件拆除方向的改变。 同年，m c g o v e m 和g u p t a 1 2 】提出了一种蚁群最优化的方法来求解多目标的拆卸 线平衡问题，其目标最小化工作站数，工作站的空闲时间尽可能相等，最小化危害指 数和需求指数，以及最小化了零件拆除方向的改变。 同年， g u p t a 和l a m b e r t 1 7 】采用了启发式方法来求解拆卸线平衡问题，其目标是 最小化拆卸费用，并与部分分支定界进行对比，说明了算法能够非常快的找到很好的 解，验证了算法的有效性。 同年， g u p t a 和g o v e r n 1 1 】提出了用蚁群算法和h k 搜索算法来求解拆卸线平衡 问题，其目标为最小化工作站数，保证了工作站的空闲时间的相似性，最小化危害指 数和需求指数，以及最小化了零件拆除方向的改变，同时比较了这两种算法。 同年，m c g o v e m 和g u p t a 1 8 用局部搜索程序和贪婪算法来求解拆卸线平衡问题， 其目标为最小化工作站数，工作站的空闲时间尽可能相等，最小化危害指数和需求指 数。 2 0 0 6 年，t u r o w s k i t ”】等考虑了拆卸线的不确定因素。 2 0 0 8 年，a g r a w a l y 和t i w a r i 2 0 利用协同蚁群算法来求解随机混合u 型拆卸 线平衡问题及排序。 同年，a 1 t e k j n 【2 1 】等利用混合整数规划和线性规划最大化了部分拆卸线的利润。 2 0 0 9 年，丁力平等【2 2 。2 3 】利用基于p a r e t o 蚁群算法求解了拆卸线的多目标问题，其 目标为最小化平均闲置率、负荷均衡指数、拆卸线成本。 2 0 1 2 年，邢宇飞等 2 4 】利用基于p a r e t o 蚁群算法求解拆卸序列规划，其目标为拆卸 方向改变次数、拆卸总行程、拆卸零件数量。 西南交通大学硕士研究生学位论文第6 页 1 3 课题研究目标、研究内容、解决的关键问题 1 ) 课题研究目标 ( 1 ) 研究拆卸线平衡问题的机理，分析拆卸线平衡问题的影响因素，比较拆卸线平 衡问题与装配线平衡问题的异同同时结合拆卸线的特点，建立多目标拆卸线平衡问题 的数学模型。 ( 2 ) 针对多目标拆卸线平衡问题提出有效的智能算法一蚁群算法和粒子群算法。 2 ) 研究内容 ( 1 ) 研究拆卸线平衡问题的机理，分析拆卸线平衡问题的影响因素，比较拆卸线平 衡问题与装配线平衡问题的异同，说明有必要发展特定的技术去研究和改善拆卸线平 衡问题，同时在装配线上累积的经验和知识又可以为拆卸线的研究提供指导。结合拆 卸线的特点，建立多目标拆卸线平衡问题的数学模型，其优化目标为最小化工作站数、 均衡各工作站空闲时间，并考虑拆卸产品零件的危害、需求以及方向。 ( 2 ) 研究多目标拆卸线平衡问题的一种粒子群算法。协同考虑拆卸线的五个方面， 优先考虑拆卸线的平衡目标，在平衡相同的情况下，优先考虑危害目标，在危害相同 的情况下，优先考虑需求目标，在需求相同的情况下，考虑拆卸方向目标，提出了一 种基于优先权的粒子群算法，并且通过实例验证算法的有效性。 ( 3 ) 研究基于p a r e t o 粒子群算法的多目标拆卸线平衡问题。协同考虑拆卸线的五个 方面，所提粒子群算法通过p a r e t o 支配以及分散度作为解的评价规则，选取非支配解， 通过小生境技术选取全局最优解，通过p a r e t o 支配以及平衡目标选取局部最优，从而 提供分布均匀的p a r e t o 解集。 ( 4 ) 研究多目标拆卸线平衡问题的一种蚁群算法。协同考虑拆卸线的五个方面，最 小化拆卸线的平衡目标，在平衡相同的情况下，最小化危害目标，在危害相同的情况 下，最小化需求目标，在需求相同的情况下，最小化拆卸方向目标，提出了一种改进 的蚁群算法，协调考虑了以零件拆卸时间、危害以及需求三种规则的启发式信息，并 综合考虑利用先验知识、探索新路径、随机选择三种方式的混合搜索机制，同时采用 局部更新和全局更新相结合的方式，有效的提高了算法的搜索效率和质量，并且通过 实例验证算法的有效性。 3 ) 解决的关键问题 ( 1 ) 针对多目标拆卸线平衡问题的研究现状，提出一种基于优先权的粒子群算法。 粒子群算法主要用来求解连续空间的优化问题，而多目标拆卸线平衡问题属于离散优 化问题，不适合标准粒子群算法的迭代方式，故需实现解的表示和粒子之间的映射， 故本文采用随机数编码方式，用随机数表示的粒子位置作为选择拆卸任务的权重，进 而得到解码的拆卸任务序列。其次多目标的求解方法有很多种，本文第一种处理方法 为：优先考虑危害目标，在危害相同的情况下，优先考虑需求目标，在需求相同的情 西南交通大学硕士研究生学位论文第7 页 况下，考虑拆卸方向目标；本文的第二种处理方法：采用p a r e t o 支配的方法来作为非劣 解得评价准则，然后用小生境技术选取全局最优解。 ( 2 ) 针对多目标拆卸线平衡问题，提出了一种改进的蚁群算法。蚁群算法任务的选 择方面，本文综合考虑利用先验知识、探索新路径、随机选择三种方式的混合搜索机 制，启发式信息方面，本文协同考虑了以零件拆卸时间、危害以及需求三种规则的启 发式信息，在信息素更新策略方面，本文采用全局更新和局部更新相结合的策略，局 部更新通过信息素的挥发，提高蚂蚁对未访问路径有较强的探索能力，全局更新只对 全局最优的蚂蚁才释放信息素，使搜索过程更具有指导性。 1 4 采取的研究方法、技术路线 1 ) 研究方法： 本文主要采用智能搜索算法粒子群群算法和蚁群算法求解多目标拆卸线平衡问 题。 协同考虑了拆卸线平衡问题的5 个方面，提出了一种基于优先权的粒子群算法， 该算法采用随机数生成粒子的位置和速度，而位置和速度的更新则为对应随机数相加 减，进而把位置的随机数作为选择零件的权重，从而根据权重的大小来选择拆卸的零 件，而对于5 个目标的处理方法，采用优先考虑危害目标，在危害相同的情况下，优 先考虑需求目标，在需求相同的情况下，考虑拆卸方向目标； 结合拆卸线的特点，提出了一种基于p a r e t o 的粒子群算法，采用p a r e t o 支配以及 分散度作为解的评价规则，选取非支配解，通过小生境技术选取全局最优解，通过p a r e t o 支配以及平衡目标选取局部最优，从而提供分布均匀的p a r e t o 解集。 提出了一种改进的蚁群算法，协调考虑了以零件拆卸时间、危害以及需求三种规 则的启发式信息，并综合考虑利用先验知识、探索新路径、随机选择三种方式的混合 搜索机制，而对于5 个目标的处理方法，采用优先考虑危害目标，在危害相同的情况 下，优先考虑需求目标，在需求相同的情况下，考虑拆卸方向目标； 2 ) 技术路线： 结合多目标拆卸线平衡问题的特点，采用群集智能优化算法粒子群算法和蚁群算 法来求解多目标拆卸线平衡问题。并采用m a t l a b 软件开发了算法的程序，最后通过实 例验证说明了算法的有效性。 图1 1 为本文研究的技术路线图。 西南交通大学硕士研究生学位论文第8 页 图1 1 本文的研究技术路线图 1 5 创新性 本课题具有以下创新点： 1 ) 结合拆卸线的特点，建立了多目标拆卸线平衡问题的数学模型，提出了两种粒 子群算法目标基于优先排序的粒子群算法以及基于p a r e t o 的粒子群算法，目前未见有 粒子群算法在拆卸线平衡问题领域的报道。 2 ) 针对多目标拆卸线平衡问题提出了一种改进的蚁群算法，协调考虑了以零件拆 卸时间、危害以及需求三种规则的启发式信息，并综合考虑利用先验知识、探索新路 径、随机选择三种方式的混合搜索机制。 1 6 论文结构和主要内容 论文的整体研究思路为，首先明确所研究课题的意义，制定研究目标，然后首先 提出所研究问题的数学模型，之后的研究路线为： 1 ) 所解决的问题为多目标拆卸线平衡问题，目标协调考虑了最小化工作站数、均 衡各工作站空闲时间、尽可能早地拆除有危害的部件、尽可能早地拆除高需求的部件、 最小化拆除方向的改变。 2 ) 所采用的多目标解决算法：主要采用了目标基于优先排序以及基于p a r e t o 的多 目标解决方法。 3 ) 所采用的求解算法：两种群集智能优化算法一蚁群算法和粒子群算法。 本文的主要研究结构如图1 2 所示，图中并未表明第一章、第二章、第五章以及 西南交通大学硕士研究生学位论文第9 页 结论和展望的内容。 研究问题求解方法论文章节 图1 - 2 论文主要研究结构 1 7 本章小结 本章的主要工作如下： ( 1 ) 首先介绍了拆卸线平衡问题的研究意义，说明了研究拆卸线平衡问题的重要性， 其次详细的说明了拆卸线所面临的挑战以及影响因素，然后从操作和技术方面对比了 拆卸线和装配线的异同，从而装配线平衡问题的求解方法以及累积的经验可为拆卸线 平衡问题提供指导，之后详细的介绍了国内外学者对拆卸线平衡问题的研究状况，引 出了本文的研究课题一拆卸线平衡问题的智能算法研究。 ( 2 ) 详细的介绍了课题研究目标、研究内容、解决的关键问题以及所采用的研究方 法和课题的创新性。 西南交通大学硕士研究生学位论文第10 页 第2 章多目标拆卸线平衡问题的概念和数学模型 2 1 多目标拆卸线的概念 多目标拆卸线平衡问题寻求找到一个可行的拆卸序列，最小化工作站数，均衡各 工作站空闲时间，以及考虑拆卸线关注的其它方面。本文考虑的其它方面为：尽可能 早的拆卸有危害的零件，尽可能早地拆除高需求的部件，最小化零件拆除方向的改变。 在一个基本的多目标拆卸线平衡问题定义中，包含以下基本要素： 1 ) 拆卸( d i s a s s e m b l y ) ，拆卸是指从废弃的产品中系统地分离有价值的零件、组件、 材料的过程。 2 ) 产品( p r o d u c t ) ，产品是指很多零件连接在一起构成的一个稳定的单元体。本文 的产品为使用过的废旧产品。 3 ) 零件( p a r t ) 。零件是指拆卸过程中形状不会发生改变的最小固体对象，不同零件 之间的组合构成拆卸线问题的一个可行解。本文规定在拆卸的过程中，一个零件对应 一项拆卸任务。 4 ) 零件拆卸时f 日- l ( p a r t t i m e ) 。零件拆卸时间指拆卸一个零件所需要的标准时间， 一般为定值。 5 ) 生产节拍( c y c l et i m e ) 。每个工作站拆卸完分配零件的指定时间。( 所有工作站 都是相同的) 6 ) 工作站操作时f 司( w o r k s t a t i o no p e r a t i n gt i m e ) 。工作站操作时间即此工作站内所 有零件的拆卸时间之和。 7 ) 空闲时间( i d l et i m e ) 。在拆卸线中，工作站操作时间一般小于节拍时间，造成 每个工作站中几乎都有少量的空闲时间，如何优化零件的组合，以减少空闲时间，提 高平衡率，是拆卸线的重要优化目标。 8 ) 零件优先关系约束( p r e c e d e n c ec o n s t r a i n t ) 。优先约束关系是拆卸线平衡问题的 基本约束条件，不同于装配线只有简单的a n d 优先关系，拆卸线平衡问题存在a n d 、 o r 以及复杂的a n d o r 优先关系。若p j 代表第f 需要拆卸的零件，以最简单的情况 说明a n d 、o r 以及复杂的a n d o r 关系。a n d 关系存在于零件p 1 ，p 2 以及关联的 零件p 3 之间，则p l ，刃都必须在p 3 之前拆卸。o r 关系存在于零件p 1 ，p 2 以及关联的 零件p 3 ，则p l 或者印必须在p 3 之前拆卸。复杂的a n d o r 关系存在于p 1 ，刃和p 3 以 及关联的p 4 之间，则p 1 和印或者p 3 必须在p 4 之间拆卸。在装配线中，图2 1 所示的 a n d 优先关系采用二进制矩阵来表示： 西南交通大学硕士研究生学位论文 第11 页 1 1 0 2 0 r=30 4 0 50 5 图2 1 任务优先关系图 在拆卸线中，优先关系采用拆卸优先矩阵( d i s a s s e m b l yp r e c e d e n c em a t r i x ，d p m ) 来 表示，d p m 包含二进制元素和属性( 奶来表示o r 以及复杂的a n d o r 关系。代表了拆卸 蝴d e d = - ( x ，y ，z ，呵，- y ，- z ) ，贝l j r = r 扩】，i , j = l ，2 ，n 。为零件总数。 吩2 l ，零件fa n d 优先零件， d ， 零件fo r 优先零件， 0 ，否则 则图2 2 所示二维优先关系可以表示为： 10 r ：2 0 30 40 t 图2 2 零件优先关系图 9 ) 可选任务。若一个任务的所有紧前任务都已经分配，则该任务为可选任务。 3 1 o o o 0 西南交通大学硕士研究生学位论文第12 页 1 0 ) 可供分配的任务。若一个任务的所有紧前任务都已经分配，并且该任务的拆 卸时间大于工作站的空闲时间，则该任务为可供分配的任务。 2 2 多目标拆卸线平衡问题的数学模型 多目标拆卸线平衡问题寻求找到一个可行的拆卸序列，最小化工作站数，均衡各 工作站空闲时间，以及考虑拆卸线关注的其它方面。 优化目标协同考虑如下五方面： 1 最小化拆卸线的工作站数，也即最小化总的空闲时间。 2 使各工作站的空闲时间尽可能的相等，也即均衡各工作站的时间。 3 尽可能早地拆除有危害的部件。 4 尽可能早地拆除高需求的部件。 5 最小化拆除方向的改变。 符号含义：c 卜周期时间，咒一任务数，一工作站数，卜第，个零件的拆卸时间， l 最d , i 作站数，地。广最大工作站数，s 卜第，个工作站的时间，月_ 危害指标， j i z 一零件的危害属性( 矗= 1 表示零件有危害，反之为0 ) ，耻拆卸系列的第k 个位置的 零件编号，肌危害零件的总数，少一计数变量，爿l 最优的危害指标数，伽一最差 的危害指标数，d 一需求指标，扛零件的需求属性( 扛1 表示零件有危害，反之为0 或 者d 需求量) ，d 一最优的需求指标数，d m 厂最差的需求指标数，肛一零件的方向指标， 卜相应拆除方向的数值，r 一最优方向改变值，r 砌，广最差方向改变值，卜方向总数， 五l 拆卸线上零件的集合，s 卜拆卸到工作站的零件集合，尸f 广表示拆卸任务的优先关 系，若任务i 是任务，的紧前任务，则只- 1 ，否则b = 0 。 其中，模型的假设如下所示： 零件的拆除时间是确定的并且是不变的。 每个产品均为完全拆卸。 所有产品的零件没有附加物、遗失或改变。 每个工作站所有零件的总拆除时间不超过周期时间。 没有违反零件的优先关系。 目标1 可以描述为： 上 m i n i m i z ez a = ( c t s 乃) ( 2 1 ) j = l 线平衡寻求获得最好的平衡所有工作站的空闲时间为0 ，但是这一般是不可能的。 线效率( l i n ee f f i c i e n c y ，l e ) 干o 平滑率( s m o o t h n e s si n d e x ，s i ) 作为评价装配线的性能指标， s i 使每个工作站的空闲时间尽可能都是相同的，由于s i 采用各工作站时间与最大工作 站时间进行比较，因而可能导致产生一个比较大的工作站数，而l e 考虑的是最小化工 西南交通大学硕士研究生学位论文第13 页 作站数，由于没有比较各工作站的时间，从而可能导致各工作站的空闲时间相差较差， 所以本文采用文献 1 2 提出的平衡措施，该方法同时兼顾最小化工作站数以及使各工作 站的空闲时间相等两个目标。其平衡措施可以描述为： f = ( c t - s t ：) ( 2 2 ) 故d l b p 的平衡目标可以表示为： m i n i m i z e z 2 = ( c 丁一踢) ( 2 - 3 ) 很明显，最好的平衡z 2 = 0 ，理论上最差的平衡： z 2 = ( c t - t j ) ( 2 - 4 ) 危害指标作为评价解系列的性能指标，其数值越小越好。其中采用二进制来表示 零件是否有危害( 1 表示有危害，0 表示没有) ，因而危害指标为二进制标记与该零件所 在位置的乘积之和，所以应该尽可能早的拆除有危害的零件，可以用下式来表示： 日= 鼢叫：u ，焉 仁5 ， t = l l ，。由w u 所以d l b p 危害零件的目标函数为： m i n i m i z e z 3 = ( 七) ( 2 6 ) 故最好的危害指标为： 日= p ( 2 7 ) 例如，四个危害零件的最好危害值为1 + 2 + 3 “= 1 0 ，最差的危害指标为： 。= p ( 2 - 8 ) 例如，危害零件数为4 ，任务数为1 0 的最差危害指标上乙伽= 7 + 8 + 9 + l o = 3 4 。 需求指标也作为衡量解系列的性能指标，其数值越小越好。同样还是用二进制表 示零件是否有需求，1 代表有需求，0 代表没有，故需求指数为需求量与零件在解系列 中所在位置的乘积。因而应尽司能早地拆除高需求的零件。司以表不为： d = ( 尼d 髓) ，d 飓，峨 k = l 故d l b p 需求零件的目标函数为： m i n i m i z e z 4 = ( 尼) ( 2 - 9 ) ( 2 1 0 ) 最好的拆卸系列为：d 飓d p s 2 r i p s 例如，三个有需求零件的需求量为2 ，1 0 ，5 ，则最差的需求指数为： 西南交通大学硕士研究生学位论文 第14 页 ( 1 10 ) + ( 2 2 ) + ( 3 5 ) = 2 9 。 最后，方向指标作为衡量解系列的性能指标，其值越小说明方向改变的越少，相 应的解也就越好，其中我们用整数值来代表相应的方向g ，y ，- y ，z ，- z ) ，如下所示： + 1 ，方向 一1 ，方向 + 2 ，方向 一2 ，方向 + 3 ，方向 一3 ，方向 从而很容易以相同的方式扩展其他的或者不同的方向，方向指标可以表示为： 尺= 薯( r ) r ki o ，1 , r 否则p s , k 1 ( 2 - 1 2 ) 故d l b p 零件的方向目标函数为： m i n i m i z e z 5 = ( r ) ( 2 - 1 3 ) 所以最好的方向指标为： r + = h 一1 ( 2 1 4 ) 例如，给定的一个产品包含六个零件，其拆除方向为( 哕，乜，吵，哕，h ，十功，则最好 的方向指标值为2 1 = 1 ，即方向只改变了一次，比如一个可能的方向系列为： ，方向的改变数总是小于任务数，方向改变的最差情况可用下式表示： 兄。= h 其中h = n - 1 ( 2 - 1 5 ) 此外，r 一鲫起决于给定拆除方向的零件数和总得拆除方向数，其界限为： h 兄。，2 - 1 其中h n - 1 ( 2 - 1 6 ) 例如，六个有危害零件的拆除方向为( h ，乜，h ，吵，乜，嘲，其r 硎为2 ，而如果六 个有危害零件的拆除方向为( 吵，乜，吵，少，h ，乜) ，则其r n 。m 值为5 。对于上面提到的危 害、需求、方向的最优或者最差的表达式都是在优先顺序满足的前提下用于产生最优 或者最差的解系列。 根据以上对拆卸线平衡目标的分析，可建立如下多目标优化数学模