陸志強， 周皓雪

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

基于精益思想的飛機移動式裝配線已成為飛機裝配生產(chǎn)的新模式，具有裝配效率高、質(zhì)量穩(wěn)定、可按需批量生產(chǎn)等特點，近年來被世界各大航空制造企業(yè)競相采用.實際上，對于每架飛機而言，移動式裝配線上的總裝任務調(diào)度問題具有裝配工序繁多、裝配任務復雜、裝配過程受到多重約束限制等特點.調(diào)度過程可根據(jù)實際應用的目的抽象為資源受限項目調(diào)度問題(RCPSP)以及與之關(guān)聯(lián)的資源投入型問題(RIP)兩大類.前者與裝配線的規(guī)劃、設計和決策相關(guān)，而后者與裝配線的運作決策關(guān)聯(lián).對裝配線的日常運作決策而言，通常需要在給定工期的條件下，優(yōu)化裝配線的各類資源配置及分配使用，達到最小化資源投入總成本的目的，即資源投入型問題.對于一般裝配線來說，裝配線復雜度較低，工作可替代性強.飛機移動式裝配線的工序繁瑣復雜、工作專業(yè)性強，對于特殊人力資源要求極高.同時，整個裝配周期較長，關(guān)鍵技術(shù)人員稀少并且可能存在不可用時間段，對于飛機裝配生產(chǎn)線考慮資源利用區(qū)間是重要且必要的.因此，在基本RIP的基礎(chǔ)上，考慮到飛機裝配生產(chǎn)中某些關(guān)鍵資源具有提前已知的不可用時間段，即引入資源空窗期約束，提出帶資源空窗期的資源投入型問題.

資源投入型問題作為RCPSP的對偶問題，最早由M?hring[1]引入，并且該問題被證明為NP-hard問題.以RCPSP的算法求解為基礎(chǔ)，得到了求解該問題的圖解精確算法.Drexl等[2]基于拉格朗日松弛和列生成方法為RIP提出了兩個下界算法，并且通過算例實驗與M?hring[1]的算法進行了比較.Rodrigues等[3]提出了一種改進型割平面法，通過啟發(fā)式算法得到初始解并不斷更新低界，縮小解空間，從而提高計算效率.由于精確算法只能求解小規(guī)模問題，因此大量國內(nèi)外學者針對大規(guī)模問題提出啟發(fā)式算法與元啟發(fā)式算法.Song等[4]提出帶局部搜索的進化算法，允許項目延期但是設有極高的延期懲罰.Myszkowski等[5]在混合蟻群算法中嵌入啟發(fā)式優(yōu)先級規(guī)則對資源進行分配.Van Peteghem等[6]提出了一種應用于RIP的人工免疫算法.He等[7]設計了基于動態(tài)優(yōu)先級規(guī)則的啟發(fā)式算法，并對任務開始時間決策區(qū)間內(nèi)的所有位置進行評測.Qi等[8]提出了一種新的粒子群算法，在解碼階段設計了多種啟發(fā)式規(guī)則以修復不可行解.由于現(xiàn)有考慮資源特點的RIP相關(guān)研究稀缺，因此帶資源空窗期的RCPSP的研究方法對本研究具有參考意義.胡淑芳[9]針對資源時間窗和任務可拆分特性，設計了小規(guī)模單技能及多技能項目調(diào)度問題求解的分支定界算法.廖廣瑞等[10]考慮資源的多技能和時間窗屬性，設計了基于優(yōu)先規(guī)則的Rollout求解算法，并嵌入了啟發(fā)式資源分配方法對資源進行快速分配.綦方中等[11]研究了基于時間窗的多項目資源分配問題，提出了帶時間窗參數(shù)以及懲罰因子的多項目管理資源分配模型.

從現(xiàn)有文獻可以看出，對于RIP的研究范圍仍偏重于基本問題，而基本RIP通常設有大量假設條件，屬于較為理想化的純理論問題，因此RIP的研究成果難以與更為復雜的實際生產(chǎn)過程有效結(jié)合.此外，從算法設計上來看，大部分啟發(fā)式算法在任務開始時間的決策區(qū)間內(nèi)取值時，計算效率不高，并且易限于局部考慮而忽略全局影響.常見的搜索算法可分為以下兩類：一類以資源量進行編碼，但這樣編碼容易導致資源上、下界差距較大，搜索效率低，難以找到結(jié)果較好的可行解；一類以任務開始時間進行編碼，但這類編碼大多數(shù)未考慮問題特點，搜索的方向性不強，導致算法效率低.基于此，在進行算法設計時重點考慮資源空窗期約束，首先提出求解RIP的啟發(fā)式算法.區(qū)別于基本RIP，設計了非關(guān)鍵任務優(yōu)先級、關(guān)鍵任務排入以及非關(guān)鍵任務調(diào)度的三階段啟發(fā)式算法,對模型進行求解.通過進一步的分析發(fā)現(xiàn)，啟發(fā)式算法處理大規(guī)模算例時具有局限性，因此在啟發(fā)式算法的基礎(chǔ)上設計了以非關(guān)鍵任務優(yōu)先級和關(guān)鍵任務開始時間為雙鏈表編碼的遺傳算法，并將啟發(fā)式規(guī)則嵌套在遺傳算法的解碼和評估階段，提高了求解的精確性.最后，通過數(shù)值實驗驗證了啟發(fā)式算法和遺傳算法的有效性，同時證實了空窗期約束的存在對于算法設計具有影響.

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

1.1 問題描述

假設飛機裝配項目由若干項任務構(gòu)成，任務之間存在著一定的時序關(guān)系，任務的執(zhí)行需要消耗相應的資源.記給定項目總工期為T，包含J項任務，每項任務j(j=1,2,…,J)的執(zhí)行時間為tj，p(j)為第j項任務的緊前任務集合，s(j)為第j項任務的緊后任務集合，tES,j、tLS,j、tEF,j和tLF,j分別為任務j(j=1,2,…,J)的最早開始時間、最晚開始時間、最早結(jié)束時間以及最晚結(jié)束時間,tTF,j表示任務j開始時間的浮動長度,即tTF,j=tLS,j-tES,j.項目中使用的可更新資源種類為P，每種資源的單位使用成本為Cp(p=1,2,…,P).rjp表示任務j(j=1,2,…,J)需要的單位資源p(p=1,2,…,P)的數(shù)量,rj,max表示任務j需要的所有資源中需求量最大的資源值.關(guān)鍵資源pk在特定的一段或多段時間區(qū)域內(nèi)不能工作，即資源的空窗期約束.Ae代表需要用到關(guān)鍵資源pk的任務集合.對時間進行離散化處理，模型的求解目標是優(yōu)化各時刻t(t=1,2,…,T)每種資源p(p=1,2,…,P)的最大需求量Rtp的總成本.

模型中決策變量包括：xjt為0、1變量，1表示任務j(j=1,2,…,J)在時刻t被執(zhí)行，否則取0；zjm為0、1變量，1表示任務j∈Ae在第m個非空窗期區(qū)間內(nèi)完成，否則取0.

1.2 空窗期

在飛機裝配的實際生產(chǎn)中，關(guān)鍵資源的使用時間往往不是連續(xù)的，某些時段可用，某些時段不可用，將這種約束稱為資源空窗期約束.參考劉振元等[12]相關(guān)論文，對空窗期相關(guān)參數(shù)進行定義.

如圖1所示，假設有M個空窗期，m=1,2,3,…,M，tb,m和te,m分別為第m個空窗期的開始和結(jié)束時間.在空窗期內(nèi)資源可用數(shù)量為零，在非空窗期內(nèi)資源可用數(shù)量為常數(shù)R0.lm表示第m個空窗期的長

圖1 資源空窗期示意圖

度，易得lm=te,m-tb,m；δ(m-1,m)表示第m個非空窗期的長度，易得δ(m-1,m)=tb,m-te,m-1.假設tb,0=te,0=0.

1.3 數(shù)學模型

目標函數(shù)為

(1)

約束為

(2)

(3)

(4)

(5)

t=1,2,…,T

(6)

txjt≤T,t=1,2,…,T

(7)

目標函數(shù)(1)表示該問題是優(yōu)化整個周期內(nèi)各資源使用的最大總成本.約束條件(2)表明時刻t資源p的使用量；式(3)表示任務在整個周期內(nèi)的執(zhí)行時間滿足該任務工期約束；任務之間應該滿足約束(4)，即滿足一定的優(yōu)先關(guān)系；式(5)說明需要關(guān)鍵資源的任務必須滿足空窗期約束；式(6)說明任務一旦開始，在完成之前不允許被中斷；式(7)說明所有任務的最晚結(jié)束時間不應大于項目給定工期.

2 啟發(fā)式算法設計

啟發(fā)式算法的設計思路為：基于關(guān)鍵路徑法(CPM)獲得項目中的關(guān)鍵鏈，確定關(guān)鍵任務和非關(guān)鍵任務.將關(guān)鍵任務納入調(diào)度計劃，決策關(guān)鍵任務排入方式為連續(xù)排入或預留時間間隔排入；在此基礎(chǔ)上安排非關(guān)鍵任務，提出四種規(guī)則確定非關(guān)鍵任務優(yōu)先級，然后以最小資源需求量為目標，確定非關(guān)鍵任務的決策區(qū)間，再通過局部規(guī)則判斷基準在決策區(qū)間內(nèi)的取值，最終確定非關(guān)鍵任務調(diào)度位置.通過以上分析可知，該啟發(fā)式算法可根據(jù)決策重點分為三個階段.

2.1 第一階段：生成非關(guān)鍵任務優(yōu)先級列表

吳怡薇等[13]在求解資源水平問題時提出采用資源用量規(guī)則和自由度規(guī)則來確定非關(guān)鍵任務優(yōu)先級.本研究在基本RIP上考慮空窗期約束，為了減少空窗期對任務的交互影響，增加工期規(guī)則以及最早開始時間(EST)規(guī)則，使可能對調(diào)度結(jié)果產(chǎn)生更大影響的任務擁有更多可排空間，盡早排入.

(1) 工期規(guī)則

任務工期越長，與已排定任務重疊度越高，在有空窗期的條件下，與空窗期重疊的可能性也越大.RIP目標的本質(zhì)就是通過調(diào)度使得任務間重疊度降低，所以tj越長，非關(guān)鍵任務j的優(yōu)先級越高.

(2) EST規(guī)則

一般而言，在RIP中任務調(diào)度順序與各任務在項目網(wǎng)絡圖中位置不完全一致.EST規(guī)則可作為前三種規(guī)則的補充，避免優(yōu)先級相同的情況出現(xiàn)，因此可定義tES,j越小，非關(guān)鍵任務j的優(yōu)先級越高.

任務的工期對開始時間決策區(qū)間的大小影響很大，而任務的資源用量直接影響資源投入總成本，故工期規(guī)則及資源用量規(guī)則作為優(yōu)先規(guī)則考慮.具體操作時，按照上述四種規(guī)則順序依次比較非關(guān)鍵任務j的tj、rj,max、tTF,j以及tES,j，最終確定非關(guān)鍵任務優(yōu)先級列表Lp.

第一階段算法步驟如下所示：

步驟1建立已安排任務集合S=?，未安排任務集合S′=J.

步驟2確定需要關(guān)鍵資源pk的任務集合Ae.

步驟4根據(jù)CPM獲得任務j∈J的tES,j、tLS,j、tEF,j、tLF,j和tTF,j.

步驟5確定關(guān)鍵任務為集合Cr，余下任務即為非關(guān)鍵任務.

步驟6生成非關(guān)鍵任務優(yōu)先級列表Lp.

2.2 第二階段：關(guān)鍵任務排入方式的確定

2.2.2關(guān)鍵任務調(diào)整基準

圖2 相關(guān)關(guān)鍵任務調(diào)整

第二階段算法步驟如下所示：

步驟1將集合Cr內(nèi)的所有關(guān)鍵任務連續(xù)排入.

步驟7t=t+1；返回步驟5.

2.3 第三階段：非關(guān)鍵任務的調(diào)度決策

2.3.1相關(guān)任務與相關(guān)距離dij

2.3.2任務j∈J開始時間tST,j可排區(qū)間點集

(8)

(9)

(10)

從而形成最終的tST,j可排區(qū)間離散點集

Smove,j={tST,j1,tST,j2,…,tST,jn}

(11)

2.3.3任務j∈J開始時間tST,j可變區(qū)間點集

社會保障體系中的商業(yè)保險：關(guān)系形成、目標構(gòu)建與屬性定位 …………………………………………… 謝長青 張藝珂（4/33）

(12)

任務j開始時間tST,j的可變區(qū)間點集即為任務j開始時間tST,j的決策區(qū)間.

2.3.4局部最優(yōu)判斷基準

對于任意非關(guān)鍵任務j而言，易得Schange,j?Smove,j，而Schange,j中的點實際上為只考慮任務j的資源總量最小解集，顯然集合內(nèi)的所有點未必都能對應全局下的最小資源總成本.

根據(jù)優(yōu)先級排入非關(guān)鍵任務，待排任務的位置確定受后序任務的影響.因此，通過考慮任務j的調(diào)度位置對后序任務的排入影響來進一步確定tST,j，即使得連續(xù)排入的兩個任務間結(jié)果最優(yōu).

第三階段算法步驟如下所示：

步驟2生成當前任一時刻t的資源列表Rtp.

步驟3按照優(yōu)先級順序選擇非關(guān)鍵任務優(yōu)先級列表Lp中任務j，獲得其對應的Re={i∈S|ij}，對于任意任務i∈Re求出相關(guān)距離dij，繼而得出tST,j可排區(qū)間點集Smove,j.

步驟7result[]中的最小值為最終結(jié)果，輸出該結(jié)果，算法結(jié)束.

3 遺傳算法設計

分析啟發(fā)式算法的設計過程，發(fā)現(xiàn)非關(guān)鍵任務的優(yōu)先級以及關(guān)鍵任務的開始時間會對最終結(jié)果產(chǎn)生較大的影響，而啟發(fā)式算法中并未對這兩項進行更多可能性的嘗試.因此，本研究遺傳算法的上層算法中，對于決策項目非關(guān)鍵任務的優(yōu)先級和關(guān)鍵任務的開始時間，下層解碼算法采用第2節(jié)中提出的啟發(fā)式規(guī)則，決策各非關(guān)鍵任務的開始、結(jié)束時間，并以此方案的目標函數(shù)值作為遺傳算法的適應度值，返回到上層遺傳算法，再不斷復制、交叉、變異，通過循環(huán)迭代的方式，得到近似最優(yōu)解.

3.1 編碼

對于有J項任務的項目，假設其中關(guān)鍵任務數(shù)量為a，非關(guān)鍵任務數(shù)量為b，易得a+b=J.每組編碼的第一層對應各非關(guān)鍵任務的調(diào)度優(yōu)先級列表，長度為b.若編碼第k位為j，則代表任務編號為j的任務調(diào)度優(yōu)先級為k.第二層對應項目中各關(guān)鍵任務開始時間，長度為a，對于關(guān)鍵任務1假定開始時間為定值tST,1=1，后續(xù)關(guān)鍵任務開始時間在開始時間的可排區(qū)間點集內(nèi)隨機確定,如圖3所示.

圖3 編碼示例

3.2 遺傳操作

3.2.1初始種群

初始種群由兩部分組成：一是按照第2.1節(jié)中啟發(fā)式算法非關(guān)鍵任務的優(yōu)先級列表以及第2.2節(jié)中連續(xù)排入的關(guān)鍵任務作為一個初始解；二是在可行范圍內(nèi)隨機生成.

3.2.2選擇

運用隨機聯(lián)賽選擇算子，適應值小的進入下一代種群.適應值函數(shù)為

(13)

3.2.3交叉

本研究采用單點交叉的方法.由于遺傳算法采用雙鏈表編碼模式，對非關(guān)鍵任務優(yōu)先級以及關(guān)鍵任務開始時間進行編碼，交叉操作后可能出現(xiàn)不可能解，因此需要進行額外操作消除不可行解.對于非關(guān)鍵任務鏈表需要消除交叉后可能出現(xiàn)的重復現(xiàn)象，對于關(guān)鍵任務開始時間鏈表需要保證交叉后的時間在該任務開始時間的可行范圍之內(nèi)，具體過程如圖4所示.

(1) 對非關(guān)鍵任務優(yōu)先級的鏈表進行交叉操作.對染色體C2，選擇與染色體C1中x位置之前的基因不相同的基因鏈，與染色體C1中x位置之后的基因段互換，生成新的染色體Sg；對染色體C1，同理生成新的染色體D.

(2) 對關(guān)鍵任務開始時間的鏈表進行交叉操作.對染色體C2，選擇與染色體C1中x位置之前的基因鏈，與染色體C1中x位置之后的基因段互換，若互換后的開始時間點處在區(qū)間[tES,tLS]內(nèi)，則直接互換；若互換后的開始時間點小于tES，則互換后的基因取值為tES；若互換后的開始時間點大于tLS，則互換后的基因取值為tLS；生成新的染色體Sg；對染色體C1，同理生成新的染色體D.

圖4 交叉操作示例

3.2.4變異

本研究采用基本位變異的方法，分以下兩步進行:

(1) 對k=1,2,…,b，在[1,b]之間隨機產(chǎn)生兩個數(shù)x、y，交換x、y兩位置所對應的任務的優(yōu)先級，生成新的列表.

(2) 對k=2,3,…,a，在[2,a]之間隨機產(chǎn)生一個數(shù)z，改變位置z所對應任務的開始時間，并重新生成位置z后序所有關(guān)鍵任務的開始時間.具體過程如圖5所示.

圖5 變異操作示例

3.3 解碼

利用上述遺傳算法，得到了非關(guān)鍵任務優(yōu)先級列表以及關(guān)鍵任務的開始時間，接下來對所得到的染色體根據(jù)第2節(jié)中介紹的啟發(fā)式規(guī)則，進行相應鏈表的解碼操作.

4 數(shù)值實驗

實驗中所用測試算例基于測試問題庫PSPLIB中的算例進行改造，對于未提供的參數(shù)，采用在一定大小范圍內(nèi)通過random函數(shù)隨機產(chǎn)生自然數(shù)的方式來確定，其中工期上限T取資源不受限下基于最早開始時間調(diào)度得到的任務最晚完成時間的1.2倍.空窗期數(shù)M=1，空窗期開始時間和結(jié)束時間隨機生成，長度不超過0.1T.遺傳算法設定的種群規(guī)模N=100，最大迭代次數(shù)λmax=50，交叉概率Pc=0.8，變異概率Pm=0.1.測試平臺為Intel Core i5處理器，2.20 GHz主頻，4.00G內(nèi)存.

表1～3顯示了小規(guī)模問題的算例結(jié)果，算例規(guī)模依次為10、20、30項任務；每組包含五個算例，C列、H列和G列分別表示CPLEX以及啟發(fā)式算法和遺傳算法在處理本組五個算例時得到的最好解的平均值取整.對于包含60和90項任務的大規(guī)模問題，啟發(fā)式算法和遺傳算法在求解速度上的差異較為明顯，而CPLEX在規(guī)定運算時間內(nèi)無法求得結(jié)果，故對于大規(guī)模問題分別對提出的兩種算法進行求解精度和求解速度的比較.每個算例的空窗期約束在首次隨機生成后統(tǒng)一設定，保證比較的合理性.表4～5為大規(guī)模問題的算例結(jié)果，v列表示每組算例在相應算法下各運行10次后得到的最小值的平均值，w列表示求得對應結(jié)果的平均時間，單位為s.

表1～5中：

(14)

(15)

(16)

表1 10項任務實驗結(jié)果

表2 20項任務實驗結(jié)果

從表1～3中g(shù)1項和g2項可以發(fā)現(xiàn)，對任務數(shù)為10、20、30的小規(guī)模算例，所設計的啟發(fā)式算法與CPLEX求解得到的最優(yōu)解分別相差4.05%、6.12%、10.85%，遺傳算法求得的結(jié)果與CPLEX求得的最優(yōu)解分別相差1.57%、3.20%、6.73%.可以證實所提出的啟發(fā)式算法和遺傳算法在一定誤差范圍內(nèi)均能求解出較好的結(jié)果，遺傳算法求解精度更高；隨著算例規(guī)模的增大，啟發(fā)式算法在求解精度上的局限性越發(fā)明顯；小規(guī)模算例中啟發(fā)式算法與遺傳算法的g3值相差3%左右.

表3 30項任務實驗結(jié)果

表4 60項任務實驗結(jié)果

表5 90項任務實驗結(jié)果

對于任務數(shù)為60和90的大規(guī)模算例而言，通過表4、表5中的g3項結(jié)果可以看出，兩種算法的g3值分別為11.87%、13.57%，相差較大，雖無法與精確結(jié)果作比較，但可以說明求解大規(guī)模問題時，與啟發(fā)式算法相比，采用遺傳算法可以明顯提升求解精度.比較兩表中的w列結(jié)果發(fā)現(xiàn)，任務數(shù)為60時兩種算法的平均求解時間分別為29.54、48.89 s,任務數(shù)為90時兩種算法的平均求解時間分別為60.60、116.78 s，啟發(fā)式算法的求解速度更快.所設計的啟發(fā)式算法的時間復雜性為O(n2)，由于提出的遺傳算法在解碼和評估階段嵌套了相同的啟發(fā)式規(guī)則，隨著算例規(guī)模的增大，兩者在求解時間上的差異也隨之變大.對于大規(guī)模算例，遺傳算法與啟發(fā)式算法相比具有較高的精度，但求解速度較慢.由此表明，提出的兩種算法在不同的層面上具有不同的應用價值.

5 總結(jié)與展望

針對飛機移動式裝配線上存在的關(guān)鍵資源帶有空窗期約束這一特性，提出以連續(xù)排入的兩個非關(guān)鍵任務間結(jié)果最優(yōu)的啟發(fā)式規(guī)則，分別設計了構(gòu)造啟發(fā)式算法和改進遺傳算法求解帶資源空窗期的RIP，并通過數(shù)值實驗驗證了所提出算法的求解精度和求解速度在不同層面上的有效性.小規(guī)模算例中，兩種算法所得解與最優(yōu)解間的平均差值在11%以內(nèi)；大規(guī)模算例中，遺傳算法的求解精度較高，啟發(fā)式算法的求解速度較快.將飛機移動式裝配線抽象為項目調(diào)度資源投入問題的研究對于提升我國飛機制造業(yè)水平、帶動經(jīng)濟發(fā)展和科技進步具有重要意義.