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

陸志強　陳丞

摘? ?要：在飛機移動裝配線中，人力資源的技能水平可以通過一定時間的學習培訓得到提升. 針對該現象，提出了在已知期望人力資源結構條件下考慮柔性資源技能進化的多項目組合調度問題，建立了以最小化達到目標人力資源結構所需項目個數和投入總成本為目標的混合整數規劃模型. 針對該模型，設計了一種多層鏈表結構編碼方式的混合多目標教學優化算法，并結合鄰域搜索提高算法的局部搜索能力. 最后，通過實驗數據結果驗證了本文模型與算法的有效性.

關鍵詞：人力資源結構;人員培訓;項目調度;多目標優化

中圖分類號：F273? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標志碼：A

Multi-project Portfolio Scheduling Problem Considering

Skill Evolution of Flexible Resource

LU Zhiqiang CHEN Cheng

（School of Mechanical Engineering，Tongji University，Shanghai 201804，China）

Abstract：In the aircraft mobile assembly line，the skill level of human resources can be improved through a certain period of learning by doing. For this phenomenon，a multi-project portfolio scheduling problem considering the skill evolution of flexible resource under the known expected human resource structure is proposed，and a mixed integer programming model is established to minimize the number of projects and the total input cost required to achieve the target human resource structure. To solve this model，a hybrid multi-objective teaching optimization algorithm with multi-layer linked list structure encoding is designed，and the neighborhood search is combined to improve the local search ability of the algorithm. Finally，the results of experimental data verify the effectiveness of this model and algorithm.

Key words：human resource structure;staff training;project scheduling;multi-objective optimization

目前，大型設備裝配過程的調度問題可以被抽象為資源受限項目調度問題[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.3? ?技能效率與技能增長模型

1.4? ?數學模型

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

2? ?算法設計原理

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

2.1? ?問題復雜性分析

2.2? ?編碼與解碼

2.3? ?教學優化

2.4? ?鄰域搜索

3? ?數值實驗

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

3.1? ?算例構造

3.2? ?算法參數設置

3.3? ?模型比較

3.4? ?算法比較

4? ?總? ?結

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

參考文獻

[1]? ? 陸志強，楊超. 基于項目網絡拆分決策的多項目協同調度問題建模[J]. 上海交通大學學報，2017，51（2）：193.

LU Z Q，YANG C. Modeling of resource constrained multi-project scheduling problem based on project splitting[J]. Journal of Shanghai Jiao Tong University，2017，51（2）：193. （In Chinese）

[2]? ? BELLENGUEZ O，EMMANUEL N. Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills[C]// Practice and Theory of Automated Timetabling V.Berlin，Heidelberg：Springer Berlin Heidelberg，2005：229—243.

[3]? ? LIAN J，LIU C G，LI W J，et al. A multi-skilled worker assignment problem in seru production systems considering the worker heterogeneity[J]. Computers & Industrial Engineering，2018，118：366—382.

[4]? ? BARZ C，KOLISCH R. Hierarchical multi-skill resource assignment in the telecommunications industry[J]. Production and Operations Management，2014，23（3）：489—503.

[5]? ? WALTER M，ZIMMERMANN J. Minimizing average project team size given multi-skilled workers with heterogeneous skill levels[J]. Computers & Operations Research，2016，70：163—179.

[6]? ? 任逸飛，陸志強，劉欣儀. 考慮技能水平的多技能資源約束項目調度[J].浙江大學學報（工學版），2017，5（15）：1000—1006.

REN Y F，LU Z Q，LIU X Y. Project scheduling problem with hierarchical levels of skills[J]. Journal of Zhejiang University （Engineering Science），2017，51（5）：1000—1006. （In Chinese）

[7]? ? MAGHSOUDLOU H，AFSHAR-NADJAFI B，AKHAVAN NIAKI S T. Multi-skilled project scheduling with level-dependent rework risk;three multi-objective mechanisms based on cuckoo search[J]. Applied Soft Computing，2017，54：46—61.

[8]? ? LIU C，WANG J，LEUNG Y T. Worker assignment and production planning with learning and forgetting in manufacturing cells by hybrid bacteria foraging algorithm[J]. Computers & Industrial Engineering，2016，96：162—179.

[9]? ? MEHMANCHI E，SHADROKH S. Solving a new mixed integer non-linear programming model of the multi-skilled project scheduling problem considering learning and forgetting effect on the employee efficiency[C]// 2013 IEEE International Conference on Industrial Engineering and Engineering Management. Bangkok，Thailand：IEEE，2013：400—404.

[10]? CHEN R，LIANG C Y，GU D X，et al. A competence-time-quality scheduling model of multi-skilled staff for IT project portfolio[J]. Computers & Industrial Engineering，2019，139：106183.

[11]? HOSSEINIAN A H，BARADARAN V，BASHIRI M. Modeling of the time-dependent multi-skilled RCPSP considering learning effect[J]. Journal of Modelling in Management，2019，14（2）：521—558.

[12]? JIN H，HEWITT M，THOMAS B W. Workforce grouping and assignment with learning-by-doing and knowledge transfer[J]. International Journal of Production Research，2018，56（14）：4968—4982.

[13]? DE BRUECKER P，BELI？魮N J，VAN DEN BERGH J，et al. A three-stage mixed integer programming approach for optimizing the skill mix and training schedules for aircraft maintenance[J]. European Journal of Operational Research，2017，267（2）：439—452.

[14]? GROSSE E H，GLOCK C H，M？譈LLER S.Production economics and the learning curve：a meta-analysis[J]. International Journal of Production Economics，2015，170（DEC.PT.B）：401—412.

[15]? WRIGHT T P.Factors affecting the cost of airplanes[J].Journal of the Aeronautical Sciences，1936，3（4）：122—128.