朱宏偉， 陸志強(qiáng)

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

資源受限項(xiàng)目調(diào)度(RCPSP)作為一類重要的調(diào)度模型，廣泛存在于制造、建筑等領(lǐng)域，其最大的特點(diǎn)是考慮資源為可更新資源，即資源在任務(wù)結(jié)束后立即釋放，同時(shí)項(xiàng)目進(jìn)程中資源總量不發(fā)生改變.然而，在許多實(shí)際裝配生產(chǎn)系統(tǒng)中，例如飛機(jī)移動(dòng)裝配中，人力資源以排班的形式進(jìn)行裝配生產(chǎn)活動(dòng)，其可用量會(huì)在生產(chǎn)過(guò)程中會(huì)受到排班的影響，因此事先制定的調(diào)度計(jì)劃與實(shí)際的生產(chǎn)進(jìn)度存在很大差距.此時(shí)，調(diào)度的關(guān)鍵在于如何將人力資源進(jìn)行合理的排班，以確定每個(gè)班次下的人力資源數(shù)量，并在排班決策下為任務(wù)安排合理的開(kāi)始時(shí)間，以獲得最小的裝配時(shí)間.此問(wèn)題稱為考慮人力資源排班的資源受限項(xiàng)目調(diào)度問(wèn)題(RCPSP-ET)，其本質(zhì)上是資源受限項(xiàng)目調(diào)度與人力資源排班(ETP)的整合問(wèn)題.由于RCPSP-ET問(wèn)題與傳統(tǒng)RCPSP問(wèn)題的決策范圍不同，現(xiàn)有的模型與算法無(wú)法直接應(yīng)用，所以對(duì)RCPSP-ET問(wèn)題的建模以及算法研究具有重要的實(shí)際與理論意義.

RCPSP作為車間調(diào)度問(wèn)題的一般化，已經(jīng)被證明是非確定性多項(xiàng)式困難問(wèn)題[1]，RCPSP-ET作為其擴(kuò)展問(wèn)題，因此也是非確定性多項(xiàng)式困難問(wèn)題.針對(duì)RCPSP，Brucker等[2-3]采用分支定界算法進(jìn)行求解.雖然分支定界等精確算法能求得問(wèn)題的精確解，但是其求解規(guī)模有限，因此許多文獻(xiàn)關(guān)注于啟發(fā)式和元啟發(fā)式算法的研究，如遺傳算法(GA)[4]，粒子群算法(PSO)[5-6]等.除此之外，Wang等[7-8]在求解RCPSP及其擴(kuò)展問(wèn)題時(shí)采用混合算法，通過(guò)將多種算法進(jìn)行混合，或在原有算法框架上設(shè)計(jì)改進(jìn)機(jī)制，來(lái)提升算法性能.

人力資源排班是為人員安排合適的工作時(shí)間窗以滿足組織內(nèi)部和外部需求的過(guò)程.Bergh等[9]根據(jù)問(wèn)題決策的不同，認(rèn)為研究可以分為5類：在滿足一定條件下決策人員所分配的任務(wù)[10]；確定人員的工作班次[11]；決策人員之間的成組[12]；時(shí)間約束下確定人員的工作時(shí)間[13]以及其他一些決策.然而，Bergh等指出，當(dāng)前研究人力資源排班的文獻(xiàn)缺少人力資源排班與其他調(diào)度問(wèn)題(如機(jī)器調(diào)度、生產(chǎn)調(diào)度)的結(jié)合.在特定的調(diào)度背景下，需將人力資源排班與其他調(diào)度問(wèn)題統(tǒng)籌考慮，才能真正地反映系統(tǒng)的調(diào)度需求.

RCPSP-ET本質(zhì)上是人力資源排班與RCPSP的整合問(wèn)題，目前有極少文獻(xiàn)對(duì)該問(wèn)題進(jìn)行研究.Drezet等[14]將軟件開(kāi)發(fā)過(guò)程抽象為資源受限項(xiàng)目調(diào)度問(wèn)題，在給定人員排班的情況下考慮勞動(dòng)法規(guī)等因素對(duì)任務(wù)安排的影響.由于RCPSP與生產(chǎn)調(diào)度又有一定的相似性，所以人力資源排班與生產(chǎn)調(diào)度結(jié)合的整合問(wèn)題對(duì)于RCPSP-ET的研究具有參考意義.Artigues等[15]考慮工人排班與車間調(diào)度的整合問(wèn)題，設(shè)計(jì)基于整數(shù)規(guī)劃和約束規(guī)劃的混合分支定界算法進(jìn)行求解.Guyon等[16]在探究求解工人排班與生產(chǎn)排班整合問(wèn)題的精確算法時(shí)，為了減小決策變量搜索空間，運(yùn)用割生成求解該整合問(wèn)題，將Benders分解以及CPLEX對(duì)比，驗(yàn)證了算法的效率.Ahmadi-Javid等[17]進(jìn)一步提升整合問(wèn)題的維度，提出結(jié)合加工車間調(diào)度、運(yùn)輸工具調(diào)度以及人力資源排班的整合問(wèn)題.

綜上所述，目前極少學(xué)者考慮將人力資源排班與RCPSP結(jié)合的整合問(wèn)題，然而RCPSP作為一類重要的生產(chǎn)過(guò)程抽象，研究RCPSP-ET問(wèn)題具有重要意義.除此之外，目前解決這些問(wèn)題的算法主要是基于問(wèn)題模型研究而設(shè)計(jì)的精確算法，缺少對(duì)混合算法等高效算法的研究.因此，本文考慮人力資源排班中存在的約束，以最小化完工時(shí)間為目標(biāo)，建立了RCPSP-ET的整數(shù)規(guī)劃模型.同時(shí)，本文設(shè)計(jì)了一種改進(jìn)任務(wù)列表編碼方式，并借鑒混合算法的思路，提出了一種基于分支定界搜索框架的遺傳算法(BBGA)，并在此基礎(chǔ)上提出支配規(guī)則，從而降低算法運(yùn)算時(shí)間，提升算法的求解效率.

1 考慮人力資源排班的資源受限項(xiàng)目調(diào)度問(wèn)題

1.1 問(wèn)題描述

某一裝配工位由N項(xiàng)任務(wù)組成，記任務(wù)集合為J={1,2,…,N}，j∈J為任務(wù)編號(hào)；第j項(xiàng)任務(wù)的緊前任務(wù)集合為Pj；i∈Pj為第j項(xiàng)任務(wù)的第i項(xiàng)緊前任務(wù)；任務(wù)j的執(zhí)行時(shí)間為tj，任務(wù)一旦開(kāi)始便無(wú)法中斷.目標(biāo)為最小化裝配總工期T.

任務(wù)的執(zhí)行需要滿足其人力資源種類和數(shù)量的需求.所有任務(wù)共享人力資源，記人力資源集合、人力資源種類集合分別為E={1,2,…,B}，K={1,2,…,R}，e∈E為人力資源編號(hào)，k∈K為人力資源種類編號(hào)，Ek表示第k類人力資源集合，rjk表示執(zhí)行任務(wù)j所需第k類人力資源的數(shù)量.人力資源無(wú)法搶占，即任務(wù)一旦開(kāi)始，其執(zhí)行過(guò)程不能更換執(zhí)行的人力資源.

裝配過(guò)程人力資源以n班制進(jìn)行裝配生產(chǎn)活動(dòng)(如兩班制，三班制分別對(duì)應(yīng)n=2，n=3).記班次集合S={1,2,…,H}，s∈S為班次編號(hào)；對(duì)時(shí)間進(jìn)行離散化處理，記離散時(shí)間集合為D={1,2,…,V}，d∈D為離散時(shí)間節(jié)點(diǎn)，Ds表示第s個(gè)班次所包含的離散時(shí)間集合.人力資源受到勞動(dòng)法規(guī)的約束，在連續(xù)n個(gè)班次中最多能被安排1個(gè)班次.由于不允許人力資源搶占，而某一人力資源又無(wú)法安排相鄰的班次，所以任務(wù)的執(zhí)行期不允許跨班次.

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

決策變量：

模型：

minT

(1)

s.t.

(2)

(3)

(9)

其中：式(1)表示調(diào)度以最小化裝配工期為目標(biāo)函數(shù)；式(2)表示為任意任務(wù)安排的執(zhí)行時(shí)間必須等于其規(guī)定的執(zhí)行時(shí)間；式(3)表示任意任務(wù)一旦開(kāi)始則不能中斷；式(4)為優(yōu)先關(guān)系約束，表示任意任務(wù)只有在其所有的緊前任務(wù)執(zhí)行結(jié)束后才能開(kāi)始執(zhí)行；式(5)表示任務(wù)的執(zhí)行時(shí)間與裝配總工期的關(guān)系；式(6)表示某類人力資源在某一時(shí)刻中的供應(yīng)量必須滿足該時(shí)刻所有任務(wù)對(duì)該類人力資源的需求量；式(7)為勞動(dòng)力約束，表示任意人力資源在連續(xù)n個(gè)班次中最多能被安排1個(gè)班次；式(8)表示任務(wù)不允許跨班次執(zhí)行；式(9)定義決策變量zjs與決策變量xjd之間的關(guān)系，其中M為無(wú)窮大的數(shù).

2 算法設(shè)計(jì)

目前解決RCPSP及其擴(kuò)展問(wèn)題的算法大多數(shù)是基于任務(wù)列表編碼的編碼形式.所有任務(wù)在滿足優(yōu)先關(guān)系的前提下隨機(jī)(或按規(guī)則)構(gòu)成任務(wù)列表，每一條任務(wù)列表代表一個(gè)解空間，任務(wù)在任務(wù)列表中的順序代表其執(zhí)行順序.在已知任務(wù)列表的情況下，一般采用串行調(diào)度進(jìn)行解碼，即在滿足資源約束的情況下盡早安排任務(wù)開(kāi)始時(shí)間.

然而，在求解RCPSP-ET問(wèn)題時(shí)，由于串行調(diào)度未考慮任務(wù)開(kāi)始時(shí)間對(duì)人力資源利用情況的影響，所以在任務(wù)列表編碼方式對(duì)應(yīng)的解空間下串行調(diào)度解碼很難獲得較優(yōu)解.圖1所示為一個(gè)僅考慮單種人力資源的示例，圖中橫坐標(biāo)t為時(shí)間，縱坐標(biāo)R為人力資源編號(hào).根據(jù)圖中的項(xiàng)目網(wǎng)絡(luò)生成調(diào)度計(jì)劃時(shí)，因?yàn)榘啻蜸1資源量充足，任務(wù)2、3和4通過(guò)串行調(diào)度均安排在d=0時(shí)刻開(kāi)始執(zhí)行，此時(shí)班次S1的資源使用量為5，班次S2的剩余資源量為1.由于不允許任務(wù)跨班次執(zhí)行，同時(shí)班次S2的剩余資源量不足以執(zhí)行任務(wù)5，所以任務(wù)5只能在之后的班次開(kāi)始執(zhí)行.容易發(fā)現(xiàn)，無(wú)論如何對(duì)換任務(wù)列表中任務(wù)2、3、4的順序，班次S1的資源占用量始終為5，這幾種情形下任務(wù)5都無(wú)法在班次S2中執(zhí)行.

圖1 任務(wù)列表與調(diào)度結(jié)果示例

針對(duì)上述任務(wù)列表編碼不足的缺點(diǎn)，本文設(shè)計(jì)了一種改進(jìn)任務(wù)列表編碼方式，并在此基礎(chǔ)上設(shè)計(jì)了BBGA.改進(jìn)任務(wù)列表編碼是在不改變?cè)瓋?yōu)先關(guān)系的基礎(chǔ)上，通過(guò)添加析取弧的方式來(lái)描述部分待確定的優(yōu)先關(guān)系，從而提升串行調(diào)度解碼的鄰域搜索能力.同時(shí)，針對(duì)遺傳算法深度搜索能力弱的缺點(diǎn)，BBGA在遺傳算法所得最優(yōu)染色體的基礎(chǔ)上，對(duì)其進(jìn)行分段深度搜索，進(jìn)一步提高算法的求解質(zhì)量.

2.1 改進(jìn)任務(wù)列表編碼方式

改進(jìn)任務(wù)列表編碼方式借鑒車間調(diào)度中析取弧的思想，通過(guò)添加析取弧的方式，在原先無(wú)直接或間接優(yōu)先關(guān)系的任務(wù)之間增加額外的優(yōu)先關(guān)系，使得解碼過(guò)程中部分并行執(zhí)行的任務(wù)轉(zhuǎn)換為先后執(zhí)行，達(dá)到降低當(dāng)前班次人力資源使用量和提升資源利用率的目的.改進(jìn)任務(wù)列表將獲得新的優(yōu)先關(guān)系的任務(wù)組成一層，每一層對(duì)應(yīng)染色體上的一個(gè)基因.編碼過(guò)程要求：① 后一層中不得包含前一層任務(wù)的直接或間接緊前任務(wù)；② 同一層中的任務(wù)在添加析取弧之前不能存在優(yōu)先關(guān)系；③ 同一層中析取弧方向由最左邊的任務(wù)依次指向最右邊的任務(wù)；④ 同一層中所有任務(wù)的工期和不能大于一個(gè)班次的工期之和.同一層中后序任務(wù)以前序任務(wù)的結(jié)束時(shí)間作為實(shí)際最早可開(kāi)始時(shí)間.只有前一層中的所有任務(wù)都被執(zhí)行完成后，后一層的任務(wù)才可以安排開(kāi)始.

改進(jìn)任務(wù)列表編碼過(guò)程如圖2所示.以圖1中的項(xiàng)目網(wǎng)絡(luò)為例，改進(jìn)任務(wù)列表第1層和第2層分別選擇任務(wù)1和4.進(jìn)行第3層編碼時(shí)，可選擇任務(wù)為任務(wù)2和3.根據(jù)改進(jìn)任務(wù)列表的性質(zhì)，任務(wù)2和3工期之和為8，與班次時(shí)間跨度相等，因此第3層可選擇編碼為{2}、{3}、{2,3}和{3,2}.此時(shí)，隨機(jī)選擇{3,2}作為第3層編碼.按照上述方法繼續(xù)分層，得到的改進(jìn)任務(wù)列表如圖2(a)所示.根據(jù)染色體的編碼，為項(xiàng)目網(wǎng)絡(luò)添加3→2的析取弧.圖2(b)給出了通過(guò)串行調(diào)度對(duì)改進(jìn)任務(wù)列表進(jìn)行解碼所得的調(diào)度計(jì)劃.相比圖1中的調(diào)度計(jì)劃，圖2(b)中的調(diào)度計(jì)劃能夠通過(guò)延遲任務(wù)2的開(kāi)始時(shí)間來(lái)降低班次S1中的人力資源使用量，使得班次S2有足夠的資源來(lái)執(zhí)行任務(wù)5.此時(shí)任務(wù)5的開(kāi)始時(shí)間為8，項(xiàng)目工期T=15.

圖2 改進(jìn)任務(wù)列表與調(diào)度結(jié)果示例

2.2 BBGA

BBGA結(jié)合GA的廣度搜索優(yōu)勢(shì)與分支定界算法的深度搜索優(yōu)勢(shì)，以改進(jìn)任務(wù)列表編碼方式作為GA染色體的表達(dá)方式，通過(guò)GA獲得初始染色體.在此基礎(chǔ)上，分支定界搜索框架將該染色體作為搜索樹(shù)中的初始分支對(duì)該染色體進(jìn)行分段局部回溯，并將每一階段搜索得到的最優(yōu)染色體作為下一階段的初始染色體，通過(guò)這種鄰域搜索機(jī)制進(jìn)一步優(yōu)化調(diào)度結(jié)果.

2.2.1遺傳算法 標(biāo)準(zhǔn)GA分為5個(gè)步驟：① 初始化種群；② 交叉；③ 變異；④ 選擇；⑤ 判斷是否滿足終止條件，不滿足返回②，滿足則終止算法.為保證進(jìn)行交叉變異操作之后所得的改進(jìn)任務(wù)列表仍滿足編碼要求，本文對(duì)傳統(tǒng)的交叉變異算子進(jìn)行改進(jìn)，交叉操作與變異操作如圖3所示.

交叉算子采用單點(diǎn)交叉，在染色體層與層之間隨機(jī)生成交叉點(diǎn)位置.子代染色體保留父代交叉點(diǎn)前的編碼順序，剩余編碼順序根據(jù)母代剔除已選任務(wù)所保留的編碼順序決定.

變異算子采用對(duì)換變異，對(duì)換層允許進(jìn)行變異操作的條件是兩個(gè)對(duì)換層中間所有任務(wù)均不存在優(yōu)先關(guān)系.

圖3 交叉操作與變異操作

2.2.2啟發(fā)式進(jìn)度生成機(jī)制 根據(jù)改進(jìn)任務(wù)列表編碼方式的特點(diǎn)，本文設(shè)計(jì)新的啟發(fā)式進(jìn)度生成方法對(duì)相應(yīng)的染色體(編碼)進(jìn)行解碼.具體決策方法如下：按照層級(jí)從前往后選擇任務(wù)，對(duì)于每層編碼中的任務(wù)，按照順序選擇，第一個(gè)任務(wù)按盡早開(kāi)始原則決策資源的選擇，后序任務(wù)將前序任務(wù)的結(jié)束時(shí)間作為最早可開(kāi)始時(shí)間進(jìn)行安排.按此方法逐步確定每層中任務(wù)的開(kāi)始時(shí)間，獲得完整的調(diào)度計(jì)劃.具體的算法步驟如下：

步驟1令染色體層級(jí)編號(hào)g=1.

步驟2讀取第g層編碼中的任務(wù)集合Ag.

步驟3按照順序從小到大選擇序號(hào)最小的任務(wù)jmin∈Ag，按盡早開(kāi)始原則為任務(wù)jmin分配資源，計(jì)算開(kāi)始時(shí)間，更新分配后的資源占有量，更新Ag=Ag-jmin.

步驟4如果Ag≠?，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟7.

步驟6如果Ag≠?，轉(zhuǎn)步驟5；否則，轉(zhuǎn)步驟7.

步驟7如果調(diào)度計(jì)劃未完成，g=g+1，轉(zhuǎn)步驟2；否則結(jié)束算法.

2.2.3分支定界搜索框架 分支定界搜索框架將改進(jìn)任務(wù)列表編碼的層級(jí)關(guān)系轉(zhuǎn)換為搜索樹(shù)中的樹(shù)節(jié)點(diǎn)關(guān)系，通過(guò)事先設(shè)定好的步長(zhǎng)進(jìn)行多階段的局部分支(分支過(guò)程以深度優(yōu)先)與回溯.其中，分支定界搜索框架以遺傳算法所求得的最佳染色體作為第一階段的初始解，之后保留每一階段的最佳染色體作為下一階段的初始解.

(1) 算法步驟.分支定界搜索框架的具體步驟如下所示：

步驟1初始化步長(zhǎng)Q，分支起始層n=2，階段s=1，初始染色體設(shè)為遺傳算法中適應(yīng)值最小的染色體.Lbest為該染色體任務(wù)列表，M為該染色體的適應(yīng)值，W為染色體總層數(shù)，F(xiàn)為算法終止判斷符號(hào).

步驟2如果Q+n

步驟3令g=n-1.

步驟4確定節(jié)點(diǎn)g的候選任務(wù)組合集合Cg，從Cg中隨機(jī)選擇任務(wù)集合Ag生成新的節(jié)點(diǎn)g+1，更新Cg=Cg-Ag.通過(guò)支配規(guī)則判斷能否截除，如果截除則轉(zhuǎn)步驟6.

步驟5如果存在未分支的任務(wù)j?Ag，則表明節(jié)點(diǎn)g可以繼續(xù)分支，令g=g+1，轉(zhuǎn)步驟4.否則，將得到的分支與步驟2所保留其余層的任務(wù)序列合并，組成新的染色體.調(diào)用啟發(fā)式進(jìn)度生成機(jī)制對(duì)該染色體進(jìn)行解碼.如果目標(biāo)函數(shù)值優(yōu)于M，則更新M并記錄最優(yōu)任務(wù)列表Lbest，轉(zhuǎn)步驟6.

步驟6回溯搜索樹(shù)，如果找到某節(jié)點(diǎn)g的Cg≠?， 則轉(zhuǎn)至步驟4；否則，結(jié)束分支，轉(zhuǎn)步驟7.

步驟7若F為假，則更新s=s+1，n=Q+n，轉(zhuǎn)至步驟2；否則滿足終止條件，轉(zhuǎn)步驟8.

步驟8若F為真，則滿足終止條件，結(jié)束算法.

圖4所示為分支定界搜索框架的示例，初始染色體編碼為{1}、{4}、{3,2}、{5}、{6,7}、{8}，設(shè)定步長(zhǎng)Q=2，分支起始層n=2.在階段s=1時(shí)，回溯第2和第3層任務(wù)，回溯任務(wù)集合J1={2,3,4}，通過(guò)回溯分支得到階段s=1的最優(yōu)染色體為{1}、{4}、{2,3}、{5}、{6,7}、{8}.在階段s=2時(shí)，將階段s=1的最優(yōu)染色體作為初始染色體，回溯第4和第5層任務(wù)，回溯任務(wù)集合J2={5,6,7}，通過(guò)回溯分支得到階段s=2處的最優(yōu)染色體為{1}、{4}、{2,3}、{5}、{6}、{7}、{8}.由于此時(shí)Q+n=6，滿足終止條件，因此將分支定界算法得到的最優(yōu)染色體輸出.

圖4 分支定界搜索框架示例

(2) 支配規(guī)則.為了提升分支定界算法的效率，本文提出2種支配規(guī)則，用于分支過(guò)程中剪除被支配的分支.為了方便支配規(guī)則的描述，事先給出以下定義：

定義1記節(jié)點(diǎn)q為當(dāng)前節(jié)點(diǎn)，如果節(jié)點(diǎn)q由節(jié)點(diǎn)q′分支得到，則稱節(jié)點(diǎn)q′為節(jié)點(diǎn)q的直接根節(jié)點(diǎn).

根據(jù)定義1的描述，記直接根節(jié)點(diǎn)調(diào)度的任務(wù)集合為Aq′，當(dāng)前節(jié)點(diǎn)調(diào)度的任務(wù)集合為Aq，所有任務(wù)i∈Aq′的工期之和為dq′，所有任務(wù)j∈Aq的工期之和為dq，班次跨度為ds.

定義2若當(dāng)前節(jié)點(diǎn)q中的所有任務(wù)j∈Aq均可以合并入其直接根節(jié)點(diǎn)q′，且合并后的任務(wù)列表與合并前的任務(wù)列表解碼所得的調(diào)度計(jì)劃相同，則稱節(jié)點(diǎn)q為重復(fù)節(jié)點(diǎn).

圖5 條件3示例

依據(jù)上述定義，給出2種支配規(guī)則的描述：

規(guī)則1(重復(fù)節(jié)點(diǎn)規(guī)則) 當(dāng)前節(jié)點(diǎn)q與其直接根節(jié)點(diǎn)q′滿足以下3個(gè)條件時(shí)，節(jié)點(diǎn)q為重復(fù)節(jié)點(diǎn)，不再對(duì)節(jié)點(diǎn)q進(jìn)行分支.

條件1對(duì)于任意節(jié)點(diǎn)q與其直接根節(jié)點(diǎn)q′，如滿足條件dq+dq′>ds，則當(dāng)前節(jié)點(diǎn)為不重復(fù)情況.

證明如果滿足dq+dq′>ds，則表明兩節(jié)點(diǎn)中所有任務(wù)的工期和大于班次時(shí)間，當(dāng)前節(jié)點(diǎn)中的任務(wù)無(wú)法全部合并入其直接根節(jié)點(diǎn)，因此當(dāng)前節(jié)點(diǎn)不為重復(fù)情況.

條件2如果任務(wù)j∈Aq與任意任務(wù)i∈Aq′存在時(shí)序約束關(guān)系，則當(dāng)前節(jié)點(diǎn)不為重復(fù)情況.

證明如果兩節(jié)點(diǎn)中的任務(wù)間存在時(shí)序約束關(guān)系，則當(dāng)前節(jié)點(diǎn)調(diào)度的任務(wù)無(wú)法全部合并入其根節(jié)點(diǎn)，因此當(dāng)前節(jié)點(diǎn)不為重復(fù)情況.

規(guī)則2(高界規(guī)則) 如果當(dāng)前節(jié)點(diǎn)的任務(wù)的完成時(shí)間超過(guò)目前所得最優(yōu)解，則該節(jié)點(diǎn)不再分支.

記目前所得的項(xiàng)目最短工期為MUB.如果任務(wù)j∈Ag的完成時(shí)間Fj>MUB，則節(jié)點(diǎn)g不再分支.新的完整調(diào)度計(jì)劃完成時(shí)，如果滿足FJ

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

本文算法運(yùn)用C#(Visual Studio 2015)編程實(shí)現(xiàn)，測(cè)試實(shí)驗(yàn)在Internet Core i7處理器，3.4 GHz主頻，8 GB內(nèi)存的測(cè)試平臺(tái)上進(jìn)行.本文的測(cè)試算例選取自PSPLIB算例庫(kù)，由于人力資源排班引入的資源不可行期會(huì)造成項(xiàng)目工期較長(zhǎng)，所以需對(duì)算例進(jìn)行改造.改造參數(shù)包括對(duì)班次n、資源系數(shù)F、班次長(zhǎng)度S和分支定界步長(zhǎng)Q進(jìn)行設(shè)定，其中資源系數(shù)F指實(shí)際使用資源量與算例庫(kù)原始資源量的比值，即F=R/R0.對(duì)于小規(guī)模算例規(guī)模(J10，J12，J14，J16，J18)，本文設(shè)定參數(shù)n、F、S和Q分別為3、1、8、4.對(duì)于中大規(guī)模算例(J30，J60，J90)，本文設(shè)定參數(shù)n、F、S和Q分別為3、2、11、5.

3.1 與CPLEX的對(duì)比

為了驗(yàn)證算法的有效性，本文將BBGA與CPLEX和GA進(jìn)行對(duì)比，如表1所示.每個(gè)規(guī)模均取30個(gè)算例，每5個(gè)算例組成一組進(jìn)行對(duì)照試驗(yàn)，設(shè)定CPLEX的運(yùn)行閾值為 7 200 s.Gvalue表示計(jì)算結(jié)果；Gtime表示算法的運(yùn)算時(shí)間；Ggap表示不同算法所得解與本組最優(yōu)解間的差值.

表1 小規(guī)模算例數(shù)值實(shí)驗(yàn)結(jié)果

從表1看出，在小規(guī)模算例實(shí)驗(yàn)中，BBGA 在可接受時(shí)間內(nèi)能夠求得較優(yōu)的結(jié)果.對(duì)于大多數(shù)J10和J12規(guī)模的算例，CPLEX可求得問(wèn)題的最優(yōu)解，而GA與CPLEX之間的Ggap值小于4.0%，BBGA 與CPLEX之間的Ggap值小于2.4%.并且隨著算例規(guī)模以及復(fù)雜度的增加(J14～J18)，CPLEX在許多情況下無(wú)法求得最優(yōu)解，而GA和BBGA仍可求得較優(yōu)解.雖然BBGA計(jì)算時(shí)間有所提升，但是相比較GA，其求解質(zhì)量能夠提升2%左右，表現(xiàn)出一定的優(yōu)勢(shì).

3.2 與現(xiàn)有文獻(xiàn)的對(duì)比

由于CPLEX無(wú)法求解中大規(guī)模問(wèn)題，同時(shí)關(guān)于人力資源調(diào)度與RCPSP結(jié)合問(wèn)題的算法研究又十分有限，所以對(duì)于大規(guī)模算例，本文借鑒文獻(xiàn)[18]中基于插入操作的領(lǐng)域搜索思想，設(shè)計(jì)了基于局部搜索(LS)的改進(jìn)啟發(fā)式算法作為對(duì)比來(lái)驗(yàn)證本文算法的有效性.其中啟發(fā)式規(guī)則選取最早開(kāi)始時(shí)間(EST)規(guī)則和最短執(zhí)行時(shí)間(SPT)規(guī)則.表2給出不同算法對(duì)于大規(guī)模問(wèn)題的實(shí)驗(yàn)結(jié)果對(duì)比，其中每組包括10個(gè)算例.

表2 中大規(guī)模算例數(shù)值實(shí)驗(yàn)結(jié)果

由表2可知，在求解大規(guī)模算例時(shí)，分支定界搜索框架對(duì)于遺傳算法能夠取得2%以上優(yōu)化效果，同時(shí)，基于局部搜索的改進(jìn)啟發(fā)式算法與BBGA的偏差約為6%，證明了BBGA的優(yōu)越性.但是，隨著算例規(guī)模的增加，BBGA計(jì)算時(shí)間增長(zhǎng)較快，并且每個(gè)算例的計(jì)算時(shí)間差異較大，其原因是回溯集合的數(shù)目隨著算例規(guī)模的增加而增長(zhǎng)，同時(shí)不同算例下回溯集合的任務(wù)數(shù)目差異較大.

3.3 支配規(guī)則效率分析

支配規(guī)則作為BBGA的重要組成部分，需要驗(yàn)證其對(duì)算法運(yùn)算效率的影響.表3給出J12中Q=12時(shí)，本文算法分別同時(shí)使用規(guī)則1和規(guī)則2(Rule 1&2)、僅使用規(guī)則1(Rule 1)、僅使用規(guī)則2(Rule 2)和不使用支配規(guī)則(None)時(shí)的運(yùn)行時(shí)間以及搜索樹(shù)的分支數(shù)目.其中設(shè)定參數(shù)n、F、S和Q分別為3、1、8、4，每組實(shí)驗(yàn)包含3個(gè)算例，Gnum欄表示在某一規(guī)則下搜索樹(shù)的分支數(shù)目.圖6顯示了不同支配規(guī)則下算法的運(yùn)行時(shí)間相對(duì)不使用支配規(guī)則時(shí)算法計(jì)算時(shí)間所占的百分比.

由表3可知，規(guī)則1和規(guī)則2均能夠通過(guò)有效減少搜索樹(shù)分支數(shù)目來(lái)降低算法的運(yùn)算時(shí)間，且當(dāng)規(guī)則1和規(guī)則2同時(shí)使用時(shí)算法的運(yùn)算時(shí)間最短.由圖6可知，使用單一規(guī)則時(shí)，算法計(jì)算時(shí)間能夠縮減到無(wú)分支規(guī)則時(shí)計(jì)算時(shí)間的60%以下(最低為14%)；當(dāng)同時(shí)使用兩種規(guī)則時(shí)，算法計(jì)算時(shí)間能夠縮減到無(wú)分支規(guī)則時(shí)計(jì)算時(shí)間的30%以下(最低為6%)，驗(yàn)證了本文設(shè)計(jì)的支配規(guī)則能夠有效地降低算法的計(jì)算時(shí)間，提高算法的計(jì)算效率.

表3 不同支配規(guī)則效率分析結(jié)果

圖6 不同支配規(guī)則下計(jì)算時(shí)間相對(duì)無(wú)分支規(guī)則下計(jì)算時(shí)間的百分比

3.4 集成決策有效性分析

由表4可知，基于RCPSP-ET集成決策的GA以及BBGA較基于“人員-任務(wù)”順序決策的GA-SD分別能夠取得均值約為5%和7%的優(yōu)化效果.同時(shí)，相比GA，GA-SD計(jì)算時(shí)間沒(méi)有明顯的縮短.因此，RCPSP-ET集成決策在決策方式上優(yōu)于傳統(tǒng)的“人員-任務(wù)”順序決策，更加適用于實(shí)際裝配生產(chǎn)中裝配計(jì)劃制定以及人力資源排班.

3.5 實(shí)例分析

為了更直觀地闡明本文方法的有效性，本節(jié)以某大型工業(yè)品裝配過(guò)程中某一部分任務(wù)為例進(jìn)行分析.該部分共計(jì)16項(xiàng)裝配任務(wù)，裝配任務(wù)優(yōu)先關(guān)系如圖7所示.其中，企業(yè)根據(jù)任務(wù)之間的順序關(guān)系為各任務(wù)安排編號(hào)，括號(hào)內(nèi)的數(shù)字分別表示任務(wù)所需操作時(shí)間和任務(wù)執(zhí)行時(shí)所需的裝配人員數(shù)量，例如“H03A(2,4)”表示任務(wù)H03A的操作時(shí)間為2，所需裝配人員數(shù)量為4.任務(wù)H00和任務(wù)H05分別表示虛擬開(kāi)始任務(wù)和虛擬結(jié)束任務(wù)，其任務(wù)所需操作時(shí)間和裝配人員需求量均為0.裝配人員以兩班制的形式執(zhí)行裝配任務(wù)，其總數(shù)為11人，每一班次的長(zhǎng)度為8 h.假定開(kāi)始階段有4名裝配人員處于休息狀態(tài).

根據(jù)上述裝配任務(wù)優(yōu)先關(guān)系圖以及問(wèn)題描述，采用本文BBGA和傳統(tǒng)任務(wù)列表編碼的遺傳算法(GA-AL)生成不同的任務(wù)調(diào)度計(jì)劃，結(jié)果分別如圖8和9所示.圖中陰影表示裝配人員受勞動(dòng)法規(guī)約束而產(chǎn)生的人員不可行期， 即裝配人員處于休息狀態(tài).

表4 中大規(guī)模算例數(shù)值實(shí)驗(yàn)結(jié)果

圖7 某大型工業(yè)品部分裝配任務(wù)優(yōu)先關(guān)系圖

可以看出，該實(shí)例下BBGA所求得的裝配任務(wù)總工期T=27，而GA-AL求得的裝配任務(wù)總工期T=29.通過(guò)進(jìn)一步分析，發(fā)現(xiàn)圖8和9中于班次S1內(nèi)執(zhí)行的任務(wù)相同，其中圖9中班次S1的人員使用量為7，而圖8中班次S1的人員使用量為6.該情況的出現(xiàn)是因?yàn)镚A-AL采用的傳統(tǒng)任務(wù)列表編碼方式僅考慮了原始的任務(wù)優(yōu)先關(guān)系，所以采用串行調(diào)度解碼時(shí)任務(wù)H01C只能在T=0時(shí)刻開(kāi)始.而B(niǎo)BGA采用的改進(jìn)任務(wù)列表編碼能夠在任務(wù)H01A和任務(wù)H01C之間添加析取弧，因此任務(wù)H01C能夠延遲到H01A后開(kāi)始.班次S1內(nèi)人員使用量的降低使得班次S2中處于不可行期的人員減少，從而為班次S2保留了更多的人員可用量，使得任務(wù)H03C和任務(wù)H03B能夠提前至班次S2中同時(shí)執(zhí)行.該結(jié)果直觀地驗(yàn)證了本文 BBGA 的有效性.

圖8 BBGA求得的調(diào)度計(jì)劃

圖9 GA-AL求得的調(diào)度計(jì)劃

4 結(jié)語(yǔ)

本文以考慮人力資源排班的資源受限項(xiàng)目調(diào)度問(wèn)題為研究對(duì)象，建立離散時(shí)間下考慮勞動(dòng)力約束的數(shù)學(xué)模型.針對(duì)問(wèn)題的特點(diǎn)，提出了改進(jìn)任務(wù)列表編碼方式.為了提升算法的深度搜索能力，根據(jù)編碼特點(diǎn)設(shè)計(jì)分支定界搜索框架，對(duì)遺傳算法得到的染色體進(jìn)行分段深度搜索.在支配規(guī)則中，通過(guò)分析判斷重復(fù)節(jié)點(diǎn)剪除被支配的分支，避免計(jì)算不必要的分支，提高算法的計(jì)算時(shí)間.數(shù)據(jù)實(shí)驗(yàn)表明，對(duì)于小規(guī)模算例，本文算法與CPLEX最優(yōu)解的差值保持在3.2%以下，部分算例相比遺傳算法能提高2%優(yōu)化效果；對(duì)于大規(guī)模算例，分支定界算法能夠在遺傳算法所得解的基礎(chǔ)上取得2%以上優(yōu)化效果；在計(jì)算時(shí)間方面，本文設(shè)計(jì)的支配規(guī)則能夠?qū)⑺惴ㄓ?jì)算時(shí)間降低到未使用支配規(guī)則的30%以下；與此同時(shí)，相比較傳統(tǒng)的“人員-任務(wù)”順序決策，RCPSP-ET集成決策能夠更加有效地優(yōu)化決策過(guò)程，獲得更好的人員排班計(jì)劃和任務(wù)執(zhí)行計(jì)劃.未來(lái)可以在考慮人力資源排班的資源受限項(xiàng)目問(wèn)題中進(jìn)一步研究人力資源多技能對(duì)排班和項(xiàng)目工期的影響.