基于可用度評價的串行生產線緩沖分配方法

周炳海,余佳迪,邵健一

（同濟大學機械與能源工程學院,上海201804）

基于可用度評價的串行生產線緩沖分配方法

周炳海,余佳迪,邵健一

（同濟大學機械與能源工程學院,上海201804）

為有效和快速地分配緩沖區容量,提高串行生產線可用度和產出率,提出一種基于可用度評價的緩沖分配方法.在考慮串行生產線特性的同時,結合馬爾科夫理論,通過分析設備狀態及緩沖狀態間的轉化規律,建立串行生產線的可用度評價模型.在此基礎上構建求解緩沖分配問題的遺傳算法,并運用算例給出緩沖分配問題的解決過程.從產出率、在制品數量等方面將提出方法與其他分配方法進行比較,從而驗證與評價數學模型的準確性.結果表明提出的緩沖分配方法是可行、有效的.

串行生產線；緩沖分配；可用度評價；馬爾科夫

緩沖區是串行生產線的重要組成部分,合理分配有限的緩沖區容量對于平衡上下游設備之間的生產率差異,減輕由設備故障等因素引發的系統波動,提高系統可用性和產出率具有重要意義.

緩沖區設置問題（buffer allocation problem, BAP）一直是個研究熱點.Manitz［1］提出了一種基于排隊模型的分析方法來分析、配置緩沖區容量.Colledani等［2］提出了一種BAP分配方法,用以評價生產系統生產和物流方面的性能.Demir等［3］針對不穩定的生產線,提出一種模糊搜索方法,以確定生產線上緩沖區的位置及容量大小,使系統產出最大.Abdul-Kader等［4］建立了基于饑餓和阻塞狀態的非線性優化模型,在此基礎上進行緩沖區容量配置問題求解.Battini等［5］考慮到機器故障和加工時間的波動,建立了仿真模型,并對緩沖區的容量進行魯棒性設計.Shi等［6］研究了加工速率呈非線性的緩沖區設置問題.Aksoy等［7］利用開放式排隊網絡和分解、擴展的方法,提出了一種漸進式的緩沖區容量優化方法.Helber等［8］考慮到設備加工時間的隨機波動性,利用線性規劃的方法進行緩沖區分配問題的求解.Pan等［9］通過分解生產系統的方法,解決了均衡、未均衡生產系統中的緩沖區分配問題.Hillier［10］以最大化系統收益為目標,建立了啟發式算法,并進行了緩沖容量優化設計.Battini等［11］設計了基于實驗的緩沖區容量分配算法.但上述文獻都沒有從設備的可用度角度來研究緩沖區容量分配.本文以帶緩沖區的串行生產線為研究對象,建立了串行生產系統的可用度評價模型,并提出了一種基于可用度評價模型的緩沖區容量分配方法.

1 問題描述

本文所研究的串行生產線由n臺設備（M1～Mn）串聯組成,布局屬于帶緩沖的Flow shop生產線,設備間在制品緩沖區為B1～Bn－1,如圖1所示.

圖1 串行生產線Fig.1 Series production line

在緩沖區總容量給定的情況下,優化求解目標是最大化系統可用度.數學模型可表示為

式中：A為串行生產線的穩態可用度,Vi為緩沖區Bi的容量,V為生產線的緩沖區總容量,Vup為緩沖區Bi的容量上限.

為了有效描述評價串行生產線可用度,做如下假設：1）生產線第1臺機器不饑餓,最后1臺機器不堵塞；2）設備故障后無需等待,可立即開展維修作業,但需要一定的時間來修復；3）設備故障和修復過程都服從指數分布；4）所研究的串行生產線t＋1時刻系統狀態的概率分布與t時刻以前的狀態無關,僅與t時刻的狀態有關,即系統滿足Markov模型.

2 二級子系統可用度

串行生產線中由相鄰2個設備及中間緩沖區組成的系統稱為二級子系統,如圖2所示.研究串行生產線可用度模型的核心思想描述如下：首先,計算二級子系統可用度；然后,使用一個虛擬設備來等效替換一個二級子系統,通過虛擬設備之間的不斷等效替換最終構建成一個基于虛擬設備的二級子系統,并進行其可用度求解.

圖2 二級子系統基本構成Fig.2 Basic components of subsystem

二級子系統可用度大小由其設備參數和緩沖區容量決定.在評價二級子系統可用度過程中,首先對二級子系統的設備狀態進行分類,描述出不同設備狀態間的相互轉化規律,并計算出系統穩態時處于各種狀態的概率.然后,分別描述不同設備狀態下緩沖區各狀態間的相互轉化規律,并分析其穩態概率.最后,綜合分析設備和緩沖區狀態,計算出二級子系統可用度.這里以包含設備M1、M2和緩沖區B1的二級子系統Sub1為例計算其可用度.

2.1 二級子系統設備狀態變化規律

二級子系統Sub1中所包含的2個設備M1和M2各自有2種設備狀態,故Sub1有4種設備狀態,其設備狀態空間Sys1可表示為

式中：狀態X1,1表示Sub1中的2個設備均處于正常工作狀態；狀態X1,2表示Sub1中的設備M1正常工作,設備M2故障；狀態X1,3表示Sub1中的設備M1故障,設備M2正常工作；狀態X1,4表示Sub1中的2個設備均處于故障狀態.

在故障和維修作業的作用下,Sub1的各狀態可以相互轉換,其狀態轉移情況如圖3所示.

圖3 二級子系統設備狀態轉移圖Fig.3 Equipment states transition of subsystem

結合M1、M2設備參數,通過分析可以得到各狀態間相互轉化的規律,二級子系統Sub1各狀態間的狀態轉移矩陣可表示為

式中：λi為設備Mi的故障率；μi為Mi的修復率.

根據Markov理論,系統在足夠長的時間內最終會運行到一個穩定狀態,即達到其穩態,Sub1設備狀態的穩態方程可表示為

2.2 二級子系統緩沖區狀態變化規律

二級子系統Sub1中緩沖區容量為V1（V1∈N＋）,故緩沖區的狀態為：空、有1個在制品、有2個在制品、…、有V1－1個在制品、滿等V1＋1個狀態,因此Sub1中的緩沖區B1的狀態空間Buf1可表示為

但對于二級子系統Sub1來講,不同系統設備狀態下的緩沖區在制品數量變化規律各不相同.當系統處于狀態X1,4時,緩沖區中在制品數量不會發生任何變化,故在接下來的在制品數量變化規律的討論中,不再考慮系統處于狀態X1,4的情況.

1）Sub1處于X1,1狀態：二級子系統處于X1,1狀態時,系統中的2個設備均正常工作,M1為緩沖區B1提供在制品的同時,M2在不斷消耗緩沖區B1中的在制品.在該狀態下,緩沖區B1的狀態變化情況如圖4所示.

圖4 X 1,1狀態下的緩沖區狀態轉移圖Fig.4 Buffer states transition under X 1,1

此時的緩沖區狀態轉移矩陣可表示為

式中：PBufi,j為Subi處于Xi,j狀態時,緩沖區Bi的狀態轉移矩陣；γ＝（1－ω1）ω2；η＝ω1（1－ω2）；ε＝ω1ω2＋（1－ω1）（1－ω2）；ωi為設備Mi的生產率.

2）Sub1處于X1,2狀態：二級子系統處于X1,2狀態時,設備M1正常工作,設備M2故障.在此種狀態下,M2不消耗B1中的在制品,而M1不斷為緩沖區B1提供在制品.在該狀態下,緩沖區B1的狀態變化情況如圖5所示.

圖5 X 1,2狀態下的緩沖區狀態轉移圖Fig.5 Buffer states transition under X 1,2

此時的緩沖區狀態轉移矩陣可表示為

3）Sub1處于X1,3狀態：二級子系統處于X1,3狀態時,設備M1故障,設備M2正常工作.在此種狀態下,M1不為緩沖區B1提供在制品,而M2卻在消耗B1中的在制品.在該狀態下,緩沖區B1的狀態變化情況如圖6所示.

圖6 X 1,3狀態下的緩沖區狀態轉移圖Fig.6 Buffer states transition under X 1,3

此時的緩沖區狀態轉移矩陣可表示為

狀態轉移矩陣PBuf1,1、PBuf1,2、PBuf1,3均為（V1＋1）×（V1＋1）階矩陣.當二級子系統處于不同設備狀態下時,緩沖區穩態方程可表示為

求解不同j取值下的式（11）,便可以得到系統在X1,1,X1,2,X1,3狀態下,緩沖區的穩態概率矩陣.結合實際情況可以知道,處于X1,2、X1,3狀態下的緩沖區在足夠長的運行時間后,必定會達到滿或空的狀態,即其緩沖區穩態運行時為滿或空的狀態.結合假設（4）,此種情況顯然是不合理的,由于設備的及時維護,系統緩沖區未必能達到其穩態.為此,在二級子系統的可用度的評價過程中,將引入設備維護方面的參數對X1,2、X1,3狀態下的緩沖區的穩態概率分布進行修正.

2.3 二級子系統可用度評價

在實際生產中,當設備Mi（i∈｛1,2,3,…, n｝）故障時,其前或其后的設備并不會立即停止作業,而會一直加工到2個設備間的緩沖區達到滿或空的狀態,因此能保證系統正常運行的狀態包括：（a）系統處于X1,1時設備M2不空閑,即M1和M2都正常工作且緩沖區B1不滿；（b）系統處于X1,2時設備M1不空閑,即M2故障,M1正常工作且緩沖區B1不滿；（c）系統處于X1,3時設備M2不空閑,即M1故障,M2正常工作且緩沖區B1不空.

二級子系統Sub1處于X1,2狀態時,其緩沖區B1“穩態”由其緩沖區初始狀態、設備M1生產速率、設備M2的維護時間共同決定.此種情況下能保證二級子系統正常工作的概率可表示如下：

式中：Numi,j,0為Subi處于Xi,j狀態時,緩沖區Bi中的在制品數量；PNumi,j,0為Subi處于Xi,j狀態且Bi中在制品數量為Numi,j,0時,系統正常工作的概率；Num1,2,0∈Z,0≤Num1,2,0≤V1,且Num1,2,0服從的概率分布.

當二級子系統Sub1處于X1,3狀態情況時,能保證二級子系統正常工作的概率可表示如下：

式中：Num1,3,0∈Z,0≤Num1,3,0≤V1,且Num1,3,0服從的概率分布.

當二級子系統Sub1緩沖區非空時,其穩態可用度可表示為

當二級子系統Sub1緩沖區為空時,其穩態可用度可表示為

3 串行生產線可用度

結合串行生產線的可靠性規律,由二級子系統

Sub1等效的虛擬設備M11的各種參數可以表示為

通過二級子系統的虛擬設備等效操作,并利用公式（4）～（18）便可求解出等效后的虛擬二級子系統的可用度.對于n臺設備的串行生產系統,其虛擬設備的等效過程如圖7所示.

等效過程的核心步驟描述如下：

Step1 將n臺設備的串行生產系統拆解成i個二級子系統,其中i＝?n／2」.

若n＝2i,可以得到Sub1＝｛M1,B1,M2｝, Sub2＝｛M3,B3,M4｝…Subi＝｛M2i－1,B2i－1,M2i｝等i個二級串行子系統.

若n＝2i＋1,分解后可以得到i個二級子系統Sub1＝｛M1,B1,M2｝,Sub2＝｛M3,B3,M4｝,…Subi＝｛M2i－1,B2i－1,M2i｝和未能分解到二級子系統中的Mn.利用式（4）～（18）求解Subi的可用度并將其虛擬成為設備,并利用、Mn、Bn－1構成的二級子系統代替原有的Subi.

圖7 二級子系統迭代過程Fig.7 Iteration process of subsystem

Step2 利用式（4）～（18）求解Step1中所得到的二級子系統的可用度,并將其虛擬成為設備｛,,…,｝.虛擬得到的i個設備｛,,…,｝和Step1中分解二級子系統所剩下的i－1個緩沖｛B2,B4,…,B2（i－1）｝構成新的串行生產線.

Step3 重復Step1和Step2步驟,最終可以得到原串行生產線等效二級子系統｛,B2k,｝,其中2k≤n,2k＋1≥n.利用式（4）～（18）便可以得到｛, B2k,｝的可用度,即串行生產線可用度的等效值.

串行生產線穩態可用度可表示為

4 求解算法

本文所研究的問題具有NP-Hard特性,傳統的運籌學方法很難對其求解,而遺傳算法隱含全局并行搜索特性非常適合本問題的求解,為此利用遺傳算法來求解該目標函數.

遺傳算法求解緩沖區設置問題的主要步驟描述如下：

Step1 初始化種群

Step2 個體評價

將初始種群代入所構建的可用度評價模型中,利用模型求解出各可行解的系統可用度,每條染色體的適應度值f（G）為其所對應系統的系統可用度,即A＝f（V1,V2,……,Vn－1）.

Step3 種群進化

1）選擇運算

2）交叉運算

從種群中選擇一對染色體α＝｛α1,α2,…,αK｝、β＝｛β1,β2,…,βK｝,根據一定的交叉概率pc進行單點交叉,得到子代染色體δ1、δ2,其中

3）變異運算

4）保留最優染色體

父代中適應度最大的染色體直接保留在子代種群中.

Step4 終止檢驗

反復執行Step3若干次,直到種群的最優適應度值達到穩態狀態,并輸出種群中適應度最大的染色體個體作為最優解.

圖8 染色體編碼Fig.8 Chromosome encoding

5 算例分析

為了有效評價本文所提出的串行生產線可用度評價模型和緩沖區分配方法,本文結合實際工程應用需求,分別以包含5～10設備的串行生產線L5～L10為例進行算例分析,其中Li為包含i個設備的串行生產線.串行生產線中的設備參數如表1所示,其中各設備的操作時間t1＝1 s,設備故障密度函數和修復時間密度函數都服從負指數分布,分別為

串行生產線Li中設備按照從前向后的順序為M1,M2,…,Mi.

基于本文所構建的可用度評價模型,利用遺傳算法對6個串行生產線L5～L10分別按照總緩沖容量為120、150、180、210、240、270進行緩沖容量分配.其種群大小50,交叉率0.4,變異概率0.001,進化迭代次數200次,模型運行結果如圖9所示,L5～L10系統可用度在模型迭代過程中不斷優化,并在若干次迭代后最終趨于平穩,即緩沖區容量達到了較優的分配.

圖9 不同串行生產線的緩沖分配方案Fig.9 Solution of BAP for different serial production lines

其中系統L5、L6、L7在模型運行過程中可用度的變化過程參考圖9中左邊的主坐標軸,系統L8、L9、L10參考圖9中右邊的輔坐標軸.所得到的各系統緩沖分配方案、系統可用度和搜索時間t2,如表2所示.

表2 緩沖區分配方案及系統可用度Tab.2 Solution of BAP and availability

為評價所構建評價模型在緩沖區分配問題上的有效性,本文將基于可用度評價模型得到的緩沖區分配結果與基于DDX［12-13］評價方法得到的緩沖區分配方案進行比較.此處,本文采用仿真模擬方法進行驗證比較,即將2個模型所得到的緩沖區分配方案輸入仿真模型,比較不同緩沖區分配方案下系統的性能.簡化表示,利用M1表示基于DDX評價方法的緩沖區分配模型,M2表示基于可用度評價模型的緩沖區分配模型.

針對算例系統L5～L10,M1所得到的緩沖區分配方案及可用度如表3所示.

表3 M1所得緩沖區分配方案及產出率Tab.3 Solution of BAP and throughput based on M1

利用Witness分別為不同參數下的串行生產線L5～L10建立仿真模型,運行105個單位時間后,仿真結果如表4所示,表中asi為緩沖區Bi中的平均在制品數量；CW為各緩沖區平均在制品數量總和；E為串行生產線產出率.

表4 Witness仿真結果Tab.4 Result of Witness simulation

由表4可知,M1和M2所得到的緩沖區分配方案所得到的系統產出率相同,即2種方法都可以有效地進行緩沖區容量分配.但2種方法在控制系統在制品數量和評價系統產出率的效果上有所區別,其中在制品數量控制效果如圖10所示,

圖10 在制品總量控制比較Fig.10 Comparison of conwip controlling ability

由圖10可知,對于不同的設備數量（5～10）,系統中在制品數量與設備數量并不存在一定的單調性.但在相同設備數量下,M2比M1能夠更好的實現在制品數量控制.

算例分析中各設備加工時間t1＝1 s,因此M2所得到的系統可用度數值上等于系統產出率［14］.為此,對于M1和M2在評價系統產出率效果的比較如圖11所示.

由圖11可知,對于所有算例,M1和M2所得的產出率都與仿真結果有著一定的差距,但M2所得到的系統產出率更加貼近實際的仿真結果.因此相比M1而言,M2對串行生產系統的產出率評價效果更好.

圖11 系統產出率評價效果比較Fig.11 Comparison of throughput assessment ability

圖12 搜索時間比較Fig.12 Comparison of searching time

由表2、3和4可得,M1和M2這2種方法都能找到較優解,但其搜索速度有所區別.如圖12所示,對于不同的設備數量（5～10）,搜索時間會隨著設備數量的增加而增加.總體來說,在相同設備數量下, M2所需的時間要比M1少.

綜上所述,對于上述算例系統,通過M1、M2這2種方法都可以得到較優的緩沖區配置方案,但M2方法在控制系統在制品數量和評價系統產出率方面效果更好.

6 結 語

本文提出的基于可用度評價的串行生產線緩沖區容量分配方法可優化串行生產線中緩沖區分配問題,同時為求解緩沖區分配問題提供了新思路.在控制系統在制品總量上,對比目前文獻中的基于DDX緩沖區容量分配方法,本文所構建的方法有明顯的優勢.在系統產出率評價方面,該方法能夠有效地改善串行線生產線的產出率.

（References）：

［1］MANITZ M.Queueing-model based analysis of assembly lines with finite buffers and general service times［J］.Computers&Operations Research,2008,35（8）：2520-2536.

［2］COLLEDANI M,TOLIO T.Integrated analysis of quality and production logistics performance in manufacturing lines［J］.International Journal of Production Research,2011,49（2）：485-518.

［3］DEMIR L,TUNALI S,ELIIYI D T.An adaptive tabu search approach for buffer allocation problem in unreliable non-homogenous production lines［J］.Computers& Operations Research,2012,39（7）：1477-1486.

［4］ABDUL-KADER W,GANJAVI O,BAKI F.A nonlinear model for optimizing the performance of a multiproduct production line［J］.International Transactions in Operational Research,2011,18（5）：561-577.

［5］BATTINI D,PERSONA A,REGATTIERI A.Buffer size design linked to reliability performance：A simulative study［J］.Computers&Industrial Engineering, 2009,56（4）：1633-1641.

［6］SHI Chuan,GERSHWIN S B.An efficient buffer design algorithm for production line profit maximization［J］.International Journal of Production Economics, 2009,122（2）：725-740.

［7］AKSOY H K,GUPTA S M.Near optimal buffer allocation in remanufacturing systems with N-policy［J］.Computers&Industrial Engineering,2010,59（4）：496 -508.

［8］HELBER S,SCHIMMELPFENG K,STOLLETZ R, et al.Using linear programming to analyze and optimize stochastic flow lines［J］.Annals of Operations Research,2011,182（1）：193-211.

［9］PAN Xiao-yong,WU Jiang,ZHANG Quan-wei,et al.The study of buffer allocation problem in complex production line［J］.TELKOMNIKA Indonesian Journal of Electrical Engineering,2014,12（3）：2342-2349.

［10］HILLIER M.Designing unpaced production lines to optimize throughput and work-in-process inventory［J］.IIE Transactions,2013,45（5）：516-527.

［11］BATTINI D,FACCIO M,PERSONA A,et al.Buffer design for availability：a new simulative study in case of infant and random failures［J］.International Journal of Services and Operations Management,2013,14（2）：157-174.

［12］DALLERY Y,DAVID R,XIE Xiao-lan.Approximate analysis of transfer lines with unreliable machines and finite buffers［J］.IEEE Transactions on Automatic Control,1989,34（9）：943-953.

［13］NAHAS N,AIT-KADI D,NOURELFATH M.A new approach for buffer allocation in unreliable production lines［J］.International journal of production economics,2006,103（2）：873-881.

［14］HOPP W J,SPEARMAN M L.工廠物理學［M］.北京：清華大學出版社,2002：248-283.

Buffer allocation method for series production lines based on availability assessments

ZHOU Bing-hai,YU Jia-di,SHAO Jian-yi
（School of Mechanical Engineering,Tongji University,Shanghai 201804,China）

To quickly and effectively solve buffer allocation problems and improve the availability and throughput of series production lines,a buffer allocation method based on availability assessments was proposed.Combining with the characteristic of serial production lines and the Markov theory,an availability assessment model was structured based on the analysis of the machine and buffer states transition rule.On the basis of the descriptions mentioned above,a genetic algorithm for solving buffer allocation problems was constructed.Numerical examples were presented to show the solving process of buffer allocation problems.To verify and evaluate the accuracy of the mathematical model,the proposed method was compared with other methods from the aspects of throughput and the number of work-in-process.The results indicate that the proposed allocation method is feasible and valid for buffer allocation problems.

series production line；buffer allocation；availability assessment；Markov

10.3785／j.issn.1008-973X.2015.05.012

TP 16

A

1008-973X（2015）05-0893-08

2014-10-17. 浙江大學學報（工學版）網址：www.journals.zju.edu.cn／eng

國家自然科學基金資助項目（61273035,71471135）；國家“863”高科技研究發展計劃資助項目（2009AA043000）.

周炳海（1965－）,男,教授,博導,從事預防性維護建模,制造系統／物流系統調度、建模、仿真的研究.E-mail：bhzhou＠tongji.edu.cn