基于启发式算法与仿真分析的混合流水线平衡优化

本资料包含pdf文件1个，下载需要1积分

混合流水线是指在不降低流水线效率的前提下，在-条流水线上实现具有相似特征的多个产品或者是-个产品系列的不同品种 的混合生产 ，与单- 产品流水线相 比，能够在保持较低库存水平的情况下更加柔性 的应对顾客个性化 和多样化 的需求 。

混合流水线平衡是混合流水线优化设计 的重要问题之-。这是因为混合流水线平衡有利于：(1)消除生产瓶颈，减少架线成本，提高生产效率。(2)提升员工士气，稳定产品质量。(3)加快物流周转，缩短生产周期，减少或消除物料及半成品周转场所。

混合产品流水线平衡远比单-产品流水线平衡复杂，现有研究多采用遗传算法、蚁群算法、粒子群算法等智能算法进行求解。张则强等提 出了-种带信息素总合规则和混合搜索机制的蚁群算法进行求解。徐炜达和肖田元 研究了带有跨工位操作，且作业完成时间为随机量的混合装配线平衡问题，结合随机模拟和遗传算法设计了混合遗传算法进行求解。Reakook Huang和 Hiroshi Katayama 设计 了两阶段遗传算法求解多目标 u型混合流水线平衡问题。凌文曙 利用遗传算法解决了某车桥混合装配线平衡问题。但是，智能算法计算复杂，耗时较长，基于规则的启发式算法计算简单快捷 ，容易为生产实践者理解和掌握 ，在单-产品流水线平衡实际应用较多，但对混合流水线平衡优化精度不高，特别是对不同产品在每个工作站的作业时间均衡效果不佳。因此，本文提出-种将启发式算法和仿真分析相结合的方法，首先将多产品的作业优先次序图转化为单-产品综合作业优先次序图，然后利用基于规则的启发式算法求得初始平衡方案，接着根据混合流水线运行特点建立仿真模型，通过仿真分析，辨识存在的问题并进行改进，从而得到最终优化平衡方案。

1 混合流水线平衡问题的描述根据流水线上加工产品品种的多少，流水线平衡问题可分为单-产品、多产品和混合产品流水线平衡问题。其中，单-产品流水线上只生产-种产收稿日期：2012-06-21；修回日期：2012-O7-l3十基金项目：国家自然科学基金资助项目(71071059)；三峡大学人才科研基金(KJ2011B03)；教育部博士点基金项目(20100172120040)；中央高衅研业务费作者简介：查靓(1978-)，女，湖北松滋人，三峡大学机械与材料学院讲师，博士，主要研究方向为工业工程等，(E-mail)maria-zhajing###hot-mail.com。

2013年 2月 查 靓，等：基于启发式算法与仿真分析的混合流水线平衡优化 ·15·品，多产品流水线上以-定的批量轮番进行多种产品的生产，例如生产 100个产品A后再生产 100个产品 ，混合品种流水线上是以-个最小比例集轮番进行多种产品的混合生产，例如以(A，B)为最小比例集重复生产 100次。

混合流水线平衡问题是指 ：给定加工 多个产品的作业优先次序图，包括作业集合、作业加工时间以及作业间的优先次序关系等信息，将作业组合分配到工作站，要求每个作业都被分派且只能被分派到- 个工作站，每个工作站的作业时间不大于节拍，满足作业间的优先次序要求，并使得某些指标达到优化。

2 混合流水线平衡问题向单-产品流水线平衡问题转化混合流水线 由于需要 完成多个 产品的加工 ，因此对应了多个产品的作业优先次序图，为了能利用单-产品流水线平衡方法来求解，第-步应该是如何将多个作业优先次序转化为-个作业优先次序图。

令第P个产品的作业优先次序图用有向图 ( ，P ，t )表示。则 PN种产品的综合作业优先次序图为 e( ，P，f)。其中：：T.LJ T2 u Te I i：1，2，nP ： Pl U P2 U PPⅣ： (i， )l 必须在 完工后才能开始由于 。 ，因此定义 6 表示 中是否包括作业 i(i∈ )，如果包括 艿。 1，否则 艿。 0。计划期 内第P个产品的需求数量为d总产品数为a，则计算出每个作业元素的加权平均作业时间为：PⅣf (∑d )/aP13 启发式算法在-个有向网络图中，从起点开始，按照作业顺序 ，连续不断地 到达终点 的- 条通路称为-条 网络路线。其中，完成每-作业需要时间最长的路线称为关键路线 ，关键路径上 的作业 的松弛时间为 0，松 弛时间 作业最迟开始时间 -作业最早开始时间 -作业时间。正因为关 键路径决定 了完成 所有作业需要的最长作业时间，因此旧能早的开始执行关键路径上的作业越有利于减少所需要的总工作站数。关键路径可以利用运筹学中的网络前向分析和后向分析，然后根据松弛时间为0计算得到 。

双向启发式算法的特点是 ，同时从第-个工作站和最后-个工作站开始，从前向后和从后向前同时试分配可行的候选作业到前向工作站和后向工作站，在分配过程中优先分配关键路径上的作业，如果试分配的前 向工作站的空闲时间小于试分配 的后向工作站的空闲时间，说明前向工作站的试分配方案优于后向的，接受前向工作站试分配方案，放弃后向的，否则接受后向工作站试分配方案，放弃前向的∮着进行下-工作站的试分配，直到所有作业均被分配到工作站。

计算步骤如下：第-步：计算关键路径作业集合 5 非关键路径作业集合S。S-S第二步：初始化 。所有作业均未分 配到工作站 JsS，S ，同时从第-个工作站和最后-个工作站开始分配作业 ，因此令首工作站为当前前向工作站，末工作站为当前后向工作站，即i1，1。

第三步：创建两个临时前向工作站和后向工作站作业集合，初始为空，FS BSi 。

第四步：试分配。筛焉行的候选作业集合，即未分配的，且不存在未分配的前序作业可分配到当前前向工作站 i，如果候选作业集合中存在关键路径上的作业，首先分配到临时前向工作站 FS ，然后按照最长作业时间等规则依序分配候选作业集合里的作业直到 FS，的总作业时间超过节拍 C为止。同理 ，如果存在未分配的且不存在未分配的后序作业可分配到当前后向工作站 ，如果候选作业集合中存在关键路径上的作业，首先分配到临时后向工作站 BSi，然后按照最长作业时间等规则依序分配候选作业集合里的作业直到BSj的总作业时间超过节拍 c为止。

第五步：确定分配方案。对于临时工作站集合FS 和 BJs，，如果 Fs 的空闲时间小于BS 的空闲时间 ，即 ≤Wb，说明当前前向工作站 i的临时分配方案优于后 向工作站 .，的 ，因此接受 FS 的分配方案成为固定分配方案 ，放弃 BSi，即 i1，S。S u FS ，S。S -FS ，FS 日Js 。如果 wf> ，说明后向工作站. 的临时分配方案优于前向工作站 i的，接受BSi的分配方案成为固定分配方案，放弃FS ，即 J1，S S。 u BS ，S。S -BSj，FS S 咖。

第六步：如果 S 说明所有作业都已分配到工作站，程序结束，输出分配方案，否则，返回第四步继续执行。

I 计算关键路径作业 l初始化 I创建新的临时工作站 l试分配临时工作站(优先分配关键路径上的作业 )固定工作站分配方案鼢 ，- N图 1 启发式算法的计算流程图· 16· 组合机床与 自动化加工技术 第 2期4 评价指标4.1 单-产品流水线平衡指标单-产品流水线平衡效果常采用生产线平衡效率P作为评价指标，如下式：∑P 100% (1)其中m代表工作站数， 代表工作站i的平均作业时间，c为节拍。P值越大说明平衡性越好，生产效率越高。对于P值，文献[8]给出了推荐的评定标准，如表1所示。

表 1 单-产品流水线平衡性评价标准平衡效率结果 评价结果P≥90% 优80% ≤p<90% 良D<80% 差4.2 混合流水线平衡指标由于混合流水线上加工的是多个产品，在-个周期 的不同阶段每个工作站实际加工的产品会发生变化，每个工作站的实际作业时间也随之发生变化，尽管按照启发式方法得到的初始方法平衡效率P值高，但不同阶段的工作站实际作业时间仍存在不平衡现象 ，甚至出现超过节拍的现象。

通常采用两种方法解决 ：-是调整生产节拍 c，使流水线节拍大于或等于最长工作站作业时间，这种方式降低了生产速度，无法满足客户需求；二是保持节拍 C不变，采取补救措施(如设置线外工作站修补)完成，采取这种方式时，每个工作站作业时间超过节拍的程度也称超负荷量对生产效率影响大 ，总的超负荷量越大，线外补救的工作就越多，需要的赶工成本越大。此外，工作站负荷不均衡，有的工作站作业时间很长，有的工作站作业时间很短 ，也会对产品质量和员工士气产生很大影响。

因此 ，最长作业时间、总的超负荷量 以及负荷均衡指数对于混合流水线的最优化设计至关重要，本文选择这三个指标作为混合流水线平衡效果的评价指标 。

CH∑∑pos( -c) (2)女口果 0≥0贝0 pos(o)0；否贝0 pos(Ⅱ)0。

r -- -------- /∑∑(f -c)S 上 ---- (3)m x利用平均作业时间和启发式算法得到的初始平衡方案无法保证这三个指标的最优性，因此需要根据混合流水线特点建立仿真模型，进而提出改善方案 。

5 案例应用5.1 案例背景介绍某客车空调生产企业原先客户少 ，生产品种数少，随着技术能力的增强，为扩大利润，开发了-些新的客户，针对客户需求研发了几个系列的新产品，这些新产品利润高，品种多，但单-品种客户需求数量少 ，为了节受线成本和运行成本 ，受精益生产思想的影响，公司拟针对系列产 品采用混合装配流水线进行生产，因此需要设计-条新的混合流水线。

选定 A(内置式)、曰(全顶置式 )、C(半顶置式 )三种产品，根据市场调研与预测，每个月三种产品的需求分别为200、200和400台，该企业每周工作6天(-个月26个工作日)，每 日工作 8小时，需求节拍G 为：计戈U期 268 60 计划期内需求数量 -200200400 15.6(分钟)根据需求节拍 CT的值 ，考虑-定 的宽放系数混合流水线的生产节拍设计为 l5分钟。

5.2 综合作业优先次序图三种产品的作业优先次序图如图2、3、4所示。其中，作业间的优先次序是根据产品装配工艺 的要求绘制的，每个作业 的作业时间是根据模特法 ，并考虑- 定的评 比系数 和宽放系数后 预订 的标准作 业时间。

图 2 产品 A的作业优先次序图6图 3 产品 B的作业优先次序 图7 2图4 产品C的作业优先次序图根据每个月三种产品的需求得到综合产品作业优先次序图如图5所示。

2013年 2月 查 靓 ，等 ：基于启发式算法与仿真分析的混合流水线平衡优化 ·17·图 5 综合作业优先次序 图5.3 求解单-产品流水线平衡 问题按照基 于关键路径的双 向启发式算法 ，首先计算关键路径作业集合为 S 1，3，6，7，8，10，l2，l4，15，然后按照图1所示的流程将作业分配到工作站 的分配过程如下表 2所示。得到的作业分配方案如表 3所示 。平衡有效性指标-6 7.5 100% 90%根据表1的评价标准，P≥90%可以认定该单-产品流水线平衡方案是优 的。

表 2 作 业分 配过程创建临时 迭代 试分配临时工作站 固定工作站工作 站FS 1，2，3 1 1.51 FSBSlBS112，14，15， FSl1，2，3FS24，5，6 ，：2 W61.52 FS2 BS1BS 12，14，15， BS1 12，14，15fFS24，5，6 r 623 FS2 BS2BS210，11，l3 FS24，5，6FS3 7，8，9 r1 W624 FS3 BS2BS210，11，13 FS37，8，9FS4 BS2 r 6 25 FS4 BS2： 10，11，13 FS4BS2 10，11，13表 3 初始作业分配方案T作 站号 站 1 站 2 站 3 站 4 站 5作业分配 1，2，3 4，5，6 7，8，9 10，11，13 12，14，155.4 仿真分析- 个月内三种产品的需求为200、200和 400，需求 比例为 1：1：2，为 了确保零件消耗 的均衡性 ，采用比例倒数法确定在-个循环 内三种产 品投放 的顺序为 CBAC，据此建立仿真模型。仿真结果表 明，在-个周期的四个阶段 内五个工作站中出现的产 品及工作站作业时间如表 4所示，工作站实际负荷如图6所示 。

表4 改善前-个周期内工作站加工产品及作业时间站 1 站 2 站 3 站 4 站 5阶段 1 C(11) C(15) A(13) B(7) C(8)阶段 2 f15) c(15) C(14) A(9) (20)阶段 3 A(19) B(13) C(14) C(18) A(2O)阶段 4 C(11) A(9) B(15) C(18) C(8)4图 6 改善前工作站 负荷最长工作站作业时间为 20，远超过节拍 l5的要求。工作站 1在第 3阶段，工作站4在第 3、4阶段，工作站 5在第 2、3阶段，作业时间较长，成为瓶颈工作站，超出节拍，而工作站4在第-阶段的作业时间只有 7，工作站5在第 4阶段的作业时间只有 8，远小于节拍，存在空闲时问。总的超负荷量为 4000，负荷均衡指数为 0.95。

由此可 以看 出，虽然初始方案针对 以加权平均作业时间为参数的单-产品流水线而言平衡效率为优，但考虑了每个产品实际的作业时间后的混合流水线上，由于排序方案的不同使得每个工作站出现的产品不同，使得工作站作业时间不同，从而出现不平衡现象，甚至超出节拍需求，在有些时间段内个别工作站无法完成作业 ，需 要在 工作站 上增加额外的活动工人来完成超出的负荷，才能使流水线正常运行。因此有必要寻求更好的平衡方案较少超负荷量水平 ，从而减少线外工作站 的修补工作量 ，提高生产效率 ，提高质量 。

5.5 优化方案工作站 1对 A的作业时间为 19分钟 ，超负荷明显 ，而工作站2中对A产品没有超负荷现象，所以考虑对工作站 1进行拆分，与工作站 2中作业进行重新分配；工作站4与工作站 5的超负荷现象更加明显 ，c产品在工作站4中作业时间超过节拍 ，而在工作站 5的作业时间只有8分钟，远小于节拍 ；A、B产品在工作站 5中作业时间超过节拍，而在工作站 4的作业 时间 较小 ，所 以考虑 对 工作 站 4、5进行 拆分 ，对其 中的作业重新 分配 。改进后 的平衡方 案如表 5所示 。

表 5 改善后工作站作业分派方案工作站号 站 1 站2 站3 站4 站5作业分配 1，3，5 2，4，6 7，8，9 10，11，12 13，14，15针对改进的平衡方案，加入排序方案后，产品以投入顺序 CBAC循环进入生产线，重新构建仿真模型，仿真结果表明在-个周期的四个阶段内五个工作站中出现的产品及工作站作业时间如表6所示，工作站实际负荷如图 7所示。

4 -· l8· 组合机床与自动化加工技术 第 2期表 6 改善后-个周 期内工作 站加 工产 品及 作业时间站 1 站 2 站 3 站 4 站 5阶段 1 C(14) C(I2) A(13) B(15) C(15)阶段 2 B(14) C(12) C(14) A(15) B(12)阶段 3 A(14) B(14) C(14) C(10) A(14)阶段 4 C(14) A(14) B(15) C(10) c(15)图 7 改 善 后 工 作 站 负 荷 图改善后最长工作站作业时间为 15，满足节拍 l5的要求，不存在工作站作业时间超过节拍的情况，CH：0，负荷均衡指数为 0.47，大大小于初始方案 ，改进后的平衡效果优。

6 结束语混合流水线的平衡过程是实现劳动生产率、设备利用率和满足市场需求三者之间平衡的过程，混合流水线平衡效果直接影响到流水线的生产效率。

本文针对混合流水线设计与运行的特点，采用启发式算法和仿真分析相结合的方法求解混合流水线平衡问题，通过对某客车空调生产企业三种产品混流生产线的设计发现，经过平衡优化后，能够减少最长工作站作业时间，避免工作站实际负荷超节拍的情况，大大减少工作站间负荷不均衡，达到提高生产效率，降低生产成本，提升员工士气，稳定产品质量等目的。