離散型生產(chǎn)流水線中緩沖區(qū)分配問題的研究

巫江 楊偉琦 王東

【摘? 要】論文研究了離散型生產(chǎn)流水線中緩沖區(qū)的分配問題。論文建立了一個將生產(chǎn)流水線分解為S-B-S（工作站-緩沖區(qū)-工作站）子系統(tǒng)的模型，利用排隊理論對各子系統(tǒng)進行聚合，對平衡生產(chǎn)流水線和不平衡生產(chǎn)流水線進行了實驗設(shè)計，并結(jié)合計算結(jié)果，提出了緩沖區(qū)分配問題的一般結(jié)論和規(guī)則。

【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.

【關(guān)鍵詞】離散型生產(chǎn)流水線;緩沖區(qū);排隊論;模擬退火法

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

【中圖分類號】F273? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻標志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號】1673-1069（2021）11-0115-04

1 引言

在生產(chǎn)型工廠中，生產(chǎn)流水線經(jīng)常會出現(xiàn)波動情況，這就需要在各工位之間設(shè)置緩沖區(qū)間，否則生產(chǎn)流水線經(jīng)常會出現(xiàn)“堵塞”和“饑餓”的問題。本文研究了相鄰工位之間有一定間隔的串行生產(chǎn)流水線，這些生產(chǎn)流水線的一些內(nèi)部區(qū)域可以用作緩沖區(qū)空間。如果給定了生產(chǎn)流水線的總長度，那么緩沖區(qū)的總大小也隨之確定。緩沖區(qū)空間的分配是生產(chǎn)流水線設(shè)計中的一個重要問題，晏磊等[1]指出緩沖區(qū)的位置和緩沖區(qū)的大小都是優(yōu)化生產(chǎn)流水線的重要因素。

大多數(shù)文獻將緩沖區(qū)定位問題建模為離散馬爾科夫過程，并使用排隊理論來解決問題，如尹慧超[2]和羅非非[3]等人對這種方法進行了詳細的回顧。然而，應(yīng)用排隊理論很難得到精確的解決方案，尤其是當問題規(guī)模越來越大時，該方法的應(yīng)用受到了限制。因此，大量文獻采用啟發(fā)式和元啟發(fā)式方法來得到合理的近似結(jié)果[4]。一些文獻將問題近似為一個連續(xù)的馬爾科夫過程，如王彪等[5]的相關(guān)研究。連續(xù)模型極大地減少了可能的狀態(tài)空間，并實現(xiàn)了與梯度相關(guān)的近似方法。

基于此，大多數(shù)的研究都只在連續(xù)生產(chǎn)流水線上研究分配問題。本文提出了一個模型，這個模型適用于并行和串行同時存在的復雜環(huán)境。與此同時，與本文研究相關(guān)的研究只考慮了吞吐量最大化的目標，很少考慮不同布局的成本。這樣做的部分原因是，在串行生產(chǎn)流水線中，不同布局的成本通常是相同的，但在既有串行線又有平行線的復雜生產(chǎn)流水線中卻不盡相同。此外，現(xiàn)有文獻對生產(chǎn)流水線空間限制和工件在緩沖器中的行程時間考慮較少。由于額外的緩沖空間增加了工件的行程時間，所以額外的緩沖空間的額外生產(chǎn)率降低。本文的模型綜合考慮了人工成本、機器成本、工件行程時間等因素，所以可以提供更合理、更實用的解決方案。

2 問題描述

本文針對性地研究了離散型生產(chǎn)流水線，生產(chǎn)流水線中共有k個工作站，Wp1，Wp2，…，Wpk個加工工件的工作站。工作站之間是緩沖區(qū)，本文分別表示為B1，B2，B3，…，Bk。圖1是復雜生產(chǎn)流水線的一個實例。本文假設(shè)平行線中的所有線都有相同的結(jié)構(gòu)。Wpi為第i個工作站，假設(shè)Wpi處于有Pli個平行線的階段。

當工作站數(shù)量大于2個時，本文采用分解的方法，進而研究S-B-S（Station-Buffer-Station）子系統(tǒng)的基本單元，如圖2所示。本文將第i個子系統(tǒng)定義為Si，并使用2個人工工作站：Ai和Di模擬生產(chǎn)流水線的上游（Wp1到Wpi-1）和下游（Wpi到Wpk）這2個區(qū)域?qū)彌_區(qū)Bi的影響。將Si的容量定義為Bi的大小和Di的大小的總和，并將其表示為Ti。工作站的寬度是Wpw，緩沖區(qū)的寬度是WB。工作站的長度為LW，緩沖器的寬度為LB。工作站與緩沖器的距離為LM，平行線中相鄰直線的距離為WM。可用工作空間限于長度為L、寬度為W的正方形，布局不應(yīng)超過可用工作空間，并假設(shè)Wpi工作站需要Pi名工人，總可用工人數(shù)為E。工人人數(shù)不應(yīng)超過可用人數(shù)，一個工人的成本是PW。一臺機器的成本是PM，它結(jié)合了機器的折現(xiàn)價值和電氣、維修等運營成本。

每個工件從Wp1進入生產(chǎn)流水線，依次經(jīng)過工位和緩沖區(qū)，最后從Wpk離開生產(chǎn)流水線。受生產(chǎn)加工時間波動的影響，過程中可能會出現(xiàn)“阻塞”或“饑餓”的情況。

“阻塞”定義為：如果任何Ai完成了工作，而Bi-1沒有可用的工作塊，那么稱Si是“阻塞的”;如果任何Di完成了它的工作并且Bi+1是滿的，那么稱Si是“阻塞的”。

“饑餓”定義為：如果任何Bi-1擁有了可用的工作塊，而Ai還沒有完成工作，那么稱Si是“饑餓的”。

3 研究方法：模擬退火法

本文采用模擬退火法來解決這個問題。模擬退火的核心思想與結(jié)晶和金屬冷卻退火的熱力學原理非常相似：大量的液體分子在高溫下可以自由移動，但隨著溫度的降低，流動性會降低。原子成行排列，形成純凈的晶體，這是能量最小的狀態(tài)。然而，如果很快地降低溫度，液態(tài)金屬就被稱為“淬火”，并將停止在高能量的多晶狀態(tài)或無定形狀態(tài)。因此，獲得完美晶體的本質(zhì)是緩慢地降低溫度，讓原子在失去流動性之前重新分配它們的位置。這個過程在技術(shù)上稱為退火。

模擬退火法是一種求解大規(guī)模全局優(yōu)化問題的元啟發(fā)式方法，特別是在存在許多局部最優(yōu)點且搜索空間很大的情況下。在本文的問題中，本文目標不是k個變量的簡單組合。搜索空間如此之大，幾乎不可能列舉出所有可能的解決方案。因此，在本文的問題中，本文采用模擬退火的算法。

根據(jù)退火原理，將固體加熱到足夠高的溫度，然后慢慢冷卻下來。當加熱時，固體顆粒的位置變得無序，具有很高的內(nèi)能。當緩慢冷卻時，它們是有序的，最終以最小的內(nèi)能達到平衡。Metropolis準則用數(shù)學的形式描述了這個過程，即粒子達到平衡狀態(tài)的概率為e-δE/ （kT ），在溫度T下，其中E是熱力學能，k是玻爾茲曼常數(shù)。當本文用模擬退火法求解組合優(yōu)化問題時，用目標函數(shù)值X代替內(nèi)能E，用控制參數(shù)t代替溫度T，從一個初始解開始，本文“生成一個新的解，計算客觀差值，接受或拒絕”迭代，逐漸衰減t值。當算法終止時，本文得到了優(yōu)化問題的近似解。退火過程由冷卻過程表控制，冷卻過程表包括控制參數(shù)t、每個δt的衰減因子、迭代次數(shù)L和停止條件S。解的生成過程為：①從現(xiàn)有的解決方案中生成新的可行的解決方案。為了便于計算，通過簡單的變換，如邊交換法和節(jié)點交換法來生成新的解。②計算目標值與舊值的差值。③確定新的解決方案是否被接受。最常用的準則是Metropolis準則：如果本文接受新的解并用它來代替舊的解S，或者本文只接受一個概率的解S'。④如果新的解決方案被接受或拒絕，迭代便就此完成。

4 結(jié)果分析

與Soares等人的研究（1988）[6]相似，本文設(shè)計了平衡和不平衡生產(chǎn)流水線2種情況下的實驗。目標是使產(chǎn)量最大化。生產(chǎn)流水線處于“推擠”狀態(tài)，即第一個工位永遠不會“挨餓”，最后一個工位永遠不會“堵塞”，并用MATLAB對模型和算法進行了編碼。為簡化問題，本文假設(shè)工作站和緩沖器的大小相同，而工作站的長度等于相鄰緩沖器和工作站的距離，寬度等于相鄰平行線的距離。即LW=LB=LM和WPW=WB=WM。

4.1 平衡生產(chǎn)流水線

假設(shè)所有工位的加工速度為單位時間一個工件。本文研究了串行線中分別有5個工作站和10個工作站的情況。寬度限制為5wm。圖3展示了生產(chǎn)流水線與總長度的最大目標。很明顯，緩沖區(qū)空間的優(yōu)勢隨著總長度的增加而減少。Hatcher（1969）[7]表明，在大多數(shù)情況下，10個緩沖區(qū)空間對于生產(chǎn)流水線是足夠的。本文的研究表明，總共設(shè)計10個緩沖區(qū)并不總是一個不錯的選擇。從圖3可以看出，當有5個工作站時，有10個緩沖空間的生產(chǎn)流水線的吞吐量可以達到理想吞吐量的60%（無波動時），而當有10個工作站時，達到理想吞吐量的40%。本文建議設(shè)計師在作出決定之前先計算不同的方案，以及增加生產(chǎn)流水線長度的成本。

表1和表2列出了緩沖區(qū)分配結(jié)果。其中，數(shù)據(jù)Ti為Si子系統(tǒng)的容量大小。數(shù)據(jù)Pli為平行線數(shù)目。規(guī)定每個數(shù)據(jù)的中間數(shù)據(jù)為中間區(qū)域范圍，表1數(shù)據(jù)Ti的中間區(qū)域范圍為T2與T3、表2數(shù)據(jù)Ti的中間區(qū)域范圍為T5;表1數(shù)據(jù)Pli的中間區(qū)域范圍為Pl3、表2數(shù)據(jù)Pli的中間區(qū)域范圍為Pl5與Pl6。

正如本文所計算得到的表格所展現(xiàn)的數(shù)字，Ti與Pli的計算結(jié)果均呈現(xiàn)低-高-低的正態(tài)分布狀態(tài)，如15緩沖區(qū)間上的Ti為3、5、4、3，Pli則為1、1、1、1、1;16緩沖區(qū)間上的Ti為3、5、5、3，Pli則為1、1、1、1、1……24緩沖區(qū)間上的Ti為5、7、7、5，Pli則為2、2、3、2、2。數(shù)據(jù)的計算結(jié)果均為先升后減。

因此，在大多數(shù)情況下，最優(yōu)分配是對稱的。

4.2 不平衡生產(chǎn)流水線

不平衡的生產(chǎn)流水線比平衡的生產(chǎn)流水線復雜得多。本文研究了2個例子。第一個例子有5個工位，每個工位單位時間的加工速度分別為4、7、10、7、4個工件。第二個例子有10個工位，每個工位單位時間的加工速度分別為8、4、7、5、

10、7、7、4、7、5個工件。生產(chǎn)流水線的最大吞吐量與總緩沖區(qū)大小的對比如圖4所示。由此可以看到，曲線與圖3非常相似，這表明在平衡線和不平衡線中，總緩沖區(qū)大小對吞吐量的影響是相似的。

表3和表4列出了緩沖區(qū)分配結(jié)果。Bulgak等人（1995）[8]表明緩沖區(qū)大小與擁塞可能性呈正相關(guān)。本文的研究表明，當本文考慮復雜的生產(chǎn)流水線時，情況更加復雜，最優(yōu)的緩沖區(qū)分配方案往往采取非常不規(guī)則的形式。與上面相關(guān)結(jié)論形成截然對比的是，數(shù)據(jù)Ti的分布區(qū)域不再呈現(xiàn)正態(tài)分布，而是從前到后逐步遞減，而數(shù)據(jù)Pli的計算結(jié)果分布趨勢仍與之相同。

5 結(jié)語

本文通過利用排隊理論對各子系統(tǒng)進行聚合，結(jié)合對平衡生產(chǎn)流水線和不平衡生產(chǎn)流水線進行實驗設(shè)計，并加以使用模擬退火的智能算法思想得出2個相關(guān)結(jié)論：在平衡生產(chǎn)流水線中，在大多數(shù)情況下，最優(yōu)分配是對稱的，并在中間區(qū)域范圍內(nèi)多分配一些;在非平衡生產(chǎn)流水線中，情況更加復雜，最優(yōu)的緩沖區(qū)分配方案往往采取非常不規(guī)則的形式。本文結(jié)論通過科學合理步驟得出，具有較高的信效度，可為多數(shù)企業(yè)的離散型生產(chǎn)流水線提供借鑒。

【參考文獻】

【1】晏磊，高萍，黃蓉蓉.關(guān)于運籌學理論及其在生活中的實際應(yīng)用研究[J].佳木斯職業(yè)學院學報，2021，37（4）：48-49.

【2】尹慧超，徐維.基于遺傳算法的串行生產(chǎn)線性能優(yōu)化[J].華北科技學院學報，2019，16（5）：79-85.

【3】羅非非，郭永江.基于累積前景理論的M/M/1排隊模型[J].哈爾濱商業(yè)大學學報（自然科學版），2021，37（4）：475-482.

【4】譚岐鈺，張紅波，高貴兵.基于人員調(diào)度優(yōu)化的混流生產(chǎn)線平衡改善[J].湖南科技大學學報（自然科學版），2021，36（2）：52-59.

【5】王彪，高天祥，孫林雨.多模式連續(xù)鑄軋生產(chǎn)線高速飛剪的應(yīng)用研究與優(yōu)化[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.