H型生产线平衡研究

潘晓勇，巫 江，石宇强，石小秋

PAN Xiao-yong1,WU Jiang1,SHI Yu-qiang2,SHI Xiao-qiu2

（1.四川长虹电器股份有限公司 工程技术中心，绵阳 621000；2.西南科技大学 制造科学与工程学院，绵阳 621010）

0 引言

生产线平衡问题（Line Balancing Problem,简称LBP）是一个组合优化问题，1954年由美国人Bryton B提出并开始着手解决。在此之后，许多学者发表大量论文以解决这类组合优化问题，平衡方法有：数学最优化方法、启发式算法以及工业工程的工作研究方法；对生产线类型的研究包括直线型和U型生产线。

文献[1]和[2]提出了遗传算法和改进遗传算法求解生产线平衡问题；文献[3]提出了生产线平衡问题的多目标优化问题等。这些论文都是解决直线型生产线平衡的组合优化问题，但直线型生产线有明显的不足，文献[4]提出的U型生产线克服了直线型生产线的不足。但在某些情况下，直线型和U型生产线并不适合，本文提出将两条平行的生产线改成H型生产线的优化方法。许多文献提出遗传算法求解线平衡组合优化问题[1,2,5,6]，但作业元素顺序之间存在先后关系，在遗传变异时，不能保证变异后是可行解，这增加了算法实现的难度。在分析比较各种智能算法的基础上，鉴于TS（禁忌搜索算法）算法的特点，在邻域解产生候选解时，加入了先后关系矩阵，保证了候选解的可行性。通过设定合理的禁忌频率来自动平衡集中性和多样性搜索。最后应用MATLAB编程实现算法并利用Flexsim仿真验证。

1 H型生产线的提出

直线型生产线有分工细、员工熟练度高等优点，但过细的分工容易使工人产生心理疲劳并且工位间相隔较远，员工不易交流。Miltenburg和Wijngaard在文献[4]中提出的U型生产线很好的解决了上述缺点。U型生产线的工位之间相距较近，并且入口和出口在同一个位置，可以利用这个特点实现弹性作业人数（少人化技术）[6]。

但某些情况下，直线型和U型生产线并不适合。例如某些组装生产线，由于上游产量大，组装车间为了达到产量的需要，通常设计为平行的两条直线型生产线（如图1所示），但在线平衡率和人员利用率的双重压力下，这种设计显然是不合理的。直线型生产线有其固有的缺点，又由于有空间和产量的要求，U型生产线也不适合。针对这类情况，本文提出将两条平行的生产线改成H型生产线的优化方法。H型生产线即共用平行的两条生产线的某些工位（如图2所示），共用工位处，我们称之为结点。如在机器控制节拍，人员操作时间不足节拍的一半；某个工位随机性强，容易造成瓶颈，则在这个工位的下一道工位空闲的概率增大等这些情况可以成为结点。H型生产线的优点在于两条线之间的工位相距较近，便于交流互助；共用了某些工位，节约了人员；由于共用工位，可以更好的提高线平衡率。

图1 直线型生产线

图2 H型生产线

2 H型生产线平衡的数学模型及算法

2.1 模型假设

为了简化问题，做如下假设：

1）把作业划分为不能再分的作业元素，并且考虑了拿工具和配件的时间，用先后关系矩阵表示作业元素间的固有顺序。

2）确一个作业元素顺序，在满足作业顺序的前提下，一个作业元素可以被分配到任何一个工位。

3）确定了作业顺序之后，依次把作业元素分配到各个工位，并满足一个工位作业元素时间之和不超过给定的固定节拍，结点处节拍为整体节拍的一半。

2.2 模型的建立

记n为H型生产线业元素个数；m为工位个数；C 为生产线节拍；作业元素的集合为；ti为各个作业元素的时间；为作业元素的一个排列；Sk为第k个工位的作业元素集合，Sl第l 个结点的作业元素集合；η为生产线平衡率：

1）目标函数

2）约束条件

（1）在确定作业元素顺序时，要满足优先关系矩阵A ={aij}，A是只有-1,0,1,2四种元素的矩阵。aij=1表示作业元素Ti优先于作业元素Tj；aij=0表示作业元素Ti与Tj无优先关系；aij=-1表示作业元素Ti后与作业元素Tj；aii=2是矩阵对角元素的值，不参与判断先后关系。

（2）若Ti∈ Sk，Tj∈ Sh且Ti优先于Tj，则∀Ti∈ Sk优先于∀Tj∈ Sh。

（3）对于任何的Sk，,且若，则。

（4）对于任何的Sl，,且若，则。

2.3 模型的TS算法

TS（禁忌搜索算法）算法是美国科罗拉多大学（University of Colorado）的Glover教授提出的。禁忌搜索算法是对人的思维模式的一种模拟，其应用领域不仅涵盖了组合优化问题的各个方面，而且在函数优化方面也取得了成就。

本文在传统TS算法的基础上进行了如下改进：在邻域解产生候选解时，因有作业顺序的约束，加入了先后关系矩阵，保证了产生的候选解的可行性；通过设定合理的禁忌频率来自动平衡集中性和多样性搜索的矛盾，解决了局部最优解和全局最优解的矛盾。

3 实例验证

C公司是国内一家生产等离子显示器（PDP）的公司，该公司采用进口生产线，技术先进自动化程度高。但该公司屏车间下游平行的两条组装生产线，人员密集，线平衡率低，人员利用率低，造成了巨大的浪费。需要对此进行改善，以期提高线平衡率和人员利用率。

首先，利用秒表测时采集相关数据，对现行生产线进行Flexsim仿真，分析可能存在的问题。其次，应用上述数学模型对工位进行组合优化计算。最后，利用Flexsim仿真改善后的方案，进行前后对比。

表1 现行工位工时及人力

3.1 Flexsim对现行生产线仿真

C公司屏车间下游的两条平行的组装生产线，涉及到27个人，13个工位。通过秒表测时，得出现行的一条生产线工位工时及人力如表1、对现行组装线仿真如图3、各工位人员利用率如表2。

图3 现行组装生产线仿真

通过计算，现行组装线平衡率为68.90%，还有很大的改善空间。从数据中发现，工位平均利用率为54.68%。其中工位1的人员利用率为38.40%，其原因是2个人员为辅助作业，人员操作时间为10S，固定节拍为26S，所以工位1可以节约一个人力。工位2人员利用率为18.90%，操作为将屏搬上机器手，时间为5S，另外一个工作人员将屏搬运到工位附近暂存区。因此，我们把两条线的工位合并，即H型生产线的结点，节约人力2人。工位3和工位是没有人员，保持原样。对工位5到工位13进行作业元素划分，如表3。

表2 工位人员利用率

3.2 TS算法实现

TS算法具体参数设计描述如下：初始解为原始作业顺序；适配值函数为；邻域结构为对换，邻域大小为4*P_size（本文的P_size为48）；禁忌对象为解的状态，即作业元素的顺序；候选解的选择是结合先后关系矩阵（由于本文是48个作业元素，先后关系矩阵为48*48的矩阵），随机选择20个为候选集；禁忌长度为静态禁忌长度2*P-size；特赦准则为基于适配值得原则，当优于Best so far时，解禁禁止状态，当候选解全部被禁止时，选择适配值最好的状态解禁作为当前解；集中性和多样性矛盾处理为：当某个状态的禁忌频率达到2时候，以此状态初始化，重新搜索，当经过200步后，还没有出现禁忌频率为2状态时，重新初始化算法；终止准则为算法运行2000步。用MATLAB编程实现，解得作业顺序为：T=[1,2,13,3,5,6,4,14,15,7,8,9,10,12,11,29,16,17,20,18,19,21,22,25,23,24,28,26,27,31,32,34,35,33,37,36,41,42,44,43,40,38,39,45,46,47,48]，目标函数F=0.0911。作业顺序分配到工位之后如表4所示。

表4 作业元素分配到工位表

3.3 Flexsim对优化后组装线的仿真

对优化后的组装线进行Flexsim仿真分析（图4）。

图4 优化后组装线仿真

改善后的人员利用率及节拍如表5所示。

表5 人员利用率及节拍

3.4 优化效果分析

改善前人力为27，改善后的人力为19；改善前人员利用率40.06%，改善后人员利用率79.70%；改善前线平衡率为68.90%，改善后线平衡率93.76%。前后比较如图5～图7所示。

图5 人力

图6 人员利用率

图7 线平衡率

4 结论

针对某一类生产线，提出将平行的两条生产线改成H型生产线的优化方法并建立线平衡模型，用TS算法求解。通过对C公司现场调研，抽象出上述线平衡模型并求解之。再利用Flexsim对优化后的方案进行仿真，表明线平衡率和人员利用率都有所提高。但本文建立的数学模型没有考虑到H型生产线两条线中节拍和工位的不同，对模型稍加改进就可以应用于两条线中节拍和工位不同的情况。在TS算法设计中，将先后关系矩阵引进邻域解产生候选解阶段，虽然保证了解的可行性，但增加了算法的时间复杂性。在算法的集中性和多样性的平衡问题上用禁忌频率来自动调整，但是并没有给出不同情况下的不同禁忌频率。

[1]扈静,蒋增强,等.基于改进遗传算法的混合装配生产线平衡问题研究[J].合肥工业大学学报：自然科学版,2010,33(7)：1006-1009.

[2]兰月政,鲁建厦,等.基于遗传算法的混流生产线产品分组指派问题研究[J].浙江工业大学学报,2011,39(3)：312-316.

[3]宋华明,韩玉启.多目标装配线平衡的优化算法[J].运筹与管理,2002,11(3)：55-62.

[4]Miltenburg G J,Wijngaard J.The U-line balancing problem[J].Management Science,1994,40(10)：1378-1388.

[5]宋华明,韩玉启.基于遗传算法的U型生产线平衡[J].系统工程学报,2002,17(5)：424-429.

[6]Moden Y.Toyota Production Systems[M].Norcross：Industrial Engineering and Management Press,Institute of Industrial Engineers,1993,159-179.