李延輝，孫　輝

(東南大學(xué)，　江蘇 南京 211189)

引　言

作為“豐田生產(chǎn)系統(tǒng)”的重要部分，平準(zhǔn)化排序法(level scheduling)得到了廣泛的關(guān)注和應(yīng)用[1]。這種排序方法旨在尋求滿足準(zhǔn)時制生產(chǎn)方式(JIT)要求的生產(chǎn)序列，使總裝車間各工作站上的物料消耗速度盡量保持穩(wěn)定，以避免物料短缺或庫存水平過高。根據(jù)不同的目標(biāo)，平準(zhǔn)化排序法又可分為基于零部件的排序法、基于工作負(fù)荷的排序法和基于產(chǎn)品的排序法[2]。將產(chǎn)品作為平準(zhǔn)化對象，要求不同類型的產(chǎn)品均勻分布于生產(chǎn)序列中，即基于產(chǎn)品的平準(zhǔn)化排序。

一個典型的汽車混合流水裝配系統(tǒng)包含車身車間、涂裝車間和總裝車間。不同車間對產(chǎn)品的投產(chǎn)順序有不同的偏好，如涂裝車間希望同色車輛連續(xù)排布以減少清洗噴頭造成的切換成本[3]；而總裝車間則希望產(chǎn)品序列有利于實(shí)現(xiàn)物料用量平準(zhǔn)化[4]。通常來自涂裝車間的車輛序列無法滿足下游總裝車間的生產(chǎn)要求，因此需要主動對來自上游的序列進(jìn)行調(diào)整[5]。在實(shí)際生產(chǎn)中，線性緩沖區(qū)(selectivity bank)投資成本低而重排序效果好，因而在汽車制造廠被廣泛使用。

本文研究如何使用線性緩沖區(qū)對來自涂裝車間的車輛序列進(jìn)行重排，以滿足總裝車間基于產(chǎn)品的平準(zhǔn)化排序目標(biāo)的要求。盡管使用線性緩沖區(qū)進(jìn)行重排序的研究已有不少，但絕大多數(shù)研究都集中在涂裝車間前的重排序問題上[6]。只有文獻(xiàn)[7]在總裝車間前進(jìn)行重排序，目標(biāo)是最小化各工作站上的總作業(yè)負(fù)荷超載。所有這些重排序研究都是基于傳統(tǒng)的重排序思路。和生產(chǎn)物流方向一致，傳統(tǒng)的重排序方法通常先確定上游車輛在緩沖區(qū)中的排布方案，再確定如何將緩沖區(qū)內(nèi)的車輛釋放至下游[5,8]。

文中提出一種以下游釋放順序為導(dǎo)向的重排序思路，即先確定上游車輛離開緩沖區(qū)的釋放順序，然后確定車輛在緩沖區(qū)內(nèi)的排布方式?；诖怂悸?，提出了3種重排序方法，最后通過算例驗證了方法的有效性和先進(jìn)性。

1　汽車總裝車間平準(zhǔn)化重排序問題

1.1　問題描述

圖1所示為一個4車道6車位的線性緩沖區(qū)。到達(dá)緩沖區(qū)的上游車輛按順序選擇車道進(jìn)入，同時緩沖區(qū)另一端不同車道上的車輛被選擇釋放至下游。這樣，車輛經(jīng)過緩沖區(qū)后便可以實(shí)現(xiàn)序列重排。

圖1　線性緩沖區(qū)示意圖

已知緩沖區(qū)有m條車道，每條車道有f個車位，初始狀態(tài)為空?？紤]來自上游涂裝車間的車輛序列，序列長度為T(T=mf)，且序列中每輛車的車型已知。每輛車在上游序列中的位置i(i=1,…,T)構(gòu)成序列π={1,…,T}。定義一個雙射函數(shù)σ∶{1,…,T}→{1,…,T}，表示重排序后車輛i在下游序列中的位置，則重排后對應(yīng)的車輛位置序列π′={σ(1),…,σ(T)}。若上游車輛序列π={1,2,3}，存在函數(shù)σ，使得σ(1)=2、σ(2)=3、σ(3)=1，則重排后下游車輛序列為π′={2,3,1}。本文所研究的問題是如何利用緩沖區(qū)對上游序列進(jìn)行調(diào)整，使得下游序列對應(yīng)的平準(zhǔn)化排序目標(biāo)值最小。

1.2　數(shù)學(xué)模型

數(shù)字模型的參數(shù)和變量如表1所示。

表1　參數(shù)和變量

根據(jù)問題描述和表1內(nèi)的參數(shù)和變量，本文所研究的汽車總裝車間平準(zhǔn)化重排序問題可用以下整數(shù)規(guī)劃模型來表示：

min：

(1)

s.t.：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

zi,j≤ui,j≤fzi,j,
i=0,…,T-1；j=i+1,…,T

(10)

(11)

i=0, …,T-1；j=i+1, …,T

(12)

zi,j∈{0,1}，i,j=0, …,T；i

(13)

ek,i∈{0,1},k,i=1, …,T

(14)

平準(zhǔn)化重排序的目標(biāo)如式(1)所示，即最小化序列內(nèi)所有車型實(shí)際生產(chǎn)率與理想生產(chǎn)率偏差的總平方和。式(2)～式(14)為約束條件。式(2)和式(3)共同規(guī)定了上下游序列車輛之間一一對應(yīng)的關(guān)系。式(4)要求每一輛車停放在一條車道的最前端，或所在車道的前方相鄰位置都有一輛上游位置靠前的車。式(5)規(guī)定了每輛車后相鄰車位最多只能安排給一輛上游位置靠后的車輛停放。式(6)表示車輛所占車道數(shù)不得超過緩沖區(qū)總車道數(shù)。式(7)給出了車輛占用車道數(shù)的下界。式(8)和式(9)給出了ui,j的遞推關(guān)系，使ui,j的值等于車輛i后同一車道內(nèi)的車輛數(shù)。式(10)表示緩沖區(qū)每一車道所放置的車輛數(shù)不超過車道容量。式(11)表示上游序列所有車輛都被放置在緩沖區(qū)中。式(12)表示車輛在進(jìn)出緩沖區(qū)時滿足先進(jìn)先出規(guī)則。式(13)和式(14)表示zi,j和ek,i是0-1整數(shù)變量。

2　以下游釋放順序為導(dǎo)向的重排序方法

和平準(zhǔn)化排序問題相同，平準(zhǔn)化重排序問題也是一個NP難問題。這樣，在可接受的時間范圍內(nèi)無法采用精確算法求得大規(guī)模算例的最優(yōu)解，因此考慮采用啟發(fā)式算法快速近似求解?；谝韵掠吾尫彭樞驗閷?dǎo)向的重排序思路，本文提出了3種重排序方法，即分組重排序、滾動重排序和基于蟻群優(yōu)化算法的重排序。

2.1　基于貪婪規(guī)則的分組重排序方法

首先將上游車輛序列分為連續(xù)的f個子序列(每個子序列中有m輛車)，然后再依次確定每一子序列內(nèi)所有車輛在下游序列中的位置。由于每組(即每一子序列)的車輛數(shù)和車道數(shù)相等，因此各組車輛可以依次占據(jù)緩沖區(qū)中同一列上的所有車位，這樣可以保證所有車輛均能按照計劃下游序列順利釋放。

在對一個子序列進(jìn)行重排序時，假設(shè)下游序列中已有K輛車，按照以下步驟從該子序列中選擇第K+1輛車：

1)計算當(dāng)前下游序列因加入車輛t(t=1,…,m)而導(dǎo)致的目標(biāo)函數(shù)增量Δt：

(K+1)rp)2

(15)

式中：t是車輛在當(dāng)前子序列中的位置；i是車輛在上游序列中的位置。

2)選取Δt最小的車輛作為第K+1輛車。如果多輛車的Δt值相等，則按等概率原則選擇其中一輛。

假設(shè)上游車輛序列π={1,…,9}，緩沖區(qū)容量為3×3。將該序列分成π1={1,2,3}、π2={4,5,6}、π3={7,8,9} 3個子序列。按照分組重排序方法依次對每個子序列進(jìn)行重排序，得到對應(yīng)的3個子序列π1′={3,1,2}、π2′={6,4,5}、π3′={8,9,7}。車輛在緩沖區(qū)內(nèi)的排布和下游釋放序列如圖2所示。圖中每輛車的第一個數(shù)字表示該輛車的上游序列位置，而括號內(nèi)的數(shù)字為該輛車的下游序列位置。

圖2　分組重排序示例

2.2　基于貪婪規(guī)則的滾動重排序方法

在以上分組重排法中使用滾動計劃區(qū)間，即成為滾動重排序。該方法采用一個長度為m的滾動計劃區(qū)間，在每一計劃區(qū)間內(nèi)根據(jù)式(15)連續(xù)選擇下游釋放車輛，直到緊鄰緩沖區(qū)的那輛車被選擇，然后計劃區(qū)間向后滾動一個位置。下一輪重排序在新的計劃區(qū)間內(nèi)進(jìn)行，直到所有車輛在下游序列中的位置都得到確定。如圖3所示，假設(shè)緩沖區(qū)有4條車道，當(dāng)前計劃區(qū)間內(nèi)第1和第3輛車分別被確定在下游第2和第1個位置釋放，下一計劃區(qū)間為上游序列第2輛車至第5輛車。

圖3　滾動計劃區(qū)間

為確保所得到的下游理想車輛序列能夠?qū)崿F(xiàn)，采用文獻(xiàn)[5]中的堆棧規(guī)則確定車輛在緩沖區(qū)內(nèi)的位置：假設(shè)下游序列π′={σ(1),…,σ(T)}，將滿足不等式(l-1)m+1≤σ(i)≤lm的m輛車放置在緩沖區(qū)第l列(l=1,…,f)的m個車位上。

2.3　基于蟻群優(yōu)化算法的重排序方法

蟻群優(yōu)化算法最初由Dorigo提出，是模擬螞蟻覓食過程中利用生物信息素與群體中的其他螞蟻交換信息，從而獲取較短覓食路徑(即最優(yōu)或近優(yōu)解)的優(yōu)化算法[9]。由于蟻群算法特別適合于組合優(yōu)化問題如旅行推銷商問題和生產(chǎn)計劃問題[9-10]，本文提出了基于蟻群算法的兩階段重排序方法。第一階段采用蟻群算法構(gòu)建一個完整的下游理想序列，第二階段以下游理想序列為導(dǎo)向，確定上游車輛在緩沖區(qū)內(nèi)的排布方案。

2.3.1蟻群優(yōu)化算法

下游車輛序列的構(gòu)建過程可以看作是人工螞蟻一步步選擇所經(jīng)車輛路徑的過程。因此，螞蟻經(jīng)過的完整車輛路徑就構(gòu)成了重排序問題的解。算法的基本思路如下：首先是信息素矩陣τ的初始化。τ中的元素τu,v定義在任意兩個車型u和v之間，為螞蟻在構(gòu)建解的過程中留下的累積信息素濃度，表示在車型u后選擇v的傾向程度。初始化時將所有元素設(shè)為一個很小的正數(shù)τ0，然后通過迭代搜索求解。每次迭代中，種群中的n只螞蟻先分別隨機(jī)選出下游序列的第一輛車，然后按照狀態(tài)轉(zhuǎn)移規(guī)則選擇后續(xù)車輛。這些螞蟻構(gòu)建解的過程是并行同步的，即所有螞蟻都選擇一輛車后才能開始下一輛車的選擇。另外，所有螞蟻前進(jìn)一步后，立刻進(jìn)行信息素的局部更新。當(dāng)所有螞蟻都完成序列構(gòu)建后，選出本次迭代的最優(yōu)序列S+，并與至今最優(yōu)序列S*比較。若S+優(yōu)于S*，則用S+替換S*。若S+與S*所對應(yīng)的目標(biāo)函數(shù)值相等，則保存S+作為另一至今最優(yōu)序列。然后進(jìn)行信息素的全局更新，完成本次迭代。重復(fù)迭代直至達(dá)到最大迭代次數(shù)tmax。注意，最后得到的最優(yōu)解序列可能不止一個。

以上所述蟻群優(yōu)化算法的路徑搜索過程總結(jié)如下：

初始化信息素矩陣τ，τi,j=τ0

FORt=1 TOtmax

FORant=1 TOn

螞蟻ant隨機(jī)選擇第一輛車

END FOR

FORk=2 TO序列長度T

FORant=1 TOn

按照狀態(tài)轉(zhuǎn)移規(guī)則選擇下游序列第k輛車

END FOR

FORant=1 TOn

信息素局部更新

END FOR

END FOR

FORant=1 TOn

計算螞蟻構(gòu)建序列的目標(biāo)函數(shù)值Zant

END FOR

計算當(dāng)前迭代最優(yōu)序列S+

更新至今最優(yōu)序列S*

信息素全局更新

END FOR

輸出所有全局最優(yōu)解

假設(shè)當(dāng)前序列中已有K輛車，最后一輛車型為u，螞蟻接下來選擇上游序列位置為j的車輛(車型為v)的可能性ηu,v,j根據(jù)下式計算：

(16)

式中：Δj為當(dāng)前序列中加入第j輛車所引起的目標(biāo)函數(shù)增量，按式(15)計算；α、β、和γ分別表示τu,v、Δj以及j的相對重要性?？梢钥闯觯浵亙A向于選擇信息素濃度較大且目標(biāo)函數(shù)增量較小的車型。另外，為方便進(jìn)出緩沖區(qū)，上游序列中位置靠前的車輛也被優(yōu)先選擇。

螞蟻在車輛候選集C(尚未安排下游位置的所有車輛)中根據(jù)以下偽隨機(jī)規(guī)則選擇下一輛車：

(17)

式中：q為[0, 1]間的隨機(jī)數(shù)；q0為[0, 1]間的常數(shù)；J表示按照概率pu,v,j選擇下一車輛。pu,v,j的計算如下：

(18)

在一次迭代中，為避免螞蟻重復(fù)構(gòu)建相同的序列，當(dāng)所有螞蟻前行一步(即選擇一輛車)后，每只螞蟻經(jīng)過路徑的邊上的信息素都要按照下式進(jìn)行局部更新：

τu,v=(1-ρ1)τu,v+ρ1τ0

(19)

式中：ρ1表示信息素的蒸發(fā)率且0<ρ1<1；τ0為信息素初始值。

在一次迭代完成后，對全局最優(yōu)路徑上的信息素按下式進(jìn)行全局更新：

(20)

式中：ρ2表示信息素的蒸發(fā)率且0<ρ2<1；Q為常數(shù)；Zant為螞蟻ant找到的最優(yōu)路徑所對應(yīng)的目標(biāo)函數(shù)值。

2.3.2確定車輛在緩沖區(qū)內(nèi)位置

基于第一階段得到的下游理想序列，根據(jù)以下規(guī)則引導(dǎo)上游車輛依次進(jìn)入緩沖區(qū)：

1)選擇非空車道。假設(shè)待進(jìn)入車輛為i，某非空車道最后一輛車為j，i可以進(jìn)入這條車道的必要條件是σ(i)>σ(j)，否則i無法在j之前釋放。當(dāng)有多個備選車道時，選擇σ(i)-σ(j)最小的車道。

2)任選一條空車道進(jìn)入。

如果所有車輛都可按照上述規(guī)則選擇車道進(jìn)入，則計劃理想序列可以實(shí)現(xiàn)，該序列即為最終重排序列。反之，如果某車輛按上述規(guī)則無法找到可選車道，則說明理想序列無法順利實(shí)現(xiàn)。如圖4所示，下游理想序列π′={3,6,2,5,4,1}。按上述規(guī)則，上游前4輛車進(jìn)入緩沖區(qū)后，第5輛車無可選車道。此時可以通過下述交換下游序列位置的方法，對原理想序列進(jìn)行適當(dāng)調(diào)整，以使所有車輛能夠順利進(jìn)入緩沖區(qū)。

圖4　兩兩交換下游序列位置

假設(shè)待進(jìn)入車輛在上游序列π中位置為i，緩沖區(qū)中所有滿足σ(i)<σ(j)的車輛j(j∈π)構(gòu)成待交換車輛的候選集。具體的交換過程如下：

1)兩兩交換車輛i與候選集內(nèi)任一車輛(如車輛j)的下游序列位置σ(i)和σ(j)，保持其他車輛位置不變，計算交換后序列的目標(biāo)函數(shù)值。按照目標(biāo)值由小到大的順序排列待交換車輛，目標(biāo)值相等的車輛則按照σ(j)由大到小的順序排列。

2)依次選擇候選集中的車輛進(jìn)行試交換。如果試交換后能夠解決當(dāng)前阻塞問題，則車輛i進(jìn)入緩沖區(qū)。如果所有試交換都不能解決阻塞問題，執(zhí)行步驟3。

3)選擇候選集內(nèi)第一輛車交換其下游序列位置，然后轉(zhuǎn)至步驟1，重復(fù)下一次交換過程，直到車輛i能夠順利進(jìn)入緩沖區(qū)。

圖4中上游第5輛車無可選車道，此時第2輛和第4輛車為候選交換車輛。交換車輛5和2后的新序列π′={3,4,2,5,6,1}，目標(biāo)函數(shù)值為3.72，而交換車輛5和4之后的新序列π′={3,6,2,4,5,1}，目標(biāo)函數(shù)值為2.39，因此選擇車輛5和4的交換。可以看出，交換后阻塞問題解決，因此交換有效。此后，當(dāng)?shù)?輛車進(jìn)入緩沖區(qū)時，所有緩沖區(qū)內(nèi)的車輛構(gòu)成交換候選集。按照以上交換規(guī)則最終選擇交換車輛2和6。由于對原下游理想序列進(jìn)行了微調(diào)，最終得到的下游理想序列目標(biāo)函數(shù)值2.39略高于原理想序列目標(biāo)函數(shù)值1.72。

3　算例分析與驗證

通過設(shè)計算例，分析驗證以上3種求解算法的性能。在實(shí)際生產(chǎn)中，考慮到基礎(chǔ)建設(shè)成本、庫存成本以及運(yùn)行效率，緩沖區(qū)的規(guī)模都不會很大，常見的線性緩沖區(qū)容量一般為30至100輛車。因此設(shè)計大、小兩種規(guī)模的緩沖區(qū)，容量分別為6×5和7×8。上游序列中車型數(shù)取5或10。假設(shè)不同車型的市場占有率不同，即消費(fèi)者對不同車型的需求有差異。對于車型數(shù)5，每種車型在序列內(nèi)的累積分布概率D1= {0.3, 0.3, 0.2, 0.1, 0.1}。對于車型數(shù)10，每種車型的累積分布概率D2= {0.15, 0.15, 0.15, 0.15, 0.1, 0.1, 0.05, 0.05, 0.05, 0.05}。

考慮(30, 5,D1)、(30, 10,D2)、(56, 5,D1)、(56, 10,D2) 4個參數(shù)組合，每個參數(shù)組合隨機(jī)生成10個上游序列，共計40個算例。所有重排序算法程序均基于微軟公司的Visual Studio 2013平臺采用C++編寫，并在一臺CPU主頻為2.5 GHz，內(nèi)存為4 GB的個人電腦上運(yùn)行。使用以上3種重排序方法對所有40個算例進(jìn)行求解。在使用基于蟻群優(yōu)化算法的重排序方法時，經(jīng)過多次試驗，選擇效果最優(yōu)的一組參數(shù)進(jìn)行求解：α=1、β=0.1、γ=1、τ0=0.01、q0=0.3、ρ1=ρ2=0.1、Q=0.7、tmax=500。按照不同參數(shù)組合計算10個算例的平均目標(biāo)值和CPU運(yùn)算時間，見表2。

表2　3種重排序方法的求解結(jié)果

將3種重排序方法的結(jié)果繪制在圖5中?？梢钥闯觯谒袇?shù)組合中，3種重排序方法均有效降低了上游序列的目標(biāo)函數(shù)值，且方法一(分組重排序)、方法二(滾動重排序)和方法三(基于蟻群優(yōu)化算法的重排序)的重排序效果逐漸增強(qiáng)。主要原因可能在于方法三中的下游理想序列是在對上游序列進(jìn)行整體迭代尋優(yōu)的基礎(chǔ)上得到的。實(shí)際上，當(dāng)上游序列有5種車型時，方法三可以使上游序列的目標(biāo)值降低約70%；當(dāng)上游序列有10種車型時，方法三可以有效降低目標(biāo)值約58%。在求解時間方面，由于采用蟻群迭代優(yōu)化，方法三的求解時間最長，但相對于實(shí)際生產(chǎn)節(jié)拍(60 ～ 90 s)，該求解時間可以接受。方法一和方法二雖然求解質(zhì)量稍差，但所需時間少(小于0.1 s)。

圖5　3種重排序結(jié)果對比

3種重排序方法都有著不錯的重排序效果，方法三的重排效果最佳，而方法一和方法二所需求解時間最少。另外，3種重排序方法的重排效果隨著車型數(shù)的增加而略有下降。

4　結(jié)束語

本文針對以下游釋放順序為導(dǎo)向的汽車總裝車間平準(zhǔn)化重排序問題建立了0-1整數(shù)規(guī)劃模型，并提出了3種求解該問題的重排序方法，即分組重排序、滾動重排序、和基于蟻群優(yōu)化算法的重排序。算例分析和驗證表明，3種重排序法都可有效地對平準(zhǔn)化重排序問題進(jìn)行快速求解，其中基于蟻群優(yōu)化算法的重排序方法表現(xiàn)最優(yōu)。

參考文獻(xiàn)

[1]KUBIAK W. Minimizing variation of production rates in just-in-time systems: A survey[J]. European Journal of Operational Research, 1993, 66(3): 259-271.

[2]BOYSEN N, FLIEDNER M, SCHOLL A. Sequencing mixed-model assembly lines: Survey, classification and model critique[J]. European Journal of Operational Research, 2009, 192(2): 349-373.

[3]黃剛. 一類無緩沖區(qū)涂裝油漆排序問題[J]. 華中科技大學(xué)學(xué)報: 自然科學(xué)版, 2009, 36(7): 108-111.

[4]BARD J, SHTUB A, JOSHI S. Sequencing mixed-model assembly lines to level parts usage and minimize line length[J]. International Journal of Production Research, 2006, 32(10): 2431-2454.

[5]DING F, SUN H. Sequence alteration and restoration related to sequenced parts delivery on an automobile mixed-model assembly line with multiple departments[J]. International Journal of Production Research, 2004, 42(8): 1525-1543.

[6]BOYSEN N, SCHOLL A, WOPPERER N. Resequencing of mixed-model assembly lines: Survey and research agenda[J]. European Journal of Operational Research, 2012, 216(3): 594-604.

[7]BOYSEN N, ZENKER M. A decomposition approach for the car resequencing problem with selectivity banks[J]. Computers & Operations Research, 2013, 40(1): 98-108.

[8]CHOI W, SHIN H. A real-time sequence control system for the level production of the automobile assembly line[J]. Computers & Industrial Engineering, 1997, 33(3-4): 769-772.

[9]DORIGO M，STüTZLE T. Ant colony optimization[J]. Cambridge: The MIT Press, 2004.

[10]姚智騫. 基于蟻群算法的復(fù)合材料結(jié)構(gòu)件的返修計劃問題[J]. 電子機(jī)械工程, 2017, 33(2): 48-55.