（机械电子工程专业论文）混流装配线排序问题的建模与算法研究.pdf

摘要 摘要 经济的全球化和用户需求的多样化、个性化带动了制造业的发展，制造业已 经由传统的大批量生产模式转变为多品种中小批量生产模式。传统的单一品种装 配线，逐渐被多品种混流装配线所代替。 多品种混流装配线是实现多品种中小批量生产模式的有效途径。而组织多品 种混流生产的关键是实现生产的平准化，而平准化的核心是混流装配线产品投产 排序的最优化。投产顺序的最优化能保证均衡生产，缩短交货期、降低产品库存， 提高企业的竞争力，较好地适应当前市场发展的需求。因此，通过对混流生产线 的投产排序问题进行研究，可以更好地发挥混流装配生产方式的优势。 投产排序问题在国内外是研究的热点。本文针对生产平准化与时间优化的目 标，提出了混流装配线的多目标优化函数各零部件消耗速率均匀化和最小生 产循环周期最短。并建立了相应的数学模型。 混流生产线的投产排序问题已被证明是组合优化问题中n p 难题，运用人工 智能算法能得到较好的解。粒子群算法是模拟鸟群捕食行为的算法，通过初始化 一群随机粒子，在每一次迭代中，粒子跟踪两个极值来更新自己，通过不断的迭 代找出最优解。模拟退火算法通过模拟热力学中固体物质冷却和退火过程，采用 m e t r o p o l i s 接受准则避免落入局部最优解，渐进地收敛于全局最优解。 本文将粒子群算法与模拟退火算法相结合，根据粒子群算法的原理，引入遗 传算法的交叉、变异操作与模拟退火算法的搜索机制，设计出改进粒子群算法。 本文最后通过一个实例，运用改进粒子群算法进行混流装配线排序问题的求 解，并与遗传算法、遗传模拟退火算法、粒子群算法的求解结果进行了对比分析， 验证了所提出的改进粒子群算法有效可行，并且比其它算法较快的得到搜索结果。 关键词：混流装配线；排序；建模；模拟退火算法；粒子群算法 广东工业大学硕士学位论文 a b s t r a c t e c o n o m i cg l o b a l i z a t i o na n dt h ed i v e r s i f i c a t i o no fu s e rn e e d sa n dp e r s o n a l i t yt o p r o m o t et h ed e v e l o p m e n to ft h em a n u f a c t u r i n gs e c t o r , t h em a n u f a c t u r i n gs e c t o rh a s b e e nc h a n g ef r o mt h et r a d i t i o n a lm o d e lo fh i g h - v o l u m ep r o d u c t i o nt os m a l la n d m e d i u mv o l u m ep r o d u c t i o no fm u l t i s p e c i e sm o d e l t r a d i t i o n a lv a r i e t i e so fas i n g l e a s s e m b l yl i n eh a v eb e e ng r a d u a l l yr e p l a c e db ym i x e d - m o d e la s s e m b l yl i n e s m i x e d - m o d e la s s e m b l yl i n ei st oa c h i e v es m a l la n dm e d i u m - s i z e dv a r i e t yo f e f f e c t i v em e a n so fm a s sp r o d u c t i o nm o d e o r g a n i z e dt h ep r o d u c t i o no fm u l t i s p e c i e s p r o d u c t i o n , t h ek e yi st h e ”s t a b i l i z a t i o n ”a n dh e i j u n k aa s s e m b l yl i n ei st h ec o r eo f p r o d u c t st h a to p t i m i z et h ep r o d u c t i o ns e q u e n c e o p t i m i z et h ep r o d u c t i o ns e q u e n c et o e n s u r eab a l a n c e dp r o d u c t i o n , s h o r t e nt h ed e l i v e r yt i m e ，r e d u c ei n v e n t o r ya n di m p r o v e t h ec o m p e t i t i v e n e s so fe n t e r p r i s e s ，t ob e t t e ra d a p tt oc u r r e n tm a r k e td e m a n d t h e r e f o r e ， m i x e d - m o d e lt h r o u g ht h ep r o d u c t i o nl i n et os o r tt h ep r o b l e m , c o u l db eb e t t e rw a yt o p l a yam i x e d - f l o wa s s e m b l ya d v a n t a g e s p r o d u c t m ns c h e d u l i n gp r o b l e mi st os t u d ya th o m ea n da b r o a d ，t h eh o t s p o t s i nt h i s p a p e r , s t a b i l i z a t i o no fp r o d u c t i o na n dt i m et oo p t i m i z et h eo b j e c t i v e so ft h ep r o p o s e d a s s e m b l yl i n em u l t i o b j e c t i v eo p t i m i z a t i o nf u n c t i o n e v e nt h ep a r t sc o n s u m p t i o nr a t e a n dt h es m a l l e s ts h o r t e s t p r o d u c t i o nc y c l e a n d e s t a b l i s ht h e c o r r e s p o n d i n g m a t h e m a t i c a lm o d e l m i x e d - m o d e lp r o d u c t i o nl i n es c h e d u l i n gp r o b l e mh a sb e e np r o v e dt ob et h ei s s u e o fc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m s i nn p , t h eu s eo fa r t i f i c i a l i n t e l l i g e n c e a l g o r i t h mc a ng e tab e t t e rs o l u t i o n p s oi sas i m u l a t i o na l g o r i t h mf o rb i r d so fp r e y b e h a v i o r , t h r o u g hag r o u po fr a n d o mp a r t i c l e si n i t i a l i z e di ne a c hi t e r a t i o n , t h et w o e x t r e m ep a r t i c l et r a c k i n gt ou p d a t et h e m s e l v e st h r o u g hc o n s t a n ti t e r a t i o nt of i n dt h e o p t i m a ls o l u t i o n s i m u l a t e da n n e a l i n ga l g o r i t h mb ys i m u l a t i n gt h et h e r m o d y n a m i c so f s o l i d st h ep r o c e s so f c o o l i n ga n da n n e a l i n g ，t h em e t r o p o l i sa c c e p t a n c ec r i t e r i at oa v o i d f a l l i n gi n t ot h eh a n d so ft h el o c a lo p t i m a ls o l u t i o n , ag r a d u a lc o n v e r g e n c et ot h eg l o b a l o p t i m u m i nt h i sp a p e r , p a r t i c l es w a r mo p t i m i z a t i o nw i t hs i m u l a t e da n n e a l i n ga l g o r i t h m a b s t r a c t c o m b i n i n gp a r t i c l es w a r mo p t i m i z a t i o nb a s e do i lt h ep r i n c i p l e ，t h ei n t r o d u c t i o no f g e n e t i ca l g o r i t h mc r o s s o v e ra n dm u t a t i o no p e r a t i o na n ds i m u l a t e da n n e a l i n ga l g o r i t h m s e a r c hm e c h a n i s m , d e s i g n e dt oi m p r o v ep a r t i c l es w a l t no p t i m i z a t i o n f i n a l l y , t h r o u g h 锄e x a m p l eo ft h eu s eo fp a r t i c l es w a r mo p t i m i z a t i o nt oi m p r o v e t h e a s s e m b l y l i n e s c h e d u l i n gp r o b l e mf o rm i x e d - m o d e ls o l u t i o n , ，a n dg e n e t i c a l g o r i t h m s ，s i m u l a t e da n n e a l i n gg e n e t i ca 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 nt os o l v e t h ec o m p a r a t i v ea n a l y s i so fr e s u l t s ，v a l i d a t i o no ft h ep r o p o s e dp a r t i c l es w a r m o p t i m i z a t i o nt oi m p r o v et h ee f f e c t i v ef e a s i b l ea n df a s t e rt h a no t h e ra l g o r i t h m sg e t s e a r c hr e s u l t s k e yw o r d s ：am i x e d m o d e la s s e m b l yl i n e ；m o d e l i n g ；s c h e d u l i n g ；s a ；p s o 广东工业大学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含他人已经发表或撰写过的研究成果，不包括 本人或其他用途使用过的成果。与我一起工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 6 2 指导老师签字： 论文作者签字： 二零零九年六月一日 ；印， ，j新澎 第一章绪论 第一章绪论 1 1 研究背景 1 1 1 现代企业面i 艋的挑战 面对激烈的市场竞争，如何提高企业的竞争力是每个企业永远的课题。先进 的技术与企业的生产模式是企业获得竞争优势的两个基本方面。技术与生产模式 血肉相连，技术为企业的生产或服务提供了方法、工具与途径；生产模式使企业 高效率地开发运用其技术能力。生产模式是企业对市场要求做出快速反应的基础， 是企业获得竞争优势的核心【。因此，选择合适的生产模式对企业提高竞争优势有 重要的作用。 随着科学技术的进步与生产力的发展，特别是现代运输业与资讯业的迅猛发 展，全球制造业进入了一个变革的时代，世界市场已经从传统的相对稳定型市场 演变成动态多变型市场。同行业之间、跨行业之间的竞争非常激烈。竞争表现在 产品生命周期、交货期、质量功能性能、用户需求多样化、成本效益价格和对 环境的影响等方面。具体主要有以下几方面【2 1 ： ( 1 ) 用户需求多样化、个性化随着经济的发展和市场的日趋饱和，市场由卖 方市场演变为买方市场，产品消费节奏明显加快，消费者的行为更加具有选择性， 用户需求多样化、个性化已经成为世界的潮流，批量生产的产品逐渐为个性化、 多样化的产品所取代。在买方市场条件下，信息是不对称的，掌握信息的是客户， 缺乏信息的是企业。因此，企业的生存法则成为以客户需求为导向，根据客户需 求变化安排生产，调整生产过程使其更具柔性，这样才能更具竞争力。 ( 2 ) 产品生命周期缩短现代科技以日新月异的速度发展，新产品层出不穷， 产品的市场寿命大大缩短。据统计，机械电子产品的平均市场寿命已经从2 0 世纪 7 0 年代后期的8 年左右缩短到2 0 世纪9 0 年代后期的4 年，与这种趋势相反，由 于新产品的功能和结构的日益复杂，新产品的开发周期却从2 0 世纪7 0 年代后期 的1 5 年增加到2 0 世纪9 0 年代后期的4 年。对企业而言，如何顺应客户的需求， 对市场变化迅速做出反应，已经成为压倒一切的竞争因素。解决好产品市场寿命 缩短和新产品开发周期延长这一日益尖锐的矛盾，已经成为企业生死攸关的问题。 广东工业大学硕士学位论文 ( 3 ) 交货期成为主要的竞争因素以时间为基准的竞争已经成为企业竞争的 一个突出特点，与此相适应的企业制造战略主要是如何在最短的时间内开发和生 产出市场需要的产品，交货期成了企业最关心的事情之一。能否更快、更好、以 更低的成本制造出新的产品投放市场，将是制造企业生存和发展的关键。时间已 经成为决定竞争胜负的最关键因素，市场占有率的很大比率属于产品首先上市的 企业。 由此可见，市场已经由过去以产品为中心的竞争转移到现在以以客户为中心 的竞争，因此，如何提高企业的灵活性，如何在保证交货期的同时满足客户的个 性化、多样化的要求己经成为了许多企业的重要目标。面对这样的情况，采用合 理的方式来组织生产成为了企业解决问题的有效措施。 1 1 2 企业的生产模式 1 大批量生产现代流水生产组织方式起源于美国汽车业的先锋开拓者亨利 福特一世。1 9 1 3 年，福特一世设计出世界上第一条汽车生产装配流水线，大大降 低了福特t 型汽车的生产成本，由此标志着大批量生产到来，揭开了现代化流水 生产的序幕，引起了制造业的一个根本性变革。在此后的半个多世纪，大规模生 产是世界制造业的主导模式，它以规模经济、高效率和低成本为特征，使制造业 获得了前所未有的速度发展，为人类文明和社会进步做出了巨大的贡献。 大批量生产是一种刚性的生产系统，该生产方式体现的是“以生产为中心 的管理思想。它是在市场环境相对稳定、市场需求供不应求的情况下产生的，大 规模生产通过采用标准制造过程和标准化的零部件，进行高效的自动化作业。它 提高了生产率、产品质量，降低了成本，使客户可以获得廉价的产品。 然而，大批量生产只适合于单一的产品市场、稳定的市场需求、产品生命周 期和产品开发周期较长。大批量生产呈刚性，灵活性差，库存水平较高，不适应 灵活多变的用户需求。用户选择余地小。企业的资金压力大，一旦客户的需求发 生转变，企业就面临着生存的危险。而且，由于产品同质化的倾向越来越明显， 靠大批量生产的低价格来获得企业的竞争优势越来越困难f 引。 2 多品种中小批量生产由上述可知，市场需求的多样性使得以往单一品种 大批量生产、靠批量降低成本的方法逐渐无法再施展其威力，企业更多地转向多 品种中小批量生产。 2 第一章绪论 多品种中小批量生产的特点是生产的产品品种较多，生产具有重复性，每个 品种的产量不大，都不能维持常年连续生产，所以在生产中形成了多种产品轮番 生产的局面。由于生产的品种多、生产的稳定性差。所以要建立正规的生产线和 流水线的难度较大，所以无法采用高生产率的专用生产设备和工艺装备，专业化 程度不高，生产率较低。但可以建立多品种的对象生产单元，使工件的生产过程 可以基本上在生产单元内封闭地完成。 多品种中小批量生产在社会生产总量中所占的比重日益增大，世界机电产品 中属于中小批量生产的产品种数由2 0 世纪6 0 年代占5 0 左右，到2 0 世纪9 0 年 代占7 5 ，产值由4 5 上升为7 5 。我国机械制造企业属于中小批量生产的占总 数的9 5 左右，多品种中小批量生产已成为当今社会上的主要生产类型。 多品种中小批量生产的产品是结构相似的系列产品，品种较多，客户的选择 余地大，灵活性高，满足客户的多样性的需求，适应市场竞争的需要1 3 。 1 1 3 多品种中小批量生产实施的有效手段 混流装配线是实现多品种中小批量生产的有效的实施手段。混流装配线( a m i x e d m o d e la s s e m b l yl i n e ，m m a l ) 是在j i t 的背景下发展起来的，是指进行产 品特性相似的不同产品类型混合生产的装配线。它可以在一定的时间内，在同一 条生产线上生产出不同类型的产品。它的出现可以降低库存，满足顾客的多样化 与个性化需求，缩短产品的上市时间，提高企业的竞争力。混流装配线十分符合 现代生产的需求，符合多品种中小批量生产方式的生产目的。近二三十年来，混 流装配线在日、美、欧等发达国家已经被广泛采用。 在汽车、家电等行业中，在它的各个零部件加工或采购完成后，必须进行多 个层次的装配操作，并在总装线上完成其最终产品的生产。生产这些产品的企业 中，相当一部分的重要资源，如人力、设备、物料、资金等，都是围绕着装配线 进行活动和增值的。装配线的重要作用在制造企业中是不可替代的，也是至关重 要的。据统计，制造业中约有1 1 - - - 4 0 的熟练劳动力被装配作业占用，装配作 业成本约占3 0 - - , 5 0 的制造成本1 4 。为解决用户需求个性化产生的产品多样化问 题，越来越多的企业选择能够进行多品种混合生产的柔性生产线，特别是以装配 为主的企业，则更需要一种能够进行多品种混合装配的流水线。 广东工业大学硕士学位论文 1 2 研究意义 随着我国加入w t o ，国内品牌要和国外品牌进行同台竞争，使得我国制造业 市场的竞争更加激烈。我国的制造行业拥有生产成本的优势。这主要是由两方面 的因素造成，一是国内劳动力成本比较低廉，二是在积累了大批量生产的经验之 后，国内制造企业已经具备了组装生产的优势。 。 但是我国的制造业普遍存在着两个明显的缺点： ( 1 ) 核心技术缺乏自主开发能力目前虽然我国有部分企业具有一定的核心 技术开发能力，但总体上来说，我国大部分制造企业技术水平低，生产的产品属 中低档产品，即使高档的产品，其核心技术和关键设备都是从国外进口。可以说， 我国制造业缺乏核心技术自主开发和设计能力，而制造业在技术开发上与发达国 家之间的巨大差距不可能在短期内缩短。 ( 2 ) 产品缺乏多样化、个性化设计当今市场中，人们己不满足于从市场上 买到标准化生产的产品，他们希望得到按照自己要求定制的产品或服务。多样化、 个性化成为世界市场的潮流。国外不少企业的产品是根据客户的需求进行生产的， 一些产品无论从外部造型还是内部功能处处都体现着客户的多样化、个性化的设 计理念，而我国企业所生产的产品大多数还是标准化生产，产品缺乏多样化、个 性化的设计。面对多样化的产品生产，过去一条生产线只能生产一种产品的生产 方式已经不能满足当今市场的需求，而必须使一条生产线能生产出几十种不同型 号的产品。 随着金融危机的到来，出口率下降，企业利润空间进一步收缩，我国制造业 面临的形式越来越严峻。要立足于竞争激烈的市场中，我国制造行业就要进一步 提高企业的竞争优势。虽然我国许多企业已经才用了多品种中小批量的生产方式， 但灵活性还远不能满足市场的需求。 由于最终产品是在装配线上生产完成的。装配线是多品种中小批量生产方式 中十分重要的一环。我国的企业虽然采用的装配线是可以在同一条生产线上进行 不同产品的生产，但是多是采用轮番生产的方式来组织生产。轮番生产就是在一 条生产线上先生产一批同样的产品，然后再生产另外一批相同的产品。轮番生产 会导致在制品库存增多、物料消耗情况不均匀，排在后面生产的产品的交货期延 长等问题，使得企业的库存成本上升，交货时间延长，不能快速的响应市场的要 4 第一章绪论 求。 我国的制造行业核心技术缺乏自主研究能力，而这一差距是不可能在短期内 缩短的，那么要和国外品牌竞争就只能选择在时间上进行竞争。混流装配线是在 同一条装配线上，根据客户订单的需求，将产品结构与装配工艺过程相似的不同 产品进行相互交替装配。由于不同类型的产品同时进行生产，这样就降低了在制 品库存，多种产品所需的零部件消耗比轮番生产均匀，缩短了产品的交货期，大 大提高了企业的灵活性与企业的市场快速反应能力。混流装配生产出来的产品是 根据客户的需求制造的，该生产方式能克服我国制造行业的缺乏多样化、个性化 的缺点，能够满足客户的不同需求，适应当今买方市场的特点。因此，采用混流 装配的方式组织生产更有利于企业的发展。 组织多品种混流生产的关键是实现生产的“平准化 ，平准化的核心是混流装 配线产品投产顺序的最优化。即：指产品被安排到装配线之前要人为的按照加工 时间、数量、品种进行合理搭配和排序，使得安排到装配线中的工件具有加工工 时上的平稳性，保证均衡生产，同时在品种和数量上实现混流加工运动，起到对 市场多品种、小批量需求的快速反应和满足功触1 。所以通过对混流生产线的投产 排序问题进行研究，可以更好地发挥混流装配生产方式的优势。 1 3 混流装配线排序问题国内外研究现状 w e s t e r 和k i l b r i d g e 于1 9 6 3 年首先研究了混流装配线的排序问题。几十年来， 学者们对这个问题进行了大量的研究，并取得了不少成果。对于混流装配线的排 序问题，学者们主要从目标函数的优化与排产方法的优化两方面进行研究。 1 3 1 混流装配线排序问题优化的主要目标 混流装配线上的排序问题，其目标函数根据不同的研究目的而不同。这些优 化目标并不是其中某一个优化目标一定优于另外一个优化目标，只是根据企业不 同的需求设定不同的优化目标。目标函数可以可归纳为下面几类： 1 负荷均衡化保证工作站的负荷均衡化，不仅可以使生产畅顺，提高劳动 生产率，而且可以提高产品的质量，从长远的观点来看，可以增强企业竞争力， 增加企业的利润。该目标函数在数学上有如下几种形式：最小化最大作业完成点、 最小化最大作业起始点、最小化总的作业范围、最小化总的未完成作业量等等。 如文献 5 6 】以最小化总的未完成作业量为目标函数。 5 广东工业大学硕士学位论文 该目标函数为【5 1 ： r a i n u i ， ( 1 1 ) 式中，阢。为工作站s 上第f 个模型的未完成作业量。 u ，= m a x ( o ，s t ，+ 蹈加五肚+ 。，一正，。) ，s ，：模型f 在工作站s 的开始作业时 间，s 乃f ，：。模型f 在模型，后立即投入到工作站s 的准备时间，：模型i 在工作 站s 的加工时间；互，：模型i 在工作站s 的完成时间：五j j 0 ，1 ) ，其中1 表示排 在第，个位置上的产品是第f 种产品，否则为0 。 2 各零部件的使用率均匀化混流装配线正常运转的一个关键前提是生产的 均衡化和同步化。各零部件的使用速率均匀化能减少供应零部件的各工序产量以 及运送量的变化，降低在制品的储存量，保持均衡生产。文献【7 1 2 】都使用了这 个目标函数。目标函数为【7 】： r a i n ( 一一岛吐p ) 2 x ( 1 2 ) 式中：f ：产品数的标号；疗：需要装配的产品数：m ：装配线上需要的零部 件种类总数；p ：生产排序中子装配的标号；j ：产品排序位置的标号；d ：在一 个生产循环中需要组装的各种产品的总和；谚：在一个生产循环中产品f 的数量； ：生产每种f 产品需要的零部件p 的数量；x 声 o ，1 ) ，其中1 表示排在第个位 置上的产品是第f 种产品，否则为o ；口p = z d ：零部件p 的理想使用速率； 岛- l p ：前一1 个产品消耗零部件p 的数量和：历，p = 乃- l ，+ b 并且磊，= o 。 3 最大化相似度基于关键件相似目标的排序，可使装配序列中相邻产品的 相似度最大化，即让关键件相同的产品在生产时尽可能排在一起，这样就可以减 少装配中关键件的变化次数，达到降低错装、漏装概率的目的。文献【1 3 1 5 】使用 了这个目标函数。 目标函数为0 4 】： 烂， m a x 正，) = s ( a f ，o l + 1 ) ( 1 3 ) 式中，z ，1 ：可连续装配相同关键件的次数，m ：产品的总数：f ：产品排序 序号；s ( 口，) ：口与的关键件相似度。其中s ( a ，) = c ( ，尾) ，n ：关 键件属性总数；和尾分别表示口和的第甩个关键件属性；c ( ，尾) ：和 尾相似度，如果c ( ，尾) = l 则表示= 尾，否则不相似。 6 第一章绪论 4 传送中断时间最小化减少传送带中断的时间和次数，能保持生产稳定、 畅顺，提高产量。文献 1 6 2 1 以此为目标函数。 目标函数为m ： 幽m a x e 【厅袅。) + f 扣。一r 】，0 ) ( 1 4 ) 式中：峻。) ：作业域七对投入顺序秒中第疗个模型的作业起点；呓( 。) ：作业域 七对投入顺序口中第刀个模型的作业时间：r 为作业域七( k ) 的长度。 5 最小化成本排序中发生的费用有：) j - v 费用、工人费用、在制品库存费 用等，成本的最小化实际上是说明了生产的最优化。文献 2 2 2 3 是以最小化成本 为目标函数。 目标函数为瞄】： mm 曲c = q - ， ( 1 5 ) 式中：c ，是第f 类安排在第时段上线生产产品承担的费用。工u o ，l ，其 中1 表示第f 类安排在第，时段上线生产，否则为0 。 6 多目标组合实际生产中，企业有不同的需求，因此多目标组合更适合实 际的生产。文献 2 4 】以每个工作站负荷平衡与最小零部件消耗量不均衡率为目标函 数。文献 2 5 】提出最小化准备时间与最小化零部件消耗量不均衡率两个目标函数作 为研究对象。文献【2 6 】提出负荷平衡、物流平准化和产品相似度3 个优化目标的优 化问题。文献【2 7 】提出最小过渡距离总和、最小起始距离总和与零部件消耗率均衡 为目标函数。文献【2 8 的目标函数则是最小化生产周期时间、最小化工作站闲置与 超载时间以及最大化平均负荷率。文献 2 9 3 1 】提出了混流装配线的三个目标函数： 最小化额外工人工作量、最小零部件消耗量不均衡率、最小化调整切换时间。 1 3 2 混流装配线排序问题的优化方法 1 最优解算法最优解算法指对特定的调度目标，能在多项式时间内得到最 优调度的一类算法，该方法较常见的有分支定界法、动态规划法等。 文献【3 2 】用分枝界定法解决目标函数为极小化加权完工时间和的f l o ws h o p 排 序问题。文献 3 3 】以最小化最大完成时间为目标函数，提出了一种新的分枝界定法 的下界算法，提高了计算的速度与剪枝的效率。文献【3 4 】针对面向团队的装配系统 的多目标设计问题，提出了一种基于返回式分枝定界算法的优化方法。文献【2 l 】 用分枝界定法对最小化停线时间为目标函数的排序问题进行计算，得出分枝界定 7 广东工业大学硕士学位论文 法对于小规模排序问题有较好的效果。文献【3 5 】运用分支界定法去解决混流装配线 的问题。 文献 3 6 】以线性规划思想提出了一套快速实现车间最优动态排序的方法，以延 迟时间最小化为目标函数，实现了车间最优动态排产。 虽然最优解算法从理论上能得到最优解，属于精确求解方法，但通常计算量 过大，实际应用中有许多困难。主要原因是：最优解算法需要对排序问题进行统 一建模，任何参数的变化都会使算法的重用性变差。而混流装配线的投产排序问 题是n p h a r d 问题，实际中的许多因素不能完全形式化，通常需要对原问题的数 学模型作简化处理，单一的数学规划模型存在求解空间大、计算困难、可能丢失 最优解等问题，因而不能很好的解决问题。其次，该算法随着问题规模的扩大， 会发生组合爆炸，而混流装配生产方式生产的产品有很多种，以致该算法很难用 来求解混流装配线的排序问题；所以用最优解算法至多只能对极小规模的投产排 序问题求得最优解。 2 仿真方法当排序问题比较复杂时，数学模型可能非常复杂，计算量大， 也可能出现无解的情况。这时候，仿真排序是一个不错的并且较为实用的解决方 案。仿真主要是通过计算机模拟现实生产环境，对可能的生产计划和排序方案在 计算机上虚拟仿真，比较计算结果，寻求最优方案。 文献 3 7 】用e m p o w e r 的平台建立了轿车总装车间的底盘工段与分装工段部分 工位仿真对象模型及控制逻辑，该混流轿车总装配线仿真系统能对设计结果进行 快速的验证，为管理者提供较好的决策依据。文献 3 8 1 根据汽车总装线规划的要求， 提出并建立了一个相应的规划仿真环境，该环境包括仿真界面、优化工具、模型 库以及数据库。文献 3 9 1 结合构建的变速箱装配线车间的虚拟仿真模型，对装配线 进行了虚拟装配仿真，结合实际仿真数据对虚拟装配线的规划进行了优化和调整， 在多次仿真和优化调整后，找出了解决装配线存在问题的方案，并实施了重新仿 真，得出了较理想的装配线平衡和优化方案。文献 4 0 l 基于面向对象建模理论，在 f l e x s i m 仿真平台基础上对混流生产线上不同的投产顺序进行仿真，为不同排产顺 序得出了仿真结果。文献【4 l 】对汽车混流装配线进行统一的面向对象的仿真建模， 对混流装配系统进行了建模与仿真，同时实现了投产序列仿真和优化。实例表明， 采用面向对象的方法，集成各种模型库、算法库建立混流装配线三维虚拟仿真系 统进行仿真优化比传统的建立数学模型来仿真优化更加可行。文献 4 2 】介绍了常用 8 第一章绪论 的f m s 仿真建模方法，并分析了其特点。提出了结合活动循环图a c d 法，利用 e m - p l a n t 软件进行离散事件仿真的建模方法。针对某汽车变速箱柔性生产线，建 立了f m s 仿真模型，并对不同的调度策略进行了仿真。 由于制造系统的复杂性，很难用一个精确的解析模型来进行描述分析，而通 过对仿真模型的运行收集数据，就能对实际系统进行性能、状态方面的分析，从 而能对系统采用合适的控制排序方法，但仿真也存在以下问题：缺乏理论意义； 应用仿真进行生产排序的费用很高；仿真的准确性很大程度受编程人员的判断和 技巧的限制。而且混流装配线系统是典型的离散事件系统，实际生产中有很多随 机的、不确定性因素，在这方面还有待进一步研究。同时优化算法方面的集成以 及优化过程的展示和可视化还可进一步完善。 3 人工智能方法由于排序问题是n p 难问题，应用传统的方法很难能够在可 接受的时间内找出问题的最优解，于是人们倾向于针对具体的组合优化问题设计 算法，以求在尽可能短的时间内找出尽可能好的解，就是通常所说的次优解。这 是一个突破性的思想，在这个思想的指引下，大量的近似求解具有n p 难度的组合 最优化问题的算法随即涌现出来，便出现了大量的智能算法优化调度问题。人工 智能方法是一种启发式算法，该类算法的一个主要特征就是牺牲求解结果的精确 性换取求解的效率，因而通常不可能在每次执行算法时都得到问题的精确最优解， 往往只是不断的逼近问题的最优解。这个特点决定了仿生进化算法在求解实际问 题的过程中有很大的调整余地，而对算法的调整主要就体现在参数的具体选择上。 人们针对智能方法的有的，提出下面的一下优化算法。 ( 1 ) 遗传算法 基本遗传算法s g a s g a 是一种统一的最基本的遗传算法。文献【1 3 ，4 3 4 7 】都是运用基本遗传算 法来解决混流装配线的排序问题的。其结果表明s g a 要优于传统的算法。 改进遗传算法 s g a 虽然要优于传统算法，但是还存在参数的选择有待进一步研究、对于超 大规模的优化问题不太适用、容易陷入早熟收敛或收敛缓慢、爬山能力差等缺点。 针对遗传算法的弱点，众学者采取了不同的方法进行改进，主要途径概括起来有 两种：一、改进遗传算法的组成成分、使用技术；二、将遗传算法与其他智能优 化算法结合。 9 广东工业大学硕士学位论文 a 第一类改进遗传算法 文献 2 】选用了锦标赛选择算子以避免收敛到局部最优解，变异算子使用了非 标准的旋转算子和移位算子两个算子相结合的变异方法保证了群体中个体的多样 性。文献【2 2 采用矩形交叉方法进行二进制二维编码，分别在两个父代矩阵中选取 随机选择相同位置的一片矩形区域进行互换，该方法提高了遗传算法的收敛速度。 文献【4 8 】提出利用分布种群遗传算法求解车间调度问题，该算法将要寻优的空间划 分成若干不相交子空间，不断对各个子空间进行划分寻优，达到在较小的范围做 精细搜索，在不牺牲搜索广度的情况下增加了搜索得深度，从而提高了算法寻优 的效率。 b 第二类改进遗传算法 文献【4 9 】针对混流装配线排序问题，提出一种混合遗传禁忌搜索算法g a t s ， 在每一代遗传演化之后，按一定比例随机选择部分解进行禁忌搜索，此算法延缓 或避免了遗传算法早熟收敛的发生，提高了遗传算法的爬山能力，具有更好的全 局搜索能力和收敛性能。文献【5 0 】提出了结合遗传算法g a 和模拟退火算法s a 的 混合遗传算法g a s a ，两种算法的混合使s a 成为并行s a 算法，提高其优化性能； 同时，s a 作为一种自适应变概率的变异操作，增强和补充了g a 的进化能力。该 混合算法丰富了优化过程中的搜索行为，增强全局和局部意义下的搜索能力和效 率。 ( 2 ) 蚁群算法 蚁群算法是由意大利科学家d o r i g o 研究总结出的一种新型的仿生启发式优化 寻优算法。该算法仿照蚂蚁群觅食机理，构造一定数量的人工蚂蚁，每个蚂蚁根 据路径上的荷尔蒙强度大小选择前进路径，并在自己选择的行进路径上留下一定 数量的荷尔蒙进行荷尔蒙强度的局部更新。当所有蚂蚁均完成一次搜索后，再对 荷尔蒙强度进行一次全局更新。通过反复的迭代，最终大多蚂蚁将沿着相同的路 线，即最优路线完成搜索。 文献 1 0 ，1 6 1 8 用蚁群算法进行运算，解决了混流装配线的调度问题，得到 了优于分支定界法、模拟退火法和遗传算法的可行解。 研究结果已经表明，蚁群优化算法具有很强的发现较好解的能力，在很少的 迭代次数内可以搜索到较好的解；具有分布式计算、易于与其它方法相结合、鲁 棒性强等优点；而且当运算规模较大时，蚁群算法要比遗传算法好。 1 0 第一章绪论 但是蚁群算法同样有一些缺点：缺乏有效的数学模型和通用的理论范式；初 期信息素匾乏，需要较长的搜索时间；由于蚁群算法的每一次循环都是一个相对 独立的过程，后一次循环的蚂蚁得到的解并不能保证是出现在原有解的领域上， 因此不易进行局部搜索。 为了解决蚁群算法的缺点，学者们提出了一些改进的蚁群算法。 文献 5 1 】针对蚁群算法易陷入局部最优解，提出了一种新的信息激素更新方 法，引入了径向基函数l 通f ，利用r b f 良好的局部性，遴选一部分蚂蚁对路径上 的信息素进行更新，从而加快收敛速度，并减少停滞现象的发生。实验仿真表明， 这种改进是成功的。文献【5 2 】提出了一种蚁群系统与遗传算法融合的算法。将遗传 算法加入到蚁群系统的每一次迭代过程中，利用遗传算法全局快速收敛的优点来 加快蚁群系统的收敛速度；并且遗传算法中的变异机制帮助提高了蚁群系统跳出 局部最优的能力。结果表明新算法在求解时间和求解质量上都取得了很好的效果。 ( 3 ) 模拟退火算法 基本模拟退火算法 文献 5 3 】以零部件消耗率均匀为优化目标，建立了混流生产线投产排序数学模 型，并运用模拟退火算法对该问题进行求解。通过算例比对，该方法在求解质量 上优于目标追迹算法，从而证明模拟退火算法是一种能够有效解决混流生产线投 产排序问题的新方法。文献【5 4 】提出了一种适用于多产品间歇化工过程排序的改进 模拟退火算法，该算法采用了非平衡、多次退火策略及多个相邻解产生方法。研 究表明，同已有的方法相比，该方法求解精度高，计算速度快。文献 5 5 】结合了 模拟退火算法与n s g a 算法的优点。在解决多目标的问题上，提出了新的精英策 略的多目标模拟退火算法。为了保证解的收敛性与多样性，运用快速非支配排序 和密度比较算子，并利用精英策略，保存最优解。对新算法加以实现，最后对其 结果进行评价。结果表明在解决小种群与简单问题上，它的优势明显，能更逼近 p a r e t o 最优解，而且能较均匀的分布。其不足之处在于，没有很好的利用到模拟退 火的优势，跳出局部最优，使得在大种群问题上，解的收敛性与多样性与n s g a 相比并没有什么突破。文献【5 6 】从供应链角度来讨论准时制系统中混合装配线的排 序问题，针对产品产出的速率和零件消耗率的排序目标，建立了物料供应速率平 准化的目标和数学模型，运用模拟退火方法来设计混合装配线的投产排序算法。 最后给出一个排序的实例，证明了模拟退火算法的搜索结果优于目标追迹算法。 广东工业大学硕士学位论文 模拟退火算法计算时间较长，所以学者们将模拟退火算法与其他算法结合得 到改进模拟退火算法。 改进模拟退火算法 文献【5 7 】为解决多个零部件在多个工作中心上进行不同的工序加工时的调度 排序问题，生成较优的作业排序计划，提出了自适应算法、模拟退火与遗传算法 相结合的混合遗传算法等优化的算法。通过简单、方便地操作，迅速生成作业排 序的优化结果，解决了多个零部件在多个工作中心上的加工调度问题，从而提高 了生产率，降低了生产成本。文献【5 8 】结合模拟退火算法概率突跳特性和遗传算法 群体并行搜索能力，给出一种同时处理一类批量可变的流水线调度问题中批量和 排序的快速有效的混合优化策略，同时算法动态缩小搜索空间以提高搜索效率并 具有保存优良解的特点。另外，利用可重升温的技术以保证算法具有更好的局部 极小突跳能力，仿真结果说明了混合策略的有效性和快速良好的搜索能力。 ( 4 ) 粒子群算法 基本粒子群算法 文献 5 9 6 0 】运用了p s o 算法来解决动态车间调度问题，快速的得到了很好的 排序结果，表明p s o 在该问题上的应用十分有效。 改进粒子群算法 如何使p s o 避免早熟收敛，加快收敛速度，一直是研究的热点和重点。通常 采用的策略可分为两类：一类是通过对参数的调整，从而使p s o 得到改进；一类 是引入其他优化算法的优点进行改进。 a 基于参数调整的粒子群算法 基于参数的调整策略实现简单，使用广泛，对大多数问题效果较理想。 文献 6 l 】提出了一种2 维粒子表示方法，通过对粒子位置向量进行排序生成有 效调度，并采用粒子位置向量多次交换的局部搜索方法来提高算法的搜索效率。 文献【6 2 】采用三维粒子表示法，同样运用文献【6 1 】的搜索策略来提高算法收敛精度。 文献 6 3 】针对p s o 对于参数的依赖性，提出用混沌优化策略对p s o 的参数进行自 适应优化和改善算法搜索性能，并且通过实验证明了算法的可行性与有效性。 b 混合粒子群算法 为了进一步提高p s o 的基本性能，许多研究者还尝试了将其与其它智能计算 方法相融合，以突破其自身局限的混合型方法。不少学者们提出了基于遗传算子 1 2 第一章绪论 的p s o 算法。该算法的基本思想是利用p s o 算法每次迭代的最优粒子位置及最优 粒子速度为基础进行变异，然后对变异前后的粒子的分量进行随机交叉操作从而 产生新一代粒子群。相当于在种群更新时进行了再一次筛选，从而减少迭代次数， 加快收敛速度。这种算法实现简单。 文献 6 4 1 提出一种基于遗传交叉因子的改进粒子群优化算法( g h p s o ) ，通过自 适应变化惯性权重来改善算法的收敛性能，通过引入交叉因子增强群体粒子的优 良特性，减小了算法陷入局部极值的可能，提高了全局搜索能力和收敛速度，改 善了优化性能。文献 6 5