基于馬爾科夫鏈的混流裝配線緩沖區配置優化研究*

曹振新，鄂世舉，焦衛東，周 武

(浙江師范大學 工學院，浙江 金華 321004)

基于馬爾科夫鏈的混流裝配線緩沖區配置優化研究*

曹振新，鄂世舉，焦衛東，周 武

(浙江師范大學 工學院，浙江 金華 321004)

為提高混流裝配線物流系統的可靠性，在各工位間需設置緩沖區。緩沖區容量是影響生產線性能指標的重要因素，在分析緩沖區功能的基礎上，提出了生產線緩沖區的類型和結構，建立了自動導引車和自動化倉庫存取系統構成的物流系統工作流程，利用馬爾科夫鏈狀態轉移方程建立了基于AGV和AS/RS的裝配線閉環物流系統數學模型，分析了緩沖區容量參數、AGV數量及生產線性能指標。實例計算表明，該模型方法與物流系統參數的正確性，滿足了混流裝配線對物流配送系統的要求。

馬爾科夫鏈；混流裝配線；緩沖區容量；排隊論

客戶的多樣化需求促使制造型企業從傳統的大規模生產方式向多品種、小批量生產方式轉化。利用混流裝配線(Mixed Model Assembly Line，MMAL)，可實現在同一條生產線上裝配多種不同型號、數量，但工藝基本相似的產品，該方法在汽車和家電等行業中得到了廣泛應用[1]。流水線的緩沖區配置是生產線設計時應考慮的重要因素。緩沖區不僅可用于存儲在制品WIP，還能進行在制品重排，使得生產線具有良好的柔性。緩沖區配置問題(Buffer Allocation Problem，BAP)就是將一定數量的緩沖區分配到生產線的工位間，使得整條生產線順利運行。物料處理延遲和緩沖區容量大小設置不合理都會影響整個裝配線的正常運行。若緩沖區太小會導致工位堵塞，過大又會導致工位空閑和時間延誤[2]。無論工位空閑還是工位堵塞，都會使生產線生產能力不平衡，出現各工位作業負荷不均，嚴重影響生產線的生產效率和可靠性；因此，配置合適的緩沖區是生產線設計中的一個重要而復雜的問題。

國內外學者對混流裝配線的研究主要集中在作業平衡與產品排序問題上，并發表了很多學術論文；但對生產線緩沖區的配置與容量優化方面卻研究較少。Michael等用排隊模型建立多工位有限緩沖區的裝配流水線生產率最大化模型，評估了兩工位子裝配線的生產性能。Fulya等用人工神經網絡算法對裝配線緩沖區容量進化優化配置和仿真分析[3]。Saeed等研究了有限容量排隊網絡的多類、多級裝配系統交貨時間優化問題，假設排隊網絡工位的裝配工序時間互相獨立，且服從指數服務概率分布，利用馬爾可夫過程概念建立了任何類型產品訂單接受時間和成品交貨時間的系統微分方程[4]。MacGre等研究了單臺服務器基于有限緩沖區的M/G/1/K排隊網絡性能[5]。國內的譚明等建立了基于有限緩沖區的生產線可靠性模型，并對生產線的轉移狀態和可靠性進行了分析，得到了生產線不同狀態間的狀態轉移概率的計算方法[6]。華中生建立了考慮隨機加工時間的非均勻節拍生產線的緩沖庫存容量設計模型，提出了緩沖庫存最優設計的一些結構特性[7]。高貴兵建立了基于馬爾科夫過程原理的混流裝配線可靠性模型，推導出裝配線可用度與緩沖區容量之間的關系[8]。孟凡力根據隨機原理提出了緩沖區被充滿概率和緩沖區容量之間的函數關系，采取遞進算法算出整個裝配系統各個工位之間的緩沖區容量[9]。

綜上所述，目前針對串/并聯生產線緩沖區(BUFFER)容量設計方法大多過于理論化。如何使緩沖區有足夠的空間存放在制品，同時避免因緩沖區設置不當引起物流中斷是非常重要的。排隊網絡是設計與分析生產線的常用方法，但應用排隊網絡解決生產線“饑餓”與“阻塞”現象的有限緩沖區配置問題卻較少。應用排隊網絡模型研究裝配線的緩沖區配置優化問題，可將該類物料運輸系統看作隨機服務系統，每個裝配工位/站是排隊網絡的一個節點。自動化存取系統(Automatic Storage and Retrieval System，AS/RS)也叫立體倉庫緩沖區，其緩沖區自動化程度高，重新排序工件性能好，易于實現混流生產，本文對該類緩沖區進行建模優化研究。

1 問題描述

由于混流裝配線由輸送帶連接若干個裝配作業單元所構成，各工位間會存在各種不確定性和干擾因素，因此需要一定的保護能力來平衡不確定性，使生產具有一定的柔性和魯棒性。這種保護能力在多數情況下可通過在生產線中加入緩沖區來實現。若緩沖區太小，容易發生堵塞故障；若容量太大，會增加緩沖區的成本、維護費用及在制品的流動時間，造成物流中斷[10]。裝配生產線上都會有瓶頸工位，在瓶頸工位之前容易出現工位堵塞，在瓶頸工位之后容易出現工位空閑，使生產線系統的可靠性和整條生產線的效率降低。根據TOC理論，在實際裝配生產線設計時，選擇在生產系統中的幾個關鍵的瓶頸工位之前設置緩沖區。混流裝配線簡化工藝流程模型如圖1所示[11]。

圖1 混流裝配線簡化工藝流程模型

在產品總裝的混流裝配過程中，各裝配工位在裝配時刻需要判斷工位旁有無相應的零部件。如沒有足夠相應類型的零部件數量，則停工待料。在瓶頸工位之前設置在制品緩沖區，可提高整條生產線的可靠性。本文主要討論混流裝配流水線相鄰關鍵工位間的基于安全提前期的緩沖區設計問題，不存在損失制和機器故障。

緩沖區按照容量大小來分，可分為無限容量緩沖區、大緩沖區和小緩沖區。無限容量緩沖區假設存儲在緩沖區上的工件的數量沒有限制，是一種純理論化的緩沖區；大緩沖區一般指容量較大的有限緩沖區，可實現在制品的重新排序，大多應用在汽車等大型機械裝備混流生產線中；小型緩沖區是設置在兩裝配工位間的有限臨時存儲區，只需周期性配送補貨。自動存取緩沖區采用了立體倉庫的結構形式，每個區域由若干運輸小車(Automated Guided Vehicle，AGV)完成存取工作。AS/RS運行和處理速度快，并可實現對工件的重新排序，提高了勞動生產率，降低了勞動強度，使企業物流更趨合理化。

2 基于AGV和AS/RS的裝配線物流調度系統

AS/RS是采用自動化存取輸送設備進行存取倉庫的物料作業，是裝配生產過程中的物流中心。其主要由存儲貨架及托盤、自動導引車、堆垛機和自動控制系統所組成。存儲貨架由1個或多個存儲巷道組成，巷道兩邊是存儲貨架，每個巷道有1個堆垛機服務。AS/RS具有拾取和放置(pickup-and-deposit)工位的存儲系統，該存儲系統能夠高效和精確地完成存取操作。AGV裝備有自動導引裝置，能夠沿設定路徑行駛的物料運輸小車在汽車生產線中得到了廣泛的應用。將工位緩沖區補充庫存的請求當作需要服務的顧客，AGV為這些請求服務，多臺AGV可作為一組服務器；各工位緩沖區為各工位服務，將其作為另一組服務器。對于每一個服務器，假設服務請求的到達和離去都是Poisson過程，各節點的服務時間呈指數分布。AGV系統增加了裝配系統的柔性，改善了操作人員的作業環境，提高了裝配系統的智能和自動化程度。

當1個工位緩沖區的庫存小于安全值時，則該工位發出要求補充緩沖區庫存消息，相應的緩沖區即成為發出一個需要AGV的信號，該請求進入以AGV為服務器的隊列。當AGV完成一個請求后，該請求即成為一個安全的緩沖區。緩沖區隊列的服務時間對應于緩沖區相鄰2次補充庫存的間隔時間。工位緩沖區與AGV之間可簡化為具有2組服務器的閉環排隊網絡模型，AGV調度系統是一個M/M/C系統。具有AGV、AS/RS以及各工位具有緩沖區的裝配系統自動化程度高、柔性大，適合大批量定制生產模式。一般AGV-AS/RS系統由多輛AGV和AS/RS構成(見圖2)，其物流調度系統流程如下。

1)當工位緩沖區監測到剩余庫存量達到安全補料庫存時，通過通信設備發出物料補充信號到物流管理中心，形成出庫任務。

2)物流調度系統將需要補充的物流種類和數量發送到AS/RS管理系統，形成堆垛機的對應任務排列。

3)AS/RS管理系統根據其出貨要求，將請求的AGV信息發送到物料中心調度系統，根據各AGV的狀態和需要的完成時間，確定為此請求服務的AGV。

4)AGV按先到先服務的原則裝載物料，并送至請求工位的緩沖區AS/RS。物料到達后，AGV將空箱送回到回收站，并回到指定停車點。

5)如果該AGV沒有其他任務，則回AGV站。物流調度系統把任務執行情況上報物流管理系統，至此完成一個物料出庫的服務周期。

6)物流調度系統根據物料入庫申請和庫存信息形成入庫任務，并由相應的堆垛機完成入庫任務，由AGV完成一個物料入庫的服務周期。

從上述物流調度系統流程可見，將基于AGV和AS/RS的物流系統視為一個隨機排隊服務系統，可建立該系統的排隊網絡模型，并分析AGV數量與系統性能指標之間的關系，如AGV的利用率、平均延遲時間及工位緩沖區的可靠性等之間的關系。假設裝配系統總體布局和AS/RS結構參數已經確定，基于AGV和AS/RS的物流系統設計的主要內容是：1)AS/RS緩沖處理能力(出庫能力)計算；2)確定AGV的調度規則；3)確定AGV的數量。

圖2 基于AGV和AS/RS構成的物流系統

3 模型構建

閉環排隊數學模型的假設條件如下。

1)生產線有m個緩沖站，緩沖站i的物料需求(顧客)是參數為λi的Poisson流。

2)物流排隊系統有AGV運輸小車n臺，服務時間獨立，且服從參數u的負指數分布。

3)設λ為到達率，u為服務率，出庫物料任務隊列按先入先出(FIFO)原則接受空閑AGV小車的運輸服務，不存在損失制。

4)在時刻t正在裝配的工位在(t,t+Δt)內，緩沖區庫存由大于安全值變為等于安全值的概率為：λΔt+o(Δt)。

5)在時刻t正在接受AGV服務的工位緩沖區庫存轉變為安全值的概率為：μΔt+o(Δt)。

6)各工位的庫存狀態信息(庫存≥安全值)分布相互獨立。

自動化立體倉庫輸送和自動引導車AGV運輸系統為隨機服務系統。{X(t),t∈T}是一個隨機過程，{X(t),t∈T}在t0時刻所處的狀態為已知時，與它在時刻t>t0之前所處的狀態無關。設馬爾可夫鏈X={X(t),t≥0}，狀態空間S={0,1,2,…}。顯然，{X(t),t≥0}是一個狀態離散、參數連續的有限齊次馬爾可夫過程。容易證明，{X(t),t≥0}是一個生滅過程。系統狀態轉移圖如圖3所示。

圖3 系統狀態轉移圖

用Xt表示該系統在時刻t庫存量≤安全值的工位數(已發出補料請求，尚未得到補料的工位)，k=0,1,2,…,m-1。則其狀態轉移概率矩陣滿足：

P(Xt,n+1=kn+1|Xt,1=k1,Xt,2=k2, …,
Xt,n=kn) =P(Xt,n+1=kn+1|Xt,n=kn)

(1)

式1表明該過程接下來的時間狀態可以完全由當前的狀態決定，而與過去的狀態無關，即具有馬爾可夫性。容易證明，{X(t),t≥0}是一個生滅過程。由生滅過程的定義有：

則根據生滅過程的相關性質，推導出該物流系統馬爾可夫過程{X(t),t≥0}的平穩分布概率為：

(2)

pk=

(3)

請求自動運輸小車服務的工位數(平均隊長)：

(4)

自動運輸小車請求的平均到達率：

(5)

AGV請求的平均等待時間：

(6)

AGV平均延遲時間：

(7)

自動運輸小車AGV的利用率：

UAGV=1-p0

(8)

工位緩沖區系統的可靠性：

(9)

4 實例計算與分析

設有一個基于AS/RS的混流裝配線系統，有4臺AGV為40個工位的緩沖區補充零部件。設AGV完成一次請求任務的平均時間為10 min，每個工位平均每小時補充一次物料。根據上述排隊網絡模型，則該過程的穩態分布p(k) = (0.032 8, 0.109 3, 0.177 5, 0.187 4, 0.144 5, 0.108 3, 0.079 0, 0.056 0, 0.038 5, 0.025 6,0.016 6, 0.010 4, 0.006 3, 0.003 6, 0.002 1, 0.001 1, 0.000 6, 0.000 3, 0.000 1, 0.000 1,0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 1, 0.000 0, 0.000 0,0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 0, 0.000 1, 0.000 0, 0.000 0,0.000 0)。橫坐標為工位的數量k，縱坐標為平穩分布值p(k)，如圖4所示。

圖4 狀態的平穩分布圖

由式5計算可得到，請求AGV服務的工位數期望(平均隊列長度)為4.0；由式6計算可得到，自動小車AGV的請求平均到達率為0.017；由式7計算可得到，請求的平均等待時間為6.70 min；由式8計算可得到，平均延遲1.70 min；由式9計算可得到，AGV的利用率為0.97；由式10計算可得到，工位緩沖區的可靠性為0.90。當AGV的數量變化時，系統性能指標與AGV數量的關系如圖5所示。

圖5 物流系統性能與AGV數量之間的關系

5 結語

多品種混流裝配提高了制造系統柔性和企業的精益化生產。緩沖區在復雜的裝配系統中起著重要作用，可為系統提供一定的保護能力來平衡各種干擾和不確定性。論文針對混流裝配線緩沖區容量優化問題進行研究，根據容量大小和結構形式對緩沖區進行了分類，建立了緩沖區容量和結構設計方法。在闡述AGV和AS/RS組成的自動存取物流系統工作流程的基礎上，建立了基于馬爾科夫鏈的物流系統的隨機排隊網絡模型，證明了該模型的可行性和正確性。經計算得到系統穩態的分布及條件排隊等待工位數量與等待時間數據，分析了該物流系統的相關性能及概率特性，證明了該方法的可行性。因實際設計生產線緩沖區時要考慮的因素較多，緩沖區容量的多目標優化配置仍需深入研究。

[1] 曹振新.混流汽車總裝過程的物料協同配送與管理信息系統研究[J]. 制造業自動化，2008(12): 25-29.

[2] Michael M. Queueing-model based analysis of assembly lines with finite buffers and general service times[J]. Computers & Operations Research, 2008(35):2520-2536.

[3] Fulya A, Berna D. Buffer allocation and performance modeling in asynchronous assembly system operations: An artificial neural network meta-modeling approach[J]. Applied Soft Computing, 2007(7):946-956.

[4] Saeed Y, Siamak N. Lead time control in multi-class multi-stage assembly systems with finite capacity[J]. Computers & Industrial Engineering, 2013(66):808-817.

[5] Smith J M. Properties and performance modeling of finite buffer M/G/1/K networks[J]. Computers & Operations Research, 2011(38):740-754.

[6] 譚民, 疏松桂. CIMS生產線中緩沖區狀態及可靠性分析[J]. 自動化學報, 1994, 20(3): 271-277.

[7] 華中生.非均勻節拍生產線緩沖庫存設計的結構特性[J]. 運籌與管理, 1994, 3(2): 29-33.

[8] 高貴兵，岳文輝，張道兵，等. 基于馬爾科夫過程的混流裝配線緩沖區容量研究[J]. 中國機械工程, 2013, 24(18): 2524-2528.

[9] 孟凡力,談大龍,黃雪梅.裝配系統中緩沖區容量的研究[J]. 計算機集成制造系統，2005，11(11)：1609-1616.

[10] 秦永法, 趙明揚.具有AGV和AS/RS的裝配線物流系統分析[J]. 機械設計與制造, 2005(6): 166-168.

[11] 李修琳，魯建廈，柴國鐘，等. 基于混合遺傳算法的混流混合車間協同調度問題[J]. 中國機械工程, 2012, 23(8): 935-940.

*浙江省自然科學基金資助項目(LY12G01004)國家自然科學基金資助項目(51405450)

責任編輯鄭練

P92大口徑厚壁無縫鋼管再獲國家支持

2015年6月1日，在工業和信息化部舉行的2014年工業轉型升級強基工程合同簽約儀式上，中國兵器工業集團公司內蒙古北方重工業集團有限公司董事長、黨委書記李建平與工信部規劃司司長肖華正式簽訂國家強基工程《超超臨界火電機組P92大口徑厚壁無縫鋼管工程項目》合同書，北重集團獲國家支持資金4980萬元。北重集團生產的P92鋼管在力學性能、顯微組織、無損檢測等主要技術指標方面與國外先進產品基本相同，國產鋼管的工藝質量水平已經達到國際先進水平，部分指標甚至已經超過國際先進水平，能夠滿足不同標準體系的技術指標要求，完全可以替代進口P92鋼管使用。

——摘自中國兵器工業集團公司網

OptimizationofBufferCapacityforMixedModelAssemblyLinebasedonMarkovChain

CAO Zhenxin, E Shiju, JIAO Weidong, ZHOU Wu

(College of Engineering, Zhejiang Normal University, Jinhua 321004, China)

The buffer is introduced between each station in order to improve the reliability and the productivity of logistics system for the mixed assembly line. Buffer capacity is an important factor affecting the production line performance indicators. The type and structure are elaborated based on analyzing the buffer function. The working procedure of the material handling system with the automatic storage retrieval system and automated guided vehicle is built. The closed-loop queuing network model using is developed using queuing theory based on Markov process. The buffer capacity and the states of work station are analyzed. Examples of calculations show that the model and buffer settings are reasonable which could meet the requirements for the mixed assembly line logistics system.

Markov chain, mixed model assembly line, buffer capacity, queuing theory

TP 29

：A

曹振新(1976-)，男，博士，副教授，碩士生導師，主要從事工業工程與管理和計算機集成制造等方面的研究。

2014-12-09