离散型生产流水线中缓冲区分配问题的研究

巫江 杨伟琦 王东

【摘  要】论文研究了离散型生产流水线中缓冲区的分配问题。论文建立了一个将生产流水线分解为S-B-S（工作站-缓冲区-工作站）子系统的模型，利用排队理论对各子系统进行聚合，对平衡生产流水线和不平衡生产流水线进行了实验设计，并结合计算结果，提出了缓冲区分配问题的一般结论和规则。

【Abstract】This paper studies the buffer allocation problem in discrete production line. The paper establishes a model that decomposes the production line into S-B-S （workstation-buffer-workstation） subsystems， uses queuing theory to aggregate the various subsystems， and conducts experimental design on balanced production line and unbalanced production line. Combined with the calculation results， this paper puts forward the general conclusions and rules of buffer allocation problem.

【关键词】离散型生产流水线;缓冲区;排队论;模拟退火法

【Keywords】discrete production line; buffer; queuing theory; simulate anneal arithmetic

【中图分类号】F273                                             【文献标志码】A                                                 【文章编号】1673-1069（2021）11-0115-04

1 引言

在生產型工厂中，生产流水线经常会出现波动情况，这就需要在各工位之间设置缓冲区间，否则生产流水线经常会出现“堵塞”和“饥饿”的问题。本文研究了相邻工位之间有一定间隔的串行生产流水线，这些生产流水线的一些内部区域可以用作缓冲区空间。如果给定了生产流水线的总长度，那么缓冲区的总大小也随之确定。缓冲区空间的分配是生产流水线设计中的一个重要问题，晏磊等[1]指出缓冲区的位置和缓冲区的大小都是优化生产流水线的重要因素。

大多数文献将缓冲区定位问题建模为离散马尔科夫过程，并使用排队理论来解决问题，如尹慧超[2]和罗非非[3]等人对这种方法进行了详细的回顾。然而，应用排队理论很难得到精确的解决方案，尤其是当问题规模越来越大时，该方法的应用受到了限制。因此，大量文献采用启发式和元启发式方法来得到合理的近似结果[4]。一些文献将问题近似为一个连续的马尔科夫过程，如王彪等[5]的相关研究。连续模型极大地减少了可能的状态空间，并实现了与梯度相关的近似方法。

基于此，大多数的研究都只在连续生产流水线上研究分配问题。本文提出了一个模型，这个模型适用于并行和串行同时存在的复杂环境。与此同时，与本文研究相关的研究只考虑了吞吐量最大化的目标，很少考虑不同布局的成本。这样做的部分原因是，在串行生产流水线中，不同布局的成本通常是相同的，但在既有串行线又有平行线的复杂生产流水线中却不尽相同。此外，现有文献对生产流水线空间限制和工件在缓冲器中的行程时间考虑较少。由于额外的缓冲空间增加了工件的行程时间，所以额外的缓冲空间的额外生产率降低。本文的模型综合考虑了人工成本、机器成本、工件行程时间等因素，所以可以提供更合理、更实用的解决方案。

2 问题描述

本文针对性地研究了离散型生产流水线，生产流水线中共有k个工作站，Wp1，Wp2，…，Wpk个加工工件的工作站。工作站之间是缓冲区，本文分别表示为B1，B2，B3，…，Bk。图1是复杂生产流水线的一个实例。本文假设平行线中的所有线都有相同的结构。Wpi为第i个工作站，假设Wpi处于有Pli个平行线的阶段。

当工作站数量大于2个时，本文采用分解的方法，进而研究S-B-S（Station-Buffer-Station）子系统的基本单元，如图2所示。本文将第i个子系统定义为Si，并使用2个人工工作站：Ai和Di模拟生产流水线的上游（Wp1到Wpi-1）和下游（Wpi到Wpk）这2个区域对缓冲区Bi的影响。将Si的容量定义为Bi的大小和Di的大小的总和，并将其表示为Ti。工作站的宽度是Wpw，缓冲区的宽度是WB。工作站的长度为LW，缓冲器的宽度为LB。工作站与缓冲器的距离为LM，平行线中相邻直线的距离为WM。可用工作空间限于长度为L、宽度为W的正方形，布局不应超过可用工作空间，并假设Wpi工作站需要Pi名工人，总可用工人数为E。工人人数不应超过可用人数，一个工人的成本是PW。一台机器的成本是PM，它结合了机器的折现价值和电气、维修等运营成本。

每个工件从Wp1进入生产流水线，依次经过工位和缓冲区，最后从Wpk离开生产流水线。受生产加工时间波动的影响，过程中可能会出现“阻塞”或“饥饿”的情况。

“阻塞”定义为：如果任何Ai完成了工作，而Bi-1没有可用的工作块，那么称Si是“阻塞的”;如果任何Di完成了它的工作并且Bi+1是满的，那么称Si是“阻塞的”。

“饥饿”定义为：如果任何Bi-1拥有了可用的工作块，而Ai还没有完成工作，那么称Si是“饥饿的”。

3 研究方法：模拟退火法

本文采用模拟退火法来解决这个问题。模拟退火的核心思想与结晶和金属冷却退火的热力学原理非常相似：大量的液体分子在高温下可以自由移动，但随着温度的降低，流动性会降低。原子成行排列，形成纯净的晶体，这是能量最小的状态。然而，如果很快地降低温度，液态金属就被称为“淬火”，并将停止在高能量的多晶状态或无定形状态。因此，获得完美晶体的本质是缓慢地降低温度，让原子在失去流动性之前重新分配它们的位置。这个过程在技术上称为退火。

模拟退火法是一种求解大规模全局优化问题的元启发式方法，特别是在存在许多局部最优点且搜索空间很大的情况下。在本文的问题中，本文目标不是k个变量的简单组合。搜索空间如此之大，几乎不可能列举出所有可能的解决方案。因此，在本文的问题中，本文采用模拟退火的算法。

根据退火原理，将固体加热到足够高的温度，然后慢慢冷却下来。当加热时，固体颗粒的位置变得无序，具有很高的内能。当缓慢冷却时，它们是有序的，最终以最小的内能达到平衡。Metropolis准则用数学的形式描述了这个过程，即粒子达到平衡状态的概率为e-δE/ （kT ），在温度T下，其中E是热力学能，k是玻尔兹曼常数。当本文用模拟退火法求解组合优化问题时，用目标函数值X代替内能E，用控制参数t代替温度T，从一个初始解开始，本文“生成一个新的解，计算客观差值，接受或拒绝”迭代，逐渐衰减t值。当算法终止时，本文得到了优化问题的近似解。退火过程由冷却过程表控制，冷却过程表包括控制参数t、每个δt的衰减因子、迭代次数L和停止条件S。解的生成过程为：①从现有的解决方案中生成新的可行的解决方案。为了便于计算，通过简单的变换，如边交换法和节点交换法来生成新的解。②计算目标值与旧值的差值。③确定新的解决方案是否被接受。最常用的准则是Metropolis准则：如果本文接受新的解并用它来代替旧的解S，或者本文只接受一个概率的解S'。④如果新的解决方案被接受或拒绝，迭代便就此完成。

4 结果分析

与Soares等人的研究（1988）[6]相似，本文设计了平衡和不平衡生产流水线2种情况下的实验。目标是使产量最大化。生产流水线处于“推挤”状态，即第一个工位永远不会“挨饿”，最后一个工位永远不会“堵塞”，并用MATLAB对模型和算法进行了编码。为简化问题，本文假设工作站和缓冲器的大小相同，而工作站的长度等于相邻缓冲器和工作站的距离，宽度等于相邻平行线的距离。即LW=LB=LM和WPW=WB=WM。

4.1 平衡生产流水线

假设所有工位的加工速度为单位时间一个工件。本文研究了串行线中分别有5个工作站和10个工作站的情况。宽度限制为5wm。图3展示了生产流水线与总长度的最大目标。很明显，缓冲区空间的优势随着总长度的增加而减少。Hatcher（1969）[7]表明，在大多数情况下，10个缓冲区空间对于生产流水线是足够的。本文的研究表明，总共设计10个缓冲区并不总是一个不错的选择。从图3可以看出，当有5个工作站时，有10个缓冲空间的生产流水线的吞吐量可以达到理想吞吐量的60%（无波动时），而当有10个工作站时，达到理想吞吐量的40%。本文建议设计师在作出决定之前先计算不同的方案，以及增加生产流水线长度的成本。

表1和表2列出了缓冲区分配结果。其中，数据Ti为Si子系统的容量大小。数据Pli为平行线数目。规定每个数据的中间数据为中间区域范围，表1数据Ti的中间区域范围为T2与T3、表2数据Ti的中间区域范围为T5;表1数据Pli的中间区域范围为Pl3、表2数据Pli的中间区域范围为Pl5与Pl6。

正如本文所计算得到的表格所展现的数字，Ti与Pli的计算结果均呈现低-高-低的正态分布状态，如15缓冲区间上的Ti为3、5、4、3，Pli则为1、1、1、1、1;16缓冲区间上的Ti为3、5、5、3，Pli则为1、1、1、1、1……24缓冲区间上的Ti为5、7、7、5，Pli则为2、2、3、2、2。数据的计算结果均为先升后减。

因此，在大多数情况下，最优分配是对称的。

4.2 不平衡生产流水线

不平衡的生产流水线比平衡的生产流水线复杂得多。本文研究了2个例子。第一个例子有5个工位，每个工位单位时间的加工速度分别为4、7、10、7、4个工件。第二个例子有10个工位，每个工位单位时间的加工速度分别为8、4、7、5、

10、7、7、4、7、5个工件。生产流水线的最大吞吐量与总缓冲区大小的对比如图4所示。由此可以看到，曲线与图3非常相似，这表明在平衡线和不平衡线中，总缓冲区大小对吞吐量的影响是相似的。

表3和表4列出了缓冲区分配结果。Bulgak等人（1995）[8]表明缓冲区大小与拥塞可能性呈正相关。本文的研究表明，當本文考虑复杂的生产流水线时，情况更加复杂，最优的缓冲区分配方案往往采取非常不规则的形式。与上面相关结论形成截然对比的是，数据Ti的分布区域不再呈现正态分布，而是从前到后逐步递减，而数据Pli的计算结果分布趋势仍与之相同。

5 结语

本文通过利用排队理论对各子系统进行聚合，结合对平衡生产流水线和不平衡生产流水线进行实验设计，并加以使用模拟退火的智能算法思想得出2个相关结论：在平衡生产流水线中，在大多数情况下，最优分配是对称的，并在中间区域范围内多分配一些;在非平衡生产流水线中，情况更加复杂，最优的缓冲区分配方案往往采取非常不规则的形式。本文结论通过科学合理步骤得出，具有较高的信效度，可为多数企业的离散型生产流水线提供借鉴。

【参考文献】

【1】晏磊，高萍，黄蓉蓉.关于运筹学理论及其在生活中的实际应用研究[J].佳木斯职业学院学报，2021，37（4）：48-49.

【2】尹慧超，徐维.基于遗传算法的串行生产线性能优化[J].华北科技学院学报，2019，16（5）：79-85.

【3】罗非非，郭永江.基于累积前景理论的M/M/1排队模型[J].哈尔滨商业大学学报（自然科学版），2021，37（4）：475-482.

【4】谭岐钰，张红波，高贵兵.基于人员调度优化的混流生产线平衡改善[J].湖南科技大学学报（自然科学版），2021，36（2）：52-59.

【5】王彪，高天祥，孙林雨.多模式连续铸轧生产线高速飞剪的应用研究与优化[J/OL].冶金自动化：1-13[2021-10-13].http：//kns.cnki.net/kcms/detail/11.2067.TF.20210820.1622.002.html.

【6】Ana da Silva Soares，Guy Latouche.Matrix-analytic methods for fluid queues with finite buffers[J].Performance Evaluation，2005，63（4）：295-314.

【7】Jerome M. Hatcher.The Effect of Internal Storage on the Production Rate of a Series of Stages Having Exponential Service Times[J].IIE Transactions，1969，1（2）：150-156.

【8】A.A. Bulgak，P.D. Diwan，B. Inozu.Buffer size optimization in asynchronous assembly systems using genetic algorithms[J].Computers & Industrial Engineering，1995，28（2）：309-322.