考虑柔性资源技能进化的多项目组合调度问题

陆志强　陈丞

摘   要：在飞机移动装配线中，人力资源的技能水平可以通过一定时间的学习培训得到提升. 针对该现象，提出了在已知期望人力资源结构条件下考虑柔性资源技能进化的多项目组合调度问题，建立了以最小化达到目标人力资源结构所需项目个数和投入总成本为目标的混合整数规划模型. 针对该模型，设计了一种多层链表结构编码方式的混合多目标教学优化算法，并结合邻域搜索提高算法的局部搜索能力. 最后，通过实验数据结果验证了本文模型与算法的有效性.

关键词：人力资源结构;人员培训;项目调度;多目标优化

中图分类号：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.