（机械电子工程专业论文）混合装配线平衡问题研究与系统实现.pdf

摘要 摘要 现代化大生产中，混合装配线的产生是为了满足顾客多样化和个性化的需要， 增强对市场的适应性。而混合装配线的平衡过程可以实现一种劳动生产率、设备 利用率和满足市场需求三者之间的平衡的过程。本文对在多品种小批量制造环境 下的混合装配线平衡问题进行了系统地研究。运用数学模型和智能优化算法来研 究混合装配线平衡，考虑到算法在实际中难以应用的问题，开发了混合装配线平 衡系统。 首先，根据平衡目标的不同，系统地设计了不同目标的数学模型，来解决多 品种小批量制造环境下的混合装配线平衡问题。这些混合装配线平衡的数学模型 改进了文献中提出的混合装配线平衡的模型，针对不同目标的装配线平衡问题的 适应性好，为混合装配线的平衡设计与生产管理提供了理论指导、方法和工具。 其次，分别设计了混合装配线平衡问题不同数学模型的算法；在遗传算法设 计中对以下方面作了改进：研究了初始种群的产生问题；设计了独特的染色体编 码规则、译码规则：在遗传操作设计中，设计遗传算子进行操作后反复检验。分 析遗传参数对改进遗传算法性能的影响，比较不同规模的问题的算法执行时间， 初步说明该算法性能良好。 最后，设计了混合装配线平衡系统，构造了作业、工作站、产品、生产线等 对象，实现了通过有向图来建模的方法。有向图很好地描述了作业之间的先后顺 序约束关系，所以用户能够很容易地对问题进行描述和修改。把设计的算法编译 为算法库以实现混合装配线的平衡优化，平衡结果通过图形的方式显示出来。在 本文最后用实际工程的数据对系统进行了验证。 关键词：混合装配线；平衡：建模；遗传算法 广东_ t 业大学工学硕士学位论文 a b s t r a c t a sc u r r e n tm a r k e t sa r ec h a r a c t e r i z e db yag r o w i n gn e i l df o rh i g h e rp r o d u c t v a r i a b i l i t y , m i x e d - m o d e la s s e m b l yl i n e s ( m m a l ) a r ep r e f e r r e do v e rt h et r a d i t i o n a l s i n g l e - m o d e la s s e m b l yl i n e s f o rm m a l ，i ti sd e s i r a b l et h a tt h el i n eb eb a l a n c e d b a l a n c i n gt h ea s s e m b l yl i n em e a n st h a tw o r k s t a t i o n si nt h el i n ea l er u n n i n ga tt h es a l n e p a c ew i t h o u ta n yi d l et i m e t h em a i no u t c o m e so ft h i st h e s i sw o r ka l e ，f i r s t l y m a t h e m a t i c a lm o d e l sa r eu s e d t od i s c u s st h em i x e d m o d e la s s e m b l yl i n eb a l a n c i n gp r o b l e m ( m m a l b p ) v a r i o u s o b j e c t i v e sa n dv a r i o u st y p e so fm i x e dm o d e la s s e m b l yl i n eb a l a n c i n gp r o b l e m sa r e m o d e l e d t h e s em o d e l so v e r c o m et h eh m i t a t i o n so ft r a d i t i o n a lm a t h e m a t i c a lm o d e l s a n da l s op r o v i d es o m eg o o dm e t h o d o l o g ya n dt o o l sf o rp r o d u c t i o nm a n a g e r s s e c o n d l y , ad e s i g no fg e n e t i ca l g o r i t h m sa s s o l u t i o n st ov a r i o u st y p e so f m m a l b pi sp r o p o s e di nt h i st h e s i s i nt e r m so fs o l v i n gm m a l b p , g e n e t i ca l g o r i t h m s a r ed e s i g n e df o rt h ed i f f e r e n tm a t h e m a t i c a lm o d e l s t h eg e n e t i ca l g o r i t h m sa r e m o d i f i e do nt h r e ep l a c e s ：t h ep r o d u c t i o no fi n i t i a lp o p u l a t i o ni ss t u d i e d ；au n i q u e ， p r a c t i c a la n ds i m p l ep r i n c i p l ef o rg e n ee n c o d i n ga n dd e c o d i n gi sd e v e l o p e d ；g e n e t i c a r i t h m e t i co p e r a t i o n sa r ed e v e l o p e df o rm i x e d m o d e la s s e m b l yl i n eb a l a n c i n g f i n a l l y , ad e s i g no fam i x e dm o d e la s s e m b l yl i n eb a l a n c i n gs y s t e mi sp r e s e n t e d i na d d i t i o n , p r e c e d e n c ed i a g r a mm o d e l i n gi si m p l e m e n t e dt h a tm o d e l st h ec o n s t r a i n t s o ft h et a s k si nam i x e d m o d e la s s e m b l yl i n es ot h a tt h eu s e rc a nd e s c r i b ea n dm o d i f y t h em o d e le a s i l y t h es y s t e mc a l l sa l g o r i t h m sw h i c ha r ec o m p i l e dt ol i b r a r i e st oo b t a i n b a l a n c i n gr e s u l t s w h e r eas o l u t i o ni sf o u n d ，i tc a l lb ed i s p l a y e dg r a p h i c a l l y t h e s y s t e mi st e s t e du s i n gp r a c t i c a lp r o j e c td a t a k e y w o r d ：m i x e dm o d e la s s e m b l yl i n e ；b a l a n c i n g ；m o d e l i n g ；g e n e t i ca l g o r i t h m 广东工业大学t 学硕士学位论文 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含他人已经发表或撰写过的研究成果，不包括 本人或其他用途使用过的成果。与我一起工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 卅7 指导老师签字：孑 论文作者签字： 弘叶 砂3 年f 月秒e t 第一章绪论 1 1 课题研究的背景 第一章绪论 现代化大生产中，在大量生产的情况下，流水生产线由于能将高度专业化的 生产和劳动对象的平行移动方式结合起来，是一种较好的被广泛采用的生产组织 形式。现代流水方式起源于福特制。福特于2 0 世纪2 0 年代创立了汽车工业流水 线，揭开了现代化流水生产的序幕，引发了制造业的一个根本变革。应用流水线 生产能使生产过程较好地符合连续性、平行性、比例性以及均衡性的要求；可以 提高劳动生产率，缩短生产周期，减少在制品占用量和运输工作量，加速资金周 转，降低生产成本；还可以简化生产管理工作，促进企业加强生产技术准备工作 和生产服务工作。但是这种福特式的生产方式，在通常情况下，一半时间人员和 设备、流水线等待零件，另一半时间等待零件一运到，全体人员总动员，紧急生 产产品。这种生产方式造成了生产过程中的物流不合理现象，尤以库存积压和短 缺为特征，生产线或者不开机，或者开机后就大量生产，从而导致了严重的资源 浪费i l l 。 2 0 世纪8 0 年代以来，出现了“准时制生产方式( j i t ) 的生产模式，j i t 的 核心是追求一种零库存的生产系统，或使库存达到最小的生产系统。其基本思想 可概括为“只在需要的时候，按需要的量生产所需的产品，然后对设备、人员等 进行淘汰、调整，达到降低成本、简化计划和提高控制的目的。为此，开发了包 括“看板 在内的一系列具体方法，并逐渐形成了一套独具特色的生产经营体系。 它将传统生产过程中前道工序向后道工序送货，改为后道工序根据“看板向前 道工序取货，把推动式的控制方式改为拉动式。j i t 将“获得最大利润 作为企 业经营的最终目标，将“降低成本 作为实现最大利润的基本目标。在福特时代， 降低成本主要是依靠单一品种的规模生产来实现的。但是在多品种、中小批量的 情况下，这种方法是行不通的。因此，j i t 力图通过“彻底消除浪费 来达到这 一目标。正是因为j i t 生产模式的出现，使得传统的制造业模式由少品种、大批 量单一品种流水线生产模式向以满足客户需要为前提而又不增加库存量的多品 广东工业大学工学硕士学位论文 种、小批量混合装配线生产模式转变。 混合装配线( m i x e dm o d e la s s e m b l yl i n e ，m m a l ) 这种类型装配线生产，可以 在一定时间内，在一条生产线上生产出多种不同型号的产品( 同一产品族) ，产品 的品种可以随顾客需求而变化。 多品种小批量混合生产的产生是为了满足顾客多样化和个性化的需要，增强 对市场的适应性。由于这种生产是一种低效率、不易实施自动化的生产方式，因 此，到目前为止，一般是由中小企业和个体企业采用这种生产方式。但至今，除 了少数特殊行业外，很多大型企业也不得不开始采用这种生产方式了。在一贯以 大批量生产为特征的汽车制造厂，现在也发展到在总装配线上流出的是款式、色 彩、内部装饰各不相同的车子，形成混流生产方式。据统计，目前包括单体生产 和小批量生产的多品种小批量生产方式，己占到8 5 t n 。混合装配线与单一装配 流水线相比，它具有更高的灵活性，线上的工作站可变性大，适应性高，有助于 提高产品质量，使得企业对市场的快速反应不在依赖成品库存，提高企业对市场 环境的快速反应能力，实现j i t 的目标，】。 近二三十年来，混合装配线在日、美、欧等发达国家已被广泛采用。最先应 用于汽车工业，如丰田汽车公司的c o r o n a s 生产线上可以生产4 0 0 0 多种类型的汽 车，每种车型的发动机、变速机、加速器、空调、车门或其他部件均不同 4 1 。现 在混合生产的应用逐渐扩大到同样是系列化生产的电子产品、家电甚至服装产业。 而目前在国内汽车厂家基本上以单一车型为主来排产，家电行业的混合生产更是 处于萌芽阶段，预计不久的将来我国这两大工业必然会向多种产品混合生产的方 向发展，开发复杂的混合生产装配线。 1 2 研究混合装配线平衡问题的必要性 混合装配线的设计目标是使生产保持一种均衡、连续的流动状态，减少工作 站的闲暇时间，提高人员和设备的利用率 5 1 。 混合装配线的设计分为两类：逻辑设计和物理设计。混合装配线的逻辑设计 主要包括两个方面的内容： ( 1 ) 混合装配线的平衡问题( m i x e dm o d e la s s e m b l yl i n eb a l a n c i n gp r o b l e m ) ， 集中于生产资源的分配方面； 2 第一章绪论 ( 2 ) 投产排序( m i x e dm o d e la s s e m b l yl i n es c h e d u l i n gp r o b l e m ) ，即排产问题， 集中于生产资源的利用与市场需求的快速响应方面。 设计混合装配线的基础和关键在于通过各种技术组织措施，将基本的作业元 素分配到工作站，满足特定的目标和约束条件，也即是平衡混合装配线。避免在 生产过程中产生瓶颈以至于造成成品生产线停顿和不必要的库存堆积是平衡的目 的。整个生产过程的组织是否合理，对于产品的产量、质量和成本都有很大的关 系，要想使混合装配线发挥其特别的作用与效用，必须要研究混合装配线的平衡 问题。 企业刚刚投产时，所建立的装配线一般都是比较平衡的，但是随着市场的变 化，引起产品需求产量的变化，往往会造成装配线不平衡。在混合装配线中造成 不平衡现象的原因很多，归结起来可以分为以下几个方面【6 1 ： ( 1 ) 产量与产品配比的变化对于混合生产而言，为了顺应市场的需求产量 和产品的配比是不断变化的，例如原来生产产品a 、b 和c 的比例为3 0 、4 0 、 3 0 ，后来调整产品比例为4 0 、2 0 、4 0 ，很可能原来平衡的装配线现在会 出现瓶颈，或者原来的瓶颈位置发生了漂移，因而原来平衡的各工位可能在产量 和产品配比发生改变之后，出现不平衡的现象。 ( 2 ) 产品配置设计的改变以及新型产品的投入由于产品设计和配置或需要 根据用户的要求随时进行调整。比如，家电中的空调产品，某些顾客需要大功率 产品，而另一些顾客需要节能、环保产品。有时生产工艺的调整对装配线的平衡 影响很大的，但是在实际生产中往往工序的安排不可能在短时间内进行合理的安 排最常见的情况是新的任务分配下来之后，生产线只是在原来工序分派方案的基 础上只作有限的调整便开始生产，因此生产线不平衡的问题就暴露出来了。 ( 3 ) 操作工对工作的熟练程度的变化操作工对工作的逐渐熟悉，使得他这 个工位的操作时间相对减少了；或者一些复杂的工序被换成新手操作，使得操作 时间增加。如不做适当调整，很可能引起装配线的不平衡。 ( 4 ) 现场布置l a y o u t 的改变生产中存在七大浪费：不良品；超量生产； 库存；搬运；多余的工序；不必要的调动；等待。其中不必要的调动即现场布局 的改变，常常是不易察觉，却会影响操作时间，因此造成装配线不平衡。 ( 5 ) 原料设备工装及操作工对生产线平衡的影响 在实际生产中，很多情况 广东工业大学工学硕士学位论文 都会导致生产线不能顺畅的运行，从而造成暂时性不平衡现象发生。例如，原材 料的供应，设备、夹具的故障，人员的操作失误等以上这些原因都会造成操作时 间增加，甚至不得不使生产线停滞，因而也是造成生产线不平衡因素。 生产线的柔性以及需求的变化增加了生产的复杂性和不确定性。这对于生产 线的平衡问题而言，意味着必须随着需求的改变、产品配比的变化以及其他因素 随时调整生产线的平衡。这就是动态的和不确定性的因素。在实际生产中，生产 线的改善是一项持续不断的工作，而人们往往忽略动态平衡的重要性。那是因为 以前的生产线并非是柔性的，这就无所谓产品配比的变化。只要在生产之初进行 平衡以后，便可一劳永逸了。但是引入多品种混合生产之后，装配线的柔性增加 了，我们必须把持续的改善工作与动态平衡结合在一起，才能够跟上生产的需要。 目前，混合装配线在工业生产中得到越来越广泛的应用，而平衡问题是混合 装配线设计要解决的关键技术。因此本课题的研究将会给企业应用混合装配线带 来很大的帮助。 在过去的几十年里，混合装配线平衡问题的研究主要是理论研究一数学建模 和算法。所建的模型和算法有一定的局限性。本文从新的角度提出目标函数是平 衡混合装配线各种不同品种产品工作站负载的数学模型，并设计改进遗传算法求 解。另外，由于理论研究大部分算法比较复杂，很难与实际接轨。此时，迫切需 要一种有效的工具，这种工具能够把不同平衡目标的数学模型的求解算法结合， 使设计者不必知道现有算法的理论就可以应用这些研究成果，有效地实现混合装 配线的平衡。但是目前并没有这样一个有效的工具。因此，需要针对生产实际， 开发混合装配线的系统软件。这个系统可以帮助生产管理人员快速地调整工序组 合、生产布局和资源安排，提供混合装配线平衡的最佳设置，提供了管理人员进 行效率分析和改善的一个平台。 本课题结合家电企业总装车间生产实际，针对目前多品种混合装配线平衡问 题，进行数学的建模和算法设计，并对多品种混合装配线平衡问题开发了混合装 配线平衡软件系统，如果软件开发成功，对充分利用有限的资源，提高生产的效 率，增加企业的效益乃至促进我国制造业尽快地实现单一品种装配线向多品种混 合装配线发展都有一定的意义。 本文的研究得到了广东省基金项目的支持。( 项目编号：2 0 0 6 8 1 2 6 0 1 0 0 2 ) 4 第一章绪论 1 3 混合装配线平衡问题的研究现状 混合装配线平衡问题的研究目标是在满足既定的优化目标前提下，使装配线 设置的工作站数和生产节拍合理，同时各操作工人的生产负荷尽量均衡，以减少 工人忙闲不均的现象。 工业生产中，装配线早已存在，平衡问题研究的方法主要集中在理论研究。 即把装配线平衡问题抽象为数学模型，设计一定的运算规则来求解。a r c u s 提出 c o m s o a l ( c o m p u t e rm e t h o do fs e q u e n c i n go p e r a t i o nf o ra s s e m b l yl i n e s ) ，利用 简单的系统记录的方式，随机地产生分配作业元素的不同分配方式，这种方法比 较通用于实际的企业( 1 9 6 6 ) ( n 。r p w ( t h er a n k e dp o s i t i o n a lw e i g h th e u r i s t i c ) 是 另一个著名的启发式算法，把要分配的作业元素按一定的规则排序，并分配到各 个工作站去【q 。 k i l b r i d g e 和w e l t e r 首次提出混合装配线概念以及混合装配线的两种类型 ( 1 9 6 1 ) ，混合装配线问题的研究早期集中在装配线的平衡方面，并提出很多算法。 首次解决混合装配线平衡问题的是t h o m o p o u l o snt ，t h o m o p o u l o snt 运用联一 合优先图的概念把混合装配线转化为单一品种装配线来处理，从而把单一品种装 配线的平衡技术和方法运用到混合装配线( 1 9 6 7 ) t g hr o b e r t ssd 和v i l l acd 建立 了求解混合装配线平衡的整数规划模型( 1 9 7 0 ) 0 0 1 ，这种模型是对g u t j a h a r 和 n e m h a u s e r 单一品种装配线平衡方法的修改，变量个数与约束条件随着a l b 问题 规模的增大而急剧增加，因而只有理论意义；d a r - e 1em 在k i l b r i d g e 和w e s t e r 等人的研究基础上，详细论述了混合装配线的分类及主要特征：包括工作站的类 型，输送系统、产品的投放规律等等( 1 9 7 9 ) t 1 1 ；e r d a le r e l 和h a d ig o k c e n 给出了 混合装配线平衡问题的最短路径算法( 1 9 9 9 ) ，这也是对g u t j a h ral 和n e m h a u s e r gi 的算法的改进，局限性在于不能解决大规模的混合装配线问题；k o r k m a z e l 和 m e r a l 提出j i t 的两大目标：使每个工位的负载均匀；生产线零部件的消耗率均匀。 重点探讨是第二个目标且优化函数为最小化实际生产量和理论生产量之差。由于 生产线零部件的消耗率均匀是装配线平衡问题，因此实现这个目标较困难。必须 保证两个方面：产品生产量与需求相当，制造过程的每一阶段零部件使用率保持 稳定( 2 0 0 1 ) t m ；j o s e p hb u k c h i n , d a r - e 1em 和j a c o br u b i n o v i t z 给出了在面向订单 广东工业大学工学硕士学位论文 环境下的混合装配线平衡的新的启发式算法( 2 0 0 2 ) o j ；还有提出的平衡设计算法不 同于常规，不同品种的产品其作业元素可以分配在不同的工作站中。由于传统的 装配线平衡问题只考虑最小化工位数，而实际更注重最小化资源。宋华明在混合 装配平衡问题引入协同进化算法，把平衡和排产作为算法的两个方面，建立了一 种新的混合流水生产算法。在算法框架中，分别建立了混合装配生产系统的基于 制造周期、负荷、物流和u 型布局等多目标协同优化模型，在基于制造周期 ( m a k e s p a n ) 的多目标协同优化中，研究了各种平衡指标与系统目标之间的关系， 将协同优化的结果与串行优化的结果进行了比较分析，给出了混合装配线协同优 化与多目标协同优化的具体算法，并且在多目标协同优化得到的决策方案 ( 2 0 0 3 ) t 5 l 。a g p a k 和g o k c e n 提出用0 1 整数规划模型求解装配线问题，优化目标 是最小化工作站数和资源( 2 0 0 5 ) t s l ；s i m a r i a 和v i l a r i n h o 用迭代基因算法求解混合 装配线平衡，优化目标是给定操作工人数，最大化生产率( 2 0 0 4 ) 0 6 1 。 随着混合装配线的应用，文献某些的假设对实际生产状况过于理想化，不能 真实地反映生产现状中不确定因素对混合产品平衡的影响。因此，出现了对不确 定因素的混合装配线的研究。例如作业元素时间超过工作站时间、分配约束和资 源约束、可变作业时间、投产排序对混合平衡的影响等，下面对这些研究作详细 分析。 1 作业元素时间超过工作站时间通常意义的工作站是一个工作站配备一台 设备和一个操作工，作业元素时间不能超过工作站时间，如果个别作业超过，则 可以通过以下两种方法解决： ( 1 ) 通过并行工作站即增加一个或多个与瓶颈工作站相同的工作站来处理作 业。具体操作：由于工作站节拍由最大的作业时间决定，当作业时间超过节拍时， 负载严重不平衡，就会出现瓶颈工作站。并行工作站就是用两台或以上的工作站 同时处理原来瓶颈工作站的作业。此时，并行工作站的节拍两倍于原来工作站的 节拍，工作站负载也是两倍于原来工作站的负载。另一方面，增加并行工作站会 增加其他成本，比如设备成本、工人工资成本和其他的费用。因此，研究带并行 工作站的混合装配线平衡通常是以成本为目标函数来求解。 ( 2 ) 通过线外工人来协助完成作业类似的情况在混合产品排产中也出现，具 体的内容在下一节中详细研究。 并行的作用： 6 第一章绪论 ( 1 ) 提高装配线平衡率( 减少空闲时间) ( 2 ) 提高生产率( 减少节拍时间) ( 3 ) 提高可靠度 直线型装配线只要一个工作站因故障或其他原因停机，整条 装配线停顿，然而备有并行工作站出现故障时，只会使装配线的生产率降低，而 不会出现全面停机的现象。 并行在装配线中的应用有三种不同形式：( 1 ) 至少两个或以上工作站并联，每 个站内设备和工人数都相同；( 2 ) 两个或以上工作站串联，这是在空间约束或传送 装置简单应用的，这种并行工作站必须在站前后设置缓冲区，以避免工件堵塞或 并行工作站空闲的现象发生：( 3 ) 是在工作站内设置并行工位，即以并联的形式安 排与原来站内相同的设备和人员。 m c m u l l e n , ei l 和f r a z i e r , c tv 提出了启发式算法求解可变作业时间和并行工 位的混合装配线平衡问题( 1 9 9 7 ) 0 7 1 。 v i l a r i n h o ，e 和s i m a r i a , s 提出分两阶段求解的启发式算法求解带分配约束和。i i 允许出现并行工作站的混合装配线平衡，目标函数有三部分组成：给定节拍最小 化工作站，平衡工作站间的负载和平衡工作站内部的负载。算法的第一阶段用改 进的位权法获得最小工作站数，第二阶段用模拟退火算法来平衡工作站间和内部 的负载( 2 0 0 2 ) t 町。 并行工作站是混合装配线平衡的一个重要研究方向。 ：、 2 变化的作业时间研究单一品种装配线平衡，作业时间通常假设为确定 值，但实际的情况是这样的：设备的故障引起生产率的变化，导致作业时间随机 性变化。大部分的研究是把随机性作业时间转化为确定性作业时间平衡来求解。 当作业时间为随机变量时，由于作业时间的随机性导致整个工作站的时间成 为一个随机变量，如满足正态分布或均匀分布等。在理论上，不论生产线的节拍 是多大的数值，都不能保证在固定的节拍内，工作站能够完成它所承担的所有作 业。在这种情况下，工作站的时间会以一个概率超过生产线节拍。假设作业元素 时间的分布服从正态分布，如果按照确定型生产线平衡方法来平衡随机型生产线， 工作站时间将以的概率超过节拍，因而随机型生产线的平衡比确定型生产线复杂 【1 9 】。 r e e v e ，r 和t h o m a s ，w 提出基于时间的模型，目标函数是最小化作业时间超 过节拍的概率】。 7 广东工业大学工学硕士学位论文 m c m u l l e n , p r 和f r a z i e r , gv 考虑不确定因素对多目标、可变作业时间及带 有并行作业的混合装配线平衡问题进行研究，其中一个目标针对可变作业时间， 对于作业时间超过节拍的部分定义为延迟概率，假设作业时间满足正态分布，标 准差则为作业时间乘以一个固定的变量系数【2 l 】。 可变作业时间一般处理方法是利用随机发生器来产生一定数量的随机作业 时间，再通过仿真实验来确定分布的平均值和标准差【矧。可变作业时间的装配线 具有实际意义。 3 分配约束分配约束有三种不同情况：作业约束、位置约束和操作工约 束。 作业约束是某些作业要求分配到同一工作站或不同工作站，对于混合装配线 来说，不同品种产品的作业元素可能有差别，绝大部分的研究者把不同产品的相 同作业分到同一个站，如b u k c h i n , j 和m c m u l l e n , ei l 。实际生产可能出现不同 产品的相同作业在不同工作站加工装配，b u k c h i n , y 对此做了研究，目标函数是 最小化工作站成本和不同产品的相同作业重复分配到不同工作站引起的费用1 2 3 1 。 位置约束是某些工件大且重，不宜经常搬动，如客车、卡车等的装配线，工 作站必须要安装在装配线左边或右边的位置，因此左边的作业不能和右边的作业 分到同一工作站内，双边装配线是装配线的一种特殊形式。 工人约束是指技能相当的工人应该分配复杂程度相当的作业。 分配约束反映了实际生产的状况。 4 投产排序对混合装配线平衡影响与单一型装配线的平衡问题不同，混合 型装配线的平衡问题包括两个相关的方面：一方面是作业元素的分配问题，即将一 系列的装配作业分配到工作站中去；另一方面是排序问题，即确定混合装配线上不 同制品的投产顺序。上述的两个方面问题对混合装配线的平衡效果均有显著的影 响，而且分别是n p h a r d 问题【z 4 】。 k a r a b a u 和s a y i n 结合排序问题来研究第1 i 类混合装配线问题，划分最小生 产循环为若干个子生产循环，每个子循环内按一定顺序投放产品到工作站，子循 环节拍由最大工作站时间决定，各子循环的节拍相加，得到整条混合装配线的节 拍嘲。通过结合产品排序来分析作业分配，解决混合装配线平衡问题更有实际 意义。 上述是对生产实际因素对混合装配生产线平衡影响的分析，考虑实际因素的 8 第一章绪论 混合装配线平衡问题将成为混合装配生产线平衡问题新的发展方向。 根据上述的文献，我们可以看出，对混合装配线的研究仅研究平衡的文献存 在的问题和研究思路有： ( 1 ) 在多数的情况下，多品种混合装配线的平衡设计是转变为单一品种装配 线的平衡问题。目前混合装配线的平衡问题主要考虑的是工作站的平均负荷，在 平均负荷不超过装配线节拍的前提下，仍然可能还会有大量的单个型号的产品的 负荷超过流水线的节拍。在这种情况下，如果这种产品被连续投产，装配线上就 会出现“瓶颈”工作站，引起大量的不能完工的产品出现，从而引起装配线停顿。 因此混合装配线的平衡问题，数学建模的目标函数既要考虑工作站平均负载，又 要考虑工作站内各种产品的负载平衡。 ( 2 ) 早期的混合装配线平衡的算法主要集中在启发式算法。这些算法主要是 学者们根据不同的目标函数提出的一些较有效的算法。指的是寻求一种能产生可 行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率高，但”4 对每一个需求解的问题必须找到其特有的启发式规则，这个启发式规则一般无通 用性，不适合其他问题。近年来，随着各种新的相关学科与优化技术的建立与发 展，混合装配线平衡问题的研究也出现了许多新的优化方法。例如：遗传算法、 模拟退火法、禁忌搜索算法等智能算法等等，众多的方法使得混合装配线平衡问 题的研究朝着多元化方向发展。然而对求解大规模的问题、收敛到最优解的速度、一： 解最优性的判断以及合理的运算时间等方面，上述算法仍需要进一步的研究改善。 混合装配线平衡和排产是混合装配线研究的很重要的两大分支。产品在装配 线上投产排序是混合装配线的另一个研究重点。混流装配线的排产问题主要解决 装配线以及整个生产系统的生产负荷均衡问题，通过确定不同产品进入装配线的 顺序，使得某个目标函数值达到最佳，避免产生系统瓶颈。零件按一定的规则依 次经过工作站，使零件在每一台设备前的等待时间减少，同时又不会出现占而不 用的情况 2 6 1 。国内外对混合装配线排产问题研究的目标主要有最小化制造周期或 实现j i t 。求解的方法也经历了从启发式算法到循环算法的过程。 总之，对混合装配线平衡和排产问题的研究，必然向着集成化、动态实用化、 高度次优化方向发展。本文研究混合装配线平衡问题，基本出发点是根据生产实 际建立合适的数学模型，设计合理的算法，更好地解决混合装配线平衡问题。 9 广东工业大学工学硕士学位论文 1 4 课题的研究内容及方法 本文研究的混合装配线具有以下特点： 生产线结构、工艺和尺寸相近，生产的品种要均匀混合流送，组织相间性投 产，从而减少装配线上生产能力的浪费和在制品的占用量。在这种装配线上，产 品的品种虽然不同，但它们在结构上必须是相似的，工艺、尺寸也必须相近，区 别很大的产品是无法组织混和生产装配的。 本文是以混合装配线平衡问题为研究对象，从以下几个方面进行研究： ( 1 ) 研究混合装配线平衡问题几个方面的相应数学模型。 ( 2 ) 研究混合装配线平衡问题数学模型的算法求解。 ( 3 ) 研究混合装配线平衡系统软件，搭建算法理论与生产实践之间的平台。 本文研究方法是： ( 1 ) 归纳前人关于混合装配线平衡问题的研究成果，在生产实际因素分析基础 上，提出混合装配线平衡问题的分析方法。 ( 2 ) 总结遗传算法的技术特点，分析国内外学者针对遗传算法缺陷所进行的改 进研究，设计基于混合装配线平衡问题的改进的遗传算法。 ( 3 ) 设计混合装配线平衡问题的系统软件。 1 5 章节安排 根据研究内容、方法，本文的结构如图1 1 所示。 l o 第一章绪论 第一章绪论 0 第二章混合装配线的平衡问题的描述 士 l 第三章混合装配线的平衡问题的数学建模 0 l 第四章混合装配线的平衡问题算法设计 士 l 第五章混合装配线的平衡问题系统实现 上 总结与展望 图1 1 本文结构示意图 f i g1 - 1s c h e m eo fp a p e rs t r u c t u r e 第一章说明了研究混合装配线平衡的背景、意义，回顾了混合装配线平衡研 究的历史和现状，提出了研究的问题，确立了本文的框架和主要内容。第二章对 混合生产线平衡的问题的描述，给出基本思路和平衡效果的评价指标。第三章回 顾了文献中装配线平衡的建模思路，建立了混合装配线的平衡问题的数学模型， 目标函数分别是各种产品平均负载平衡和各种产品在工作站内负载平衡，说明新 模型的优越性。第四章详细描述了混合装配线的平衡问题算法设计来解决混合装 配线平衡问题。根据平衡目标的不同，分别设计了两种混合装配线平衡的算法。 第五章开发混合装配线平衡的系统，并通过实例验证。最后进行全文总结，并展 望未来，提出存在问题和今后继续研究的方向。 广东工业大学工学硕士学位论文 第二章混合装配线的平衡问题的描述 2 1 混合装配线的平衡的基本概念 2 1 1 混合装配线平衡问题的定义 装配线平衡问题( a s s e m b l yl i n eb a l a n c i n gp r o b l e n 1 a l b 问题) ，广义解释是指 工程流动间或作业流动间负荷之差距最小，流动顺畅，减少因时间差所造成之等 待或滞留现象。狭义解释是指对给定的传输速度和作业总量，如何尽可能均衡地 将装配作业分配给沿线各作业站，而不违反各作业元素执行先后顺序的限制，并 保证各站的总作业时间不超过规定的周期。即就是指为有效的达成预计的生产目 标，而对设备和人员做适当的调整【卯 对于该定义，可以这样理解，工作站之间负荷的差距最小是装配线达到平衡 的特征，而使流动、顺畅减少等待或滞留的现象，从而提高生产效率则是装配线 平衡所要达到的最终目标。 混合装配线平衡问题首先考虑的是工作站的平均负载，也即是上述工作站之 间负载，在平均负载不超过装配线节拍的前提下，却仍然可能还会有大量的单个 品种的产品的负载超过装配线的节拍。在这种情况下，如果连续投产这种产品就 会出现装配线上的瓶颈工作站，引起大量的不能完工的产品出现，从而引起装配 线停顿。此时，需要解决工作站各个品种产品的负载平衡，即各种产品在同一工 作站内部的负载时间尽可能接近。从而使工作站的平均负载和工作站内部的各种 产品负载均衡，实现混合装配线平衡的目标。 2 1 2 混合装配线问题的分类 装配线可以采用多种标准对其进行分类，由于具体的生产条件不同，工业企 业中的装配生产线形式是多种多样的，通常可将装配线按以下几项标志进行分类： 1 按生产对象的移动方式可以分为固定装配线和移动装配线。固定装配线是 指劳动对象固定，而生产工人携带工具沿着顺序排列的劳动对象进行移动加工： 移动装配线是指劳动对象发生了移动，而工人、设备、工具的位置相对固定，劳 1 2 第二章混合装配线的平衡问题的描述 动对象经过各工作地进行加工后，变成半成品或成品。 2 按生产对象的数目可以分为单一品种装配线、多品种可变装配线和多品种 混合装配线。单一品种装配线是指在装配线上固定地只生产一种产品；多品种装 配线是指生产两种或两种以上产品的装配线。根据流送方式的不同，这种装配线 包括多品种可变装配线、多品种混合装配线( 简称混合装配线) 。 它们的主要区别在于 2 7 1 ： ( 1 ) 单一品种流水线一条装配线在计划周期内只生产一种或一类产品： ( 2 ) 可变装配线当一条装配线在计划周期内先后生产不同种类、不同批量 的订单处理要求，而且产品更换需要进行较长时间的生产准备；或者在同一时间， 有多个产品、多条装配线在同时进行，需要在有限的人员和设备之间进行协调， 以满足多个订单的交货要求； ( 3 ) 混合装配线指一条装配线在计划周期内混合地、交替地生产多种或多 类产品，产品的品种可以随顾客需求而变化。混合装配生产线与单一品种流水线 相比，它具有更高的灵活性，线上的工作站可变性大，适应性高，有助于提高产 品质量，使得企业对市场的快速反应不在依赖成品库存，提高企业对市场环境的 快速反应能力，实现j i t 的目标，三种装配线的示意图如图2 1 。 图2 1 各种装配线的示意图 f i g2 - 1s c h e m eo ft h r e ed i f f e r e n ta s s e m b l yl i n e s 3 按生产过程的连续程度可分为连续装配线和间断装配线。连续装配线是指 生产过程的各道工序具有高度的同期化，生产对象从投入到出产毫无停留地从一 广东工业大学工学硕士学位论文 道工序转到另一道工序，整个生产过程是连续不间断的；间断装配线是指生产对 象在各道工序或部分工序上缺乏严密的同期性，零件在工序间要出现停留等待， 致使整个生产过程是间断的。 4 按照装配线的布局，可以分为直线型和u 型。直线型是最传统的装配线形 式，设备排列简单，组织容易，流程通畅，效率高，但平衡困难，缺乏弹性。u 型适用于场地狭窄，零件或材料进口与成品出口必须置于同侧的情况，此种布置 可以灵活增减作业工人，柔性较好，平衡也比较容易实现，工作中工人易于相互 交流和帮助，是较佳的装配线平面布置形式瞄】。 混合生产线是由单一品种装配线演化而来，其分类与单一品种装配有相似， 也有不同。根据影响平衡的因素是确定性还是随机性，可以分为静态平衡和动态 平衡；静态平衡主要以算法研究为主，根据求解静态平衡的方法不同划分为几个 发展阶段：最优化法时期，启发式算法时期和循环算法时期等；根据求解平衡的 方法可分为简化的多品种平衡和非简化的多品种分别平衡：根据装配线投放速率 分为固定节拍装配线和非固定节拍混合装配线；根据作业时间的变化分为确定和 可变作业混合装配线；根据装配任务是否存在作业时间超过节拍时间分为带有并 行工作站或并行工位的混合装配线；根据分配约束可分为位置约束、作业约束和 操作工技能约束混合装配线等【2 7 l 。 2 1 3 混合装配线平衡的术语、符号定义 本文研究的混合装配线平衡的相关术语： 工作站：操作者为了完成指定作业在装配线上的工作位置，用s 表示； 作业元素：不能再分的或最小的作业单元，用f 来表示第f 个作业元素； 作业元素时间：完成一个作业元素所需要的工作时间，用f ，表示； 平均节拍时间：在混合生产装配中，相继完成两件不同品种产品在制品之间的时 间间隔，它是由计划期和需求数量来决定的，用c ，表示； 工作站时间：完成分配给一个工作站的全部作业所需时间，也称为工作站负载， 用s l 表示； 工作站空闲时间：在节拍内完成分配给一个工作站的全部作业后所剩余的时间， 它等于节拍减去负载时间； 总作业时间：完成整个产品装配过程所需时间，它等于所有作业元素时间之和， 1 4 第二章混合装配线的平衡问题的描述 用丁表示，有t = e t , ； 总空闲时间：整个装配过程中，所有工作站空闲时间之和，用厂表示，有 户( c - s l ) ； 紧后作业：从该作业出发沿着装配优先顺序图上所有路经前进直到终点所遇到的 所有作业； 紧前作业：从该作业开始逆路经方向而行直至起点所遇到的所有作业； 装配作业顺序图：给出一个产品装配过程的可能步骤之间明晰的内在逻辑关系， 由产品的工艺决定。 下面是一张简单的作业顺序图。 4 图2 2 作业顺序图 f i g2 - 2t a s k ss e q u e n c ed i a g r a m 图2 2 中，每个节点( 圆圈) 表示一个作业元素，每个作业元素有唯一的作业编 号和作业时间，分别用圆圈中的数字和圆圈上方的数字来表示；优先图中的两个 节点之间的箭头表示作业之间先后顺序的约束关系，箭头指向始端的作业必须在 箭头指向末端的作业之前完成，没有箭头连接则表示他们之间没有先后顺序约束。 作业顺序矩阵：对于作业元素之间的先后关系可以用作业顺序图来表示，但是对 计算机来说，这种图形难以处理。将作业顺序图数量化，使之易于处理。这样就 产生了作业顺序矩阵。对于装配线上含有聆个作业元素的产品，它的作业顺序矩 阵为刀刀方阵p 。 p = ( p 。) 。 ( 2 1 ) 其中作业关系的元素仇( f = 1 , 2 ，疗；= 1 , 2 ，m ) 取决于第f 个作业元素与第- 个作业 元素的优先关系，即 广东工业大学工学硕士学位论文 图 p = 平衡评价参数：装配线平衡的评价标准，有以下指标： 平衡率：总作业时间与工作站数乘以瓶颈工作站时间的百分比，用三e 表示， l e = ，( m x s 一) x 1 0 0 ( 2 2 ) 平滑指数： 通常应用平衡率为评价指标。 s i = 2 2 混合装配线平衡问题的复杂性 ( 2 3 ) 装配线平衡问题是n p h a r d 问题，将”个作业元素分配到m 个工位的计算复 杂度是o ( m 2 n ) ，计算的复杂性随着工位装配元素和工位数目的增长而呈指数增 长。而对比单一品种装配线平衡，混合装配线平衡问题要复杂得多，这主要是由 于混合装配线平衡同时生产装配不同品种产品，各种产品的工序和作业时间不 同，单一品种装配线平衡的研究方法不完全适用于解决这一问题。下面通过一个 例子来说明。 单一品种装配线只装配a 产品，只需要把装配产品a 的所有作业( 工序) 分 配到各个工作站中去，根据实际情况，满足相关约束及以下目标之一：