摘 要

由于通过使用混流装配线，企业可以在少量增加固定资产投入的情况下尽可能满足消费者的定制化需求，混流装配线已经成为了汽车制造业的首选。

本文针对第二类混流装配线平衡问题建立了一个包含更低生产节拍、不平衡率、更低成本的多目标加权简化模型，采用改进的粒子群优化算法求解该问题，研究了改进粒子群优化算法的效果。

第一章介绍本文的研究背景与研究意义，编写了文献综述，简单介绍了混流装配线平衡问题、多目标优化方法、以及粒子群算法的研究现状。

第二章对混流装配线平衡问题进行了基本描述，结合学界以前的对该问题的探索对MMALB问题建立一种考虑比以前更多实际情况的改进模型。

第三章将针对本文模型进行算法设计，提出了一种结合模拟退火算法与遗传算法的改进粒子群算法，最后选取了一个小规模问题对算法性能进行了测试。

第四章验证改进粒子群算法在求解混流装配线平衡问题中的有效性，参考其他文献中的案例，使用MATLAB编程求解。

第五章对本文关于MMALB以及改进PSO的研究进行了总结，并对此进行了展望。

本文对使用粒子群算法求解MMALB问题有一定实际意义，为企业混流装配线的平衡提供了理论支持，帮助企业选择更高效、准确的方式优化装配线，进而实现生产效率的优化。

关键词：混流装配线平衡；多目标优化；粒子群算法

Abstract

With the use of mixed-model assembly line, enterprises can meet the customized needs of consumers as much as possible with a small increase in fixed assets investment. Mixed-model assembly line has become the preferred choice of automobile manufacturing industry.

In this paper, a multi-objective weighted simplified model with lower production rhythm, unbalance rate and lower cost is established for the second kind of mixed-model assembly line balancing problem. The improved particle swarm optimization algorithm is used to solve the problem, and the effect of the improved particle swarm optimization algorithm is studied.

Chapter 1 introduces the research background and significance of this paper, compiles a literature review, briefly introduces the mixed-flow assembly line balancing problem, multi-objective optimization method, and the research status of particle swarm optimization.

Chapter 2 describes the balancing problem of mixed-model assembly line, and establishes an improved model of MMALB problem considering more actual conditions.

In Chapter 3, an improved particle swarm optimization algorithm combining simulated annealing algorithm and genetic algorithm is proposed. Finally, a small-scale problem is selected to test the performance of the algorithm.

Chapter 4 verifies the effectiveness of the improved particle swarm optimization algorithm in solving mixed-model assembly line balancing problem. Referring to the cases in other literatures, it uses MATLAB programming to solve the problem.

Chapter 5 summarizes the research of this paper and looks forward to it.

This paper has some practical significance for solving MMALB problem by using particle swarm optimization. It also provides theoretical support for the balance of mixed-model assembly line, helps enterprises choose more efficient and accurate ways to optimize assembly line, and then realizes the optimization of production efficiency.

Key words: mixed-model assembly line balancing; multi-objective optimization; particle swarm optimization

目 录

第一章 绪论 1

1.1课题背景 1

1.2目的与意义 1

1.3国内外研究现状 1

1.3.1装配线平衡的问题研究 1

1.3.1.1混流装配线平衡的研究现状 2

1.3.1.2多目标优化的处理方法 3

1.3.2粒子群算法的研究 4

1.4研究内容及思路 4

1.4.1 研究内容 4

1.4.2 研究重点与难点 4

1.4.3 研究方法与技术路线 5

第二章 多目标混流装配线平衡问题的模型构建 6

2.1 装配线概述 6

2.1.1 混流装配线 6

2.1.2 混流装配线的相关术语 6

2.2 装配线平衡问题的分类 7

2.3 问题描述与模型构建 9

2.3.1 问题描述 9

2.3.2 问题基本假设 9

2.3.3 模型中所用符号说明 10

2.3.4 模型构建 11

2.4 本章小结 12

第三章 改进粒子群算法的MMALB问题应用 12

3.1 标准粒子群算法 12

3.2模拟退火算法与交叉操作概述 13

3.3 标准粒子群算法在求解MMALB问题中存在的问题 14

3.3.1 局部最优解问题 14

3.3.2 标准粒子群算法在解有约束0-1整数规划中遇到的问题 15

3.4 用于MMALB改进粒子群算法的介绍与流程分析 15

3.4.1粒子编码解码设计——优先权重法 17

3.4.2装配任务的分配 17

3.4.3适应度计算 18

3.4.4确定群体引导者 18

3.4.5结合模拟退火算法与压缩因子改进更新种群 18

3.4.6交叉操作 19

3.4.7重复迭代 19

3.5算法可行性测试 19

3.6 本章小结 21

第四章 应用实例——以某汽车内饰装配线为例 21

4.1算例描述 21

4.2数据分析 21

4.3 结果分析 25

4.4 改进粒子群算法的性能评估 31

4.5 本章小结 31

第五章 总结与展望 32

5.1全文总结 32

5.2本文创新点 32

5.3 研究展望 32

参考文献 33

附录A 算法性能测试结果 34

附录B 算例数据 38

致谢 47

第一章 绪论

1.1课题背景

在中国制造2025的浪潮下，制造业逐步从大规模生产走向定制化生产。特别是我国汽车行业，上个世纪的单品种装配线已经一去不复返了。为了满足人民群众日益增长的物质需求以及面对消费升级转型的压力，汽车制造企业需要为顾客提供同一车型的多种配置，以最大限度的占领细分市场。

由于通过使用混流装配线，企业可以在少量增加固定资产投入的情况下尽可能满足消费者的定制化需求，进而提升消费者满意度与品牌忠诚度。混流装配线已经成为了汽车制造业的首选。

1.2目的与意义

众所周知，衡量企业经营好坏的重要指标之一公认是资产收益率，而资产收益率可以使用库存周转率*利润率来计算， 这意味着企业提升自身单位资产盈利能力有两种方式：提升利润率或者提升库存周转率。 而库存周转率与平均库存成反比例函数关系，可以说，提升企业盈利能力的重要手段是降低库存。

为了实现按单生产效率的优化，混流装配线平衡便显得十分重要了。生产效率不仅直接关乎毛利率，更关乎库存周转率，通过对混流装配线平衡问题的研究，实现生产效率的提升，可以让资产收益率以指数速度上升。

据统计，虽然装配线平衡问题的研究已经比较成熟，但是真正使用先进技术优化装配线的企业并不多。因此，研究更贴近实际、效率更高的优化方法是有必要的。

本文针对第二类混流装配线平衡问题建立了一个包含更低生产节拍、不平衡率、更低成本的多目标加权简化模型，并使用改进粒子群算法对问题求解，并针对改进粒子群算法的效果进行了研究。通过这些研究，本文为企业混流装配线的平衡提供了理论支持，帮助企业选择更高效、准确的方式优化装配线，进而实现生产效率的优化与经营效果的提升。

1.3国内外研究现状

1.3.1装配线平衡的问题研究

关于装配线平衡问题的研究由来已久。主要的研究方法分为两种：最优化方法（包括线性规划法、动态规划法等方法）与智能优化算法（比如神经反馈网络算法、循环神经网络、模拟退火算法、禁忌搜索法、前向神经反馈网络算法、遗传算法、蚁群算法、深度信念网络等）。

混流装配线问题（Maxed Model Assembly Line Balancing Problem，也即MMALBP）的求解的关键在于将多个结构类似的产品的作业顺序图转变成为一个能反映所有产品的优先顺序的综合作业顺序图，通过这种方法，一个混流装配线问题就可以通过单一产品装配线的解决方法进行求解。

由于装配线平衡对于工业的重要意义，学界有大量关于此问题的研究。装配线平衡（Assembly Line Balancing，也即ALB）通常包括一个寻找帮助优化装配线平衡决策过程的优化模型。Salveson^[1]首次尝试使用数学解决ALB问题，学术工作主要集中在如何把任务分配给工作站。

此前的ALB问题普遍都做了很多简化的假设，这些研究被 Baybars^[2]称为简单装配线平衡（Simple Assembly Line Balancing SALB）。

后续的研究工作逐步延伸到更加实际的问题，Becker和Scholl^[3]在2006年的研究涉及了U形装配线，平行工作站以及替代流程。这些研究被称为一般平衡问题。

对ALB的学术研究与现实中的ALB问题仍然相差甚远。20世纪70年代（Chase，1974）和20世纪80年代（Schöniger和Spingler，1989）的实地调查显示，当时只有极少数公司使用数学算法进行装配线平衡优化。显然，该问题在实际生产中缺乏学术研究的应用。

1.3.1.1混流装配线平衡的研究现状

而混流装配线平衡问题的研究则到1962年Wester L与Kibridge 联合发表的《Heuristic Line Balancing- A case》才正式确定并界定了混流装配线的两种问题。到了1970年Thomopoulos的《考虑平滑工作站分配的混流装配线平衡》则首次尝试使用将混流装配线等价为单品种装配线问题处理，通过将多个类似的顺序图化为一个“综合优先顺序图”，研究者可以使用单品种装配线的方法解决混流装配线的问题。这种综合优先图法至为止仍是用于解决混流装配线平衡问题的标准思路。^[4]

新世纪以来，国外继续对该问题进行探究。

Gokcen和Erel ^[5]开发了一种二元整数公式，用于第一类混流装配线平衡问题，在给定的生产节拍下最小化工作站数量。

Haqetal^[6]为混流装配线平衡问题开发了一种混合遗传算法，其目标是在给定的生产节拍里最小化工作站的数量。他们使用了改进的排序位置权重方法以生成遗传算法的初始解。Fattahi和Salehi ^[7] 使用模拟退火算法解决混合模型装配线平衡问题，希望最小化效用与闲置成本。他们希望把装配线平衡问题与投产问题结合，确定最佳的参数。Hamta等人^[8]针对单产品装配线开发了一种混合粒子群优化算法（HPSO），其可变邻域搜索（VNS）作为其局部搜索算法，并制定了多个目标：最小化生产节拍，总设备成本和平滑度指数。

李险峰^[9]将遗传算法与模拟退火算法结合，针对遗传算法的早熟问题经行了改进。杨卓^[10]使用蚁群算法，将装配线平衡问题与装配线投产问题混合求解。刘芹^[11]针对企业生产运作方式和目的，结合实际发动机生产线，提出了汽车发动机混流装配线排序问题的多目标优化函数。吴永明等人^[12]基于改进粒子群算法研究了简单装配线平衡问题。孙宝凤等人^[13]针对混流装配线投产排序建立了双目标决策模型。

罗利飞^[14]等人针对混流制造系统装配线平衡和物料配送车辆路径优化问题,从优化目标、影响因素和约束条件等方面,建立了以装配线平衡最小均衡系统、物料小车最短行驶距离和最小车辆利用率最大为优化目标的多目标混流装配线模型。姚午厚^[15]建立了装配节拍、平滑指数和工人人力成本最小化的细平衡模型，对智能家居行业混流装配线平衡与排序方法进行了研究

1.3.1.2多目标优化的处理方法

装配线平衡多目标优化目前有三种处理方式：经典方法、目标优化法、帕累托解法。

第一种，即经典处理方法，根据一定的权重将多目标问题转化为单目标问题。 这种方法的优势在于它为决策者提供了最适合他们需求的解决方案。

第二种处理方式时按照“目标优化”的方法，对多个目标按优先级排序，按优先级从高到低依次优化。（事实上，由于特定的目标最优常常仅有少数情况，这种优化方式基本只会优化优先级最高的目标）。

第三种则参考“帕累托解”的理论，在引入“非劣解”与“支配”的概念。

所谓“非劣解”，即不存在其他解比该解在所有目标上都更优。所谓“支配”，即假设解A支配解B，那么解A在所有目标上都优于解B。这种方法可以求得一个帕累托解集，每个解都不被其他解支配。虽然这种方法可以提供大量解给决策者选择，但是它们未必合适。原因在于决策者可能并不希望得到一个单一方面的最优解，而希望得到多个目标综合起来的较优解，最终问题又会回到使用加权法选择上。然而由于大量的“被支配解”已经被舍弃，对实际决策的支持能力并不一定强于经典方法。

1.3.2粒子群算法的研究

粒子群算法（Particle Swarm Optimization，以下简称PSO）是一种比较新的智能优化算法，首先被Kennedy^[16]等人提出，尽管PSO的计算方法与遗传算法类似，不过诸如杂交、变异等方式，在PSO中并没有被采用。PSO通过模仿群体行为（比如鸟群）来搜索更优解，因此具有简单、控制参数较少、容易实现等诸多优点。

1.4研究内容及思路

1.4.1 研究内容

本文研究内容如下：

第一章介绍本文的研究背景与研究意义，并查阅了关于ALB问题的相关文献，据此编写了文献综述，简单介绍了混流装配线平衡问题、多目标优化方法、以及粒子群算法的研究现状。

第二章首先对混流装配线平衡问题进行了基本描述，然后解释了本章将用到的相关概念。之后分析MMALB问题的建模方法、完整阐述了学界对于ALB问题的界定，这为本文的建模提供了基本的理论基础。之后的内容提出了模型的详细假定，并基于以上假定为结合前人的研究对MMALB问题建立一种考虑更多实际情况的改进模型，以了使模型使之更符合实际情况、提升研究对决策者的现实意义。

第三章将针对本文模型进行算法设计，并针对MMALB问题的特点对粒子群算法进行了改进。本章首先简单介绍了基本粒子群算法、以及将用于本文的改进的模拟退火算法与遗传算法，之后阐述了基本粒子群算法在求解MMALB问题上的两处缺陷，并分析原因。然后，针对造成缺陷的原因，提出了一种结合模拟退火算法与遗传算法的改进粒子群算法，并详细介绍了该算法的流程与具体实现方式。本章最后选取了一个小规模问题对算法性能进行了测试。

第四章为了验证第三章中提出了改进粒子群算法在求解混流装配线平衡问题中的有效性，参考了其他文献中的案例，并增加了案例中的约束，使之更加符合现实情况，并使用MATLAB编程求解。在最后将会评估改进的有效性。

第五章进行了全文总结与展望。