考虑员工请假情形的多技能分布式资源受限多项目反应型调度优化

doi:10.16381/j.cnki.issn1003-207x.2022.2456

摘要/Abstract

摘要：

在以人力资源为主要资源的项目中，员工请假会使项目执行过程中资源可用量下降，导致事先制订的基线调度计划遭到破坏，采用反应型调度方法可以对被破坏的基线调度计划进行有效修复。针对员工请假情形的多技能分布式资源受限多项目调度问题（MS-DRCMPSP），建立包括初始局部调度、全局协调决策和修复调度的三阶段决策模型，初始局部调度模型和全局协调决策模型用于制订初始的基线调度计划，当员工请假导致基线调度计划遭到破坏时，管理者根据对活动和员工的决策偏好修复被破坏的基线调度计划，设计包含等待和调整策略的动态策略制订修复调度计划；基于MPSPLIB问题库改编生成多技能多项目调度问题算例，开展详细的实验研究。研究结果表明：考虑修复前后员工工作时间偏差最小的修复目标时，可使用等待或动态策略进行修复；考虑平均项目延期及修复前后活动开始时间偏差最小的修复目标时，可使用调整或动态策略进行修复；综合考虑活动和员工两方面的修复目标时，可直接使用动态策略完成修复调度计划。求解大规模算例时，本文设计的基于冲突活动的softmax评分机制的修复算法优于序贯博弈算法及其余启发式算法，优化结果最大可提升14.48%。

关键词: 多技能人力资源, 分布式决策, 多项目, 反应型调度, 修复策略

Abstract:

In the distributed decision-making environment， the shared resources are considered multi-skilled staff， independently dispatched by the respective project decision-makers from their interests. The shared multi-skilled staff， as the only link between multiple projects， are uniformly coordinated and distributed by the coordination manager. An effective coordination mechanism based on staff characteristics is designed to allocate shared multi-skilled staff for multi-project activities and determine the activity’s start time. This problem is called Multi-Skilled Distributed Resource Constrained Multi-Project Scheduling Problem （MS-DRCMPSP）. In these staff-oriented projects， the staff leave will reduce the available resources during project execution， destroying the pre-established baseline scheduling plan. How to repair the damaged baseline scheduling plan with a reactive scheduling method is studied.To solve the distributed resource-constrained multi-project scheduling problem with the multi-staff leave， a three-stage decision model including initial local scheduling， global coordination decision-making， and repaired schedule is established. The first two models are used to formulate the initial baseline scheduling plan. The initial local scheduling stage takes minimizing the project makespan as the optimization goal， and the global coordination decision-making model takes minimizing the average project delay （APD） as the optimization goal. When the baseline scheduling plan is damaged due to staff leave， the manager designs the repaired objective according to the decision preference of activities and staff to repair the damaged baseline scheduling plan. A “dynamic” strategy， including “waiting” and “adjusting” strategies is designed to develop the repaired scheduling plan， and a softmax scoring mechanism based on conflict activities is designed to apply in the repaired scheduling plan. The softmax scoring mechanism includes a series of evaluation factors： activity duration， slack time， resource demand， and several immediate activities.An example of a multi-skilled scheduling problem is generated based on MPSPLIB and experimental research is carried out on this example. The research shows that when considering the repaired objectives of staff working time deviation before and after the repairing， the “waiting” or “dynamic” strategy can be applied； When considering the minimizing repaired objectives of the APD and the deviation of activities start time before and after repairing， the “adjusting” or “dynamic” strategy can be applied； When considering the minimizing repaired objectives of both activities and staff， the “dynamic” strategy can be directly used to complete the repaired scheduling plan； When solving large-scale examples， the three-stage algorithm of softmax scoring mechanism based on conflicting activities is superior to sequential game algorithm and other heuristic algorithms. The optimization results can be improved by 14.48% at most.The vacancy of the multi-skilled scheduling problem in the distributed decision-making environment is made up for， especially in the case of uncertain resource availability. In addition， it provides a suitable repaired strategy for managers' different preferences and the related reference for subsequent relevant researches.

Key words: multi-skilled staff, distributed decision, multi-project, reactive scheduling, repaired strategy

中图分类号:

N945

于懿宁, 徐哲, 赵松, 李飞飞. 考虑员工请假情形的多技能分布式资源受限多项目反应型调度优化[J]. 中国管理科学, 2025, 33(8): 131-143.

Yining Yu, Zhe Xu, Song Zhao, Feifei Li. Research on the Distributed Resource-constrained Multi-project Reactive Scheduling Problem Considering Multi-skilled Staff Leave[J]. Chinese Journal of Management Science, 2025, 33(8): 131-143.

图/表 19

表1

符号及说明"

符号	说明
$P$	项目集合， $i ∈ P, P = {1,2, …, m}$
$V i$	项目 $i$ 的活动集合， $j ∈ V i, V i = {J i - 1 + 1, …, J i}$
$a i j$	项目 $i$ 的活动 $j$ ， $i ∈ P, ∀ j ∈ V i$
$E i j$	$a i j$ 的紧前活动集合
$t$	时刻序号， $t = 0,1, 2, …, T$ ， $T$ 为项目计划期上限
$s$	技能序号， $s = {1,2, …, S}$ ， $S$ 为技能种类
$R i k$	项目 $i$ 对局部资源 $k$ 的可用量
$l g s$	掌握技能 $s$ 的全局资源 $g$ 的水平
$r i j k$	$a i j$ 对局部资源 $k$ 的需求量
$r i j s$	$a i j$ 对技能 $s$ 的需求量
$d ¯ i j$	$a i j$ 的计划工期
$C P D i$	项目 $i$ 的关键路径工期
$v i j s$	布尔变量，表示 $a i j$ 需要技能 $s$ 时为1；否则，为0
$N L g s$	布尔变量，表示全局资源 $g$ 掌握技能 $s$ 时为1；否则，为0
$x i j t$	决策变量，表示 $a i j$ 在 $t$ 时刻完成时为1；否则，为0
$y i j t g s$	决策变量，表示 $g$ 在 $t$ 时刻使用技能 $s$ 执行 $a i j$ 时为1；否则，为0
$z g s t$	决策变量，表示 $g$ 在 $t$ 时刻使用技能 $s$ 时为1；否则，为0
$ϕ g t$	决策变量，表示 $g$ 在 $t$ 时刻请假为1；否则，为0

表1

图1

图2

图3

表2

“活动-技能-资源”信息矩阵"

活动						技能	人力资源
$a 11$	$a 12$	$a 13$	$a 21$	$a 22$	$a 23$	技能	$g 1$	$g 2$	$g 3$	$g 4$	$g 5$
1			2			$s 1$	1	0.8		0.6
	2			1		$s 2$	0.8		1	0.8	0.6
		3			1	$s 3$	0.6	0.6	0.8		1

表2

表3

t=3.5时刻的softmax评分相关信息"

评价因素	活动
评价因素	$a 13$	$a 22$	$a 23$
计划工期	3	3	2
计划松弛时间	0	0	1
资源需求量	3	1	1
紧后活动个数	0	0	0
Total_softmax	1.9121	2.5926	2.4953

表3

表4

t=3.5时刻的“活动-资源-技能”信息"

活动			技能	人力资源
$a 22$	$a 23$	$a 13$	技能	$g 1$	$g 2$	$g 3$	$g 4$	$g 5$
			$s 1$	1	0.8		0.6
1			$s 2$	0.8		1	0.8	0.6
	1	3	$s 3$	0.6	0.6	0.8		1

表4

图4

表5

策略一的softmax评分相关信息"

评价因素	活动
评价因素	$a 13$	$a 21 *$
剩余实际工期	3	0.5
实际松弛时间	0	0
资源需求量	3	2
紧后活动个数	0	2
Total_softmax	0.9640	3.0360

表5

图5

表6

策略二的softmax评分相关信息"

评价因素	活动
评价因素	$a 12 *$	$a 21 *$
剩余实际工期	0.5	0.5
实际松弛时间	0	0
资源需求量	2	2
紧后活动个数	1	2
Total_softmax	1.7689	2.2311

表6

图6

表7

表8

表9

表10

图7

表 11

图8

参考文献 36

[1]	Bellenguez O， Néron E. Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills［C］// Proceedings of the International Conference on the Practice and Theory of Automated Timetabling， Pittsburgh， PA USA， August 18-20， Springer，2004：18-20.
[2]	Kahn K B， Barczak G， Nicholas J， et al. An examination of new product development best practice［J］. Journal of Product Innovation Management， 2012， 29（2）： 180-192.
[3]	Singh A. Resource constrained multi-project scheduling with priority rules & analytic hierarchy process［J］. Procedia Engineering， 2014， 69： 725-734.
[4]	Wu M C， Sun S H. A project scheduling and staff assignment model considering learning effect［J］.The International Journal of Advanced Manufacturing Technology， 2006， 28（11）： 1190-1195.
[5]	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.
[6]	芦鹏宇，孙文俊，井瑞. 基于时间片段的多IT项目人力资源调度问题求解［J］. 系统工程理论与实践，2012，32（4）： 731-737.
	Lu P Y， Sun W J， Jing R. Time slice based solution for human resource scheduling problem of multiple IT projects［J］. Systems Engineering - Theory & Practice. 2012， 32（4）： 731-737.
[7]	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.
[8]	Lau J S K， Huang G Q， Mak K L， et al. Distributed project scheduling with information sharing in supply chains： Part I-an agent-based negotiation model［J］. International Journal of Production Research， 2005， 43（22）： 4813-4838.
[9]	Lau J S， Huang G Q， Mak K L， et al. Distributed project scheduling with information sharing in supply chains： Part II-theoretical analysis and computational study［J］. International Journal of Production Research， 2005， 43（23）： 4899-4927.
[10]	Lau J S K， Huang G Q， Mak K L， et al. Agent-based modeling of supply chains for distributed scheduling［J］. IEEE Transactions on Systems， Man， and Cybernetics-Part A： Systems and Humans， 2006， 36（5）： 847-861.
[11]	Confessore G， Giordani S， Rismondo S. A market-based multi-agent system model for decentralized multi-project scheduling［J］. Annals of Operations Research， 2007， 150（1）： 115-135.
[12]	李飞飞，徐哲，于静.基于序贯博弈谈判机制的分布式多项目调度［J］. 系统工程理论与实践， 2018， 38（3）： 696-709.
	Li F F， Xu Z， Yu J. A sequential game-based negotiation approach to distributed multi-project scheduling problem［J］. Systems Engineering - Theory & Practice. 2018， 38（3）： 696-709.
[13]	刘东宁，徐哲，李飞飞. 基于合作博弈协商机制的分布式资源受限多项目调度［J］. 系统工程理论与实践， 2019， 39（6）： 1507-1516.
	Liu D N， Xu Z， Li F F. Distributed resource constrained multi-project scheduling problem with cooperative-game based negotiation mechanism［J］. Systems Engineering - Theory & Practice， 2019， 39（6）： 1507-1516.
[14]	Homberger J. A multi‐agent system for the decentralized resource-constrained multiproject scheduling problem［J］.International Transactions in Operational Research， 2007， 14（6）： 565-589.
[15]	Homberger J. A （μ， λ）-coordination mechanism for agent-based multi-project scheduling［J］. OR Spectrum， 2012， 34（1）： 107-132.
[16]	赵松，徐哲，刘东宁.考虑全局资源闲置成本的RCMPSPTT［J］.系统工程理论与实践， 2020， 40（7）： 1882-1894.
	Zhao S， Xu Z， Liu D N. Decentralized RCMPSPTT with cost of idleness［J］. Systems Engineering-Theory & Practice， 2020， 40（7）： 1882-1894.
[17]	Zhao S， Xu Z. New closed-loop approximate dynamic programming for solving stochastic decentralized multi-project scheduling problem with resource transfers［J］.Expert Systems with Applications， 2021， 185（15）： 115593.
[18]	赵松，徐哲，刘东宁. 地域分散型多项目时间/成本权衡问题［J］. 中国管理科学， 2023， 31（9）： 62-72.
	Zhao S， Xu Z， Liu D N. Time/cost trade-off problem in decentralized multi-project scheduling［J］. Chinese Journal of Management Science， 2023， 31（9）： 62-72.
[19]	Yu Y， Xu Z， Liu D， et al. A two-stage approach with soft max scoring mechanism for a multi-project scheduling problem sharing multi-skilled staff［J］. Expert Systems with Applications， 2022， 203： 117385.
[20]	于懿宁，徐哲，刘东宁.考虑多技能资源的分布式多项目调度问题［J］. 系统工程理论实践， 2020， 40（11）： 2921-2933.
	Yu Y N， Xu Z， Liu D N. Distributed multi-project scheduling problem with multi-skilled staff［J］. Systems Engineering-Theory & Practice， 2020， 40（11）： 2921-2933.
[21]	Leus R， Herroelen W ． Stability and resource allocation in project planning［J］. IIE Transactions，2004，36（7）： 667-682．
[22]	李佳媛，何正文. 基于资源缓冲的鲁棒性多模式项目调度优化［J］.工业工程与管理，2013， 18（3）： 49-55．
	Li J Y， He Z W. Robust multi-mode project scheduling optimization based on resource buffering［J］. Industrial Engineering and Management， 2013， 18（3）： 49-55．
[23]	Lambrechts O， Demeulemeester E， Herroelen W. Proactive and reactive strategies for resource-constrained project scheduling with uncertain resource availabilities［J］. Journal of Scheduling， 2008， 11（2）： 121-136.
[24]	陈蓉，梁昌勇，叶春森，等. 考虑随机离职的新产品研发项目组合多技能员工调度模型［J］. 系统工程理论实践， 2018， 38（1）： 164-176.
	Chen R， Liang C Y， Ye C S， et al. A multi-skilled staff scheduling model for new product R&D project portfolio under stochastic turnover［J］. Systems Engineering- Theory & Practice，2018，38（1）： 164-176.
[25]	刘振元，袁慧涛，周成，等. 多技能资源时间窗约束下可中断项目调度的分支定界算法［J］. 系统工程理论与实践， 2019， 39（1）： 183-199.
	Liu Z Y， Yuan H T， Zhou C， et al. Branch-and-bound based approach for preemptive project scheduling with time-window constraints on multi-skilled resources［J］. Systems Engineering-Theory & Practice. 2019， 39（1）： 183-199.
[26]	Barreto A， de O Barros M， Werner C M L. Staffing a software project： A constraint satisfaction and optimization-based approach［J］. Computers & Operations Research， 2008， 35（10）： 3073-3089.
[27]	张沙清，陈新度，陈庆新，等.基于优化资源流约束的模具多项目反应调度算法［J］. 系统工程理论与实践， 2011， 31（8）： 1571-1580.
	Zhang S Q， Chen X D， Chen Q X， et al. Reactive scheduling algorithm for multiple mould and die projects based on optimized resource ow constraints［J］. Systems Engineering-Theory & Practice， 2011， 31（8）： 1571-1580.
[28]	Cheng J， Ji J， Guo Y， et al. Dynamic multi objective software project scheduling optimization method based on firework algorithm［J］. Mathematical Problems in Engineering， 2019， 2019（1）： 8405961.
[29]	Xiao J， Osterweil L J， Wang Q， et al. Dynamic resource scheduling in disruption-prone software development environments［C］//Proceedings of the International Conference on Fundamental Approaches to Software Engineering， Paphos， Cyprus， March 20-28，2010.
[30]	Xiao J， Osterweil L J， Wang Q， et al. Disruption-driven resource rescheduling in software development processes［C］// Proceedings of the International Conference on Software Process， Paderborn， Germany， July 8-9，2010.
[31]	Shen X， Minku L L， Bahsoon R， et al. Dynamic software project scheduling through a proactive-rescheduling method［J］. IEEE Transactions on Software Engineering， 2016， 42（7）： 658-686.
[32]	Felberbauer T， Gutjahr W J， Doerner K F. Stochastic project management： Multiple projects with multi-skilled human resources［J］. Journal of Scheduling， 2019， 22（3）： 271-288.
[33]	王全兴. 劳动法［M］. 北京：法律出版社， 2008.
	Wang Q X. Labor law［M］. Beijing： Law Press， 2008.
[34]	Bishop C M， Nasrabadi N M. Pattern recognition and machine learning［M］. New York： Springer， 2006.
[35]	Wang M， Liu G， Lin X. Dynamic optimization of the multi-skilled resource-constrained project scheduling problem with uncertainty in resource availability［J］. Mathematics， 2022，10（17）： 3070.
[36]	Snauwaert J， Vanhoucke M. A new algorithm for resource-constrained project scheduling with breadth and depth of skills［J］. European Journal of Operational Research， 2021， 292（1）：43-59.

问题集	问题规模	算例个数	项目数	活动数
MP30_2	60	5	2	30
MP90_2	180	5	2	90
MP30_5	150	5	5	30
MP90_5	450	5	5	90
MP30_10	300	5	10	30
MP90_10	900	5	10	90

问题集	等待策略	调整策略	动态策略
MP30_2	2.61	2.89	2.05
MP90_2	0.32	0.34	0.28
MP30_5	0.53	0.51	0.48
MP90_5	0.34	1.28	0.33
MP30_10	0.64	0.82	0.69
MP90_10	0.23	0.24	0.23

问题集	等待策略	调整策略	动态策略
MP30_2	47.29	56.24	37.05
MP90_2	40.68	37.75	36.75
MP30_5	23.14	23.2	23.03
MP90_5	35.77	36.54	35.41
MP30_10	63.22	59.7	59.56
MP90_10	92.79	91.76	89.75

问题集	等待策略	调整策略	动态策略
MP30_2	93.30	91.40	69.90
MP90_2	82.57	79.67	79.09
MP30_5	46.30	46.16	45.12
MP90_5	71.08	71.16	70.04
MP30_10	124.19	119.39	118.21
MP90_10	190.22	188.94	182.54

α=1	Softmax	SGNM	LST	LFT	MINSLK	Gap(%)
MP30_2	69.90	67.20	78.54	85.36	89.75	-3.86
MP90_2	79.70	78.40	90.5	95.34	96.18	-1.63
MP30_5	45.10	43.85	45.46	45.82	44.63	-2.77
MP90_5	70.00^*	75.73	73.82	76.52	71.55	8.52
MP30_10	101.50^*	118.68	111.02	117.97	116.72	14.48
MP90_10	154.30^*	178.42	167.48	173.76	171.79	13.52