李延輝，孫　輝

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

引　言

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

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

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

文中提出一種以下游釋放順序為導向的重排序思路，即先確定上游車輛離開緩沖區(qū)的釋放順序，然后確定車輛在緩沖區(qū)內的排布方式。基于此思路，提出了3種重排序方法，最后通過算例驗證了方法的有效性和先進性。

1　汽車總裝車間平準化重排序問題

1.1　問題描述

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

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

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

1.2　數學模型

數字模型的參數和變量如表1所示。

表1　參數和變量

根據問題描述和表1內的參數和變量，本文所研究的汽車總裝車間平準化重排序問題可用以下整數規(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)

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

2　以下游釋放順序為導向的重排序方法

和平準化排序問題相同，平準化重排序問題也是一個NP難問題。這樣，在可接受的時間范圍內無法采用精確算法求得大規(guī)模算例的最優(yōu)解，因此考慮采用啟發(fā)式算法快速近似求解?；谝韵掠吾尫彭樞驗閷虻闹嘏判蛩悸罚疚奶岢隽?種重排序方法，即分組重排序、滾動重排序和基于蟻群優(yōu)化算法的重排序。

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

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

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

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

(K+1)rp)2

(15)

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

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

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

圖2　分組重排序示例

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

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

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

為確保所得到的下游理想車輛序列能夠實現，采用文獻[5]中的堆棧規(guī)則確定車輛在緩沖區(qū)內的位置：假設下游序列π′={σ(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)化問題如旅行推銷商問題和生產計劃問題[9-10]，本文提出了基于蟻群算法的兩階段重排序方法。第一階段采用蟻群算法構建一個完整的下游理想序列，第二階段以下游理想序列為導向，確定上游車輛在緩沖區(qū)內的排布方案。

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

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

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

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

FORt=1 TOtmax

FORant=1 TOn

螞蟻ant隨機選擇第一輛車

END FOR

FORk=2 TO序列長度T

FORant=1 TOn

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

END FOR

FORant=1 TOn

信息素局部更新

END FOR

END FOR

FORant=1 TOn

計算螞蟻構建序列的目標函數值Zant

END FOR

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

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

信息素全局更新

END FOR

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

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

(16)

式中：Δj為當前序列中加入第j輛車所引起的目標函數增量，按式(15)計算；α、β、和γ分別表示τu,v、Δj以及j的相對重要性。可以看出，螞蟻傾向于選擇信息素濃度較大且目標函數增量較小的車型。另外，為方便進出緩沖區(qū)，上游序列中位置靠前的車輛也被優(yōu)先選擇。

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

(17)

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

(18)

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

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

(19)

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

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

(20)

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

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

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

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

2)任選一條空車道進入。

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

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

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

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

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

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

圖4中上游第5輛車無可選車道，此時第2輛和第4輛車為候選交換車輛。交換車輛5和2后的新序列π′={3,4,2,5,6,1}，目標函數值為3.72，而交換車輛5和4之后的新序列π′={3,6,2,4,5,1}，目標函數值為2.39，因此選擇車輛5和4的交換?？梢钥闯觯粨Q后阻塞問題解決，因此交換有效。此后，當第6輛車進入緩沖區(qū)時，所有緩沖區(qū)內的車輛構成交換候選集。按照以上交換規(guī)則最終選擇交換車輛2和6。由于對原下游理想序列進行了微調，最終得到的下游理想序列目標函數值2.39略高于原理想序列目標函數值1.72。

3　算例分析與驗證

通過設計算例，分析驗證以上3種求解算法的性能。在實際生產中，考慮到基礎建設成本、庫存成本以及運行效率，緩沖區(qū)的規(guī)模都不會很大，常見的線性緩沖區(qū)容量一般為30至100輛車。因此設計大、小兩種規(guī)模的緩沖區(qū)，容量分別為6×5和7×8。上游序列中車型數取5或10。假設不同車型的市場占有率不同，即消費者對不同車型的需求有差異。對于車型數5，每種車型在序列內的累積分布概率D1= {0.3, 0.3, 0.2, 0.1, 0.1}。對于車型數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個參數組合，每個參數組合隨機生成10個上游序列，共計40個算例。所有重排序算法程序均基于微軟公司的Visual Studio 2013平臺采用C++編寫，并在一臺CPU主頻為2.5 GHz，內存為4 GB的個人電腦上運行。使用以上3種重排序方法對所有40個算例進行求解。在使用基于蟻群優(yōu)化算法的重排序方法時，經過多次試驗，選擇效果最優(yōu)的一組參數進行求解：α=1、β=0.1、γ=1、τ0=0.01、q0=0.3、ρ1=ρ2=0.1、Q=0.7、tmax=500。按照不同參數組合計算10個算例的平均目標值和CPU運算時間，見表2。

表2　3種重排序方法的求解結果

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

圖5　3種重排序結果對比

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

4　結束語

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

參考文獻

[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]. 華中科技大學學報: 自然科學版, 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]姚智騫. 基于蟻群算法的復合材料結構件的返修計劃問題[J]. 電子機械工程, 2017, 33(2): 48-55.