巫江 楊偉琦 王東

【摘? 要】論文研究了離散型生產(chǎn)流水線中緩沖區(qū)的分配問(wèn)題。論文建立了一個(gè)將生產(chǎn)流水線分解為S-B-S（工作站-緩沖區(qū)-工作站）子系統(tǒng)的模型，利用排隊(duì)理論對(duì)各子系統(tǒng)進(jìn)行聚合，對(duì)平衡生產(chǎn)流水線和不平衡生產(chǎn)流水線進(jìn)行了實(shí)驗(yàn)設(shè)計(jì)，并結(jié)合計(jì)算結(jié)果，提出了緩沖區(qū)分配問(wèn)題的一般結(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ū);排隊(duì)論;模擬退火法

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

【中圖分類號(hào)】F273? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文獻(xiàn)標(biāo)志碼】A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?【文章編號(hào)】1673-1069（2021）11-0115-04

1 引言

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

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

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

2 問(wèn)題描述

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

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

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

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

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

3 研究方法：模擬退火法

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

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

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

4 結(jié)果分析

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

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

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

表1和表2列出了緩沖區(qū)分配結(jié)果。其中，數(shù)據(jù)Ti為Si子系統(tǒng)的容量大小。數(shù)據(jù)Pli為平行線數(shù)目。規(guī)定每個(gè)數(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。

正如本文所計(jì)算得到的表格所展現(xiàn)的數(shù)字，Ti與Pli的計(jì)算結(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ù)的計(jì)算結(jié)果均為先升后減。

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

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

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

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

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

5 結(jié)語(yǔ)

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

【參考文獻(xiàn)】

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

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

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

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

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