汽车混流装配线的排产优化

1、广西工学院毕业论文论文题目汽车混流装配线的排产优化-柳州裕信方盛汽车饰件有限公司为例姓 名 梁荣欢系别管理系专业工业工程班别工业工程082指导教师.何恒日期2012年4月3日摘 要:多品种小批量混流生产能够快速、 灵活地组织生产特定的产品， 从而响应市场日益变化 的不同需求。这种新的生产模式已被越来越多的大型汽车制造企业所采用，但与之相关的投产排序问题也日益成为研究的热点。本文概述了国内外轿车混流生产的应用状况及混流装配线的投产排序优化对于提高企 业生产效率的重大意义，介绍了该课题在国内外研究状况及能用于解决该课题的遗传算法的 基本原理和运行步骤。 通过研究“柳州裕信方盛” 实行的多品种混流生

2、产方式，发现优化投产顺序可以降低目前存在于不同装配工位工作负荷不均衡导致暗灯停线频率的现象。这种现象因混流装配线上不同产品所需的装配工艺和装配时间不同而难以避免，并造成一定的浪 费。本文以工作负荷均衡化为投产排序目标建立了数学模型，并运用遗传算法对该数学模型进行解算。本文按上述遗传算法编写 MATLAB程序，通过算实例验证了该算法和 MATLAB程序 的可行性。结合“柳州裕信方盛”三课汽车内饰件装配车间的应用实例的研究，通过对混流生产线上的车型进行排序， 在理论上验证了该投产排序方法能有效降低制造成本，为企业带来收益。最后在总结全文的基础上，提出了对多品种混流生产调度系统的展望。关键词：汽车、

3、装配线、MATLAB，多品种混流生产，遗传算法，投产排序IIAbstractMany kinds of small batch mixed flow producti on can fast flexibility to orga nize product ion of specific products, resp onse to cha nging market n eeds. This new product ion model has bee n more and more large car manu facturi ng en terprise used, But the rela

4、ted product ion scheduli ng problems are also in creas in gly become the research focus.This paper summarizes the domestic and foreig n cars mixed flow product ion applicati on status and mixed flow assembly line product ion of the sort to improve product ionefficie ncyoptimizati onof the great sig

5、ni fica nee,in troducesthedomestic and foreig n research status and project can be used to solve this topic, the basic prin ciple of gen etic algorithms and operati on procedures.Through thestudy of a “ YuXin FangCheng LiuZ hou” margin of mixed flow modeof production,findoptimizationcan reduce produ

6、ction order at present are found in differentassemblylocation imbalanee working load in dark light stop line frequency phenomenon. This phenomenon for mixed flow on the assembly line for different product assembly process and assembly time differentand hard to avoid, and cause certain waste. This pa

7、perwork load equilibrium product ion in order to target a mathematical model is set up,a nd the use of gen etic algorithms in the mathematical model for calculat ing.This paper accordi ng to the above writ ing MATLAB gen etic algorithm,through the calculati on examples show that the proposed algorit

8、hm is and the feasibility of MATLAB. Liuzhou margin Fan gChe ng letter with three class car inner decoration assembly workshop examples of application of research, through to the mixed flow line type of order, in theory to prove the product ion scheduli ng method can effectively reduce the product i

9、on cost, for en terpriseto bring in reve nue last on the basisof sum ming up,proposed to the many kinds of mixed flow producti on scheduli ng system outlook Keywords: car、 assembly line 、 MATLAB、 variety of batch mixed flow production 、 gen etic algorithm、Put into product ion order3摘 要： IIAbstract i

10、ii第一章绪论 11.1研究背景 11. 2研究的目的 21.3研究的意义 21.4国内外研究状况 31.4.1国外研究状况 3142国内研究状况 3第二章汽车混装配线排产的优化目标 52. 1汽车混流装配线概念 52. 2汽车混流装配线的特点 52. 3汽车混流装配线问题描述 62.4混流装配线不平衡现象及其产生原因分析 72.5混流装配线投产排序的必要性 82.6求解混流装配线投产顺序的主要算法 92.6.1几种主要算法 92.6.2遗传算法基本原理 102.6.3遗传算法的实现形式 102.6.4遗传算法的运行步骤和流程图 11第三章混流装配线的投产排序数学建模及排序方法 133.1混流

11、总装线投产排序建模思想 133.2混流装配线投产排序数学建模 133.3基于遗传算法混流总装线投产排序模型解算 163.4运用软件MATLA求解 18第四章 应用范例及效果评估 214.1柳州裕信方盛汽车饰件有限公司驾驶舱装配车间简介 .214.2驾驶舱装配车间混流生产模式介绍 221、生产车型及配比 222、生产模式及节拍 223、产线人员编制及问题描述 224、各类车型相关工作站的装配工时 234.3实例计算及评估 23第五章全文总结和展望 26致谢： 27参考文献 286第一章绪论引言：随着现代科学技术的迅猛发展，产品生命周期大大缩短，同时由于用户需求的多样性， 单一品种、大批量的生产方

12、式已不再适应用户对商品的多样化需求。因此当今世界的企业都面临着增长减缓和来自国内外巨大竞争压力，特别08年金融风暴过后，各企业要在本行业拥有属于自己的一片天地，竞争压力甚是激增。那么，要在这么激烈的市场竞争中取胜，企业就必须快速、灵活地组织生产，从而响应市场日益变化的不同需求，因此随之运用的另一种生产模式随之诞生一多品种小批量混流生产模式。多品种小批量混流生产模式虽然解决了用户个性化的需求，给企业带来了新的利益， 但也存在一些问题，其中之一就是多品种混流生产的投产顺序问题。1.1研究背景20世纪50年代以来，随着科学技术发展异常迅速，产品更新换代速度大大加快，再加之社会经济发展，消费水平不断提

13、高， 消费观念、消费心理发生了巨大变化，追求产品多样化、新颖化成为当今社会持续的时尚，产品的寿命周期也随之大大缩短。在这种情况下，由福特提出的大规模生产模式已经无法适应快速多变的市场需要，已经不能满足用户需求的多样性，因此单一品种、大批量的生产模式已不再适应用户对产品的多样化的需求。正因如此，企业也不可能再长期生产一两种固定的产品，而是必须跟随技术进步的步伐及时地进行产品的更新换代，并不断开发多种多样新产品以适应市场需求。特别是08年金融风暴过后，世界各个行业都面临着增长减缓和来自国内外巨大的竞争 压力，要在这么激烈的市场竞争中取胜，就必须快速、灵活地组织生产， 以最快的速度开发出高质量、低成

14、本、高附加值的新产品，响应市场的需求。为此，一种新的生产模式随之诞 生：多品种、小批量生产模式。这种生产模式被越来越多的企业所采用，特别是在汽车制造业，其逐渐成为主导的生产模式，因为这种生产模式可以实现弹性生产，生产上具有更多的灵活性，提高企业的应变能力，不断满足市场的动态需求，更能适应现今的“买方市场”。由于汽车工业的发展与变革对全球经济产生着重大的影响，因为汽车工业与社会整体经济关系非常密切，它能在某种程度上带动大量行业，如公路建设、石油石化、钢铁、机械制 造、电子、保险（汽车保险等）等行业的发展，正因如此，汽车工业被世界多数国家看作是 国家的支柱产业1。在我国也不例外，汽车工业也是我国的

15、重要的龙头工业之一，政府在 汽车工业方面采取了正确的政策，改善了汽车消费得环境，促进消费结构升级，私人购买汽车逐渐升温，以此为起点，逐渐走向消费和生产的良性循环；加之现在人们的消费观发生了一些转变，越来越多的人都用轿车 （汽车）来代步，所以中国汽车工业已逐步迎来了良好的 发展机遇。从目前形势看，我国汽车需求量在不断上升，人们汽车消费素质也在逐渐提高，特别是人们对轿车的需求在不断的上升，所以越来越多的汽车制造企业开始把注意力转移到轿车生 产上来，因此，在轿车制造方面，这些企业面临着更加激烈的竞争压力，各个企业都在支招，都期望以最小的成本生产出附加值更多的产品，同时汽车工业是全球工业的龙头行业之一

16、， 所以其业内竞争也是很激烈的，在加之市场的变化，由原来的“卖方市场”转向“买方市场”，这种竞争压力激增。为了满足消费者对汽车日益多样化、个性化的不同需求，因此，目前汽车制造业都普遍采用多品种、少批量混流生产的生产模式。基于上述，为了很好的满足客户的需求，汽车企业必须在进行汽车生产过程中制定良好 的生产模式及生产计划，而良好的汽车生产计划又依赖于完善的汽车排产安排。多品种、少批量混流生产的生产模式虽然适应了当前的市场要求，但在组织生产上也暴露出了一些难以避免的问题，其中怎样进行排产， 减少流水线的停线时间（次数）就是一个有待解决的问题。因此，这些相关的问题都有待我们去逐一解决。1.2研究的目的

17、随然说大规模生产模式已经不再适用于“买方市场”的市场需求，多品种、少批量混流生产的生产方式倍受各个行业的青睐，但多品种、少批量混流生产的生产方式在组织生产上也暴露出了一些难以避免的问题，女口：生产计划调整问题、排产安排问题、制造设备柔性问题、企业物流规划问题、 库存控制问题等， 这些问题的出现以及对企业产生的影响是不可忽 视的。汽车混流装配（生产）线正常运转的一个关键前提是生产的均衡化和同步化，而这些都与投产的排产顺序有关，而一个好的排产顺序能保证生产线的正常运行，可减少因停线所造成的可控制的成本浪费，所以要使生产线能够正常的转动，就必须对排产进行相关的研究。再者，为了适应复杂多变的当今市场，

18、 在激烈的市场竞争中取胜， 企业必需充分发挥其 生产系统的生产能力， 缩短生产周期、提高生产效率，从而降低生产成本， 提高企业的市场 竞争力。总的来说，汽车投产的排序问题会影响到生产计划的实施、设备的利用程度、物料流动的状况以及库存水平的高低等多方面， 因此它的解决及其实施效果的好坏， 是衡量企业生产 管理与作业控制水平非常重要的一个方面， 它的解决也是企业提高生产效率， 降低生产成本， 提高市场竞争力的前提，所以对其进行研究具有很重要的意义。1.3研究的意义对多品种、小批量混流生产线的排产研究，及它的解决和实施效果的好坏，是一个使用该组织生产方式的企业提高其生产效率，缩短产品的生产周期，使企

19、业的现有资源实现利用率最大化，减少企业的生产运作成本、提高企业的整体效益、市场竞争力的基础。一个混乱的排产方案，将使企业承受更多的生产制造成本。比如没有给混流生产线进行合理的排产将会导致某一个工位在一段时间内处于过于闲置状态，而某个工位的工作负荷又过于饱和，长时间的工作后， 过于工作负荷过于饱和的工位的工人容易疲劳，工人的工作状态将大大降低，这都有可能导致其不能按预定的工时完成本工位应该完成的工作量，致使整条生产线的临时性停线。这些因素将使企业在激烈的市场竞争中处于劣势。下面举个简单的例子来说明企业合理的排产能够为企业节约的生产制造成本：假设：某企业的某个汽车装配车间（混流线上同时装配不同的车

20、型）的某条装配线共有50名装配工，实行两班制生产，一年上班的时间为250天，如果产线排产优化后能使流水线每天减少1分钟的停线。这样一年内能为企业节省的工时为：50 x 2 x 250 x 1/ 60= 416.7 小时而如果这条线每分钟能为企业创造1000元的价值，则产线优化后一年内能为企业创收：1000 x 2x 250 x 1 = 500000 元。由上例我们可以看出，通过优化混流生产线上不同品种车型的投产顺序是非常重要的。1.4国内外研究状况1.4.1国外研究状况汽车排产问题一直是国外学者研究的热点，并且他们在这方面的研究起步较早，相关研究主要如下：在工业生产中，尽管混流线早已存在，但第

21、一个明确提出这个问题的是Kilbridge MD和wester。1961年，Kilbridge和Wester首次提出了混流线的概念以及混流线的两种类型。Thomopoulos在1967年建立了关于负荷平衡的以最小总惩罚代价为目标的数学模型并 用启发式算法进行了求解。1970年，Thomopoulos通过组合优先图的方法把混流装配线转化为单一型流水线来处理，从而把单一型流水线的平衡技术和方法运用到混合流水线，首次解决了混流线的平衡问题。文献13提出了一种基于混流装配线均匀零部件消耗速率的新启发式算法一方差算法， 对目标追随法进行了改进。Bukchin等研究了基于订单生产条件下的混流线平衡问题14

22、文献15考虑了混流线上存在并行工作站的情况，并提出了数学模型和遗传算法求解过 程。Kilbridge于1963年就己经开始研究混流装配线的排序问题，Jonathan提出了一个针对混流装配线问题的涵盖每一个决策变量的通用数学框架，并给出6类模型的数学公式2。Chul采用一种新的基因遗传算法解决多目标排序问题，提出了一种新的因适应度函数 及选择机制，其考虑的二个目标是最小化超标工作时间、保持均匀的零部件消耗速率和最小化调整费用，结果表明该基因算法优于已存在的其他基因算法161.4.2国内研究状况从上面国外研究现状可以看出国外对此问题己经有较长时间研究，而国内对此问题的研究较晚，直到最近几年才出现一

23、些相关的研究成果。但是随着汽车行业发展以及意识到其重要性，已经有很多人员对该领域进行研究，主要如下：赵伟等（2000）通过建立多级混流装配线调度模型，并利用遗传算法（GA）以及模拟退火法（SA）对该模型进行求解，并将求解结果与目标追随法（GCA）的求解结果进行了对比。孙新宇（2002）则在均衡混流生产线上各零部件的使用率前提下，通过蚁群算法（从）来对排产数学模型进行求解，并把求解结果与目标追随法、遗传算法以及模拟退火法进行了对 比。蔡志峰（2002）则在其他研究人员的研究成果基础上，通过原有的遗传算法以及自调整 参数遗传算法相结合的混合遗传算法来求解排产数学模型，并得出一个比较满意的排产方 案

24、。宋华明和韩玉启（2002）6分别用模拟退火法对典型的排产案例进行求解和利用遗传算 法对装配线平衡数学模型进行求解。易东波（2003）8在均衡生产速度的要求下建立数学模型，利用丰田生产方式中的“目标 追随法”对排产模型进行求解，然后最后得出混流装配线的最终排产结果。董建华（2003）9针对混流装配线的排序问题，提出了一种混合遗传禁忌搜索算法，在每 一代遗传演化之后，按一定比例随机选择部分解进行禁忌搜索，以提高算法的全局搜索能力和收敛性，并通过一个混流装配线排序实验，分别利用遗传算法和遗传禁忌搜索算法（GTSA）进行求解，得出一个更好的排序结果。总之，有关混流排产问题国内外都有了一定的研究，相比

25、之下，国外的研究要比我们国内的早，并且已经比较深入；而国内的有关研究相对较少也相对要慢。4第二章汽车混装配线排产的优化目标2.1汽车混流装配线概念流水装配线从单一品种流水作业发展到现在的多品种混流装配，混流装配生产系统有时也称为混合装配系统。A.E.欧文是这样描述的：“混合装配系统是柔 性装配系统的一种实现形式，是柔性装配设备、物流储运装置、计算机控制调度 系统和必要的生产管理人员所组成的用于满足多品种共线生产的一种柔性装配 系统，它包括多个柔性装配工作单元，能根据装配任务或生产环境的变化迅速进 行调整，适用于多品种、小批量生产。” A.E.欧文的定义主要侧重于柔性化的装 配设备，应该讲，这是

26、混流装配生产系统的一大类。由于混流装配生产系统还在发展之中， 所以尚无统一的定义，但综合目前的 发展可以认为：混流装配生产系统是一种运用于装配生产领域的生产组织与运作 的方式，可以很好的解决企业多品种、 小批量生产的问题，这是柔性生产系统原 理在装配生产领域的具体实践。在混流装配线上，不同品种产品混合、连续地进行，装配线上产品一般是模 块化设计的系列产品。这些产品在功能上和作业方式上基本相同， 仅仅在规格以 及型号上有所区别。在汽车、家电工业中，产品经常是系列化的产品，在装配生 产过程中，大部分的装配工序是相同的，更换产品品种时基本不需要调整生产线 10。有时，混流装配线也特指汽车的混流总装线

27、，是指在一条装配线上装配多 种车型。2.2汽车混流装配线的特点汽车混流装配线生产系统其实就是一个多品种小批量的生产系统。这是由于汽车混流装配线生产系统具有以下特征所决定的：(1) 生产品种的多样化。汽车车型与品种较多，而批量与交货期又各不相同。(2) 生产过程的复杂化。各种零部件进入的时间需要准时化，而“物流”作 业会由于计划改变而需要经常变换。(3) 生产环境条件的多变性。由于车型的规格、数量、交货期的变化很大， 往往要更改计划，甚至在出现特别紧急的订单时，会发生外购件或原材料交货不 准时、供货不及时等意外情况。(4) 生产计划的变动性。因为订货的规格不一致，为满足不同的的客户，必然会造成车

28、辆在制造过程的多变以及物流保障工作的复杂性。因此，要实现工艺计划和进度计划在这种生产方式下的最优是一项复杂的任务。(5) 生产管理的动态性。由于具体任务在组织实施生产的过程中情况多变，容易引起设备故障、人员缺勤、熟练程度不足等问题。如果依靠经验或凭直觉来 管理，有可能陷入管理的混乱，很难做到规范化管理。(6) 个计划期内，在同一条生产线上生产 m种规格的车辆。(7) 生产线上的m种车辆通常是结构和工艺相似，但规格和型号不同。(8) 生产过程中，不同车型之间的转换基本上不需调整生产线。(9) 生产线上m种车辆是连续、混合投入的。2.3汽车混流装配线问题描述汽车混流装配线生产系统是一个多品种小批量

29、的生产系统， 由于汽车混流装 配线可以忽略从一种车型转换到另一种车型所需的花费，混流装配线是一种制造 各种车型的有效方式，它提供给生产系统快速响应需求变化的能力， 并且不需要 保持大量的零部件库存。我们知道平衡问题是装配线规划过程中必须首先要解决的基本问题之一，不平衡的装配线是不理想的，但是由于各种原因，产线是不可能达到完全平衡的， 而混流装配线更是难以做到这一点。因为混流装配线大多是在同一条生产线上连 续、混合投产多种结构和工艺相似，但规格及型号不同的车型(产品)，这样在考虑一种车型的投产产线平衡的同时还要考虑到其它的在该条生产线上投产的 车型的平衡问题，这就大大的增加了产线平衡问题解决的难

30、度。虽然说混流装配线在工艺、产线平衡的规划等方面存在一些难度， 但相比开 两条生产线或是开n条生产线(假设车型种类为n种)要维持大量的人力物力(固 定资产等)的投入要划算得多，因为当今社会已由原来的“卖方市场”转变成“买 方市场”，商品的生命周期大为缩短，企业对单一产品的相对投入越多，风险就 越大。再者，一般一条混流生产线上投产的车型(产品)工艺类似，大体上可以 合理的安排投产，使产线能处于一种非完全平衡的平衡状态。混流装配线是按产品原则进行布置的，产品原则布置的优点在于它把要做的 工作分解为可由工人或专用机器快速而机械地完成一系列单元作业。但是完成这些单元作业所需的时间一般从不足几秒到几十秒

31、甚至更多，由于单元作业的工时相差太大，所以为每一个工人或机器只分配一个单元作业是非常不现实的。一方面是因为大多数工人很快会被简单的重复工作弄得很厌烦，降低工作效率；另一方面是即使生产一个很简单的产品也需要庞大的工人队伍。通常的做法是将各单元作业组合成不同作业包分配给各工位，每个工位由一个工人(或多名工人)或一台主要设备负责相关作业。对装配线，决定如何将单元作业分配到工位的过程 就称为装配线平衡(Assembly Line Balancing,ALB )。装配线平衡的目的就是尽 量使各工位的作业时间相等，以避免由于工时相差太大而造成某些工位作业堆 积，而另外一些工位又工时流失的现象，以减少总的闲

32、置时间，提高整条装配线的效率。通过装配线平衡，还可以提高重要设备的利用率，减少工人由于作业不平衡而引起的情绪问题混流生产（装配）线虽然在生产上有其它生产模式没有的优势， 但是也存在 一些有待解决的问题。如：在实际生产中我们最常遇到这样的问题，在刚刚投入正式生产的时候，所有工位的工作都是较为平衡的。但是经过一段时间之后，有 些工位的操作时间相对其它要少，而 有的工位的操作时间明显要多于其它工位 的操作时间，在某个工位堆积了较多的作业，可能还经常造成暗灯停线，生产线 由原来的平衡变成了不平衡的现象等。上述情况也就相当于在装配流水线上某装配工位 j,可能出现的2种情况： 一种是，某一种i车型的车辆装

33、配结束后，下一个品种i + 1的车辆尚未进入该工 位，操作工回到工作起点等待，处于闲置状态；另外一种是，操作工在其自身的 工位未能完成这一种i车型的装配任务，剩余的工作要停线完成或是由线外的工 人即时帮助完成，这就是处于超负荷作业状态。由上述我们可以知道，混流装配线主要存在的问题就是产线的平衡问题， 而 平衡的问题主要以两种形式存在。 在此，我们把由于车型（产品）及工艺不同而 引起的产线不平衡称为“第一种不平衡现象”；把装配线在经过一段时间的生产 后，由原来的平衡变成不平衡甚是停线的现象称为“第二种不平衡现象”。2.4混流装配线不平衡现象及其产生原因分析由上一节我们知道混流装配线产线不平衡主要

34、有两种不平衡现象，那么它们是都由那些因素引起的呢，下面作进一步的分析。一条装配线，若其上所有的工位的作业时间完全相等，称为完全平衡。完全 平衡的装配线由于各工位的作业是同步进行的， 从而实现了工人和设备的最大利 用，工作流没有任何阻碍，十分畅快。对于第一种不平衡现象而言， 要达到装配 线完全平衡是很困难的，甚至是不可能的。最主要的原因有：首先，工位的工时等于其上各单元作业时间的累加，而单元作业时间相差很大，并且是离散分布的，不大可能存在一种所有工位工时相等的作业分配方案。其次，由于对设备的要求不同和部分作业之间的不相容，把一些作业分配到 同一个工位是不可行的，如应该让“加汽油”的工位远离有装配

35、操作的工位， 以 至于不能随意分配装配作业。再者，不同作业之间可能存在技术上的顺序约束关系，有些作业必须在某些 其他作业完成后才能进行，例如装配汽车驾驶台仪表台，必须先安装完毕驾驶台 天线过度线等线束，而不能相反。这种顺序约束关系也妨碍一些作业的任意组合。在实际中，装配线平衡不是追求完全平衡，而是满足作业之间的不相容约束 和顺序约束的前提下，使各工位的作业时间尽可能相等。对于第二种不平衡现象，其主要的影响因素有：第一，由于操作者本身因素而引起。女口：操作人员长时间的作业后会产生疲 劳，从而引起作业效率下降、操作失误等。第二，混流装配线上每个工位装配不同产品类型的操作时间可能存在的差 异。某种车

36、型在某些工位上可能需要满负荷的作业，这样就会出现某些工位非常 繁忙，而有些工位又相对空闲。第三，混流产线排产不合理引起，这也是第二种不平衡现象最主要的影响因 素。就如在某种车型在某些工位上需要满负荷的作业，而需要在该工位满负荷作 业的产品类型又被连续的排产，从而引起因长时间满负荷作业的工位容易出现作 业疲劳，又回到了第一和第二个因素的影响中，并最终可导致产线停线的可能。 所以说要解决第二种不平衡现象的问题， 最重要的就是如何给装配（生产）线进 行合理的生产排序。当然，对产线不平衡的影响因素不止这些，比如人员对作业内容的熟练程度、 工艺的变更、零部件的质量问题等都会影响产线的平衡。在实际生产中，

37、大多数的生产（装配）线在初始设计及投产过程都会对产线 进行调整，最大限度的降低“第一种不平衡现象”的因素的影响，都有足够的柔 韧性去调整装配时间的不同，从而使生产线达到平衡状态。所以本文主要是对“第 二种不平衡现象”方向进行研究。2.5混流装配线投产排序的必要性从混流装配线的特性我们可以知道， 在装配线上的一个计划期内，在同一条 产线上生产m种规格的车辆，m种车辆是连续、混合投入的，并且产线上的 m 种车辆通常是结构和工艺相似， 但规格和型号不同，在生产过程中，不同车型之 间的转换基本上不需调整生产线。所以说大多数生产线有足够的柔韧性去调整装 配时间的不同，从而不会使生产线减慢或停止。 然而，

38、如果需要较长操作时间的 产品类型被连续排序一也就是产线的排产不合理，那么，最终将可能导致生产线 的临时性停止。这也正是前面所说的：混流装配（生产）线在刚刚投入正式生产的时候，所有工位的工作都是较为平衡的，但是经过一段时间之后，有些工位的操作时间明 显多于其它工位的操作时间，可能还经常造成暗灯临时性停线， 生产线产生了不 平衡的现象。在一个企业，生产线的停止运转意味着企业正在浪费其生产资料。因为不管其产线的运行与否，企业都要维持大量的人力物力，这将使生产设备及人员等处 于闲置状态，使企业蒙受生产成本上的浪费，就如在第一章种所举得例子一样， 一年就要浪费掉500000元，在当今竞争激烈的社会中，这

39、将使企业在竞争中处 于劣势。从上述可知，一个合理的生产排序方案，能够给企业在生产中节约部分不必 要的生产成本，使企业在无形中“赚回自己的钱”，增强企业的竞争力。所以说对混流装配（生产）线进行排产是非常有必要的。2.6求解混流装配线投产顺序的主要算法261几种主要算法用于求解混流车型装配线投产排序的有效算法被作为提高工作业绩的一个 重要需求而受到广泛的重视。目前求解混流装配线投产顺序的主要算法归纳起来 分别属于最优解算法、试探算法和循环改进算法。1718191 最优解算法常见的有：分支定界法、动态规划法、整数规划法等20 21。这类算法可以保证在可能解空间上搜索出最优解来。但对于多数混合车型装配

40、线的投产排序问 题其在生产实际中的可利用性是有限的。 其至多只能对极小规模的投产排序问题 求得最优解，如：分枝定界算法只能求出总车辆数在20台以下的混流生产线投产排序问题的最优解22。2 试探算法试探算法被广泛地应用于求解混合车型装配线的投产排序问题中，其形式呈多样化，但它们的基本原理是相同的，那就是假设已确定了前面n台车辆的投入 顺序，在确定第n+1台车辆的车型时，选择一种可能车型对目标函数值的影响效 果最为显著。例如，丰田公司开发的著名的“目标追迹算法23 ”，是针对投产排序问题中的第二类目标求解，即：使混合车型装配线上每个零部件的使用速率保 持不变。在确定第n+1台车辆的车型时，如有多种

41、车型可供选择，则从中选择一 种车型，使第n+1台车辆投入时各零部件的使用速率最为均匀，这类方法被称为 贪婪算法24 25。即每次确定车辆的投入顺序时，均选择最为有利的一种车型。 这类方法在确定车辆的投入顺序时，每次只考虑当前的状态，而不考虑全局状态， 一般而言，试探算法在理论上不能保证所确定的顺序为投入顺序的最优解26。但多数情况下，它们能在一个多项式计算时间内产生一个较为满意的局部近似最 优解。3 循环改进算法改进的方向朝着最优 解的改进后，最终所产生的解以概率 求解混流车型投产顺序问题中的传送 当解的改进次数多于一定次数时， 所可求解大规模的投入自90年代以来，循环改进算法开始进入混合车型

42、装配线投产排序问题的研 究领域，具有代表性的循环改进算法有： 模拟退火算法、遗传算法、禁忌搜索算 法神经网络算法等。这类方法的基本原理，是任意选择一个（或多个）初始解， 从该初始解出发，按照一定的控制准则不断进行解的改进， 解逼近，即经过多次（理论上为无限多次） 1收敛于最优解。文献11即应用遗传算法， 带停止时间最小化问题。大量的算例表明，所产生的解愈靠近最优解，所需的产生的解收敛于整体最优解。在一个可接受的计算时间内， 顺序问题。循环改进算法解的改进次数愈多，计算时间也愈长262遗传算法基本原理遗传算法是一种基于自然选择原理和自然遗传机制的寻优算法， 模拟自然界 中的生命进化机制，在人工系

43、统中实现特定参数目标的优化。 遗传算法中所用到 的进化理论的基本特性为： 生物进化是一个对于染色体、而不是对生物体本身进行操作的过程。 自然选择的过程联系着染色体和它们的各基因串的性能，各个子串的性能越好的染色体越容易生存下来。 有性生殖的过程保证其后代的基因混合、基因重组和基因突变，以产生适应力更强的后代。 生物进化无记忆。有关产生生物体的信息包含在生物体所携带的染色体的 集合以及染色体编码的结构之中，这些生物体会很好地适应它们的环境。Holla nd创建的遗传算法是一种概率搜索算法，其核心思想源于这样的基本 认识：从简单到复杂，从低级到高级的生物进化过程本身是一个自然、并行发生的、稳健的优

44、化过程。生物之所以进化是由于生物个体有其内部结构即基因结构 生物体经过繁殖、变异，产生大量新的结构，由于生存的压力，生物通过优胜劣 汰选择能适应环境的个体，使其好的基因型个体得以保存，再经过繁殖、交叉变 异，使优秀的个体重新组合，产生更优的个体，并通过竞争选择得以保存，这样 生物就得以进化。遗传算法是一种随机算法，但它不是简单的随机走动，它可以有效地利用已 有的信息来搜寻那些有希望改善质量的个体。类似与自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对 求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评 价，并基于适应值来选择染色体

45、，使适应性好的染色体比适应性差的染色体有更 多的繁殖机会。263遗传算法的实现形式1. 编码为了运用遗传算法，首先必须对优化的对象编码，使优化对象有“基因”型 结构，能够象生物进化过程那样，进行交叉、变异等操作。它是遗传算法的重要 基础。2. 初始群体的设定生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由若干 个体所组成的集合，称为群体，遗传算法正是这样一种群体型的操作， 任何遗传 操作都是从一个由若干个初始个体组成的初始群体开始的。初始群体的每个个体 都是通过随机方法产生的。初始群体也称为进化的初始代，即第一代。初始群体 规模（即群体中包含个体的数目）的确定和个体种类的选择对优

46、化过程有着一定 影响：若群体规模太大，则计算量增加，影响算法性能，还对交叉操作产生负作 用，表现在：当群体中个体非常多时，少量适应度很高的个体会被选择而生存下 来，但大多数个体却被淘汰，影响配对库的形成，若群体规模太小，会使遗传算 法的搜索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起早熟现 象123 适应度函数的设计在研究自然界中生物的遗传和进化现象时， 生物学家使用适应度这个术语来 度量某个物种对于其生存环境的适应程度。对生存环境适应程度较高的物种将有 更多的繁殖机会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少， 甚至会逐渐灭绝。与此相类似，遗传算法中也使用适应度这个概

47、念来度量群体中 各个个体在优化计算中有可能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；而适应度较低的个体遗传到下一代 的概率就相对小一些。度量个体适应度的函数称为适应度函数。遗传算法在进化 搜索中基本上不用外部信息，仅用目标函数即适应度函数为依据。 遗传算法的目 标函数不受连续可微的约束，且定义域可以为任意集合。对目标函数的唯一要求 是，针对输入可计算出能加以比较的结果。4 遗传操作为了优化解，必须获得优秀的基因和增大搜索空间。 遗传操作是遗传算法的 核心部分。在遗传算法中，通过编码组成初始群体后，遗传操作的任务就是对群 体中的个体按照它们对环境适应的程

48、度 （适应度评估）施加一定的操作，从而实 现优胜劣汰的进化过程。通过选择，用高适应度的个体替换低适应度的个体， 从 而保证了搜索是朝着优化的方向进行。为防止个体的多样化丢失，将配对个体以 交叉概率Pc （即各代中交叉产生的后代数与种群的个体数之比）进行交叉。交 叉算子组合群体中有价值的信息， 产生新的信息，具有遗传功能。当个体已接近 最优解领域时，利用变异算子的局部随机搜索能力可以加速向最优解收敛。将配对个体以变异概率Pm （指种群变异基因数在总基因数中的百分比）产生变异。 从优化搜索的角度而言，遗传操作可使问题的解，一代又一代地优化，并逼近最 优解。5 遗传算法的收敛性我们已就遗传算法中的编

49、码、适应度函数、选择、交叉和变异等主要操作的 基本内容及设计进行了介绍。作为一种搜索算法，遗传算法通过对这些操作的适 当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索。2.6.4遗传算法的运行步骤和流程图1 .运行步骤遗传算法是一个迭代过程，它模仿生物在自然环境中的遗传和进化机理， 反 复将选择算子、交叉算子、变异算子作用于群体，最终可得到问题的最优解或近 似最优解。对于一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法。第一步：确定决策变量及其各种约束条件，即确定出个体的表现型和问题的 搜索空间（解空间）。第二步：建立优化模型，即确定出目标函数的类型（是

50、求目标函数的最大值 还是求目标函数的最小值）及其数学描述形式或量化方法。第三步：确定表示可行解的染色体编码方法， 也即确定出个体的基因型及遗 传算法的遗传空间。第四步：确定解码方法，即确定出由个体基因型到个体表现型的对应关系或 转换方法。第五步：确定个体适应度的量化评价方法，即确定出由目标函数值到个体适 应度的转换规则。第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算 子的具体操作方法。2. 遗传算法实现的具体流程图图2.1遗传算法实现的具体流程图第三章混流装配线的投产排序数学建模及排序方法3.1混流总装线投产排序建模思想由前面两章的叙述可知，汽车装配车间混流生产线上不同车型

51、所需作业时间 有时不同，有的低于流水线节拍，而有的又高于流水线节拍。如果连续地投入一 种相同的车型，会使某些装配工位非常紧张，出现连续的长时间满负荷作业，而 另外一些装配工位负荷不足，这样就有可能使生产线出现暗灯临时性停线等不良 的后果。为了解决各个装配工位忙闲不均的矛盾， 同时又要实现订单拉动生产线，只 有通过均衡混流生产计划和控制混流产品投产顺序。优化的产品投产顺序，应使 各工位的忙闲程度最为均匀，即各个工位的工作超载和等待时间总和最小化。在 此思想的基础上建立混流生产线投产排序的数学模型。3.2混流装配线投产排序数学建模对于批量制造的产品，在实践中采用循环排序法2728，这种方法的优点已

52、被实践所证实。设:某汽车制造企业的一条混流生产线生产M种车型，规定一班为一个计划期，假设一个计划期内对 M种车型的需求量分别为 D1，D2，,， DM，假设D1，D2，,， DM 最大公 约数 d,令 ri=Di/d( i=1，2，,， M)，在生产运M作中，只针对以R=v ri为单位的车型进 行排序，称为一个循环流程。i =1重复进行d个流程，可得一个计划期内所有产品的投产顺序。 本文的投产排序算 法是针对一个循环流程进行的。由于混合车型装配线上车型数为 M，在一个生产循环里，这 M种车型的需 求量分别r1 , r2 ,，rM，则计划期内的一个生产循环中，M种车型的总需求量 是：m工 r i

53、R=i(3-1)i 二 1在计划期内的一个生产循环中，对 M种车型装配车辆进行投产排序，也就 是对总需求量R辆车进行投产排序，即在一个生产循环中，一共有 R! /(r1!*r2 ! *,， rM !)种投产顺序。设T （j, i） （j=1 , 2, , , N; i=1, 2, , , R）为针对这R辆车的某一投 产序列r1, r2, , , rR,各个装配岗位（j=1, 2, , , N）装配不同车型i （i=1, 2, , , R）所需的时间，T（j, i）组成一个矩阵（表3） PI X。表3 对应某1投产顺序的工位、操作时间矩阵 PIXi代表辆车的某 投产序列r1, r2, , , r

54、R,1235Rj代表工位1T11T12T125T 1R2T21T 22T235T 2R3T31T 32T335T 3R55555XTx1Tx2T X35Txr前面介绍过，在装配流水线上某装配工位j,可能出现的2种情况：一种是, 某一种i车型的车辆装配结束后，下一个品种i+ 1的车辆尚未进入该工位，操作 工回到工作起点等待，处于闲置状态；另外一种是，操作工在其自身的工位未能 完成这一种i车型的装配任务，剩余的工作要停线完成或是由线外的工人即时帮 助完成，这就是处于超负荷作业状态。由于车间每天的生产任务是不同的，因此, 每个岗位的闲置状态和超载状态是不相同的，它和每天流过这个岗位的混流车辆投产序列

55、相关。下面我们举例，来分析一下第j个岗位的工作情况。在每一次操作循环开始时，操作工在工位 j的起点等待装配车辆的到来，即 开始时间Sj1 = 0, j = 1, 2, .,N, （j为工位，1代表在该工位装配的第1辆车）从PIX矩阵可知，在第j工位内，投产序列中第i个产品的加工时间为Tji （j为工位，i代表在该工位装配的第i辆车）个时间单位，从而可计算出其结束 时间为Eji = Sji+Tji。当n= R+ 1时，即装配最后一辆车时Ejn=Sjn+Tj1我们假设产品的投放速率是连续的并且是固定的，即为流水线节拍时间R操作工在工位j中第i个车辆在Eji结束装配后，操作工立即回到下一个车辆的 装

56、配起点（Tji包括了装配工从第i个车辆装配结束点返回到FPS起点的时间） 因此，装配车辆序列中第i+ 1个产品加工起点为有2种情况1、当操作工提前完成装配，即 Eji R,操作工需继续完成装配。 这样，他下一辆车的装配起点为 Eji - R;综合 2 种情况，S (j，i+1)= max 0,Eji R并且，在第1种情况下，投产序列中第i个车辆在第j个工位有工位闲置 工位闲置时间 Idleji = max 0,R Eji而在第2种情况下，投产序列中第i个车辆在第j个工位有工位超载 工位超载时间 Overtji = max 0,Sji + Tji R(i= 1,2,ooo R, j= 1,2,ooo，N 0 j为工位，i代表在某1投产序列中该工位 装配的第i辆车)。因此，对于这种投产序列，所有装配岗位的闲置与超载时间的总和为X R二二(Idle ji Over