考慮柔性資源技能進化的多項目組合調度問題

陸志強，陳丞

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

目前，大型設備裝配過程的調度問題可以被抽象為資源受限項目調度問題[1]及其擴展問題.對于飛機移動裝配線來說，多架飛機連續通過工位則可以看作多個串行項目的組合調度問題，對項目作業及資源建立合理的調度計劃仍是企業生產管理的重點.在飛機裝配中，人力資源是關鍵資源之一，然而目前生產中人力資源技能水平不高、結構不合理的現狀未得到根本性改變.技能水平較低的人力資源可能會導致更長的作業時間和更差的產品質量，而人力資源結構不合理則會導致部分人力資源的缺失以及部分人力資源的浪費.因此對企業長期發展來說，明確人力資源結構同時構建合理高效的柔性人力資源培訓體系極為重要.由于人力資源可以通過在項目作業中不斷學習來提升技能水平，企業中一種常見的內部人力資源培訓方法是在實際項目作業中培訓技能水平較低的人力資源.但這種培訓方式可能與生產相沖突，企業投入的人力資源整體技能水平過低會導致項目逾期完成或者更多的資源投入.為解決此問題，本文提出考慮柔性資源技能進化的多項目組合優化調度問題，將項目作業調度與人力資源培訓進行耦合建模研究，其目的為在滿足生產需求的條件下更快更低成本地培訓符合要求的柔性人力資源.

考慮柔性資源技能進化的多項目組合優化調度問題具體可分為兩個部分：單項目內的作業開始時間與人力資源調度，多項目下人力資源培訓方向的確定.在單個項目內，員工的技能水平變化不大，可以看作固定技能水平的多技能資源約束項目調度問題.Bellenguez 等[2]率先對帶有技能水平的基本多技能資源約束問題進行了研究，認為其可看成多模式資源約束項目調度問題的擴展，并證明了該問題是NP-hard 問題.Lian 等[3]在漿液生產系統中考慮了工人技能和熟練程度的差異，同時解決了工作人員分組、單元加載和任務分配.Barz 等[4]使用離散時間馬爾可夫決策過程解決了電訊業中的具有分層技能結構的多技能資源的資源分配問題.Walter 等[5]構造了混合整數線性模型以最大程度地減少不同技能水平的多技能工人團隊規模，并設計了三種構造試探法加速商用求解器的求解.任逸飛等[6]認為資源技能水平會對作業時間產生影響，并將資源分為關鍵和輔助2 類，以最小化項目總工期為目標建立優化模型.Maghsoudlou 等[7]同時考慮了員工的技能水平會引起作業返工風險的差異，并將以項目的執行成本和作業的返工風險作為目標函數.上述研究均認為技能水平的差異會對作業的時間和質量產生一定影響，并在考慮該影響的情況下對單項目內固定技能水平的項目調度問題進行了求解優化.

當問題擴展成多個項目，員工的技能水平變化情況則應當被考慮，同時需要對該變化引起的生產調度的影響進行具體的討論.Liu 等[8]在動態蜂窩制造系統中考慮了工人的學習和遺忘作用，認為學習和遺忘作用使得工作站的生產率變化，有必要重新分配多技能工人.Mehmanchi 等[9]在多技能項目調度中考慮到學習和遺忘對人類技能的影響，并利用線性近似技能效率的指數變化，通過實驗驗證了其簡化近似的有效性.Chen 等[10]研究了IT 行業中考慮員工學習能力的人員分配，綜合考慮了員工整體技能水平的提高，公司的發展效率和產品質量，員工技能增長按照學習曲線.Hossein 等[11]考慮了資源受限問題中的資源學習情況，利用社交網絡來研究不同資源間效率的交互情況.Huan 等[12]在并行生產系統中同時考慮了員工獨自的學習經歷和同組員工間的相互學習，做出員工分組和分配決策，以最大化制造系統的產出量.Bruecker 等[13]在飛機維修行業中首先得到便宜的勞動力組合然后求解了最佳可行的培訓計劃.以上研究雖考慮了員工技能水平的變化，但其主要目標仍然是對項目的調度，而不是人力資源的培訓.

總之，目前對大型工業品裝配過程中考慮人力資源培訓的研究較少，并且研究目標多為最大化人力資源技能水平的增長量，這種優化可能會導致單個項目資源技能水平增長快而后續項目中增長緩慢.針對現有文獻的不足，本文以飛機裝配線為背景，在已知期望人力資源結構的條件下，通過學習曲線來描述項目進行中人力資源的技能增長過程，以最小化人力資源結構達到理想結構所經歷過的項目個數和投入總成本為目標，建立了多目標混合整數規劃模型，并設計了相應的混合多目標教學優化算法進行求解.

1 問題描述及數學模型

1.1 問題描述與基本假設

某企業一條生產線上需連續裝配N 架飛機，各飛機的型號序列已知，保證各架飛機按序串行生產，不可并行.每裝配一架飛機都被抽象成執行一個項目，每個項目由多個作業組成，各作業只有在滿足時序約束的條件下才可以執行，并需要一定數量一定技能的人力資源，其實際作業時間由分配的人力資源的技能等級決定.現有人力資源的技能水平和目標人力資源技能需求已知.各資源在執行作業的過程中，只增加已有技能的熟練度，而不會增加新的技能.由于技能效率增長緩慢，假設在項目執行過程中技能效率是不變的，只有在項目結束時才計算技能效率的增長量，并代入到下一個項目中.該問題的目標是在保證各個項目在其給定工期內完成的條件下，最小化每個項目的資源使用成本和最小化現有資源達到目標要求所經過的項目個數.

1.2 參數與變量

本文模型中所涉及的決策變量與參數分別如表1 和表2 所示.

表1 模型所涉決策變量Tab.1 Decision variables in the model

表2 模型所涉參數Tab.2 Parameters in the model

1.3 技能效率與技能增長模型

人力資源的技能效率η（0 ＜η ≤1）代表著作業的基準作業時間tij與其執行作業實際作業時間的比值，如果作業只需要一個資源，則有=tij/η.人力資源的技能效率η 越接近1，其實際作業時間越接近作業最小時間.當作業需要多個資源時，實際作業時間取決于所投入資源的平均技能效率，如式（1）所示：

人力資源的技能效率增長是普遍存在的，只要人力資源使用技能，其技能效率就會自動增長.目前，對學習過程的建模方式種類眾多，但根據Grosse等[14]的分析，其中最有效的仍是Wright 所提出的指數學習曲線[15]：

式（2）代表著重復生產一件產品的單件生產時間和作業次數的關系，T1和Tu分別表示生產第1 個和第u 個產品所用時間，a 表示學習效率（0

雖然人力資源的技能效率能夠增長，但是這種增長速率是緩慢的，因此可以假設在單個項目執行過程中人力資源技能效率是不變的，只有在當前項目結束切換到下一個項目時才計算其技能效率的增長量.對人力資源在項目中使用技能s 執行作業的時間進行求和，代入到式（3）得到資源技能效率和累積技能使用時間在項目切換中的變換公式：

1.4 數學模型

其中，式（6）表示最小化現有人力資源達到目標人力資源結構所經歷過的項目個數；式（7）表示最小生產總成本；式（8）表示只有當所有人力資源都達到要求時培訓才算完成；式（9）表示決策變量zijsr與yijrds間的關系；式（10）表示各個作業在工期內都可以被執行完成；式（11）表示時序約束，每一項作業在其所有緊前作業完成后才開始；式（12）表示作業一旦開始就不能結束；式（13）表示作業在滿足技能需求的情況下才能進行；式（14）表示資源是非搶占式的；式（15）表示資源只能執行作業一種技能；式（16）表示資源同時只能執行一項作業；式（17）表示每個現有人力資源最多只能培訓成一個目標資源；式（18）表示所有目標資源都需要得到培訓；式（19）表示決策變量的取值范圍.

2 算法設計原理

本文問題屬于NP-hard 問題，并且即使各個項目的規模很小，整合起來的規模仍然很大，很難在有效時間內得到精確解，因此可行且有效的方法是通過智能搜索算法獲取近似的Pareto 解集.本文設計了一種混合多目標教學優化算法（HMOTLBO）.在該算法中，對資源培訓方向和項目的具體調度方案編碼，并在傳統教學優化算法中的教學階段引入自適應變化因子，在學習階段將自我學習與向他人學習相結合，同時在迭代中引入鄰域搜索以提高算法的局部搜索能力.

2.1 問題復雜性分析

關于本文問題的計算復雜性，有如下性質：

性質1本文問題具有NP-Hard 的計算復雜性.

證當所有各種技能只有一種水平且各資源均為單技能資源并且技能無法進化時，即=1，ar=0 時，本文問題退化為多個基本RCPSP 問題.由于RCPSP 問題具有NP-Hard 的計算復雜性，依據調度問題計算復雜性遞階關系，本文問題同樣屬于NP-Hard 問題.證畢.

2.2 編碼與解碼

本文在對解碼編碼時需要同時考慮到項目內的作業次序，為作業分配一定數量的資源，人力資源在作業中使用恰當的技能以及人力資源的培養方向.由于需要處理的信息過多，傳統的任務列表編碼很難求得較優解.本文引用Maghsoudlou 等[7]的多層鏈表編碼同時考慮到作業、技能和資源三個層面，可以有效地解決該問題，同時本文對其加以改進，將資源培養方向囊括進去.如圖1 所示，編碼可分為兩層，第一層為資源培訓方向，共有1 行R 列，R 為現有資源數量.其編碼值為非負整數，正整數代表其要培養成的資源序號，0 代表其沒有培訓方向，例如現有1號資源沒有培訓方向，而現有2 號資源需要培訓為目標1 號資源.編碼第二層為調度編碼，共有2 +max qijs行和L 列，L 為項目的各種活動所需的技能總和.第1 行為作業調度次序，第2 行為技能分配次序，其余為資源對作業的分配.其編碼值為隨機生成的0 到1 的小數.

編碼的解碼過程主要包括兩部分：一是對單個項目內的作業和資源進行具體的調度；二是隨著項目計算并更新資源的總投入以及資源技能效率的變化情況.單項目內的調度存在兩種方式，一種是資源未培訓達標時同時考慮資源培訓和成本的調度方式，另一種是資源培訓達標后只考慮成本的調度方式.整體解碼具體步驟如圖1 所示。

圖1 編碼Fig.1 Coding

Step1：項目i=1，初始成本C=0；

Step2：判斷資源是否全部達標，如果達標則輸出f1=i-1，轉step4；否則轉step3；

Step3：按照最小成本與資源培訓的方式對項目i進行調度，并計算項目i 所用成本Ci，C=C+Ci.i=i+1，轉step2；

Step4：按照最小成本方式對項目i 進行調度，并計算項目i 所用成本Ci，C=C+Ci；

Step5：判斷i 是否等于項目總數N，如果不等于則輸出i=i+1，轉step4；否則，則輸出f2=C，同時解碼過程結束.

以一個3 作業、3 技能、每個技能2 水平的示例來對編碼中單項目的調度方案解碼進行說明.其中每種技能的等級劃分界限均為0.7（即技能效率在0～0.7 間的等級為1 級，技能效率在0.7～1 間的等級為2 級）.作業次序與技能需求如表3 所示，現有資源技能效率和目標資源等級分別如表4 和表5所示.根據以上信息對圖1 中的編碼進行單項目的解碼.

表3 作業次序與技能需求Tab.3 Predecessor sets and skills required

表4 現有資源技能效率Tab.4 Skill efficiency of existing resources

表5 目標資源技能等級Tab.5 Target resource skill level

單項目內具體的調度方案由三部分組成：作業執行次序、技能分配次序和資源對作業的分配.作業執行次序由調度編碼的第一行來決定.將每確定一個作業次序視為一個階段step，初始階段為1.在每一階段中，將所有緊前作業已完成的作業放入到可開始作業集合中，將可開始作業數目與調度編碼中（1，step）的編碼值相乘并向上取整得到A 值，則將要開始作業為可開始作業集合中的第A 個作業，如表6 中階段1 的可開始作業為作業1 和2，A 值為2，最先開始的作業為可開始作業集合中的第2 個作業即作業2.每一階段都更新可開始作業集合，并在確定作業次序后將其從可開始作業集合中刪除，重復以上步驟，直到所有作業分配完成.由表6 得到最終作業調度次序為2，1，3.

表6 作業次序的確定Tab.6 Sequence of activities specified

在得到作業次序的基礎上，需確定技能分配的次序，該次序由調度編碼的第二行來決定.將每確定一個技能分配次序視為一個階段step，初始階段為1.已知作業2 需要技能2 和技能3，將待分配的技能數量與調度編碼中（2，step）的編碼值相乘并向上取整得到A 值，則將要分配的技能為待分配技能集合中的第A 個技能，如表7 中最先分配的為作業2 的技能2.當技能分配過后將其從待分配技能中刪去，重復上述過程，直到所有作業技能分配完成.其最終技能分配結果如表7 所示.

表7 作業技能的分配Tab.7 Skills to activities assigned

第三步需要對已分配完成的技能進行資源分配，由調度編碼的第3 行到最后一行來決定.在為作業技能分配資源時，首先要確定擁有該技能的可分配資源，如果某資源已經分配過該作業的其它技能，那么該資源不能成為該作業該技能的可分配資源.分配資源時存在兩種分配方式，分別對應單項目內的兩種調度方式，在分配前需要判斷資源是否全部培訓完成，如果完成則采用只考慮成本的調度方式，否則采用同時考慮成本和培訓的調度方式.采用只考慮成本的調度方式分配資源時，對于某作業中某技能的第i 個需求，將可分配資源數量與調度編碼中（2+i，step）的編碼值相乘并向上取整得到A 值，然后將可分配資源中的第A 個資源分配給該技能需求.依次對作業技能需求分配資源，直到所有作業技能都有資源執行.其最終資源分配結果如表8 所示.

同時考慮成本和培訓的調度方式在分配資源時需考慮資源達到要求的培訓時間，以使資源更大概率地分配到使整體資源技能效率增長快的技能上.具體步驟如下：1）確定各資源的技能效率與目標資源技能效率的差值，已培訓完成的資源和無培訓目標的資源技能效率差值為0.2）判斷效率差值不為0的資源數目：如果全部可分配資源的數目效率差值均為0，將可分配資源數量與調度編碼（2+i，step）位相乘并向上取整得到A 值，然后將可分配資源中的第A 個資源分配給該技能需求；如果只有一個資源技能差距不為0，則將其分配給該技能需求；如果多個資源技能差距不為0，則按照輪盤賭選擇法在技能差距不為0 的資源中選擇資源分配給該技能需求.其最終資源分配結果如表8 所示.

表8 兩種方式分配資源Tab.8 Resources allocated in two ways

2.3 教學優化

教學優化算法是模仿課堂教學的算法，通過“教”階段來提高班級中學員的整體水平，通過不同學員之間“學”階段再來提高個體成績，從而優化種群.在算法的每一次迭代過程中，都將未被支配的個體作為老師，其余個體作為學生.

“教”階段以一個隨機過程來表示老師幫助學生提高水平.對于第i 個學生Xi，對其具體調度方案編碼的更新機制如下：

其中，Teacher 個體是在Pareto 前沿中隨機選擇的個體，Mean（t）=代表所有個體的平均值，TF=round[1+rand（0，1）]代表著向均值更改的幅度.t 為當前迭代次數，Tmax為最大迭代次數，在迭代初期（1-t/Tmax）的值較大，可以快速向最優個體周圍靠攏；隨著迭代進行，（t/Tmax）越來越大，個體維持自身狀態能力增強，減緩了向最優個體靠近的速度，避免過早的聚集于教師周圍.

“學”階段，學生根據自己梯度信息進行自我學習.對于第i 個學生Xi（t），對其調度方案編碼的更新機制表示如下：

式（20）表示第i 個學生自我學習過程中的連續變化.但如果在連續兩代值中值沒有變化，那么第i 個學生的值將不會更新.這可能會降低算法的搜索能力，尤其是在迭代過程的后期.為了提高搜索能力，如果第i 個學生的位置連續兩代保持不變，將通過小組討論進行交互式學習以提高水平.對于第i 個學生Xi（t），對其調度方案編碼的更新機制表示如下：

其中Xk（t）代表著從學生中隨機選擇的其它個體，dominate 代表著完全支配.

2.4 鄰域搜索

為了增強算法的局部搜索能力，本文在每次迭代過程中加入鄰域搜索策略，對Pareto 前沿中的解在鄰域內進行搜索改進.設定鄰域結構集合Nk={N1，N2，N3}，對種群中個體x 從第一個鄰域結構N1開始擾動，若獲得改進解x′，則令x=x′，并返回第一個鄰域結構重新開始迭代，直到無法改進則執行下一個鄰域結構.本文采用如下三種鄰域結構：

1）交換資源培訓方向：在相同技能種類資源中隨機選中兩個資源，交換兩資源的培訓方向.

2）交換作業次序：在確定作業次序階段，隨機選擇step，將確定其A 值的編碼值進行更改，使A 值發生變動.

3）更改分配資源：在分配資源階段，隨機選擇step，將確定其A 值的編碼值進行更改，使分配到同一作業的資源發生變動.

3 數值實驗

本文所有算法均運用python3.7 編程實現，測試實驗在Internet Core i5 處理器，3.4 GHz 主頻，8 G 內存的計算機上進行.

3.1 算例構造

考慮到目前在飛機生產中考慮人力資源培訓的調度問題尚無標準測試集，本文對測試問題庫PSPLIB 中算例進行改造，構建測試算例.構建過程如下：1）生成生產項目序列.項目總數N 服從在[10，20]上的均勻分布.項目序列隨機生成，并且為保證生產的連續性，在向項目序列中添加項目時要保證相同項目連續生產不少于4 個.項目中作業個數，作業時間，作業時序關系，作業技能需求均來自于PSPLIB 算例.2）設定=3，每種技能分為3 級，即=3.3）資源柔性度F 表示所有資源掌握的技能數量總和與技能數和資源種類乘積的比值F=.現有資源數量=0.6，各級人員按6:3:1 比例配置.目標資源數量=10，F=0.6，各級人員按3:5:2 比例配置.4）各人員學習效率ar為0.5～0.9 的隨機數.

3.2 算法參數設置

本文所使用的教學算法具有參數設置少的優點，所需確定的參數只有種群規模與迭代次數.種群大小分別取值30、50、70、100，算法在1 000 代終止.如圖2 所示，目標函數值在500 代后未有改進，因此設置算法最大迭代次數500 足以獲得近優解.此外，在種群數量50，70 和100 情況下，500 代后所得近優解的目標函數值非常接近，因此設置算法種群數量為50.

圖2 不同種群數量的收斂曲線Fig.2 Performance comparison of different population sizes

3.3 模型比較

為了說明本文提出多項目下最小化達標項目個數和總成本（MINPRTAC）的模型優越性，將其分別與單項目內最小化投入成本（MIC）和單項目內最大化技能效率增長量（MASG）兩種建模方式進行比較.所比較的指標為資源達標項目個數（NPRT）和投入的總成本（C）.在Pareto 前沿中選取待比較的解時，將原模型內的雙目標轉換為單目標，將資源培訓項目個數轉換為成本，從中選取折算總成本最小的解進行比較，折算總成本計算方式如下：

其中，RD0和RD 分別表示項目未開始時的資源差距和項目結束后的資源差距，資源差距RD 代表著資源培訓所需的最短時間，計算方式如下：

實驗結果如表9 所示.其中，在NRTP 中，“-”代表著全部項目結束后資源仍未達標，括號內數值為項目結束后的資源差距RD.由表9 可知，MIC 由于不能控制資源的技能水平增長，使其成本往往是最高的；而MASG 局限于單項目內，忽略了資源長期發展，使其對資源的培訓也不是最快的.相比之下，本文提出的模型在大部分情況資源可以達到要求且資源培訓速度更快同時成本更低.

表9 模型比較結果Tab.9 Results of model comparison

為對這種情況進行具體的解釋說明，本文以其中某算例進行具體的資源差距和成本變化分析，其結果如圖3 和圖4 所示.由圖3 中可知，在資源培訓上，MASG 初期具有一定的優勢，但隨著項目的進行，其資源差距的減小幅度逐漸變小，并且在所有項目結束后仍未完成，可能原因是其只考慮了資源培訓的增量而沒有考慮資源培訓的方向，導致了培訓方向上的偏差.并且其一直考慮資源效率的增長，忽略了成本，使其成本一直都很高.在成本方面，由圖4 可知，MIC 在初期具有一定優勢，但這種優勢逐漸被本文模型所趕超，并且資源也沒有培訓完成.相比較之下，MINRTP 在初期的成本高，資源效率增幅比較小，但是由于其培訓了正確的資源，使其在后續的進展中，資源能夠達到要求并且成本也能控制下來，體現了整體建模的優越性.

圖3 資源差距比較Fig.3 Resource gap comparison

從實際角度看，在復雜設備裝配過程中，人力資源的在線培訓是普遍存在的.對管理者來說，應當舍棄短期內培訓更多低水平資源的策略，而應該明確各人力資源的長期培訓目標，才能制定更優的培訓路徑以更快完成目標進行更靈活的調度.

3.4 算法比較

為了驗證本文算法HMOTLBO（A0）的有效性，將其與原始的多目標教學算法（MOTLBO，A1）和帶精英策略的非支配選擇遺傳算法（NSGA-Ⅱ，A2）進行比較.根據正交實驗，NSGA-Ⅱ算法種群規模為100，交叉率為0.8，變異率為0.1.比較指標有三種，Pareto 解的個數（N），平均理想距離（MID），間距指標（SP）.其中，MID 越小，表明算法收斂性越好；SP 越小，表明算法多樣性越佳.實驗結果如表10 所示，可以觀察到，本文HMOTLBO 算法在三項指標上都優于NSGA-Ⅱ算法，并且隨著問題規模增加，算法優越性也在增加.與傳統的MOTLBO 相比，雖小部分算例性能相近，但大部分情況下要優于MOTLBO.可以看出本文算法的優越性.

表10 算法比較結果Tab.10 Results of algorithm comparison

以其中一個20 項目算例為例，3 種算法得到的Pareto 解集如圖5 所示，其中項目數21 代表其資源未完成培訓.在解的數量方面，HMOTLBO 和MOTLBO 遠多于NSGA-Ⅱ算法，并且質量也更優.MOTLBO 算法雖然也得到了質量較優的解，但其解的分布與HMOTLBO 相比不夠均勻.

圖5 算法Pareto 解比較Fig.5 Pareto front comparison of 3 algorithms

4 總結

在飛機裝配中，人員的培訓問題常被忽略.本文在目標人員結構給定的情況下，以最小化資源培訓經歷項目個數和最小化總生產成本為目標，對串行項目建立了聯合優化的混合整數規劃模型.針對該問題，設計了新編碼方式的混合多目標教學優化算法.仿真實驗結果表明，本文所建立的模型要優于單項目下最小化成本和最大技能效率增長的建模方式.同時，本文的算法也顯示出一定的優越性.由于不同的企業階段目標、觀點不同，本文為決策者提供了一組可行的Pareto 解，決策者可以從中選出最符合企業目標的人員培訓方案，在保證作業的基礎上提高企業的競爭力.本文考慮的人員技能效率增長模型采用了經典的指數學習曲線，未來可以進一步研究人員技能效率的評定以及具體變化.