摘 要

本论文主要从生产系统入手，先根据生产系统的复杂程度介绍了NP问题相关的基础知识，然后引入流水线的概念，先后阐述了流水线的期量标准以及流水线的分类，重点指出在流水线广泛被应用的今天，仍存在制约生产效率的问题，即流水线平衡问题，接下来从流水线平衡问题入手，阐述了一些应对简单问题时可采用的数学模型，以及解决方法。在这些知识的铺垫下，提出混流生产线的生产平衡问题，这种问题相对复杂，以A公司现有的生产为依据，通过调查收集相关数据，计算出现有的生产线平衡率，通过建立数学模型，采用遗传算法，使用MATLAB软件进行编程求解优化，根据求解结果给出了新的工作站排产投放顺序，与之前的生产方式进行对比，以表明优化之后该公司的生产线平衡率得到了大幅提升，从而提高了生产效益，并且在之后说明了生产线平衡率提升的原因。

关键词：混流生产线；生产线平衡率；遗传算法

ABSTRACT

This paper mainly starts from the production system, and introduces the basic knowledge related to NP problem according to the complexity of the production system. Then introduce the concept of the pipeline, and elaborate the pipeline standard and the classification of the pipeline. It is pointed out that today, when the pipeline is widely used, there are still problems that restrict production efficiency, that is, the problem of pipeline balance. The next step is to start with the problem of pipeline balancing, and explain some mathematical models and solutions that can be used to deal with simple problems. Under the guidance of these knowledge, the production balance problem of the mixed flow production line is proposed. This kind of problem is relatively complicated. Based on the existing production of Company A, the relevant data is collected through investigation, and the equilibrium rate of the existing production line is calculated. By establishing a mathematical model, Using genetic algorithms, Using MATLAB software to optimize the programming solution, according to the solution results, the new workstation scheduling sequence is given, which is compared with the previous production method to show that the company's production line balance rate has been greatly improved after optimization, thereby improving production efficiency. And the reasons for the increase in the balance rate of the production line are explained later.

KEYWORDS: Mixed flow production line; Production line balance rate; Genetic algorithm

目 录

1.绪论 1

2. NP-hard问题与NP完全问题 3

2.1复杂系统概述 3

2.2 P、NP、NPC、NP-Hard问题 4

2.2.1 预备知识 4

2.2.2 P、NP、NPC、NP-Hard问题的概念及认识 4

3. 流水线平衡 6

3.1流水线的期量标准 6

3.2流水线的分类 7

3.3流水线平衡问题的描述及平衡方法 8

4.混流生产线 11

4.1混流生产线的平衡问题 11

4.2混流生产线案例 11

5.混流生产线数学建模及遗传算法 17

5.1数学建模 17

5.2遗传算法简介 17

6.总结 21

参考文献 22

致谢 24

1.绪论

随着经济全球化的发展以及科技的长足进步，国外先进的汽车生产企业已经熟练的运用并推广拉式生产(JIT)的理念，从而可以更快速地相应市场及客户需求，提高了整个生产的柔性，使得每个生产线上可以完成多种产品的生产装配。由于我国市场的不断扩张，客户需求量的不断增加，拉式生产(JIT)目前已经是我国大多数汽车制造商所选用的主要生产方式，并不断地对混流生产线提出越来越高的要求。

1961年，混流生产线的概念和定义首次在国外提出。之后丰田公司提出了GC-1和GC-2两种算法以解决在混流生产的模式下各个工作台的负载问题以及平衡效率问题，在19世纪末20世纪初，有遗传算法，模拟退火算法，最小二乘算法和新的粒子群算法等算法¹，使得在求解混流生产线排产优化及生产平衡等多方面问题是变得方便快。相比于国外，我国在1998年提出混流生产线排产问题，在此领域的研究相对较晚，但发展迅速并得到广泛的应用。与国外的发展经历相类似，都是在不断的寻求新的效率更高的算法对现有的生产线进行不断的改进，以求得最大的效益。

混流生产线的生产方式是在机器设备不变更的情况下，多种不同品种的零件交替生产加工，可以在相同的工作时间内生产多种不同型号产品的流水线。这种生产方式便带来了相应的难题，如它对自动化程度要求较高，对员工的技术要求很高以及如何更优化平衡整个生产线的生产等，如果能对整个混流生产线提出一套相对成熟的排产优化方式，可以有效的解决在生产线上遇到的瓶颈问题，使整个生产线达到平衡，这样就可以使生产线上的人力资源、参与生产制造的原材料都可以得到充分利用，这对一个汽车生产企业及时响应市场需求，避免过量生产或生产不足等都是至关重要的。

制造业的生产线通过细分作业的方法，从而产生多道工序，形成了连续的流水生产线。这样一来，由于细分，使得各个工序的作业难度大大降低，工人不需进行多种作业，运营熟练程度急剧上升，整条生产线的效率也有所提高。但由于采用了工作站的方式，使得各工作站的实际作业时间不能完全等同于生产线的节拍²，这将导致大量非生产性空闲时间，同时，由于每个工作站的节拍不一致，产生了瓶颈工序。不仅损失了有效的工作时间，同时还会由于瓶颈工序产生一定的工序堆积，产生了大量的在制品。因此，为了使上述问题尽可能不在实际生产中出现，需要平均每道工序的操作时间。重新分配瓶颈工作站的工作任务，对相似工序进行合并，实行标准化作业等。

通过一些有效的方法平衡生产线后，可以实现的一些结果如下：

(1)可以直观地看出工人及设备的工作效率有所提升，整条生产线的生产效率大幅提升。

(2)通过对瓶颈工序进行优化，可以缩短单位产品的生产时间，提升单位时间的产出，降低制造成本，增加收益。

(3)减少在制品的数量，这样便可以减少在制品所占用的空间，从而更加合理的对厂区进行布置，提高空间利用率。

(4)减少作业之间的等待时间和每个工作站的非生产性空闲时间。

(5)加强对工人操作的培训，并严格把关，有利于提升工人士气，使工人拥有良好的素养。

(6)容易实现单元化生产，更加柔性的生产，从而对市场需求的变化、生产任务的变更能轻松从容的应对。

2. NP-hard问题与NP完全问题

2.1复杂系统概述

复杂系统(Complex System)是由许多平级要素构成的网络，这些组分通过使用一些既定的规则来对外界复杂的信息进行井然有序地处理，自身可以通过学习和记忆从而做出更好的决策，并不断完善系统以应对更复杂的信息。复杂系统具有一定的规模，是不断进化的系统，如生物的大脑、细胞、社会总体以及生态系统等，每个复杂系统内部都有多个子系统。

复杂系统通常被认为具有以下特征：

1. 非线性

非线性表明整个系统不是简单的组分堆砌而成的，而是各组分之间有机地结合在一起，即整个系统远大于各组分之和，每一个子系统以及部分子系统之和也不能代表系统整体，它们只能是该系统的一部分³。

这表明非线性是复杂系统的先决条件，是必要条件。

(2) 动态性

动态性说明系统是活的，是持续进化的，是远离平衡态的。随着时间的迁移，在自身因素和外界环境的共同影响下，不断的调节自身以适应环境的变化，通过自组织的作用，向更条例有序的方向发展、改进。

(3) 积累效应(初值敏感性)

积累效应说明在系统初期的决策会对整个系统的发展起着巨大的影响。也就是人们常说的“蝴蝶效应”，当系统在起始状态时发生了微小的变化，那么随着时间的迁移，系统不断的演化，这种微小的变化就会慢慢积累并逐步放大，最终会对系统的决策产生巨大的影响。

由于这种敏感性的存在，导致不能对整个系统做出精准地预测。

(4)分型性(结构自相似性)

也就是系统中的各组分以一定的方式与系统整体相关联，同时系统中的各组分之间也会存在自相似性。这为我们研究认识系统整体与各组分提供了思路。

(5)自组织性

自组织性表明每一个子系统或者每一个组分之间的工作在各司其职的条件下，并互相保持着一定的联系，所有的行为是自发组织起来的。这就表明了当一个系统的自组织性越强时，那么这个系统进化和适应新的外界环境的速度就越快。

综上所述，一个复杂系统内部有很多相互联系有机结合的子系统，具有能独立完成相关功能的动态体系，它是一个开放的，自组织的，自相似的非线性系统。就像当我们的身体被刮伤时，人体的自我治愈并不是杂乱无章的，而是各组织、细胞按照相关的步骤严格执行的：身体受损→血小板迅速到达伤口以止血并凝结→身体的免疫系统以发挥体液和细胞免疫功能，来抵御外来细菌病毒的侵害→相关细胞组织的自我修复治愈→伤口愈合；即使当前世界科技已经得到了长足的发展，可是人们还是无法创造出和大脑那样聪明的机器，因为人脑中大约有成百上千亿个脑细胞，而每一个脑细胞所发挥的作用相当于世界上较为先进的计算机，成百上千亿的脑细胞之间的相互联系会导致这种制造复杂度成几何倍数飞速增加，所要面对的难题也是无法想象的。所以我们身边充满了复杂系统。

2.2 P、NP、NPC、NP-Hard问题

2.2.1 预备知识

(1)时间复杂度描述了算法运行所需的时间⁴。随着问题规模不断地的扩大，会导致解空间的爆炸，是用来衡量一个算法求得最优解所需的时间增长的快慢。时间复杂度通常以大O符号表示。任意一个算法的时间复杂度通常可分为两个级别：

–多项式级的时间复杂度，如O(log(n))等；

–非多项式级的，如O(n!)、O(a^n)等。(计算机无法计算这个时间复杂度)

(2)约化，如果可以找到更改规则，则可以根据此规则将任何问题A的输入转换为问题B的输入。 为了使两个问题的输出相同，那么可以说问题A可以简化为问题B.简单地说，问题A可以简化为问题B的意思。 问题B可以通过解决问题A来解决。 也可以说问题A是问题B的特例。同时也告诉了我们一个直观的信息：B的时间复杂度高于或者等于A的时间复杂度。⁵

2.2.2 P、NP、NPC、NP-Hard问题的概念及认识

P(Polynomial)问题是计算起来很快的问题。

如果问题是在多项式的时间复杂度范围之中的，并且可以找到解决它的算法，则该类问题是P问题。它的时间复杂度是多项式级别的，这些问题可以用穷举法求解。

NP(Non-deterministic Polynomial)问题是指存在多项式算法能够解决的非决定性问题，即可以在多项式时间复杂度猜到一个解的问题。⁶ 这类问题计算起来不一定很快，但可以非常快的验证每一个答案的正确与否。

NPC(Non-deterministic Polynomial Complete)问题是在P问题与NP问题上的一个重大进展，它是NP问题的一个子集，也就是说存在一个NP问题，使得该类所有NP问题都可以多项式时间地约化为NPC问题⁷，通过约化的传递性，NP问题被分层并减少，并且最终可以获得足够的广义NP问题，称为NPC问题。根据前面约化的含义，可知NP问题不比NPC问题难。

NPC问题需要满足两个条件：

(1) 是NP问题；

(2) 所有NP问题都可以约化成NPC问题。

旅行商问题是典型的NPC问题，该类问题的求解思路是要在不同的排列组合中寻求这些物品中最有价值的一个子集。本论文要做的生产线平衡问题也是NPC问题⁸。

NP-Hard问题，顾名思义，就是比所有的NP问题都难以求解的问题。NP-Hard问题比NPC问题更广泛，并非所有问题都是NP问题。

NPC问题与NP-Hard问题的区别是：验证一个问题是不是NP-Hard问题不需要验证该问题是不是NP问题，但验证一个问题是不是NPC问题则该问题首先得是NP问题才行，由此便可以知道NPC问题是NP-Hard问题的一个子集。

P、NP、NPC、NP-Hard问题关系文氏图如下：

图2.1 P、NP、NPC、NP-Hard问题关系文氏图

3. 流水线平衡

流水线，目前已经在全世界范围内得到了大量的应用，同时不断地赋予流水线新的内容，新的形式。同时又把流水线称为装配线(Assembly Line)，这种生产方式广泛地使用于工业、制造业，它将整个生产线分为了有限数量的工作单元，每个工作单元只需要处理整个生产过程的某一特定步骤，不直接参与其他生产过程，这样就可以保证整个生产上的分子被充分使用，这提高了每个工作单元的生产率和最终产品的质量。

由此，我们便可以得知流水线具有以下运行特征：

(1)所生产的工件按照一定顺序通过传送带的运输在不同工位上进行加工，而工位上的工人和生产对象不同步前进；

(2)在每一个工位上会有多名操作工人，并且每个工人所进行的工作内容各不相同；

(3)每个工位的工人需要在工件离开工位时完成加工；

(4)每个工位之间不直接产生影响，但是前一个工位上操作工人的工作内容完成情况会影响下一个工位上工人的工作。

接下来，依次从流水线的相关概念、流水线的分类以及流水线的平衡设计来了解流水线。

3.1流水线的期量标准

期量标准，又被称作为作业计划标准，是指通过人们进行科学的分析及准确的计算，所得到的一系列关于生产加工产品在整个生产运作中的数量标准和时间标准。一条流水线能否高效的运行取决于期量标准是否合理。

流水线的期量标准所包含的内容有在制品占用量、节拍以及目视管理图。

(1)在制品占用量

在制品(Work-In-Process)，就是目前还需在流水线上进行加工生产的对象。即从整个生产的开始到结束，以原材料的形式进入生产再以成品的形式入库，是所有未完成所有加工工艺的制品总称。在制品的配额是指在现有技术组织的生产条件下确保整个生产过程连续性所需的数量标准。大多数现代制造业使用JIT的生产方法，因此在生产过程中，过程中产品的趋势越来越少。

(2)节拍(Takt Time)

节拍，又被称为产距时间，指在一条流水线上生产一件成品所需要的时间，即一天总的有效的工作时间除以该天所生产的合格产品。节拍是一种人为制定目标时间，是根据每天的生产计划的变化而变化的，每天的生产计划是取决于当天的市场需求。如一台中央空调在生产线上的节拍为200s，而一辆轿车在生产线上的节拍为160s。

因为在生产中会出现一些设备停机、不合格品、工人操作失误等导致流水线混乱的情况，所以节拍的计算公式如下：

其中，生产线稼动率(Performance Rate)是指，在每日总的生产时间中去掉因为设备机器、员工、不合格品等因素导致的生产线无效的生产时间之后，所得到的该生产线的稼动时间，它与每日总的生产加工时间之比为稼动率⁹。

这便为我们提供了一种思路，可以利用节拍来识别瓶颈工序。瓶颈(Bottleneck)，它指的是一条流水线中生产节拍最慢的环节，并且限制了整个生产线的生产速度。与“木桶定律”相似，生产线的最大容量（生产效率）不依​​赖于具有最短操作时间的站。 这取决于具有最长操作时间的站。当这两个工位的时间差别越大时，该生产线的生产能力损失也就越大。

周期时间指的是在生产线上生产一件产品所需要的时间，周期时间是可以不等于节拍的，但是不论是加班还是提前生产都会提高生产成本，因此在安排流水线的生产计划时，应尽量追求生产周期时间与生产的节拍保持一致，否则将会造成生产成本的上升及生产资源的浪费。

节距时间是可以根据工人的状态进行调节的，它所表示的是经过相邻两个工作站的时间间隔，在生产制造过程中，节距时间总是等于周期时间。但是当工人未进入工作状态时，可先将节距时间调大然后在慢慢调节等于周期时间。

单元化生产是在生产线平衡的基础上实现的，单元化就是将整个生产制造车间分为若干个单元，这些单元按照生产加工的顺序进行排列，以实现在每个单元里生产资料的搬运最小，从而完成一部分或者全部生产进程。通过这样布置厂房，可以将各工位的工序复杂度降低，同时提高了整个生产线的柔性，可以灵活转换生产不同类型的产品，能更快的适应市场多变的需求，使生产商的竞争力提高。每个单元内可以有较短的流水线，其生产方式可以是工位以加工工序顺序进行排列生产或一个工位完成该单元内部所有的工序作业。

(3)目视管理图

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：