陸志強， 宗保氏

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

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

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

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

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

1.1 問題描述

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

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

圖1 單架飛機總裝作業(yè)

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

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

圖2 飛機總裝作業(yè)子項目拆分

1.2 數(shù)學模型

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

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

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

目標函數(shù)：

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

2 PSS-JRTS雙層迭代算法

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

2.1 算法整體步驟

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

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

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

(3)若z

(4)輸出Abest.

2.2 上層PSS算法

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

2.2.1項目初始拆分策略

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

(8)

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

(9)

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

2.2.2拆分調整策略

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

用mi表示子項目i的作業(yè)個數(shù)，αi表示選擇子項目i作為移出作業(yè)子項目的概率：

(10)

圖3 子項目n中可移動作業(yè)

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

?∩Y1j=1,?j∈J}

(11)

(2) 若1

Ynj=1,?j∈J} (1

(12)

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

?j∈J}

(13)

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

2.3 下層JRTS算法

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

2.3.1時間因素評估函數(shù)

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

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

(14)

圖4 作業(yè)j的可排區(qū)間

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

2.3.2資源因素評估函數(shù)

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

Ik=MaxRkt

(15)

Max{Rke+rjmk|t≤e

(16)

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

?j,?m

(17)

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

2.3.3時間-資源綜合評估函數(shù)

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

ftotal(j,m,t)=

(18)

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

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

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

(19)

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

2.3.4JRTS算法步驟

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

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

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

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

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

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

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

3 數(shù)據(jù)實驗

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

3.1 基于優(yōu)先級規(guī)則的啟發(fā)式算法

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

表1 兩類優(yōu)先級規(guī)則

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

3.2 數(shù)據(jù)對比

表2 J10實驗結果

表3 J20實驗結果

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

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

表4 J30實驗結果

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

表5 J60實驗結果

表6 J90實驗結果

圖5 不同規(guī)模算法提高百分比

4 總結與展望

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