考慮資源空窗期的資源投入問題的建模與優化

陸志強，石 婷

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

飛機制造對于促進科技實力進步、帶動國民經濟發展和提升國家綜合實力有著重要的意義.飛機的移動裝配過程復雜，裝配工序繁多，傳統的經驗式調度安排往往導致線邊資源的極大浪費.因此，研究飛機移動裝配相關基礎問題的建模與科學決策，可以優化各裝配任務的作業時間，有效降低裝配過程的成本.事實上，裝配線上任何單架飛機總裝過程調度決策的基礎問題都可看作是一個資源受限項目調度問題(RCPSP)，各裝配作業任務可認為是完成這個項目的活動，完成各裝配作業任務所需的線邊裝配人員、工裝、工具及儀器設備等可視為是完成項目所需的各類資源.資源投入問題作為該問題的對偶問題，其決策是以預定的工期期限作為約束來控制的，旨在獲得較低的資源投入成本.該問題最早由M?rhing[1]提出，證明了此問題為NP-hard問題，并以求解RCPSP問題的算法為基礎，設計了求解該問題的圖解精確算法.Demeulemeester[2]同樣參照對RCPSP問題的研究，將他與Herroelen[3]共同提出的基于深度優先的求解RCPSP問題的分支定界算法進行了改進，構建了求解資源投入問題(RIP)的優化算法.由于精確算法在求解該類問題時效率差，無法有效處理大規模問題，因此學者們相繼設計了相關元啟發式算法.Yamashita等[4]最早提出求解該問題的元啟發式算法，將Multi-Start啟發式算法和分散搜索(Scatter Search)過程相結合，用以修復不可行解并通過路徑重連提高解的質量.Najafi等[5]提出了以各作業浮動時間為編碼方式的遺傳算法，在解碼階段設計了2種局部優化操作.Van等[6]設計了求解該問題的人工免疫算法，為避免早熟對資源列表及變異操作進行了改進.吳怡薇等[7]以遺傳算法為框架，提出非關鍵任務調度優先級規則，利用區間細分、全局影響評估任務可排區間.Zhu等[8]將RIP問題拆分成排序和資源決策兩類子問題，通過設計鄰域搜索、路徑重連及2種啟發式算法來求解相應的子問題，并通過算例實驗驗證了算法的有效性.

現有文獻中對于RIP問題的研究都以研究RCPSP問題的算法為框架，主要存在2點不足：① RCPSP本身也是NP-hard問題，對于某一資源水平，無法準確判斷該資源下調度結果能否滿足RIP的工期限制；② 在資源投入調度方面，對資源組合的搜索方向性不強，不能充分利用迭代過程中的信息使算法向最優解方向收斂，同時也導致算法效率低.因此，本文在算法設計中首先通過搜索算法直接確定各作業開始時間來間接獲得項目資源投入量，避免了對資源大范圍低效率的搜索；其次，根據迭代過程中的信息，對遺傳算法變異操作進行改進，提出基于概率分布的作業開始時間選擇方法，不斷優化資源使用量，為進一步降低所得目標值，設計分支定界算法用以優化部分作業的開始時間.

另一方面，裝配線上任何一架飛機裝配的總周期時間一般都很長，線上資源特別是關鍵人力資源通常需要在同架飛機(同一項目)和線上不同架飛機(不同項目)的作業任務之間共享，因此，往往會存在因所需資源緊缺而必須延遲調度的情形，本文將資源存在的不可用時間段稱為資源空窗期.胡淑芳[9]考慮資源時間窗和作業可拆分特性，設計了求解小規模單技能及多技能項目調度問題的分支定界算法.Lu等[10]結合微軟的項目調度軟件，說明資源日歷對項目作業最早開始時間的影響，分析了4種時間關系在資源日歷下的延遲.Jirachai等[11]研究了作業可拆分在考慮資源空窗期的多模式RCPSP問題中對調度結果的影響，設計了求解小規模該類問題的分支定界算法.針對項目調度中部分資源存在不可用期的這一實際，本文在設計求解基礎RIP問題算法的基礎上，參照求解帶資源空窗期的RCPSP問題的研究方法，考慮資源存在提前已知的空窗期約束，并著重分析空窗期的引入對問題及算法設計的影響，提出適用于該問題的帶局部分支優化操作的遺傳算法.

1 問題描述及數學模型

1.1 問題描述

項目由J項作業構成，作業間存在著一定的時序關系，各作業僅在滿足時序約束并且所需資源充足的條件下才可開始執行.記給定項目工期上限為T，作業集合A={1,2,…,J}，每項作業j(j∈A)的執行時間為dj，Bpre(j)為項目中第j項作業的緊前作業集合，Bsuc(j)為其緊后作業集合.全部作業共享K種可更新資源，構成資源種類集P={1,2,…,K}，同一種類下的所有資源皆一樣.每種資源p的單位使用成本為Cp(p∈P)，Wp為第p類資源下所有資源在項目工期T內的可用時間窗集，引入參量Zpt，Zpt=1表示資源p在t時刻可以使用，即t∈Wp，否則Zpt=0.各作業j所需要的資源種類為集合Mj，該集合大小為Sj，rjp表示作業j需要的單位資源p(p∈Mj)的數量.Rtp表示各作業在時刻t對資源p的使用量之和.對時間進行了離散化處理，模型的求解目標是優化項目周期內各資源p的使用成本.

1.2 數學模型

(1)

(2)

?t∈Wp,?p∈P

(3)

?j∈A,?t∈T

(4)

(5)

?j*∈Bpre(j),?t∈T

txjt≤T?j∈A,?t∈T

(6)

(7)

?j∈A,?t∈T

xjt={0,1} ?j∈A,?t∈T

(8)

式(1)為目標函數，表示最小化整個周期內資源使用總成本.式(2)可以計算各資源p在其可用時間窗Wp內的使用量.式(3)表示作業只有在所需資源皆可使用的情形下才能執行.式(4)表示作業在整個項目工期內的執行時刻必須滿足該作業工期要求.式(5)表示時序約束，即作業必須在其所有緊前作業完成后才能進行.式(6)表示所有作業的最晚結束時間不應大于項目給定工期.式(7)表示作業一旦開始執行就不能中斷.式(8)定義了決策變量xjt的可行域，作業j在時刻t執行時xjt=1；否則xjt=0.

2 算法設計

用RCPSP問題的求解思路解決RIP問題的算法設計中都以資源組合進行編碼，采用某種優先級規則下調度生成機制的解碼方式來評判各組合在給定工期上限內的可行性，由于對應每一編碼下的子問題仍是NP問題，簡單的啟發式算法所得結果往往較差，從而增大將可行資源組合判定為不可行的幾率，不利于求得較好的目標值.本文算法設計中避免了由資源解碼得到作業調度計劃的過程，通過直接確定作業開始時間的方式來間接獲得項目中的資源投入量，解碼算法中只需根據各作業執行位置計算各時刻資源消耗.考慮到后續的局部優化操作，故對項目工期內各時刻執行的作業進行編碼.以遺傳算法為搜索框架，充分利用迭代過程中作業不同開始時間對應不同目標值的信息，設計基于不同執行位置概率分布的作業開始時間選擇方法來改進變異操作，使資源使用量向最優解收斂.在遺傳算法求得較優可行解的基礎上，針對所得列表，以各資源最大用量的時刻為起始點，考慮資源空窗期的影響，對后續相鄰作業進行局部分支定界搜索，通過部分作業的重調度來進一步降低資源使用量.

算法框架如圖1所示.圖中：M為未改進代數；m為未改進代數閾值.

圖1 算法框架Fig.1 Algorithm framework

2.1 空窗期分析

(9)

i∈Bpre(j),j=1,2,…,J

(10)

i∈Bsuc(j),j=1,2,…,J

圖2 資源空窗期影響作業開始時間示意圖Fig.2 The diagram of starting time of the job affected by the resource vacations

由此可見，當作業所需資源存在空窗期且影響作業開始時間的決策區間時，空窗期的引入會導致作業的可排區間進一步縮小，降低作業調度的靈活性，影響調度結果，從而加劇空窗期前后位置的資源投入量，增加項目的成本支出.為優化考慮資源空窗期對項目調度的影響，解決此類資源投入問題，本文提出以下遺傳算法及局部搜索算法進行求解.

2.2 遺傳算法

2.2.1基于作業位置的編碼 本設計中采用對作業位置進行編碼的方式，項目工期上限為T，則編碼長度為T段，編碼第i段表示該時刻t下開始執行的作業集合，各編碼段集合大小不一.每一編碼段i上的作業集合必須保證各作業之間沒有緊前關系，且其緊前作業在該編碼段之前已執行完畢.以圖3(a)所示算例為例，該網絡圖下的一種可行編碼方式為3(b)，其中作業2～7的開始時間分別為2、0、0、5、4和8.

圖3 編碼示例Fig.3 Example of code

染色體生成步驟如下：

(1)定義時刻t=0，已排作業集Y={1}，可排作業集H=?，未排作業集N={1,2,…,J}；

(2)若t=T，轉步驟(5)；否則，尋找t時刻緊前作業已完成的作業，加入可排作業集H，并將該作業從未排作業集中刪除；

(3)尋找可排作業集H中各作業的全部組合形式，加入集合B；

(4)隨機選擇集合B中的一種作業組合，作為時刻t的執行作業集，令t=t+1，A=?，更新集合Y和N，轉步驟(2)；

(5)輸出編碼列表.

2.2.2單點交叉 在經過輪盤賭選擇機制獲得的種群中，根據交叉概率Pc選擇需要進行交叉操作的染色體組成集合C，

Pc=

(11)

式中：Pc1和Pc2均為預先定義的常數；favg和fmin分別為所有染色體的平均適應度值和最小適應度值.

圖4 交叉操作Fig.4 Crossover operation

2.2.3基于作業執行位置選擇概率的變異 對經過交叉之后得到的染色體，根據變異概率Pm選擇需要進行變異操作的染色體組成集合G，Pm同樣通過式(11)求得.

對集合G中的染色體，本文設計了一種在迭代中改進作業開始時間的變異機制，通過不斷調整迭代過程中各作業可排區間內各開始時間取值的概率，排除會產生極大資源用量的作業開始時間值，進一步縮小搜索空間，從而找到更好的作業調度方案.

定義染色體中變異作業μ開始時間選擇概率Ptsμ(tes≤ts≤tls)和該開始時間下需要多投入的資源量Rtsμ.在初始種群中，令Rtsμ=1.之后的每條染色體，都根據當代的資源用量R更新Rtsμ：

Rtsμ=Rtsμ+max{0,R-R0}

(12)

染色體中需要變異的作業的開始時間ts被選中的概率為

(13)

式中：R0為當前得到的最低資源用量.

在迭代過程中，資源用量越大的作業開始時間ts對應的Rtsμ會不斷增大，使得其被選中的概率Ptsμ不斷減小；反之，越接近R0的作業開始時間對應的Rtsμ較小，使得相應Ptsμ被選中的概率變大，由此可以不斷縮小作業開始時間的決策區間，使得作業調度向著產生更好的解的方向收斂.

綜上，遺傳算法步驟如下：

(1)初始化種群，令迭代次數λ=0，當前資源投入量為X；

(2)判斷λ<λmax，若是，轉步驟(3)；否則，轉步驟(7)；

(3)對各染色體進行解碼，求得相應的資源使用量；

(4)采用3.2.2和3.2.3中的交叉和變異機制生成新的種群；

(5)計算新生成個體的目標函數值，更新X；

(6)運用輪盤賭選擇算子產生下一代種群，λ=λ+1，轉步驟(2)；

(7)輸出X.

2.3 局部優化算法

在遺傳算法所得作業調度方案的基礎上，為進一步優化調度結果，降低資源投入成本，本文提出以分支定界算法為框架的局部優化操作，對調度結果中各最大資源量處的作業進行完全搜索，尋找較低資源用量的作業組合方式及執行方案，現就其中涉及的分支方法與支配規則進行闡述.

2.3.1分支方法 對所得作業位置列表，計算各時刻各資源消耗量，選擇各資源最大用量處開始執行的j項作業進行深度搜索，通過回溯方法驗證其鄰域分支，直至完全搜索，具體步驟如下：

(2)確定j項作業中可以在節點g處執行的作業組合集合Cg；

(3)從Cg中隨機選擇作業組合Eg，更新Cg=Cg-Eg；

(5)若所有分支節點都滿足Cg=?，則搜索結束，更新原調度方案中j項作業的執行位置及資源消耗量.

以圖3(a)所示7項作業的項目網絡圖為例，對應的搜索樹結構如圖5所示.圖中：節點O=?表示該時刻有未執行完成的作業，可以不選擇新的作業執行.

圖5 搜索樹示例Fig.5 Example of search tree

2.3.2支配規則 為提高分支過程搜索的效率，本文提出4種支配規則，用以剪除多余不可行或不好的分支.

定義當前調度時刻為t，當前節點為g，g在時刻t-1的根節點為g′，作業j：

(1)未調度且其緊前作業在t之前皆已執行完畢，則稱作業j為時刻t可排作業；

(2)未調度且其tes=t，則稱作業j為時刻t必排作業；

(3)已調度且其結束時間tft>t，則稱作業j為時刻t執行作業；

(4)已調度且其結束時間tft≤t，則稱作業j為時刻t已排作業；

(5)不屬于已排作業，則稱作業j為時刻t未排作業.

規則1若決策集E(t)中存在不包含所有必排作業集L(t)中的元素的子集Fv(t)，v∈N*，則該子集Fv(t)所在節點不再分支.

證明所謂必排作業，即滿足tls=t，tls的值是根據工期上限和資源空窗期確定的，代表作業的最晚開始時間，超出該時刻執行則表明項目一定會延期，在既定工期上限下無法求得可行解，所以對不包含必排作業的節點進行截斷.

圖6 規則1示例圖Fig.6 Example of rule 1

證明該問題旨在求得項目最低資源投入成本，當前已得可行解X，則任一資源用量不小于X的節點都無需再枚舉.以圖3(a)算例為例，示意圖如圖7所示.當前可行解X=7，該時刻已完成調度的作業為4(作業2未執行完畢)，可排作業組合為{?，{6}，{3}，{3,6}}，各組合節點的資源使用成本分別為3/5/7/9，其中節點O22和O23的資源使用成本≥X，則相應節點被截斷.

圖7 規則2示例圖Fig.7 Example of rule 2

(14)

時刻t未排作業及子集Fv(t)中剩余未執行工期在[t+1,T]時間段內對各資源p的需求量

R=pg=(RpN(t)-RpFv(t))/(T-t-1)

圖8 規則3示例圖Fig.8 Example of rule 3

規則4若時刻t的決策集F(t)中存在2個子集Fu(t)和Fv(t)滿足：

則子集Fu(t)所在節點不再分支.

證明2個子集Fu(t)和Fv(t)間存在從屬關系，包含作業數多的子集Fv(t)在當前不完全調度下所得局部目標函數值明顯優于包含作業數少的子集Fu(t)，且不影響全局目標函數值，相對后續調度而言，Fv(t)能節省出更多資源及時間的選擇，降低局部目標值提升的概率.

局部優化算法步驟如下：

(3)根據支配規則判斷當前節點是否能夠剪除，若可以轉步驟(4)；否則，繼續分支.

(4)若所有分支皆已枚舉，則轉步驟(5)；否則，回溯搜索樹，繼續分支，轉步驟(3).

(5)選擇集合H的最優調度計劃，更新原計劃，若p>K，優化結束；否則，轉步驟(2).

3 數值實驗

為驗證上述提出的帶局部優化操作的遺傳算法對于求解帶資源空窗期的資源投入問題的有效性，本文運用C#(Visual Studio 2013)編程實現該算法，測試平臺為Intel Core i5處理器，2.40 GHz主頻，8 G內存.

3.1 實例驗證

選取飛機裝配過程中包含部分裝配作業的一個小規模裝配實例對所提算法進行驗證分析.項目中共計18項作業，其中作業1和作業18為虛作業，工期為0且不占用資源.作業間時序關系、作業工期及所需資源量如表1所示.表中：資源R4存在空窗期 [0,1]和[27,29].分別利用CPLEX、本文提出的GA算法和文獻[6]中設計的算法來求解該實例，調度方案如圖9所示.圖中：3種方法調度所得實例中的資源總成本分別為58、59和61.由于資源R4存在前后2段空窗期，限制了如2、4、15和17等作業的最早開始時間，導致其決策區間縮小，3種算法皆安排未使用資源4的作業3和作業16在相應空窗期時刻執行，降低空窗期前后位置的資源使用峰值.圖9(b)和(c)中為本文設計的遺傳算法求解該實例的結果，可以發現，當引入局部分支定界優化操作后能將資源量從63降至59，大大提升優化效率，甚至更優于文獻設計的算法，獲得接近于最優解的目標值.

表1 作業時序關系、工期及資源量Tab.1 Precedence relations,duration and resources of jobs

圖9 各算法調度結果Fig.9 Scheduling results of different algorithms

3.2 算例對比分析

為了驗證本文所提算法的有效性，將該算法的運行結果與CPLEX軟件所求精確解及文獻算法進行了對比.本文所用測試算例是基于測試問題庫PSPLIB中的算例進行改造的，對于基本算例中未提供的參數，采用在一定大小范圍內通過Random函數隨機產生自然數的方式來確定，其中工期上限T取資源不受限下基于最早開始時間調度得到的作業最晚完成時間的 1.2 倍，資源空窗期通過在項目工期內隨機產生長度為3的區間獲得.

在表2～4中，每組包含5個算例，CPLEX列中OC表示CPLEX在處理本組5個算例時得到的最優解的平均值取整，tC表示CPLEX平均運算時間；GA列中AG表示本文算法在處理本組5個算例時得到的最好解的平均值取整，tG表示本文算法平均運算時間；對2種算法所得結果進行比較.BB列中AB表示本文局部優化算法中所設計的分支定界算法用以處理本組算例得到的最好解的平均值取整，tB表示算法平均運算時間，同樣將其與CPLEX結果進行比較.其中：

從表2～4中GAP1項可以發現，對作業數為10,12,16的算例，本文所設計遺傳算法求得的問題的解較CPLEX所得最優解分別相差 0.34%,0.78%,1.48%，平均偏差小于1%，從而證明本文算法在求解小規模問題上的有效性.表格中的后半部分，將應用于遺傳算法中局部優化操作的分支定界算法用以求解相應算例，從BB欄的tB項及GAP2項可以發現，此算法能在較短的時間內獲得問題的最優解，由此表明本文提出的4條支配規則能有效提高分支定界算法搜索效率.

表2 10個作業實驗結果Tab.2 Experiment results of 10 jobs

表3 12個作業實驗結果Tab.3 Experiment results of 12 jobs

表4 16個作業實驗結果Tab.4 Experiment results of 16 jobs

對于作業數為30，60，90的中大型規模的算例，CPLEX在規定時間內無法求得問題的最優解，所得上下界間的差距也極大，因此本研究中以此類規模算例為例，將所設計遺傳算法與文獻[6]中提出的人工免疫算法AIS進行了對比.表5～7中，每組同樣包含5個算例，其中GA列中VG項表示GA在處理本組算例時運行5次后得到的最小值的平均值，tG項表示GA平均運算時間；AIS列中VA項表示對比算法在處理本組算例時運行5次后得到的最小值的平均值，tA項表示對比算法平均運算時間；

通過表5～7的數值結果可以發現，本文所設計的遺傳算法較現有文獻的人工免疫算法，就作業數為30,60,90這3類算例而言，求解精度分別提升1.96%,2.55%,3.36%，局部分支優化的操作能進一步降低所得資源成本，從而實現全局優化.

表5 30個作業實驗結果Tab.5 Experiment results of 30 jobs

表6 60個作業實驗結果Tab.6 Experiment results of 60 jobs

表7 90個作業實驗結果Tab.7 Experiment results of 90 jobs

4 結語

資源投入問題是工程調度問題的一個重要分類，長期以來備受關注.針對飛機裝配中部分關鍵資源存在空窗期這一特性，本文設計了帶分支定界局部優化操作的改進型遺傳算法求解該問題，提出了基于作業位置的編碼方式，及在迭代中改進作業開始時間的變異機制.通過數值實驗，驗證了本文所提出的算法在求解該問題時的有效性.小規模算例中，算法所得解與最優解間的平均差值在1%以下；中大規模算例中，相較現有文獻的人工免疫算法，帶分支局部優化的遺傳算法能進一步提升問題的求解精度，降低資源的投入成本.后續對該問題的研究中可以考慮引入作業可拆分、作業多執行模式等特性，通過降低空窗期對問題調度的影響，進一步優化調度結果.