陸志強， 曾 浚

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

飛機移動裝配生產(chǎn)線近年來開始逐步運用于飛機的生產(chǎn)，對于實現(xiàn)裝配的穩(wěn)定性、提高裝配效率具有重要的意義.在移動裝配生產(chǎn)線上，飛機以緩慢且平穩(wěn)的速度通過生產(chǎn)線，同時完成各工位所對應(yīng)的裝配作業(yè)，通過調(diào)整裝配線的速度以適應(yīng)生產(chǎn)節(jié)拍的變化.飛機裝配過程復(fù)雜，其所需的零部件種類繁多，物料配送延遲會導(dǎo)致整條裝配線的延期[1-2].飛機裝配作業(yè)所需物料的配送是實現(xiàn)移動生產(chǎn)線穩(wěn)定運作的關(guān)鍵環(huán)節(jié)，因此對其物流配送系統(tǒng)的調(diào)度也有極高要求.

飛機裝配作業(yè)所需物料主要分為三類：數(shù)量少、形狀不規(guī)則的大型結(jié)構(gòu)件，如發(fā)動機等；需求量較大、體積小的通用標準件，如螺釘螺母等；種類多、體積中等的裝配件，如儀表等.大型結(jié)構(gòu)件由于線邊存儲容量有限，采用準時化的方式進行配送；通用標準件由于需求量較大且易于暫存于線邊，采用線邊存儲(line stocking)的方式，且通過定期配送實現(xiàn)補貨；體積小、種類多的裝配件，由于零部件間組裝的相關(guān)性，采用齊套(kitting)的方式進行配送.本文主要考慮裝配件的供應(yīng)，采用標準料箱進行配送.

多載量小車(tow-train)以循環(huán)配送的方式將料箱配送至相應(yīng)的線邊空間，同時考慮將空箱回收至倉庫以減少對線邊空間的占用，從而提高線邊空間的利用率.為了以盡量少的運輸次數(shù)以滿足物料供應(yīng)需求，兼顧線邊空間約束，協(xié)調(diào)空箱的回收是關(guān)鍵.與一般裝配線物料配送問題的主要區(qū)別在于問題中引入了空箱回收因素，問題的優(yōu)化不僅需要安排裝配作業(yè)所需物料的配送時間，還必須同時對空箱的回收時間進行決策.因此，可認為是一類集物料配送與空箱回收問題于一體的聯(lián)合決策問題，本文將這一問題稱之為飛機移動生產(chǎn)線物料配送與空箱回收集成決策問題(integrated material delivery and container pickup problem for aircraft moving assembly line, IMDCP-AMAL).

現(xiàn)有文獻中關(guān)于汽車裝配線的物料配送問題的研究對于本文具有一定的借鑒意義.Boysen等[3]總結(jié)了混流裝配線的物料配送方式：循環(huán)(milkrun)配送和點對點配送.Souza 等[4]研究裝配線準時化物料配送問題，采用不同尺寸的料箱將物料點對點配送至裝配線，以最小化搬運費用和庫存費用為目標，并提出了具有貪婪隨機自適應(yīng)搜索的啟發(fā)式算法.Cunha等[5]研究裝配線的物料供應(yīng)問題，對物料的配送批次和頻次進行集成決策，基于提出的整數(shù)規(guī)劃方法并通過分支定界算法得到上界和下界.Emde等[6]研究了milkrun的配送方式下，以最小化線邊庫存水平為目標建立數(shù)學(xué)模型，證明其為NP完全問題，提出了基于分解算法的禁忌搜索算法.Boysen等[7]研究在配送能力約束下，從倉庫將物料組批配送至單一工位，以小車最少出行次數(shù)為目標函數(shù)建立數(shù)學(xué)模型，并證明其為NP-hard問題.Golz等[8]研究汽車混流裝配線配送問題，基于準時化原則，構(gòu)建了以最小化小車數(shù)量為目標函數(shù)的數(shù)學(xué)模型并設(shè)計了兩階段啟發(fā)式算法進行求解.Fathi等[9]拓展了裝配線的小車的調(diào)度問題，以最小化出行次數(shù)和線邊庫存為目標，建立了多目標混合整數(shù)規(guī)劃模型，并提出了改進的模擬退火算法用于解決實際問題.針對飛機移動生產(chǎn)線的物料配送問題，胡鑫銘等[10]引入了物料在飛機移動生產(chǎn)線線邊的存儲決策，構(gòu)建了物料配送與線邊存儲集成決策的數(shù)學(xué)模型，并設(shè)計了一種以免疫算法為框架的啟發(fā)式算法進行求解.朱永國等[11]考慮了飛機裝配工位物料需求時間的模糊化現(xiàn)象，建立了基于正態(tài)模糊時間窗約束的裝配物料配送路徑規(guī)劃的數(shù)學(xué)模型，并采用遺傳算法進行求解.

綜上所述，現(xiàn)有文獻研究的重點大多集中于物料配送問題，而缺少對物料配送與空箱回收相整合的研究.但在實際飛機移動裝配過程中，同一時刻可能存在多項并行裝配的作業(yè)，且裝配作業(yè)的時間長，因此線邊空間的占用率高.由于線邊空間的容量限制，物料配送的決策需要權(quán)衡線邊空間資源.通過空箱的回收釋放被占用的線邊空間，以協(xié)調(diào)配送的調(diào)度.若將物料配送和空箱回收分為兩階段進行獨立決策，則小車的運載能力不能得到充分利用.同時，由于線邊空間的約束，物料配送時間與空箱回收時間相互影響，因此通過聯(lián)合決策可以為物料配送和空箱回收提供更有效的協(xié)同性計劃，保證生產(chǎn)線的順暢運轉(zhuǎn)，具有較高的理論研究意義.

因此，在分析現(xiàn)有文獻中相關(guān)研究成果的基礎(chǔ)上，本文所提出的IMDCP-AMAL問題，基于飛機實際生產(chǎn)背景，以飛機移動生產(chǎn)線的一個裝配節(jié)拍為決策周期，在倉庫與線邊存儲區(qū)域間以循環(huán)運輸?shù)姆绞酵瓿裳b配所需物料與空箱的回收，建立以最小化小車出行次數(shù)為目標函數(shù)的數(shù)學(xué)模型，優(yōu)化決策物料與空箱的組批方式及相應(yīng)的配送/回收時間.針對上述問題，提出并建立相應(yīng)的數(shù)學(xué)模型，并設(shè)計了以遺傳算法為框架的啟發(fā)式算法(CHBG)對模型進行優(yōu)化求解.最后通過數(shù)值實驗驗證所提出算法在求解該問題時的有效性.

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

飛機移動生產(chǎn)線配送與回收集成問題，是通過優(yōu)化決策小車對各作業(yè)的物料配送時間、空箱回收時間，以協(xié)調(diào)各作業(yè)的物料的配送及其空箱的回收，達到以最少的小車出行次數(shù)完成配送與回收任務(wù)的目標.圖1所示為飛機移動生產(chǎn)線的物料供應(yīng)模式.IMDCP-AMAL問題的假設(shè)與說明如下：

圖1 飛機移動生產(chǎn)線物料供應(yīng)模式Fig.1 Schematic of material supply mode for aircraft moving assembly line

(1) 飛機移動裝配項目包含n項作業(yè)，J={1,2,…,n}.任意j∈J的執(zhí)行工期為tj，開始時間為Tjs,完成時間Tjf=Tjs+tj.裝配作業(yè)所需物料的供應(yīng)包含兩類任務(wù)，即送料任務(wù)和回收任務(wù).j′∈α={1,2,…,n}表示送料任務(wù)集合，包含n項任務(wù)，表示將作業(yè)j′∈J所需物料配送至相應(yīng)的線邊空間.j″∈β={n+1,n+2,…,2n}表示回收任務(wù)集合，包含n項任務(wù)，表示將作業(yè)(j″-n)∈J的空箱回收至倉庫.

(2) 將時間離散化，時間集合為T={1,2,…,?}，?表示計劃期時長，任意t∈T表示離散的時間節(jié)點.

(3) 線邊存儲區(qū)域是工位旁用于暫存提前送達的料箱和未及時回收的空箱的區(qū)域，將線邊存儲區(qū)域離散為單位線邊空間，l∈L={1,2,…,w}表示單位線邊空間位置集合，且l的最大容量為Cmax.假設(shè)作業(yè)j的物料的線邊暫存位置為lj，lj∈L.任意線邊單元l被分配暫存的作業(yè)集合為Ωl，Ωl?J.對任意線邊位置e,f∈L，Ωe∩Ωf=φ.

(4) 作業(yè)j所需的物料量為mj，由多載量小車配送至相應(yīng)的線邊空間.某項作業(yè)所需的所有物料由一輛小車一次性完成配送，且一輛小車每次可配送多個作業(yè)所需的物料，小車的最大容量為Dmax.為了保證作業(yè)j的正常進行，其物料的配送完成時間Tjd≤Tjs.作業(yè)結(jié)束后空箱可以被回收，即空箱的開始回收時間Tjc≥Tjf.因此作業(yè)j占用線邊空間的時間為料箱送達線邊空間的時刻至空箱被小車回收完成的時刻.任意作業(yè)的所有空箱由一輛小車一次性完成回收，且一輛小車一次可回收多個作業(yè)的空箱.

(5) 物料配送與空箱的回收采用milkrun的方式.R表示小車出行次數(shù)集合，k∈R={1,2,…,r}.小車從倉庫出發(fā)，沿著給定路徑行駛并在相應(yīng)的線邊單元對物料箱或空箱進行裝卸，然后返回.小車從倉庫到線邊空間l的行車時間為tl，小車卸載料箱和回收空箱的時間分別為tun,tc.假設(shè)作業(yè)j的物料配送完成時間為料箱卸載完成的時間.

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

(1) 決策變量：τk為整數(shù)變量，表示第k次出行的發(fā)車時刻；Zjk為0，1變量，當其為1時表示作業(yè)j所需物料在第k次出行時配送，否則為0；Yjk為0，1變量，當其為1時表示作業(yè)j的空箱在第k次出行時回收，否則為0.

(2) 目標函數(shù)：

minZ=|R|

(1)

約束：

(2)

(3)

τk+1≤τk+1,?k∈R

(4)

(5)

?k∈R,l∈L

(6)

?k∈R,l∈L

(7)

?k∈R,l∈L

(8)

?k∈R,j∈J

(9)

(10)

τk,?k∈R

(11)

Zjk∈{0,1},Yjk∈{0,1},?k∈R,j∈J

(12)

其中，式(1)為目標函數(shù)，即最小化多載量小車的出行次數(shù)；式(2)表示任意裝配作業(yè)的料箱必須一次性配送至相應(yīng)的線邊空間；式(3)表示表示任意裝配作業(yè)的空箱必須一次性回收至倉庫；式(4)定義了多載量小車出行次數(shù)的先后順序約束；式(5)表示每次安排配送的料箱總量不得超過小車的最大容量；式(6)表示小車離開任意線邊位置時的運載量不超過小車的最大容量；式(7)定義了小車到達線邊位置的時間；式(8)表示安排入任意單位線邊空間暫存的料箱量不得超過線邊空間的最大容量；式(9)表示任意作業(yè)的物料的配送完成時間應(yīng)不晚于其裝配開始時間，其中M為無窮大的數(shù)；式(10)表示任意作業(yè)的空箱的回收開始時間應(yīng)不早于其裝配完成時間；式(11)和式(12)定義了決策變量的可行域.

2 算法設(shè)計

針對IMDCP-AMAL的特點，設(shè)計了一類以遺傳算法為框架的啟發(fā)式算法(CHBG)，其中嵌套了局部搜索算法.該算法的基本框架與主要思路為：通過遺傳算法較強的全局搜索能力搜索較優(yōu)的任務(wù)(送料、回收)執(zhí)行順序，為每一條包含任務(wù)執(zhí)行順序的染色體設(shè)計有效的解碼過程對小車裝載能力進行合理分配，從而獲得各項作業(yè)的物料配送時間、空箱回收時間的可行解.在此基礎(chǔ)上，基于上述結(jié)果，通過深度局部搜索算法對配送與回收任務(wù)進行再分配，使得更多的任務(wù)能并行完成，進一步減少小車出行次數(shù).以下分別對遺傳算法框架、約束轉(zhuǎn)換、啟發(fā)式解碼以及局部搜索算法進行闡述.

2.1 算法框架

遺傳算法采用任務(wù)列表方式編碼，染色體由任務(wù)列表λ組成，每一個基因位表示一個任務(wù)序號，則每一條染色體代表一個任務(wù)順序列表.一個任務(wù)列表包含所有的送料任務(wù)和回收任務(wù)的執(zhí)行的優(yōu)先順序.染色體的初始化方式包括隨機生成和基于優(yōu)先規(guī)則生成兩種，優(yōu)先規(guī)則包括最小冗余度任務(wù)優(yōu)先、最小最早離開時間任務(wù)優(yōu)先、最大最早離開時間任務(wù)優(yōu)先、最小最遲離開時間任務(wù)優(yōu)先、最大最遲離開時間任務(wù)優(yōu)先.遺傳算法的進化算子可以參考文獻[12-14],本文不再贅述.

設(shè)定遺傳算法的種群大小為P，迭代次數(shù)為N，λ表示當前代數(shù).適應(yīng)度函數(shù)Fit如式(13)所示，表示小車裝載率平方的均值，用于評估小車裝載量的利用.CHBG算法的目標為最大化染色體個體的適應(yīng)度值.

(13)

算法框架如圖2所示.對每個染色體個體，首先進行約束轉(zhuǎn)換，然后通過啟發(fā)式解碼得到可行解，最后利用深度局部搜索進行優(yōu)化.

圖2 遺傳算法框架Fig.2 Genetic algorithm framework

2.2 約束轉(zhuǎn)換

在求解IMDCP-AMAL問題時，通過將線邊空間的容量約束轉(zhuǎn)換為任務(wù)的完成時間約束，以松弛約束，便于問題的求解.

為了保證裝配作業(yè)j的正常執(zhí)行，其對應(yīng)的送料任務(wù)j′的最遲完成時間L等于Tjs，回收任務(wù)j″的最早完成時間Ej″等于Tjf.送料任務(wù)的初始完成時間dtj∈[0,Tjf]，回收任務(wù)的初始完成時間ctj∈[Tjs,T].則作業(yè)j的料箱(物料及空箱)在線邊空間的占用時間窗為[dtj,ctj]，由送料任務(wù)的完成時間和回收任務(wù)的完成時間共同決定.在計劃期內(nèi)，任意時刻的料箱占用量不超過線邊空間的容量.因此，通過約束送料任務(wù)j′的最早完成時間和回收任務(wù)j″的最遲完成時間可實現(xiàn)線邊空間容量的限制.轉(zhuǎn)換方式舉例說明如下：

圖3所示為某線邊位置所分配的所有作業(yè)的調(diào)度計劃.該線邊位置所分配暫存的作業(yè)集合為Ω={1,2,3,4}，Cmax=5.作業(yè)1、2、3的料箱在線邊空間占用的絕對時間窗交集為Α=[6,7]，作業(yè)4的料箱在線邊空間占用的絕對時間窗為B=[12,17].Con表示某時刻線邊空間的初始占用量.對任意t∈(3,10),Con+m1>Cmax，為了保證線邊空間容量約束，則Α∩Β=?.因此，若先安排作業(yè)4所對應(yīng)的送料任務(wù)，其最早完成時間E4″為7，作業(yè)1、2、3中所對應(yīng)的回收任務(wù)min{Lj″|j″=1,2,3}min{ctj|j=1,2,3}.

圖3 調(diào)度計劃甘特圖Fig.3 Gantt chart representation of schedule

2.3 啟發(fā)式解碼

基于確定的任務(wù)優(yōu)先順序，綜合考慮物料配送能力和線邊空間存儲能力為各項任務(wù)安排完成時間.本文設(shè)計啟發(fā)式方法對染色體(編碼)進行解碼.具體決策方法如下：在安排某次小車出行時，首先根據(jù)任務(wù)列表順序選擇某個未完成任務(wù)，安排該任務(wù)在此次出行中完成從而確定小車出行的時間窗.然后通過兩階段啟發(fā)式算法決策送料任務(wù)與回收任務(wù)，不斷調(diào)整小車出行時間.其中，第一階段，與回收任務(wù)協(xié)調(diào)，優(yōu)先安排線邊位置靠前的送料任務(wù)；第二階段，借鑒文獻[13]的FFD(first-fit-decreasing)啟發(fā)式規(guī)則安排回收任務(wù).若小車空間約束不滿足，則開始下一次出行的安排.通過依次安排小車每次出行所完成的任務(wù)，獲得完整的配送與回收計劃.啟發(fā)式解碼的具體步驟如下：

(1) 令k=1，初始化已安排任務(wù)集合ω=?，未安排任務(wù)集合η={1,…,2n},未安排的送料任務(wù)集合D={1,…,n}，未安排回收任務(wù)集合Ρ={n+1,…,2n}.

(2) 初始化第k次出行已安排任務(wù)集合υk=?，送料任務(wù)集合Dk=?，回收任務(wù)集合Pk=?.

(3) 可選擇的任務(wù)集合ωk=η.讀取編碼中的任務(wù)列表.

(4) 按照順序從小到大選擇序號最小的任務(wù)b∈ωk，以任務(wù)b確定小車離開時間窗[εA,ψA].

(10) 令k=k+1，若η≠?，轉(zhuǎn)(2)，否則轉(zhuǎn)(11).

(11) 檢驗單位線邊空間容量約束，即計劃期T內(nèi)任意時刻所有線邊空間的料箱數(shù)都不超過上限，若不滿足，則k=k+ζ，ζ為懲罰因子.

(12) 輸出配送回收計劃S，算法結(jié)束.

2.4 局部搜索

局部搜索算法以啟發(fā)式解碼得到的可行出行計劃作為初始解，將小車單次出行的任務(wù)集作為搜索對象，判斷該集合中每個任務(wù)可于其他某次出行中完成的情況.若所有任務(wù)均可實現(xiàn)轉(zhuǎn)移，則將此次出行的全部任務(wù)分配至其他出行中完成，以達到減少整體出行次數(shù)的目的.算法的具體步驟如下：

(1) 獲取可行計劃S，由一組元組(Θ,λ)∈S表示，Θ代表每次出行安排的任務(wù)集合，λ代表小車出行時間.

(4) 若所有更新的q滿足時間約束，則|R|=|R|-1.

(5) 通過調(diào)整出行時間使線邊空間容量約束滿足，若能滿足，則更新計劃S，轉(zhuǎn)(2)，否則轉(zhuǎn)(6).

(6) 輸出優(yōu)化后的計劃S.

3 數(shù)值實驗

本文算法運用C#(Visual Studio 2015)編程實現(xiàn)，測試實驗在Internet Core i7處理器，3.4 GHz主頻，8G內(nèi)存的測試平臺上進行.測試算例基于PSPLIB算例庫，根據(jù)IMDCP-AMAL的特點對數(shù)據(jù)進行擴充，為裝配作業(yè)數(shù)量為16、18、20、22、24、30、45和60八類規(guī)模的數(shù)據(jù)，分別生成30組算例.同時為算例中每個作業(yè)j生成l∈(1,10)的線邊存放位置，隨機生成m∈(1,5)的物料需求量.設(shè)定多載量小車從倉庫到第一個線邊位置的行車時間t1=4，到第l個線邊位置的行車時間tl=tl-1+1,?l=2,…,w，停留時間tun=2,tc=2.多載量小車配送能力上限D(zhuǎn)max=5，單位線邊空間容量上限Cmax=5.

3.1 與CPLEX的對比

通過表1可以得出，在小規(guī)模算例實驗中，CHBG算法在可接受的時間內(nèi)能夠求得較優(yōu)的結(jié)果.對于大多數(shù)算例規(guī)模為16和18的作業(yè)，CHBG算法求得的解與CPLEX得到的結(jié)果GAP值不超過5%.隨著算例規(guī)模以及復(fù)雜度的增加(算例規(guī)模為20～24)，CPLEX在許多情況下無法求得最優(yōu)解，而CHBG算法仍可求得較優(yōu)解.

表1 小規(guī)模算例實驗結(jié)果Tab.1 Numerical experiment results of small- scale examples

3.2 與現(xiàn)有文獻的對比

通過表2可得出，在求解大規(guī)模算例時，CHBG集成算法在可接受的時間內(nèi)能夠求得較優(yōu)的結(jié)果.對于大多數(shù)算例規(guī)模為30的作業(yè)，而CHBG算法求得的解相對于CAS的優(yōu)化比例達到25.6%，隨著算例規(guī)模以及復(fù)雜度的增加(算例規(guī)模為45和60)，CHBG算法的優(yōu)化比例也在4.82%以上.說明將物料配送和空箱回收綜合考慮進行集成決策相比傳統(tǒng)的獨立決策方法具有優(yōu)勢.

表2 大規(guī)模算例實驗結(jié)果Tab.2 Numerical experiment results of large- scale examples

4 總結(jié)與展望

(1) 以飛機移動生產(chǎn)線為實際背景，同時考慮了物料的配送及其空箱的回收問題，將這兩類相互影響的決策整合到一個聯(lián)合決策框架中，提出了集成決策的優(yōu)化模型.

(2) 針對集成模型設(shè)計了以遺傳算法為框架的啟發(fā)式算法，該算法對小車的裝載、調(diào)度進行了聯(lián)合優(yōu)化決策，通過充分利用小車運載能力優(yōu)化了小車出行次數(shù)，減少了配送與回收的總成本.

(3) 通過數(shù)值實驗對算法進行了驗證，實驗結(jié)果證明了本文提出的算法的有效性，為飛機移動生產(chǎn)線這類考慮空箱回收的物料配送問題研究提供了借鑒.

(4) 后續(xù)可以考慮對飛機移動生產(chǎn)線中線邊空間物料擺放決策展開詳細研究，為IMDCP-AMAL問題提供更高效的決策.