基于新型線邊集成超市的周期性物料配送優化

周炳海,徐佳惠,彭 濤

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

0 引 言

物料配送(Part feeding)占車輛生產成本的20%～50%[1]。如何設計高效、合理的物料配送系統,對降低混流裝配線的生產成本具有重要意義。

許多國內外學者對傳統送料機制,即線邊儲料(Line stocking)和成套供料(Kitting)進行了廣泛的對比和研究[2,3],并指出不存在絕對的最優機制,應根據物料特性和實際生產環境選用不同送料機制才可有效降低系統配送總成本。近年來,研究焦點逐漸轉移為準時化配送策略[4,5],即采用物料超市(Supermarket)替代傳統的中心倉庫存放物料,通過對多載量小車等送料設備的調度[6]實現物料的小批量多頻次配送。為充分結合傳統線邊儲料、成套供料以及準時化配送策略的優勢,降低系統總運作成本,Boysen等[7]結合某德國汽車制造商的實際運營情況,提出并介紹了“線邊集成超市”(Line-integrated supermarkets)的概念,但未對具體的物料配送調度問題進行深入研究。Battini等[8]對廠內物流進行研究時也簡單提及了“魚骨型物流超市”(Fish bone supermarkets),即線邊集成超市,并說明了其可行性和潛在價值。

雖然基于線邊集成超市的物料配送有效利用當前送料機制的優勢、降低系統成本,但是目前尚未發現其他相關研究。為此,本文引入線邊集成超市的概念,研究送料工人與工位之間的合理配置問題,并對物料配送進行調度決策,以最小化包括工人固定成本和物料配送成本的系統總運作成本。對于小規模問題,結合問題的引理、定理建立嵌套啟發式動態規劃方法獲取精確解,并構建改進型和聲搜索算法(Modified harmony search algorithm,MHSA)求中大規模問題的滿意解。

1 問題描述

如圖1所示,為有效降低物料的線邊庫存,送料工人采用準時化順序供應(Just-in-sequence,JIS),即根據實際生產計劃和裝配情況準備并配送物料到對應工位,并按需按序放置于JIS料箱,以滿足裝配需求。為明確物料配送任務、有效管理送料工人,本文將物料配送調度分解成兩個子問題:①送料工人與工位的分配問題P1,即確定各送料工人負責工位;②周期性配送問題P2,即確定送料工人的周期性配送時間間隔。

圖1 線邊集成超市物料配送系統Fig.1 Part feeding system with line-integrated supermarkets

為有效描述該配送系統,作如下假設:①采用節拍時間作為基本時間單位;②裝配線不允許發生缺料;③一個送料工人負責一個或多個連續工位;④送料工人對所負責的工位進行周期性配送;⑤送料工人搬運能力有限;⑥送料工人一旦從線邊超市出發送料,必須配送完所有物料后返回;⑦每個工位設一個JIS料箱,存放物料,其容量有限;⑧送料工人揀料、卸料時間,以及從線邊超市到工位的行走時間均為定值;⑨每個工位僅裝配一類物料,且僅考慮每個生產節拍內的物料需求量;⑩生產系統為一個相對穩定的系統,不考慮不確定因素。

結合以上描述和假設,定義如下問題參數和決策變量,并建立數學模型。

(1)參數與變量

設S為裝配工位集合,s＝1,2,…,;W為送料工人集合,w＝1,2,…,;P為待裝配車輛總數,p＝1,2,…,P;T為系統生產節拍總數,t＝1,2,…,T;ct為系統節拍時間;B s為工位s處JIS料箱的容量;為工位s在第t個生產節拍所需物料量;wt為送料工人從線邊超市到工位的行走時間;st為送料工人在兩連續工位間的行走時間;at w為送料工人w每次的分揀、裝卸物料時間;C w為第w個送料工人的搬運能力;δw為第w個送料工人負責的最左邊工位編號;T w為第w個送料工人的周期性配送時間間隔,且T w≥1;D w為第w個送料工人的單次送料時長,且D w＝at w＋2·[wt＋st·(δw＋1－1－δw)];R w為第w個送料工人的送料次數,r＝1,2,…,R w;為第w個送料工人第r次配送的物料量;F w為第w個送料工人的固定成本;u為單位物料單位時間的搬運成本。

(2)數學模型

式(1)～(4)以最小化送料工人數為目標求解問題P1。其中,式(2)(3)表示各送料工人至少負責1個工位,且負責的工位不重復。式(4)為終止條件,均為虛擬值,不計入目標函數。此外,為有效應對問題P2,即減少物料配送等非增值活動的成本,建立以最小化單位物料配送的最大時間為目標的數學模型,如式(5)所示。式(6)(7)為配送量約束,即應滿足裝配過程不發生缺料。式(8)(9)分別為送料工人能力和JIS料箱容量約束。式(10)表明送料工人周期性配送時間間隔不得小于其固定的送料時長。

顯然,兩個子問題相互關聯:工位分配問題確定送料工人數和負責工位(W,δw),其作為問題P2的已知參數;相應地,只有求出每個工人的周期性配送時間才可明確工人數是否滿足要求,工位分配問題是否合理、可行?；趦烧叩年P聯性,結合式(1)(5)建立總目標函數(11)進行求解,其代表最小化包括工人固定成本和物料配送成本的系統總成本,式中“?”表示相應目標函數的最優解。函數(11)應滿足約束(2)(3)(4)、(6)～(10)。

2 算法構建

2.1 引理和定理

引理1 若送料工人w負責工位m,…,n的物料配送,且周期性配送時間和次數分別為T w和R w,則當時,Z2(T w)取最小值。

證明 若工人w負責工位m,…,n,則D w為定值。取最小值時,則Z(T)取得最小值。根據2w數學不等式性質可得:

定理2 送料工人w負責工位m,…,n,若存在可行周期性配送時間,對應配送次數X、Y,且a i、b j(i＝1,2,…,X;j＝1,2,…,Y)分別表示每次配送的量,則當,即X＜Y時,。

證明 根據引理1可得:

2.2 嵌套啟發式動態規劃算法

根據模型P1,需決策每個工人w負責的最左邊工位,繼而可知其負責的所有工位。故將決策過程劃分為個階段,每階段表示一個工位,i＝1,2,…,為終止階段。每階段的狀態亦為i,表示工人負責的最左邊工位,從狀態i到狀態j,即表示w負責工位i,…,(j－1),從1到依次進行前向遞歸,并計算狀態轉移對應目標函數值的變化:

式中:“?”為i,…,(j－1)工位周期性配送問題最優解。

用H(i)表示從工位1到i的最優目標函數值,則:

Step1 計算工位s(s＝i,…,j－1)最少配送次數:,取。

Step2 計算該子區域i,…,(j－1)最少配送次數:。

Step3 根據Step1和Step2確定w最少配送次數。

Step4 計算w配送次數,相應周期時間。

2.3 改進型和聲搜索算法

為了有效求解中、大規模問題,引入和聲搜索算法(Harmony search,HS),該算法原理簡單、控制參數少、收斂速度快,且文獻[9]證明了其解決離散問題時的全局收斂性,已成功應用于各類非線性優化問題[10]。然而,HS算法仍存在搜索后期收斂較慢、局部探索能力差、易陷入局部最優等缺陷。因此,提出了一種改進型和聲搜索算法MHSA,基本流程如下。

Step1 參數初始化。給定和聲記憶庫大小HMS、精度ε、最大迭代次數SNI及參數HMCR,PAR。

Step2 初始化和聲記憶庫。結合約束(2)(3)(4),隨機產生H MS個和聲,存入記憶庫。

Step3 按照和聲長度(即所需工人數)將和聲記憶庫分解成為若干個子和聲記憶庫。

Step4 對于每個子和聲記憶庫,基于HMCR、PAR進行即興創作,產生新的和聲向量。

Step5 更新子和聲記憶庫,即判斷新和聲向量是否優于當前子和聲記憶庫中最差和聲。

Step6 判斷子和聲記憶庫終止準則,若當前迭代次數sk大于最大迭代次數SNI,則合并所有子和聲記憶庫構成新的和聲記憶庫,否則重復Step4、Step5。

Step7 對記憶庫最差和聲向量X w1、X w2進行交叉、變異形成新和聲X′、X″,并更新和聲記憶庫。

Step8 判斷終止準則。若任兩個和聲對應目標值之差均小于精度ε,終止算法,否則重復Step3～Step7。

2.3.1和聲編碼方式

和聲向量X i采用變長雙層編碼方式[11],i＝1,2,…,HMS。由編碼長度可得所需送料工人數,即。第一層為工位層,代表各工人負責的最左邊工位δw。根據約束(2)(3)(4)可知其以1開始,以結束,且升序排列。第二層為時間層,代表工人配送時間間隔T w。圖2所示為以上算例的兩個和聲編碼示意圖。其中,X1即為最優解,可行解X2表示由5個工人分別負責1個工位,且其對應配送時間間隔分別為5、5、2、2、5個周期。

圖2 和聲編碼示意圖Fig.2 Diagram of encoded mode for harmony vector

2.3.2 初始化和聲記憶庫

給定S,則和聲的最大長度;根據定理1計算最少送料工人數,則。因此,和聲X i(i＝1,2,…,H MS)的長度范圍為[Lenmin,Lenmax]。分別用1,2表示和聲X i第一、二層編碼的第j列,。為生成初始可行解,結合約束(2)(3)(4)隨機生成HMS個和聲,?i＝1,2,…,H MS,和聲X i滿足:

根據和聲X i計算對應函數值f(X i),一并存入和聲記憶庫HM,即實現和聲記憶庫的初始化。

2.3.3 子和聲記憶庫操作

Chen等[12]指出,對于中等規模的問題,通常采用較小的HM優于較大的HM,即應該設置較小的H MS。因此,本文將HM按照和聲長度Len i劃分成大小不同的若干子和聲記憶庫Sub-HM。對于每個Sub-HM,為防止算法過早收斂、陷入局部最優,結合參數H MCR、PAR等創作新和聲,并不斷更新Sub-HM。

對于每個Sub-HM,新和聲Xnew以HMCR概率繼承現有Sub-HM中和聲,并以PAR概率進行微調。由于編碼的特殊性,結合定理3,對Xnew進行鄰域搜索。新和聲Xnew以(1－HMCR)的概率進行創作,不同于HS中按定義域隨機生成,本文采用輪盤賭算法從Sub-HM中選取兩個和聲X a、X b,并引入比例系數α生成新和聲元素1。為進一步加快算法收斂速度,求得較優解,沿用2.2中的啟發式算法求2。最后,計算新和聲Xnew和最差和聲Xworst對應目標函數值f(Xnew)和f(Xworst),并比較、更新Sub-HM。

2.3.4 更新和聲記憶庫

為進一步增加和聲多樣性并改善解質量,對于重組后HM中的和聲進行交叉、變異操作,具體流程如下。

(1)交叉操作

給定交叉概率P c,根據

選取兩個和聲X w1,X w2,若rand(0,1)＜P c,則:

Step1 隨機選取X w1、X w2的交叉點C1、C2,記,則新和聲X′、X″長度分別為L′＝C1＋L2－C2,L″＝C2＋L1－C1。

Step2 若1,轉Step3,否則轉Step4。

Step3對X w1、X w2在C1、C2處交叉,結合2.2節中Step1～Step 5求相應2X′j、2X″j,形成新和聲X′、X″,并求f(X′),f(X″)。

Step4 重新生成交叉點C2,并轉Step3。

Step5 和聲X w1、X w2交叉結束。

如圖3所示,分別選取X1、X2(L1＝3,L2＝6)的交叉點C1＝2,C2＝4,按照Step2和Step3進行交叉,并重新計算周期性配送時間,得到兩個長度分別為L′1＝4,L′2＝5的新和聲X1′、X2′。

圖3 交叉操作示意圖Fig.3 Diagram of crossover operation

(2)變異操作

和聲X w1、X w2經交叉后變為X′、X″,若f(X′)＜f(X w1)f(X″)＜f(X w2),則X w1←X′,X w2←X″;否則記Xchng為待變異和聲,引入變異概率P m,若rand(0,1)＜P m,進行如下操作:

Step2 結合約束(3)進行隨機變異:1,并根據2.3.3節中Step1～Step5求相應2,形成鄰域解Xchng。

Step3 計算f(Xchng),若f(Xchng)＜f(X w1),則X w1←Xchng,否則轉Step1。

Step4 和聲Xchng變異結束。

3 仿真實驗與分析

為評價該線邊集成超市物料配送系統及MHSA算法,結合文獻[5]生成如下實驗參數。該混流裝配線生產多種車型,工位s(s∈S)在周期t＝1,2,…,T所需物料,即采用(0,3)的均勻分布,表示就近取整,同理。系統節拍時間ct＝100s,且st＝0.1ct,wt＝0.2ct,at w＝0.3ct。分別取不同的和T組合,每種組合運行20次并進行統計分析。

3.1 有效性驗證

為驗證MHSA的有效性,將其與嵌套啟發式動態規劃算法進行比較,其計算機運行時限設置為1800 s,若求解超過時限,即視為中大規模問題,無法求得最優解。表1為小規模問題參數和實驗結果。其中,MHSA方法的相關參數如HMCR、PAR參見文獻[9]推薦值,初始和聲記憶庫大小為HMS＝2·|S|。動態規劃方法求得最優解,MHSA運行20次后取平均值,由表1可知,其與最優解的偏差Gap均小于5%,即可得到滿意解,驗證了該算法的有效性。同時,隨著問題規模擴大,偏差減小,表明隨著問題規模擴大,MHSA的記憶庫擴大,和聲多樣性增加,避免局部最優,因此,MHSA適用于求解中大規模的問題。

表1 小規模問題的實驗參數和結果Table 1 Parameters and results of small scale problems

3.2 算法比較

3.2.1 比較MHSA、ACO和SA

MHSA模擬音樂家創作優美和聲的過程,將其與其他模擬自然現象的優化算法進行比較,包括蟻群算法(Ant colony optimization,ACO)和模擬退火算法(Simulated annealing,SA)。問題規模和結果如表2所示。

表2 MHSA、ACO和SA的結果比較Table 2 Experimental results of MHSA,ACO&SA

由表2可知,隨著問題規模T和的擴大,MHSA算法的尋優能力優于ACO和SA等優化算法。尤其在較大規模情況下(T≥100,),ACO和SA與MHSA的目標函數值Gap均超過5%,MHSA算法深度的搜索能力更為突出,一定程度上驗證了MHSA算法處理中大規模問題時的有效性。

圖4 算法收斂性能比較Fig.4 Convergence performance of algorithms

圖4(a)(b)分別為MHSA、ACO和SA算法在T＝20,時的收斂曲線。由圖4(a)可知,在問題規模較小時,MHSA、ACO均能快速收斂;而隨著問題規模的擴大,本文提出的子和聲記憶庫操作加快算法的收斂速度,結合交叉變異等操作擴大鄰域搜索范圍,避免陷入局部最優,使MHSA明顯優于ACO和SA算法,如圖4(b)所示。

3.2.2 比較MHSA、IHS、GHS和NGHS

為進一步說明MHSA算法可有效避免或減少HS算法早熟收斂、易陷入局部最優的缺點,如圖5所示,將其與目前引用較廣泛的IHS[13]、GHS[14]和NGHS[15]進行對比。

圖5 MHSA、IHS、GHS和NGHS結果比較Fig.5 Experimental results of MHSA,IHS,GHSand NGHS

3.2.3 參數分析

為最小化線邊超市供料系統的運行成本,必須找到一個平衡點,使送料工人的雇傭成本與物料配送成本之和最小,根據式(11)可知,其受參數F w和u影響。令問題規模T＝20,,參數u＝1保持不變,F w分別取0,100,200,…,1000,則F w/u對目標函數值的影響如圖6所示。由圖可知,隨著F w/u線性遞增,對應目標函數值也基本呈線性遞增,斜率約為7.54,即所需的平均送料工人數;截距約為6028.54,即物料配送成本。

圖6 F w/u對目標函數值的影響Fig.6 Effect of F w/u on objectives

根據以上分析可知,F w/u的變化主要影響送料工人數量。取F w/u∈[0,3000],令T＝20,分別取為20,40,…,120,則相應的工人數隨F w/u變化的情況如圖7所示,其中,圖7(b)為圖7(a)在YOZ平面投影。由圖7可知,當生產周期數T一定時,隨著增加,所需工人數增加。對任意給定隨F w/u的增加而減少,且減少到一定程度(約|S|/2,即平均1個工人負責2個工位)后保持不變,即得到該T、|S|情形下滿足所有約束條件的最小工人數,此時增加F w/u僅對目標函數有影響,對無影響。

圖7 F w/u對送料工人數量的影響Fig.7 Effect of F w/u on number of logistics operators

4 結束語

本文將新型線邊集成超市物料配送分解為工位分配和周期性配送調度問題進行研究,并以最小化送料工人固定成本和物料的配送成本為目標建立數學模型進行求解。針對該關聯問題,提出相應的引理、定理,并建立嵌套啟發式動態規劃方法以獲取小規模問題的精確解;對于中大規模問題,構建了改進型和聲搜索算法(MHSA)獲取滿意解。最后,通過仿真實驗與其他模擬算法或改進算法進行對比,驗證了MHSA的可行性和有效性。后續為提升工人的利用率,將對一組送料工人共同負責一個裝配區域的情況進行研究。

[1]Lau H Y K,Woo S O.An agent-based dynamic routing strategy for automated material handling systems[J].International Journal of Computer Integrated Manufacturing,2008,21(3):269-288.

[2]Sali M,Sahin E,Patchong A.An empirical assessment of the performances of three line feeding modes used in the automotive sector:line stocking vs.kitting vs.sequencing[J].International Journal of Production Research,2015,53(5):1439-1459.

[3]Caputo A C,Pelagagge P M,Salini P.A decision model for selecting parts feeding policies in assembly lines[J].Industrial Management&Data Systems,2015,115(6):974-1003.

[4]Battini D,Boysen N,Emde S.Just-in-time supermarkets for part supply in the automobile industry[J].Journal of Management Control,2013,24(2):209-217.

[5]Boysen N,Emde S,Hoeck M,et al.Part logistics in the automotive industry:decision problems,literature review and research agenda[J].European Journal of Operational Research,2015,242(1):107-120.

[6]周炳海,徐佳惠.基于支持向量機的多載量小車實時調度[J].吉林大學學報:工學版,2016,46(6):2027-2033.Zhou Bing-hai,Xu Jia-hui.SVM-based real-time scheduling approach of multi-load carriers[J].Journal of Jilin University(Engineering and Technology Edition),2016,46(6):2027-2033.

[7]Boysen N,Emde S.Scheduling the part supply of mixed-model assembly lines in line-integrated supermarkets[J].European Journal of Operational Research,2014,239(3):820-829.

[8]Battini D,Gamberi M,Persona A,et al.Part-feeding with supermarket in assembly systems:transportation mode selection model and multi-scenario analysis[J].Assembly Automation,2015,35(1):149-159.

[9]趙玉新,Yang X S,劉利強.新興元啟發式優化方法[M].北京:科學出版社,2013:201,202,216-218.

[10]Manjarres D,Landa-Torres I,Gil-Lopez S,et al.A survey on applications of the harmony search algorithm[J].Engineering Applications of Artificial Intelligence,2013,26(8):1818-1831.

[11]Zhou B,Peng T.Scheduling the in-house logistics distribution for automotive assembly lines with justin-time principles[J].Assembly Automation,2017,37(1):51-63.

[12]Chen J,Pan Q K,Wang L,et al.A hybrid dynamic harmony search algorithm for identical parallel machines scheduling[J].Engineering Optimization,2012,44(2):209-224.

[13]Mahdavi M,Fesanghary M,Damangir E.An improved harmony search algorithm for solving optimization problems[J].Applied Mathematics and Computation,2007,188(2):1567-1579.

[14]Omran M G H,Mahdavi M.Global-best harmony search[J].Applied Mathematics and Computation,2008,198(2):643-656.

[15]Zou D,Gao L,Li S,et al.Solving 0-1 knapsack problem by a novel global harmony search algorithm[J].Applied Soft Computing,2011,11(2):1556-1564.