考慮人力資源排班的資源受限項目調度問題建模與優化

朱宏偉， 陸志強

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

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

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

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

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

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

1 考慮人力資源排班的資源受限項目調度問題

1.1 問題描述

某一裝配工位由N項任務組成，記任務集合為J={1,2,…,N}，j∈J為任務編號；第j項任務的緊前任務集合為Pj；i∈Pj為第j項任務的第i項緊前任務；任務j的執行時間為tj，任務一旦開始便無法中斷.目標為最小化裝配總工期T.

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

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

1.2 數學模型

決策變量：

模型：

minT

(1)

s.t.

(2)

(3)

(9)

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

2 算法設計

目前解決RCPSP及其擴展問題的算法大多數是基于任務列表編碼的編碼形式.所有任務在滿足優先關系的前提下隨機(或按規則)構成任務列表，每一條任務列表代表一個解空間，任務在任務列表中的順序代表其執行順序.在已知任務列表的情況下，一般采用串行調度進行解碼，即在滿足資源約束的情況下盡早安排任務開始時間.

然而，在求解RCPSP-ET問題時，由于串行調度未考慮任務開始時間對人力資源利用情況的影響，所以在任務列表編碼方式對應的解空間下串行調度解碼很難獲得較優解.圖1所示為一個僅考慮單種人力資源的示例，圖中橫坐標t為時間，縱坐標R為人力資源編號.根據圖中的項目網絡生成調度計劃時，因為班次S1資源量充足，任務2、3和4通過串行調度均安排在d=0時刻開始執行，此時班次S1的資源使用量為5，班次S2的剩余資源量為1.由于不允許任務跨班次執行，同時班次S2的剩余資源量不足以執行任務5，所以任務5只能在之后的班次開始執行.容易發現，無論如何對換任務列表中任務2、3、4的順序，班次S1的資源占用量始終為5，這幾種情形下任務5都無法在班次S2中執行.

圖1 任務列表與調度結果示例

針對上述任務列表編碼不足的缺點，本文設計了一種改進任務列表編碼方式，并在此基礎上設計了BBGA.改進任務列表編碼是在不改變原優先關系的基礎上，通過添加析取弧的方式來描述部分待確定的優先關系，從而提升串行調度解碼的鄰域搜索能力.同時，針對遺傳算法深度搜索能力弱的缺點，BBGA在遺傳算法所得最優染色體的基礎上，對其進行分段深度搜索，進一步提高算法的求解質量.

2.1 改進任務列表編碼方式

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

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

圖2 改進任務列表與調度結果示例

2.2 BBGA

BBGA結合GA的廣度搜索優勢與分支定界算法的深度搜索優勢，以改進任務列表編碼方式作為GA染色體的表達方式，通過GA獲得初始染色體.在此基礎上，分支定界搜索框架將該染色體作為搜索樹中的初始分支對該染色體進行分段局部回溯，并將每一階段搜索得到的最優染色體作為下一階段的初始染色體，通過這種鄰域搜索機制進一步優化調度結果.

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

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

變異算子采用對換變異，對換層允許進行變異操作的條件是兩個對換層中間所有任務均不存在優先關系.

圖3 交叉操作與變異操作

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

步驟1令染色體層級編號g=1.

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

步驟3按照順序從小到大選擇序號最小的任務jmin∈Ag，按盡早開始原則為任務jmin分配資源，計算開始時間，更新分配后的資源占有量，更新Ag=Ag-jmin.

步驟4如果Ag≠?，轉步驟5；否則，轉步驟7.

步驟6如果Ag≠?，轉步驟5；否則，轉步驟7.

步驟7如果調度計劃未完成，g=g+1，轉步驟2；否則結束算法.

2.2.3分支定界搜索框架 分支定界搜索框架將改進任務列表編碼的層級關系轉換為搜索樹中的樹節點關系，通過事先設定好的步長進行多階段的局部分支(分支過程以深度優先)與回溯.其中，分支定界搜索框架以遺傳算法所求得的最佳染色體作為第一階段的初始解，之后保留每一階段的最佳染色體作為下一階段的初始解.

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

步驟1初始化步長Q，分支起始層n=2，階段s=1，初始染色體設為遺傳算法中適應值最小的染色體.Lbest為該染色體任務列表，M為該染色體的適應值，W為染色體總層數，F為算法終止判斷符號.

步驟2如果Q+n

步驟3令g=n-1.

步驟4確定節點g的候選任務組合集合Cg，從Cg中隨機選擇任務集合Ag生成新的節點g+1，更新Cg=Cg-Ag.通過支配規則判斷能否截除，如果截除則轉步驟6.

步驟5如果存在未分支的任務j?Ag，則表明節點g可以繼續分支，令g=g+1，轉步驟4.否則，將得到的分支與步驟2所保留其余層的任務序列合并，組成新的染色體.調用啟發式進度生成機制對該染色體進行解碼.如果目標函數值優于M，則更新M并記錄最優任務列表Lbest，轉步驟6.

步驟6回溯搜索樹，如果找到某節點g的Cg≠?， 則轉至步驟4；否則，結束分支，轉步驟7.

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

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

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

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

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

定義1記節點q為當前節點，如果節點q由節點q′分支得到，則稱節點q′為節點q的直接根節點.

根據定義1的描述，記直接根節點調度的任務集合為Aq′，當前節點調度的任務集合為Aq，所有任務i∈Aq′的工期之和為dq′，所有任務j∈Aq的工期之和為dq，班次跨度為ds.

定義2若當前節點q中的所有任務j∈Aq均可以合并入其直接根節點q′，且合并后的任務列表與合并前的任務列表解碼所得的調度計劃相同，則稱節點q為重復節點.

圖5 條件3示例

依據上述定義，給出2種支配規則的描述：

規則1(重復節點規則) 當前節點q與其直接根節點q′滿足以下3個條件時，節點q為重復節點，不再對節點q進行分支.

條件1對于任意節點q與其直接根節點q′，如滿足條件dq+dq′>ds，則當前節點為不重復情況.

證明如果滿足dq+dq′>ds，則表明兩節點中所有任務的工期和大于班次時間，當前節點中的任務無法全部合并入其直接根節點，因此當前節點不為重復情況.

條件2如果任務j∈Aq與任意任務i∈Aq′存在時序約束關系，則當前節點不為重復情況.

證明如果兩節點中的任務間存在時序約束關系，則當前節點調度的任務無法全部合并入其根節點，因此當前節點不為重復情況.

規則2(高界規則) 如果當前節點的任務的完成時間超過目前所得最優解，則該節點不再分支.

記目前所得的項目最短工期為MUB.如果任務j∈Ag的完成時間Fj>MUB，則節點g不再分支.新的完整調度計劃完成時，如果滿足FJ

3 數據實驗

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

3.1 與CPLEX的對比

為了驗證算法的有效性，本文將BBGA與CPLEX和GA進行對比，如表1所示.每個規模均取30個算例，每5個算例組成一組進行對照試驗，設定CPLEX的運行閾值為 7 200 s.Gvalue表示計算結果；Gtime表示算法的運算時間；Ggap表示不同算法所得解與本組最優解間的差值.

表1 小規模算例數值實驗結果

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

3.2 與現有文獻的對比

由于CPLEX無法求解中大規模問題，同時關于人力資源調度與RCPSP結合問題的算法研究又十分有限，所以對于大規模算例，本文借鑒文獻[18]中基于插入操作的領域搜索思想，設計了基于局部搜索(LS)的改進啟發式算法作為對比來驗證本文算法的有效性.其中啟發式規則選取最早開始時間(EST)規則和最短執行時間(SPT)規則.表2給出不同算法對于大規模問題的實驗結果對比，其中每組包括10個算例.

表2 中大規模算例數值實驗結果

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

3.3 支配規則效率分析

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

由表3可知，規則1和規則2均能夠通過有效減少搜索樹分支數目來降低算法的運算時間，且當規則1和規則2同時使用時算法的運算時間最短.由圖6可知，使用單一規則時，算法計算時間能夠縮減到無分支規則時計算時間的60%以下(最低為14%)；當同時使用兩種規則時，算法計算時間能夠縮減到無分支規則時計算時間的30%以下(最低為6%)，驗證了本文設計的支配規則能夠有效地降低算法的計算時間，提高算法的計算效率.

表3 不同支配規則效率分析結果

圖6 不同支配規則下計算時間相對無分支規則下計算時間的百分比

3.4 集成決策有效性分析

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

3.5 實例分析

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

根據上述裝配任務優先關系圖以及問題描述，采用本文BBGA和傳統任務列表編碼的遺傳算法(GA-AL)生成不同的任務調度計劃，結果分別如圖8和9所示.圖中陰影表示裝配人員受勞動法規約束而產生的人員不可行期， 即裝配人員處于休息狀態.

表4 中大規模算例數值實驗結果

圖7 某大型工業品部分裝配任務優先關系圖

可以看出，該實例下BBGA所求得的裝配任務總工期T=27，而GA-AL求得的裝配任務總工期T=29.通過進一步分析，發現圖8和9中于班次S1內執行的任務相同，其中圖9中班次S1的人員使用量為7，而圖8中班次S1的人員使用量為6.該情況的出現是因為GA-AL采用的傳統任務列表編碼方式僅考慮了原始的任務優先關系，所以采用串行調度解碼時任務H01C只能在T=0時刻開始.而BBGA采用的改進任務列表編碼能夠在任務H01A和任務H01C之間添加析取弧，因此任務H01C能夠延遲到H01A后開始.班次S1內人員使用量的降低使得班次S2中處于不可行期的人員減少，從而為班次S2保留了更多的人員可用量，使得任務H03C和任務H03B能夠提前至班次S2中同時執行.該結果直觀地驗證了本文 BBGA 的有效性.

圖8 BBGA求得的調度計劃

圖9 GA-AL求得的調度計劃

4 結語

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