基于項(xiàng)目拆分決策的多模式資源投入

陸志強(qiáng)， 宗保氏

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

圖2 飛機(jī)總裝作業(yè)子項(xiàng)目拆分

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

不同于單模式問題，在作業(yè)多模式條件下的資源投入調(diào)度問題中，作業(yè)j有m(m=1,2,…,M)種執(zhí)行模式，分別對應(yīng)的執(zhí)行時(shí)間為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īng)的作業(yè)任務(wù)集合記為子項(xiàng)目i(i=1,2,…,N).項(xiàng)目節(jié)拍周期記為C，對時(shí)間離散化處理，時(shí)間點(diǎn)集合T={t|t=1,2,…,C}，設(shè)U為一個足夠大的正數(shù).

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

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

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

2 PSS-JRTS雙層迭代算法

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

2.1 算法整體步驟

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

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

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

(3)若z

(4)輸出Abest.

2.2 上層PSS算法

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

2.2.1項(xiàng)目初始拆分策略

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

(8)

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

(9)

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

2.2.2拆分調(diào)整策略

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

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

(10)

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

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

?∩Y1j=1,?j∈J}

(11)

(2) 若1

Ynj=1,?j∈J} (1

(12)

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

?j∈J}

(13)

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

2.3 下層JRTS算法

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

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

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

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

(14)

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

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

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

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

Ik=MaxRkt

(15)

Max{Rke+rjmk|t≤e

(16)

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

?j,?m

(17)

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

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

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

ftotal(j,m,t)=

(18)

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

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

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

(19)

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

2.3.4JRTS算法步驟

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

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

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

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

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

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

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

3 數(shù)據(jù)實(shí)驗(yàn)

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

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

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

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

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

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

表2 J10實(shí)驗(yàn)結(jié)果

表3 J20實(shí)驗(yàn)結(jié)果

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

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

表4 J30實(shí)驗(yàn)結(jié)果

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

表5 J60實(shí)驗(yàn)結(jié)果

表6 J90實(shí)驗(yàn)結(jié)果

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

4 總結(jié)與展望

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