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

陸志強　陳丞

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

關(guān)鍵詞：人力資源結(jié)構(gòu);人員培訓;項目調(diào)度;多目標優(yōu)化

中圖分類號：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

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

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

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

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

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

1.1? ?問題描述與基本假設(shè)

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

1.2? ?參數(shù)與變量

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

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

1.4? ?數(shù)學模型

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

2? ?算法設(shè)計原理

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

2.1? ?問題復雜性分析

2.2? ?編碼與解碼

2.3? ?教學優(yōu)化

2.4? ?鄰域搜索

3? ?數(shù)值實驗

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

3.1? ?算例構(gòu)造

3.2? ?算法參數(shù)設(shè)置

3.3? ?模型比較

3.4? ?算法比較

4? ?總? ?結(jié)

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

參考文獻

[1]? ? 陸志強，楊超. 基于項目網(wǎng)絡(luò)拆分決策的多項目協(xié)同調(diào)度問題建模[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]? ? 任逸飛，陸志強，劉欣儀. 考慮技能水平的多技能資源約束項目調(diào)度[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.