有兼容作业元素的混流装配线平衡问题研究*

龚 轲，丁武学，王栓虎

（南京理工大学机械工程学院，南京 210094）

有兼容作业元素的混流装配线平衡问题研究*

龚 轲，丁武学，王栓虎

（南京理工大学机械工程学院，南京 210094）

基于第Ⅰ类混流装配线平衡问题，对作业元素之间的兼容性问题进行了研究，即将那些需要使用到相同作业设备，或受某些工艺条件约束而需要在同一工作站上完成的兼容作业元素分配到同一工作站，以使企业在建立混流装配线时，避免设备重复配置造成的成本浪费，并以空闲时间最小、工作站之间负荷均衡和在装配不同产品时，同一工作站内负荷均衡为优化目标建立了多目标优化的数学模型，然后采用遗传算法对该模型进行求解，最后通过实例来分析验证所提方法的有效性。

兼容作业元素；混流装配线；装配线平衡；遗传算法

0 引言

装配线是由工作站、物流对象、作业元素和操作人员按一定的规则组成的生产系统，产品依次通过装配线上的各个工作站逐渐成为成品下线［1-2］。装配线平衡就是在工艺约束的条件下，将作业元素分配到各工作站，使各工作站负荷尽可能均衡，达到空闲和超载时间最少的目的［3］。自美国学者Bryton B第一次提出装配线平衡问题以来，装配线平衡就一直是装配线设计领域研究的重点问题。随着人们的需求逐渐变得多样化，装配线上生产的产品类型也逐渐从单品种生产向多品种混合生产转变。与单品种装配线平衡相比，混流装配线平衡显得更为困难，其原因在于［4］：①单品种装配线上，各作业元素的作业时间是固定的，而混流装配线上，在装配不同产品时，同一作业元素其作业时间不尽相同，有时还相差很大；②在同步传送的情况下，混流装配线的生产节拍必须等于任意工作站上的最大作业时间，才能保证所有工位上的作业任务在该工位内完成，这就会产生较大的空闲时间，使装配线效率低下。

由于单品种装配线的平衡相对简单，所以自装配线平衡问题提出来之后，关于单品种装配线平衡的研究非常多，但关于混流装配线平衡问题的研究一直进展缓慢。直到1970年，ThomoPoulos NT首次运用联合作业优先图的概念，将混流装配线平衡问题转化为单品种装配线平衡问题来处理，才使得混流装配线平衡问题的研究有了突破性的进展，目前关于混流装配线的研究依然采用这种思路。由于装配线平衡问题是典型的NP难题，无法通过解析法求得其精确解，所以目前对于混流装配线平衡问题的研究主要侧重于对特定问题的数学建模以及模型求解的研究，即针对具体问题建立相应的数学模型，和寻找一种更有效的方法来求解数学模型。

在产品的装配过程中，在完成某些作业元素时，需要使用到相同的作业设备，为了避免设备重复配置造成投资成本的浪费，可将这些作业元素分配到同一工作站，还有一些作业元素，由于受工艺条件的约束也必须分配到同一工作站进行作业，将这些需要分配到同一工作站的作业元素称为兼容元素。目前有关装配线平衡问题的研究虽然多，但涉及到作业元素兼容性的相关文献却非常的少。如文献［5-8］都对特定问题进行了研究，并建立了相应的数学模型，提出了有效的求解方法，但这些文献都没有涉及到作业元素兼容性的问题。

1 模型建立

混流装配线平衡问题主要可分为2类，第Ⅰ类装配线平衡主要针对新装配线的建立，即给定生产节拍，使工作站数量最少；第Ⅱ类装配线平衡主要是对已建立的装配线进行优化，即给定工作站数，使生产节拍最小。本文基于第Ⅰ类装配线平衡，再综合考虑作业元素的兼容性，建立如下数学模型：

式中，J1、J2、J3和J为优化目标，CT为生产线节拍，对于第Ⅰ类装配线平衡问题，CT=计划期内有效工作时间/计划总产量；qm为第m种产品在预期总产量中的比例，在计划期内qm=产品m的计划产量/计划总产量；tmk为第m种产品在工作站k的单件作业时间；S为工作站数；N为在混流装配线上完成产品装配的作业元素数；xik为决策变量，如果xik=1则代表作业元素i被分配到工作站k，如果xik=0则代表第i项作业元素没有被分配到工作站k；tim表示第m种产品在完成第i项作业元素时所需的作业时间，如果第m种产品不需要进行第i项作业元素，则tim=0；Fi表示在作业优先关系中，不能在作业元素i之前先完成的作业元素集；ZP为必须分配到同一工位的作业元素集合，即兼容元素集；w1、w2、w3为权重系数，其满足w1+w2+w3=1，w1、w2、w3的大小由决策者根据其侧重点选取。

式（1）、式（2）和式（3）分别为三个不同的优化目标。式（1）为空闲时间，在生产节拍给定的情况下，装配线空闲时间最小，则意味着工作站数量最少，生产效率最高，因此J1可代表工作站数量最小化，通过这样的转换使工作站数最小化的优化目标与其他两个优化目标统一于相同的数量级；式（2）为装配线各工作站负荷的标准差，其值越小代表装配线各工作站之间负荷越均匀；式（3）为工作站上不同产品作业时间的标准差的平均值，其值越小代表在同一工位上装配不同产品时，该工位的作业时间波动越小。J1、J2和J3通过加权求和得到综合优化目标函数式（4）。

约束式（5）可以确保完成产品装配的所有作业元素都只被分配到一个工作站；约束式（6）确保了作业元素的优先约束关系；等式（7）是计算第m种产品在工作站k上完成单件产品所需的作业时间；约束式（8）是作业时间约束，它保证了所有工位上都不会出现超时现象；约束式（9）为兼容性约束条件，它可以确保兼容元素被分配到同一工作站；约束式（10）给出了决策变量的取值范围。

2 模型求解

装配线平衡问题是典型的NP难题，对于NP难题的求解，到目前为止仍然没有找到一个多项式时间的有效算法，模拟生物进化的遗传算法由于其强大的搜索能力，能以很大的概率找到整体最优解，因而在求解NP难题的研究中有着广泛的应用。本文将选用遗传算法求解该模型。

2.1编码和解码

编码方式对遗传算子，尤其是对杂交和变异算子的功能和设计有很大的影响，最终会影响到遗传算法的收敛速度和解的质量。Gen M［9］已经证明了在工程优化问题中，实数编码是一种较好的编码方式。本文采用一串长度等于作业元素数的数字串作为编码基因，每个基因位代表一个作业元素，作业元素按其编号顺序依次排列在基因位上，每一个基因值代表该处作业元素被分配到的工位。图1为基因的编码和解码示例。

图1 基因的编码和解码示例

2.2 适应度函数

由于数学模型的优化目标是使目标函数最小化，而在生物进化的过程中，总是希望个体的适应度越大越好，故适应度函数可设计为：

式中，J为目标函数，u为适应度函数参数，其值等于当前种群中目标函数J的最大值。

2.3 遗传算子

2.3.1 选择

由于随机联赛选择不仅能有效地避免超级个体的影响，还能在一定程度上避免早熟，因此本文采用随机联赛选择，随机的从当前种群中选取一定数量的个体，然后选择其中适应度最大的个体作为下一代的父代，重复该过程，直至完成个体的选取。

2.3.2 交叉

交叉是为了将原有的优良基因遗传给下一代，并产生包含新的基因信息的新个体。本文选用两点交叉的方式进行交叉重组，由于在本数学模型中，个体受到作业时间和作业优先顺序等多种约束，交叉之后的个体不一定是有效个体，对于这种无效个体，应进行适当的调整使其满足约束要求。

2.3.3 变异

本文采用均匀性变异，在父代个体中随机选择一个基因位，然后以其取值范围内一个均匀分布的随机数取代该基因位的当前值。变异也会产生无效个体，因此需要对变异后的个体进行检验，若变异之后的个体无效，则重新选择父代个体进行变异。

2.3.4 确定交叉和变异概率

交叉概率和变异概率的选择影响着遗传算法的行为和性能。为提高交叉和变异质量，防止早熟和收敛速度过慢，交叉概率和变异概率均采用自适应方式，使交叉概率和变异概率与进化程度相关联。交叉概率Pc和变异概率Pm的具体表达式为

式中k1、k2、k3和k4为常数，其取值为（0，1）；fmax和favg分别为上代种群中最大适应值和平均适应值；fc为要交叉的两个体中较大的适应值；fm为需要变异个体的适应值。

3 实例分析

现通过算例分析文中所提方法的有效性。设在同一装配线上需装配A、B、C三种产品，三种产品的综合作业优先顺序图如图2所示，各作业元素的作业时间如表1所示，其中作业元素11与12、17与19均需要使用到相同的工具，即它们是兼容的作业元素。一个工作日内三种产品的计划产量分别为DA=400件，DB=200件，DC=300件，一个工作日8小时，则按生产节拍的计算公式可确定装配线节拍为32s。

图2 综合作业优先顺序图

表1 A、B、C三种产品各作业元素的标准工时

按本文所建数学模型，取权重系数w1、w2和w3均为1/3，用MATLAB按本文所提遗传算法编写程序（其中k1=0.6，k2=0.9，k3=0.1，k4=0.1），经过100代进化后，获得最优个体，最优个体的解码结果如表2所示。结果表明本文所提方法不仅能将兼容元素分配到相同的工作站，还能使装配线有较高的利用率。

表2 运算结果

4 总结

本文在有关第Ⅰ类混流装配线平衡研究的基础上，对第Ⅰ类混流装配线平衡问题进行了进一步的研究，在考虑装配线空闲时间、工作站之间负荷均衡，以及同一工作站上装配不同产品时的负荷均衡等问题的同时，还考虑了作业元素之间的兼容性，即将需要使用到相同作业工具的作业元素，或因其他工艺约束而必须在同一工位上进行作业的作业元素，分配到同一工位，这能使企业在投资建立装配线时，避免因设备重复配置而造成的成本浪费。文章最后的实例分析验证了本文所提方法的有效性。

［1］胡罗克，陈勇，唐任仲.混流装配线平衡分析与算法设计［J］.现代制造工程，2011（9）：1-4，9.

［2］X Delorme，O Battaïa，A Dolgui.Multi-objective Approaches for Design of Assembly Lines［J］.Applications of Multi-Criteria and Game Theory Approaches，2014：31-56.

［3］周小丽，曹振新.混流装配线的规划设计与仿真研究［J］.机床与液压，2008，36（4）：344-348.

［4］于兆勤，苏平.基于遗传算法和仿真分析的混合装配线平衡问题研究［J］.计算机集成制造系统，2008，14（6）：1120-1129.

［5］苑明海，李东波，于敏建.面向大规模定制的混流装配线平衡研究［J］.计算机集成制造系统，2008，14（1）：79-83，131.

［6］Yazgan H R，Beypinar I，Boran S，et al.A new algorithm and multi-response Taguchi method to solve line balancing problem in an automotive industry［J］.The International Journal of Advanced Manufacturing Technology，2011，57：379-392.

［7］ÜgurÖzcan，Bilal Toklu.Balancing of mixed-model two-sided assembly lines［J］.Computers&Industrial Engineering，2009，57（1）：217-227.

［8］CemalettinÖ，Semra T，Brahim Hnich M，et al.Balancing and scheduling of flexible mixed model assembly lines［J］.Constraints，2013，18：434-469.

［9］Gen M，Cheng R.Genetic Algorithms and Engineering Optimization［M］.Toronto：John Wiley&Sons，Inc，2000.

（编辑 赵蓉）

Mixed-model Assembly Line Balancing Problem with Compatible Tasks Research

GONG Ke，DING Wu-xue，WANG Shuan-hu
（School of Mechanical Engineering，Nanjing University of Science and Technology，Nanjing 210094，China）

The compatible tasks problem based on MMALBP-Ⅰwas researched to make compatible tasks used the same equipment or constrained by some process conditions in the same work station，and the enterprise could reduce the amount of equipment and cost for it.A mathematical programming model was built for it and it had three objectives，such as minimize idle time of workstation，balancing workload between stations and balancing workload assembling different model in the same station and a genetic algorithm was used to solve it.Finally an example was showed to prove the efficiency of the approach.

compatible tasks；mixed-model assembly line；assembly line balancing；genetic algorithm

TH166；TG65

A

1001-2265（2015）06-0134-03 DOI：10.13462/j.cnki.mmtamt.2015.06.036

2014-10-12；

2014-10-31

江苏省产学研前瞻性联合研究项目（BY2014004-02）

龚轲（1988—），男，湖南娄底人，南京理工大学硕士研究生，研究方向为混流装配线的规划与设计，（E-mail）gongke0613@163.com。