基于項目拆分決策的多模式資源投入

陸志強， 宗保氏

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

在飛機、輪船等大型工業品的裝配過程中，由于產品規模較大，工藝操作繁瑣等自身特點，導致傳統固定站位式生產方式效率低穩定性差，從而無法滿足市場需求，因此由汽車精益生產方式衍變而來的具有高效率和高穩定性特點的移動式裝配生產線逐漸成為大型工業品的主流生產方式.以飛機移動裝配線為例，類似于汽車移動生產線，裝配線通常被劃分為多個工位，飛機依次緩慢通過所有工位，按照裝配計劃完成全部裝配作業.然而由于飛機裝配工期長，線邊資源特別是關鍵資源不再被固定在特定工位，而是整個裝配線共享所有資源[1]，所以這類問題可以看作一類項目調度問題.將整個飛機裝配過程抽象成一個大項目，裝配線上每個工位需要完成的裝配作業集合組成了飛機裝配的一個子項目，在裝配線資源共享條件下對這些子項目進行調度，可以看作并行執行的多項目調度問題.進一步，在實際生產中，作業往往有多種執行模式，不同的執行模式對應于不同的資源用量和加工時間，而且由于飛機裝配線每個工位含有大量種類繁多的裝配作業，所以合理地安排作業執行模式可以有效的節約資源縮短工期.綜上所述，飛機移動裝配線總裝調度問題在理論上是一類具有作業多模式、約束復雜等特征，且關聯資源投入的大規模多項目協同調度問題.這一類問題可以稱為基于項目拆分決策的多模式資源投入調度問題(multi-mode resource investment project scheduling problem based on project splitting, MRIPSP-PS).目前尚未有針對MRIPSP-PS問題的直接研究，與經典的MRIPSP(multi-mode resource investment project scheduling problem)問題相比，MRIPSP-PS 的決策不僅涵蓋了作業調度、作業模式選擇與資源投入等決策，同時還集成了項目拆分決策，并且這些決策相互影響，現有求解 MRIPSP 問題的方法也無法直接應用于求解 MRIPSP-PS問題，因此對 MRIPSP-PS 問題的建模與算法研究，有重要的理論及實際意義.

顯然，MRIPSP-PS 問題與MRIPSP 問題具有相關性，所以現有的MRIPSP問題的算法對求解MRIPSP-PS問題具有一定參考意義.對MRIPSP問題的研究起始于單模式下的資源投入項目調度問題(Resource Investment Project Scheduling Problem, RIPSP).Mohring[2]最早提出了RIPSP問題，并設計了精確算法對問題進行求解.通過改進Mohring的算法，Demeulemeester[3]設計了一種稱為Minimum Bounding Algorithm(MBA) 的精確算法，通過算例對比證明了MBA具有更高的求解效率.Rodrigues 和 Yamashita[4]將啟發式算法與類似于MBA的分支算法相結合，加快了求解速度.Rangaswamy[5]詳細地介紹了一個新的基于分支定界的算法，進一步提高了求解效率.然而精確算法僅能用于小規模問題，無法有效求解大規模問題.為了求解大規模問題的，不同學者提出了各種啟發式算法.Kelly[6]最早研究了啟發式算法，算法包括優先規則(Priority Rule, PR)和調度生成機制(Schedule Generation Scheme, SGS)兩部分.之后的學者，包括Kurtulus[7]，Boctor[8]，Lawrence[9]，分別提出了不同的優先級規則.Afshar-Nadjafi[10]引入了資源釋放時間的概念，建立了一種新的多模式資源投入問題模型.Chen[11]設計了3類規則，分別用于選擇作業、作業的執行模式和作業的開始時間，并通過3類規則的不同組合來嘗試求解多模式資源投入問題.

然而現有的研究在應用于MRIPSP-PS問題時存在幾點不足：①MRIPSP-PS問題需要對項目進行拆分，需要研究如何確定合理的拆分方案；②文獻中對多模式資源投入型項目調度問題的研究較少，需要更深入研究作業模式選擇和作業優先規則，以及其中涉及的時間約束與資源約束的相互影響關系.因此，針對上述問題，本文提出了包含項目拆分算法和多模式資源投入型項目調度算法的雙層優化算法，上層項目拆分算法將整個項目合理的拆分成多個子項目；下層多模式資源投入型項目調度算法，通過時間因素評估函數和資源因素評估函數，提出了一種新的優先級規則.

1 問題描述及數學模型

1.1 問題描述

以飛機移動裝配線為應用背景，飛機總裝項目可以用節點式網絡G=(V,E)表示，其中V為項目網絡G中的節點集合，代表項目的作業集合，E為項目網絡中弧的集合，代表作業之間的優先關系.項目由編號為j(j=1,2,…,J)的J項作業組成，另外添加作業0和作業J+1兩個虛作業分別代表項目的開始作業和結束作業.

一架飛機所需的全部裝配作業及優先關系如圖1所示.飛機緩慢通過整個裝配線，同時利用裝配線兩側的裝配資源，按照裝配調度計劃完成總裝所需的全部裝配作業任務.

圖1 單架飛機總裝作業

裝配線對多架飛機同時進行裝配，每隔一個裝配節拍，一架飛機完成裝配離開生產線，同時一架待裝配飛機進入生產線.為了對裝配線上的多架飛機進行調度建模，同時滿足裝配節拍的周期性調度，可以將裝配線上各個工位對應為多個“虛擬大工位”，進而把一架飛機所包含的全部裝配作業合理的分配給這些“虛擬大工位”，每個“虛擬大工位”對應一個裝配作業子集合，稱為子項目.例如以圖1中的虛線為界，將飛機總裝作業劃分為3個子項目，劃分后的示意圖如圖2所示.

在此情形下，一方面，對一架飛機來講，它通過了整個裝配線也就通過了所有子項目，完成所有需要的裝配任務；另一方面，每隔一個裝配節拍，裝配線當前子項目位置上的飛機完成對應作業子集中所有任務后進入下一個子項目(或者裝配完成離開生產線)，同時后一架飛機進入當前子項目位置.由于各個子項目的裝配過程在時間上是不同的，這多個子項目可以作為并行開展的多個項目共享整個裝配線的資源，這樣既實現了資源在項目內和項目間的共享，又使得資源的分配計劃符合裝配節拍的周期性要求.顯然，裝配線的資源投入量取決于子項目劃分決策和劃分后多個子項目的資源投入調度計劃.

圖2 飛機總裝作業子項目拆分

1.2 數學模型

不同于單模式問題，在作業多模式條件下的資源投入調度問題中，作業j有m(m=1,2,…,M)種執行模式，分別對應的執行時間為djm，全部作業共享K種可更新資源，rjmk(k=1,2,…,K)表示作業j按照模式m需要第k中資源的數量.Pj表示作業j的緊前作業集合，作業h(h∈Pj)表示作業h為作業j的緊前作業，Sj表示作業j的緊后作業集合.按照從左到右的順序，定義第i個“虛擬大工位”對應的作業任務集合記為子項目i(i=1,2,…,N).項目節拍周期記為C，對時間離散化處理，時間點集合T={t|t=1,2,…,C}，設U為一個足夠大的正數.

MRIPSP-PS問題要求在滿足作業優先關系約束和節拍周期約束的前提下，確定作業的所屬子項目和作業的開始時間，與基本RIPSP問題一樣，MRIPSP-PS問題的目標函數也是項目資源投入最小化.

項目資源投入記為A，具體決策變量如下：Yij為0，1變量，作業j屬于子項目i為1，否則為0；xjmt為0，1變量，作業j在選擇模式且在時刻完成為1，否則為0.

目標函數：

(1)

約束條件：

?i∈N,?j∈J,?h∈Pj,?t∈T

(2)

(3)

U(2-Yij-Yih), ?i∈N,?j∈J,?h∈Pj

(4)

(5)

(6)

xjmt≤C,?j∈J,t∈T

(7)

其中，式(1)表示問題的目標函數為最小化資源投入；式(2)表示在拆分決策中，任意作業的緊前作業不能被分配到該作業所在子項目的后續子項目中；式(3)表示一項作業只能在一種模式下被執行一次；式(4)表示優先關系約束，任意一項作業開始時間必須大于所有實際有效緊前作業的完成時間；式(5)表示任意一項作業能且僅能被分配到某一個子項目中；式(6)表示資源實際用量，項目所需資源量必須大于或等于任意時刻所有在執行作業的資源使用總量；式(7)表示工期約束，任意作業必須在項目工期內完成，不能延期.

2 PSS-JRTS雙層迭代算法

根據模型的決策變量，需要做出兩種決策，針對決策變量Yij的決策稱為拆分決策，針對決策變量xjmt的決策稱為多模式資源投入項目調度決策.基于項目拆分決策的多模式資源投入問題不僅要決策作業的所屬節拍，還要決策作業的執行模式及開始時間，因此本文提出一種雙層迭代算法，PSS-JRTS算法 (project split scheme，joint resource and time scheme)，上層PSS(project split scheme)算法包含項目初始拆分策略和作業移動調整策略，通過對不斷有效調整拆分結果獲得合理的拆分方案， 下層JRTS(joint resource and time scheme)算法通過分析安排不同作業時對項目時間約束和資源約束的影響來確定作業的優先級規則.

2.1 算法整體步驟

算法的整體結構：上層PSS算法劃分作業的所屬子項目，下層JRTS算法確定作業的執行模式及開始時間來生成調度方案，具體步驟如下：

(1)調用上層PSS算法的項目初始拆分策略，將項目中所有作業劃分到N個子項目中，初始化項目拆分結果Yij，設置拆分調整迭代次數Iiter=100，z表示當前迭代次數，初始化為零，項目資源投入記為Abest，初始化為無窮大.

(2)調用下層JRTS算法對當前拆分方案求解，更新xjmt，得到當前方案的資源投入A′.若A′

(3)若z

(4)輸出Abest.

2.2 上層PSS算法

為了獲得一個合理的拆分方案，本文采用一種先將項目作初始拆分，再不斷調整拆分結果的啟發式算法.項目初始拆分策略將項目拆分為N個子項目，使得每個作業都屬于且僅屬于某一個子項目.在每次迭代中，通過將某個子項目中的一個作業移動到其它子項目的方式來調整拆分結果，獲得不同的拆分方案.

2.2.1項目初始拆分策略

初始拆分策略是要在滿足作業優先關系的其條件下將作業劃分到N個子項目中，本文采用了基于CPM(critical path method)的初始拆分方案[12].對未拆分的初始項目，由CPM生成滿足優先關系的調度方案，得到每個作業的結束時間tftj，其中，作業的工期均采用作業所有模式的平均工期計算.為了將項目拆分成N個可行的子項目，按照關鍵鏈工期長度tftJ+1將項目拆分成N份.定義時間截斷區間長度L為

(8)

對每一個作業，按照以下方案分配到子項目中：

(9)

由于CPM得到每個作業的結束時間tftj均小于其緊前作業的結束時間，這樣的拆分方案保證了任意作業的緊前作業不會被分配到該作業所在子項目的后續子項目中，從而使得拆分方案可行.

2.2.2拆分調整策略

按照初始拆分策略將項目拆分為N個子項目后，通過在不同子項目間移動作業來調整拆分結果，獲得新的拆分方案.每次移動需要確定兩個變量，包括從哪一個子項目中移出作業和確定此子項目中的可移動的作業.為了獲得一個較優的拆分方案，使目標函數最小化，那么應該避免在拆分方案中出現各個子項目中作業個數分布差異過大的情況.本文設計了一種考慮子項目中作業個數分布情況的優先規則來決策每次迭代中用于移出作業的子項目.同時，根據不同子項目中作業的可移動條件來確定可移動作業的集合，最終從可移動作業的集合選定要移動的作業.

用mi表示子項目i的作業個數，αi表示選擇子項目i作為移出作業子項目的概率：

(10)

圖3 子項目n中可移動作業

(1) 若n=1，圖3表示第一個子項目，此時子項目的作業只能向后移動到子項目2中，不能前移.圖3中作業14和作業15可以移動，而作業7—13都存在有效緊后作業，不能直接移動.即子項目1中的作業需滿足緊后作業為空時才能移動，則有

?∩Y1j=1,?j∈J}

(11)

(2) 若1

Ynj=1,?j∈J} (1

(12)

(3) 若n=N，此時圖3表示最后一個子項目，子項目中作業只能前移到子項目n-1中，不能向后移動.圖3中作業7、8、9可以前移，其他作業都不能移動，即子項目N中的可移動作業集FN為

?j∈J}

(13)

當選定子項目來移出作業，本文按照每次從可移動作業集Fn中移動一個作業到其他子項目的方式來調整項目拆分方案，得到新的拆分結果Yij.

2.3 下層JRTS算法

通過上層PSS算法，將項目拆分為多個并行的子項目，如圖2所示，下層JRTS算法需要確定作業的執行模式以及開始時間，即決策變量xjmt.本文采用啟發式算法[6]，包含進度生成機制和優先級規則兩部分.其中進度生成機制為串型進度生成機制(serial schedule generation scheme, SSGS)，而傳統的優先級規則涉及到選擇每一次要排的作業以及這個作業的開始時間和執行模式.選擇不同的作業、不同的執行模式和不同的開始時間，會對調度計劃產生不同的影響，主要包括對時間約束的影響和對資源約束的影響.本文提出一種同時考慮資源與時間調度(JRTS, joint resource and time scheme)的函數，分別分析作業安排對兩種約束的影響，設計了一種有效的優先級規則，同時決策要排的作業以及相應的執行模式和開始時間.

2.3.1時間因素評估函數

時間因素評估函數用于評價作業的安排方案對時間約束的影響.根據CPM可以得到作業j的最早及最晚開始時間，分別對最短工期模式(shortest duration mode)和最長工期模式(longest duration mode)得到的變量做出如下定義：tSESTj為最早開始時間(最短工期模式)；tSLSTj為最晚開始時間(最短工期模式)；tSLFTj為最晚結束時間(最短工期模式)；tLTFTj為最晚結束時間(最長工期模式).如圖4所示，作業j的執行時間應在時間窗[tSEST,tSLFTj]內，且當位于時間窗的前半段[tSESTj,tLTFTj]內時，因為不超過最長工期模式下的最晚結束時間，所以作業j的后續作業均可以選擇所有的執行模式執行而不會延期.當作業j的執行時間位于[tLTFTj,tSLFTj]內時，超過了最長工期模式下的最晚結束時間，此時若作業j的后續作業均按照最長工期模式執行，必然無法在項目總工期內完工，引起延期.極端情況為作業j的完工時間為tSLFTj，此時作業j的后續作業只能選擇最短工期模式執行，否則必然引起延期.

綜合考慮作業j的執行時間處在不同位置是對后續作業的影響，當作業j以模式m在t時刻開始的時間因素評估函數為

(14)

圖4 作業j的可排區間

式(14)中tft(j,m,t)=t+djm，表示作業j以模式m在t時刻開始的結束時間，分母用于標準化最大值為1.當作業j在tLTFTj結束時，ftime(j,m,t)為0;隨著結束時間的推遲，ftime(j,m,t)會逐漸增大，且當作業在tSLFTj時刻結束時，ftime(j,m,t)取最大值1；若ftime(j,m,t)大于1時，說明后續作業必然引起延期，表示作業j以模式m在t時刻開始不可行，且時間因素評估函數的值越小越好.

2.3.2資源因素評估函數

資源因素評估函數用于評價作業安排對資源約束的影響.對于一個局部進度計劃，Rrt表示時刻t時資源k的消耗量;Rke表示時刻e時資源k的消耗量.項目中資源k的投入成本Ik可以表示為

Ik=MaxRkt

(15)

Max{Rke+rjmk|t≤e

(16)

假設此時的資源投入上限為RRIL，則資源因素評估函數為

?j,?m

(17)

同樣的，式(17)中分母用于標準化函數的最大值為1.安排作業j以模式m在t時刻開始，若不增加額外的資源投入，fresource(j,m,t)的值為零；若增加額外的資源投入，fresource(j,m,t)的值增大，且在達到資源投入上限RIL時，取得最大值1；若fresource(j,m,t)大于1，表示此時資源約束被破壞，作業j以模式m在t時刻開始不可行.類似于時間因素評估函數，資源因素評估函數越小越好.

2.3.3時間-資源綜合評估函數

ftime(j,m,t)和fresource(j,m,t)分別表示安排活動時面臨的時間影響和資源影響.將兩個因素結合考慮，作業j以模式m在t時刻開始的時間-資源綜合評估函數為

ftotal(j,m,t)=

(18)

在式(18)中，condition條件為11表示存在約束被破壞.若資源約束和工期約束均未被破壞，則ftotal(j,m,t)取時間因素評估函數和資源因數評估函數的平均值，易知此時ftotal(j,m,t)的取值范圍是[0,1]；若某一個約束被破壞，即作業j以模式m在t時刻開始不可行時，將ftotal(j,m,t)賦值為2.應用式(18)，選擇j,m,t的步驟：

(1)對每個待選擇的作業，選定它對應于最小綜合評估函數值的模式和開始時間，這表示若選擇此作業時的最優選擇.

(2)對于所有確定了模式和開始時間的待選擇作業，選擇最大綜合評估函數值的作業.這樣，綜合評估函數值最大的活動最先排，對后續作業的影響最下，避免安排后續作業時使得解變差，即

(19)

在串行調度階段，進度生成機制按照每一步排入一個作業的方式，將所有作業排入進度計劃中.其中，每一步需要決策將要排入調度計劃的作業和作業的執行模式與作業的開始時間.應用式(19)，可以綜合時間約束和資源約束，選擇合適的作業和作業的執行模式與作業的開始時間.

2.3.4JRTS算法步驟

JRTS算法采用先設定一個較低的資源投入上限RRIL，在此RRIL下，應用串行進度生成機制和由式(19)確定的優先級規則對拆分后的多個子項目進行調度求解.若根據式(19)選定的j,m,t使得式(19)中ftotal(j,m,t)>1，即不可行時，不斷增加資源投入上限RRIL，并重新進行調度求解，直到求出可行的最小RRIL，具體步驟如下：

(1)初始化已排作業集合SAS=?,可排作業集合SCS=?,待排作業集合SWS=J，初始化Rrt為均為零，設定初始資源投入上限RRIL=0.

(2)更新可排作業集合，調用式(19)選擇j,m,t.

(3)判斷是否可行.若ftotal(j,m,t)>1，即不可行時，RRIL=RRIL+1，并轉入(1)；若ftotal(j,m,t)≤1，則轉入(4).

(4)將作業j以模式m安排在t時刻開始，并更新Rkt，更新SAS,SCS和SWS.

(5)若待排作業集合SWS=?，表示作業已排完，則轉入(6)；否則，轉入(2).

(6)輸出資源投入最小值A=RRIL.

3 數據實驗

選用PSPLIB標準算例庫中的算例進行算法測試，運用PyCharm(Python 3.5.3)開發環境編程，仿真測試平臺為Intel Core i7-4790處理器，12G內存.現有文獻中關于MRIPSP-PS的研究較少，為了驗證本文算法的有效性，選擇多模式資源首相項目調度問題MRCPSP (Multi-Mode Resource-Constrained Project Scheduling Problem)問題中常用的優先規則構建對比算法[13]，其優先規則通常包含兩類:①優先級規則用于選擇每次要排的作業;②優先級規則用于選擇作業的執行模式和開始時間.

3.1 基于優先級規則的啟發式算法

基于優先級規則的對比算法通過串行進度生成機制生成調度計劃，每次應用作業優先級規則選定要排的作業，再調用作業模式和開始時間優先級規則將作業排入調度計劃中.具體規則如表1所示：

表1 兩類優先級規則

表1中的規則中最小松弛時間規則表示RMST；最晚完成時間規則表示RMLTT；最小額外投入規則表示RMEI；同時上述三種規則可以組成MST-MEI和MLTT-MEI兩種啟發式算法，本文將分別針對不同規模算例與兩種對比算法比較.

3.2 數據對比

表2 J10實驗結果

表3 J20實驗結果

為了在更大的規模下對比算法的有效性，在PSPLIB問題庫的基礎上，將30個作業的算例串聯，分別構造出包含60個作業和90個作業的大規模算例，進一步對算法的性能進行對比，實驗結果如表5～表6所示.

從表2～表4的數據實驗結果可以看出，在小規模的問題下，本文算法領先于MST-MEI算法和MLTT-MEI算法，說明本文算法可以發揮資源評價函數和時間評價函數的綜合優勢，使作業按照較優的方式安排.同時，兩種對比算法，尤其是MLTT-MEI算法的結果在小規模問題中非常接近本文算法，這也說明本文選擇最晚作業結束時間規則作為對比算法是正確的.而且針對不同的拆分數量N，實驗結果顯示本文算法都得到更優的解，證明了其穩健性.

表4 J30實驗結果

在圖5的圖例中，MST_N2和MST_N3分別表示在拆分個數分別為2和3時，每組算例平均領先對比算法的百分比.在問題規模從10增加到30時，本文算法的GAP從2%左右提高到4%以上，而且對比不同的對比算法都展現出有效的競爭力.同時，在不同拆分個數下，本文算法都能取得穩定的領先.在60和90個作業的大規模問題下，本文算法領先對比算法的GAP穩定在4%左右，而且對比不同的拆分個數和不同的對比算法，本文算法均能保持不低于3%的領先.

表5 J60實驗結果

表6 J90實驗結果

圖5 不同規模算法提高百分比

4 總結與展望

研究了飛機移動裝配線作業調度的作業執行多模式問題，建立了包含項目拆分和多模式資源投入項目調度的數學模型，提出了合理的項目拆分策略和基于時間-資源綜合評估規則的啟發式算法.通過數據實驗，PSS-JTRS算法可以發揮資源評價函數和時間評價函數的優勢，能夠比其他啟發式算法更好的對問題進行求解.在以后的研究中，可以考慮依次啟發式算法為基礎，進一步加入遺傳算法、模擬退火算法等元啟發式算法，使算法加入搜索機制，對飛機移動裝配線作業調度問題進行更系統的優化.