MRO服务中心多技能员工优化调度模型

删除或更新信息，请邮件至freekaoyan#163.com(#换成@)

本站小编 Free考研考试/2020-03-23

陈迪, 孙福权, 刘士新
东北大学信息科学与工程学院, 辽宁沈阳 110819
收稿日期: 2015-04-28
基金项目: 国家自然科学基金资助项目(71171038，61333006)..
作者简介: 陈迪(1982-),女,辽宁锦州人,东北大学博士研究生;
孙福权(1964-),男,辽宁北镇人,东北大学教授;
刘士新(1968-),男,辽宁调兵山人,东北大学教授，博士生导师。

摘要: MRO服务企业如何科学合理地调配资源直接影响收益.从MRO服务提供商视角，综合考虑员工旅行费用和工作时间成本，研究为分布于不同地理位置的客户的设备提供维修服务的多技能员工的优化调度问题，建立了以维修成本最小化为目标的多技能员工优化调度的非线性整数规划模型.根据整数变量的特点将非线性模型进行线性化，形成线性整数规划模型，进而使用ILOG CPLEX优化软件进行编程求解.通过具有不同参数特征的大量仿真实验案例，验证了模型的合理性和有效性.
关键词：RO服务中心多技能员工调度非线性整数规划
Multi-skilled Workforce Scheduling Model for MRO Service Center
CHEN Di, SUN Fu-quan, LIU Shi-xin
School of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Abstract: The resources scheduled affect the profit of MRO (maintenance,refair and overhaul) service companies directly. From the perspectives of MRO service provider， an optimization scheduling problem of multi-skilled workforce working was studied for customers distributed in different locations. Considering workforce travel cost and time cost, a multi-skilled workforce scheduling optimization model was established to get the minimum total workforce cost, which is an integer nonlinear programming model. According to the characteristics of integer variables, the model was linearized， and solved by means of ILOG CPLEX. Through a large number of simulation experiments with different parameters, the validity of the model was verified.
Key Words: MRO (maintenance,refair and overhaul)service centermulti-skilled workforceschedulingnonlinear integer programming
MRO(maintenance,repair and overhaul)是设备在使用阶段所进行的各种维护、维修和大修等制造服务活动的总称，是产品全生命周期管理的重要组成部分.MRO与设备及运营密切相关，是企业连续生产非常重要的一环.激烈的全球化竞争对MRO技术提出了新的挑战，MRO也因此成为了国内外学者研究的新热点.
针对MRO的研究从早期的航空运输和军工领域，逐步向轨道交通、制造设备、物流等领域扩展，主要研究内容包括：设备的维护、维修管理活动以及交通工具的优化调度^[1-3]；基于设备运行状态制定设备的维修计划^[4]；MRO的采购与供应服务链设计优化^[5]；MRO信息系统的建模与维护^[6]等.在进行MRO服务活动中，人力资源的优化调度是非常关键的一环，但相关的研究工作却很少，特别是关于多技能员工调度的研究工作更少^[7].在知识经济时代，多技能人力资源是企业的核心资源之一，实现多技能员工的优化调度具有重要的理论研究价值和实际应用价值，因而受到国内外学者的高度关注^[8-10].
本文从MRO服务提供商的视角，综合考虑员工旅行费用和工作时间成本，以维修总成本最小为优化目标，研究员工指派和旅行路径联合优化问题.首先提出了多技能员工优化调度的非线性整数规划模型，进一步根据整数变量的特点将非线性模型线性化.通过大量仿真案例验证了模型的有效性，并分析了问题参数对模型求解难度的影响.
1 问题描述及数学模型1.1 问题描述MRO服务中心多技能员工调度问题(multi-skilled workforce scheduling problem for MRO center，简称MSWSP-MRO)描述如下：MRO服务中心拥有一支多技能维修员工队伍，总人数为 S，员工掌握技能种类总数为 K，服务中心为分布在不同地理位置的 J 项维修任务指派员工.已知任务 j(j = 0,1,…,J)的位置，执行时间d_j，需要的技能种类集合 K_j，对掌握第 k(k = 0,1,2,…,K)种技能员工的需求量 r_jk，其中，j = 0代表处于服务中心的虚工作，k = 0代表员工处于服务中心时使用的虚技能；掌握技能 k 的工人集合 S_k，员工技能对应矩阵为E(E=(e_sk),如果k∈S_k,则e_sk=1,否则e_sk=0,?s∈S,?k∈K);员工 s(s = 1,2,…,S)的单位时间出差成本c_s，每个员工从任务 i 转移到任务 j 的旅行时间 t_ij 和旅行成本c_ij.问题是如何在满足维修任务人力资源要求的前提下指派员工到维修任务，使得旅行成本和工作时间总成本最小.员工工资分为两个部分：基本工资和出差补助，基本工资数额固定，出差补助直接影响MRO服务提供商客户维修总成本，因此，员工在维修中心时属基本工资范畴，不计入本文多技能人员优化调度模型的维修成本计算之中.
根据实际情况，本文给出如下约定：
1) 只有一个服务中心；
2) 维修任务开始时间 h_j 已知；
3) 维修任务开始后不能中断、不能换人；
4) 每位员工同一时间至多只能使用一种技能执行一项维修工作；
5) 员工平时停留在服务中心，只要离开服务中心，在转移路上、服务中心以外的地点等待或者在执行任务均算作出差；
6) 计划展望期为T，从时刻0开始，T=max{h_j+d_j+t_j0|j=1,2,…,J}.
1.2 数学模型在1.1节问题描述的基础上，引入如下决策变量：

目标是实现最小化员工的转移成本和差旅成本之和.因此，目标函数为

(1)

对于每项维修任务j，要求执行期间对各种技能的需求都得到满足，并且任务 j 执行期间的每一阶段对技能员工总需求也要得到满足：

(2)

(3)

对于员工s，则要满足如下约束：

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

约束(4)要求如果员工 s 被指派执行任务 j，那么任务开始后不能中断，直至任务结束员工 s 才能离开；约束(5)要求从计划周期开始时(t = 0时刻)起至任务开始前一天止不能有员工在该任务节点，即员工可以选择回维修中心或者在已完成工作地点等待；约束(6)要求员工在每个任务节点工作时，至多使用一种技能；约束(7)要求员工在每一时刻至多只能存在于一个任务节点；约束(8)～(9)保证员工每次出差旅行构成一个单循环；约束(10)保证同一员工的两个相邻任务时间关系得到满足；约束(11)要求所有员工计划周期开始时(t = 0)都在中心；约束(12)要求所有员工在计划周期结束时全部回到中心.
同时决策变量x_sij和z_stj之间存在相互制约关系：

(13)

决策变量 x_sij，y_sjk 和z_stj的取值范围为

(14)

(15)

(16)

综上，式(1)～式(16)构成求解MSWSP-MRO问题的非线性整数规划模型(NILP).
1.3 NILP约束的线性化MSWSP-MRO优化问题中只有约束(13)是非线性的，而决策变量x_sij和z_stj都是0-1变量，因此可将非线性约束(13)转化为等价的线性约束(17a)～(17c)，从而将非线性模型NILP转化为线性模型ILP.

(17a)

(17b)

(17c)

一方面如果员工 s 执行任务 i 和任务 j，则有z_sti=z_s[t+t_ij]j=1，另一方面员工 s 只有直接从任务 i 到任务 j 时，有x_sij= 1，否则x_sij= 0，因此，可将非线性约束(13)转化为等价的3个线性约束.
1.4 参数定义由于模型求解难度由任务需求和员工技能水平决定，因此，本文定义若干相关参数，并随机生成具有不同参数值的测试案例，以检验模型的求解性能.
定义1 技能需求强度(KRF):

(18)

KRF反映在整个工期中任务对技能的需求强度，KRF越小，技能需求越弱，人员分配限制越松，KRF越大，人员分配限制越紧.
定义2 技能耦合强度(SRF):

(19)

SRF反映每项任务对技能种类的需求情况，SRF越大，说明任务需要的技能种类越多，即任务对技能需求的耦合程度越高，求解越困难.
2 实验与结果2.1 实验数据为了测试模型的有效性，本文设计了多组仿真案例，并使用CPLEX软件进行求解.
实验中员工技能矩阵采用随机生成的方式，在此，引入员工技能水平(skill level)的概念，用SL 来表示.

(20)

SL反映了所有员工掌握技能数量的平均比例.SL越大，说明工作分配时技能员工资源的限制越松；SL越小，说明工作分配时技能员工资源的限制越紧.给定S和SL值后，就可以仿真生成员工技能对应矩阵E.方法如下：
步骤1 生成 S×K的矩阵A_S×K，A中所有元素初始值均为0；
步骤2 按照均匀分布随机生成 b= Random(0,1)，如果b＜ SL，令c= 1，否则c= 0；
步骤3 依次执行 S×K次步骤2，将每次得到的c值逐行逐列依次填入 A；
步骤4 将A传递给E，即得到了一个员工技能水平近似等于SL的一个员工技能对应矩阵E；
步骤5 计算当前实际 SL值，如果当前 SL值低于预期，随机抽取矩阵中为0数据，将其置1；反之，则将1 置0；
步骤6 再次计算 SL值，如果 SL值还不满足要求，跳至步骤5，直至SL值满足要求，程序终止.
在案例生成过程中，设定有J=10项服务任务，计划周期 T=30d.技能员工数S、技能需求强度 SRF和技能耦合强度 KRF参数取值如表 1所示，员工技能矩阵采用随机生成的方式，每名员工最多掌握的技能数为5.表 1中的3项参数分别组合得到27组案例集，每组案例集中包含10个案例，本文共测试270个案例.
表 1(Table 1)

表 1 案例生成参数表Table 1 Parameters for instances

参数		取值
S	8	10	12
SRF	0.4	0.6	0.8
KRF	(0,0.05)	[0.05,0.1]	(0.1,0.3)

表 1 案例生成参数表 Table 1 Parameters for instances

2.2 实验结果针对2.1节生成的仿真案例，使用CPLEX进行求解，求解时间上限设为900s，统计求得最优解的比例，结果参见表 2.表中KRF 取值的3个区间(0，0.05)，[0.05，0.1]，(0.1,0.3)分别用Ⅰ，Ⅱ，Ⅲ表示.
表 2(Table 2)

表 2 不同问题规模及参数特性下求得最优解的比例Table 2 Percentage of instances solved to optimal with different sizes and parameter


SRF-KRF	0.4-Ⅰ	0.4-Ⅱ	0.4-Ⅲ	0.6-Ⅰ	0.6-Ⅱ	0.6-Ⅲ	0.8-Ⅰ	0.8-Ⅱ	0.8-Ⅲ
S = 8	100	96	89	95	92	87	92	85	81
S = 10	100	97	92	96	90	85	94	89	84
S = 12	100	98	94	96	92	88	91	86	82

表 2 不同问题规模及参数特性下求得最优解的比例 Table 2 Percentage of instances solved to optimal with different sizes and parameter

由表 2可见，在员工数S和技能耦合强度SRF值确定的条件下，随着技能需求强度KRF值变大，模型求得最优解的比率降低，即任务技能需求强度越大，员工限制越紧，求解越困难；在S和KRF值确定的条件下，SRF值变大时求得最优解的比率降低，即任务的技能需求变紧，员工的技能种类耦合度要求变高，求解难度随之增大；在SRF和KRF值确定的条件下，变换员工数目，模型在求得最优解的比率上并未体现出明显的规律.可见随着技能需求强度和技能耦合强度的增大，员工技能限制越紧，求解越困难，因此，技能需求强度和技能耦合强度是影响模型求解效率的主要因素.
对于每个仿真算例，CPLEX求解后输出的最优解包括维修总成本和x_sij，y_sjk，z_stj决策变量的取值，从而得到完整的人员调度方案.因此，MRO服务提供商可根据实际情况确定人员调度方案.
3 结语本文针对MRO服务中心多技能员工调度问题建立了非线性整数规划模型，目标实现维修总成本最小，根据整数变量特点将非线性整数规划模型转化为线性模型，通过仿真算例验证了模型的有效性.面对具有设备集成度高、服务需求多和位置分散等特点的现代设备服务模式，选择合适的维修人员，制定合理的调度方案，是MRO服务提供商提升企业竞争力的重要保证.
MRO服务提供模式是一种新型的服务供应模式，针对该问题的研究还处于初始阶段，特别是对于MRO服务模式下的多技能人力资源管理的研究更是稀少，而当今社会人力资源已成为企业的核心资源，是企业在激烈的市场竞争中脱颖而出的重要决定因素，因此，本文研究成果将对MRO服务中心人力资源管理水平的提升具有参考价值.
参考文献

[1]	Moubray J. Reliability-centered maintenance[M].New York: Industrial Press, 1997.(0)
[2]	Ashutosh S, Pratap K J M. Maximum utilization of vehicle capacity:a case of MRO items[J].Computers & Industrial Engineering, 2008, 54(2): 185–201.(0)
[3]	Seo J H, Bai D S. An optimal maintenance policy for a system under periodic overhaul[J].Mathematical and Computer Modeling, 2004, 39(4/5): 373–380.(0)
[4]	Mayank P, Ming J Z, Ramin M, et al. Selective maintenance for binary systems under imperfect repair[J].Reliability Engineering and System Safety, 2013, 113: 42–51.(0)
[5]	Mclaughlin P, Durazo-Cardenas I. Cellular manufacturing applications in MRO operations[J].Procedia CIRP, 2013, 11: 254–259.(0)
[6]	Zhu H H, Gao J, Li D B, et al. A web-based product service system for aerospace maintenance,repair and overhaul services[J].Computers in Industry, 2012, 63(4): 338–348.(0)
[7]	Pan K,Zhang D,Gu X J,et al.A three-phase approach to service staff assignment for MRO task[C]//Proceedings of IIE Asian Conference 2011.Shanghai:Shanghai Jiaotong University Press,2011:612-622.(0)
[8]	Heimerl C, Kolisch R. Work assignment to and qualification of multi-skilled human resources under knowledge depreciation and company skill level targets[J].International Journal of Production Research, 2010, 48(13): 3759–3781.(0)
[9]	Firat M, Hurkens C A J. An improved MIP-based approach for a multi-skill workforce scheduling problem[J]. Journal of Scheduling, 2012, 15(3): 363–380.(0)
[10]	Golalikhani M, Karwan M H. A hierarchical procedure for multi-skilled sales force spatial planning[J].Computers & Operations Research, 2013, 40(5): 1467–1480.(0)